0
$\begingroup$

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)

$\endgroup$

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thank you. If I understand correctly, the distributed law can be used even if the AND and OR are not the same in both parentheses? $\endgroup$
    – Student17
    Sep 27 at 19:19
  • 1
    $\begingroup$ Yes, the $R$ can be any logical expression. In this case, it is $\lnot A \lor C$. $\endgroup$
    – RobPratt
    Sep 27 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .