How to prove that $\{\land,\lnot\}$ is complete?

Question

I am curious one one would prove that a set of operators is "complete," which to my understanding means it can be used to represent all possible truth tables.

So normally if we had $\{\land,\lor, \lnot\}$ and a truth table what I do is look at where the outputs are true and then chain the expressions together with ors. For example in the truth table for XOR the output is true when either $p$ or $q$ is true but not both, so $(p \land \lnot q) \lor (\lnot p \land q)$.

Using this approach I think you can do it for any truth table so $\{\land,\lor, \lnot\}$ is complete.

Now let's say you want to show that some other set of operators are complete. Does it suffice to show that you can synthesize the $\{\land,\lor, \lnot\}$ operators?

For example let's say you asked me to prove:

1. Is $\{\land, \lnot\}$ complete? We can synthesize the missing "or" operation in terms of these two with with $p \lor q = \lnot(\lnot p \land \lnot q)$

2. Is $\def\nand{\barwedge} \{\nand\}$ (NAND) complete? Assuming $p \nand q$ is the same as $\lnot(p \land q)$ I can say $\lnot p = \lnot p \lor \lnot p = \lnot(p \land p) = p \nand p$, and then $p \land q = \lnot(\lnot(p \land q)) = \lnot(p \nand q) = (p \nand q) \nand (p \nand q)$. And if we absolutely needed $\lor$ we could just copy our example from earlier in terms of NAND: $p \lor q = \lnot(\lnot p \land \lnot q) = \lnot p \nand \lnot q = (p \nand p) \nand (q \nand q)$.

Am I way off base or is this a valid way to prove completeness? First by showing $\{\land,\lor, \lnot\}$ is complete via the process in my second paragraph, and then in the future, showing that any arbitrary set of operators can be used to synthesize $\{\land,\lor, \lnot\}$ (or if we wish to be minimal, $\{\land, \lnot\}$)?

Answer 1

Yes, to prove that a given set of operators is complete, it's enough to prove that some other set of operators that is known to be complete can be defined in terms of your given set. For example, if you know that $\{\land, \lor, \neg \}$ is complete, and you want to prove that $\{\land, \neg \}$ is complete, it's enough to show that you can define $\lor$ using $\land$ and $\neg$. One way to define it is to write $a \lor b := \neg(\neg a \land \neg b)$

Answer 2

If you do not want to rely on another complete operator set, you can prove completeness by a simple induction.

I use the follwing notations: $$a \lor b = a + b,\, a \land b = a\cdot b = ab \mbox{ and } \neg a = \bar a, \, T = 1, F = 0$$

It is to be shown that $\forall n \in \mathbb{N}$ any truth function $f:\, \{0,1\}^n \rightarrow \{0,1\}$ can be written using only $\cdot$ and $\bar{}$.

• $n = 1$: So, $f:\, \{0,1\} \rightarrow \{0,1\}$. $f(a) = a$ or $f(a) = \bar a$ or $f(a) = a\bar a$ or $f(a) = \overline{a \bar a}$ are doing the job.
• $n \rightarrow n+1$: So, $f:\, \{0,1\}^{n+1} \rightarrow \{0,1\}$. Split $f(a_1,\ldots ,a_n, a_{n+1})$ into $$g_0(a_1,\ldots ,a_n) = f(a_1,\ldots ,a_n, 0) \mbox{ and } g_1(a_1,\ldots ,a_n) = f(a_1,\ldots ,a_n, 1)$$ According to induction hypothesis $g_0$ and $g_1$ can be expressed using only $\cdot$ and $\bar{}$. Now we have $$f(a_1,\ldots ,a_n, a_{n+1}) = \bar a_{n+1}g_0(a_1,\ldots ,a_n) + a_{n+1}g_1(a_1,\ldots ,a_n)= \overline{\overline{ \bar a_{n+1}g_0(a_1,\ldots ,a_n) + a_{n+1}g_1(a_1,\ldots ,a_n)}}= \overline{\overline{\bar a_{n+1}g_0(a_1,\ldots ,a_n)}\cdot \overline{a_{n+1}g_1(a_1,\ldots ,a_n)}}$$ So, we have written $f$ as an expression using only $\cdot$ and $\bar{}$.

Done.