# Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators.

Show that $\neg$ and $\wedge$ form a functionally complete collection of logical operators.

I was given the hint that I could use De Morgan law to show that $p \vee q$ is logically equivalent to $\neg (\neg p \wedge \neg q)$.

$$\neg (\neg p \wedge \neg q) \equiv \neg (\neg p) \vee \neg (\neg q)$$

$$\neg (\neg p) \vee \neg (\neg q) \equiv p \vee q$$

But I cannot figure out? am I done?

• Whether you're done or not depends on what facts you already have. For instance, do you know that $\{\neg, \land, \lor\}$ is complete? – Git Gud Mar 16 '15 at 19:07
• No, you are not done. You need to show that you can express any function $F:\{T,F\}^n \rightarrow \{T, F\}$ for $n>0$ in terms of the given truth functions. – James Mar 16 '15 at 19:07
• Maybe I have to study what "functionally complete collection of logical operators" means – Alim Teacher Mar 16 '15 at 19:12
• @AlimTeacher: If you don't know that, you certainly can't hope to prove anything about it until you have found out what it means. – hmakholm left over Monica Mar 16 '15 at 19:13

You may or may not be done, depending on whether you already know that $\{{\neg},{\land},{\lor}\}$ is a functionally complete collection.

If you do know that, you can reason as follows: Suppose we're given some truth function. Express it as an expression that uses $\neg$, $\land$, and $\lor$ (you already know this can be done). Rewrite every $\lor$ in that expression using the proof you already have. The result is an expression for the function that uses only $\neg$ and $\land$.

On the other hand, if you don't know that $\{{\neg},{\land},{\lor}\}$ is complete, then you're not done yet. Your best bet is to know some complete set and show that every function in that set can be made from your selection of operators.

If you don't know any complete sets of connectives, you have to start from scratch and find a proof that for every possible truth table of $n$ inputs can be realized by some expression that uses only $\neg$ and $\land$. (Or perhaps you can show some larger set to be complete, and then use that as a stepping stone to $\{{\neg},{\land}\}$ being complete.

To show if an operator set is functionally complete you can use Post's 5 criteria from his 1921 thesis.

2) A little more difficult to follow but more rigorous. Pdf is readily available: https://sites.ualberta.ca/~francisp/Phil428/Phil428.11/PostPellMartin.pdf

The five properties are that a Boolean function $f$ may have are:

• $f$ preserves zero $(T_0)$,
• $f$ preserves one $(T_1)$,
• $f$ is linear $(L)$,
• $f$ is monotone $(M)$,
• $f$ is self-dual $(S)$.

Post's Completeness Theorem may be stated as follows (This is straight from the first reference):

Theorem. A system of Boolean functions is functionally complete if and only if this system does not entirely belong to any of $T_0$, $T_1$, $L$, $M$, $S$.

This means that

• at least one function that does not preserve zero (i.e. it is not in $T_0$), and
• at least one function that does not preserve one (i.e. it is not in $T_1$), and
• at least one function that is not linear (i.e. it is not in L), and
• at least one function that is not monotone (i.e. it is not in M), and
• at least one function that is not self-dual (i.e. it is not in S).

The aforementioned documents spell these out in great detail so I will not belabor the point here. Post's Completeness Theorem, however, states that a functionally complete operator set is a set of operators which at least one function $f$ of the set does not entirely below to all of these sets 1 through 5.

If you test $\{\lnot, \land\}$ for each of the criteria you will notice that they meet the requirements for the theorem and are therefore (minimally) functionally complete.