Try
A small access rule has two inputs: p means “the pass is present” and q means “the supervisor approves.” In this synthetic example, access is granted when the two inputs agree. The table, rather than a remembered formula, is the specification. Can you construct a formula that accepts exactly its two permitted rows?
Boolean values are 0 for false and 1 for true. The symbol ¬ means NOT, ∧ means AND, and ∨ means OR. An assignment of values to all inputs is called a valuation. A formula represents a specification when it produces the specified result at every valuation, not merely at the cases tried so far.
| p | q | Grant access | Row-specific construction |
|---|
| 0 | 0 | 1 | True-row term: ¬p ∧ ¬q |
|---|
| 0 | 1 | 0 | False-row clause: p ∨ ¬q |
|---|
| 1 | 0 | 0 | False-row clause: ¬p ∨ q |
|---|
| 1 | 1 | 1 | True-row term: p ∧ q |
|---|
Predict
The term ¬p ∧ ¬q is true only at row 00. Predict what happens if we OR it with p ∧ q. Then predict whether changing that OR to AND preserves the rule. It does not: no valuation makes both complete terms true, so the AND would reject every row.
There is a second route. Instead of collecting permitted rows, exclude each forbidden row. To exclude 01, use p ∨ ¬q: both literals are false at 01, while at least one is true at every other row. A clause for excluding a row uses the opposite literal polarity to a term for accepting that row. Merely copying the row’s bits is not enough.
Experiment
On paper, write the two formulas
D = (¬p ∧ ¬q) ∨ (p ∧ q) and C = (p ∨ ¬q) ∧ (¬p ∨ q).
Add two columns to the supplied table and evaluate D and C at every row. For each accepted row of D, underline the term that accepts it. For each rejected row of C, circle the clause that rejects it. This supplies a visible witness for each output instead of an unexplained final column.
Now change the specification at row 01 to grant access. Predict the edit before calculating: D gains the term ¬p ∧ q, while C loses the clause p ∨ ¬q. Verify all four rows again. Removing a rejection clause weakens a conjunction; adding an acceptance term enlarges a disjunction. Explain why neither edit changes the other three rows.
These are complete finite checks for this two-input specification. They are not empirical tests of how an actual security system behaves, nor evidence that the chosen access policy is appropriate.
Understand
A literal is a variable or its negation. Disjunctive normal form, DNF, is an OR of AND terms of literals. Conjunctive normal form, CNF, is an AND of OR clauses of literals. Single literals are allowed as terms or clauses. General normal forms need not mention every variable in every term or clause and need not be unique.
For a finite variable set V, a complete minterm Mₐ describes one valuation a: for each variable v, use v if a assigns 1 and ¬v if a assigns 0, then AND all these literals. At any valuation b, every literal is true exactly when b agrees with a on every variable. Thus Mₐ is true exactly at a.
A complete maxterm Cₐ excludes a: use ¬v when a assigns 1 and v when a assigns 0, then OR the literals. All its literals are false exactly at a. If b differs from a, the literal for a differing variable is true, so the clause accepts b.
Let f be any Boolean specification on these valuations. OR together Mₐ for every a with f(a)=1. At an arbitrary b, a term succeeds exactly when its row equals b; therefore the formula outputs f(b). Alternatively, AND together Cₐ for every a with f(a)=0. This fails exactly when b is one of the forbidden rows, so it also outputs f(b). These arguments prove equivalence for every finite V, rather than extrapolating from our four-row example.
The empty OR is false: with no terms, no term succeeds. The empty AND is true: with no clauses, no clause fails. Consequently an always-false function has an empty canonical DNF, and an always-true function has an empty canonical CNF. If V itself is empty, there is still one valuation, the empty assignment. Its minterm is an empty AND and its maxterm an empty OR; the same construction works for both possible specifications.
For a fixed V, the true-row set determines the canonical complete DNF terms uniquely, ignoring ordering and redundant repeats. That does not make every equivalent DNF identical. For example, p and (p ∧ q) ∨ (p ∧ ¬q) represent the same function, but only the latter lists complete minterms on V consisting of p and q.
Apply
Create an unfamiliar three-input specification that grants access exactly when one input is 1. List all eight valuations, construct its three-term canonical DNF and five-clause canonical CNF, and explain why a valuation with two 1s is rejected by both. Exchange formulas with another learner or check independently by truth table. A useful review identifies the accepting term or rejecting clause, not only agreement totals.
Then audit the cost of the method. With n variables there are 2ⁿ valuations. For the specification f = x₁, half of them are true. Its complete DNF uses 2ⁿ⁻¹ terms, each with n literals, even though the single literal x₁ already represents the function. Canonical construction guarantees existence, not economical representation. Exhaustive comparison of formulas terminates on finitely many rows, but this procedure can take exponentially many row evaluations. That is not a proof that every conceivable equivalence algorithm must take exponential time.
Continue
Use the practice below to repair polarity errors, handle constant specifications, prove the general construction and separate uniqueness of a canonical row set from uniqueness of syntax. In later circuit work, a truth-table equivalence proof checks logical behavior; operation count and circuit depth require separate arguments about the implementation.
This lesson is supporting depth. The inspected MIT Spring 2015 problem set 1 made textbook section 3.4 optional. These independently authored tasks teach a useful representation mechanism; they do not turn an optional source section into a requirement for every learning path or certify performance on MIT’s assessments.
