Proving Tautology in Logical Expressions

A tautology in logic is a statement that is always true, regardless of the truth values of its components. In this article, we will explore how to prove that the following expression is a tautology:

[p ∨ q] ∧ [p → r] ∧ [q → r] → r

Step-by-Step Proof

To show that the expression

[p ∨ q] ∧ [p → r] ∧ [q → r] → r

is a tautology, we will use logical equivalences and laws. Let's break down the proof into steps.

Step 1: Rewrite Implications

First, we rewrite the implications:

p → r ≡ ?p ∨ r
q → r ≡ ?q ∨ r

Step 2: Substitute the Implications

Substituting these into our original expression, we get:

(p ∨ q) ∧ (?p ∨ r) ∧ (?q ∨ r) → r

Step 3: Rewrite Using Implication Equivalence

Using the equivalence:

A → B ≡ ?A ∨ B

We rewrite the expression as:

?[(p ∨ q) ∧ (?p ∨ r) ∧ (?q ∨ r)] ∨ r

Step 4: Apply De Morgan's Laws

Applying De Morgan's Laws to the negation:

?[(p ∨ q) ∧ (?p ∨ r) ∧ (?q ∨ r)] ≡ (?p ∧ ?q) ∨ (p ∧ ?r) ∨ (q ∧ ?r)

Step 5: Combine with r

Now we combine this with (r):

(?p ∧ ?q) ∨ (p ∧ ?r) ∨ (q ∧ ?r) ∨ r

Step 6: Analyze the Cases

We can analyze the cases for (r):

If (r) is true:

In this case, the entire expression is true, regardless of the other components.

If (r) is false:

The expression simplifies to:

(?p ∧ ?q) ∨ (p ∧ ?r) ∨ (q ∧ ?r)

In this case, for the entire expression to hold, (p ∨ q) must be false, which means both (p) and (q) are false, satisfying (?p ∧ ?q).

Conclusion:

Thus, if (r) is false, (p) and (q) must also be false, leading to a contradiction because the original expression (p ∨ q) would be false. Therefore, the given expression is always true regardless of the truth values of (p), (q), and (r).

Hence, we conclude that the expression

(p ∨ q) ∧ (p → r) ∧ (q → r) → r

is a tautology.

Revisiting the Simplified Proof

We are given that all of the following are true:

p ∨ q

p → r

q → r

So we assert the first expression:

p ∨ q

We can then AND each disjunct with another true expression without changing its truth value:

(p ∧ (p → r)) ∨ (q ∧ (q → r))

Applying modus ponens to each side:

r ∨ r

By idempotence of OR:

r Q.E.D.