Skip to content

Boolean Functions#

Definition: Boolean Function

A Boolean function is a function which takes a tuple whose elements come from a set of two elements and outputs one of the elements of the same set.

Notation

Most commonly, the elements of such a set are denoted by \(0\) and \(1\). This means that Boolean functions are usually written in the following way:

\[ f: \{0,1\}^n \to \{0,1\} \]

Sometimes, the labels \(\mathrm{F}\) and \(\mathrm{T}\) may be used instead of \(0\) and \(1\) because Boolean algebra is used ubiquitously in propositional logic.

Definition: Off-Set

The off-set of \(f\) is the set of all inputs for which \(f\) outputs \(0\):

\[ \overline{F} \overset{\text{def}}{=} \{x \in \{0,1\}^n \mid f(x) = 0\} \]

Definition: On-Set

The on-set of \(f\) is the set of all inputs for which \(f\) outputs \(1\):

\[ F \overset{\text{def}}{=} \{x \in \{0,1\}^n \mid f(x) = 1\} \]

Definition: Shannon Cofactors

The positive Shannon cofactor of \(f\) with respect to the \(i\)-th variable is the restriction of \(f\) to \(\{(x_1, \dotsc, x_{i-1}, 1, x_{i+1}, \dotsc, x_n) \mid x_k \in \{0,1\}\}\).

Notation

\[ f_{x_i} \]

The negative Shannon cofactor of \(f\) with respect to the \(i\)-th variable is the restriction of \(f\) to \(\{(x_1, \dotsc, x_{i-1}, 0, x_{i+1}, \dotsc, x_n) \mid x_k \in \{0,1\}\}\).

Notation

\[ f_{\overline{x_i}} \]

Definition: Contradiction

A Boolean function \(f: \{0,1\}^n \to \{0,1\}\) is a contradiction or contradictory when \(f(x) = 0\) for all \(x \in \{0, 1\}^n\).

Definition: Tautology

A Boolean function \(f: \{0,1\}^n \to \{0,1\}\) is a tautology or tautological when \(f(x) = 1\) for all \(x \in \{0, 1\}^n\).

Definition: Dependence and Independence

Let \(f: \{0,1\}^n \to \{0,1\}\) be a Boolean function.

We say that \(f\) is:

  • dependent on \(x_i\) if \(f(x_1, \dotsc, x_i, \dotsc, x_n) \ne f(x_1, \dotsc, \neg x_i, \dotsc, x_n)\);
  • independent of \(x_i\) if \(f(x_1, \dotsc, x_i, \dotsc, x_n) = f(x_1, \dotsc, \neg x_i, \dotsc, x_n)\).

Definition: Boolean Vector Function

A Boolean vector function is a function which takes and outputs tuples whose elements come from the same set of two elements:

\[ f: \{0,1\}^m \to \{0,1\}^n \]

Tip

Every Boolean vector function \(f: \{0,1\}^m \to \{0,1\}^n\) is equivalent to \(n\) Boolean functions \(f_1, \dotsc, f_n: \{0,1\}^m \to \{0,1\}\).

Theorem: Cofactor Substitution

The Shannon cofactors of a Boolean function \(f: \{0,1\}^n \to \{0,1\}\) obey the following rules:

\[ \begin{aligned} x_i \land f &= x_i \land f_{x_i} \\ \overline{x_i} \land f &= \overline{x_i} \land f_{\overline{x_i}} \\ x_i \lor f &= x_i \lor f_{\overline{x_i}} \\ \overline{x_i} \lor f &= \overline{x_i} \lor f_{x_i} \end{aligned} \]
Proof

We need to prove four things:

  • (1) \(x_i \land f = x_i \land f_{x_i}\).
  • (2) \(\overline{x_i} \land f = \overline{x_i} \land f_{\overline{x_i}}\).
  • (3) \(x_i \lor f = x_i \lor f_{\overline{x_i}}\).
  • (4) \(\overline{x_i} \lor f = \overline{x_i} \lor f_{x_i}\).

Proof of (1):

