Boolean Algebra and Boolean Functions

This chapter studies Boolean expressions as functions: how to represent them, prove identities, and simplify implementations. The two-element algebra connects propositional truth tables with digital logic. Basic propositions and quantifiers are introduced in Mathematical Foundations; formal derivations and inference algorithms have their own chapters below.

Our main example is the two-element Boolean algebra, rather than a general classification of abstract Boolean algebras. Its core operations are conjunction, disjunction, and complement; XOR is a derived operation. Truth-table review here supports algebraic equivalence and function representation, rather than repeating the foundations' proof-method lessons.

Boolean Expression and Truth Table

We call Boolean Algebra "Algebra" of course, because it possesses property of Algebra. We will start with basic algebra operation and thus, proceed to get the rule of Boolean operation, which we call the "Truth Table".

Property of Algebra Operation

For normal algebra operation of numbers, we have the following general law by representing the number in $x$, $y$, and $z$.

Law	Addition expression	Multiplication expression
Identity	$x + 0 = x$	$x \cdot 1 = x$
Property of zero		$x \cdot 0 = 0$
Inverse	$x + (-x) = 0$	$x \cdot x^{-1} = 1$, for $x \neq 0$
Commutative	$x + y = y + x$	$x \cdot y = y \cdot x$
Associative	$(x + y) + z = x + (y + z)$	$(x \cdot y) \cdot z = x \cdot (y \cdot z)$
Distributive		$x \cdot (y + z) = x \cdot y + x \cdot z$

Common Algebraic Laws

In this case, we call $x$, $y$, and $z$ variables as in programming. For all possible values of these variables, these laws hold. These laws justify transformations in the chosen algebraic structure; they do not imply that every true mathematical equality follows from this short list alone. We take $-1 \times -1$ as an example. One may say without a second thought that the answer is 1. But why? Can we prove it? Now we try to prove it using the common algebraic laws.

ExampleProve that (-1) (-1) = 1

Prove that $(-1)\times (-1) = 1$

Proof

$$\begin{aligned} (-1)\times(-1) &= ((-1)\times(-1))+0 \\ &= ((-1)\times(-1))+((-1)+1) \\ &= (((-1)\times(-1)+(-1))+1) \\ &= (((-1)\times(-1)+((-1)\times 1))+1) \\ &= ((-1)\times((-1)+1))+1 \\ &= ((-1)\times 0)+1 \\ &= 0+1 \\ &= 1+0 \\ &= 1. \end{aligned}$$

Remark: Some people may not understand why we have to write $0+1$ into $1+0$. This is because Addition Identity is only defined in the table as $x+0=x$, so we need to apply Commutative law of addition to fit it into the known conclusion.

After seeing this, you may think, do we really have to know this to make sure that $-1\times-1=1$? Of course not, but keep in mind that Every mathematical conclusion cannot be simply referred as rules such as "a negative times negative give you a positive number", but by meticulous, reasonable, and replicable proof.

Boolean Expression and Truth Table

Hold on a second, isn't this chapter on Boolean Algebra? Why we still need to go over these old knowledge from primary school? Well, this is because we will prove Boolean expression in the same way. Before that, we introduce Boolean value and operations.

DefinitionBoolean Values

In mathematics and computer science, a Boolean value is defined as an element of the Boolean domain $B$, which can be mathematically represented as:

$$\mathbb{B} = \{0, 1\}$$

where:

• $0$ typically represents false

• $1$ typically represents true

Some may be confused by true and false here. Just recall what we have done to propositions in the first chapter in this book. When a statement holds for given condition, we take it as correct, while incorrect when it does not hold. A Boolean expression evaluates to a Boolean value after its variables receive values. Before an assignment is supplied, it generally represents a function, not a constant.

DefinitionBoolean Algebra

Boolean algebra involves operations such as AND, OR, NOT, XOR, which operate on these Boolean values. These operations are defined as follows:

• AND ($\land$): An operation on two Boolean values that returns true if both operands are true, otherwise returns false.

• OR ($\lor$): An operation on two Boolean values that returns true if at least one of the operands is true, otherwise returns false.

• NOT ($\lnot$): A unary operation that returns true if the operand is false and vice versa.

• XOR ($\oplus$): An operation on two Boolean values that returns true if the operands are different, otherwise returns false.

Remark: There are more Boolean operators to be discussed later.

In computer science, Boolean values are fundamental in conditional statements and loops, where they determine the flow of control in algorithms and programs. They are also essential in the design of electronic circuits and digital computing. The following table shows the truth table of these basic Boolean operations. the first column shows the combination of inputs for the specific operator, and the second column shows the result of operation.

A	$\neg \textbf{A}$
F	T
T	F

Common Boolean Operators Truth Tables

A	B	$\textbf{A} \land \textbf{B}$
F	F	F
F	T	F
T	F	F
T	T	T

Common Boolean Operators Truth Tables

A	B	$\textbf{A} \lor \textbf{B}$
F	F	F
F	T	T
T	F	T
T	T	T

Common Boolean Operators Truth Tables

A	B	$\textbf{A} \oplus \textbf{B}$
F	F	F
F	T	T
T	F	T
T	T	F

Common Boolean Operators Truth Tables

It's noticeable that different Boolean operators may differ in the number of input. $\lnot$ operator takes only one Boolean variable (input) to get an output by negating the input, however the rest take two inputs and produce one output.

We defined the Boolean space as $B=\{0,1\}$. This choice reflects the two truth values used by Boolean algebra. Among the four familiar arithmetic operations, Boolean expressions are generated from a small basis such as $\lnot$, $\land$, and $\lor$; other operators can be expressed in terms of these. For example,

$$A\oplus B=(A\land\lnot B)\lor(\lnot A\land B).$$

The addition and multiplication tables for $0$ and $1$ illustrate the analogy with ordinary algebra.

$A$	$B$	$A \times B$
0	0	0
0	1	0
1	0	0
1	1	1

Addition and Multiplication Rule of 0 and 1

$A$	$B$	$A + B$
0	0	0
0	1	1
1	0	1
1	1	1

Addition and Multiplication Rule of 0 and 1

Now you may have realized that this is exactly the truth table for $\land$ and $\lor$, shown in Table 1.5.

Boolean Identities

Now recall that $A \oplus B= (A \land \lnot B) \lor(\lnot A \land B)$. In this expression, we cannot get a direct answer from the RHS by using the truth table of $\lor$. So, we need to try harder to get the truth table for the expression as shown in the table below.

$A$	$B$	$\neg B$	$A \land \neg B$	$\neg A$	$\neg A \land B$	$(A \land \neg B) \lor (\neg A \land B)$
F	F	T	F	T	F	F
F	T	F	F	T	T	T
T	F	T	T	F	F	T
T	T	F	F	F	F	F

Truth table for $(A \land \neg B) \lor (\neg A \land B)$

With this method, we can find truth table for more complex expressions, and some of them are categorized as Basic Boolean Identities. The LHS and RHS are could be proven qaual by listing truth table respectively.

