Boolean Algebra

In mathematical logic, Boolean algebra (boolean algebra) is a branch of algebra. In elementary algebra, the values of variables are numbers, and its main operations are addition, multiplication, exponentiation, and the inverse operations of these three operations. In Boolean algebra, however, variable values are only true and false (usually written as $1$ and $0$), and its main operations are conjunction (AND, $\land$), disjunction (OR, $\lor$), and negation (NOT, $\lnot$). Just as elementary algebra is a form for describing numerical operations, Boolean algebra is a form for describing logical operations.

Boolean Functions

Definition

A Boolean function (boolean function) is a function of the form $f:\mathbf{B}^k\to \mathbf{B}$, where $\mathbf{B}=\{0,1\}$ is the Boolean domain (boolean domain), and the nonnegative integer $k$ is the arity of the Boolean function. A Boolean function with $k=1$ is a unary function, and so on. When $k=0$, we consider the function to be a constant in $\mathbf{B}$.

We generally study only unary and binary functions. Unless otherwise specified, the Boolean functions below are limited to unary and binary functions.

In addition to the usual expression of a function, we can also represent a Boolean function using a truth table (truth table), a logic gate (logic gate), or a Venn diagram.

Truth Table

For a Boolean function, we enumerate all possible input cases and list the inputs and corresponding outputs in a table. This table is called a truth table.

An $n$-ary Boolean function can also be represented by a propositional formula (propositional formula) containing $n$ variables. A propositional formula $p$ and $q$ are logically equivalent if and only if they describe the same Boolean function, written as $p\iff q$.

The following are some common Boolean functions. We also collectively call these Boolean functions logical connectives (logical connective) or logical operators (logical operator):

The corresponding truth table (From Wikipedia):

The corresponding Venn diagram and Hasse diagram (with the inclusion relation of sets $\subseteq$ as the partial order, From Wikipedia):

Since the inputs of an $n$-ary Boolean function have $2^n$ possible values, there are $2\uparrow (2\uparrow n)$ $n$-ary Boolean functions, where $\uparrow$ is the Knuth arrow.

We call a combination of logical operators a logical expression (logical expression).

If we regard $\mathbf{B}$ as a residue class modulo $2$, then XOR is equivalent to addition modulo $2$, and equivalence is equivalent to multiplication modulo $2$. Thus, we sometimes use $\mathbf{Z}_2$ to represent the Boolean domain.

Precedence

Unary logical operators have higher precedence than binary logical operators; that is, the precedence of $\lnot$ is higher than that of $\land$, $\lor$, $\oplus$, and so on.

There are multiple conventions for the precedence among binary logical operators. Some sources consider $\land$, $\lor$, and $\oplus$ to have higher precedence than $\to$, $\gets$, and $\leftrightarrow$, while other sources take the opposite view. Therefore, it is recommended to add more parentheses to make the order explicit when using them.

The conventions in C++ can be found in C++ Operator Precedence Overview.

Functionally Complete Operators and Complete Operator Sets

In fact, the rest of the logical operators can be expressed using only NAND or NOR; CPUs are also built on this fact. However, because the four logical operators AND, OR, NOT, and XOR have better properties, we generally use only these four functions when studying Boolean algebra.

How to Express the Remaining Logical Operators Using NAND and NOR Separately

We have

• $\lnot p=p\bar{\land} p=p\bar{\lor} p$,
• $p\land q=(p\bar{\land}q)\bar{\land}(p\bar{\land}q)=(p\bar{\lor}p)\bar{\lor}(q\bar{\lor}q)$,
• $p\lor q=(p\bar{\land}p)\bar{\land}(q\bar{\land}q)=(p\bar{\lor}q)\bar{\lor}(p\bar{\lor}q)$,
• $p\to q=p\bar{\land} (q\bar{\land} q)=((p\bar{\lor}p)\bar{\lor}q)\bar{\lor}((p\bar{\lor}p)\bar{\lor}q)$.

In addition

• $p=\lnot\lnot p$,
• $p\nleftrightarrow q=p\oplus q=(p\lor q)\land\lnot (p\land q)$,
• $p\leftrightarrow q=p\odot q=\lnot(p\oplus q)$,
• $p\nrightarrow q=\lnot(p\to q)$,
• $p\gets q=q\to p$,
• $p\nleftarrow q=\lnot(p\gets q)$.

Can all logical operators be described using a specified set of logical operators? This leads to the definition of a functionally complete operator set.

Definition

