Counting Boolean functions; self-dual functions; XOR tricks

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Is {AND, OR} functionally complete? from Lesson 3.2.2
• How many minterms does a term with k of n variables cover? from Lesson 3.2.1
• What is A ⊕ A? from Lesson 3.1.2

1 · The Hook

🎣

A function of n variables is just a truth table: 2ⁿ rows, each with output 0 or 1. So counting functions is counting ways to fill a column. GATE asks variations: how many functions are self-dual, how many have exactly k minterms, how many treat all inputs alike. Each one is a short counting argument once you see which rows are free.

2 · Predict First

🤔

A function of 2 variables has a truth table with 4 rows. In how many ways can the output column be filled?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Each of 4 rows is 0 or 1: 2⁴ = 16 functions.

🗣️

In plain words

Count the rows (2ⁿ), then ask how many of them you may fill freely. If every row is free, there are 2^(2ⁿ) functions. Conditions tie rows together or fix some of them; count only the free choices.

1. All functions

n variables → 2ⁿ rows → 2^(2ⁿ) functions: n = 2 → 16, n = 3 → 256, n = 4 → 65,536. The 16 two-input functions include 0, 1, A, B, A', B', AND, OR, NAND, NOR, XOR, XNOR, A'B, AB', A' + B (implication) and A + B'.

2. Counting with conditions

Why self-dual is 2^(2ⁿ⁻¹): rows pair up as (row m, its complement row 2ⁿ − 1 − m). Choosing the output for one row of a pair forces the other (it must be the opposite). There are 2ⁿ⁻¹ pairs, each with 2 choices. Why symmetric is 2ⁿ⁺¹: the number of 1-inputs can be 0, 1, …, n (n + 1 cases), each with output 0 or 1.

3. Recognising self-dual functions

F is self-dual when F(A', B', C') = F(A, B, C)'. Quick test: no two complementary rows (m and 7 − m for 3 variables) may both be 1 or both be 0, so a self-dual function of n variables has exactly 2ⁿ⁻¹ minterms.

• Majority AB + BC + CA is self-dual. A ⊕ B ⊕ C is self-dual. AB is not.

4. XOR and XNOR chains

• A ⊕ B ⊕ … ⊕ Z = 1 ⟺ an odd number of inputs are 1.
• (A ⊕ B)' = A ⊙ B (XNOR). A chain of XNORs over an odd number of variables equals the XOR chain: A ⊙ B ⊙ C = A ⊕ B ⊕ C. Over an even number it is the complement: A ⊙ B ⊙ C ⊙ D = (A ⊕ B ⊕ C ⊕ D)'.
• x ⊕ x = 0 and x ⊕ 0 = x, so repeated inputs cancel: A ⊕ B ⊕ A = B.

4 · Visual

A self-dual function of 3 variables: 4 pairs, 2 choices each → 2⁴ = 16 functions.

5 · Worked Examples

Example 1 Easy

How many Boolean functions of 3 variables are there?

Solution

2⁸ = 256.

Example 2 Medium

How many functions of 4 variables have exactly 3 minterms?

Solution

C(16, 3) = 560.

Example 3 GATE

How many self-dual functions of 3 variables are there?

Solution

2^(2²) = 16.

6 · GATE Traps

⚠️

• 2^(2ⁿ), not 2ⁿ or (2ⁿ)²: the exponent is the number of rows.
• Self-dual: 2^(2ⁿ⁻¹) (half the rows are free).
• Symmetric functions: 2ⁿ⁺¹ (n + 1 possible counts of 1-inputs).
• XNOR chains equal XOR chains only for an odd number of inputs.

7 · Memory Hook

🧠

"Count the free rows, raise 2 to it. Self-dual: half the rows. Symmetric: n + 1 counts."

8 · Connect the Dots

Phase 3 is complete. We can write any function in canonical form, but canonical forms are long. Phase 4 finds the shortest SOP and POS, first with Karnaugh maps, then with the tabular (Quine–McCluskey) method.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markAll functions

How many Boolean functions of 2 variables are there?

Numerical answer: ________

Q2NAT2 marksSelf-dual

How many self-dual Boolean functions of 4 variables are there?

Numerical answer: ________

Q3NAT2 marksNeutral

How many functions of 3 variables output 1 in exactly 4 of the 8 rows?

Numerical answer: ________

Q4NAT2 marksSymmetric

How many symmetric Boolean functions of 3 variables are there?

Numerical answer: ________

Q5MCQ1 markXNOR chain

A ⊙ B ⊙ C (XNOR of three variables) equals:

• (A) ABC
• (B) A ⊕ B ⊕ C
• (C) (A ⊕ B ⊕ C)'
• (D) A + B + C

10 · Rule Card

• n variables: 2ⁿ rows, 2^(2ⁿ) functions.
• Exactly k minterms: C(2ⁿ, k). Neutral: C(2ⁿ, 2ⁿ⁻¹). F(0…0) fixed: 2^(2ⁿ − 1).
• Self-dual: 2^(2ⁿ⁻¹) (complementary rows have opposite outputs; exactly 2ⁿ⁻¹ minterms). Symmetric: 2ⁿ⁺¹.
• XOR chain = 1 iff odd number of 1s; XNOR chain = XOR chain for odd n, its complement for even n.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

number of Boolean functionsfunctions with k mintermsneutral functionsself-dual functions and their countsymmetric functions and their countthe 16 two-variable functionsXOR and XNOR chains

12 · Answer Vault