National Higher School of Technology and Engineering Annaba

Department of preparatory classes Computer Science 1 Course

Chapitre 3 : Algèbre de Boole

Chapter 3: Boolean Algebra

Chapter Objective: This chapter presents the main techniques for understanding Boolean
algebra and the Karnaugh method.

Dr Lachtar 1
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole

1. Introduction :

Boolean algebra, or Boolean calculus, is a branch of mathematics, logic, and electronics that deals with operations
and functions on logical variables. More specifically, Boolean algebra allows the use of algebraic techniques to
manipulate expressions with two truth values in propositional calculus. It was initiated by the British
mathematician George Boole (1815-1864) in the mid-19th century. Boolean algebra is an algebra that aims to
translate signals into mathematical expressions. To achieve this, each elementary signal is defined using logical
variables, and their manipulation is done through logical functions. Methods such as truth tables are used to define
the desired operations and to transcribe the result into an algebraic expression. By applying rules known as laws
of composition, these expressions can be simplified. This simplification allows for the representation of a logical
circuit using symbols, which means representing the arrangement of basic components at a logical level, without
concerning the physical realization using transistors. Today, Boolean algebra finds numerous applications in
computer science and in the design of electronic circuits. It was first used for switching circuits in telephony by
Claude Shannon. A processor is composed of transistors that perform functions on digital signals. These
transistors, when assembled, form components that can carry out very basic functions. By combining these
components, it becomes possible to create circuits that perform highly complex operations. Boolean algebra for
logical functions allows for modeling logical reasoning by expressing a "state" in terms of conditions.

2. Logical Variables and Functions

2.1. Logical Variable:
A computer operates with binary data, so a logical variable is referred to as binary data, meaning data that can
exist in two possible states: 0 (false) or 1 (true). Electronic signals can have a voltage value of approximately 5
Volts (as a general magnitude), which is represented as 1, or 0 Volts, represented as 0. Example 1: Consider two
logical variables: Transmitter: Active (on) = 1 (true) Inactive (off) = 0 (false) Receiver: Active (on) = 1 (true)
Inactive (off) = 0 (false).

A logical (Boolean) variable is a variable that can take on the values 0 or 1. Typically, it is represented by a single
uppercase alphabetical character (A, B, S, ...).

Logical Level: When studying a logical system, it is important to specify the level of work.

Level Positive Logic Negative Logic

High H 1 0

Low L 0 1

2.2. Logical Functions

A logical function is an entity that accepts multiple logical values as inputs and has one or more possible outputs,
each of which can be in one of two states: 0 or 1. In reality, these functions are electronic components that take
electrical signals as input and produce an output signal.

The basic logical functions are known as logic gates:

• The OR function sets its output to 1 if either of its inputs is 1.

• The AND function sets its output to 1 if both of its inputs are 1.
• The XOR (Exclusive OR) function sets its output to 1 if either of its inputs is 1, but not both
simultaneously.
• The NOT function (also called an inverter) sets its output to 1 if its input is 0, and vice versa.

Dr Lachtar 2
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole
The NOR (NOT OR) and NAND (NOT AND) functions are generally defined as the respective compositions of
a NOT gate with an OR gate and an AND gate.

Example:

Communication = Transmitter AND Receiver (C = T AND R)

C = 1 (communication established) 0 (communication not established)

T = 1 (transmitter active) 0 (transmitter inactive)

R = 1 (receiver active) 0 (receiver inactive)

Communication is "TRUE" if both the Transmitter and Receiver are active (it is a logical function dependent on
the Transmitter and Receiver variables).

Pick up the phone = (Decision to answer AND Ringing) OR Decision to call (P = (A AND R) OR C)

Picking up the phone is "TRUE" if you hear the phone ringing and decide to answer it OR if you decide to make
a call.

Note: If a logical function has N logical variables, there are 2 N possible combinations, and the function has 2 N
values. These values can be represented by a Truth Table (TT).

2.3. Truth Table

A truth table is a table used to describe all possible output combinations based on input variables. Input variables
are placed in the left columns, varying them in a way that covers all possibilities. The right column (or columns,
if the function has multiple outputs) describes the output. Here are truth tables for some basic logic gates:
Gate Name Inputs Output
A B S
0 0 0
0 1 1
OR (OU)
1 0 1
1 1 1
0 0 0
0 1 0
AND (ET)
1 0 0
1 1 1
0 0 1
0 1 0
NOR (NON OU)
1 0 0
1 1 0
0 0 1
0 1 1
NAND( NON ET)
1 0 1
1 1 0
0 0 0
0 1 1
XOR
1 0 1
1 1 0
0 1
NOT (NON)
1 0

