Finding a logically equivalent conjunctive normal form.

Question

Here is the definition of a conjunctive normal form:

A conjunctive normal form is a conjunction of one or more conjuncts that are disjunctions of one or more literals (letters). For example, $A \land (B \lor A) \land (\lnot B \lor A)$ is a conjunctive normal form.

I need to find a logically equivalent conjunctive normal form of the expression $\lnot (A \to B) \lor (\lnot A \land C)$. The answer in the textbook is $(A \lor C) \land (\lnot B \lor \lnot A) \land (\lnot B \lor C)$. I don't understand how they got this answer.

Can another answer be $A\land (\lnot B\lor \lnot A)\land C$?

Answer 1

Conditional Negation, Distribution, Complementation, and Identity.

$\begin{align} &\neg (A\to B)\vee(\neg A\wedge C)\\\equiv ~& (A\wedge\neg B)\vee(\neg A\wedge C)\\\equiv~& (A\vee\neg A)\wedge(A\vee C)\wedge(\neg B\vee \neg A)\wedge(\neg B\vee C)\\\equiv~& \qquad\qquad\quad(A\vee C)\wedge(\neg B\vee \neg A)\wedge(\neg B\vee C)\end{align}$

I am not sure how you figured this would be equivalent to $A\wedge(\neg B\vee\neg A)\wedge C$, because it is not.

Answer 2

$$ \begin{align} &\neg (A\to B)\vee (\neg A\wedge C)\\ &= \neg(B \vee \neg A )\vee (\neg A\wedge C)\\ &=(\neg B \vee A )\vee (\neg A\wedge C)\\ &=((\neg B \wedge A) \vee \neg A)\wedge ((\neg B \wedge A) \vee C)\\ &=(\neg B \vee \neg A) \wedge (A \vee \neg A)\wedge (\neg B \vee C) \wedge (A \vee C)\\ &=(\neg B \vee \neg A) \wedge (T)\wedge (\neg B \vee C) \wedge (A \vee C)\\ \end{align} $$

How can we justify these equalities:

1) Definition of $\rightarrow$. $x\rightarrow y = (y\vee \neg x)$

2) Distribute $\neg$. We can find that $\neg(x \vee y)=\neg x \wedge \neg y$

3) Demorgan's law. $x \wedge (y\vee z)=(x\vee y) \wedge (x\vee z) $

4) More application of Demorgan's law.

5) Tautology $x \vee \neg x =T$

Then you arrive at your conclusion after we remove this Tautology and rearrange.

You can verify that $(A,B,C)= (T,T,F)$ satisfies the expression above. but it doesn't satisfy $A\wedge (\neg B \vee\neg A) \wedge C$. This would be one way to assure yourself that these expressions aren't equal.

Answer 3

The formula $A \land (\lnot B \lor \lnot A)\land C$ is not logically equivalent to the formula $(A\lor C) \land (\lnot B \lor \lnot A) \land (\lnot B \lor C)$: take for instance the truth assignment $v$ such that $v(A) = \top$ and $v(B) = v(C) = \bot$, then $A \land (\lnot B \lor \lnot A)\land C$ is false for $v$ but $(A\lor C) \land (\lnot B \lor \lnot A) \land (\lnot B \lor C)$ is true for $v$. Therefore, it is impossible that both formulas are simultaneously conjunctive normal forms (CNF) of $\lnot (A\to B)\lor (\lnot A\land C)$.

Which one is a CNF of $\lnot (A\to B)\lor (\lnot A\land C)$? To discover it, I use the logical equivalences listed here as rewriting rules for forumlas.

1. First step: eliminate implication. \begin{align} \lnot (A\to B)\lor (\lnot A\land C) &\equiv \lnot (\lnot A \lor B)\lor (\lnot A\land C) \end{align}

2. Second step: move NOTs inwards by applying De Morgan's law and double negation law. \begin{align} \lnot (\lnot A \lor B)\lor (\lnot A\land C) &\equiv (\lnot\lnot A \land \lnot B)\lor (\lnot A\land C) \\ &\equiv (A \land \lnot B)\lor (\lnot A\land C) \end{align}

3. Third step: apply the distribution law, identity law and commutativity. \begin{align} (A \land \lnot B)\lor (\lnot A\land C) &\equiv ((A \land \lnot B) \lor \lnot A) \land ((A \land \lnot B) \lor C)\ &\text{distr.} \\ &\equiv (A \lor \lnot A) \land (\lnot B \lor \lnot A ) \land ((A \land \lnot B) \lor C) &\text{distr.} \\ &\equiv (\lnot B \lor \lnot A ) \land ((A \land \lnot B) \lor C) &\text{ident.} \\ &\equiv (\lnot B \lor \lnot A ) \land (A \lor C) \land (\lnot B \lor C ) &\text{distr.} \\ &\equiv (A\lor C) \land (\lnot B \lor \lnot A) \land (\lnot B \lor C) &\text{comm.} \end{align} where the identity law can be applied because $A \lor \lnot A$ is a tautology.

Therefore, $\lnot (A\to B)\lor (\lnot A\land C) \equiv (A\lor C) \land (\lnot B \lor \lnot A) \land (\lnot B \lor C)$ and we can conclude that $(A\lor C) \land (\lnot B \lor \lnot A) \land (\lnot B \lor C)$ is a CNF of $\lnot (A\to B)\lor (\lnot A\land C)$ because $(A\lor C) \land (\lnot B \lor \lnot A) \land (\lnot B \lor C)$ is in CNF.