Transform to CNF (conjunctive normal form)

288 Views Asked by At

I am trying to convert the following expression to CNF (conjunctive normal form):

$\left(A\Rightarrow B\right)\Rightarrow\left(A\Rightarrow C\right)$

As my first steps I am removing the implications like so:

$\left(\lnot A ∨ B\right)\Rightarrow\left(\lnot A ∨ C\right)$

$\lnot\left(\lnot A ∨ B\right)∨\left(\lnot A ∨ C\right)$

Removing the negation by applying it to the parentheses:

$\left(A\land\lnot B\right)\vee\left(\lnot A\vee C\right)$

Until here everything is clear for me. This next step where (I think) the distributive law is used is not clear to me:

$\left(A\vee\lnot A \vee C\right)\land\left(\lnot B \vee\left(\lnot A \vee C\right)\right)$

(The answer the teacher gave us)

1

There are 1 best solutions below

2
On BEST ANSWER

Those steps are all correct, and the last step uses the distributed law $$(P \land Q) \lor R \equiv (P \lor R) \land (Q \lor R)$$

What your teacher provided is CNF but can be further simplified because $A\lor \lnot A$ is always true, yielding $\lnot B \lor \lnot A \lor C$.