2
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ Seems right to me $\endgroup$
    – angryavian
    Aug 2, 2018 at 5:36

1 Answer 1

3
$\begingroup$

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}

$\endgroup$
3
  • $\begingroup$ would the DNF be the same? $\endgroup$ Aug 2, 2018 at 14:44
  • $\begingroup$ @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. $\endgroup$ Aug 2, 2018 at 16:05
  • $\begingroup$ @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. $\endgroup$ Aug 2, 2018 at 16:08

You must log in to answer this question.

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