finding the conjunctive normal form of a statement

404 Views Asked by At

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$

1

There are 1 best solutions below

3
On BEST ANSWER

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}