# How to prove that a set of connectives is adequate

I have this Table:

$$\begin{array} {|c|} \hline A & B & A*B\\ \hline 1 & 1 & 0\\ \hline 1 & 0 & 1\\ \hline 0 & 1 & 1\\ \hline 0 & 0 & 0\\ \hline \end{array}$$

I have to prove that $\{\to, *\}$ forms an adequate set of connectives.

My first thought would be to prove that $\{\wedge, \lor, \neg \}$ is adequate, because I know that is an adequate set and I also know I could solve it for $\{\to, \neg\}$ as well, but as far as proving it I have no idea how to tie the two together.

First, what is the definition of adequate? We note that set of connectives is called adequate (or functionally complete) iff all other connectives can be expressed in terms of it.

Then it suffices to show that we can express all the standard connectives we already know by means of $*$ and $\to$:

$\neg$:

$\$ $\$ $\$ \ \neg \varphi \Leftrightarrow \varphi \to (\varphi*\varphi) \wedge:\begin{align} \varphi \wedge \psi & \Leftrightarrow \neg(\varphi \to \neg \phi) \\ & \Leftrightarrow (\varphi \to (\psi \to (\psi*\psi))) \to ((\varphi \to (\psi \to (\psi*\psi)))*(\varphi \to (\psi \to (\psi*\psi)))) \end{align} \vee: \ \ \ \\varphi \vee \psi \Leftrightarrow \neg(\neg \varphi \wedge \neg \psi) \Leftrightarrow (and so on)

You can confirm this definition by checking their truth-tables, i.e. noting that:

$$\begin{array} {|c|} \hline A & \neg A & A \to (A*A)\\ \hline 1 & 0 & 0\\ \hline 0 & 1 & 1 \\ \hline \end{array}$$

And the same for conjunction and disjunction.

• I have been looking at those, I still don't understand in the first link how the answers are being achieved: for example When a is true and b is false it returns true, and a is false and b is true it returns true. What necessarily does that mean? Could it mean if A and -B, and could it mean -A and B for the next one? Commented Oct 30, 2014 at 8:55
• @user3357318 Please see my edit above. I hope it can help you to solve you problem. Commented Oct 30, 2014 at 9:11
• ¬0=1. (0*0)=0. This answer is not correct. Commented Oct 30, 2014 at 20:10
• You switched variables in the $\land$ part. But other than that this looks alright. Commented Oct 31, 2014 at 15:16