0

If I had two propositions, P and Q, and wanted to write an expression such that either P or Q are true but not both, what would be the best notation for it?

Chillo
  • 29
  • $$P\bar Q+\bar PQ$$ http://en.wikipedia.org/wiki/XOR_gate or http://en.wikipedia.org/wiki/Exclusive_or – lab bhattacharjee Jan 31 '14 at 15:09
  • Wikipedia has a nice roundup at the end of this paragraph after some explanations: http://en.wikipedia.org/wiki/Exclusive_disjunction#Equivalencies.2C_elimination.2C_and_introduction – Piwi Jan 31 '14 at 15:14

2 Answers2

3

The most common term is "exclusive or", abbreviated "xor".

As for logical notation, just translating what you said does nicely. Two ways of writing it would be $$ (P\lor Q)\land\lnot(P\land Q)\\ (\lnot P \land Q) \lor (P\land \lnot Q) $$

Arthur
  • 199,419
2

The simplest way in terms of the most common connectives would be $$(P \wedge \neg Q) \vee (\neg P \wedge Q)$$ You could bash this with de Morgan's laws: $P \wedge \neg Q$ is equivalent to $\neg (P \to Q)$ and $\neg P \wedge Q$ is equivalent to $\neg (Q \to P)$, so we can write this as $$\neg (P \to Q) \vee \neg (Q \to P)$$ which is itself equivalent to $$(P \to Q) \to \neg (Q \to P)$$ I don't really know why you'd want to do this though, I'm just listing some options for you to choose from!

Sometimes this is expressed with an 'xor' operator $\oplus$, in which case it's simply $$P \oplus Q$$ but this notation is much less widespread than $\wedge\ \vee\ \neg\ \to$.

Clive Newstead
  • 64,925
  • Great answer, thanks! – Chillo Jan 31 '14 at 15:14
  • 1
    You could add to this list the (probably shortest without defining something new) form $\neg (P\leftrightarrow Q)$. Not very intuitive or particularly useful though... – Piwi Jan 31 '14 at 15:19