Dr Lachtar 3
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole
Order of Operator Precedence (Operator Priority)
To evaluate a logical expression (logical function):
• Begin by evaluating sub-expressions inside parentheses.
• Then, evaluate the complement (NOT).
• Next, evaluate the logical product (AND).
• Finally, evaluate the logical sum (OR).

For example 2:
The truth table (TV) for the function P is as follows:

A R C P
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

The algebraic expression associated with this truth table is

𝑃 = 𝐴. 𝑅. 𝐶. +𝐴. 𝑅. 𝐶̅ + 𝐴. 𝑅̅ . 𝐶 + 𝐴.
̅ 𝑅. 𝐶 + 𝐴̅. 𝑅̅ . 𝐶

2.4. Logical Circuits

2.4.1. Representation of Logic Gates

The conventional representation of logic gates is as follows:

Dr Lachtar 4
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole
2.4.2. Creation of logic circuits (logic diagram)

A logical circuit (or combinational circuit) is a set of logic gates connected together to implement an algebraic
expression. It involves translating the simplified algebraic expression into an electrical diagram using the
representations mentioned above. For example, the algebraic expression:

S = (A + B) · (A + ¬C)

Will be schematically represented as follows:

2.5. Conclusion

Boolean algebra is a common field shared by three disciplines, which is why different notations are encountered
for denoting the same object. Boolean algebra is composed of:

1. A set E,
2. Two specific elements of E: 0 and 1 (corresponding to FALSE and TRUE, respectively),
3. Two binary operations on E: + (disjunction) and · (conjunction) (corresponding to logical OR and AND,
respectively),
4. A unary operation on E: ¬ (bar, corresponding to logical negation).

A logical function can be represented by an algebraic expression or by its truth table (mathematical modeling) or
by a logic circuit (electronic implementation).

3. Fundamental Laws of Boolean Algebra (Composition Laws)

Composition laws are logical rules that simplify the writing of algebraic expressions.
Associativity: (A · B) · C is equivalent to A · (B · C)
(A + B) + C is equivalent to A + (B + C)
Absorption: A · (A + B) is equivalent to A
A + A · B is equivalent to A

Commutativity: A · B is equivalent to B · A
A + B is equivalent to B + A

Distributivity: A + (B · C) is equivalent to (A + B) ·(A + C)

A · (B + C) is equivalent to A · B + A · C

Idempotence: A · A is equivalent to A A + A is equivalent to A

Identity: 1 · A is equivalent to A
0 + A is equivalent to A

Inversion: A · A̅ is equivalent to 0
A + A̅ is equivalent to 1

Dr Lachtar 5
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole
Nullity: 0 · A is equivalent to 0
1 + A is equivalent to 1

De Morgan's Theorem:
• is equivalent to
• is equivalent to

Example of expression: simplification: Consider the following simplification:

̅ 𝑩𝑪 + 𝑨𝑩𝑪 + 𝑨𝑩
𝑨 ̅𝑪̅ + 𝑨𝑩
̅𝑪

