TAOCP 7.1.1 Exercise 17

The given De Morgan form is a conjunction of terms of the form $\overline{u_{i1}\wedge\cdots\wedge u_{ik_i}}$, followed by a single outer negation.

Section 7.1.1: Boolean Basics

Exercise 17. [10] [10] By De Morgan's laws, a general disjunctive normal form such as (25) is not only an OR of ANDs, it is a NAND of NANDs:

$$\overline{(\overline{u_{11}\wedge\cdots\wedge u_{1k_1}})\wedge\cdots\wedge(\overline{u_{m1}\wedge\cdots\wedge u_{mk_m}})}.$$

A student named J. H. Quick rewrote this expression in the form

$$(u_{11}\mathbin{\bar\wedge}\cdots\mathbin{\bar\wedge} u_{1k_1})\mathbin{\bar\wedge}\cdots\mathbin{\bar\wedge}(u_{m1}\mathbin{\bar\wedge}\cdots\mathbin{\bar\wedge} u_{mk_m}).$$

Was that a good idea?

Verified: yes
Solve time: 1m07s


The given De Morgan form is a conjunction of terms of the form $\overline{u_{i1}\wedge\cdots\wedge u_{ik_i}}$, followed by a single outer negation. Each inner term is a NAND applied to a whole conjunction, and the outer structure is a (binary) NAND iteration over these terms.

The rewritten expression replaces each inner negated conjunction by a chained binary NAND

$(u_{i1}\mathbin{\bar\wedge}\cdots\mathbin{\bar\wedge}u_{ik_i})$. Since $\bar\wedge$ is a binary operation defined by $x\bar\wedge y=\overline{x\wedge y}$, the iterated form depends on parenthesization and does not preserve the value of $\overline{u_{i1}\wedge\cdots\wedge u_{ik_i}}$ in general. For example, $(a\bar\wedge b)\bar\wedge c=\overline{(\overline{a\wedge b})\wedge c}$ differs from $\overline{a\wedge b\wedge c}$ by the identity $(\overline{a}\vee \overline{b})\wedge(\overline{c}\vee a)\wedge(\overline{c}\vee b)$ after simplification, which is not equivalent to $\overline{a}\vee\overline{b}\vee\overline{c}$. Since even the inner grouping is altered, the outer NAND structure no longer corresponds to the stated De Morgan transformation.

The idea is therefore not correct as written, because it treats $\bar\wedge$ as an associative multi-ary operator, while its definition is strictly binary and changes meaning under iteration.