How do I prove if a set of operations is complete?

Question

For example $\{\land, \lnot\}$ apparently forms a functionally complete set as it can form any logical expression.

But I don't really know what this means or how you show it. Do we just show that some set is complete and then in the future if we have a new set, show that we can replicate the known operations with the new ones?

Do you have to find these strategically or is there a systematic way?

Answer 1

Do we just show that some set is complete and then in the future if we have a new set, show that we can replicate the known operations with the new ones?

Yeah, that's how we typically show that $\{ \land , \neg \}$ is complete: we already know that $\{ \land, \lor, \neg \}$ is functionally complete, and we just point out that $\lor$ can be rewritten in terms of $\land $ and $\neg$:

$$P \lor Q \Leftrightarrow \neg (\neg P \land \neg Q)$$

Also, here is a post explaining why $\{ \land , \lor, \neg \}$ is complete

Answer 2

Here, once again - as the other page was marked as duplicate - a systematic way of showing completeness without relying on an already given complete set of operators.

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.