Identity	AND form	OR form
Idempotent law	$x \cdot x = x$	$x + x = x$
Identity law	$x \cdot 1 = x$	$x + 0 = x$
Domination law	$x \cdot 0 = 0$	$x + 1 = 1$
Complement law	$x \cdot \lnot x = 0$	$x + \lnot x = 1$
Double negation law	$\lnot(\lnot x) = x$	$\lnot(\lnot x) = x$
Commutative law	$x \cdot y = y \cdot x$	$x + y = y + x$
Associative law	$x \cdot (y \cdot z) = (x \cdot y) \cdot z$	$x + (y + z) = (x + y) + z$
Distributive law	$x \cdot (y + z) = (x \cdot y) + (x \cdot z)$	$x + (y \cdot z) = (x + y) \cdot (x + z)$
De Morgan's law	$\lnot(x + y) = \lnot x \cdot \lnot y$	$\lnot(x \cdot y) = \lnot x + \lnot y$
Absorption law	$x \cdot (x + y) = x$	$x + (x \cdot y) = x$

Basic Boolean Identities

RemarkReading Boolean Identities

If you are confused by the algebra form of Boolean identities, just take $x$, $y$, $z$ as $A$, $B$, and $C$; take 0/1 as F/T; take + as $\lor$, and $\times$ as $\land$.

It is quite important to be familiar with these rules, as they are just as essential as the normal algebra laws we've learned before, since we may simplify complex Boolean expressions using these rules. Also, the proof of some of these identities using truth table will be added to the problem set for this section. If you remain any doubt or confusion about any laws given, just try to get the truth table for the LHS and RHS of the identity, simple as that.

This is actually not yet a complete table of Boolean Identities, two laws are still missing from the table, because they are relevant to secondary operator, one of which is already mentioned($\oplus$).

With these basic Boolean laws, we can derive more interesting and useful theorems. A commonly used theorem when simplifying Boolean expressions is the consensus theorem, also called the redundancy theorem.

TheoremThe Consensus Theorem

The consensus theorem helps simplify Boolean expressions by eliminating a redundant term. Like the other identities, it has both an OR form and an AND form. For Boolean variables $x$, $y$, and $z$,

$$xy\lor\bar{x}z\lor yz=xy\lor\bar{x}z,$$

which is equivalent to

$$(x\lor y)(\bar{x}\lor z)(y\lor z)=(x\lor y)(\bar{x}\lor z).$$

Proof

The OR form follows from the following calculation:

$$\begin{aligned} xy\lor\bar{x}z\lor yz &=xy\lor\bar{x}z\lor(x\lor\bar{x})yz \\ &=xy\lor\bar{x}z\lor xyz\lor\bar{x}yz \\ &=(xy\lor xyz)\lor(\bar{x}z\lor\bar{x}yz) \\ &=xy(1\lor z)\lor\bar{x}z(1\lor y) \\ &=xy\lor\bar{x}z. \end{aligned}$$

In additive notation, the same identity is

$$\begin{aligned} xy + \overline{x}z + yz &= xy + \overline{x}z + (x + \overline{x})yz \\ &= xy + \overline{x}z + xyz + \overline{x}yz \\ &= (xy + xyz) + (\overline{x}z + \overline{x}yz) \\ &= xy(1 + z) + \overline{x}z(1 + y) \\ &= xy + \overline{x}z. \end{aligned}$$

Secondary Boolean Operators

DefinitionDerived Boolean Operators

Secondary operators are derived from basic operators:

• Material conditional: $x \rightarrow y = \lnot x \lor y$

• Material biconditional: $x \leftrightarrow y = (x \land y) \lor (\lnot x \land \lnot y)$

• Exclusive OR (XOR):

$$x \oplus y = \lnot(x \leftrightarrow y) = (x \lor y) \land (\lnot x \lor \lnot y) = (x \land \lnot y) \lor (\lnot x \land y)$$

Their truth tables for the secondary operation are below:

$x$	$y$	$x \rightarrow y$	$x \leftrightarrow y$	$x \oplus y$
0	0	1	1	0
1	0	0	0	1
0	1	1	0	1
1	1	1	1	0

Truth values of material conditional, biconditional, and XOR for all possible inputs.

The $\rightarrow$ operation holds that $x \rightarrow x = 1$. This expression means that when $x=y$, then $x\rightarrow y$ must be true. The complete form of secondary operators and the implication identity will be the last Boolean identity to be covered in this chapter.

1. Material Conditional ($\rightarrow$): The material conditional $x \rightarrow y$ is read as "if $x$ then $y$" or "$x$ implies $y$". It represents the logical implication. The truth value of $x \rightarrow y$ is false only when $x$ is true and $y$ is false; in all other cases, it is true. This is a bit counter-intuitive when $x$ is false because the implication will be true regardless of the value of $y$. It can be expressed using basic operations as $\lnot x \lor y$.

2. Material Biconditional ($\leftrightarrow$): The material biconditional $x \leftrightarrow y$, also known as logical equivalence, is the operation that is true when $x$ and $y$ have the same truth values, and false otherwise. It's often read as " $x$ if and only if $y$". It can be formulated as $(x \land y) \lor (\lnot x \land \lnot y)$, meaning both $x$ and $y$ are true, or both are false.

3. Exclusive OR (XOR): The exclusive OR $x \oplus y$ is true when $x$ and $y$ have different truth values, that is, one is true and the other is false. It differs from the regular OR operation in that $x \oplus y$ is false when both $x$ and $y$ are true. It can be represented as $(x \land \lnot y) \lor (\lnot x \land y)$.

With these basic identities and operators, we can prove more interesting Boolean theorems. Below are more theorems to be proved as example. Maybe you are ready to draw a truth table to prove them. However, with these basic Boolean Laws, we actually don't have to do that, but prove it by using Algebra techniques.

ExampleProve the following identities using the table given earlier

Prove the following identities using the table given earlier.

Expression	Name
$(x \rightarrow \text{False}) = (\lnot x)$	$\lnot$ as $\rightarrow$
$(x \rightarrow y) = (\lnot y \rightarrow \lnot x)$	Contrapositive
$((x \rightarrow y) \land (x \rightarrow z)) = (x \rightarrow (y \land z))$	Implication
$((x \rightarrow y) \land (\lnot x \rightarrow y)) = y$	Absurdity
$(x \rightarrow (\lnot x)) = (\lnot x)$	Contradiction

Proof

To prove $\lnot$ as $\rightarrow$, we just need to use the definition of $\rightarrow$.

$$x\rightarrow\text{ False}= \lnot x \lor False = \lnot x + 0 = \lnot x \ \text{(OR Identity Law)}$$

The contrapositive identity states that $(x \rightarrow y)$ is logically equivalent to $(\lnot y \rightarrow \lnot x)$.

$$$$$$\begin{aligned} x \rightarrow y &\equiv \lnot x \lor y \\ &\equiv y \lor \lnot x\ \text{(Commutative Law)}\\ &\equiv \lnot y \rightarrow \lnot x \end{aligned}$$$$$$

Remark: This proof shows why proof by contrapositive (mentioned in chapter1) is correct.

The implication identity can be proved by showing that $(x \rightarrow y) \land (x \rightarrow z)$ is equivalent to $x \rightarrow (y \land z)$.

$$$$$$\begin{aligned} (x \rightarrow y) \land (x \rightarrow z) &\equiv (\lnot x \lor y) \land (\lnot x \lor z) \\ &\equiv \lnot x \lor (y \land z) \\ &\equiv x \rightarrow (y \land z) \end{aligned}$$$$$$

The absurdity identity states that $(x \rightarrow y) \land (\lnot x \rightarrow y)$ is equivalent to $y$.

$$$$$$\begin{aligned} (x \rightarrow y) \land (\lnot x \rightarrow y) &\equiv (\lnot x \lor y) \land (x \lor y) \\ &\equiv y \lor (x \land \lnot x) \\ &\equiv y \lor \text{False} \\ &\equiv y \end{aligned}$$$$$$

