Definition:Exclusive Or

From ProofWiki
Jump to navigation Jump to search

Definition

Exclusive Or is a binary connective which can be written symbolically as $p \oplus q$ whose behaviour is as follows:

$p \oplus q$

means:

Either $p$ is true or $q$ is true but not both.


or symbolically:

$p \oplus q := \paren {p \lor q} \land \neg \paren {p \land q}$

where $\land$ denotes the and operator and $\lor$ denotes the or operator.


There is no standard symbol for this, but the one shown above is seen commonly enough to be adopted as standard for this site.


Truth Function

The exclusive or connective defines the truth function $f^\oplus$ as follows:

\(\displaystyle f^\oplus \left({F, F}\right)\) \(=\) \(\displaystyle F\)
\(\displaystyle f^\oplus \left({F, T}\right)\) \(=\) \(\displaystyle T\)
\(\displaystyle f^\oplus \left({T, F}\right)\) \(=\) \(\displaystyle T\)
\(\displaystyle f^\oplus \left({T, T}\right)\) \(=\) \(\displaystyle F\)


Truth Table

The characteristic truth table of the exclusive or operator $p \oplus q$ is as follows:

$\begin{array}{|cc||c|} \hline p & q & p \oplus q \\ \hline F & F & F \\ F & T & T \\ T & F & T \\ T & T & F \\ \hline \end{array}$


Boolean Interpretation

The truth value of $\mathbf A \oplus \mathbf B$ under a boolean interpretation $v$ is given by:

$v \left({\mathbf A \oplus \mathbf B}\right) = \begin{cases} F & : v \left({\mathbf A}\right) = v \left({\mathbf B}\right) \\ T & : \text{otherwise} \end{cases}$


Notational Variants

Various symbols are encountered that denote the concept of exclusive or:

Symbol Origin Known as
$p \oplus q$ sometimes called o-plus
$p\ \mathsf{XOR} \ q$
$p + q$
$p \not \Leftrightarrow q$
$p \not \equiv q$
$p \ne q$
$p \ \dot \lor \ q$
$p \ \_ \lor \ q$


Also known as

This usage of or, that disallows the case where both disjuncts are true, is also called:

  • exclusive disjunction
  • logical inequality
  • non-equivalence
  • symmetric difference
  • the alternative function
  • aut (from the Latin), pronounced out.

Some sources refer to this as the strong or, where the weak or is used in the sense of the inclusive or.

In natural language, when it is necessary to be precise about the nature of the term being used, the phrase but not both is often employed.


Examples

Monday or Not Monday

The following is an example of an exclusive or statement:

Either today is Monday or today is not Monday.


One of Five Statements is True

Which of the following $5$ statements is true?

$(1): \quad$ Exactly one of these statements is false.
$(2): \quad$ Exactly two of these statements are false.
$(3): \quad$ Exactly three of these statements are false.
$(4): \quad$ Exactly four of these statements are false.
$(5): \quad$ Exactly five of these statements are false.


Also see

  • Results about exclusive or can be found here.


Sources