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
- Eliminate ↔:
- Eliminate →:
- Push ¬ inward (De Morgan, double negation)
- 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
3. Functional completeness
A set of connectives is functionally complete if every Boolean function can be written using only those connectives.
| Set | Complete? | 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:
- T-preserving (all inputs T ⇒ output T)
- F-preserving (all inputs F ⇒ output F)
- Monotone
- Self-dual
- 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 .
5. Complexity links (useful for TOC questions)
- 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