Can anyone help me with this? I'm suppose to use resolution to prove that [(p ? q) ^ (q ? (r ^ s))] ? (p ? s)

Question

I have to use resolution to prove these inferences are valid [(p → q) ^ (q → (r ^ s))] → (p → s) ?

Answer 1

[(p → q) ∧ (q → (r ∧ s))] → (p → s)

 

1. Rewrite each A → B as ¬A ∨ B

 

¬[(¬p ∨ q) ∧ (¬q ∨ (r ∧ s))] ∨ ¬p ∨ s

 

2. Resolve ¬p ∨ q with ¬q ∨ (r ∧ s)

 

¬[¬p ∨ (r ∧ s)] ∨ ¬p ∨ s

 

3. DeMorgan's Law ×2

 

[p ∧ ¬(r ∧ s)] ∨ (¬p ∨ s)

[p ∧ (¬r ∨ ¬s)] ∨ (¬p ∨ s)

 

4. Distributivity of ∧ over ∨.

 

(p ∧ ¬r) ∨ (p ∧ ¬s) ∨ (¬p ∨ s)

 

 

5. DeMorgan's Law

 

(p ∧ ¬r) ∨ ¬(¬p ∨ s) ∨ (¬p ∨ s)

 

6. Disjunction of opposites.

 

(p ∧ ¬r) ∨ TRUE

 

7. Definition of ∨

 

TRUE

 

[(p → q) ∧ (q → (r ∧ s))] → (p → s) is therefore a tautology.