The contradiction identity states that $x \rightarrow (\lnot x)$ is equivalent to $\lnot x$.

$$$$$$\begin{aligned} x \rightarrow (\lnot x) &\equiv \lnot x \lor (\lnot x) \\ &\equiv \lnot x \end{aligned}$$$$$$

RemarkBoolean Expression Notation

Some may feel confused by the notation of Boolean expression we use in this chapter. Sometimes we use logic notation, while sometimes use algebra operation. Both are ok, it's really up to your preference.

When you look through the whole process, you'll find that we are actually doing the same thing as simplifying Boolean expressions, where all the laws could be used so that we don't need to draw truth table again and again.

Exercises

ExerciseUse Table 1

Use Table 1.1 and $1+1=2$ to show that $(x+x)=(2\times x)$.

Proof

$$$$$$\begin{aligned} ( 2\times x) & =( 1+1) \times x\ ( by\ 1+1=2)\\ & =\ 1\times x+1\times x\ ( Distributive\ Law)\\ & =x+x\ ( Multiplication\ Identity) \end{aligned}$$$$$$

ExerciseShow that ((-1) x)+x=0 using the table

Show that $((-1)\times x)+x=0$ using the table.

Proof

$$$$$$\begin{aligned} (( -1) \times x) +x & =x( -1+1) \ ( Distributive\ Law)\\ & =\ x\times 0\ ( Addition\ Inverse)\\ & =0\ ( Multiplication\ Property\ of\ Zero) \end{aligned}$$$$$$

ExerciseShow that (x+(((-1) (x+y))+z)) + y =z, you may use the conclusion of...

Show that $(x+(((-1)\times (x+y))+z)) + y =z$, you may use the conclusion of previous exercise.

Proof

To make it clear, we use square and curly bracket for different layers of parenthesis.

$$$$$$\begin{aligned} \ & \{x+[((-1) \times ( x+y)) +z]\} +y\\ & =\{x+[(( -1) \times x) +(( -1) \times y)] +z\} +y\ ( Distributive\ Law\ )\\ & =\{x+(( -1) \times x) +[(( -1) \times y) +z]\} +y\ ( Associative\ Law\ of\ Addition)\\ & =\{(( -1) \times x) +x+\ [(( -1) \times y) +z]\} +y( Commutative\ Law\ of\ Addition)\\ & =0+\{[(( -1) \times y) +z] +y\}\ ( Previous\ Conclusion)\\ & =\{[(( -1) \times y) +z] +y\} +0\ ( Commutative\ Law\ of\ Addition)\\ & =\{[(( -1) \times y) +z] +y\} \ ( Addition\ Identity)\\ & =(( -1) \times y) +( z+y) \ ( Associative\ Law\ of\ Addition)\\ & =( z+y) +(( -1) \times y) \ ( Commutative\ Law\ of\ Addition)\\ & =z+[ y+(( -1) \times y)] \ ( Associative\ Law\ of\ Addition)\\ & =z+[(( -1) \times y) +y] \ ( Commutative\ Law\ of\ Addition)\\ & =z+0\ ( Previous\ Conclusion)\\ & =z\ ( Addition\ Identity) \end{aligned}$$$$$$

ExerciseUse truth table to show that De Morgan's Law is correct

Use truth table to show that De Morgan's Law is correct.

Proof

De Morgan's First Law: $\lnot (A \land B) = \lnot A \lor \lnot B$

$A$	$B$	$A \land B$	$\lnot (A \land B)$	$\lnot A \lor \lnot B$
0	0	0	1	1
0	1	0	1	1
1	0	0	1	1
1	1	1	0	0

De Morgan's Second Law: $\lnot (A \lor B) = \lnot A \land \lnot B$

$A$	$B$	$A \lor B$	$\lnot (A \lor B)$	$\lnot A \land \lnot B$
0	0	0	1	1
0	1	1	0	0
1	0	1	0	0
1	1	1	0	0

ExerciseUse truth table to show that Absorption Law is correct

Use truth table to show that Absorption Law is correct.

Proof

$x$	$y$	$x \lor y$	$x \land (x \lor y)$
T	T	T	T
T	F	T	T
F	T	F	F
F	F	F	F

$x$	$y$	$x \land y$	$x \lor (x \land y)$
T	T	T	T
T	F	F	T
F	T	F	F
F	F	F	F

ExerciseShow the truth table of x or (( y) and ( z))

Show the truth table of $\displaystyle x\lor (( \lnot y) \land ( \lnot z))$.

Hint: For Boolean expression of 3 variable, there will be more combinations.

Solution:

$x$	$y$	$z$	$\lnot y$	$\lnot z$	$(\lnot y) \land (\lnot z)$	$x \lor ((\lnot y) \land (\lnot z))$
0	0	0	1	1	1	1
0	0	1	1	0	0	0
0	1	0	0	1	0	0
0	1	1	0	0	0	0
1	0	0	1	1	0	1
1	0	1	1	0	0	1
1	1	0	0	1	0	1
1	1	1	0	0	0	1

Truth table for the expression $x \lor ((\lnot y) \land (\lnot z))$

ExerciseGiven the expressions & (x y) and ( x y) & (( x) or y) and (x or ( y))

Given the expressions:

$$$$$$\begin{aligned} 1. & \quad (x \rightarrow y) \land (\lnot x \rightarrow \lnot y) \\ 2. & \quad ((\lnot x) \lor y) \land (x \lor (\lnot y)) \\ 3. & \quad \lnot((x \land (\lnot y)) \lor ((\lnot x) \land y)) \\ 4. & \quad \lnot((x \lor y) \land (\lnot x \lor \lnot y)) \\ \end{aligned}$$$$$$

Show that they are equivalent and find the common (simplified) form of the four expression

Proof

$$$$$$\begin{aligned} (x \rightarrow y) \land (\neg x \rightarrow \neg y) & \equiv (\neg x \lor y) \land (x \lor \neg y) && \text{(Implication equivalence)} \\ & \equiv (x \lor \neg y) \land (\neg x \lor y) && \text{(Commutativity of OR)} \\ & \equiv (x \lor \neg y) \land (y \lor \neg x) && \text{(Commutativity of AND)} \end{aligned}$$$$$$$$$$$$\begin{aligned} ((\neg x) \lor y) \land (x \lor (\neg y)) & \equiv (y \lor \neg x) \land (x \lor \neg y) && \text{(Commutativity of OR)} \\ & \equiv (x \lor \neg y) \land (y \lor \neg x) && \text{(Commutativity of AND)} \end{aligned}$$$$$$$$$$$$\begin{aligned} \neg((x \land (\neg y)) \lor ((\neg x) \land y)) & \equiv \neg(x \land (\neg y)) \land \neg((\neg x) \land y) && \text{(De Morgan's laws)} \\ & \equiv (\neg x \lor y) \land (x \lor \neg y) && \text{(De Morgan's laws)} \\ & \equiv (x \lor \neg y) \land (y \lor \neg x) && \text{(Commutativity of OR and AND)} \end{aligned}$$$$$$$$$$$$\begin{aligned} \neg((x \lor y) \land (\neg x \lor \neg y)) & \equiv \neg(x \lor y) \lor \neg(\neg x \lor \neg y) && \text{(De Morgan's laws)} \\ & \equiv (\neg x \land \neg y) \lor (x \land y) && \text{(De Morgan's laws)} \\ & \equiv (x \land y) \lor (\neg x \land \neg y) && \text{(Commutativity of OR)} \\ & \equiv (x \lor \neg y) \land (y \lor \neg x) && \text{(Distribution)} \end{aligned}$$$$$$

