SC/MATH 1019B - HOMEW ORK 1
DUE SEPTEMB ER 20, 2024
Solutions to the problems below must be brought to class on September 20, 2018.
Solutions may by typed or neatly hand written. You must clearly indicate which
problem you are solving. All solutions must be fully justified.
# 1. Show that the conditional statement (p ∧ q) → (p ∨ q) is a tautology both
(a) by using truth tables,
(b) and by applying a chain of logic identities.
In the truth table
p q p ∧ q p ∨ q (p ∧ q) → (p ∨ q)
T T T T T
T F F T T
F T F T T
F F F F T
we see that the last column which corresponds to (p ∧ q) → (p ∨ q) contains only
T . Therefore (p ∧ q) → (p ∨ q) is a tautology.
Alternatively, the chain of logical equivalences
(p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q)
≡ (¬p ∨ ¬q) ∨ (p ∨ q)
≡ ¬p ∨ ¬q ∨ p ∨ q
≡ (¬p ∨ p) ∨ (¬q ∨ q)
≡T∨T
≡T
also demonstrates that (p ∧ q) → (p ∨ q) is a tautology.
# 2. Find the negation of the quantified statement
∃x, ∀y (x < y) ∨ (x > 2) → (xy = 2)
where the symbol ¬ does not appear in the final answer.
!
¬ ∃x, ∀y (x < y) ∨ (x > 2) → (xy = 2) ≡ ∀x, ∃y¬ (x < y) ∨ (x > 2) → (xy =
2)
≡ ∀x, ∃y¬ ¬ (x < y) ∨ (x > 2) ∨ (xy = 2)
≡ ∀x, ∃y (x < y) ∨ (x > 2) ∧ (xy /= 2)
1
DUE SEPTEMB ER 20, 2024
Solutions to the problems below must be brought to class on September 20, 2018.
Solutions may by typed or neatly hand written. You must clearly indicate which
problem you are solving. All solutions must be fully justified.
# 1. Show that the conditional statement (p ∧ q) → (p ∨ q) is a tautology both
(a) by using truth tables,
(b) and by applying a chain of logic identities.
In the truth table
p q p ∧ q p ∨ q (p ∧ q) → (p ∨ q)
T T T T T
T F F T T
F T F T T
F F F F T
we see that the last column which corresponds to (p ∧ q) → (p ∨ q) contains only
T . Therefore (p ∧ q) → (p ∨ q) is a tautology.
Alternatively, the chain of logical equivalences
(p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q)
≡ (¬p ∨ ¬q) ∨ (p ∨ q)
≡ ¬p ∨ ¬q ∨ p ∨ q
≡ (¬p ∨ p) ∨ (¬q ∨ q)
≡T∨T
≡T
also demonstrates that (p ∧ q) → (p ∨ q) is a tautology.
# 2. Find the negation of the quantified statement
∃x, ∀y (x < y) ∨ (x > 2) → (xy = 2)
where the symbol ¬ does not appear in the final answer.
!
¬ ∃x, ∀y (x < y) ∨ (x > 2) → (xy = 2) ≡ ∀x, ∃y¬ (x < y) ∨ (x > 2) → (xy =
2)
≡ ∀x, ∃y¬ ¬ (x < y) ∨ (x > 2) ∨ (xy = 2)
≡ ∀x, ∃y (x < y) ∨ (x > 2) ∧ (xy /= 2)
1
