2
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Cite a reference for CNF and DNF. You will see that neither of your answers qualify. $\endgroup$
    – GEdgar
    Commented May 30, 2020 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
    Commented May 30, 2020 at 10:52
  • 1
    $\begingroup$ @GEdgar, is it both? $\endgroup$
    – Dexter
    Commented May 30, 2020 at 10:59

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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