I am learning boolean algebra. So apologies for this naive question. During our discussion among friends, we came across following puzzle,

How can I convert following statement into CNF and DNF?

$$ A \wedge \neg A $$

Is it following for CNF? $$ (A \vee A ) \wedge ( \neg A \vee \neg A) $$

Similarly, for DNF, is following correct?

$$ (A \wedge \neg A ) \vee ( A \wedge \neg A ) $$

I tried to use truth table method like shown in this post, but answer to this statement is always false. So how can I build DNF for such statement from truth table?

  • $\begingroup$ Cite a reference for CNF and DNF. You will see that neither of your answers qualify. $\endgroup$ – GEdgar May 30 '20 at 10:46
  • 1
    $\begingroup$ Well, maybe they do qualify, but in fact there is never need for repetition, so $A \wedge \neg A$ is already in CNF and in DNF $\endgroup$ – GEdgar May 30 '20 at 10:52
  • 1
    $\begingroup$ @GEdgar, is it both? $\endgroup$ – Dexter May 30 '20 at 10:59

The statement $(1)$

$$A\land\lnot A,\tag{1}$$

is already in CNF (conjunctive normal form), and DNF (disjunctive normal form).

All conjunctions of literals and all disjunctions of literals are in CNF, as they can be seen as conjunctions of one-literal clauses and conjunctions of a single clause, respectively. Vice versa for DNF formulas.

$$(A\lor A )\land(\lnot A \lor\lnot A)\tag{2}$$

$$(A \land \lnot A ) \lor ( A \ \land \lnot A )\tag{3}$$

$(2)$ and $(3)$ are in CNF and DNF respectively, however as @GEdgar has pointed out, there is no need for repetition of literals.


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.