Section 1.4 Predicate Logic
71
15. (4x)P(x) ` (E x)[P(x)]′ S (E x)Q(x)
16. (4x)[S(x) S (E y)(P(x,y) ` T( y))] ` (E x)(C(x) ` S(x)) S (E x)(E y)(C(x) ` T( y) ` P(x, y))
In Exercises 17–30, either prove that the wff is a valid argument or give an interpretation in which it is false.
17. (E x)[A(x) ` B(x)] S (E x)A(x) ` (E x)B(x)
18. (E x)[R(x) ~ S(x)] S (E x)R(x) ~ (E x)S(x)
19. (E x)P(x) ` (E x)(E y)Q(x, y) S (E x)(E y)[P(x) ` Q(x, y)]
20. (4x)[P(x) S Q(x)] S [(4x)P(x) S (4x)Q(x)]
21. (4x)(P(x))′ S (4x)(P(x) S Q(x))
22. [(4x)P(x) S (4x)Q(x)] S (4x)[P(x) S Q(x)]
23. (E x)(4y)Q(x, y) S (4y)(E x)Q(x, y)
24. (4x)P(x) ~ (E x)Q(x) S (4x)[P(x) ~ Q(x)]
25. (4x)[A(x) S B(x)] S [(E x)A(x) S (E x)B(x)]
26. (4y)[Q(x, y) S P(x)] S [(E y)Q(x, y) S P(x)]
27. [P(x) S (E y)Q(x, y)] S (E y)[P(x) S Q(x, y)]
28. (4x)(P(x) ~ Q(x)) ` (E x)Q(x) S (E x)P(x)
29. (E x)[P(x) ` Q(x)] ` (4y)[Q( y) S R( y)] S (E x)[P(x) ` R(x)]
30. (4x)(4y)[(P(x) ` S(x, y)) S Q( y)] ` (E x)B(x) ` (4x)(B(x) S P(x)) ` (4x)(E y)S(x, y) S (E x)Q(x)
31. The Greek philosopher Aristotle (384–322 b.c.e.) studied under Plato and tutored Alexander the Great. His
studies of logic influenced philosophers for hundreds of years. His four “perfect” syllogisms are identified
by the names given them by medieval scholars. For each, formulate the argument in predicate logic notation and then provide a proof.
a. “Barbara”
All M are P
All S are M
Therefore all S are P
b. “Celarent”
No M are P
All S are M
Therefore no S are P
c. “Darii”
All M are P
Some S are M
Therefore some S are P
d. “Ferio”
No M are P
Some S are M
Therefore some S are not P
Using predicate logic, prove that each argument in Exercises 32–42 is valid. Use the predicate symbols
shown.
32. Some plants are flowers. All flowers smell sweet. Therefore, some plants smell sweet. P(x), F(x), S(x)
71
15. (4x)P(x) ` (E x)[P(x)]′ S (E x)Q(x)
16. (4x)[S(x) S (E y)(P(x,y) ` T( y))] ` (E x)(C(x) ` S(x)) S (E x)(E y)(C(x) ` T( y) ` P(x, y))
In Exercises 17–30, either prove that the wff is a valid argument or give an interpretation in which it is false.
17. (E x)[A(x) ` B(x)] S (E x)A(x) ` (E x)B(x)
18. (E x)[R(x) ~ S(x)] S (E x)R(x) ~ (E x)S(x)
19. (E x)P(x) ` (E x)(E y)Q(x, y) S (E x)(E y)[P(x) ` Q(x, y)]
20. (4x)[P(x) S Q(x)] S [(4x)P(x) S (4x)Q(x)]
21. (4x)(P(x))′ S (4x)(P(x) S Q(x))
22. [(4x)P(x) S (4x)Q(x)] S (4x)[P(x) S Q(x)]
23. (E x)(4y)Q(x, y) S (4y)(E x)Q(x, y)
24. (4x)P(x) ~ (E x)Q(x) S (4x)[P(x) ~ Q(x)]
25. (4x)[A(x) S B(x)] S [(E x)A(x) S (E x)B(x)]
26. (4y)[Q(x, y) S P(x)] S [(E y)Q(x, y) S P(x)]
27. [P(x) S (E y)Q(x, y)] S (E y)[P(x) S Q(x, y)]
28. (4x)(P(x) ~ Q(x)) ` (E x)Q(x) S (E x)P(x)
29. (E x)[P(x) ` Q(x)] ` (4y)[Q( y) S R( y)] S (E x)[P(x) ` R(x)]
30. (4x)(4y)[(P(x) ` S(x, y)) S Q( y)] ` (E x)B(x) ` (4x)(B(x) S P(x)) ` (4x)(E y)S(x, y) S (E x)Q(x)
31. The Greek philosopher Aristotle (384–322 b.c.e.) studied under Plato and tutored Alexander the Great. His
studies of logic influenced philosophers for hundreds of years. His four “perfect” syllogisms are identified
by the names given them by medieval scholars. For each, formulate the argument in predicate logic notation and then provide a proof.
a. “Barbara”
All M are P
All S are M
Therefore all S are P
b. “Celarent”
No M are P
All S are M
Therefore no S are P
c. “Darii”
All M are P
Some S are M
Therefore some S are P
d. “Ferio”
No M are P
Some S are M
Therefore some S are not P
Using predicate logic, prove that each argument in Exercises 32–42 is valid. Use the predicate symbols
shown.
32. Some plants are flowers. All flowers smell sweet. Therefore, some plants smell sweet. P(x), F(x), S(x)