̅ )(𝑩𝑪) + (𝑪 + 𝑪
(𝑨 + 𝑨 ̅ )(𝑨𝑩
̅)

̅
𝑩𝑪 + 𝑨𝑩

4. Properties of Logical Functions

4.1. Textual Definition of a Logical Function: This involves defining the mathematical model (the logical
function) based on a textual description corresponding to the system's operation.

For example:

Consider a high-security lock that opens based on three keys. The operation of the lock is defined as follows:
• The lock is opened if at least two keys are used.
• The lock remains closed in all other cases.
The system has three inputs, where each input represents a key. We will assign a logical variable to each key: Key
1 to A, Key 2 to B, and Key 3 to C.
• If Key 1 is used, then variable A = 1, otherwise A = 0.
• If Key 2 is used, then variable B = 1, otherwise B = 0.
• If Key 3 is used, then variable C = 1, otherwise C = 0.
The system has a single output, representing the state of the lock (open or closed). We will assign a variable S to
denote the output:
• S = 1 if the lock is open.
• S = 0 if the lock is closed.
The function can be expressed as: S = F(A, B, C) F(A, B, C) = 1 if at least two keys are used. F(A, B, C) = 0
otherwise.

Note: It is important to specify the logical level with which one is working (positive or negative logic).

4.2. Canonical Forms of Logical Functions: There is an equivalence/transition between a logical expression
and the truth table of the function. One can always determine one from the other. Two logical functions are
identical if it can be shown through the properties of Boolean algebra that their logical expressions are
identical or if their truth tables are identical.

Note 1: When referring to a logical function, it is often discussed in the context of the corresponding logical
expression. For a logical function with x variables:

• A minterm is a group of x variables linked by AND.

• A maxterm is a group of x variables linked by OR.

Canonical forms of a logical function: the most commonly used are:

1. First form (disjunctive form): union (OR) of minterms (sum of products). It is a disjunction of
conjunctions. Example: F(A, B, C) = A·B·C + A·B̅·C + A̅·B̅·C̅
Example :
F(A,B,C) = A.B.C + A.𝐵̅ .C +𝐴̿𝐵̅𝐶̅

Dr Lachtar 6
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole
2. Second form (conjunctive form): intersection (AND) of maxterms (product of sums). It is a conjunction
of disjunctions.
Example: F(A, B, C) = (A+B+C)·(A+B̅+C)

Note 2: The first and second canonical forms are equivalent. Any logical function can be converted to one of the
canonical forms. This involves adding missing variables to terms that do not contain all the variables (non-
canonical terms). This can be done using the rules of Boolean algebra:
• Multiplying a term with an expression that equals 1.
• Adding to a term with an expression that equals 0.
• Then, distribute as necessary.

Example of Conversion to the First Canonical Form

Let's consider the function:
F(A,B,C)=A.B+𝐵̅ . 𝐶 + 𝐴. 𝐶̅

First minterm: A·B. The variable C is missing.

Transform A·B into A·B·(C + C̅) because C + C̅ = 1.
Do the same for the other two minterms:
F(A, B, C) = A·B·(C + C̅) + B̅·C·(A + A̅) + A·C̅·(B + B̅)
= A·B·C + A·B·C̅ + A·B̅·C + A̅·B̅·C + A·B·C̅ + A·B̅·C̅

Conversion from the Truth Table to the Logical Function

From the truth table, the function is under: First canonical form:
• For each value of F(X) equal to 1, define a minterm of all variables. If a variable Xi = 1, write Xi;
otherwise, write X̅i. The first canonical form of F(X) is the OR of these minterms.
Second canonical form:
• For each value of F(X) equal to 0, define a maxterm of all variables. If a variable Xi = 0, write Xi;
otherwise, write X̅i. The AND of these maxterms is F(X).

Example: F(A, B, C) = A·B + B̅·C + A·C̅

The truth table is as follows:

A B C 𝐵̅ 𝐶̅ AB 𝐵̅ 𝐶 𝐴𝐶̅ F
0 0 0 1 1 0 0 0 0
0 0 1 1 0 0 1 0 1
0 1 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 0
1 0 0 1 1 0 0 1 1
1 0 1 1 0 0 1 0 1
1 1 0 0 1 1 0 1 1
1 1 1 0 0 1 0 0 1

First Canonical Form: F(A, B, C) = 1 when:

• A = 0, B = 0, C = 1, leading to the minterm A̅B̅C
• A = 1, B = 0, C = 0, leading to the minterm AB̅C̅
• A = 1, B = 0, C = 1, leading to the minterm AB̅C
• A = 1, B = 1, C = 0, leading to the minterm ABC̅
• A = 1, B = 1, C = 1, leading to the minterm ABC
So, F(A, B, C) = A̅B̅C + AB̅C̅ + AB̅C + ABC̅ + ABC

Second Canonical Form: F(A, B, C) = 0 when:

• A = 0, B = 0, C = 0, leading to the maxterm A + B + C

• A = 0, B = 1, C = 0, leading to the maxterm A + B̅ + C
• A = 0, B = 1, C = 1, leading to the maxterm A + B̅ + C̅

Dr Lachtar 7
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole
So, take the AND of these maxterms: (A + B + C)(A + B̅ + C)(A + B̅ + C̅).

F(A, B, C) = 0 when:
• A = 0, B = 0, C = 0, leading to the maxterm A + B + C
• A = 0, B = 1, C = 0, leading to the maxterm A + B̅ + C
• A = 0, B = 1, C = 1, leading to the maxterm A + B̅ + C̅
So, take the AND of these maxterms: (A + B + C)(A + B̅ + C)(A + B̅ + C̅).

Second Canonical Form: F(A, B, C) = 0 when:

• A = 0, B = 0, C = 0, leading to the maxterm A + B + C
• A = 0, B = 1, C = 0, leading to the maxterm A + B̅ + C
• A = 0, B = 1, C = 1, leading to the maxterm A + B̅ + C̅
So, take the AND of these maxterms: (A + B + C)(A + B̅ + C)(A + B̅ + C̅).

4.3. Simplification of Boolean Expressions

Canonical forms of a logical function provide a correct definition of the function, but they can be simplified,
meaning that the same function can be expressed with fewer and simpler terms (fewer logical variables). This
simplification is important for implementing the function with fewer electronic components (logic gates).

There are two methods for simplifying the expression of a logical function:

1. Using the properties of Boolean algebra (algebraic method).

2. Using the Karnaugh map method.

2.1.1. Algebraic Method

The principle is to apply the rules of Boolean algebra to eliminate variables or terms. However, there is no
specific step-by-step procedure. Here are some commonly used rules:

A.B+ A.B= B
A + A.B= A
A + A.B= A + B
( A + B) ( A + B) = A
A . ( A + B) = A
A . (A + B) = A . B
Term grouping
Example:

ABC + AB C + A BCD = AB (C + C) + A BCD

= AB + A BCD
= A ( B + B (CD))
= A ( B + CD)
= AB + ACD
Add an already existing term to an expression
Example :
A B C + ABC + A BC + ABC =
ABC + ABC + ABC + A BC + ABC + ABC =
BC + AC + AB
Dr Lachtar 8
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole

It is possible to delete a superfluous term (an additional term), that is to say already included in the
combination of other terms
Example:
F(A, B, C) = A B + BC + AC = AB + BC + AC ( B + B)
= AB + BC + ACB + A BC
= AB ( 1 + C) + BC (1 + A)
= AB + BC

4.3.1. Karnaugh Table Method

The Karnaugh diagram is a graphical tool that allows you to simplify a logical equation.

General principles
• Representation in a particular form of the truth table of a logical function
• Determination of rectangular blocks of size 2 n(1, 2, 4, 8...) bits adjacent to 1
• Deduction of the simplified function associated with the truth table.

Two terms are said to be adjacent if they have the same variables, the only difference is the state of a variable
which changes.
Example: A.B +A.𝐵̅ . These two minterms are said to be adjacent, the simplification of the expression eliminates
the variable B (the one which changes state) to retain only A.

We represent a 2-dimensional array

• Each dimension concerns one or 2 variables.
• Moving from a column to an adjacent column or from a row to an adjacent row changes the value of a
single variable.
• The table closes on itself: the leftmost column is next to the rightmost column, the same goes for the top
and bottom rows.
• For the 2 extreme columns (2 rows), again, only one variable must change value between these 2 columns
(rows)
• A box in the table contains a Boolean value, determined from the truth table and the values of the variables

The transition from the truth table to the Karnaugh table is done as follows:
• For each combination which represents a mintermes there is a corresponding box in the table which must
be set to 1.
• For each combination which represents a maxterm there is a corresponding box in the table which must
be set to 0.
• When we fill in the table, we must either take the minterms or the maxterms

Principles of simplification:
• Grouping of adjacent 1 bits into rectangular blocks
• All 1 bits in the table must be encompassed in at least one block (a block with a size of 1, 2, 4, 8 ... bits)
• A bit at 1 can belong to several block
• We must create the largest blocks possible
• Each block corresponds to a term formed as follows:
o For the block, if a variable takes the value 0 and 1, we do not take it into accoun
o We only keep the variables which do not vary. If a variable A remains at 1: we note A, if it
remains at 0: we note 𝐴̅
• The logical term of the block corresponds to the AND of these variables which do not change
• The simplified logical function is the OR of all the terms of the blocks found

Example: table with two variables:

Dr Lachtar 9
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole

We have 2 groups of two adjacent bits

For the vertical group (A does not change and always at 1) so we have the term A
For the horizontal group (B does not change and always at 1) so we have the term B
F= A+B

Example: table with 3 variables:

This simplification gives F =𝐴̅𝐵̅𝐶 + A

This simplification is not final because the table closes on itself

AB 00 01 11 10
C

0 0 0 11 11

1 1 0 11 11

𝐵̅𝐶 A
The final simplification gives F = A + 𝐵̅ 𝐶

Dr Lachtar 10
 National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 1 Course
Chapitre 3 : Algèbre de Boole
Example: table with 4 variables:

Case of a function not completely defined

Let's look at the following example:
A security lock opens using four keys A, B, C D. The operation of the lock is defined as follows
S(A,B,C,D)= 1 if at least two keys are used
S(A,B,C,D)= 0 Otherwise

Keys A and D cannot be used at the same time.

Note that if key A and D are used at the same time the state of the system is not determined.
These cases are called impossible or forbidden cases. How to represent these cases in the truth table?
For impossible or prohibited cases, you must put an X in the Truth Table and the Karnaugh table
The simplification rules for these cases are to use the X in groupings with 1 by taking them for 1 or in groupings
with 0 by taking them for 0 but you should not take groupings formed only of X.

The previous example gives us

Dr Lachtar 11