1

Prove $\neg B \wedge A$ cannot be expressed using only exclusive or (XOR) and negation of $A$ and $B$.

Exclusive or gives whether $A,B$ are different. So any statement's truth table is invariant to exchanging $A,B$ which is not true for $\neg B \wedge A$. This proves $\neg B \wedge A$ cannot be expressed as just exclusive or. But with negation, this is really not quite intuitive to me. I tried to prove by induction on number of xors. And I prove a stronger case where any XOR and negation alone cannot express any statement with truth table of three $T$ or three $F$. The base case is easy to check. The inductive case is to show "given that a statement with less than $n$ xors does not express aforementioned clause, show a statement with less than $n+1$ xors cannot either". Fix such a statement with $n$ xors, we may write it as $G(A,B) \oplus H(A,B)$. Suppose to contrary that $G \oplus H$ expresses some $3T$ or $3F$ statement, say $\neg B \wedge A$. Then it may be checked that one of $G,H$ can too. For example, to express $\neg B \wedge A$, draw truth table for both $G,H$; their $T,F$ entry must differ and all other 3 entries match. But this will force $3T,3F$ to appear in either $H$ or $G$'s truth table, contradicting inductive hypothesis.

I'm not a logician so this is the best I can think of myself.

Questions: what is the standard way of proving this? and are there more intuitive/easier way to understand this phenomenon. Thank you!

Daniel Li
  • 3,200
  • 1
    My answer to Implement using only XOR gates applies here too. – hmakholm left over Monica Aug 22 '19 at 23:43
  • By the way, your first argument does not work. XOR is invariant under exchange of its two inputs but nobody says those two inputs are $A$ and $B$ in partucular. For example, $A\oplus(B\oplus A)$ gives you a truth function that is not unchanged under swapping $A$ and $B$. – hmakholm left over Monica Aug 22 '19 at 23:46
  • @HenningMakholm Thank you very much. The answer you linked is using only XOR gates whereas this question involves XOR and negation. – Daniel Li Aug 22 '19 at 23:50
  • @HenningMakholm As to the first argument, I guess what I meant is that you may switch truth table input column for A,B (A,B,Result) and still have same Result column for a statement of xor only. This property is not shared by $\neg B \wedge A$. – Daniel Li Aug 23 '19 at 00:14
  • x @Daniel: The question I linked is for XOR and a "true" constant, and notes that negation can be made as $x\oplus 1$. – hmakholm left over Monica Aug 23 '19 at 09:57
  • x @Daniel: Your swap-the-columns argument only applies to a single XOR operation, not to an expression that is built from multiple operations where some feed input to others. Did you look at the example I gave? $A\oplus(B\oplus A)$ does not define the same truth function as $B\oplus(A\oplus B)$. – hmakholm left over Monica Aug 23 '19 at 09:58

1 Answers1

2

Your proof is basically sound. In my logic class we worked on induction by the formation of the statement. For instance, let $P(A)$ represent that the sentence A contains an even number of T's in its truth table. If you can show that $P(p)$ for every literal (the base case) and that $P(A)$ and $P(B)$ implied $P(\neg A)$ and $P(A\not\equiv B)$ (the inductive case), then it was true for any well-formed sentence whose operators were just negation and XOR. Therefore, no truth table with an odd number of T's in its truth table can be expressed with just negation and XOR.