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?
Best Answer
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.