Lecture 8: Boolean Algebra

Based on Discrete Mathematics and Its Applications (opens in a new tab) by Kenneth H. Rosen, 7th Edition.

Boolean Operations

Example

Find the value of the following expression:

Solution: Using the definitions of the operations, we get:

Boolean Expressions

A boolean expression is a combination of boolean variables and boolean operations. For example, $x \cdot y + \overline{z}$ is a boolean expression.

Boolean Functions

Let $B = \{0, 1\}$ be the set of boolean values. Then, a boolean function $f: B^n \rightarrow B$ is a function that takes in $n$ boolean variables and returns a boolean value. $B$ is also denoted as $B^n = \{ (x_1, x_2, \dots, x_n) \mid x_i \in B$ for $1 \leq i \leq n \}$. A function $f: B^n \rightarrow B$ is called a boolean function of degree $n$.

Example

Find the values of the following boolean functions:

Solution: We can find the values of the function by plugging in all possible values of $x, y, z$ into a table represented below:

n-cube representation

We can represent a boolean function of degree $n$ as an $n$-cube. For example, the boolean function $f(x, y, z) = xy + \overline{z}$ can be represented as a cube with $n^3$ vertices

The vertices that correspond to $f(x, y, z) = 1$ are

Number of Boolean Functions

Suppose that we have $n$ different boolean variables. Each of these variables can take on two values, $0$ or $1$. Therefore, there are $2^n$ possible combinations of values for the $n$ variables. For each of these combinations, we can assign a value of $0$ or $1$. Therefore, there are $2^{2^n}$ possible boolean functions of degree $n$.

Table below shows the number of boolean functions for different values of $n$:

Identities of Boolean Algebra

Duality

The dual of a boolean function $f$ is the function $f^*$ obtained by interchanging the operations $\cdot$ and $+$ and the constants $0$ and $1$ in $f$. For example, the dual of $f(x, y, z) = xy + \overline{z}$ is $f^*(x, y, z) = x + \overline{y}z$.

Exercises

1. Find the sum-of-products expansion of the boolean function $F(x_1, x_2, x_3, x_4, x_5)$ that has the value $1$ if and only if three or more of the variables $x_1, x_2, x_3, x_4, x_5$ have the value $1$.

Representing Boolean Functions

Sum-of-products Expansions

Example

Find boolean expressions that represent the function $F(x, y, z)$ and $G(x, y, z)$ defined by the following tables:

Solution: We can find the boolean expressions by looking at the rows where the function is $1$ and then taking the product of the variables in the row. For example, for $F(x, y, z)$, we have:

Similarly, for $G(x, y, z)$, we have:

Actually, the $F(x, y, z)$ is a function that determine whether the number of $1$ in the input is even or odd. If the number of $1$ is even, then the function is $1$. Otherwise, the function is $0$. The $G(x, y, z)$ is a function that determine whether the number of $1$ in the input is odd. If the number of $1$ is odd, then the function is $1$. Otherwise, the function is $0$.

Minterm

Example

Find the minterm of the boolean function that takes 5 variables that return true if and only if the first, second, and fifth term are true.

Solution: The minterm is $\overline{x_1} \cdot \overline{x_2} \cdot x_3 \cdot x_4 \cdot \overline{x_5}$.

Logic Gates