Transform $(\phi \vee \psi) \wedge (\neg \phi \vee \neg \psi) $ to $ (\phi \wedge \neg \psi) \vee (\neg \phi \wedge \psi)$ using equivalences?

121 Views Asked by At

$(\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?

2

There are 2 best solutions below

0
On

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)$

0
On

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)$$