These expressions could be simplified to $(\lnot y \lor x)\land(\lnot x\lor y)$, or $(y\rightarrow x)\land(x\rightarrow y)$, which can also be understood as $x$ and $y$ cannot be true of false in the same time.

ExerciseShow that the two forms of the consensus theorem are equivalent

Show that the two forms of the consensus theorem are equivalent.

$$xy\lor\bar{x}z\lor yz=xy\lor\bar{x}z$$

and

$$(x\lor y)(\bar{x}\lor z)(y\lor z)=(x\lor y)(\bar{x}\lor z)$$

are equivalent.

Solution: We can simplify the product form to the standard form easily.

$$$$ $$\begin{aligned} (x \lor y)(\overline{x} \lor z)(y \lor z) &= x\overline{x} \lor xz \lor y\overline{x} \lor yz \lor xy \lor xz \lor y^2 \lor yz \\ &= 0 \lor xz \lor y\overline{x} \lor yz \lor xy \lor xz \lor y \lor yz \\ &= xz \lor y\overline{x} \lor yz \lor xy \\ &= xy \lor xz \lor y\overline{x} \end{aligned}$$ $$$$

Boolean Function

This section will bring you some further ideas of Boolean operation. Just like we can take a normal algebra expression, such as $2x+3$, as a function $f(x)=2x+3$; we can define Boolean Function with Boolean operation.

DefinitionBoolean Functions

A Boolean function is a function that returns a Boolean value (true or false) for each possible combination of Boolean inputs. $f: B^n \rightarrow B$ is a function from the set of $n$-tuples of Boolean values to the set of Boolean values, where $B = \{0, 1\}$.

For example, we can write the basic operations we just went over in Boolean Functions:

1. Algebraic notation:

   • AND: $f(x, y) = x \cdot y$ or $f(x, y) = xy$

   • OR: $f(x, y) = x + y$

   • NOT: $f(x) = x'$ or $f(x) = \overline{x}$

2. Logical notation:

   • AND: $f(x, y) = x \wedge y$

   • OR: $f(x, y) = x \vee y$

   • NOT: $f(x) = \neg x$

We have actually learned about this earlier in the chapter. Think about what we have done using truth tables. Just like what you have done at the beginning of learning functions, you were making tables to show all results of each input with their output. For Preliminary functions, we always have $f: R\rightarrow R$, which makes the mapping hard to make table, because there are infinite many real numbers. But things is much easier for Boolean function, because we have known in the definition that each function generate only one single output, and the most important part is that we always have limited inputs. Since $|B|=2$ for the Boolean Domain, so each input gives us 2 choices only, and therefore when we have $n$ inputs, we have $2^n$ cases only. $2^n$ seems huge, but in most cases we have less than 5 inputs in a Boolean function, so the size of the table is still manageable.

Representation of Boolean Function

In most cases, we construct a Boolean Function from a given truth table. All Boolean functions could be represented in both Disjunctive Normal Form (also known as sum of product;SOP form) and Conjunctive Normal Form (also known as Product of Sum;POS form).

DefinitionSum-of-Products Form

The Sum of Products (SOP) form, also known as the Disjunctive Normal Form (DNF), is a way to represent a Boolean function as a sum (logical OR) of product (logical AND) terms. Each product term consists of literals (variables or their complements) that correspond to the function's minterms, which are the input combinations that result in a function value of 1. The general form of an SOP expression is:

$$f(x_1, x_2, \ldots, x_n) = \sum_{i=1}^{m} \prod_{j=1}^{n} x_j^{(i)},$$

where $m$ is the number of minterms, $n$ is the number of variables, and $x_j^{(i)}$ is either $x_j$ or $x_j'$ (complement of $x_j$) depending on the value of $x_j$ in the $i$-th minterm.

DefinitionProduct-of-Sums Form

The Product of Sums (POS) form, also known as the Conjunctive Normal Form (CNF), is a way to represent a Boolean function as a product (logical AND) of sum (logical OR) terms. Each sum term consists of literals (variables or their complements) that correspond to the function's maxterms, which are the input combinations that result in a function value of 0. The general form of a POS expression is:

$$f(x_1, x_2, \ldots, x_n) = \prod_{i=1}^{M} \sum_{j=1}^{n} x_j^{(i)},$$

where $M$ is the number of maxterms, $n$ is the number of variables, and $x_j^{(i)}$ is either $x_j$ or $x_j'$ (complement of $x_j$) depending on the value of $x_j$ in the $i$-th maxterm.

RemarkMinterms and Maxterms

Minterms and maxterms are fundamental building blocks for representing Boolean functions, corresponding to the input combinations that result in function values of 1 and 0, respectively.

But why we are so obsessed with whether the output for one single row is 1(T) or 0 (F)? This is because, when we are constructing a Boolean function, we are trying to make the mapping from $B^n$ to $B$, while $B = {0,1}$. Hence, we could conclude that the result of boolean function is actually binary, meaning only two cases for the output(we will talk about it later in the chapter). So, we only need to figure out either of all the cases where the output is 0, or all the cases where the output is 1. This actually explains what are stated in the Canonical Form Theorem.

TheoremCanonical Forms of Boolean Functions

Any Boolean function can be expressed in either of two canonical forms:

1. Sum of Products (SOP) form, also known as the Disjunctive Normal Form (DNF): Any Boolean function can be represented as a disjunction (OR) of one or more minterms, where a minterm is a product (AND) of literals corresponding to the rows in the truth table where the function value is 1.

2. Product of Sums (POS) form, also known as the Conjunctive Normal Form (CNF): Any Boolean function can be represented as a conjunction (AND) of one or more maxterms, where a maxterm is a sum (OR) of literals corresponding to the rows in the truth table where the function value is 0.

Proof

To prove the Canonical Form Theorem, we will consider an arbitrary Boolean function $f(x_1, x_2, \ldots, x_n)$ and show that it can be expressed in both SOP and POS forms.

Proof of SOP form (DNF):

1. For each row in the truth table where the function value is 1, create a minterm by taking the conjunction (AND) of the literals corresponding to the input values in that row. If the input variable is 1, use the original variable; if the input variable is 0, use the complement of the variable.

2. Take the disjunction (OR) of all the minterms obtained in step 1. This resulting expression is the SOP form of the Boolean function.

Since every row where the function value is 1 is represented by a minterm, and the disjunction of these minterms covers all the cases where the function is 1, the resulting SOP form is equivalent to the original Boolean function.

Proof of POS form (CNF):

1. For each row in the truth table where the function value is 0, create a maxterm by taking the disjunction (OR) of the literals corresponding to the input values in that row. If the input variable is 0, use the original variable; if the input variable is 1, use the complement of the variable.

2. Take the conjunction (AND) of all the maxterms obtained in step 1. This resulting expression is the POS form of the Boolean function.

Since every row where the function value is 0 is represented by a maxterm, and the conjunction of these maxterms covers all the cases where the function is 0, the resulting POS form is equivalent to the original Boolean function.

Therefore, any Boolean function can be expressed in either SOP or POS form, proving the Canonical Form Theorem.

ExampleConsidering x y f(x, y) 0 0 1 0 1 0 1 0 0 1 1 1

Considering

$x$	$y$	$f(x, y)$
0	0	1
0	1	0
1	0	0
1	1	1

