Let $\oplus$ be a binary connective defined by the truth table:

$\begin{array} {|r|r|} \hline p &q & p \oplus q\\ \hline 0 &0 &0\\ \hline 0 &1 &1\\ \hline 1 &0 &1\\ \hline 1 &1 &0\\ \hline \end{array}$

I am trying to prove that the set of connectives $\{\lnot,\oplus\}$ is not adequate.

I was thinking it would be impossible to construct the standard connective $\land$ from $\{\lnot,\oplus\}$ since the truth value would always be 0 for p=1,q=1 so there doesn't exist a formula $f$ such that $p\land q \vDash f$ but I am not sure if this would be correct. Can anyone help please? Thanks in advance

  • $\begingroup$ Questions about functionally complete (or in your terminology adequate) sets of propositional connectives have been asked on MSE many times before. See en.wikipedia.org/wiki/Functional_completeness for Post's theorem that answers the question. $\endgroup$ – Rob Arthan Jan 29 '16 at 23:54

It's inadequate because the operations you provide is modulo2 addition and ones complementation (ie $-1-x$). This means that any expression in $p$ and $q$ would need to be a affine combination of $p$ and $q$ with integer coefficients. That is that it should be able to write as $\alpha p + \beta q + \gamma$.

Now making this odd only when $p$ and $q$ are would be impossible, for example assume that $p$ and $q$ are odd and $\alpha p + \beta q + \gamma$ is odd then consider what would happen if we add one to $p$ or $q$. That would mean that $\alpha p + \beta (q+1) + \gamma$ would be even which means that $\beta$ is odd, in the same way we can conclude that $\alpha$ is odd. This means that $(\alpha-1)p + (\beta-1)q$ would be even and $\alpha p + \beta q + \gamma = (\alpha-1)p + (\beta-1)q + \gamma + p+q$ which means the eveness of the expression would depend on the eveness of $\gamma$ on one hand and on the other hand the eveness of $p+q$. This means that if the expression is odd for odd $p$ and $q$ it would be odd also for even $p$ and $q$.

You could alternatively note that since it's modulo 2 algebra that only values $0$ and $1$ matters, and the expression could be written as the $\oplus$-ing of selected occurences of $a$, $b$ and $1$. This results in eight possibilities. You can construct $0$, $1$, $a$, $a \oplus 1 =\neg a$, $b$, $b\oplus1=\neg b$, $a\oplus b$ and $a\oplus b\oplus 1 = \neg (a\oplus b)$


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.