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?
Best Answer
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.