# Show that $\neg p$ cannot be written in terms of the set $\{ \land, \rightarrow \}$

Show that you cannot express $\neg p$ in terms of the set $\{ \land, \rightarrow \}$.

What I did was notice that if $f(x_1, \dots, x_n)$ is a boolean function constructed from $\land$, then $$f(\top, \dots, \top) = \top$$ and similarly, if $g(x_1, \dots , x_n)$ is a boolean functions constructed from $\rightarrow$, then $$g(\top, \dots ,\top) = \top$$ Now, any combination $f \land g$, $f \rightarrow g$ or $f \land g$ or $g \land f$ or $g \rightarrow f$ satisfies that property. So if $\neg p$ could be written in terms of $\{ \land, \rightarrow \}$, $\neg p$ would have the property as above, but $$\neg \top = \bot$$ and hence, $\neg p$ cannot be written in terms of $\land$ and $\rightarrow$.

Is this reasoning correct? I have the feeling that I left things unproved or that the argument could be made more formally correct.

Here is a nice inductive proof (since you had a nice inductive proof for that other question you asked ...):

Claim For any expression $\varphi$ built up from $p$, $\land$, and $\to$: $v(\varphi)=T$ if $v(p)=T$

Proof by structural induction on formation of $\varphi$

Base $\varphi=p$. Then $v(\varphi)=T$ if $v(p)=T$. Check!

Step Suppose (inductive hypothesis) that $v(\varphi_1)=T$ and $v(\varphi_1)=T$ if $v(p)=T$

Now, if $\varphi=\varphi_1 \land \varphi_2$, then if $v(p)=T$: $v(\varphi)=v(\varphi_1 \land \varphi_2) = T \land T = T$

And if $\varphi=\varphi_1 \to \varphi_2$, then if $v(p)=T$: $v(\varphi)=v(\varphi_1 \to \varphi_2) = T \to T = T$

Check!

Finally, by the claim that we have now proven, any expression $\varphi$ built up from $p$, $\land$, and $\to$ cannot express a truth-function $f(p)$ for which $f(T) =$. Therefore, $\land, \to$ cannot capture $\neg$.

• Nice one! Thanks again for all the help (in this and in other logic question I've been asking around today and days before) =) – user313212 Jun 20 '17 at 18:48

This reasoning is correct. Hint: you can prove it rigorously by proving that any logical function built from them is truth-preserving ("returns T under any interpretation which assigns T to all variables"), by inducting on the "depth" of function (how many "levels of composition" it took to make the function).

In general, Emil Post proved that a set of logical connectives is functionally complete if and only if it is not a subset of any of five sets of connectives, characterized here. Using this criterion, $\{ \land, \rightarrow \}$ is not functionally complete precisely because both of these are truth-preserving, which is exactly what you noticed them to be.