TUTORIAL 1 - Answers
DISCRETE STRUCTURE - SSK3003 GROUP 5
SEMESTER 1 2019/2020
1. Construct a truth table to prove that the following statements are logically
equivalent:
𝑝 → (𝑞 → 𝑟) ≡ (𝑝 ∧ 𝑞) → 𝑟
Answer:
p q r 𝒒 →𝒓 𝒑 → (𝒒 → 𝒓) (𝒑 ∧ 𝒒) 𝒑 → (𝒒 → 𝒓) ≡ (𝒑 ∧ 𝒒) → 𝒓
0 0 0 1 1 0 1
0 0 1 1 1 0 1
0 1 0 0 1 0 1
0 1 1 1 1 0 1
1 0 0 1 1 0 1
1 0 1 1 1 0 1
1 1 0 0 0 1 0
1 1 1 1 1 1 1
∴ 𝑝 → (𝑞 → 𝑟) is logically equivalent to (𝑝 ∧ 𝑞) → 𝑟
Prepared by: Dr. Normalia Samian
2. Construct a truth table for the following logical statement. State whether it is a
tautology or not.
[ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)] ↔ [ 𝑝 ∨ (𝑞 ∧ 𝑟)]
Answer:
p q r 𝒑∨𝒒 𝒑∨𝒓 (𝒑 ∨ 𝒒) ∧ (𝒑 ∨ 𝒓) 𝒒∧𝒓 𝒑 ∨ (𝒒 ∧ 𝒓) ↔
0 0 0 0 0 0 0 0 1
0 0 1 0 1 0 0 0 1
0 1 0 1 0 0 0 0 1
0 1 1 1 1 1 1 1 1
1 0 0 1 1 1 0 1 1
1 0 1 1 1 1 0 1 1
1 1 0 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1
∴ [ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)] ↔ [ 𝑝 ∨ (𝑞 ∧ 𝑟)] is a tautology.
Prepared by: Dr. Normalia Samian
3. Given p = True, q = False, and r = True. Evaluate the following statement:
[ 𝑝 ∧ (𝑝 → 𝑞) ∧ 𝑟] → [(𝑝 ∨ 𝑞) → 𝑟]
Answer:
[ 𝑝 ∧ (𝑝 → 𝑞) ∧ 𝑟] → [(𝑝 ∨ 𝑞) → 𝑟]
= [ 𝑇 ∧ (𝑇 → 𝐹) ∧ 𝑇] → [(𝑇 ∨ 𝐹) → 𝑇]
= [ 𝑇 ∧ 𝐹 ∧ 𝑇] → [(𝑇 → 𝑇)] by implication and disjunction
=𝐹→𝑇 by implication and conjunction
=𝑇 by implication
Prepared by: Dr. Normalia Samian
4. Write the truth table for the proposition:
¬ (𝑟 → ¬ 𝑞) ∨ (𝑝 ∧ ¬ 𝑟)
Answer:
p q r ¬𝒒 ¬𝒓 (𝒓 → ¬ 𝒒) ¬ (𝒓 → ¬ 𝒒) (𝒑 ∧ ¬ 𝒓) ∨
T T T F F F T F T
T T F F T T F T T
T F T T F T F F F
T F F T T T F T T
F T T F F F T F T
F T F F T T F F F
F F T T F T F F F
F F F T T T F F F
Prepared by: Dr. Normalia Samian
5. By using logical equivalence, show that ¬ (𝑝 ∨ ¬𝑞) ≡ 𝑞 ∧ ¬𝑝.
Answer:
¬ (𝑝 ∨ ¬𝑞)
≡ ¬𝑝 ∧ ¬¬𝑞 De Morgan’s law
≡ ¬𝑝 ∧ 𝑞 Double negation law
≡ 𝑞 ∧ ¬𝑝 Commutative law
Prepared by: Dr. Normalia Samian
6. Simplify each of the following by using law of logic.
a) ¬(𝑝 ∨ 𝑞) ∨ (¬𝑝 ∧ 𝑞)
b) ¬(¬𝑝 → ¬𝑞)
Answer (a)
¬(𝑝 ∨ 𝑞) ∨ (¬𝑝 ∧ 𝑞)
= (¬𝑝 ∧ ¬𝑞) ∨ (¬𝑝 ∧ 𝑞) De Morgan’s Law
= ¬𝑝 ∧ (¬𝑞 ∨ 𝑞) Distributive Law
= ¬𝑝 ∧ 𝑇 Negation Law
= ¬𝑝 Identity Law
Answer (b)
¬(¬𝑝 → ¬𝑞)
= ¬(¬¬𝑝 ∨ ¬𝑞) from table
= ¬(𝑝 ∨ ¬𝑞) Double negation
= ¬𝑝 ∧ ¬¬𝑞 De Morgan
= ¬𝑝 ∧ 𝑞 Double negation
7. Using the truth table method, determine whether a given propositional logic is
a tautology, a contradiction or a contingency. Provide a precise justification for
your answer.
(p→q)→(p ∨(p →q))
Prepared by: Dr. Normalia Samian
Answer (b)
¬(¬𝑝 → ¬𝑞)
= ¬(¬¬𝑝 ∨ ¬𝑞) By Implication
= ¬(𝑝 ∨ ¬𝑞) Double negation
= ¬𝑝 ∧ ¬¬𝑞 De Morgan’s Law
= ¬𝑝 ∧ 𝑞 Double negation
Prepared by: Dr. Normalia Samian
Prepared by: Dr. Normalia Samian
