Hi,
How would you go about showing that the proposition below is a tautology using algebraic manipulation of logical equivalences (not using a truth table)?
( ( p ∨ q) ∧ ( p → r) ∧ ( q → r) ) → r
Thanks!
To show that the given proposition is a tautology using algebraic manipulation of logical equivalences, we need to simplify the proposition step by step until we reach a tautology.
Let's start with the given proposition:
((p ∨ q) ∧ (p → r) ∧ (q → r)) → r
To simplify this proposition, we can use the following logical equivalences:
1. Implication Equivalence: p → q ≡ ¬p ∨ q
2. Distributive Equivalence: (p ∧ q) ∨ r ≡ (p ∨ r) ∧ (q ∨ r)
3. Idempotent Laws: p ∨ p ≡ p
Now, let's simplify the given proposition step by step:
Step 1: Apply the implication equivalence to both (p → r) and (q → r):
( (p ∨ q) ∧ (¬p ∨ r) ∧ (¬q ∨ r) ) → r
Step 2: Use the distributive equivalence to distribute (∧) over (∨):
( ((p ∨ q) ∧ ¬p ∨ r) ∧ ¬q ∨ r ) → r
Step 3: Apply the distributive equivalence again:
( (p ∧ ¬p ∨ q ∧ ¬p ∨ r) ∧ ¬q ∨ r ) → r
Step 4: Use the idempotent laws to simplify p ∧ ¬p and q ∧ ¬p:
( (False ∨ q ∧ ¬p ∨ r) ∧ ¬q ∨ r ) → r
Step 5: Simplify the False ∨ q ∧ ¬p term:
( q ∧ ¬p ∨ r ∧ ¬q ∨ r ) → r
Step 6: Rewrite q ∧ ¬p ∨ r ∧ ¬q as (q ∨ r) ∧ (¬p ∨ r) using the distributive equivalence:
( (q ∨ r) ∧ (¬p ∨ r) ∨ r ) → r
Step 7: Simplify the (¬p ∨ r) ∨ r term using the idempotent laws:
( (q ∨ r) ∨ r ) → r
Step 8: Simplify the (q ∨ r) ∨ r term using the idempotent laws:
( q ∨ r ) → r
Step 9: Apply the implication equivalence to (q ∨ r) → r:
¬(q ∨ r) ∨ r
Step 10: Use De Morgan's Law: ¬(q ∨ r) ≡ ¬q ∧ ¬r
(¬q ∧ ¬r) ∨ r
Step 11: Use the distributive equivalence to distribute (∨) over (∧):
(¬q ∨ r) ∧ (¬r ∨ r)
Step 12: Simplify (¬r ∨ r) using the identity law:
(¬q ∨ r) ∧ True
Step 13: Simplify (¬q ∨ r) using the identity law:
¬q ∨ r
Step 14: Apply the implication equivalence to ¬q ∨ r:
q → r
Since we have obtained q → r as the simplified proposition, which is a known tautology, we can conclude that the initial proposition ((p ∨ q) ∧ (p → r) ∧ (q → r)) → r is also a tautology.
Therefore, using algebraic manipulation of logical equivalences, we have shown that the given proposition is a tautology.