Page 56 - Discrete Mathematics and Its Applications

1.3 Propositional Equivalences 35

c) Mei walks or takes the bus to class. 29. Show that (p → q) ∧ (q → r) → (p → r) is a tautol-
d) Ibrahim is smart and hard working. ogy.
8. Use De Morgan’s laws to find the negation of each of the 30. Show that (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a tautology.
following statements.
31. Show that (p → q) → r and p → (q → r) are not log-
a) Kwame will take a job in industry or go to graduate ically equivalent.
school. 32. Show that (p ∧ q) → r and (p → r) ∧ (q → r) are not
b) Yoshiko knows Java and calculus.
c) James is young and strong. logically equivalent.
d) Rita will move to Oregon or Washington. 33. Show that (p → q) → (r → s) and (p → r) →
9. Show that each of these conditional statements is a tau- (q → s) are not logically equivalent.
tology by using truth tables. The dual of a compound proposition that contains only the
a) (p ∧ q) → p b) p → (p ∨ q) logical operators ∨, ∧, and ¬ is the compound proposition
c) ¬p → (p → q) d) (p ∧ q) → (p → q) obtained by replacing each ∨ by ∧, each ∧ by ∨, each T
e) ¬(p → q) → p f) ¬(p → q) →¬q by F, and each F by T. The dual of s is denoted by s .
∗
10. Show that each of these conditional statements is a tau- 34. Find the dual of each of these compound propositions.
tology by using truth tables. a) p ∨¬q b) p ∧ (q ∨ (r ∧ T))
a) [¬p ∧ (p ∨ q)]→ q c) (p ∧¬q) ∨ (q ∧ F)
b) [(p → q) ∧ (q → r)]→ (p → r) 35. Find the dual of each of these compound propositions.
c) [p ∧ (p → q)]→ q
d) [(p ∨ q) ∧ (p → r) ∧ (q → r)]→ r a) p ∧¬q ∧¬r b) (p ∧ q ∧ r) ∨ s
11. Show that each conditional statement in Exercise 9 is a c) (p ∨ F) ∧ (q ∨ T)
∗
tautology without using truth tables. 36. When does s = s, where s is a compound proposition?
∗ ∗
12. Show that each conditional statement in Exercise 10 is a 37. Show that (s ) = s when s is a compound proposition.
tautology without using truth tables. 38. Show that the logical equivalences in Table 6, except for
13. Use truth tables to verify the absorption laws. the double negation law, come in pairs, where each pair
a) p ∨ (p ∧ q) ≡ p b) p ∧ (p ∨ q) ≡ p contains compound propositions that are duals of each
14. Determine whether (¬p ∧ (p → q)) →¬q is a tautol- other.
ogy. ∗∗ 39. Why are the duals of two equivalent compound proposi-
15. Determine whether (¬q ∧ (p → q)) →¬p is a tautol- tions also equivalent, where these compound propositions
ogy. contain only the operators ∧, ∨, and ¬?
Each of Exercises 16–28 asks you to show that two compound 40. Find a compound proposition involving the propositional
propositions are logically equivalent. To do this, either show variables p, q, and r that is true when p and q are true
that both sides are true, or that both sides are false, for exactly and r is false, but is false otherwise. [Hint: Use a con-
the same combinations of truth values of the propositional junction of each propositional variable or its negation.]
variables in these expressions (whichever is easier). 41. Find a compound proposition involving the propositional
16. Show that p ↔ q and (p ∧ q) ∨ (¬p ∧¬q) are logically variables p, q, and r that is true when exactly two of p, q,
equivalent. and r are true and is false otherwise. [Hint: Form a dis-
17. Show that ¬(p ↔ q) and p ↔¬q are logically equiva- junction of conjunctions. Include a conjunction for each
lent. combination of values for which the compound proposi-
18. Showthatp → q and¬q →¬p arelogicallyequivalent. tion is true. Each conjunction should include each of the
19. Show that ¬p ↔ q and p ↔¬q are logically equivalent. three propositional variables or its negations.]
20. Show that ¬(p ⊕ q) and p ↔ q are logically equivalent. 42. Suppose that a truth table in n propositional variables is
21. Show that ¬(p ↔ q) and ¬p ↔ q are logically equiva- specified. Show that a compound proposition with this
lent. truth table can be formed by taking the disjunction of
22. Show that (p → q) ∧ (p → r) and p → (q ∧ r) are log- conjunctions of the variables or their negations, with one
ically equivalent. conjunction included for each combination of values for
23. Show that (p → r) ∧ (q → r) and (p ∨ q) → r are log- which the compound proposition is true. The resulting
ically equivalent. compound proposition is said to be in disjunctive nor-
24. Show that (p → q) ∨ (p → r) and p → (q ∨ r) are log- mal form.
ically equivalent. A collection of logical operators is called functionally com-
25. Show that (p → r) ∨ (q → r) and (p ∧ q) → r are log- plete if every compound proposition is logically equivalent to
ically equivalent. a compound proposition involving only these logical opera-
26. Showthat ¬p → (q → r)andq → (p ∨ r)arelogically tors.
equivalent. 43. Show that ¬, ∧, and ∨ form a functionally complete col-
27. Show that p ↔ q and (p → q) ∧ (q → p) are logically lection of logical operators. [Hint: Use the fact that every
equivalent. compound proposition is logically equivalent to one in
28. Show that p ↔ q and ¬p ↔¬q are logically equivalent. disjunctive normal form, as shown in Exercise 42.]