Discrete Mathematics Exercises 9. Predicate Calculus
Shin-Cheng Mu Spring 2013
1. Prove (9.6) (∀x R P ) ≡ P ∨ (∀x ¬R), provided ¬occurs(x, P ).
Solution: Proof. P ∨ (∀x ¬R) = = { distributivity (9.5), since ¬occurs(x, P ) } (∀x P ∨ ¬R) { trading (9.3a) } (∀x R P )
2. Prove the weakening/strengthening rules (9.10) (∀x Q ∨ R P ) ⇒ (∀x Q P ) and (9.11) (∀x R P ∧ Q) ⇒ (∀x R P ). Hint: you may need the range splitting or distributivity laws from Chapter 8, as well as weakening/strengthening rules from Chapter 3.
Solution: (9.10) Range weakening/strengthening:
(∀x Q ∨ R P ) ⇒ (∀x Q P ) Proof. (∀x Q ∨ R P ) = ⇒ { range split (8.18), since ∧ idempotent } (∀x Q P ) ∧ (∀x R P ) { weakening (3.76b) } (∀x Q P )
1
(9.11)
Body weakening/strengthening:
(∀x R P ∧ Q) ⇒ (∀x R P ) Proof. (∀x R P ∧ Q) = ⇒ { distributivity (8.15), since P, Q B } (∀x R P ) ∧ (∀x R Q) { weakening (3.76b) } (∀x R P )
3. Prove the trading theorem (9.19): (∃x Q ∧ R P ) ≡ (∃x Q R ∧ P ).
Solution: Proof. (∃x Q ∧ R P ) = = = = { generalized de Morgan (9.17) } ¬(∀x Q ∧ R ¬P ) { trading (9.4b) } ¬(∀x Q ¬R ∨ ¬P ) { generalized de Morgan (9.17) } (∃x Q ¬(¬R ∨ ¬P )) { de Morgan (3.47b), double negation (3.12) } (∃x Q R ∧ P )
4. Prove (9.21) distributivity of ∧ over ∃: (∃x R P ∧ Q) ≡ P ∧ (∃x R Q)) , provided ¬occurs(x, P )
Solution:
Page 2
Proof. (∃x R P ∧ Q) = = = = { generalized de Morgan (9.17), de Morgan (3.47) } ¬(∀x R ¬P ∨ ¬Q) { distributivity (9.5), ¬occurs(x, P ) } ¬(¬P ∨ (∀x R ¬Q)) { de Morgan (3.47) } P ∧ ¬(∀x R ¬Q) { generalized de Morgan (9.17) } P ∧ (∃x R Q)
5. Prove (9.25) range weakening/strengthening: (∃x R P ) ⇒ (∃x Q ∨ R P )
Solution: Proof. (∃x R P ) ⇒ (∃x Q ∨ R P ) = = = { generalized de Morgan (9.17) } ¬(∀x R ¬P ) ⇒ ¬(∀x Q ∨ R ¬P ) { contrapositive (3.61) } (∀x Q ∨ R ¬P ) ⇒ (∀x R ¬P ) { weakening/strengthening (9.10) } true
6. Translate the following English sentences to predicate logic. You may need to define/invent suitable predicates and...
