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 start with the proposition and apply a series of logical equivalences to derive a logically equivalent expression that is trivially true.

Let's break down the steps to prove this:

1. Begin with the given proposition: ( ( p ∨ q) ∧ ( p → r) ∧ ( q → r) ) → r

2. Apply the definition of implication: P → Q is equivalent to ¬P ∨ Q. Use this on the (p → r) and (q → r) parts of the proposition, resulting in:
( (p ∨ q) ∧ (¬p ∨ r) ∧ (¬q ∨ r) ) → r

3. Apply the distributive property of ∧ over ∨ to the first part of the proposition:
( (p ∧ (¬p ∨ r) ∨ (q ∧ (¬p ∨ r) ) ) ∧ (¬q ∨ r) ) → r

4. Apply the distributive property of ∨ over ∧ to the first part of the proposition:
( ((p ∧ ¬p) ∨ (p ∧ r) ∨ (q ∧ ¬p) ∨ (q ∧ r)) ∧ (¬q ∨ r) ) → r

5. Apply the law of non-contradiction: P ∧ ¬P is always false. Therefore, we can remove the first part of the proposition:
( (p ∧ r) ∨ (q ∧ ¬p) ∨ (q ∧ r) ) → r

6. Apply the law of absorption: P ∨ (P ∧ Q) is equivalent to P. Use this on the (p ∧ r) part of the proposition, resulting in:
( p ∨ (q ∧ ¬p) ∨ (q ∧ r) ) → r

7. Apply commutativity: (P ∨ Q) is equivalent to (Q ∨ P) to rearrange terms in the proposition:
( p ∨ (¬p ∧ q) ∨ (r ∧ q) ) → r

8. Apply associativity: (P ∨ (Q ∨ R)) is equivalent to ((P ∨ Q) ∨ R). Rearrange terms in the proposition to group common terms:
( (p ∨ ¬p) ∨ (q ∨ q) ∨ (r ∨ r) ) → r

9. Apply the law of non-contradiction: P ∨ ¬P is always true and (Q ∨ Q) is equivalent to Q, for any proposition Q. Remove these parts of the proposition:
( T ∨ T ∨ (r ∨ r) ) → r

10. Apply the law of identity: P ∨ T is always true. Replace the remaining parts of the proposition with T:
( T ) → r

11. Apply the law of identity again: T → P is always true. Replace the remaining part of the proposition with T:
T → r

Since T → r is always true (tautology), we have shown that the initial proposition: ( ( p ∨ q) ∧ ( p → r) ∧ ( q → r) ) → r is a tautology.

Note: This is one possible way of proving the tautology using algebraic manipulation of logical equivalences. There may be alternative approaches that yield the same result.