0
$\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$
  • $\begingroup$ $\overline A\land \overline B$ is a negation of $A\lor B.$ In the given example are DNF and CNF equal. $\endgroup$ – user376343 Jan 29 '19 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 Jan 29 '19 at 22:47
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.