Functional completeness

From Wikipedia, the free encyclopedia

In logic, a set S of logical connectives is functionally complete (also expressively adequate or simply adequate) if every possible logical connective can be defined in terms of the members of S. S is minimal functionally complete if no member of S can be defined in terms of the other members. These concepts also carry over to the corresponding Boolean operators.

1 Informal
2 Characterization of functional completeness
3 Minimal functionally complete operator sets
4 References

[edit] Informal

Modern texts on logic typically take as primitive some subset of the connectives conjunction ( $\land$ ), disjunction ( $\lor$ ), negation ( $\neg$ ), material conditional ( $\to$ ) and possibly the biconditional ( $\leftrightarrow$ ). These connectives are functionally complete. However, they do not form a minimal functionally complete set, as the conditional and biconditional may be defined as:

$A \to B := \neg A \lor B$

$A \leftrightarrow B := (A \to B) \land (B \to A).$

So ${\neg, \land, \lor}$ is also functionally complete. But then, $\lor$ can be defined as:

$A \lor B := \neg(\neg A \land \neg B).$

$\land$ can also be defined in terms of $\lor$ in a similar manner.

It is also the case that $\vee$ can be defined in terms of $\rightarrow$ as follows:

$\ A \vee B := (A \rightarrow B) \rightarrow B.$

No further simplifications are possible. Hence $\neg$ and one of { $\land, \lor, \rightarrow$ } are each minimal functionally complete subsets of
{ $\neg, \land, \lor, \to, \leftrightarrow$ }.

[edit] Characterization of functional completeness

Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of the following sets of connectives:

The monotonic connectives, e.g. $\vee$ , $\wedge$ , $\top$ , $\bot$ .

The affine connectives, such that each connected variable either always or never affects the truth value these connectives return, e.g. $\neg$ , $\top$ , $\bot$ , $\leftrightarrow$ , $\not\leftrightarrow$ .

The self-dual connectives, which are equal to their own de Morgan dual, e.g. $\neg$ , MAJ(p,q,r).

The truth-preserving connectives; they return the truth value T under any interpretation which assigns T to all variables, e.g. $\vee$ , $\wedge$ , $\top$ , $\rightarrow$ , $\leftrightarrow$ .

The falsity-preserving connectives; they return the truth value F under any interpretation which assigns F to all variables, e.g. $\vee$ , $\wedge$ , $\bot$ , $\not\rightarrow$ , $\not\leftrightarrow$ .

In fact, Post gave a complete description of the lattice of all clones (sets of operations closed under composition and containing all projections) on the two-element set {T, F}, nowadays called Post's lattice, which implies the above result as a simple corollary: the five mentioned sets of connectives are exactly the maximal clones.

[edit] Minimal functionally complete operator sets

It has been suggested that sole sufficient operator be merged into this article or section. (Discuss)

NOR and NAND are each functionally complete by themselves and are called sole sufficient operators.

The following table lists all pairs of logical connectives / Boolean operators with arity ≤ 2, that are minimal functionally complete operator sets:

Operator	Arity	And One Binary	Operator:
		Primal	Dual
$\bot$	$\ 0$	$\rightarrow$
$\top$	$\ 0$		$\not\leftarrow$
$\neg$	$\ 1$	$\vee, \rightarrow, \leftarrow$	$\wedge, \not\leftarrow, \not\rightarrow$
$\rightarrow$	$\ 2$	$\not\leftarrow$	$\not\rightarrow, \not\leftrightarrow$
$\leftarrow$	$\ 2$	$\not\rightarrow$	$\not\leftarrow, \not\leftrightarrow$
$\leftrightarrow$	$\ 2$	$\not\rightarrow, \not\leftarrow$