5

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.

Bruno Bentzen
  • 3,362
user3357318
  • 153

1 Answers1

4

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.

Bruno Bentzen
  • 3,362
  • 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? – user3357318 Oct 30 '14 at 08:55
  • @user3357318 Please see my edit above. I hope it can help you to solve you problem. – Bruno Bentzen Oct 30 '14 at 09:11
  • ¬0=1. (0*0)=0. This answer is not correct. – Doug Spoonwood Oct 30 '14 at 20:10
  • You switched variables in the $\land$ part. But other than that this looks alright. – Doug Spoonwood Oct 31 '14 at 15:16