For a given set of logical operators, if all logical operators can be described using only functions in this set, then the set is called a functionally complete operator set (functionally complete operator set). In particular, if all logical operators can be described using only one logical operator, that operator is called a sole sufficient operator (sole sufficient operator) or a Sheffer function (Sheffer function).

If removing any element from a functionally complete operator set makes it unable to describe all logical operators, the set is called a minimal functionally complete operator set (minimal functionally complete operator set).

It can be proved that only $\bar{\land}$ and $\bar{\lor}$ among logical operators are sole sufficient operators.

The following are common minimal functionally complete operator sets⁴:

• $\{\bar{\land}\}$, $\{\bar{\lor}\}$,
• $\{\land,\lnot\}$, $\{\lor,\lnot\}$, $\{\gets,\lnot\}$, $\{\to,\lnot\}$, $\{\nleftarrow,\lnot\}$, $\{\nrightarrow,\lnot\}$,
• $\{\gets,\bot\}$, $\{\to,\bot\}$, $\{\nleftarrow,\top\}$, $\{\nrightarrow,\top\}$,
• $\{\gets,\nleftarrow\}$, $\{\to,\nleftarrow\}$, $\{\gets,\nrightarrow\}$, $\{\to,\nrightarrow\}$,
• $\{\gets,\nleftrightarrow\}$, $\{\to,\nleftrightarrow\}$, $\{\nleftarrow,\leftrightarrow\}$, $\{\nrightarrow,\leftrightarrow\}$,
• $\{\lor,\leftrightarrow,\bot\}$, $\{\lor,\leftrightarrow,\nleftrightarrow\}$, $\{\lor,\nleftrightarrow,\top\}$,
• $\{\land,\leftrightarrow,\bot\}$, $\{\land,\leftrightarrow,\nleftrightarrow\}$, $\{\land,\nleftrightarrow,\top\}$.

Properties

First are properties related to algebraic structures:

• AND and OR each form a commutative monoid over $\mathbf{B}$. That is, both AND and OR have commutativity, associativity, and an identity element ($x\land 1=x\lor 0=x$).
• XOR and XNOR each form a group over $\mathbf{B}$. That is, both XOR and XNOR have commutativity, associativity, an identity element ($x\oplus 0=x\odot 1=x$), and an inverse element ($x\oplus x=0$, $x\odot x=1$).
• NAND and NOR are not associative, so they do not form semigroups.

For $\land$ and $\lor$, we have

• Distributive laws:
  • $a\land(b\diamond c)=(a\land b)\diamond (a\land c)$, where $\diamond$ can be $\land$, $\lor$, or $\oplus$,
  • $a\lor(b\diamond c)=(a\lor b)\diamond (a\lor c)$, where $\diamond$ can be $\land$, $\lor$, or $\odot$.
• Idempotent law: $x\land x=x$, $x\lor x=x$.
• Monotonicity: $a\to b\iff(a\land c)\to(b\land c)$, $a\to b\iff(a\lor c)\to(b\lor c)$.
• Absorption law: $x\land(x\lor y)=x\lor(x\land y)=x$.
• Relationship with "$\to$":
  • $a \lor b \iff (\lnot a \to b) \land (\lnot b \to a)$,
  • $a \land b \iff \lnot((a \to \lnot b) \lor (b \to \lnot a))$.

Monotonicity of Boolean Functions

For a Boolean function $f(x_1,\dots,x_n)$ and two elements $(a_1,\dots,a_n),(b_1,\dots,b_n)$ in $\mathbf{B}^n$, if $a_i\leq b_i,~~\forall i=1,\dots,n$ always implies $f(a_1,\dots,a_n)\leq f(b_1,\dots,b_n)$, then the Boolean function is called monotonic.

We also have the following properties:

• Law of excluded middle: $p\lor\lnot p$ is always true.
• $\lnot p\iff p\to\bot$.
• Double negation / the involution law of $\lnot$: $\lnot\lnot x=x$.
• The involution law of $\oplus$ and $\odot$: $x\oplus y\oplus y=x$, $x\odot y\odot y=x$.
• De Morgan's laws: $\lnot(p\land q)=\lnot p\lor \lnot q$, $\lnot(p\lor q)=\lnot p\land \lnot q$.

Normalization of Logical Expressions

According to the properties above, we can apply certain equivalent transformations to logical expressions so that they conform to a particular normal form. This can be used in automated theorem proving. Common normal forms include conjunctive normal form (conjunctive normal form, CNF), disjunctive normal form (disjunctive normal form, DNF), and algebraic normal form (algebraic normal form, ANF).