If \(x_i = 0\), then the left-hand side is \(x_i \land f = 0 \land f = 0\). Similarly, the right-hand side is \(x_i \land f_{x_i} = 0 \land f_{x_i} = 0\). The left-hand side and right-hand side are therefore equal when \(x_i = 0\).

If \(x_i = 1\), then the left-hand side is \(x_i \land f = 1 \land f = f\). Similarly, the right-hand side is \(x_i \land f_{x_i} = 1 \land f_{x_i} = f_{x_i}\). However, in this case, \(f\) and \(f_{x_i}\) are the same by definition. The left-hand side and right-hand side are therefore equal when \(x_i = 1\).

We have thus shown that the law holds for all possible values of \(x_i\), i.e. it holds in general.

Proof of (2):

If \(x_i = 0\), then the left-hand side is \(\overline{x_i} \land f = 1 \land f = f\). Similarly, the right-hand side is \(\overline{x_i} \land f_{\overline{x_i}} = \overline{0} \land f_{\overline{x_i}} = 1 \land f_{\overline{x_i}} = f_{\overline{x_i}}\). However, in this case, \(f\) and \(f_{\overline{x_i}}\) are the same by definition. The left-hand side and right-hand side are therefore equal when \(x_i = 1\). The left-hand side and right-hand side are therefore equal when \(x_i = 0\).

If \(x_i = 1\), then the left-hand side is \(\overline{x_i} \land f = \overline{1} \land f = 0 \land f = 0\). Similarly, the right-hand side is \(\overline{x_i} \land f_{\overline{x_i}} = \overline{1} \land f_{\overline{x_i}} = 0 \land f_{\overline{x_i}} = 0\). The left-hand side and right-hand side are therefore equal when \(x_i = 1\).

We have thus shown that the law holds for all possible values of \(x_i\), i.e. it holds in general.

Proof of (3):

Analogous.

Proof of (4):

Analogous.

Boole's Expansion Theorem

If \(f_{x_i}\) and \(f_{\overline{x_i}}\) are the Shannon cofactors of a logical connective \(f: \{0,1\}^n \to \{0, 1\}\) with respect to the \(i\)-th variable, then:

\[ f = (x_i \land f_{x_i}) \lor (\overline{x_i} \land f_{\overline{x_i}}) = (x_i \lor f_{\overline{x_i}}) \land (\overline{x_i} \lor f_{x_i}) \]
Proof

We need to prove two things:

  • (1) \(f = (x_i \land f_{x_i}) \lor (\overline{x_i} \land f_{\overline{x_i}})\).
  • (2) \(f = (x_i \lor f_{\overline{x_i}}) \land (\overline{x_i} \lor f_{x_i})\).

Proof of (1): The following proof was generated by AI and has not been human-verified. As such, it may contain mistakes.

If \(x_i = 1\):

  • The LHS becomes \(f(x_1, \dots, 1, \dots, x_n)\), which by definition is the cofactor \(f_{x_i}\).
  • The RHS becomes \((1 \land f_{x_i}) \lor (\overline{1} \land f_{\overline{x_i}})\).
  • Since \(\overline{1} = 0\), this simplifies to \((1 \land f_{x_i}) \lor (0 \land f_{\overline{x_i}})\).
  • Using the identities \(1 \land A = A\) and \(0 \land B = 0\), we get \(f_{x_i} \lor 0\).
  • Using the identity \(A \lor 0 = A\), the RHS simplifies to \(f_{x_i}\).
  • Thus, for \(x_i=1\), LHS = RHS.

If \(x_i = 0\):

  • The LHS becomes \(f(x_1, \dots, 0, \dots, x_n)\), which by definition is the cofactor \(f_{\overline{x_i}}\).
  • The RHS becomes \((0 \land f_{x_i}) \lor (\overline{0} \land f_{\overline{x_i}})\).
  • Since \(\overline{0} = 1\), this simplifies to \((0 \land f_{x_i}) \lor (1 \land f_{\overline{x_i}})\).
  • Using the identities \(0 \land A = 0\) and \(1 \land B = B\), we get \(0 \lor f_{\overline{x_i}}\).
  • Using the identity \(0 \lor B = B\), the RHS simplifies to \(f_{\overline{x_i}}\).
  • Thus, for \(x_i=0\), LHS = RHS.

