1

$(\phi \oplus \psi) \equiv (\phi \vee \psi) \wedge (\neg \phi \vee \neg \psi) \equiv (\phi \wedge \neg \psi) \vee (\neg \phi \wedge \psi)$

I found the first one in a book and thought of the second one myself and was under the impression that I can transform one into the other using just the usual equivalences for classical propositional logic. How do I transform $(\phi \vee \psi) \wedge (\neg \phi \vee \neg \psi) $ to $ (\phi \wedge \neg \psi) \vee (\neg \phi \wedge \psi)$ using just the usual equivalences?

steve
  • 639
  • 1
  • 5
  • 8

2 Answers2

1

I wrote down my question and instantly knew the answer. I just leave this here since I already typed it.

$(\phi \vee \psi) \wedge (\neg \phi \vee \neg \psi) $

$\equiv (\phi \wedge (\neg \phi \vee \neg \psi)) \vee (\psi \wedge (\neg \phi \vee \neg \psi)) $

$\equiv (\phi \wedge \neg \psi) \vee (\neg \phi \wedge \psi)$

steve
  • 639
  • 1
  • 5
  • 8
0

Another approach:

XOR is a negation of equivalence: $$\neg (P\iff Q)\equiv \neg\underbrace{(P\implies Q)\land(Q\implies P)}_{\text{conjunction}}\equiv\\\neg(P\implies Q)\lor \neg(Q\implies P)\equiv (P\land\neg Q)\lor(Q\land\neg P)$$

PinkyWay
  • 4,565