College of Technology

2nd Semester 2022-2023

MODULE TWO
LESSON 1:
BOOLEAN ALGEBRA THEOREMS AND PROPERTIES

BOOLEAN ALGEBRA, like any deductive mathematical systems, maybe defined with a set of
elements, a set of operators, and a number of unproved axioms or postulates. It is one of the most basic
tools available to a logic designer and is effectively used for simplification of complex logic expression.
Boolean algebra is a system of mathematical logic, introduced by a mathematician George Boole in 1854.
Boolean algebra differs from ordinary algebra and binary number system. It is a binary algebra defined to
perform binary and logical operations

A SET OF ELEMENTS is any collection of objects having a common property. A set with a
denumerable number of elements is specified by braces: A = { 1,2,3,4}./ i.e. the elements of set A are the
numbers 1,2,3 and 4.

BOOLEAN EXPRESSION is combining the variables and operations yields Boolean expressions. A
Boolean expression is a logical statement that is either TRUE or FALSE.

BOOLEAN FUNCTION: A Boolean function typically has one or more input values and yields result,
based on these input value, in (0,1) the range.

A BOOLEAN OPERATOR ca be completely described using a table that list inputs, all possible values
for these inputs, and the resulting values of the operation.

A TRUTH TABLE shows the relationship, in tabular form, between the input values and the result
of a specific Boolean operator or function on the input variables.

Terminologies used in Boolean Algebra:

VARIABLE – different symbols in a Boolean Expression. A symbol which represents arbitrary

elements in Boolean Algebra Y= A + BC. A, B, AND C, are variables.
CONSTANT – it is a fixed value. In an expression Y= A +1, “A” represents a variable and “1” is a fixed
value, which is termed constant.

LITERAL – each occurrence of a variable in a Boolean function either in complemented or

normal form.

Page 41
 College of Technology
2nd Semester 2022-2023

The AND operator is also known as a Boolean Product.

The Boolean expression xy is equivalent to the expression x*y and is read “x and y”. The behavior of
this operator is characterized by the truth table shown in table 3.1.

The OR operator is often referred to as a Boolean sum. The expression x + y is read “x or y”. The
truth table OR is shown in Table 3.2.

Both x and x’ are read as “NOT x”. The truth table for NOT is shown in table 3.3.

Page 42
 College of Technology
2nd Semester 2022-2023

POSTULATES OF BOOLEAN ALGEBRA

1. IDENTITY LAW

First, 0 OR A = A (the sum of “0” and any number or variable is the number or variable itself)

Second, 1 AND A = A (the product of 1 and any number or variable is the number or variable
itself)

2. Commutative Law

Commutative law states that the inter-changing of the order of operands in a Boolean equation does
not change its result.

Page 43
 College of Technology
2nd Semester 2022-2023

3. Associative Law

Associative law of addition states that OR-ing more than two variables i.e. mathematical addition
operation performed on variables will return the same value irrespective of the grouping of variables
in an equation. It involves in swapping of variables in groups.

Associative law of multiplication states that AND-ing more than two variables i.e. mathematical
multiplication operation performed on variables will return the same valueirrespective of the grouping of
variables in an equation.

This law allows the removal of brackets from an expression and regrouping of the
variables.

4. Distributive Law

The multiplication of two variables and adding the result with a variable will result in samevalue as
multiplication of addition of the variable with individual variables.

The addition of two variables and multiplying the result with a variable will result in samevalue as
addition of multiplication of the variable with individual variables.

THEOREMS OF BOOLEAN ALGEBRA

Boolean algebraic theorems are the theorems that are used to change the form of a boolean
expression. Sometimes these theorems are used to minimize the terms of the expression andsometimes
they are used just to transfer the expression from one form to another.

1. Annulment Law

A term AND-ed with a “0” equals 0

A.0=0

A term OR-ed with a “1” will equal 1.

A+1=1

Page 44
 College of Technology
2nd Semester 2022-2023

2. Identity Law

 in this law variable remain unchanged it is ORed with “0’ or ANDed with “1’

A variable OR-ed with 0 is always equal to the variable.

A+0=A

A variable AND-ed with 1 is always equal to the variable.

A.1=A

3. Idempotent Law

A variable OR-ed with itself is always equal to the variable.

A+A=A

A variable AND-ed with itself is always equal to the variable.

A.A=A

4. Complement Law

A variable AND-ed with its complement is always equal to 0

A . A̅ = 0

A variable OR-ed with its complement is always equal to 1.

A + A̅ = 1

5. Commutative Law
 a variable order does not matter in this law

The order in which two variables are AND-ed makes no difference.

A.B=B.A

The order in which two variables are OR’ed makes no difference.

A+B=B+A

Page 45
 College of Technology
2nd Semester 2022-2023

6. Double Negation Law or Involution Law

- a variable with two negation its symbol gets cancelled out and original variable is obtained, i.e.,

Or ((A)’)’=A

7. de Morgan´s Theorem

Complement of a product is equal to the sum of its complement.

(A.B)’ = A’ + B’

Complement of a sum is equal to the

product of the complement.

(A + B)’ = A’.B’

8. Transposition Theorem

This theorem can be used for expressions having two terms, provided that a given variable in one
term has its complement in the other.

ĀX+AX̄ = (A+X)( Ā+ X̄ )
AX+ Ā X̄ = (A+ X̄ )(Ā+X)

9. Eliminating Redunduncy

If a variable X is multipled by an expression containing X and X̄ in addition to other variables,then

all Xs and X̄ s can e replaced with 1s and 0s respectively.

X̄ .f(X,X̄ ,Y,Z) = X̄ .f(0,1,Y,Z)

