10 · Beyond the Slides (GATE extras)

Not in the Neso Chapter 1 deck

These topics are not in your slides but do show up in GATE logic / digital-logic questions. Learn them after notes 01–09.


1. Counting formulas

Quantity (n variables)Count
Rows in a truth table
Distinct Boolean functions (= non-equivalent formulas)
Self-dual functions
Neutral functions (exactly half the rows T)

Example

  • 2 variables → binary connectives (∧, ∨, →, ↔, ⊕, NAND, NOR, … are 7 of these).
  • 3 variables → functions.

Counting satisfying assignments

For NAT questions like “how many assignments satisfy F”, split on one variable and count each branch — faster than a full table. Total rows minus falsifying rows is often quicker for → and ∨ formulas.


2. Normal forms

  • Literal: or
  • DNF (Disjunctive Normal Form) = OR of ANDs = sum of products — e.g.
  • CNF (Conjunctive Normal Form) = AND of ORs = product of sums — e.g.
  • PDNF / canonical DNF = OR of minterms (one per T row, every variable appears)
  • PCNF / canonical CNF = AND of maxterms (one per F row)

Conversion steps

  1. Eliminate ↔:
  2. Eliminate →:
  3. Push ¬ inward (De Morgan, double negation)
  4. Distribute: ∧ over ∨ for DNF; ∨ over ∧ for CNF

← DNF Distribute : ← CNF

PDNF and PCNF of

T rows: (T,T), (F,T), (F,F) → PDNF F row: (T,F) → PCNF (A maxterm is the negation of the falsifying row: row p=T, q=F → .)

Facts

  • minterms in PDNF + maxterms in PCNF .
  • A formula is a tautology ⟺ its PDNF has all minterms (PCNF is empty).
  • A CNF is a tautology ⟺ every clause contains some and — easy to check.
  • A DNF is satisfiable ⟺ some term doesn’t contain both and — easy to check.

3. Functional completeness

A set of connectives is functionally complete if every Boolean function can be written using only those connectives.

SetComplete?Reason
{¬, ∧, ∨}✅DNF uses only these
{¬, ∧}✅
{¬, ∨}✅
{¬, →}✅
{→, F}✅
{NAND} ↑✅universal gate
{NOR} ↓✅universal gate
{∧, ∨}❌can’t make ¬ (monotone)
{∧, ∨, →, ↔}❌all T in ⇒ T out (T-preserving), so no ¬
{→}❌T-preserving
{¬, ↔} / {¬, ⊕}❌affine (linear) — can’t build ∧

Post's criterion (quick test)

A set is complete iff for each of these 5 properties, at least one connective in the set lacks it:

  1. T-preserving (all inputs T ⇒ output T)
  2. F-preserving (all inputs F ⇒ output F)
  3. Monotone
  4. Self-dual
  5. Affine (expressible with ⊕ only)

NAND breaks all five alone — that’s why it’s universal.

NAND / NOR constructions

NAND (↑)NOR (↓)
¬p
p ∧ q
p ∨ q

NAND and NOR are not associative: .


4. Duality

For a formula using only ¬, ∧, ∨, T, F, its dual swaps ∧ ↔ ∨ and T ↔ F (¬ and variables unchanged).

  • Principle of duality: if then . Every law in 08 Logical Equivalences comes in dual pairs (a)/(b).
  • Example: dual of is .
  • A function is self-dual if . E.g. ¬p and majority(p,q,r) are self-dual; ∧ is not.

Express → first

Dual is defined for ¬/∧/∨ formulas. To take the dual of , rewrite as → dual .


  • SAT (is a CNF satisfiable?) is NP-complete (Cook–Levin). 3-SAT is NP-complete.
  • 2-SAT is in P (polynomial time).
  • TAUTOLOGY (is a formula valid?) is co-NP-complete.

Prev ← 09 Rules of Inference · Next → 11 GATE PYQs