SE 500 Fall 2024
HW #8: Predicate Logic; Proofs and Translations from English
Due: 4:00pm, Friday, November 22

1. Let Person be a type whose "universe" is the set of all persons. Consider these three predicates:

• D : Person ⟶ Boolean, where D(x) corresponds to the statement "x owns a dog".
• S : Person ⟶ Boolean, where S(x) corresponds to the statement "x eats spinach".
• L : Person × Person ⟶ Boolean, where L(x,y) corresponds to the statement "x likes y".

Translate each of the following statements into an expression in predicate logic, using the predicates D, S, and L.

(a) Some people who eat spinach also own a dog.

(b) Everyone who owns a dog likes someone other than (her/him)self.

(c) There is a person who dislikes all people who eat spinach.

(d) There is a dog owner who likes everyone who both owns a dog and does not eat spinach.

(e) Every person who both eats spinach and doesn't own a dog dislike everyone who owns a dog.

(f) If everyone likes (her/him)self, then everyone either owns a dog or eats spinach.

(g) If no one both owns a dog and eats spinach, then everyone dislikes all spinach-eaters.

In what follows, all exercises cited by number come from the end of Chapter 9 of Gries & Schneider. In proving a numbered theorem, use only axioms, theorems, and metatheorems that have a smaller number. Keep in mind that the General Laws of Quantification (as expressed in the theorems of Chapter 8) apply to universal and existential quantification.

2. Without making use of Theorem (9.3), prove

Hints: Theorem (9.4a) is proved in the book; (3.60)

3. Do Exercise 9.1, which can be restated as follows:

Suppose that, in place of Axiom (9.5), Gries & Schneider had offered this seemingly weaker version:

Axiom (9.5') Provided that there are no free occurrences of x in P,

Use (9.5') to prove (9.5):

(9.5) Provided that there are no free occurrences of x in P,

Hint: Use Trading (9.3).

4. Do Exercise 9.7, which asks for a proof of Theorem (9.10).

Hint: Don't forget about the theorems in Chapter 8.

5. Do Exercise 9.12, which asks for a proof of Theorem (9.18a) (Generalized DeMorgan).

Hint: Use Axiom (9.17), which defines existential quantification in terms of universal quantification.

6. Do Exercise 9.17, which asks for a proof of Theorem (9.21):

(9.21) Provided that there are no free occurrences of x in P,

Hint: Use Generalized De Morgan to translate existential quantification into universal, do some manipulations, and then translate back to existential quantification.

7. Prove   (∃x |: P ==> Q)  ≡  (∃x |: ¬P) ∨ (∃x |: Q)