5 Minimum functionally complete sets

I claim that we can get rid of either or , and the remaining set of ,,∧} is still functionally complete. This can be proven by de Morgan’s law.

AB = ¬(¬A∧¬B), therefore is not necessary when ¬ and are available. Likewise, AB = ¬(¬A∨¬B), therefore is not necessary when ¬ and are available.

Consequently, ,∧} and ,∨} are both minimum functionally equivalent sets.

In computer and electrical engineering, or-gates and and-gates are not that “natural”. Instead, nand-gates and nor-gates are more natural (due to the way semiconductor devices operate). Let represent nand, and + represent nand and nor, respectively. Then AB = ¬(A B), and A+B = ¬(A B). I claim that {} and {+} are both minimum functionally complete sets.

Here is the proof. ¬A = A+A = AA, and AB = (AB)(AB) = (A+A)+(B+B). Because we already know that ,∧} and ,∨} are both minimum functionally complete sets, it follows that {} and {+} are functionally complete, as well.