Conjunctive Normal Form and Disjunctive Normal Form

We make the following recursive definitions:

1. Literal (literal): For a variable $x$, $x$ and $\lnot x$ are literals.
2. Subformula:
   • A literal is a subformula.
   • If $A$ is a literal and $B$ is a subformula, then $A\lor B$ is a subformula.
3. Conjunctive normal form:
   • If $A$ is a subformula, then $(A)$ is a conjunctive normal form.
   • If $A$ is a subformula and $B$ is a conjunctive normal form, then $(A)\land B$ is a conjunctive normal form.

Similarly, exchanging $\land$ and $\lor$ in the definition above gives the definition of disjunctive normal form.

For example, the following logical expressions are all disjunctive normal forms:

• $(A\land\lnot B)\lor(C\land D\land\lnot E)$,
• $(A\land B)\lor (C)$,
• $(A\land B)$,
• $(A)$.

The following logical expressions are all conjunctive normal forms:

• $(\lnot A\lor\lnot B\lor C)\land(\lor D\lor\lnot E)$,
• $(A\lor B)\land (C)$,
• $(A\lor B)$,
• $(A)$.

The following logical expressions are neither conjunctive nor disjunctive normal forms:

• $\lnot(A\land B)$,
• $A\land (B\lor (C\land D))$.

We can transform any logical expression containing only $\lnot$, $\land$, and $\lor$ operations into DNF using the following steps:

$$\begin{array}{rcccl} \lnot\lnot x &&\mapsto&& x,\\ \lnot(x\lor y) &&\mapsto&& \lnot x\land \lnot y,\\ \lnot(x\land y) &&\mapsto&& \lnot x\lor \lnot y,\\ x\land(y\lor z) &&\mapsto&& (x\land y)\lor (x\land z),\\ (x\lor y)\land z &&\mapsto&& (x\land z)\lor (y\land z). \end{array}$$

To obtain the CNF of expression $X$, simply obtain the DNF of $\lnot X$, then negate it and apply De Morgan's laws.

Algebraic Normal Form

First, we recursively define subformulas as follows:

• Variable $x$ is a subformula.
• If $A$ is a subformula and $x$ is a variable, then $x\land A$ is a subformula.

A logical expression satisfying one of the following three forms is an algebraic normal form:

1. $1$, $0$,
2. The XOR of several pairwise nonequivalent subformulas, such as $a\oplus b\oplus(a\land b)\oplus(a\land b\land c)$,
3. The XOR of several pairwise nonequivalent subformulas and the unique $1$, such as $1\oplus a\oplus b\oplus(a\land b)\oplus(a\land b\land c)$.

Notice that algebraic normal forms correspond one-to-one with polynomials over $\mathbf{Z}_2$, so algebraic normal forms are also called Zhegalkin polynomials (Zhegalkin polynomial).

We can transform any logical expression containing only $\lnot$, $\land$, $\lor$, and $\oplus$ operations into ANF using the following steps:

1. $\oplus$: Expand directly. For example, $(1\oplus x)\oplus(1\oplus x\oplus y)=1\oplus x\oplus 1\oplus x\oplus y=y$.
2. $\land$: Expand using the distributive law. For example, $x\land(1\oplus x\oplus y)=(x\land 1)\oplus (x\land x)\oplus (x\land y)=x\oplus (x\land y)$.
3. $\lnot$: Replace $\lnot x$ with $1\oplus x$. For example, $\lnot(1\oplus x\oplus y)=1\oplus 1\oplus x\oplus y=x\oplus y$.
4. $\lor$: Replace $x\lor y$ with $1\oplus((1\oplus x)\land(1\oplus y))$ or $x\oplus y\oplus (x\land y)$. For example, $(1\oplus x)\lor(1\oplus x\oplus y)=1\oplus((1\oplus 1\oplus x)\land(1\oplus 1\oplus x\oplus y))=1\oplus x\oplus(x\land y)$.

References and notes

1. Boolean algebra - Wikipedia
2. Boolean function - Wikipedia
3. Logical connective - Wikipedia
4. Disjunctive normal form - Wikipedia
5. Zhegalkin polynomial - Wikipedia

Footnotes

1. When used for propositional derivation, double long arrows should be used, such as $A\implies B$, $A\impliedby B$, and $A\iff B$. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. Equivalent to XNOR. ↩

3. Equivalent to XOR. ↩

4. Vaughan, H. E. (1942). Complete sets of logical functions.Transactions of the American Mathematical Society 51: 117–32. ↩