Section 1.3 Quantifiers, Predicates, and Validity
57
d. Some Web sites have neither audio nor video.
e. Every Web site either has text or else has both audio and video.
30. Write the negation of each of the following statements.
a. Only students eat pizza.
b. Every student eats pizza
c. Some students eat only pizza.
31. Write the negation of each of the following statements.
a. Some farmer grows only corn.
b. All farmers grow corn.
c. Corn is grown only by farmers.
32. Write the negation of each of the following statements
a. Some child fears all clowns.
b. Some children fear only clowns.
c. No clown fears any child.
33. Explain why each wff is valid.
a. (4x)(4y)A(x, y) 4 (4y)(4x)A(x, y)
b. (E x)(E y)A(x, y) 4 (E y)(E x)A(x, y)
c. (E x)(4y)P(x, y) S (4y)(E x)P(x, y)
d. A(a) S (E x)A(x)
e. (4x)[A(x) S B(x)] S [(4x)A(x) S (4x)B(x)]
34. Give interpretations to prove that each of the following wffs is not valid:
a. (E x)A(x) ` (E x)B(x) S (E x)[A(x) ` B(x)]
b. (4x)(E y)P(x, y) S (E x)(4y)P(x, y)
c. (4x)[P(x) S Q(x)] S [(E x)P(x) S (4x)Q(x)]
d. (4x)[A(x)]′ 4 [(4x)A(x)]′
35. Decide whether each of the following wffs is valid or invalid. Justify your answer.
a. (E x)A(x) 4 ((4x)[A(x)]′)′
b. (4x)P(x) ~ (E x)Q(x) S (4x)[P(x) ~ Q(x)]
36. Decide whether each of the following wffs is valid or invalid. Justify your answer.
a. (4x)A(x) S ((E x)[A(x)]′)′
b. (4x)[P(x) S Q(x)] ` (E x)[P(x) ~ Q(x)] S (E x)[P(x) ` Q(x)]
c. (4x)[P(x) ~ Q(x)] S (4x)P(x) ~ (E y)Q( y)
37. From Example 24c, we know that (4x)[P(x) ` Q(x)] 4 (4x)P(x) ` (4x)Q(x) is valid. From Practice 21, we know that (4x)[P(x) ~ Q(x)] 4 (4x)P(x) ~ (4x)Q(x) is not valid. From Exercise 34a, we
know that (E x)[P(x) ` Q(x)] 4 (E x)P(x) ` (E x)Q(x) is not valid. Explain why (E x)[P(x) ~ Q(x)] 4
(E x)P(x) ~ (E x)Q(x) is valid.
38. A predicate wff is in prenex normal form if all the quantifiers appear at the front of the wff. Write each of
the following expressions as an equivalent wff in prenex normal form.
a. (4x)P(x) ` (4y)Q( y)
b. (4x)(P(x) S (4y)[Q( y) S W(x, y)])
c. (E x)P(x) ` (E x)Q(x)
57
d. Some Web sites have neither audio nor video.
e. Every Web site either has text or else has both audio and video.
30. Write the negation of each of the following statements.
a. Only students eat pizza.
b. Every student eats pizza
c. Some students eat only pizza.
31. Write the negation of each of the following statements.
a. Some farmer grows only corn.
b. All farmers grow corn.
c. Corn is grown only by farmers.
32. Write the negation of each of the following statements
a. Some child fears all clowns.
b. Some children fear only clowns.
c. No clown fears any child.
33. Explain why each wff is valid.
a. (4x)(4y)A(x, y) 4 (4y)(4x)A(x, y)
b. (E x)(E y)A(x, y) 4 (E y)(E x)A(x, y)
c. (E x)(4y)P(x, y) S (4y)(E x)P(x, y)
d. A(a) S (E x)A(x)
e. (4x)[A(x) S B(x)] S [(4x)A(x) S (4x)B(x)]
34. Give interpretations to prove that each of the following wffs is not valid:
a. (E x)A(x) ` (E x)B(x) S (E x)[A(x) ` B(x)]
b. (4x)(E y)P(x, y) S (E x)(4y)P(x, y)
c. (4x)[P(x) S Q(x)] S [(E x)P(x) S (4x)Q(x)]
d. (4x)[A(x)]′ 4 [(4x)A(x)]′
35. Decide whether each of the following wffs is valid or invalid. Justify your answer.
a. (E x)A(x) 4 ((4x)[A(x)]′)′
b. (4x)P(x) ~ (E x)Q(x) S (4x)[P(x) ~ Q(x)]
36. Decide whether each of the following wffs is valid or invalid. Justify your answer.
a. (4x)A(x) S ((E x)[A(x)]′)′
b. (4x)[P(x) S Q(x)] ` (E x)[P(x) ~ Q(x)] S (E x)[P(x) ` Q(x)]
c. (4x)[P(x) ~ Q(x)] S (4x)P(x) ~ (E y)Q( y)
37. From Example 24c, we know that (4x)[P(x) ` Q(x)] 4 (4x)P(x) ` (4x)Q(x) is valid. From Practice 21, we know that (4x)[P(x) ~ Q(x)] 4 (4x)P(x) ~ (4x)Q(x) is not valid. From Exercise 34a, we
know that (E x)[P(x) ` Q(x)] 4 (E x)P(x) ` (E x)Q(x) is not valid. Explain why (E x)[P(x) ~ Q(x)] 4
(E x)P(x) ~ (E x)Q(x) is valid.
38. A predicate wff is in prenex normal form if all the quantifiers appear at the front of the wff. Write each of
the following expressions as an equivalent wff in prenex normal form.
a. (4x)P(x) ` (4y)Q( y)
b. (4x)(P(x) S (4y)[Q( y) S W(x, y)])
c. (E x)P(x) ` (E x)Q(x)