Boolean Algebra

This page explains Boolean algebra and logical operations.

<Note>
This page uses MathJax to display formulas. If your browser settings block script execution, the formulas on this page will not display correctly.

Truth values and logical operations

Consider reasoning about things using only two choices, “yes” and “no”, such as whether a proposition is correct or not. There is a field of mathematics like this, called Boolean algebra or Boolean logic. As technical terms, “yes” and “no” would be odd, so “true” and “false” are used instead, and these two are called truth values. Furthermore, these values are often mapped to the numbers 1 and 0 respectively.

Just as ordinary numbers have the four arithmetic operations, truth values have operations called logical operations. There are several kinds of logical operations, but only the important ones are explained here.

Negation

Definition
The operation that reverses a truth value is called negation.
The negation of a truth value \(\ P\ \) is written \(\ \lnot P,\ !P,\ \mathrm{NOT}\ P\ \).

Conjunction (logical AND)

Definition
The operation that is true only when two truth values \(\ P,Q\ \) are both true, and false otherwise, is called conjunction (logical AND).
The conjunction of truth values \(\ P,Q\ \) is written \(\ P \land Q,\ P\&Q,\ P\ \mathrm{AND}\ Q\ \).

Disjunction (logical OR)

Definition
The operation that is false only when two truth values \(\ P,Q\ \) are both false, and true otherwise, is called disjunction (logical OR).
The disjunction of truth values \(\ P,Q\ \) is written \(\ P \lor Q,\ P|Q,\ P\ \mathrm{OR}\ Q\ \).

NAND

Definition
The negation of conjunction is called NAND.
The NAND of truth values \(\ P,Q\ \) is written \(\ P \uparrow Q,\ P\ \mathrm{NAND}\ Q\ \).

Definition
The negation of disjunction is called NOR.
The NOR of truth values \(\ P,Q\ \) is written \(\ P \downarrow Q,\ P\ \mathrm{NOR}\ Q\ \).

Exclusive OR

Definition
The operation that is true only when two truth values \(\ P,Q\ \) differ from each other, and false otherwise, is called exclusive OR.
The exclusive OR of truth values \(\ P,Q\ \) is written \(\ P \not\leftrightarrow Q,\ P \not\equiv Q,\ P\oplus Q,\ P\ \mathrm{XOR}\ Q\ \).

Equivalence (necessary and sufficient condition)

Definition
The negation of exclusive OR is called equivalence, or necessary and sufficient condition.
The equivalence of truth values \(\ P,Q\ \) is written \(\ P \leftrightarrow Q,\ P \equiv Q,\ P\ \mathrm{XNOR}\ Q,\ P\ \mathrm{IFF}\ Q\ \).

Properties of logical operations

Just as the four arithmetic operations on ordinary numbers have various properties, logical operations also have various properties.

Theorem
For logical operations, the following properties always hold.
\[\begin{array}{ll} {P\land P=P\\ P\lor P=P} & \mbox{(idempotent laws)}\\ {P\land Q=Q\land P\\ P\lor Q=Q\lor P} & \mbox{(commutative laws)}\\ {(P\land Q)\land R=P\land(Q\land R) \\ (P\lor Q)\lor R=P\lor (Q\lor R)} & \mbox{(associative laws)}\\ {P\lor(Q\land R)=(P\lor Q)\land(P\lor R)\\ P\land(Q\lor R)=(P\land Q)\lor(P\land R)} & \mbox{(distributive laws)}\\ {P\lor(P\land Q)=P\\ P\land(P\lor Q)=P} & \mbox{(absorption laws)}\\ P\land 0=0\\ P\lor 0=P\\ P\land 1=P\\ P\lor 1=1\\ P\land (\lnot P)=0\\ P\lor (\lnot P)=1\\ \lnot(\lnot P)=P & \mbox{(double negation)}\\ \end{array} \]

In addition, logical operations have the following important properties.

Theorem (functional completeness of NOR and NAND)
Every logical operation can be expressed using only a combination of multiple NAND operations, or only of multiple NOR operations.

Theorem (De Morgan’s laws)
For conjunction and disjunction and their negations, the following equations hold.
\[\begin{gathered} \lnot(P\lor Q)=(\lnot P)\land(\lnot Q)\\ \lnot(P\land Q)=(\lnot P)\lor(\lnot Q) \end{gathered}\]

Logical operations on arbitrary numbers

So far we have considered logical operations on truth values. By applying these, we can in fact consider logical operations on arbitrary integers.

Definition
For arbitrary integers \(\ P,Q\ \), the result of a logical operation on these values is the value obtained as the result of the bitwise logical operation on their binary representations.

By applying the logical operation to each pair of bits in the same position (empty positions are of course treated as 0), logical operations are extended to general integers without losing any of their properties. For example, the OR, AND and XOR of the two numbers 174 and 231 are as follows.

Exercise
Compute the OR, AND and XOR of the two numbers 174 and 231.
174 is 0b10101110 in binary and 231 is 0b11100111 in binary, so
\[\begin{array}{lll} \begin{array}{ll} & 1010\ 1110\\ \mathrm{OR} & 1110\ 0111\\ \hline & 1110\ 1111=239 \end{array} & \begin{array}{ll} & 1010\ 1110\\ \mathrm{AND} & 1110\ 0111\\ \hline & 1010\ 0110=166 \end{array} & \begin{array}{ll} & 1010\ 1110\\ \mathrm{XOR} & 1110\ 0111\\ \hline & 0100\ 1001=73 \end{array} \end{array}\]

Logical negation for arbitrary numbers can be defined in the same way, and it ends up being exactly the bit inversion operation.