clausal normal form

191 Views Asked by At

I am trying to solve a problem, the solution of which I already have, the thing is that I am not understanding a step in it. Basically I don't get it why this premise (p ⇒ q) ⇒ (q ⇒ r), gets transformed like this {p, ¬q, r} {¬q, r} .

Whole exercise and solution:

Question: Given these premises: p, (p ⇒ q), and (p ⇒ q) ⇒ (q ⇒ r) conclude to r. Breaking down in clausal form:

  1. {p} Premise

  2. {¬p, q} Premise

  3. {p, ¬q, r} Premise
  4. {¬q, r} Premise
  5. {¬r} Premise
  6. {q} 1, 2
  7. {r} 4, 6
  8. {} 5, 7

Thank you very much !!

1

There are 1 best solutions below

0
On

Converting to CNF:

$(p \rightarrow q) \rightarrow (q \rightarrow r) \Leftrightarrow$ (Implication x 3)

$\neg (\neg p \lor q) \lor (\neg q \lor r) \Leftrightarrow$ (De Morgan)

$(p \land \neg q) \lor (\neg q \lor r) \Leftrightarrow$ (Distribution)

$(p \lor \neg q \lor r) \land (\neg q \lor \neg q \lor r) \Leftrightarrow$ (Idempotence)

$(p \lor \neg q \lor r) \land (\neg q \lor r)$

So, you get clauses $\{ p , \neg q , r\}$ and $\{ \neg q , r \}$