0
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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