2.5Counting functions, self-dual functions and completeness
The idea
There is a fixed number of Boolean functions for n variables, and some special families (self-dual, monotone). Functional completeness asks whether a set of gates can build everything.
Think of it like this: Counting recipes: each of the 2ⁿ rows can independently be 0 or 1.
Why it exists
GATE asks "how many functions" and "which set is functionally complete" as short conceptual questions.
How it works
- Each truth table row is free to be 0 or 1, so there are 2^(2ⁿ) functions.
- A self-dual function must give opposite values on rows i and 2ⁿ − 1 − i, so only half the rows are free: 2^(2ⁿ⁻¹).
- A set is complete if it can express NOT and one of AND or OR (or if it is NAND or NOR alone).
- Sets built only from monotone gates (AND, OR) or only XOR and AND are not complete.
Worked example: Functions of 3 variables
Eight rows, each 0 or 1: 2⁸ = 256 functions, of which 2⁴ = 16 are self-dual.
Now play with it
- →Set n = 2 and see 16 functions and 4 self-dual ones.
- →Read the completeness table and find why {AND, OR} fails.
n = 2 gives 16 functions, n = 3 gives 256 functions and 16 self-dual ones.
| Set of operations | Complete? | Why |
|---|---|---|
| {AND, NOT} | yes | OR from De Morgan |
| {OR, NOT} | yes | AND from De Morgan |
| {NAND} | yes | NOT, then AND |
| {NOR} | yes | NOT, then OR |
| {AND, OR} | no | all monotone, no inversion |
| {XOR, AND} | no | cannot make 1 or NOT (all 0-preserving) |
| {XOR, AND, constant 1} | yes | NOT x = x ⊕ 1 |
Check yourself
The number of distinct Boolean functions of 3 variables is
Exam notes (the dense version)
There are 2^(2ⁿ) distinct Boolean functions of n variables (16 for n = 2, 256 for n = 3). A function is self-dual if F(x₁…xₙ) = F′(x₁′…xₙ′): the rows i and 2ⁿ − 1 − i must have opposite values, so there are 2^(2ⁿ⁻¹) of them. A set of operations is functionally complete if it contains functions that are non-monotone, non-self-dual, non-linear, and neither 0-preserving nor 1-preserving. {AND, NOT}, {OR, NOT}, {NAND}, {NOR} are complete; {AND, OR} and {XOR, AND} (without constants) are not.
Previous year questions: Boolean Algebra, Canonical Forms & K-Maps (27)
PYQs are grouped by topic, so this is the full set for Boolean Algebra, Canonical Forms & K-Maps; try the ones that match this subtopic. Open all 27 on the topic page.