X̄ +f(X, X̄ ,Y,Z) = X̄ +f(1,0,Y,Z)

Page 46
 College of Technology
2nd Semester 2022-2023

Solved Examples:

Simplify:

Example #1: A . (AB + C) = AAB + AC (A.A) = A (Idempotent law)

= AB + AC
= A (B + C)

Example # 2: Simplify Y = (AB’(C+BD) + A’B’)C

(0)
Y = (AB’.C + AB’.BD + A’B’) C A.A’ = 0 (complement law)
Y = (AB’C + A’B’) C
Y = (AB’C.C + A’B’. C) A.A = A (Idempotent Law)

Page 47
 College of Technology
2nd Semester 2022-2023

LESSON 2: LOGIC GATES

Computers, calculators, and other digital devices are sometimes looked upon by the general public
as being magical. Actually, digital electronics devices are extremely logical in their operation. The basic
building block of any digital circuit is the logic gate.

Logic gates are the heart of digital electronics. A gate is an electronic device which is used to
compute a function on a two valued signal. Logic gates can be constructed by using simple switches,
relays, vacuum tubes, transistors and diodes, or IC’s. The task perform by logic gate is called logic
function. Logic function can be implemented by hardware (logic gates) or by programming devices such
as microcontrollers or computers.

DIGITAL LOGIC LEVELS

A logic level is defined as a specific state or voltage of a signal. We know that 0 and 1 are the two
states of logic gates. The logic levels 0 and 1 are known as LOW and HIGH respectively. In digital
electronics, these binary logic levels play a crucial role in data storage, data transfer.

Generally, these logic levels can be understood as ON and OFF states. As we said earlier, the logic
levels are introduced to the logic gate by the supply voltage. If the supply voltage to thelogic gate is 0 volts,
it refers to Low logic level or OFF state.

TRUTH TABLE

Page 48
 College of Technology
2nd Semester 2022-2023

o Truth tables are used to show the function of a logic gate. Truth tables helps us understand the
behavior of logic gates.
o They show how the input(s) of a logic gate relate to its output(s).
o The gate input(s) are shown in the left column(s) of the table with all the different possibleinput
combinations. This is normally done by making the inputs count up in binary.
o The gate output(s) are shown in the right- hand side column.

LOGIC GATES
THREE BASIC LOGIC GATES

1. Logic AND Gate

 An AND gate is a logic circuit having two or more inputs and one output. AND gate is sometimes
called the “all or nothing gate”. (means you must closed both switches to get the output to light)
 The output of this gate is HIGH only when all inputs are HIGH.
 When one of the inputs of the AND Gate is LOW, then the output of the AND Gate is LOW. In AND
Gate, the output ofattains the state 1 if and only if all the inputs are in state 1.
 “1” closed and “0” is open

Page 49
 College of Technology
2nd Semester 2022-2023

2. Logic OR Gate

 The “OR” gate is sometimes called the “any or all gate” (means that the output will light when either or
both of the input switches are closed but not when both are open.)
 The unique output from OR gate is LOW only when all inputs are LOW.
 The output of the OR Gate is high, when one or more inputs are high. In OR Gate, the output attains
the state 1 if one or more inputs attain the state 1.

3. NOT Gate

 The NOT circuit has only one input and one output.
 The job of NOT circuit (inverter) is to give an output that is not the same as the input.
 The output of the NOT gate is the reverse of the input. When the input of the NOT gate is HIGH then
the output will be low and vice versa. In NOT Gate, the output attains the state 1 if and only if the input
attains the state 0.

Page 50
 College of Technology
2nd Semester 2022-2023

OTHER LOGIC GATES THAT DERIVED FROM THE 3 BASIC GATES

1. NOR Gate

 The NOR Gate is actually a NOT OR Gate. In other words, the output of an OR gate is inverted to
form a NOR gate.
 NOR Gate function is being performed by an OR gate and an inverter..
 The unique output from the NOR gate is a HIGH only when all inputs are LOW.

Page 51
 College of Technology
2nd Semester 2022-2023

2. NAND Gate

 The NAND Gate is a NOT AND, or an inverted AND functions.

 The little invert bubble (small circle) on the right end of the symbol means to invert the output
of AND.
 The truth table for the NAND gate is developed by inverting outputs of the AND Gate.
 The unique output of the NAND function is a LOW output only when all inputs are HIGH.

3. The Exclusive OR Gate – “XOR” gate

Page 52
 College of Technology
2nd Semester 2022-2023

 The exclusive OR Gate is sometimes referred to as the “Odd but not even gate”
 The term “exclusive OR gate is often shortened to “XOR Gate”.
 The unique characteristic of the XOR gate is that it produces a HIGH output only when an
odd number of HIGH inputs are present. (it means If any one of the inputs of this
gate is high, then the output of the XOR Gate will be high. In XOR Gate, the output
attains the state 1 only if one of the inputs is 1)
 The plus(+) sign within the circle is used as the Boolean expression of the XOR gate. The
symbol of the XOR gate is ⨁. This Ex-OR symbol also defines the "direct sum of sub-
objects" expression.

4. The Exclusive NOR Gate - “ XNOR Gate”

The Bar expression tells us

we have inverted the output
of XOR gate.

 The term “exclusive

NOR gate” is often shortened to “XNOR Gate”
 Logic symbol is the XOR symbol with the added invert bubble on the output side.
 Notice that the output of the XNOR gate is the complement of the XOR truth table.
 The unique output of the XNOR gate is LOW only when the odd number of inputs are HIGH
which is the opposite from the XOR gate.

Page 53
 College of Technology
2nd Semester 2022-2023

SUMMARY

Module
3:

Page 54