/* MINDFIRE BLOG */

“[The AND, OR, and NOT operations] suffice to generate all possible logic functions; or, more concisely, they form an adequate set.”
— E.T. Jaynes, Probability Theory: The Logic of Science, p. 15

In our previous post, we covered the basics of propositional logic. Here, we’ll show how three simple operations—conjunction (AND), disjunction (OR), and negation (NOT)—can be combined to create any Boolean function. In other words, AND, OR, and NOT are an adequate set of operations.

To prove this, we’ll start with the four “atomic” functions built from just AND and NOT, then stitch them together with OR to form the familiar but non-trivial implication function, A → B. Along the way, you’ll see why implication is vacuously true when A is false, how it’s equivalent to ¬A ∨ B, and how to verify the whole construction with side-by-side truth tables.

The Atoms of Logic

Imagine a function fᵢ that takes two Boolean inputs, A and B. Since each input can be True (T) or False (F), there are exactly four input combinations—and if we only allow AND and NOT, there are exactly four possible functions. Let’s label them f₁ through f₄:

Note that each fᵢ is true on exactly one input row—these are the building blocks (known as minterms) for all two-variable logic.

The Implication Function

The implication A → B is defined by this truth table:

You might pause and ask, “Why is A → B true whenever A is false?” Think of it as a promise:

“If I press the button (A), then the light will turn on (B).”

• Press and no light (A = T, B = F) → promise broken → False
• Press and light (A = T, B = T) → promise kept → True
• But, if you never press the button (A = F), you never give the promise a chance to fail—so it’s regarded as vacuously true regardless of B.

You might wonder why we don't instead call this 'undefined'. But then that would require Boolean logic to have three states! Plus, assigning a value of True always gives the right result. Consider a real life example. If I said "If I arrive on time, I'll be there to help you." Suppose I don't arrive on time. Did that make the original statement false?

Okay, but can we really build such a complicated function as the implication function using only those four minterms stitched together with OR? The answer is yes—and we’ll prove it in two complementary ways.

Implication Equals “¬A ∨ B”

Another way to see it is that

(A → B) ≡ (¬A ∨ B).

Here are their truth tables side by side to prove they are equivalent:

They match perfectly, so implication really is “not A or B.” This makes sense since, as we already discussed, if A is False* then we want the implication function to always be True. So that's why we negate (A) and OR it with (B).

Reconstructing Implication with Minterms

Which minterms from Step 1 fire on the rows where A → B is true?

• A = T, B = T → f₁
• A = F, B = T → f₃
• A = F, B = F → f₄

Thus we can write

(A → B)
= f₁ ∨ f₃ ∨ f₄
= (A ∧ B) ∨ (¬A ∧ B) ∨ (¬A ∧ ¬B).

Or in other words: (A → B) = (A ∧ B) ∨ (¬A ∧ B) ∨ (¬A ∧ ¬B)

Note that this later form is made up of only AND and OR operators 'stitched' together with OR operators. This is known as disjunctive normal form (DNF).

Verifying the DNF Matches ¬A ∨ B

Finally, let’s check that our disjunctive normal form (DNF) agrees with ¬A ∨ B. Side by side:

They coincide on every row, confirming the construction is correct.

Why This Proves Universality

So, using only AND and NOT we can build minterms for any boolean function with exactly one True value per function. Then using OR we can stitch them together to form any other boolean function. Or in other words:

1. Every Boolean function on n variables picks a subset of the 2ⁿ input rows to be true for one column.
2. Each row corresponds to one minterm built from AND and NOT.
3. OR the chosen minterms, and you can create any desired function.

We’ve built a non-trivial example—implication—using only AND, OR, and NOT. But the same process works for any Boolean function of any size. That is to say the AND, OR, and NOT operators are universal.