.If you are familiar with the Boolean operations, you may have realized this is actually a XNOR operation, which negates XOR. We will try to get the Algebra expression of this function in both POS and SOP.

SolutionFor the SOP form Function value is 1 for the corresponding input...

For the SOP form:

• Function value is 1 for the corresponding input combinations.

• Smallest terms: $m_0 = x'y'$, $m_3 = xy$.

• SOP form of the Boolean function: $f(x, y) = m_0 + m_3 = x'y' + xy$.

For the POS form:

• Function value is 0 for the corresponding input combinations.

• Largest terms: $M_1 = x + y'$, $M_2 = x' + y$.

• POS form of the Boolean function: $f(x, y) = M_1 \cdot M_2 = (x + y')(x' + y)$.

These two forms can be converted to each other based on the truth table of a Boolean function.

This method also works for Boolean functions with more variables, and the only difference is that it may take a little more time. You may check more relevant problems in the exercises.

Properties of Boolean Function

In this part of the chapter, we will look into further details of Boolean Expression, specifically, Boolean Function. As an intro, we start with completeness and duality of Boolean Function. After this, we will introduce the Fundamental Theorem of Boolean Algebra, also known as Boole's expansion theorem (or Shannon expansion), which in the foundation of logic circuit design and implementation.

TheoremFunctional Completeness

A set of Boolean operators is said to be functionally complete if every Boolean function can be expressed using only those operators. The following sets are known to be functionally complete:

1. The set {AND, OR, NOT}, also known as the standard or canonical basis.

2. The set {NAND}, known as the NAND-only implementation.

3. The set {NOR}, known as the NOR-only implementation.

The completeness property is important in digital logic design, as it allows designers to create any desired Boolean function using a minimal set of logic gates.

ProofWhy AND, OR, and NOT suffice

For each input row where $f=1$, form the conjunction that uses $x_i$ when that row has bit one and $\neg x_i$ when it has bit zero. This conjunction is true on exactly that row. Their disjunction therefore agrees with $f$ on every row. If no row is true, use the constant zero, or $x\land\neg x$ when an input is available. Thus every finite Boolean function has a representation in this basis. The constructions below then implement this basis using NAND alone or NOR alone; for zero-input functions constants must be available explicitly.

RemarkLogic Gate Terminology

If you are getting confused by the word "Logic Gate", just take it as another way we call Boolean or Logic Operators. Logic gates are what electric engineers use to construct Boolean circuits, which is not discussed in details in this book, since we only discuss the mathematical aspect of this practice. You may refer to this link if you want to get more details.

To further illustrate, we could say that all Boolean Functions, or Boolean expressions can be expressed by either combinations of {AND, OR, NOT}, or NAND gates(s), or NOR gate(s). The first point is already quite clear, we have shown that all secondary operators can be written equivalently in basic operators, {AND, OR, NOT}. While NAND and NOR are general logic gates that could construct any logic gates. Below is a simplified proof.

Proof

We start the proof with the fact that all Boolean operations can be written by $\lnot, \land, \lor$ operators. To show that all Boolean operations could be implemented by NAND and NOR gate, we only need to show that {AND, OR, NOT} can be expressed by both NAND and NOR operator.

1. Using NAND gates:

• NOT gate: A NAND gate with its inputs connected together acts as a NOT gate.

• AND gate: A NAND gate with its output inverted by a NOT gate (another NAND gate) acts as an AND gate.

• OR gate: An OR gate can be constructed using NAND gates and De Morgan's Law: $x + y = (x' \cdot y')'$.

2. Using NOR gates:

• NOT gate: A NOR gate with its inputs connected together acts as a NOT gate.

• OR gate: A NOR gate with its output inverted by a NOT gate (another NOR gate) acts as an OR gate.

• AND gate: An AND gate can be constructed using NOR gates and De Morgan's Law: $x \cdot y = (x' + y')'$.

Now, we have shown that all the three basic logic gates could be expressed by only NAND and NOR gate(s), which completes the proof.

RemarkApplications of Logic Gates

You can get more details of the logic gates here. This fact is more used in engineering practice but not in mathematics. So you just need to know the basic idea (in this book).

TheoremThe Duality Principle

For an expression built from AND, OR, NOT, and constants, form its dual by swapping AND with OR and zero with one, while leaving variables and NOT operations unchanged. The resulting function satisfies

$$f^D(x_1,\ldots,x_n)=\neg f(\neg x_1,\ldots,\neg x_n).$$

Consequently the dual is independent of the chosen expression, $(f^D)^D=f$, and every valid identity remains valid after taking duals on both sides.

Proof

Use structural induction on the expression. For a variable, the right side is $\neg\neg x=x$, so $x^D=x$, not $\neg x$. Constants zero and one are interchanged. Assume the formula holds for $g,h$. De Morgan's laws give

$$\neg(g(\neg\mathbf x)\land h(\neg\mathbf x)) =g^D(\mathbf x)\lor h^D(\mathbf x),$$

and the analogous formula with AND/OR exchanged. For a NOT node, $\neg(\neg g(\neg\mathbf x))=g(\neg\mathbf x)=\neg g^D(\mathbf x)$, so the induction also covers negation. This exhausts the constructors. The formula depends only on the function values, hence is representation-independent. Applying it twice cancels both input and output negations, proving double duality. Equal functions remain equal after the same input substitution and output negation, proving the identity principle.

For example, $(x\lor\neg y)^D=x\land\neg y$ and $((a\lor b)\land\neg c)^D=(a\land b)\lor\neg c$. NAND and NOR are dual. The dual of implication $\neg x\lor y$ is $\neg x\land y$, not converse implication. Duality changes connective structure; it does not separately complement every literal.

The next result decomposes a function by the value of one variable.

TheoremBoole's Expansion Theorem

Boole's expansion theorem, often referred to as the Shannon expansion or decomposition, is the identity: $F=x\cdot\dot{F}_x+x^{\prime}\cdot F_{x^{\prime}}$,where $F$ is any Boolean function, $x$ is a variable, $x^{\prime}$ is the complement of $x$, and $F_x$ and $F_{x^{\prime}}$ are $F$ with the argument $x$ set equal to 1 and to 0 respectively. The terms $F_x$ and $F_{x^{\prime}}$ are sometimes called the positive and negative Shannon cofactors, respectively, of $F$ with respect to $x$. These are functions, computed by restrict operator, restrict$(F,x,0)$ and restrict$(F,x,1)$. The former represents the function $F$ where the variable $x$ is set to 0, and the latter represents the restriction of the function $F$ where the variable $x$ is set to 1.

$$\begin{aligned}&\text{A more explicit way of stating the theorem is:}\\&f(X_1,X_2,\ldots,X_n)=X_1\cdot f(1,X_2,\ldots,X_n)+X_1^{\prime}\cdot f(0,X_2,\ldots,X_n)\end{aligned}$$

Proof

Proof of Shannon's Expansion Theorem. Let $f(x_1, x_2, \ldots, x_n)$ be a Boolean function of $n$ variables, and let $x_i$ be a selected variable. We want to express $f$ in terms of two subfunctions: one where $x_i$ is true and the other where $x_i$ is false.

First, we define two subfunctions:

$$$$$$\begin{aligned} f_{x_i} &= f(x_1, x_2, \ldots, x_i=1, \ldots, x_n) \\ f_{\overline{x_i}} &= f(x_1, x_2, \ldots, x_i=0, \ldots, x_n) \end{aligned}$$$$$$

Now, consider the following expression:

