---
title: Sentential Connectives and Normal Forms
module: Sentential Logic
moduleNumber: 2
lessonNumber: 5
order: 205
summary: >
  Every formula computes a Boolean function of its atoms, and Post's theorem gives
  the converse: every Boolean function is realized by a wff in disjunctive normal
  form, so the five connectives are more than enough. Minimal complete sets follow,
  down to the single connectives NAND and NOR, together with a method for proving a
  set of connectives incomplete.
topics: [Sentential Logic]
sources:
  - book: Enderton
    ref: "Ch. 1 — Sentential Logic; §1.5 Sentential Connectives"
draft: false
---

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

$$
(\#\alpha\beta\gamma) \ \models\mid\models \ (\alpha \wedge \beta) \vee (\alpha \wedge \gamma) \vee (\beta \wedge \gamma).
$$

Both questions are answered cleanly by shifting attention from formulas to the
truth functions they compute.[^enderton-conn]

## Boolean functions

> **Definition (Boolean function).** A **$k$-place Boolean function** is a
> function $\{F, T\}^k \to \{F, T\}$. The two $0$-place Boolean functions are the
> constants $F$ and $T$.

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.

> **Definition (Function realized by a wff).** Let $\alpha$ be a wff with sentence
> symbols among $A_1, \dots, A_n$. The **Boolean function realized by $\alpha$**
> is
> $$
> B_\alpha^n(X_1, \dots, X_n) = \bar v(\alpha), \quad\text{where } v(A_i) = X_i.
> $$
> It reads $\bar v(\alpha)$ as a function of $v$, with $\alpha$ fixed.

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$.

> **Theorem (Boolean-function criterion for tautological relations).** For wffs $\alpha, \beta$ with sentence symbols among
> $A_1, \dots, A_n$:
> $$
> \alpha \models \beta \iff B_\alpha \le B_\beta \text{ pointwise}, \qquad
> \alpha \models\mid\models \beta \iff B_\alpha = B_\beta, \qquad
> \models \alpha \iff B_\alpha \equiv T.
> $$

> **Proof of the first.** $\alpha \models \beta$ means every assignment making
> $\alpha$ true makes $\beta$ true, i.e. for every tuple $\vec X$,
> $B_\alpha(\vec X) = T \Rightarrow B_\beta(\vec X) = T$, which with $F < T$ is
> exactly $B_\alpha(\vec X) \le B_\beta(\vec X)$. $\blacksquare$

## Post's theorem

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

> **Theorem (Expressive completeness; Post, 1921).** Every $n$-place Boolean function $G$ with
> $n \ge 1$ is realized by some wff.

> **Proof.** If $G$ is constantly $F$, take $\alpha = A_1 \wedge (\neg A_1)$.
> Otherwise let $\vec X_1, \dots, \vec X_k$ ($k > 0$) be the tuples where $G$ is
> $T$. For each such tuple $\vec X_i$ form the conjunction of literals
>
> $$
> \gamma_i = \beta_{i1} \wedge \cdots \wedge \beta_{in}, \qquad
> \beta_{ij} = \begin{cases} A_j & \text{if } X_{ij} = T,\\ (\neg A_j) & \text{if } X_{ij} = F, \end{cases}
> $$
>
> and set $\alpha = \gamma_1 \vee \cdots \vee \gamma_k$. Exactly one assignment
> satisfies each $\gamma_i$, namely the one given by $\vec X_i$, so $\alpha$ is true
> at precisely $\vec X_1, \dots, \vec X_k$. Hence $B_\alpha = G$. $\blacksquare$

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

> **Worked example.** Read a formula in disjunctive normal form off the $3$-place
> function $G$ that is $T$ exactly at the assignments $FFT$, $FTF$, $TFF$, $TTT$
> (and $F$ at the other four).
>
> Each true row contributes one conjunction of literals, positive where the
> variable is $T$ and negated where it is $F$:
>
> $$
> \begin{aligned}
> FFT &\rightsquigarrow (\neg A) \wedge (\neg B) \wedge C, &
> FTF &\rightsquigarrow (\neg A) \wedge B \wedge (\neg C),\\
> TFF &\rightsquigarrow A \wedge (\neg B) \wedge (\neg C), &
> TTT &\rightsquigarrow A \wedge B \wedge C.
> \end{aligned}
> $$
>
> Disjoining the four gives a DNF realization:
>
> $$
> \alpha = ((\neg A) \wedge (\neg B) \wedge C) \vee ((\neg A) \wedge B \wedge (\neg C)) \vee (A \wedge (\neg B) \wedge (\neg C)) \vee (A \wedge B \wedge C).
> $$
>
> The true rows are precisely those with an odd number of $T$s, so
> $\alpha \models\mid\models (A \leftrightarrow B \leftrightarrow C)$ — a far
> shorter realization of the same function, showing the DNF one is rarely
> minimal.

$$
% caption: The eight-row table of the three-place function; Post's construction
% keeps the four shaded rows where the value is T and turns each into a
% conjunction of literals, whose disjunction realizes the function.
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \fill[acc!12] (-0.5,0.99) rectangle (3.3,1.41);
  \fill[acc!12] (-0.5,0.54) rectangle (3.3,0.96);
  \fill[acc!12] (-0.5,-0.36) rectangle (3.3,0.06);
  \fill[acc!12] (-0.5,-1.71) rectangle (3.3,-1.29);
  \draw[black] (0.4,-1.78) -- (0.4,2.1);
  \draw[black] (1.2,-1.78) -- (1.2,2.1);
  \draw[black] (2.05,-1.78) -- (2.05,2.1);
  \node at (0,2.35) {A}; \node at (0.8,2.35) {B}; \node at (1.6,2.35) {C};
  \node[text=acc] at (2.7,2.35) {G};
  \draw[black] (-0.5,2.05) -- (3.3,2.05);
  \foreach \y/\a/\b/\c/\g in {1.65/F/F/F/F, 1.2/F/F/T/T, 0.75/F/T/F/T, 0.3/F/T/T/F, -0.15/T/F/F/T, -0.6/T/F/T/F, -1.05/T/T/F/F, -1.5/T/T/T/T} {
    \node at (0,\y) {\a}; \node at (0.8,\y) {\b}; \node at (1.6,\y) {\c}; \node at (2.7,\y) {\g};
  }
\end{tikzpicture}
$$

$$
% caption: Post's construction reads the true rows of a truth function off its
% table; each true row becomes a conjunction of literals fixing that row, and the
% disjunction of them is a formula realizing the function.
\begin{tikzpicture}[font=\footnotesize,
  row/.style={draw, minimum width=20mm, minimum height=7mm, align=center, font=\footnotesize},
  cj/.style={draw=acc, minimum width=44mm, minimum height=7mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[font=\footnotesize] at (-1.0,2.7) {rows where value is T};
  \node[row] (r1) at (-1.0,1.9) {F, F, T};
  \node[row] (r2) at (-1.0,1.0) {F, T, F};
  \node[row] (r3) at (-1.0,0.1) {T, F, F};
  \node[row] (r4) at (-1.0,-0.8) {T, T, T};
  \node[cj] (c1) at (5.0,1.9) {not A and not B and C};
  \node[cj] (c2) at (5.0,1.0) {not A and B and not C};
  \node[cj] (c3) at (5.0,0.1) {A and not B and not C};
  \node[cj] (c4) at (5.0,-0.8) {A and B and C};
  \foreach \r/\c in {r1/c1,r2/c2,r3/c3,r4/c4} \draw[->, black] (\r) -- (\c);
  \node[text=acc, font=\footnotesize] at (5.0,-1.8) {disjoin the four conjunctions};
\end{tikzpicture}
$$

The formula built this way has a special shape.

> **Definition (Disjunctive normal form).** A wff is in **disjunctive normal
> form** (DNF) iff it is a disjunction $\gamma_1 \vee \cdots \vee \gamma_k$ of
> conjunctions of **literals**, a literal being a sentence symbol or its negation.

> **Corollary (Disjunctive normal form).** Every wff is tautologically equivalent to one in disjunctive
> normal form.

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.

| Normal form | Shape | Reads off |
| --- | --- | --- |
| DNF | $\bigvee_i \bigwedge_j \ell_{ij}$ | the rows where the formula is **true** |
| CNF | $\bigwedge_i \bigvee_j \ell_{ij}$ | the rows where the formula is **false** |

## 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_\varphi$, and Post gives a wff over $\{\neg, \wedge, \vee\}$ realizing the same
function, hence equivalent to it.

> **Definition (Complete set).** A set of connectives is **complete** (adequate)
> iff every Boolean function of arity $\ge 1$ is realized by a wff using only
> those connectives.

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

> **Theorem (Completeness of $\{\neg,\wedge\}$ and $\{\neg,\vee\}$).** $\{\neg, \wedge\}$ and $\{\neg, \vee\}$ are each complete.

> **Proof.** Start from a wff over $\{\neg, \wedge, \vee\}$ and eliminate $\vee$ using
> De Morgan, $\beta \vee \gamma \models\mid\models \neg(\neg\beta \wedge \neg\gamma)$,
> applied throughout. Dually, eliminate $\wedge$ to reach $\{\neg, \vee\}$. $\blacksquare$

> **Worked example.** Rewrite $((A \vee B) \wedge (\neg C))$ over $\{\neg, \wedge\}$.
>
> Replace the single $\vee$ by its De Morgan form
> $A \vee B \models\mid\models \neg((\neg A) \wedge (\neg B))$, substituted in
> place:
>
> $$
> ((A \vee B) \wedge (\neg C)) \ \models\mid\models \ ((\neg((\neg A) \wedge (\neg B))) \wedge (\neg C)).
> $$
>
> The result uses only $\neg$ and $\wedge$ and realizes the same Boolean function.
> Longer formulas are handled the same way, one $\vee$ at a time.

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.

> **Definition (Sheffer stroke and joint denial).** The **Sheffer stroke**
> $\alpha \mid \beta$ (NAND) realizes $\neg(\alpha \wedge \beta)$. **Joint
> denial** $\alpha \downarrow \beta$ (NOR) realizes $\neg(\alpha \vee \beta)$.

> **Theorem.** Each of $\{\mid\}$ and $\{\downarrow\}$ is complete on its own.

> **Proof for the stroke.** $\neg\alpha \models\mid\models (\alpha \mid \alpha)$ and
> $\alpha \vee \beta \models\mid\models (\neg\alpha \mid \neg\beta)$. Since
> $\{\neg, \vee\}$ is complete and both are simulated by $\mid$, so is $\{\mid\}$.
> $\blacksquare$

$$
% caption: The Sheffer stroke rebuilds a complete set: NAND with a repeated input
% gives negation, negating both inputs then NAND gives disjunction, and negation
% of a NAND gives conjunction.
\begin{tikzpicture}[font=\footnotesize,
  g/.style={draw=acc, minimum width=22mm, minimum height=10mm, align=center, font=\scriptsize},
  o/.style={draw, minimum width=26mm, minimum height=10mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[g] (nand) at (0,0) {NAND\\(the only primitive)};
  \node[o] (not) at (5.2,1.5)  {negation:\\input NAND itself};
  \node[o] (or)  at (5.2,0)    {disjunction:\\NAND of negations};
  \node[o] (and) at (5.2,-1.5) {conjunction:\\negate a NAND};
  \draw[->, black] (nand) -- (not);
  \draw[->, black] (nand) -- (or);
  \draw[->, black] (nand) -- (and);
\end{tikzpicture}
$$

> **Worked example.** Rebuild $\neg$, $\vee$, and $\wedge$ from the Sheffer stroke
> $\mid$ alone.
>
> $$
> \begin{aligned}
> \neg A &\models\mid\models (A \mid A),\\
> A \vee B &\models\mid\models ((A \mid A) \mid (B \mid B)),\\
> A \wedge B &\models\mid\models ((A \mid B) \mid (A \mid B)).
> \end{aligned}
> $$
>
> The first is immediate from $A \mid A = \neg(A \wedge A) = \neg A$. The second
> negates both inputs and applies the stroke:
> $(A \mid A) \mid (B \mid B) = \neg((\neg A) \wedge (\neg B)) = A \vee B$. The
> third negates the stroke's output. Since $\{\neg, \vee\}$ is complete and both
> $\neg$ and $\vee$ are now expressed with $\mid$, so is $\{\mid\}$.

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, $\{\bot, \to\}$ is complete, with
$\neg\alpha \models\mid\models (\alpha \to \bot)$; it even realizes the $0$-place
functions ($\bot$ itself and $\top \models\mid\models (\bot \to \bot)$), so it is
**supercomplete**. The catalog of small connectives:

- **$0$-ary:** two, the constants $\bot$ (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.

| Connective | Realizes | Note |
| --- | --- | --- |
| $\wedge$ | and | multiplication in $\{0,1\}$ |
| $\vee$ | inclusive or | maximum |
| $+$ | exclusive or | addition mod $2$ |
| $\mid$ | NAND | complete alone |
| $\downarrow$ | NOR | complete alone |

## 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.

> **Example.** $\{\wedge, \to\}$ is not complete.

> **Proof.** By induction, any wff built from $\{\wedge, \to\}$ is assigned $T$ when
> all its sentence symbols are $T$: atoms are, and both connectives return $T$ on
> all-$T$ inputs. So every such formula has $B_\alpha(T, \dots, T) = T$. But $\neg A$
> has $B(T) = F$, so nothing over $\{\wedge, \to\}$ realizes it. The same argument
> shows $\{\wedge, \vee, \to, \leftrightarrow\}$ is incomplete. $\blacksquare$

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.

$$
% caption: Descending from the five familiar connectives to minimal complete
% sets; each arrow drops a connective while staying complete, ending at single
% connectives that suffice alone.
\begin{tikzpicture}[font=\footnotesize,
  s/.style={draw, minimum width=26mm, minimum height=9mm, align=center, font=\scriptsize},
  m/.style={draw=acc, text=acc, minimum width=20mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[s] (all) at (0,2.4) {all 5 connectives};
  \node[s] (three) at (0,1.0) {not, and, or};
  \node[s] (na) at (-3.2,-0.5) {not, and};
  \node[s] (no) at (3.2,-0.5) {not, or};
  \node[m] (nand) at (-2.0,-2.2) {NAND alone};
  \node[m] (nor) at (2.0,-2.2) {NOR alone};
  \draw[->, black] (all) -- (three);
  \draw[->, black] (three) -- (na);
  \draw[->, black] (three) -- (no);
  \draw[->, black] (na) -- (nand);
  \draw[->, black] (no) -- (nor);
\end{tikzpicture}
$$

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.

[^enderton-conn]: Enderton, §1.5 — Boolean functions, the function realized by a wff, Theorem 15A relating implication to the pointwise order, Post's theorem (15B) with the DNF construction (Corollary 15C), completeness of $\{\neg,\wedge,\vee\}$, $\{\neg,\wedge\}$, $\{\neg,\vee\}$ (Theorem 15D), $\{\mid\}$, $\{\downarrow\}$, the incompleteness method, and the connective catalog.