Since the equality holds for both possible values of \(x_i\), the identity is proven true for all inputs.

Proof of (2): The following proof was generated by AI and has not been human-verified. As such, it may contain mistakes..

If \(x_i = 1\):

  • The LHS is again \(f(x_1, \dots, 1, \dots, x_n) = f_{x_i}\).
  • The RHS becomes \((1 \lor f_{\overline{x_i}}) \land (\overline{1} \lor f_{x_i})\).
  • Since \(\overline{1} = 0\), this simplifies to \((1 \lor f_{\overline{x_i}}) \land (0 \lor f_{x_i})\).
  • Using the identities \(1 \lor A = 1\) and \(0 \lor B = B\), we get \(1 \land f_{x_i}\).
  • Using the identity \(1 \land A = A\), the RHS simplifies to \(f_{x_i}\).
  • Thus, for \(x_i=1\), LHS = RHS.

If \(x_i = 0\):

  • The LHS is again \(f(x_1, \dots, 0, \dots, x_n) = f_{\overline{x_i}}\).
  • The RHS becomes \((0 \lor f_{\overline{x_i}}) \land (\overline{0} \lor f_{x_i})\).
  • Since \(\overline{0} = 1\), this simplifies to \((0 \lor f_{\overline{x_i}}) \land (1 \lor f_{x_i})\).
  • Using the identities \(0 \lor A = A\) and \(1 \lor B = 1\), we get \(f_{\overline{x_i}} \land 1\).
  • Using the identity \(A \land 1 = A\), the RHS simplifies to \(f_{\overline{x_i}}\).
  • Thus, for \(x_i=0\), LHS = RHS.

Theorem: Function Equivalence

Two Boolean functions \(f, g: \{0,1\}^n \to \{0,1\}\) are the same if and only if the function

\[ (\neg f \lor g) \land (f \lor \neg g) \]

is tautological.

Proof

TODO

Canonical Conjunctive Normal Form#

Theorem: Canonical Conjunctive Normal Form

Every non-tautological Boolean function can be expressed as a conjunctive normal form of \(p\) maxterms, where \(p\) is the cardinality of \(f\)'s off-set.

Definition: Canonical Conjunctive Normal Form (CCNF)

Such an expression is known as a canonical conjunctive normal form (CCNF) of \(f\).

Proof

TODO

Algorithm: Finding CCNFs

We are given a Boolean function \(f: \{0,1\}^n \to \{0,1\}\):

