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$


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$.

| cite | improve this answer | |
  • $\begingroup$ Nice one! Thanks again for all the help (in this and in other logic question I've been asking around today and days before) =) $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.