DISCRETE MATHEMATICS

Question

Let p, q, and r be propositions.

(a) Use logical equivalences (De Morgan’s laws, etc.) to show that

¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬q.

(b) Show that (p ⇒ r) ∨ (q ⇒ r) ≡ (p ∧ q)) ⇒ r (use any method you like).

Answer 1

not ( p v ( not p and q)) =

not p and not ( not p and q) =

not p and (p or not q) =

(not p and p) or (not p and not q)=

F or (not p and not q)

the truth value then depends entirely

upon not p and not q =

not (p or q)

[end of proof]

-----------------------------------------------

(not p or R) or (not q or R) <-- implication identity

(not p or not q ) or (R or R) <--- associative

not (p and q) or R <--- deMorgan's;

(p and q) --> R <-- implication identity