\[f(x_1, \dotsc, x_n)\]

  1. Identify the off-set \(\overline{F}\) of \(f\).

  2. For each \((x_1^{\ast}, \dotsc, x_n^{\ast}) \in \overline{F}\) construct the maxterm \(\mathop{\operatorname{OR}}(x_1', \dotsc, x_n')\), where

  • \(x_k' = x_k\) if \(x_k^{\ast} = 0\);
  • \(x_k' = \neg x_k\) if \(x_k^{\ast} = 1\).
  1. The conjunctive normal form of \(f\) is the conjunction of all the maxterms from step 2.
Example

The easiest way is to use the truth table of \(f\). Suppose \(f(x_1, x_2, x_3)\) has the following truth table:

\(x_1\) \(x_2\) \(x_3\) \(f(x_1, x_2, x_3)\)
\(0\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(1\)
\(0\) \(1\) \(0\) \(1\)
\(0\) \(1\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(0\)
\(1\) \(1\) \(0\) \(1\)
\(1\) \(1\) \(1\) \(0\)

The off-set of \(f\) is easily determined by looking at the rows which contain \(0\) in the column for \(f(x_1, x_2, x_3)\). In this example, these rows are \(1\), \(5\), \(6\), and \(8\).

On row \(1\) we see that \(x_1\), \(x_2\) and \(x_3\) are all \(0\). We therefore construct the maxterm \(x_1 \lor x_2 \lor x_3\).

On row \(5\) we see that \(x_1\) is \(1\), while \(x_2\) and \(x_3\) are both \(0\). We therefore construct the maxterm \(\neg x_1 \lor x_2 \lor x_3\).

On row \(6\) we see that \(x_1\) and \(x_3\) are both \(1\), while \(x_2\) is \(0\). We therefore construct the maxterm \(\neg x_1 \lor x_2 \lor \neg x_3\).

On row \(6\) we see that \(x_1\), \(x_2\) and \(x_3\) are all \(1\). We therefore construct the maxterm \(\neg x_1 \lor \neg x_2 \neg \lor x_3\).

Finally, we build the conjunction of all maxterms:

\[ f(x_1, x_2, x_3) = (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_2 \lor \neg x_3) \land (\neg x_1 \lor \neg x_2 \neg \lor x_3) \]

Algorithm: CCNF to DNF

We are given the CNF of a Boolean function \(f: \{0,1\}^n \to \{0,1\}\) and want to find its DNF:

  1. Apply the distributive law for conjunction recursively, starting left to right.
  2. It may be possible to further simplify the resulting conjunctions in the DNF.
Example

TODO

Algorithm: CNF to CCNF

We are given a CNF of a Boolean function \(f: \{0,1\}^n \to \{0,1\}\) and want to find a CCNF:

\[f(x_1, \dotsc, x_n) = \prod_{i=1}^c C_i\]
  1. For each clause \(C_i\) and each variable \(x_j\):
  • If \(C_i\) contains \(x_j\) or \(\overline{x}_j\), then do nothing.
  • If \(C_i\) does not contain \(x_j\) or \(\overline{x}_j\), then replace it by the product \((C_i + x_j)(C_i + \overline{x_j})\).
  • Recursively repeat the same process for each of the newly generated clauses, until you only have maxterms.
  1. If you have multiple identical maxterms, then merge them into a single one.
  2. The result from step 2 is a CCNF of \(f\).

Canonical Disjunctive Normal Form#

Theorem: Canonical Disjunctive Normal Form (CDNF)

Every non-contradictory Boolean function \(f: \{0, 1\}^n \to \{0,1\}\) can be expressed as a disjunctive normal form of \(p\) minterms, where \(p\) is the cardinality of \(f\)'s on-set.

Definition: Canonical Disjunctive Normal Form

Such an expression is known as a canonical disjunctive normal form (CDNF) of \(f\).

Proof

TODO

Algorithm: Finding CDNFs

We are given a Boolean operator \(f: \{0,1\}^n \to \{0,1\}\):

\[f(x_1, \dotsc, x_n)\]

  1. Identify the on-set \(F\) of \(f\).

  2. For each \((x_1^{\ast}, \dotsc, x_n^{\ast}) \in F\) construct the minterm \(\mathop{\operatorname{AND}}(x_1', \dotsc, x_n')\), where

  • \(x_k' = x_k\) if \(x_k^{\ast} = 1\);
  • \(x_k' = \neg x_k\) if \(x_k^{\ast} = 0\).
  1. The disjunctive normal form of \(f\) is the disjunction of all the minterms from step 2.
Example

The easiest way is to use the truth table of \(f\). Suppose \(f(x_1, x_2, x_3)\) has the following truth table:

\(x_1\) \(x_2\) \(x_3\) \(f(x_1, x_2, x_3)\)
\(0\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(1\)
\(0\) \(1\) \(0\) \(1\)
\(0\) \(1\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(0\)
\(1\) \(1\) \(0\) \(1\)
\(1\) \(1\) \(1\) \(0\)

The on-set of \(f\) is easily determined by looking at the rows which contain \(1\) in the column for \(f(x_1, x_2, x_3)\). In this example, these rows are \(2\), \(3\), \(4\), and \(7\).

On row \(2\) we see that \(x_1\) and \(x_2\) are both \(0\), while \(x_3\) is \(1\). We therefore construct the minterm \(\neg x_1 \land \neg x_2 \land x_3\).

On row \(3\) we see that \(x_1\) and \(x_3\) are both \(0\), while \(x_2\) is \(1\). We therefore construct the minterm \(\neg x_1 \land x_2 \land \neg x_3\).

On row \(4\) we see that \(x_1\) is \(0\), while \(x_2\) and \(x_3\) are both \(1\). We therefore construct the minterm \(\neg x_1 \land x_2 \land x_3\).

On row \(7\), we see that \(x_1\) and \(x_2\) are both \(1\), while \(x_3\) is \(0\). We therefore construct the minterm \(x_1 \land x_2 \land \neg x_3\).

Finally, we build the disjunction of all minterms:

\[ f(x_1, x_2, x_3) = (\neg x_1 \land \neg x_2 \land x_3) \lor (\neg x_1 \land x_2 \land \neg x_3) \lor (\neg x_1 \land x_2 \land x_3) \lor (x_1 \land x_2 \land \neg x_3) \]

Algorithm: DNF to CNF

We are given a CCNF of a Boolean function \(f: \{0,1\}^n \to \{0,1\}\) and want to find its CNF:

  1. Apply the distributive law for disjunction recursively, starting left to right.
  2. It may be possible to further simplify the resulting disjunctions in the CNF.
Example

TODO

Algorithm: DNF to CDNF

We are given are given a DNF of a Boolean function \(f: \{0,1\}^n \to \{0,1\}\) and want to find a CDNF:

\[f(x_1, \dotsc, x_n) = \sum_{i=1}^p P_i\]
  1. For each product term \(P_i\) and each variable \(x_j\):
  • If \(P_i\) contains \(x_j\) or \(\overline{x}_j\), then do nothing.
  • If \(P_i\) does not contain \(x_j\) or \(\overline{x}_j\), then replace it with \(P_i x_j + P_i \overline{x_j}\).
  • Recursively repeat the same process for the newly generated product terms until you have only minterms.
  1. If you have multiple identical minterms, then merge them into a single one.
  2. The result from step 2 is a CDNF of \(f\).
Example

Consider \(f(A, B, C) = A + \overline{B}C\).

The first is \(A\). We need to perform two expansions on it:

\[ \begin{aligned} A &= A(B + \overline{B}) = AB + A \overline{B} \\ A &= A(C + \overline{C}) = AC + A \overline{C} \end{aligned} \]

We also need to expand the each of the newly generated terms once:

\[ \begin{aligned} AB &= AB(C + \overline{C}) = ABC + AB\overline{C} \\ A\overline{B} &= A\overline{B}(C + \overline{C}) = A\overline{B}C + A\overline{B}\overline{C} \\ AC &= AC(B + \overline{B}) = ACB + AC\overline{B} \\ A\overline{C} &= A\overline{C}(B + \overline{B}) = A\overline{C}B + A\overline{C}\overline{B} \end{aligned} \]

We thus generated the following minterms: \(ABC\), \(AB\overline{C}\), \(A\overline{B}C\), \(A\overline{B}\overline{C}\).

Now, we do the same for the other original product term \(\overline{B}C\). We only need to expand it once:

\[ \overline{B}C = \overline{B}C(A + \overline{A}) = \overline{B}CA + \overline{B}C\overline{A} \]

We thus generated the following minterms: \(\overline{B}CA\) and \(\overline{B}C\overline{A}\).

To obtain a CDNF of \(f\), we sum all generated minterms:

\[ f(A, B, C) = ABC + AB\overline{C} + A\overline{B}C + A\overline{B}\overline{C} + \overline{B}CA + \overline{B}C\overline{A} \]

We see that \(A\overline{B}C\) and \(\overline{B}CA\) are the same, so we just leave \(A\overline{B}C\):

\[ f(A, B, C) = ABC + AB\overline{C} + A\overline{B}C + A\overline{B}\overline{C} + \overline{B}C\overline{A} \]