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

Question

Earlier this day I ask about the assignmet:

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?

Answer 1

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.

Answer 2

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

1) Easy to understand yet must log into Scribd unfortunately. https://www.scribd.com/document/255983069/Posts-Criterion

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.