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.

  • $\begingroup$ Why not to finish the proof with Post's theorem? $\endgroup$
    – VIVID
    Mar 20, 2021 at 18:56
  • 1
    $\begingroup$ If $v$ assigns T to $p$, what is $v(\neg p)$? Is that consistent with what you’ve already shown about $\{\land,\to\}$? $\endgroup$ Mar 20, 2021 at 19:05
  • $\begingroup$ @VIVID Can't use it, unfortunately =\ $\endgroup$
    – Dennis
    Mar 20, 2021 at 19:06
  • $\begingroup$ @BrianM.Scott $v(\neg p)$ is "illegal" (as far as I understand). $\endgroup$
    – Dennis
    Mar 20, 2021 at 19:08
  • $\begingroup$ @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 … ? $\endgroup$ Mar 20, 2021 at 19:11


You must log in to answer this question.

Browse other questions tagged .