Any set of Boolean operators that is sufficient to represent all Boolean…
2018
Any set of Boolean operators that is sufficient to represent all Boolean expressions is said to be complete. Which of the following is not complete?
- A.
{ AND, OR }
- B.
{ AND, NOT }
- C.
{ NOT, OR }
- D.
{ NOR }
Attempted by 179 students.
Show answer & explanation
Correct answer: A
A set of Boolean operators is functionally complete if it can express all possible Boolean functions. Sets like {AND, NOT}, {OR, NOT}, {NAND}, and {NOR} are complete. However, the set {AND, OR} is not functionally complete because it cannot represent the NOT operation. Any combination of AND and OR operations results in a monotonic function, whereas NOT is non-monotonic. Therefore, {AND, OR} cannot generate all Boolean expressions.
A video solution is available for this question — log in and enroll to watch it.