$$$$$$\begin{aligned} f &= x_i \cdot f_{x_i} + \overline{x_i} \cdot f_{\overline{x_i}} \\ &= (x_i \cdot 1 + \overline{x_i} \cdot 0) \cdot f_{x_i} + (x_i \cdot 0 + \overline{x_i} \cdot 1) \cdot f_{\overline{x_i}} \\ &= x_i \cdot f_{x_i} + \overline{x_i} \cdot f_{\overline{x_i}} \end{aligned}$$$$$$

We need to prove that this expression is equal to the original function $f(x_1, x_2, \ldots, x_n)$. For any combination of input values $(x_1, x_2, \ldots, x_n)$, either $x_i$ is true or $\overline{x_i}$ is true (but not both).

Therefore, one of the two product terms in the expression will be zero, and the other will be equal to the value of $f$ for that input combination.

If $x_i$ is true, then $x_i \cdot f_{x_i} = f_{x_i}$ and $\overline{x_i} \cdot f_{\overline{x_i}} = 0$, so the expression evaluates to $f_{x_i}$, which is the correct value of $f$ when $x_i$ is true.

If $x_i$ is false, then $x_i \cdot f_{x_i} = 0$ and $\overline{x_i} \cdot f_{\overline{x_i}} = f_{\overline{x_i}}$, so the expression evaluates to $f_{\overline{x_i}}$, which is the correct value of $f$ when $x_i$ is false.

Therefore, the expression $x_i \cdot f_{x_i} + \overline{x_i} \cdot f_{\overline{x_i}}$ correctly represents the Boolean function $f(x_1, x_2, \ldots, x_n)$ for all possible input combinations, proving Shannon's expansion theorem.

Write $f_1,f_0$ for the restrictions at $x=1,0$, with duals taken only in the remaining variables. Taking the dual of Shannon's expression gives

$$f^D=(x\lor f_1^D)\land(\neg x\lor f_0^D).$$

At $x=0$ this is $f_1^D$; at $x=1$ it is $f_0^D$. Thus the equivalent sum form is

$$f^D=(\neg x\land f_1^D)\lor(x\land f_0^D).$$

The branch values swap because the semantic formula negates the input before evaluating $f$.

Simplification of Boolean Function

Simplifying boolean functions is a crucial step in digital logic design. It involves reducing the complexity of a boolean expression without changing its truth table or output behavior. The method of simplification is manifold. This chapter shows several most commonly used ways.

Simplification by Boolean Laws (Algebra)

In the previous chapter, we discussed Boolean laws and identities. They can simplify expressions, but a truth table becomes unwieldy as the number of variables grows. Four inputs already give $2^4=16$ rows, and a sum-of-products or product-of-sums expression may contain many terms. For larger expressions, a Karnaugh map or an algorithmic minimizer is usually more practical.

Simplification by Karnaugh Maps

Karnaugh Maps (K-maps) are visual tools for simplifying boolean functions of up to six variables. They reduce the need for extensive calculations by taking advantage of human pattern recognition.

The K-map is essentially a truth table arranged in a grid that helps in the identification of common patterns and the elimination of redundant terms. Each cell in a K-map represents a possible input configuration of the variables, and the cells are arranged such that only one variable changes between adjacent cells. This adjacency allows for the visual grouping of terms, which corresponds to combining terms in the Boolean function that differ by only a single variable. As a result, K-maps make it easy to apply the combining rule: when two terms differ by only a single variable, that variable can be eliminated from the combined term.

ExampleConsidering this truth table X1 X2 X3 X4 Z1

Considering this truth table.

$X_1$	$X_2$	$X_3$	$X_4$	$Z_1$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	0

By finding the minterms, we have a four variable SOP function.

$$$$$$\begin{aligned} F_1(X1,X2,X3,X4) = & \overline{X1}\ \overline{X2}\ \overline{X3}\ \overline{X4}+\overline{X1}\ \overline{X2}\ \overline{X3}{X4}\\ &+\overline{X1}\ \overline{X2}{X3}{X4}+{X1}\overline{X2}{X3}{X4}\\ &+ \overline{X1}{X2}{X3} \overline{X4}+\overline{X1}{X2}{X3}{X4}\\ &+{X1}\ \overline{X2}\ \overline{X3}{X4}+{X1} \overline{X2}{X3} \overline{X4}\\ &+{X1}{X2}\overline{X3}\ \overline{X4}+{X1}{X2}\overline{X3}{X4} \end{aligned}$$$$$$

Of course we don't want to simplify such thing using Boolean Laws, which is definitely time-consuming. What we do here is to make a K-map for the graph. Notice that the sequence of the combination for the variables must follow Gray code sequence. In brief, change one bit at one time. Such as 01, 10, 11, 10 for combination of two variables. On the left we can see the K-map. To find the expression (here we try to get the SOP form), we need to group all 1s by the following pattern.

Grouping in Karnaugh Maps follows specific rules to ensure the correct simplification of a Boolean function. These rules are rooted in the principles of Boolean algebra and help to minimize the number of logical terms. Here are the key rules for grouping in K-maps:

1. Power of Two: Groups must contain either 1, 2, 4, 8, ... (powers of two) cells. This is to ensure that each group can be represented by a simplified product term.

2. Maximize Group Size: Groups should be as large as possible to maximize simplification. Larger groups result in fewer variables in the corresponding product term.

3. Overlap Allowed: Groups may overlap if doing so allows for larger groups to be formed, further simplifying the expression.

4. Wrap Around: Groups can wrap around the edges of the K-map, thanks to the toroidal topology of K-maps. This means that cells on the top edge are considered adjacent to those on the bottom edge, and similarly, the left edge is adjacent to the right edge.

5. Include All Ones: Each '1' in the K-map must be included in at least one group. The aim is to cover all minterms represented by the '1's.

6. Unused Cells: Cells with '0' values are not included in the groups unless they contribute to making a larger group with '1's.

7. Essential Prime Implicants: After grouping, any group that covers a minterm not covered by any other group represents an essential prime implicant and must be included in the final expression.

Applying these rules gives us the grouped graph on the right-hand-side. Now we only need to analyze group by group to rule out inconsistent variables among the group. Below are the breakdowns.

1. The first group (green) gives $\overline{X1}\ \overline{X2}\ \overline{X3}\ \overline{X4}$ and $\overline{X1}{X2}\overline{X3}\ \overline{X4}$, which rules out the $X2$ term, so we have $\overline{X1}\ \overline{X3}\ \overline{X4}$ in the expression.

2. The second group (red) gives $\overline{X1}\ \overline{X2}\ \overline{X3}{X4}$ and ${X1}\overline{X2}\ \overline{X3}{X4}$, which rules out the $X1$ term, so we have $\overline{X2}\ \overline{X3}{X4}$ in the expression.

3. The third group (blue) gives $\overline{X1}\ \overline{X2}{X3}{X4}$ and $\overline{X1}{X2}{X3}{X4}$, so we can rule out $X2$ terms, so we have $\overline{X1}{X3}{X4}$ in the expression.

4. The fourth group (purple) gives $\overline{X1}{X2}{X3}{X4}$ and $\overline{X1}{X2}{X3}\overline{X4}$, which rules out $X4$ terms, so we have $\overline{X1}{X2}{X3}$ in the expression.

5. The fifth group (yellow) gives ${X1}{X2}\overline{X3}\ \overline{X4}$ and ${X1}{X2}\overline{X3}{X4}$, which rules out $X4$ terms, so we have ${X1}{X2}\overline{X3}$ in the expression.

