Sentential Connectives and Normal Forms

Five connectives are convenient, but they are neither forced nor minimal. Two questions make the choice precise: would adding a connective let us say anything new, and could we drop some and still say everything? A three-place majority connective $\#$, with $(\#\alpha \beta \gamma )$ true iff at least two of $\alpha ,\beta ,\gamma$ are, illustrates the first. It adds nothing: every formula using it is tautologically equivalent to one without, since

Both questions are answered cleanly by shifting attention from formulas to the truth functions they compute.¹

Boolean functions

There are $2^{2^k}$ Boolean functions of $k$ places: a table with $2^k$ rows, each row's output chosen from two values. Every formula produces one.

The connectives themselves realize the basic Boolean functions: negation realizes $N$ with $N(F)=T,N(T)=F$; conjunction realizes $K$ (the minimum, with $F<T$); disjunction realizes $A$ (the maximum); the conditional and biconditional realize $C$ and $E$; and $A_i$ realizes the $i$th projection $I_i^n$. From these, composition builds the rest, mirroring how connectives nest inside a formula.

Passing to Boolean functions identifies tautologically equivalent formulas and frees us from the formal language. Order $\{F,T\}$ by $F<T$.

Post's theorem

The functions realized by wffs comprise all the Boolean functions and nothing else.

The formula $\alpha$ transcribes the table: one disjunct per true row, each disjunct spelling out that row's assignment.

The formula built this way has a special shape.

By dualizing — interchanging the roles of $\wedge$ and $\vee$, or applying the construction to the false rows and negating — one gets conjunctive normal form (CNF): a conjunction of disjunctions of literals. Every wff has an equivalent CNF as well.

Complete sets of connectives

Post's theorem realizes every function using only $\neg ,\wedge ,\vee$. So no exotic connective adds expressive power: any wff of an extended language realizes some $B_{\phi }$, and Post gives a wff over $\{\neg ,\wedge ,\vee \}$ realizing the same function, hence equivalent to it.

So $\{\neg ,\wedge ,\vee \}$ is complete. It is not minimal.

Once one complete set is known, showing another set complete reduces to simulating each connective of a known complete set. Two single connectives suffice by themselves.

Other complete sets are known. $\{\neg ,\to \}$ is complete, since $\alpha \vee \beta \models \mid \models ((\neg \alpha )\to \beta )$ recovers disjunction. Allowing a $0$-place constant, $\{\perp ,\to \}$ is complete, with $\neg \alpha \models \mid \models (\alpha \to \perp )$; it even realizes the $0$-place functions ($\perp$ itself and $\top \models \mid \models (\perp \to \perp )$), so it is supercomplete. The catalog of small connectives:

• $0$-ary: two, the constants $\perp$ (always $F$) and $\top$ (always $T$).
• Unary: four, of which only negation is of interest — the others are the identity and the two constants.
• Binary: sixteen. Six are essentially constant or unary; the ten really binary ones include $\wedge ,\vee ,\to ,\leftrightarrow$, the reversed conditional, exclusive or $+$, NAND $\mid$, NOR $\downarrow$, and the two strict orderings.

Testing for incompleteness

Proving a set complete means simulating a known complete set; proving one incomplete means finding a property shared by all its formulas but missing from some Boolean function.

The pattern is a preserved invariant — here true at the all-true assignment — that the target function violates. The minimal complete sets sit at the bottom of a hierarchy of adequacy.

Completeness guarantees that any specification of a truth function can be met by a formula, and — through the correspondence between formulas and gate networks — by a physical circuit. The single-connective results are why a whole processor can be built from one gate type.