Forms and complete sets

ACompressed recap

🧾

Minterm (AND, plain where the row has 1), maxterm (OR, primed where 1); F = Σm(1-rows) = ΠM(0-rows); a k-literal term covers 2ⁿ⁻ᵏ minterms. NAND/NOR universal (NAND: NOT 1, AND 2, OR 3, XOR 4); SOP → NAND–NAND, POS → NOR–NOR; Post's five families. 2^(2ⁿ) functions; self-dual 2^(2ⁿ⁻¹); symmetric 2ⁿ⁺¹; XOR chain = odd parity.

BMerged rule card

3.2.1 Canonical forms: minterms, maxterms, SOP and POS

• Minterm mᵢ: AND of all variables, plain where row i has 1. Maxterm Mᵢ: OR of all variables, primed where row i has 1. Mᵢ = mᵢ'.
• F = Σm(1-rows) = ΠM(0-rows); F' = Σm(0-rows).
• Expand a term by multiplying with (X + X') for each missing variable; k of n variables → 2ⁿ⁻ᵏ minterms.
• SOP = OR of AND terms; POS = AND of OR terms; canonical = every term has all variables.

3.2.2 NAND and NOR as universal gates; functionally complete sets

• NAND: NOT = 1, AND = 2, OR = 3, XOR = 4, XNOR = 5 gates. NOR: NOT 1, OR 2, AND 3, XNOR 4, XOR 5.
• SOP → NAND–NAND; POS → NOR–NOR.
• Post: complete ⟺ some gate is not 0-preserving, some not 1-preserving, some not self-dual, some not monotone, some not linear.
• Complete: {NAND}, {NOR}, {AND, NOT}, {OR, NOT}, {XOR, AND, 1}, {→, 0}. Not: {AND, OR}, {XOR, AND}, {→}, {majority, NOT}.

3.2.3 Counting Boolean functions; self-dual functions; XOR tricks

• 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.

CInterleaved GATE-style questions

Q1MCQ1 markCanonical

F(A, B, C) = Σm(0, 3, 5) is equivalent to:

• (A) ΠM(1, 2, 4, 6, 7)
• (B) ΠM(2, 4, 6)
• (C) Σm(1, 2, 4, 6, 7)
• (D) ΠM(0, 3, 5)

Q2NAT1 markExpansion

F(A, B, C, D) = AB + CD. How many minterms does F have?

Numerical answer: ________

Q3MCQ1 markMaxterm

For F(A, B, C, D), the maxterm M₁₀ is:

• (A) AB'CD'
• (B) A' + B' + C' + D'
• (C) A' + B + C' + D
• (D) A + B' + C + D'

Q4NAT1 markNOR count

Minimum number of 2-input NOR gates to build a 2-input AND gate?

Numerical answer: ________

Q5MCQ2 marksCompleteness

The set {→} (implication, A → B = A' + B) with the constant 0 available is:

• (A) not complete, because → preserves 1
• (B) complete, because A → 0 = A' and A' → B = A + B
• (C) not complete, because → is monotone
• (D) complete without the constant too

Q6NAT2 marksCounting

How many functions of 3 variables satisfy F(0, 0, 0) = 0 and F(1, 1, 1) = 1?

Numerical answer: ________

Q7MCQ1 markSelf-dual

Which function is self-dual?

• (A) A'B
• (B) AB
• (C) A + B
• (D) AB + BC + CA

Q8NAT2 marksXOR chain

How many of the 16 rows of A ⊕ B ⊕ C ⊕ D are equal to 1?

Numerical answer: ________

DAnswer Vault