6. The last group (pink) is a single block, so we must also include ${X1}\overline{X2}{X3}\overline{X4}$ in the expression.

Each term we have found will be joined by + sign. Hence, we get the simplified SOP form for $F_1$.

$$$$$$\begin{aligned} F_1=\overline{X1}\ \overline{X3}\ \overline{X4}+\overline{X2}\ \overline{X3}{X4}+ \overline{X1}{X3}{X4}+\overline{X1}{X2}{X3}+{X1}{X2}\overline{X3}+{X1}\overline{X2}{X3}\overline{X4} \end{aligned}$$$$$$

Don't you think it's like magic? We have reduced this to a sum of six terms from ten terms. Does this method can help us to solve all the problems? Sadly no, because when we have seven or more variables in the k-map, something unexpected will happen.

We obtained the SOP form in this method, is it possible to get the POS form of the expression? Yes it is. All we need to do is repeating this process to 0s in the graph and apply same grouping rules. In the end, we rule out inconsistent variables for each turn and write them in a product of sum.

While Karnaugh Maps are powerful tools for simplifying Boolean expressions, they are commonly only used for functions with up to four to six variables due to several practical limitations:

1. Visualization Complexity: K-maps rely on spatial arrangements that allow the human eye to detect patterns and groupings. As the number of variables increases beyond six, the map becomes excessively complex, making it challenging to discern such patterns effectively.

2. Cognitive Load: The human brain has a limited capacity for processing complex information visually. The cognitive load increases significantly with each additional variable, making it difficult to perform the simplification accurately.

3. Physical Representation: A K-map's size doubles with each additional variable, leading to an exponential growth in the number of cells. A 6-variable K-map already has 64 cells, and a 7-variable map would have 128 cells, which becomes unwieldy for manual simplification.

4. Efficiency and Errors: With a large number of variables, the probability of making errors in grouping increases. It also becomes less efficient compared to computerized methods, such as the Quine-McCluskey algorithm (to be discussed later) or Binary Decision Diagrams (BDDs), which can handle a large number of variables systematically.

For these reasons, while theoretically possible, using K-maps for more than six variables is not practical, and alternative methods are preferred for simplifying larger Boolean functions.

To give a clearer idea on the nature of it and why it works, we can explain this mechanism by set theory. Each cell in a K-map corresponds to an element in the power set (the set of all subsets) of the Boolean variables' domain, reflecting a unique combination of variable values. Adjacent cells in the map are defined such that they only differ by one variable state, conforming to the principle of adjacency in set theory, where the intersection of sets differs by the least possible criteria.

Grouping cells in a K-map is akin to finding the union of subsets that share a common feature, thus simplifying the Boolean expression to include only the necessary variables. The simplified function represents the union of all such groups. The goal is to cover all the '1's in the K-map (the truth set of the function) with the fewest and largest possible groups of adjacent cells (subsets). These groups are then translated back into a minimized Boolean expression.

Simplification by Quine-McCluskey Method

Quine-McCluskey Method was developed in the 1950s by W. V. Quine and E. J. McCluskey, Jr. This method truly provides a mechanized way to simplify Boolean functions, which is more generalized.

The Quine--McCluskey algorithm, also known as the method of prime implicants, is a systematic technique used for minimizing Boolean functions. Similar to Karnaugh maps, the Quine--McCluskey algorithm finds the prime implicants of the function, which can then be used to extract the essential prime implicants, resulting in the simplified Boolean expression. However, unlike Karnaugh maps, the Quine--McCluskey algorithm does not rely on visual patterns and is therefore well-suited to computerization and can handle functions with many variables.

The algorithm consists of several steps:

1. List the minterms of the function in binary form.

2. Group the minterms based on the number of ones in their binary representation.

3. Compare each pair of minterms within adjacent groups to find pairs that differ by exactly one bit. Combine these pairs to form new terms, and mark the minterms that were combined.

4. Repeat the process until no further combinations are possible. The terms that remain are the prime implicants.

5. Use a prime implicant chart to identify essential prime implicants and select a minimal cover for the function.

In pseudo code it will be.

Algorithm 1 Quine-McCluskey Simplification

Require: Boolean function $f$

Ensure: a simplified Boolean expression

1:Convert each term of $f$ into binary form to obtain the minterms.

2:Group the minterms by the number of ones in their binary representations.

3:while further combinations are possible do

4:Combine pairs from adjacent groups that differ in one bit.

5:Mark the minterms that were combined.

6:end while

7:Collect unmarked terms as prime implicants.

8:Build a prime-implicant chart and select a minimal cover.

9:return the simplified function

ExampleAn Example of Boolean Function Representation

You may check one example here.

Exercises

ExerciseExpress XOR and implication in Boolean Function

Express XOR and implication in Boolean Function.

SolutionF(x, y)= x y &= (x and y) or ( x and y) &= xy' + x'y

$$$$$$\begin{aligned} F(x,y)= x \oplus y &= (x \land \lnot y) \lor (\lnot x \land y)\\ &= xy' + x'y \end{aligned}$$$$$$$$$$$$\begin{aligned} F(x,y)= x \rightarrow y &= \lnot x \lor y\\ &= x' + y \end{aligned}$$$$$$

ExerciseUse a table to express the values of each of these Boolean functions

Use a table to express the values of each of these Boolean functions.

1. $F(x, y, z) = xy$

2. $F(x, y, z) = x + yz$

3. $F(x, y, z) = xy + (xyz)$

4. $F(x, y, z) = x(yz + \overline{y}z)$

The third function simplifies to $xy$ by absorption; the fourth to $xz$ because $y+\overline y=1$.

$x$	$y$	$z$	$xy$	$x+yz$	$xy+xyz$	$x(yz+\overline y z)$
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	0	1	0	0
1	0	0	0	1	0	0
1	0	1	0	1	0	1
1	1	0	1	1	1	0
1	1	1	1	1	1	1

ExerciseProve duality of Boolean Function in Algebra method

Prove duality of Boolean Function in Algebra method.

Proof

The structural proof above covers variables, constants, both binary connectives, and negation. In particular for $f=x\lor\neg y$, both direct dualization and $\neg f(\neg x,\neg y)=\neg(\neg x\lor y)$ give $x\land\neg y$.

ExerciseUse K-map to simplify the Boolean Function from the following truth table

Use K-map to simplify the Boolean Function from the following truth table.

$X_1$	$X_2$	$X_3$	$X_4$	$Z_1$
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	1
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	0

SolutionThe function is given by F2(X1, X2, X3, X4) = & X1 X2 X3X4+ X1 X2X3 X4

The function is given by:

$$$$$$\begin{aligned} F_2(X1,X2,X3,X4) = &\overline{X1}\ \overline{X2}\ \overline{X3}{X4}+\overline{X1}\ \overline{X2}{X3}\overline{X4}\\ &+\overline{X1}\ \overline{X2}{X3}{X4}+\overline{X1}{X2}\overline{X3}\ \overline{X4}\\ &+\overline{X1}{X2}{X3}\overline{X4}+{X1}\overline{X2}\ \overline{X3}\ \overline{X4}\\ &+{X1}\overline{X2}\ \overline{X3}{X4}+{X1}\overline{X2}{X3}{X4}\\ &+{X1}{X2}\overline{X3}\ \overline{X4}+{X1}{X2}\overline{X3}{X4}. \end{aligned}$$$$$$

The K-map is as follows.

