Show functional completeness of $\{\nleftarrow, \sim\}$ (inhibition, negation) via structural induction

Question

I came across an exercise which asks to determine via structural induction whether the connective set {$\nleftarrow$, $\sim$} is a functionally complete set, knowing that the set {$\wedge, \vee, \sim$} is a functionally complete set. (The symbol $\nleftarrow$ meaning "Inhibition of A", that is (NOT A) AND B).
I have found this information here:\https://en.wikipedia.org/wiki/Functional_completeness

It says there that {$\nleftarrow, \sim$} is indeed minimal functionally complete, is that correct? And if so, how do I prove it?

Thank you in advance

Answer 1

You would just need to implement $\wedge, \vee, \sim$ using only $\nleftarrow, \sim$. $\sim$ is already there so you only need to define $\wedge$ and $\vee$.

Answer 2

Here is a simple proof with Logical equivalence:

Knowing that the set $\{∧,∨,\neg\}$ is a functionally complete set. Then we will prove that any operator in $\{∧,∨,\neg\}$ can be expressed by operators in $\{\not\leftarrow,\neg\}$. \begin{align} A\land B&\equiv \neg(\neg A\lor\neg B)\tag*{De Morgan's law}\\ &\equiv\neg(\neg A\leftarrow B)\tag*{Conditional equivalence}\\ &\equiv\neg A\not\leftarrow B\tag*{Definition of $\not\leftarrow$}\\\\ A\lor B&\equiv A\leftarrow \neg B\tag*{Conditional equivalence}\\ &\equiv\neg\neg(A\leftarrow\neg B)\tag*{Double negation law}\\ &\equiv\neg(A\not\leftarrow\neg B)\tag*{Definition of $\not\leftarrow$} \end{align} Hence $\{\not\leftarrow,\neg\}$ is also a functionally complete set.

Answer 3

To do a proper proof that shows that any truth-function can be expressed in terms of atomic variables, $\neg$, and $\not \leftarrow$, we indeed borrow from the fact that any truth-function can be expressed using $\neg, \land$, and $\lor$. That is, below we will show that any expression built up from atomic sentences, $\neg$, $\land$, and $\lor$ can be captured by an expression built up from atomic statements, $\neg$, and $\not \leftarrow$. So, given that any truth-function can be expressed using $\neg, \land$, and $\lor$, it then follows that any truth-function can be expressed in terms of atomic variables, $\neg$, and $\not \leftarrow$.

We will use structural induction over the formation of expressions to show that any expression built up from atomic sentences, $\neg$, $\land$, and $\lor$ can be captured by an expression built up from atomic statements, $\neg$, and $\not \leftarrow$:

Base: Any atomic variable $A$ can be captured by itself. Done!

Step: Assume (this is the inductive Hypothesis) that $\phi$ and $\psi$ are expressions built up from atomic sentences, $\neg$, $\land$, and $\lor$, for which there are equivalent expressions built up from atomic statements, $\neg$, and $\not \leftarrow$. Let these equivalent expresions be $\phi'$ and $\psi'$.

Now we need to show that $\neg \phi$, $\phi \land \psi$, and $\phi \lor \psi$ can be expressed in terms of atomic statements, $\neg$, and $\not \leftarrow$ as well.

First, for $\neg \phi$ we simply use $\neg \phi'$. Done!

For $\phi \land \psi$ and $\phi \lor \psi$: as @Manx shows, we know that $\phi \land \psi$ is equivalent to $\neg \phi \not \leftarrow \psi$. But since $\phi$ is equivalent to $\psi'$ and $\psi$ is equivalent to $\psi'$, that means that $\phi \land \psi$ is equivalent to $\neg \phi' \not \leftarrow \psi'$, and the latter is an expression built up from atomic statements, $\neg$, and $\not \leftarrow$. Done! Similar for $\lor$. Done!

So, we have now shown that $\{ \neg, \not \leftarrow \}$ is functionally complete.

Finally, to show that $\{ \neg, \not \leftarrow \}$ is minimally functionally complete, we need to show that removing either the $\neg$ or the $\not \leftarrow$ from this set will result in a set that is not functionally complete. In other words, we need to show that $\{ \neg \}$ and $\{ \not \leftarrow \}$ are not functionally complete.

That $\{ \neg \}$ is not functionally complete is trivial: the $\neg$ is a unary function, and so can't capture any function that meaningfully depends on multiple inputs. Thus, for example, there is no way that $\{ \neg \}$ can capture the truth-function captured by $A \land B$. Indeed, how would it? You only have expressions like $\neg \neg \neg A$ or $\neg \neg \neg \neg \neg B$. I'll leave it up to you to actually create a proper mathematical proof, but with structural induction this is very easy.

To show that $\{ \not \leftarrow \}$ is not functionally complete is more interesting. Let's first consider its truth-table

\begin{array}{l|l|c} P & Q & P \not \leftarrow Q\\ \hline T&T&\neg (T \leftarrow T) = \neg T = F\\ T&F&\neg (T \leftarrow F) = \neg T = F\\ T&T&\neg (F \leftarrow T) = \neg F = T\\ T&T&\neg (F \leftarrow F) = \neg T = F\\ \end{array}

OK, so looking at this, I am immediately struck by the last line: when $P$ and $Q$ are both False, we have that $P \not \leftarrow Q$ is also False. This strongly suggest that any expression built up from $P$, $Q$, and $\not \leftarrow$: if $P$ and $Q$ are False, then the expression (no crazy long or complex it is) will evaluate to False as well, and that means that such an expression cannot possibly capture any truth-function (such as the $NAND$ or the $NOR$) that returns True when both $P$ and $Q$ are False, and hence $\{ \not \leftarrow \}$ is not functionally complete.

Again, for a proper proof, use structural induction. That is, by structural induction we'll show that for any expression built up from $P$, $Q$, and $\not \leftarrow$: if $P$ and $Q$ are False, then the expression will evaluate to False as well:

Base: For any atomic expression built up from $P$, $Q$, and $\not \leftarrow$ (so that has to be either $P$ or $Q$), it is trivially true that if $P$ and $Q$ are both set oto False, then the expression evaluates to False as well. Done!

Step: Assume (inductive hypothesis) that $\phi$ and $\psi$ are expressions built up from $P$, $Q$, and $\not \leftarrow$ that evaluate to False when both $P$ and $Q$ are set to False. Well, then $\phi m\not \leftarrow \psi$ will evaluate to False as well, as demonstrated by the truth-table. Done!