Introduction to boolean algebra

Boolean algebra is an algebraic system used to work with logical values and logical operations. It provides a mathematical foundation for propositional logic, switching circuits, and digital logic.

Unlike ordinary algebra, Boolean algebra uses operations such as OR, AND, and complementation. In the familiar two-element Boolean algebra, the only values are

$$0 \quad \text{and} \quad 1$$

where

• $0$ represents False
• $1$ represents True

The symbols $+$ and $\cdot$ are used for Boolean addition and Boolean multiplication respectively, but they do not behave exactly like ordinary arithmetic addition and multiplication.

---

Definition of Boolean Algebra

A non-empty set $B$ equipped with two binary operations $+$ and $\cdot$, a unary operation $'$, and two distinct elements $0$ and $1$ is called a Boolean algebra if the required Boolean algebra laws are satisfied.

It is written as

$$(B,+,\cdot,',0,1)$$

For elements $a,b,c\in B$:

• $a+b$ represents the OR operation.
• $a\cdot b$ represents the AND operation.
• $a'$ represents the complement of $a$.
• $0$ and $1$ are the distinguished Boolean elements.

When there is no possibility of confusion, the multiplication symbol may be omitted:

$$a\cdot b = ab$$

---

Fundamental Laws of Boolean Algebra

Boolean algebra is governed by a collection of fundamental laws.

Commutative Laws

The order of the operands does not affect the result.

For OR:

$$a+b=b+a$$

For AND:

$$ab=ba$$

---

Distributive Laws

Boolean algebra has two distributive laws.

AND distributes over OR:

$$a(b+c)=ab+ac$$

OR also distributes over AND:

$$a+bc=(a+b)(a+c)$$

This second distributive law is one of the important differences between Boolean algebra and ordinary algebra.

---

Identity Laws

For OR:

$$a+0=a$$

For AND:

$$a\cdot1=a$$

Thus, $0$ is the identity element for OR, while $1$ is the identity element for AND.

---

Complement Laws

Every Boolean element $a$ has a complement $a'$ such that

$$a+a'=1$$

and

$$aa'=0$$

For the two Boolean constants,

$$0'=1$$

and

$$1'=0$$

---

Basic Theorems of Boolean Algebra

Several useful results follow from the fundamental laws.

Idempotent Laws

Repeating the same variable does not change the result.

$$a+a=a$$

and

$$aa=a$$

For example,

$$1+1=1$$

and

$$0\cdot0=0$$

---

Boundedness Laws

OR with $1$ always gives $1$:

$$a+1=1$$

AND with $0$ always gives $0$:

$$a\cdot0=0$$

---

Absorption Laws

The absorption laws are

$$a+ab=a$$

and

$$a(a+b)=a$$

For example,

$$x+xy=x$$

because once $x$ is true, the value of $y$ does not affect the OR expression.

---

Associative Laws

The grouping of variables does not affect the result.

For OR:

$$(a+b)+c=a+(b+c)$$

For AND:

$$(ab)c=a(bc)$$

Therefore, expressions such as

$$a+b+c$$

and

$$abc$$

can usually be written without parentheses.

---

Uniqueness of Complement

The complement of an element is unique.

If an element $x$ satisfies

$$a+x=1$$

and

$$ax=0,$$

then

$$x=a'$$

Therefore, every element of a Boolean algebra has exactly one complement.

---

Involution Law

Taking the complement twice returns the original element:

$$(a')'=a$$

For example,

$$(0')'=0$$

because

$$0'=1$$

and

$$1'=0.$$

---

Complement of the Constants

The Boolean constants are complements of each other:

$$0'=1$$ $$1'=0$$

---

De Morgan's Laws

The complement of an OR expression is the AND of the complements:

$$(a+b)'=a'b'$$

The complement of an AND expression is the OR of the complements:

$$(ab)'=a'+b'$$

These laws are among the most important tools for simplifying Boolean expressions.

---

Summary of Important Boolean Laws

Also,

$$(a')'=a.$$

---

Algebraic Verification of Some Boolean Laws

Boolean identities can be proved either algebraically using previously established laws or by constructing truth tables.

Proof of the Idempotent Law

We want to prove

$$a+a=a.$$

Using the identity and complement laws,

$$a+a$$

can be written as

$$a+a\cdot1.$$

Since

$$1=a+a',$$

we obtain

$$a+a(a+a').$$

Using distributivity,

$$a+aa+aa'.$$

Since

$$aa'=0,$$

this becomes

$$a+aa.$$

Using absorption,

$$a+aa=a.$$

Hence,

$$\boxed{a+a=a}$$

Similarly,

$$\boxed{aa=a}.$$

---

Proof of the Boundedness Law

Consider

$$a+1.$$

Since

$$1=a+a',$$

we have

$$a+1=a+(a+a').$$

Using associativity and idempotence,

$$a+a+a'=a+a'.$$

Therefore,

$$a+1=1.$$

Hence,

$$\boxed{a+1=1}$$

The dual result is

$$\boxed{a\cdot0=0}.$$

---

Proof of an Absorption Law

Consider

$$a+ab.$$

Using the distributive law,

$$a+ab=a(1+b).$$

Since

$$1+b=1,$$

we get

$$a\cdot1=a.$$

Therefore,

$$\boxed{a+ab=a}.$$

Its dual is

$$\boxed{a(a+b)=a}.$$

---

Some Distinctive Features of Boolean Algebra

Boolean algebra differs from ordinary arithmetic algebra in several important ways.

In the commonly used two-element Boolean algebra,

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

all variables take only the values $0$ or $1$.

However, Boolean algebras can contain more than two elements. The two-element algebra is simply the most important one for logic and digital circuits.

Boolean algebra also has no direct equivalent of ordinary subtraction or division.

Another characteristic operation is complementation:

$$a'$$

which has no direct counterpart among the standard arithmetic operations.

---

Boolean Subalgebra

Suppose

$$(B,+,\cdot,',0,1)$$

is a Boolean algebra.

A non-empty subset $A\subseteq B$ is called a Boolean subalgebra if $A$ itself forms a Boolean algebra under the same Boolean operations.

In particular, the subset must be closed under the required operations.

If

$$a,b\in A,$$

then the appropriate results such as

$$a+b,$$ $$ab,$$

and

$$a'$$

must also belong to $A$.

---

Example Using the Divisors of 30

Consider

$$D_{30}=\{1,2,3,5,6,10,15,30\},$$

the set of positive divisors of $30$.

Define

$$a+b=\operatorname{lcm}(a,b),$$ $$ab=\gcd(a,b),$$

and

$$a'=\frac{30}{a}.$$

Under these operations, $D_{30}$ forms a Boolean algebra.

Here the Boolean zero is the number $1$, because

$$\operatorname{lcm}(a,1)=a,$$

while the Boolean one is $30$, because

$$\gcd(a,30)=a.$$

Consider the subset

$$A=\{1,5,6,30\}.$$

The complements are

$$1'=30,$$ $$5'=6,$$ $$6'=5,$$

and

$$30'=1.$$

The subset is also closed under the corresponding $\gcd$ and $\operatorname{lcm}$ operations. Therefore it forms a Boolean subalgebra of $D_{30}$.

---

Basic Boolean Operations

The three basic operations of Boolean algebra are:

• logical addition,
• logical multiplication,
• complementation.

They correspond to

$$\text{OR},\qquad \text{AND},\qquad \text{NOT}.$$

In digital logic, $0$ and $1$ can be interpreted in several equivalent ways.

The exact physical interpretation depends on the system being considered.

---

Logical Addition: OR Operation

Logical addition is represented by

$$+$$

and corresponds to the OR operation.

Its basic rules are

$$0+0=0$$ $$0+1=1$$ $$1+0=1$$ $$1+1=1.$$

If

$$C=A+B,$$

then $C$ is true whenever at least one of $A$ or $B$ is true.

Truth Table of OR

Therefore,

$$A+B$$

is read as

A OR B.

Notice that Boolean addition is different from ordinary arithmetic addition because

$$1+1=1$$

in Boolean algebra.

---

Logical Multiplication: AND Operation

Logical multiplication corresponds to the AND operation.

It may be written as

$$A\cdot B$$

or simply

$$AB.$$

The operation is defined by

$$0\cdot0=0$$ $$0\cdot1=0$$ $$1\cdot0=0$$ $$1\cdot1=1.$$

If

$$C=AB,$$

then $C$ is $1$ only when both $A$ and $B$ are $1$.

Truth Table of AND

Thus,

$$AB$$

is read as

A AND B.

---

Complementation: NOT Operation

Complementation reverses the Boolean value of a variable.

If

$$A=0,$$

then

$$A'=1.$$

If

$$A=1,$$

then

$$A'=0.$$

Therefore,

$$0'=1$$

and

$$1'=0.$$

The expression

$$A'$$

is read as

NOT A.

Truth Table of NOT

---

Principle of Duality

One of the most useful properties of Boolean algebra is the principle of duality.

The dual of a Boolean expression is obtained by simultaneously replacing

$$+\longleftrightarrow\cdot$$

and

$$0\longleftrightarrow1.$$

Variables and their complements remain unchanged.

For example, consider

$$a+0=a.$$

Replacing OR with AND and $0$ with $1$ gives

$$a\cdot1=a.$$

Thus these two identity laws are duals of one another.

Similarly,

$$a+1=1$$

has the dual

$$a\cdot0=0.$$

Another example is

$$a+ab=a.$$

Its dual is

$$a(a+b)=a.$$

The principle of duality means that when a Boolean identity follows from the Boolean algebra axioms, its dual identity also follows.

---

Example of Forming a Dual

Suppose

$$F=(a\cdot1)(0+a').$$

To obtain the dual, interchange

$$\cdot\leftrightarrow+$$

and

$$0\leftrightarrow1.$$

Therefore,

$$F^D=(a+0)+(1\cdot a').$$

The variables themselves remain unchanged.

---

De Morgan's Theorems

De Morgan's theorems describe how complementation interacts with OR and AND.

They are

$$(x+y)'=x'y'$$

and

$$(xy)'=x'+y'.$$

In words:

• the complement of an OR becomes the AND of the complements;
• the complement of an AND becomes the OR of the complements.

---

Verification Using a Truth Table

The final two columns are identical. Therefore,

$$\boxed{(x+y)'=x'y'}$$

Similarly:

Therefore,

$$\boxed{(xy)'=x'+y'}.$$

---

De Morgan's Theorem for More Than Two Variables

De Morgan's laws can be extended to any number of Boolean variables.

For example,

$$(x+y+z)'.$$

Let

$$A=x+y.$$

Then

$$(x+y+z)'=(A+z)'.$$

Using De Morgan's theorem,

$$(A+z)'=A'z'.$$

Since

$$A'=(x+y)'=x'y',$$

we obtain

$$(x+y+z)'=x'y'z'.$$

Therefore,

$$\boxed{(x+y+z)'=x'y'z'}.$$

Similarly,

$$\boxed{(xyz)'=x'+y'+z'}.$$

---

Applying De Morgan's Theorem to Expressions

The variables in De Morgan's theorem may themselves be compound Boolean expressions.

Consider

$$(AB'+C)'.$$

Using De Morgan's theorem,

$$(AB'+C)'=(AB')'C'.$$

Now,

$$(AB')'=A'+(B')'.$$

Using the involution law,

$$(B')'=B.$$

Therefore,

$$(AB')' = A'+B.$$

Hence,

$$(AB'+C)'=(A'+B)C'.$$

Distributing $C'$ gives

$$\boxed{A'C'+BC'}.$$

---

A General Rule for Complementing Boolean Expressions

To complement a Boolean expression, perform the following transformations simultaneously:

• replace $0$ with $1$,
• replace $1$ with $0$,
• replace $+$ with $\cdot$,
• replace $\cdot$ with $+$,
• replace every variable with its complement.

This provides a systematic way of applying De Morgan's theorem to larger expressions.

---

Logic Gates

Boolean operations can be implemented electronically using logic gates.

A logic gate is a digital circuit that accepts one or more input signals and produces an output signal according to a Boolean operation.

The main gates considered here are:

• OR
• AND
• NOT
• NAND
• NOR
• XOR
• XNOR

Each input and output normally has one of two logical values:

$$0\quad\text{or}\quad1.$$

---

OR Gate

An OR gate performs Boolean addition.

For two inputs $A$ and $B$,

$$F=A+B.$$

The output is $1$ when at least one input is $1$.

An OR gate symbolically represented as

Loading image…

Two-Input OR Truth Table

The OR operation can also be extended to more than two inputs.

For three inputs,

$$F=A+B+C.$$

Loading image…

Three-Input OR Truth Table

---

AND Gate

An AND gate performs Boolean multiplication.

For two inputs,

$$F=AB.$$

Loading image…

The output is $1$ only when both inputs are $1$.

The same principle applies to an AND gate containing more than two inputs.

For example,

$$F=ABC$$

is $1$ only when

$$A=B=C=1.$$

---

NOT Gate

A NOT gate has only one input and one output.

It is also called an inverter because its output is the opposite of its input.

$$F=A'$$

It is symbolically represented as

Loading image…

---

NAND Gate

A NAND gate is an AND operation followed by complementation.

Therefore,

$$F=(AB)'.$$

Using De Morgan's theorem,

$$F=A'+B'.$$

It is symbolically represented as

Loading image…

Its truth table is

Thus, a NAND gate produces $0$ only when both inputs are $1$.

---

NOR Gate

A NOR gate is an OR operation followed by complementation.

Therefore,

$$F=(A+B)'.$$

Using De Morgan's theorem,

$$F=A'B'.$$

It is symbolically represented as

Loading image…

Its truth table is

A NOR gate therefore produces $1$ only when both inputs are $0$.

---

Exclusive OR: XOR Gate

The ordinary OR operation is sometimes called inclusive OR, because it produces $1$ even when both inputs are $1$.

The Exclusive OR, or XOR, behaves differently.

It produces $1$ when the two inputs are different.

The XOR operation is represented by

$$\oplus.$$

Thus,

$$F=A\oplus B.$$

Its Boolean expression is

$$\boxed{A\oplus B=A'B+AB'}.$$

It is symbolically represented as

Loading image…

XOR Truth Table

Thus, XOR produces $1$ when exactly one of the two inputs is $1$.

---

Exclusive NOR: XNOR Gate

An XNOR gate is the complement of an XOR gate.

Therefore,

$$F=(A\oplus B)'.$$

Its Boolean expression is

$$\boxed{F=AB+A'B'}.$$

The output is $1$ when both input values are equal.

It is symbolically represented as

Loading image…

XNOR Truth Table

Thus,

$$F=AB+A'B'$$

can also be written as

$$F=A\operatorname{XNOR}B$$

or

$$F=(A\oplus B)'.$$

---

Logic Gates at a Glance

---

Combined Truth Table of Two-Input Gates

The behavior of the major two-input gates can be compared directly.

The NOT gate is not included in this table because it has only one input.

Its truth table is simply

---

Interconnecting Logic Gates

Logic gates can be connected together to form larger logic networks or gating networks.

The Boolean expression corresponding to a circuit can be determined by moving systematically from the inputs toward the final output.

Consider an intermediate output

$$X=AB$$

and another operation

$$F=X+C.$$

Substituting the expression for $X$ gives

$$F=AB+C.$$

Thus, the Boolean expression for a network can be built one gate at a time.

Several gates may also use the same input. In a circuit diagram, this can be represented by branching the input line so that the same signal is supplied to multiple gates.

Few examples of interconnected gates

Loading image…

---

Final Summary

Boolean algebra provides an algebraic framework for working with logical quantities.

Its three fundamental operations are

$$\boxed{\text{OR},\quad \text{AND},\quad \text{NOT}}$$

represented respectively by

$$+,\qquad \cdot,\qquad '.$$

Important Boolean laws include the identity, complement, idempotent, boundedness, absorption, associative, distributive, involution, and De Morgan laws.

The principle of duality allows one valid Boolean identity to generate another by interchanging

$$+\leftrightarrow\cdot$$

and

$$0\leftrightarrow1.$$

De Morgan's theorems,

$$(x+y)'=x'y'$$

and

$$(xy)'=x'+y',$$

provide a systematic method for complementing Boolean expressions.

Finally, Boolean operations are implemented physically using logic gates such as AND, OR, NOT, NAND, NOR, XOR, and XNOR. By interconnecting these gates, increasingly complex Boolean expressions and logic networks can be constructed.