Exclusive Disjunction of Formulas
By the definition of a formula, if the logical operator \(\veebar\) is applied to formulas \(A,B\), the resulting expression \begin{equation*}
A\veebar B
\end{equation*}is also a formula. The symbol \(\veebar\) is a logical operator called exclusive disjunction, and the formula \(A\veebar B\) is called the exclusive disjunction of \(A\) and \(B\), or “either \(A\) or \(B\)” (\(A\) or \(B\), but not both).
P &:&\text{Suzuki is lying} \\
Q &:&\text{Kato is lying}.
\end{eqnarray*}Then “Both Suzuki and Kato are lying” is formalized as
\begin{equation*}
P\wedge Q,
\end{equation*}while “Neither Suzuki nor Kato is lying” is formalized as
\begin{equation*}
\lnot P\wedge \lnot Q.
\end{equation*}Therefore, the entire statement is formalized as
\begin{equation*}
\left( P\wedge Q\right) \veebar \left( \lnot P\wedge \lnot Q\right).
\end{equation*}
P &:&\text{The husband works} \\
Q &:&\text{The wife works}.
\end{eqnarray*}Then
\begin{eqnarray*}
P\wedge \lnot Q &:&\text{The husband works and the wife does not} \\
\lnot P\wedge Q &:&\text{The husband does not work and the wife does}.
\end{eqnarray*}Therefore,
\begin{equation*}
\left( P\wedge \lnot Q\right) \veebar \left( \lnot P\wedge Q\right) :\text{Either the husband works and the wife does not, or the husband does not work and the wife does}
\end{equation*}holds.
Interpretation of Exclusive Disjunction
The value of the exclusive disjunction \(A\veebar B\) depends on the values of \(A\) and \(B\). The correspondence is defined by the following truth table.
$$\begin{array}{ccc}\hline
A & B & A\veebar B \\ \hline1 & 1 & 0 \\ \hline1 & 0 & 1 \\ \hline0 & 1 & 1 \\ \hline0 & 0 & 0 \\ \hline\end{array}$$
Thus, exclusive disjunction \(\veebar\) is a logical operation that takes formulas \(A,B\) as inputs and outputs a formula \(A\veebar B\) whose value is \(1\) if and only if exactly one of \(A\) and \(B\) has value \(1\). In the remaining cases, namely when both \(A\) and \(B\) have value \(1\) or when both have value \(0\), the value of \(A\veebar B\) is \(0\).
For the disjunction \(A\vee B\) to be true, it is sufficient that at least one of \(A\) and \(B\) be true, and \(A\vee B\) is also true when both \(A\) and \(B\) are true. By contrast, the exclusive disjunction \(A\veebar B\) is true only when exactly one of \(A\) and \(B\) is true. When both \(A\) and \(B\) are true, \(A\veebar B\) is not true. This is the difference between exclusive disjunction and disjunction.
$$\begin{array}{ccc}\hline
P & Q & P\veebar Q \\ \hline1 & 1 & 0 \\ \hline1 & 0 & 1 \\ \hline0 & 1 & 1 \\ \hline0 & 0 & 0 \\ \hline\end{array}$$
$$\begin{array}{cccccc}\hline
P & T & F & P\veebar T & P\veebar F & T\veebar F \\ \hline1 & 1 & 0 & 0 & 1 & 1 \\ \hline0 & 1 & 0 & 1 & 0 & 1 \\ \hline\end{array}$$
\left( P\veebar Q\right) \veebar R,
\end{equation*}is also a formula. Their truth values satisfy the following relation.
$$\begin{array}{ccccc}\hline
P & Q & R & P\veebar Q & \left( P\veebar Q\right) \veebar R \\ \hline
1 & 1 & 1 & 0 & 1 \\ \hline1 & 1 & 0 & 0 & 0 \\ \hline1 & 0 & 1 & 1 & 0 \\ \hline1 & 0 & 0 & 1 & 1 \\ \hline0 & 1 & 1 & 1 & 0 \\ \hline0 & 1 & 0 & 1 & 1 \\ \hline0 & 0 & 1 & 0 & 1 \\ \hline0 & 0 & 0 & 0 & 0 \\ \hline\end{array}$$
$$\begin{array}{ccccccc}\hline
P & Q & \lnot P & \lnot Q & P\veebar Q & \lnot P\veebar Q & P\veebar \lnot Q \\ \hline1 & 1 & 0 & 0 & 0 & 1 & 1 \\ \hline1 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \hline0 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline\end{array}$$
$$\begin{array}{ccccccc}\hline
P & Q & R & \lnot P & \lnot R & \lnot P\wedge Q & \left( \lnot P\wedge Q\right) \veebar \lnot R \\ \hline1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline1 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline1 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline1 & 0 & 0 & 0 & 1 & 0 & 1 \\ \hline0 & 1 & 1 & 1 & 0 & 1 & 1 \\ \hline0 & 1 & 0 & 1 & 1 & 1 & 0 \\ \hline0 & 0 & 1 & 1 & 0 & 0 & 0 \\ \hline0 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline\end{array}$$
Relationship Between Exclusive Disjunction and Negation, Conjunction, and Disjunction
For arbitrary formulas \(A,B\), we obtain the following truth table.
$$\begin{array}{cccccc}\hline
A & B & A\veebar B & A\wedge \lnot B & \lnot A\wedge B & \left(A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \\ \hline1 & 1 & 0 & 0 & 0 & 0 \\ \hline1 & 0 & 1 & 1 & 0 & 1 \\ \hline0 & 1 & 1 & 0 & 1 & 1 \\ \hline0 & 0 & 0 & 0 & 0 & 0 \\ \hline\end{array}$$
The truth table above shows that the value of the exclusive disjunction \(A\veebar B\) always agrees with the value of the formula \begin{equation*}
\left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right).
\end{equation*}This means that exclusive disjunction \(\veebar\) can be defined indirectly in terms of negation \(\lnot\), conjunction \(\wedge\), and disjunction \(\vee\). Therefore, once negation, conjunction, and disjunction have been defined, it is not strictly necessary to define exclusive disjunction as a new logical operation. Nevertheless, defining exclusive disjunction as an independent logical operation is often convenient, so we continue to use \(\veebar\) in this text.
Exercises
- Either you go buy eggs, or we will have fried rice without eggs.
- Exactly one of Kato and Suzuki is absent.
- Satoshi is either at the office or at the gym.
- Either every integer is divisible by \(2\), or it is not the case that every integer is divisible by \(2\).
P &:&\text{Kato is at home} \\
Q &:&\text{Suzuki is at home}.
\end{eqnarray*}One person formalized the statement as
\begin{equation*}
\left( P\wedge \lnot Q\right) \vee \left( Q\wedge \lnot P\right),
\end{equation*}while another formalized it as
\begin{equation*}
P\veebar Q.
\end{equation*}Which is correct? Give your answer with a reason.
$$\begin{array}{ccccccc}\hline
P & Q & T & F & P\wedge Q & \left( P\wedge Q\right) \veebar T & \left( P\wedge Q\right) \veebar F \\ \hline1 & 1 & 1 & 0 & & & \\ \hline1 & 0 & 1 & 0 & & & \\ \hline0 & 1 & 1 & 0 & & & \\ \hline0 & 0 & 1 & 0 & & & \\ \hline\end{array}$$
$$\begin{array}{ccccccc}\hline
P & Q & T & F & P\veebar Q & \left( P\veebar Q\right) \veebar T& \left( P\veebar Q\right) \veebar F \\ \hline1 & 1 & 1 & 0 & & & \\ \hline1 & 0 & 1 & 0 & & & \\ \hline0 & 1 & 1 & 0 & & & \\ \hline0 & 0 & 1 & 0 & & & \\ \hline\end{array}$$
\begin{equation*}
\left( \left( \cdots \left( \cdots \left( \left( A_{1}\veebar A_{2}\right)
\veebar A_{3}\right) \veebar \cdots \right) \veebar A_{n-1}\right) \veebar A_{n}\right)
\end{equation*}is true.
