A set of Boolean connectives is functionally complete if all Boolean functions…
2008
A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?
- A.
EX-NOR
- B.
implication, negation
- C.
OR, negation
- D.
NAND
Attempted by 276 students.
Show answer & explanation
Correct answer: A
Answer: EX-NOR is not functionally complete.
Reason: Equivalence (EX-NOR) is an affine operation. In Boolean algebra, EX-NOR can be written as 1 ⊕ x ⊕ y (equivalently as the negation of XOR). Any composition of affine functions is itself affine. Nonlinear functions such as AND are not affine, so they cannot be produced using EX-NOR alone. Therefore the set containing only EX-NOR is not functionally complete.
implication and negation: functionally complete. Using negation and implication you can form OR by (¬A) → B = A OR B, and then form AND via De Morgan: A AND B = ¬(¬A OR ¬B).
OR and negation: functionally complete. With NOT and OR you get AND by A AND B = ¬(¬A OR ¬B), so all Boolean functions are expressible.
NAND alone: functionally complete. NOT can be obtained as A NAND A, and AND as (A NAND B) NAND (A NAND B); these let you build any Boolean function.
Summary: EX-NOR is the only set listed that is not functionally complete because it yields only affine functions; the other listed sets can express AND, OR, and NOT and therefore are functionally complete.