Show functional completeness of $\{\nleftarrow, \sim\}$ (inhibition, negation) via structural induction 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
 A: 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!
A: 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.
A: 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$.
