Any set of Boolean operators that is sufficient to represent
Duration: 1 min
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 183 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.