# Prove that $\{\wedge, \rightarrow\}$ is functionally incomplete

I know that I need to show that the relation $$\neg$$ can't be expressed.

I proved that the set $$\{\wedge, \rightarrow\}$$ is

• truth preserving: return the truth value T under any interpretation which assigns T to all variables.

If I take the assignment   $$v$$   that assigns T to any atomic $$p_i$$, so  $$v(\Phi)=T$$  for any expression $$\Phi$$ that consists of those $$p_i$$'s.

I am having problem to show the punchline: that any combination of $$\{\wedge, \rightarrow\}$$ is not equivalent to the negation relation $$\neg$$.

Can anyone help me finish the proof?

I tried to assume the opposite but couldn't finish the proof. Please advise.

• Why not to finish the proof with Post's theorem? Mar 20, 2021 at 18:56
• If $v$ assigns T to $p$, what is $v(\neg p)$? Is that consistent with what you’ve already shown about $\{\land,\to\}$? Mar 20, 2021 at 19:05
• @VIVID Can't use it, unfortunately =\ Mar 20, 2021 at 19:06
• @BrianM.Scott $v(\neg p)$ is "illegal" (as far as I understand). Mar 20, 2021 at 19:08
• @Dennis: You’re trying to show that it is not equivalent to any formula using only $\land$ and $\to$. $\neg p$ is not such a formula, but it still has a truth value under any given interpretation. And you’ve shown that its value under any interpretation that assigns T to $p$ is different from that of every formula that uses only $\land$ and $\to$, so … ? Mar 20, 2021 at 19:11