1. The first group (blue) gives $\overline{X1}\ \overline{X2}{X3}\overline{X4}$ and $\overline{X1}{X2}{X3}\overline{X4}$, which rules out $X2$ terms, so we have$\overline{X1}{X3}\overline{X4}$ in the expression.

2. The second group (yellow) gives $\overline{X1}{X2}\overline{X3}\ \overline{X4}$ and ${X1}{X2}\overline{X3}\ \overline{X4}$, which rules out $X1$ terms, so we have ${X2}\overline{X3}\ \overline{X4}$ in the expression.

3. The third group (red) has four blocks, so we can exclude two terms from it, and in this case we find that $X3$ and $X1$ terms differ, so we have $\overline{X2}{4}$ in the expression.

4. The last group (green) is also four-block, in the same way we rule out ${X2}$ and $X{4}$ terms, and we have $X1\overline{X3}$ in the expression.

Hence we get the simplified SOP form for $F_2$.

$$$$$$\begin{aligned} F_2=\overline{X1}{X3}\ \overline{X4}+{X2}\overline{X3}\ \overline{X4}+\overline{X2}{X4}+{X1}\overline{X3} \end{aligned}$$$$$$

ExerciseExpress each of these Boolean functions using the operators (AND) and...

Express each of these Boolean functions using the operators $\cdot$ (AND) and $-$ (NOT).

1. $x + y + z$

2. $x + \overline{y}(x + z)$

3. $x + \overline{y}$

4. $x(\overline{x} + y + z)$

SolutionWe need to use De Morgan's law to replace each occurrence of s + t by...

We need to use De Morgan's law to replace each occurrence of $s + t$ by $\overline{\overline{s} \cdot \overline{t}}$, simplifying by use of the double complement law if possible.

$$(x + y) + z = \overline{(\overline{x + y}) \cdot \overline{z}} = \overline{\overline{x} \cdot \overline{y}} \cdot \overline{z} = \overline{x} \cdot \overline{y} \cdot \overline{z}$$

$$x + \overline{y}(x + z) = x + \overline{y}(\overline{\overline{x} \cdot \overline{z}}) = x + \overline{y}\overline{\overline{x} \cdot \overline{z}} = x + \overline{y}\overline{x} \cdot \overline{z}$$

3. In this case, we can just apply De Morgan's law directly, to obtain $\overline{x \cdot \overline{y}} = \overline{x} + y$.

4. The second factor is changed in a manner similar to part (a). Thus, the answer is $\overline{x} \cdot (\overline{x} \cdot y)$.

ExerciseFind the sum-of-products expansion of the Boolean function F(x1, x2,...

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$, and $x_5$ have the value 1.

SolutionWe need to include all terms that have three or more of the variables...

We need to include all terms that have three or more of the variables in their uncomplemented form. This will give us a total of $1 + 5 + 10 = 16$ terms. The answer is:

$$$$$$\begin{aligned} F(x_1, x_2, x_3, x_4, x_5) = \ & x_1 x_2 x_3 x_4 x_5+ x_1 x_2 \overline{x_3} x_4 x_5\\ + \ & x_1 x_2 x_3 x_4 \overline{x_5} + x_1 x_2 x_3 \overline{x_4} x_5 \\ + \ & x_1 \overline{x_2} x_3 x_4 x_5 + \overline{x_1} x_2 x_3 x_4 x_5 \\ + \ & x_1 x_2 x_3 \overline{x_4} \overline{x_5} + x_1 x_2 \overline{x_3} x_4 \overline{x_5} \\ + \ & x_1 \overline{x_2} x_3 x_4 \overline{x_5} + \overline{x_1} x_2 x_3 x_4 \overline{x_5} \\ + \ & x_1 x_2 \overline{x_3} \overline{x_4} x_5 + x_1 \overline{x_2} x_3 \overline{x_4} x_5 \\ + \ & \overline{x_1} x_2 x_3 \overline{x_4} x_5 + x_1 \overline{x_2} \overline{x_3} x_4 x_5 \\ + \ & \overline{x_1} x_2 \overline{x_3} x_4 x_5 + \overline{x_1} \overline{x_2} x_3 x_4 x_5. \end{aligned}$$$$$$

ExerciseHow many different Boolean functions F(x, y, z) are there such that F(...

How many different Boolean functions $F(x, y, z)$ are there such that

$$F(\overline{x}, y, z) = F(x, \overline{y}, z) = F(x, y, \overline{z})$$

for all values of the Boolean variables $x, y$, and $z$?

SolutionSuppose that you specify F(0, 0, 0)

Suppose that you specify $F(0, 0, 0)$. Then the equations determine $F(0, 0, 0) = F(1, 1, 0)$ and $F(0, 0, 0) = F(1, 0, 1)$. It also therefore determines $F(1, 1, 0) = F(0, 1, 1)$, but nothing else. If we now also specify $F(1, 1, 1)$ (and there are no restrictions imposed so far), then the equations tell us, in a similar way, what $F(0, 0, 1)$, $F(0, 1, 0)$, and $F(1, 0, 0)$ are. This completes the definition of $F$. Since we had two choices in specifying $F(0, 0, 0)$ and two choices in specifying $F(1, 1, 1)$, the answer is $2 \times 2 = 4$.

ExerciseWe discussed in part 1 of the book about visualization of Euclidean Space

We discussed in part 1 of the book about visualization of Euclidean Space. Now, can you try to explain that how can we define $\mathbb{B}^n$'s visualization.

• How can we visualize $\mathbb{B}, \mathbb{B}^2, \mathbb{B}^3$? What kind of geometrical objects are they?

• Can you try to explain how $\mathbb{B}^4$ could be explained in terms of $\mathbb{B}^3$?

SolutionThe set B represents the Boolean domain, which consists of two...

The set $\mathbb{B}$ represents the Boolean domain, which consists of two elements: 0 and 1. For higher dimensions:

• $\mathbb{B}^2$ can be visualized as a square on a binary (2D) grid, where each corner corresponds to a pair of Boolean values (00, 01, 10, 11).

• $\mathbb{B}^3$ extends this to a cube in a three-dimensional binary grid, with each corner representing a triplet of Boolean values (000, 001, 010, 011, 100, 101, 110, 111).

Visualizing $\mathbb{B}^4$ is more abstract since we cannot directly perceive four dimensions. However, we can understand $\mathbb{B}^4$ in terms of $\mathbb{B}^3$ by considering a hypercube or tesseract, which is a theoretical shape in four-dimensional space. Each vertex of the tesseract corresponds to a unique 4-tuple of Boolean values (e.g., 0000, 0001, ..., 1111).

While we can't visualize four dimensions spatially, we can represent $\mathbb{B}^4$ using a four-dimensional binary grid, where each point is uniquely identified by its four Boolean coordinates.

Below is the visualization of Boolean Domain in Euclidean Space as collection of points.

Predicates and Quantifiers

A Boolean function takes truth values as inputs. A predicate instead describes objects from a specified domain, and a quantifier ranges over that domain. For the working definitions and negation laws, see Propositions and Axiomatic Systems. For formal syntax, variable scope, substitutions, and quantifier inference rules, continue with Formal Logic and Natural Deduction.

Inference and Deduction

Algebraic simplification preserves a function; inference asks what follows from premises. A useful reading sequence is formal logic and natural deduction, propositional automated reasoning, then first-order resolution and theorem proving. The CNF representation developed here becomes input to resolution and SAT, while Karnaugh maps and Boolean minimization remain part of the algebraic route.