1
$\begingroup$

Can i get the CNF of the following expression if i know the DNF?

I've the following expression:

$$\Bigl(\bigl(A\rightarrow (\overline A \land B) \bigr)\land \bigl((\overline A \land B)\rightarrow A\bigr)\Bigr)\rightarrow\bigl(B\land \overline B\bigr)$$

The DNF will be:

$A\rightarrow B \Rightarrow \overline A \lor B:$

$$\Rightarrow\Bigl(\bigl(\overline A \lor(\overline A \land B)\bigr)\land \bigl((A\lor\overline B)\lor A\bigr)\Bigr)\rightarrow \bigl(B\land \overline B\bigr)$$

$\overline A \lor(\overline A \land B) \Rightarrow \overline A$

$(A\lor\overline B)\lor A \Rightarrow A\lor\overline B$

$$\Rightarrow \bigl(\overline A\land (A\lor \overline B)\bigr)\rightarrow (B\land \overline B) $$

$A\rightarrow B \Rightarrow \overline A \lor B:$

$$\Rightarrow\overline{\bigl(\overline A \land(A\lor\overline B)\bigr)}$$

$$\Rightarrow \bigl( A\lor(\overline A\land B)\bigr)$$

$$\Rightarrow (A\lor B)$$

So, As we can see, The DNF of this expression is $A\lor B$, My question: Is it correct to say that the CNF of this expression will be $\overline A\land \overline B$?

I looked at Graham Kemp's Answer for this question, And didn't successfully understood how an expression that has only the operator $\land$ can be both conjunction of two disjunctions of one literal and disjunction of two conjunctions of one literal at the same time.

Because as i know (Please correct me if i wrong), A CNF has the form of $A\land B\land C\land D$ Where $A,B,C,D$ are expressions of the form $x\lor y\lor z$, And DNF has the form of $A\lor B\lor C\lor D$ Where $A,B,C,D$ are expressions of the form $x\land y\land z$.

Thanks for reading the question so far, please correct me if i made any mistake.

Thanks!!!

$\endgroup$
2
  • $\begingroup$ $\overline A\land \overline B$ is a negation of $A\lor B.$ In the given example are DNF and CNF equal. $\endgroup$
    – user376343
    Commented Jan 29, 2019 at 22:44
  • 1
    $\begingroup$ CNF is a product if sums while DNF is a sum of products. In the above case one can consider $A\lor B$ as any of them. $\endgroup$
    – user376343
    Commented Jan 29, 2019 at 22:47

1 Answer 1

1
$\begingroup$

First, the CNF of any expression is equivalent to that expression, and same for the DNF, meaning that the CNF and DNF should always be equivalent to each other as well.

So, if the DNF is $A \lor B$, then the CNF cannot be $\neg A \land \neg B$, since that is the negation of it, i.e. not something that is equivalent.

Ok, so then what is the CNF?

Well, the CNF is just $A \lor B$ as well. Think of it as a conjunctin that consists of a single conjunct. And, since that conjunct is a disjunctin of literals, it fits the definition of CNF just fine.

$\endgroup$

You must log in to answer this question.

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