52 Other gates

We have seen circuits that use the gates $\{\neg ,\vee ,\wedge \}$, but we can design circuits using arbitrary gate types.

Definition

A basis is a set $\Omega =\{f_i{\}}_{i<k}$ of Boolean function (‘connectives’). We say that $\Omega$ is complete if every Boolean function is computed by an expression/formula formed from variables and elements of $\Omega$.

Example

• Some complete bases: $\{\neg ,\vee ,\wedge \},\{\neg ,\vee \},\{0,\to \},\{\neg ,{\mathrm{MAJ}}^3,0\}$
• Some non-complete bases: $\{\vee ,\wedge \},\{\neg ,\oplus \},\{{\mathrm{MAJ}}^3\}$

Example: some (in) completeness arguments

$$\{\neg ,{\mathrm{MAJ}}^3,0\}\text{ complete}$$

$\{\vee ,\wedge \}$ is not complete

To prove $\{\vee ,\wedge \}$ is not complete, we need to show that $\neg$ cannot be expressed.
We prove by structural induction that any formula built only using $\vee$ and $\wedge$ evaluates to $0$ when all inputs are $0$

Base Case

A formula consisting of a single variable $x_i$ satisfies

$$x_i(0,\cdots ,0)=0$$

Induction Hypothesis

Assume formulas $A$ and $B$ satisfy

$$A(0,\cdots ,0)=0,B(0,\cdots ,0)=0$$

Induction Step

If $F=A\vee B$ then:

$$F(0,\cdots ,0)=A(0,\cdots ,0)\vee B(0,\cdots ,0)=0\vee 0=0$$

If $F=A\wedge B$ then:

$$F(0,\cdots ,0)=A(0,\cdots ,0)\wedge B(0,\cdots ,0)=0\wedge 0=0$$

Hence every formula using only $\{\vee ,\wedge \}$ has output $0$ on the all-zero input.
But negation does not satisfy this:

$$\neg 0=1$$

Therefore $\neg$ cannot be expressed using only $\{\vee ,\wedge \}$ so $\{\vee ,\wedge \}$ is not functionally complete.