Tag Archives: conjunctive normal form

Simple point I had not previously realised about Boolean functions


Here is a typical Boolean truth table:

A    B    S        O

0    0    0        0
0    0    1        0
0    1    0        0
0    1    1        1
1    0    0        1
1    0    1        0
1    1    0        1
1    1    1        1

By now I am sure more than a few will have recognised this as a simple multiplexer circuit, with S as the select line – set S to 1 and the output O is the value of input B, otherwise O is the value of A.

Like me you were probably taught this could be simplified by ORing together all the 1 outputs eg:

(\neg A \wedge B \wedge C) \vee (A \wedge \neg B \wedge \neg C) \vee (A \wedge B \wedge \neg C) \vee (A \wedge B \wedge C)

… which can be further simplified to …

(A \wedge \neg C) \vee (B \wedge C)

Well, I now know this is the disjunctive normal form and that there is also a conjunctive normal form which is, of course, created by ANDing together all the terms that give a 0 output:

(A \vee B \vee C) \wedge (A \vee B \vee \neg C) \wedge (A \vee \neg B \vee C) \wedge (\neg A \vee B \vee \neg C)

which may also be slightly simplified to (A \vee B) \wedge (A \vee \neg B \vee C) \wedge (\neg A \vee B \vee \neg C) .
I know this is a simple observation, but it was new to me! Another thing I picked up from A. K. Dewdney’s book.