How would I prove this predicate calculus theroem?

Question

[ (P → Q) → ((P → R) ← (Q → R)) ]

Answer 1

There are two ways; I will show you both.

(I) BY CONSIDERING CASES:

Case 1: P is TRUE

The expression [ (P → Q) → ((P → R) ← (Q → R)) ] simplifies to

[ (Q) → ((R) ← (Q → R)) ]

Case 1.1: Q is TRUE (and P is TRUE)

The expression [ (Q) → ((R) ← (Q → R)) ] simplifies to

[ ((R) ← (R)) ]

That simplifies to TRUE.

Case 1.2: Q is FALSE (and P is TRUE)

The expression [ (Q) → ((R) ← (Q → R)) ] simplifies to TRUE.

Case 2: P is FALSE

The expression [ (P → Q) → ((P → R) ← (Q → R)) ] simplifies to

[ (TRUE) → ((TRUE) ← (Q → R)) ]

which simplifies to TRUE.

(II) BY RESOLUTION

Convert the formula into disjunctive normal form:

[ (P → Q) → ((P → R) ← (Q → R)) ]

[ (¬P ∨ Q) → ((¬P ∨ R) ← (¬Q ∨ R)) ]

[ (P ∧ ¬Q) ∨ ((¬P ∨ R) ∨ (Q ∧ ¬R)) ]

[ (P ∧ ¬Q) ∨ ¬P ∨ R ∨ (Q ∧ ¬R) ]

This gives four clauses:

1. P ∧ ¬Q

2. ¬P

3. R

4. Q ∧ ¬R

Resolve 1 and 4:

5. P ∧ ¬R

Resolve 2. and 5.

6. ¬R

Resolve 3. and 6.

7. TRUE