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.