# How to prove that $\{\land,\lnot\}$ is complete? [duplicate]

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\}$)?

## marked as duplicate by Bram28 logic StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Mar 16 '18 at 17:10

• Weird ... you asked this very same question earlier .. but now you're basically posting my Answer to that question and make it out to be 'your work'. Not cool. – Bram28 Mar 16 '18 at 17:08
• @Bram28 I actually did end up deriving it on my own. The approach that I normally use for converting truth tables into expressions is the DNF approach, I just didn't know at the time that this was also how you could show completeness too with (and, or, not) – user539262 Mar 16 '18 at 17:47
• Well, OK, I believe you. But that means you didn't look at my answer in detail. Indeed, I note the accepted answer is exactly what I answered to your previous question ... and I gave the link to my explanation why you can prove the completeness of $\{ \land, \lor, \neg \}$ using truth-tables. – Bram28 Mar 16 '18 at 18:11
• @Bram28 I did look at the link (that's how I noticed "Oh, this is what I already do!"), this question is (intended to be, maybe I didn't clarify sufficiently) more about proving completeness by synthesizing other known complete sets rather than messing with truth tables directly – user539262 Mar 16 '18 at 18:30
• OK, I see now. Yeah, that wasn't quite clear. Still, the accepted answer is basically yes, that works .. which I already said in the earlier post as well. At least the other answer adds something of interest to that, which is that you need to use induction to make that a rigorous proof. – Bram28 Mar 16 '18 at 18:43

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

• If I can't recreate $\{\land, \neg \}$ with an arbitrary set of operators, does that prove the set is not complete? How do we know if it can't be done vs. we just couldn't figure it out even if it's possible? – user539262 Mar 16 '18 at 3:35
• Also I think $\{\lor, \neg \}$ is complete as well? – user539262 Mar 16 '18 at 5:52
• @user539262: If we just couldn't figure out that it is possible, then it doesn't count as a proof. However, if we can prove that there is absolutely no way to express either "and" or "or" or "not" using your set of boolean operations, then your set cannot be functionally complete, simply by definition of functionally complete. If you cannot prove it, then of course it does not count as a proof – user21820 Mar 16 '18 at 7:31

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.

• What does $f:\, \{0,1\}^n \rightarrow \{0,1\}$ mean? Do you have an example? – user539262 Mar 16 '18 at 8:29
• Any truth table is nothing but another way of writing a function, that assigns to a tuple of truth values a truth value. Example: $a \lor b = a + b: \{0,1\}^2 = \{0,1\}\times \{0,1\} \rightarrow \{0,1\}$. So, for example: $0 \lor 1 = 0 + 1 = 1$. – trancelocation Mar 16 '18 at 8:35
• $\{0,1\}^n$ means the set of all $n$-tuples $(a_1,\ldots , a_n)$ of truth values. For example for $n=3$: $(0,1,0)$ would be an element of $\{0,1\}^3$. – trancelocation Mar 16 '18 at 8:40
• $\{0,1\}^n$ has $2^n$ such tuples? Even with this idea in mind I don't understand what "$a \lor b = a + b: \{0,1\}^2 = \{0,1\}\times \{0,1\} \rightarrow \{0,1\}$" is saying. An operator that acts on Boolean inputs of the form $(i_1, i_2)$ and returns a single Boolean output $(o_1)$? – user539262 Mar 16 '18 at 8:45
• "It is to be shown that ∀n∈ℕ any truth function f:{0,1}n→{0,1} can be written using only ⋅ and ¯."... does having a function like $f(a)=a$ or $f(a)=0$ or $f(a)=1$ contradict this? i.e. functions that don't actually use operators but return some fixed value? – user539262 Mar 16 '18 at 8:50