# finding the conjunctive normal form of a statement

I am currently trying to find the conjunctive normal form of this statement

$(A \land B) \lor ((\lnot C \lor A) \land \lnot B) \lor B$.

I think I have found the answer but I am unsure if it is correct.

Am I correct in saying the answer is:

$A \lor B \lor \lnot C$

• Seems right to me Aug 2, 2018 at 5:36

Yes, $$A \lor B \lor \lnot C$$ is a conjunctive normal form (CNF) of $$(A \land B) \lor ((\lnot C \lor A) \land \lnot B) \lor B$$.

A way to prove it is just to observe that $$A \lor B \lor \lnot C$$ is a CNF and it is logically equivalent (you can check it by means of truth tables) to $$(A \land B) \lor ((\lnot C \lor A) \land \lnot B) \lor B$$.

An alternative proof is to use logical equivalences as rewriting rules leading from $$(A \land B) \lor ((\lnot C \lor A) \land \lnot B) \lor B$$ to $$A \lor B \lor \lnot C$$. More precisely, observe first that:

\begin{align} ((\lnot C \lor A) \land \lnot B) \lor B &\equiv (\lnot C \lor A \lor B) \land (\lnot B \lor B) &&\text{distributivity law} \\ &\equiv \lnot C \lor A \lor B &&\text{identity law (as \lnot B \lor B is a tautology).} \end{align}

Then (the use of the associativity law below is always implicit), \begin{align} (A \land B) \lor ((\lnot C \lor A) \land \lnot B) \lor B &\equiv (A \land B) \lor (\lnot C \lor A \lor B) &&\text{substitution} \\ & \equiv (A \land B) \lor (A \lor B) \lor \lnot C &&\text{Associative law} \\ &\equiv ((A \lor A \lor B) \land (B \lor A \lor B)) \lor \lnot C && \text{distributivity law} \\ &\equiv ((A \lor B) \land (A \lor B)) \lor \lnot C && \text{idempotent law} \\ &\equiv A \lor B \lor \lnot C &&\text{idempotent law.} \end{align}

• would the DNF be the same? Aug 2, 2018 at 14:44
• @user10168997 - Yes, of course. In this case, your starting formula $(A \land B) \lor ((\lnot C \lor A) \land \lnot B) \lor B$ has a CNF and a DNF that coincide. Aug 2, 2018 at 16:05
• @user10168997 - Pay attention that a CNF of a given formula is not unique, and similarly for DNF. For instance, $A \land (A \lor B \lor \lnot C)$ is a CNF of $(A \land B) \lor ((\lnot C \lor A) \land \lnot B) \lor B$ as well. So, properly speaking it is not clear what you refer to when you talk of the CNF of a given formula. Aug 2, 2018 at 16:08