I'm trying to find the CNF of the $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q))$, and afterwards proving it's validity. As i'm new to CNF i wanted to ensure i've found the right CNF before trying to move on, so for $(p \rightarrow q) \rightarrow p$:

the normal from is: $p \rightarrow q \wedge q \rightarrow p$

and it's valid?

  • 4
    $\begingroup$ The CNF shouldn't contain the "$\rightarrow$" operation $\endgroup$ – HEKTO Dec 3 '18 at 23:03

Your formula is incorrect as CNF. Conjunctive normal form (CNF) is a normal form like

$$ (a_1 \vee \neg a_2 \vee \dots \vee a_n) \wedge (\neg b_1 \vee \dots \vee b_m) \wedge \dots \wedge (c_1 \vee \dots \vee c_l) $$

therefore a formula in CNF has only literals (i.e. atoms or negated atoms), $\wedge$, and $\vee$. It doesn't have $\to$.

If it's allowed to transform $p \to q$ to its equivalent formula $(\neg p) \vee q$, you can use this for the first step to convert a given formula to a CNF formula.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.