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