How to prove that a set of connectives is adequate

Question

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.

Answer 1

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.