# Proving inadequacy given a set of connectives

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

• 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. Commented Jan 29, 2016 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)$