Boolean algebra &

logic gates.
Boolean algebra
• Contains variables, which take two discrete values (1 or 0).

• Binary logic.
• Consists of binary variables and a set of logical
operations.

• There are three basic logical operations: AND, OR and

NOT.

• Each operation produces a binary result.

 Two-valued Boolean algebra

• A two-valued Boolean algebra is defined

• on a set of two elements, i.e. B = {0,1}
• with rules for the two binary operators “+” and “·”
• The rules are in following table.
• same as the AND, OR and NOT operations.
Postulates
1. Closure: The structure is closed with respect to the two operators
 Inputs and output of each operationis either 1 or 0

2. Identity:
 0 is an identityelementto “+”
 1 is an identityelementto “-”

3. Commutative laws
 𝑥+ 𝑦=𝑦 + 𝑥
 𝑥 .𝑦 = 𝑦 .𝑥

4. Distributive laws
 𝑥 " (𝑦 + 𝑧) = (𝑥 " 𝑦) + (𝑥 " 𝑧)
 𝑥 + (𝑦 " 𝑧) = (𝑥 + 𝑦) " (𝑥 + 𝑧)

5. For every element x є B, there is an element x’ є B

(called complement of x )
 𝑥 + 𝑥’ = 1
 𝑥. 𝑥 ! = 0

6. There exists at least two elements x, y є B such that x ≠ y.

 1 ≠0
Theorems
1. Theorem 1
 𝑥+𝑥 =𝑥
 𝑥. 𝑥 = 𝑥

2. Theorem 2
 𝑥+1 = 1
 𝑥. 0 = 0

3. Theorem 3 (Involution)
 𝑥! ! = 𝑥

4. Theorem 4 (Associative)
 𝑥+ (𝑦 + 𝑧) = (𝑥+ 𝑦) + 𝑧
 𝑥. 𝑦 𝑧 = 𝑥 𝑦 . 𝑧

5. Theorem 5 (DeMorgan)
 (𝑥 + 𝑦)’ = 𝑥!𝑦′ (𝑥 + 𝑦) = 𝑥. 𝑦
 (𝑥𝑦)!= 𝑥! + 𝑦!
𝑥. 𝑦 = 𝑥 + 𝑦
6. Theorem 6 (Absorption)
 𝑥 + 𝑥𝑦 = 𝑥
 𝑥 𝑥+𝑦= 𝑥
Postulates and Theorems
 Logic Gates

Two input AND gate Two input OR gate NOT gate

Three input AND gate Four input OR gate

 Logic Gates

• Logic gates are electronic circuits.

• Operate with one or more input signals and produce an output

signal.

• The input terminal of digital circuits accepts binary signals within

an allowable range.

• Output signal falls within a specified range.

• The intermediate region is crossed only during a state transition.

What is mean by 1 & 0 ?
 Boolean expression

• A Boolean expression is described by an algebraic expression.

𝐹= 𝑥 + 𝑦‘𝑧
• A Boolean expression can also be represented by a truth table.

𝒙 𝒚 𝒛 𝑭𝟏
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
 Gate Level Implementation of Boolean
expression
• A Boolean expression can be represented by a circuit diagram.
• The gate level implementation of the Boolean expression 𝐹( is
given below.

𝐹= 𝑥 + 𝑦‘𝑧
 Gate Level Implementation of Boolean
expression

The Boolean expression F2 dictates the inter connection

of gates in the below logic-circuit diagram.
𝐹2= 𝑥‘𝑦‘𝑧 + 𝑥‘𝑦𝑧 + 𝑥𝑦′

𝐹2 = 𝑥‘𝑦‘𝑧 + 𝑥′𝑦𝑧 + 𝑥𝑦‘

= 𝑥 ‘𝑧 𝑦 ‘ + 𝑦 + 𝑥𝑦‘ = 𝑥 ‘𝑧. 1 + 𝑥𝑦‘ = 𝑥 ‘𝑧 + 𝑥𝑦′
Simplified Boolean expressions
The simplified circuit of F2 is,

𝐹+ = 𝑥‘𝑧 + 𝑥𝑦′
Truth table of Boolean expression

The truth tables of the Boolean expressions F1 and F2 are,

𝐹1 = 𝑥 + 𝑦‘𝑧
𝐹2= 𝑥‘𝑧 + 𝑥𝑦′
Exercise.

1. Simplify the following Boolean functions.

a) 𝑥. (𝑥 ' + 𝑦)
b) 𝑥 + 𝑥 '𝑦
c) (𝑥 + 𝑦)(𝑥 + 𝑦 ' )
d) (𝑥 + 𝑦)(𝑥 ' + 𝑧)(𝑦 + 𝑧)
e) 𝑥 + 𝑦𝑧' + 𝑥𝑦 + 𝑦' 𝑧′

𝑎) 𝑥. 𝑥‘ + 𝑦 = 𝑥. 𝑥‘+ 𝑥. 𝑦 (𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒)
= 0 + 𝑥. 𝑦(𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡)
= 𝑥. 𝑦 (𝑖𝑑𝑒𝑛𝑡𝑖𝑡𝑦)

b) 𝑥 + 𝑥‘𝑦 = 𝑥 + 𝑥‘𝑦
= 𝑥 + 𝑥+ . 𝑥 + 𝑦 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑒
= 1. x + y complement
= x + y (identity)
Canonical and standard forms.

A Boolean expression can be represented in either

normal form (x) or in its complement form (x’).
Minterm or Standard product
• n-variables forming an AND term of 2n possible combinations is called a
minterm or standard product.
• Denoted by 𝑚0 , 𝑚1 , 𝑚2 , … …, 𝑚2𝑛 / 1

Maxterm or Standard sum

• n-variables forming an OR term of 2n possible combinations is called a
maxterm or standard sum.
• Denoted by 𝑀0 , 𝑀1 , 𝑀2 , … …, 𝑀2𝑛 / 1
Minterms and Maxterms.

Minterms and maxterms of three binary variables, x,

y, and z.

Minterms
𝒙 𝒚 𝒛
Term Designation
0 0 0 𝑥*𝑦*𝑧′ 𝑚0
0 0 1 𝑥 * 𝑦* 𝑧 𝑚1
0 1 0 𝑥*𝑦𝑧′ 𝑚2
0 1 1 𝑥*𝑦𝑧 𝑚3
1 0 0 𝑥𝑦′𝑧′ 𝑚4
1 0 1 𝑥𝑦′𝑧 𝑚5
1 1 0 𝑥𝑦𝑧′ 𝑚6
1 1 1 𝑥𝑦𝑧 𝑚7
 Minterms and Maxterms.
Minterms and maxterms of three binary variables, x, y,
and z.
Maxterms
𝒙 𝒚 𝒛
Term Designation
0 0 0 𝑥+𝑦+𝑧 𝑀0
0 0 1 𝑥 + 𝑦 + 𝑧′ 𝑀1
0 1 0 𝑥 + 𝑦* + 𝑧 𝑀2
0 1 1 𝑥 + 𝑦* + 𝑧′ 𝑀3
1 0 0 𝑥* + 𝑦 + 𝑧 𝑀4
1 0 1 𝑥* + 𝑦 + 𝑧′ 𝑀5
1 1 0 𝑥* + 𝑦* + 𝑧 𝑀6
1 1 1 𝑥* + 𝑦* + 𝑧′ 𝑀7
Sum of minterms

• Write the Boolean function F = A + B’C as sum of minterms.

A = A(B + B‘) = AB + AB‘
A = AB(C + C‘) + AB‘(C + C‘)
= ABC + ABC‘ + AB‘C + AB‘C‘
B’C = B’C(A + A’) = AB’C + A’B’C
F = A + B’C
=ABC + ABC‘ + AB‘C + AB‘C‘+AB’C + A’B’C
AB’C appears twice, and according to theorem 1 (x + x = x),
it is possible to remove one of those occurrences.
F = A‘B‘C + AB‘C + AB‘C + ABC‘ + ABC
= m1 + m4 + m5 + m6 + m7
Product of maxterms

• Write the Boolean function F = A + B’C as prod of maxterms.

• To express a Boolean function as a product of maxterms, it
must first be brought into a form of OR terms. This may be
done by using the distributive law, x + yz = (x + y)(x + z).
Then any missing variable x in each OR term is ORed with
xx’
• F = (A + B’ + CC’)(A + C + BB’)
= (A + B’ + C)(A + B’ + C’)(A + B + C)(A + B’ + C)
= (A + B’ + C)(A + B’ + C’)(A + B + C)
Boolean algebra from Truth table

Maxterms

Minterms

𝐹𝐴,𝐵,𝐶 = Σ 1,4,5,6,7 = Π(0,2,3)

Minterms
𝐴+𝐵+𝐶+ 𝐴𝐵+𝐶++ 𝐴𝐵+𝐶 +
𝐹𝐴,𝐵,𝐶 = 𝐴𝐵𝐶+ + 𝐴𝐵𝐶
𝐹𝐴,𝐵,𝐶 = A + B + C (A++ B + C′)(A+ + B + C)
Maxterms
 Design circuit

Sum of Products implementation of a Boolean

expression, F1 using logic gates is given below.

𝐹( = 𝑦) + 𝑥)𝑦𝑧) + 𝑥𝑦
 Design circuit

Product of Sums implementation of a Boolean

expression, F2 using logic gates is given below.

𝐹2 = 𝑥. (𝑦 " + 𝑧)(𝑥 " + 𝑦 + 𝑧)

Different types of gates
 Selection of logic gates
Factors to consider
• Feasibility and cost of a gate.

• Number of inputs of the gate.

• Number of gates driven by the gate.

• Power consumption of the gate.

• Noise margin of the gate.

• Response time of the gate.

• Ability to implement a Boolean expression in alone or conjunction with other
gates.
Some terminologies…

• Fan-out
• Number of standard loads that the output of a typical gate that can drive
without impairing its normal operation.
• Fan-in
• The number of inputs available in a gate.
• Power dissipation
• The power consumed by the gate.
• Propagation delay
• The average transition delay time for a signal to propagate from input to
output.
• Noise margin
• The maximum external noise voltage added to an input signal that does not
cause an undesirable change in the circuit output.
Integrated circuits

• An integrated circuit is fabricated on a die of semiconductor crystal.

• A complex chemical and physical process is used to produce a

semiconductor circuit.

• Various circuits are interconnected inside the chip to create the required
circuit.

• External pins are welded with the circuit, which may range from low
number to several thousands.
 Levels of Integration.

• The complexity of a digital circuit

• measured based on number of logic gates used in a single package.

• Differ from few internal gates to 100k of gates, decided by a

customer reference.

Integrated Circuit Category Internal circuitry

SSI No. of gates < 10
MSI 10 < No. of gates < 1000
LSI Contains processors, memories and PLDs
VLSI Contains large memory arrays and
complex microcomputer chips.
 Digital logic families.
• Digital ICs can be also classified not only by their complexity or
logical operation but also by the specific circuit technology to
which they belong.
• The universal logic gates are NAND, NOR, and Inverter gates.
• Easy to fabricate
Gates in integrated circuits

NOT gate
DL OR Gate
Schematic, and truth table DL OR gate

X Y Z
0 0 0
0 1 1
1 0 1
1 1 1
TTL NOT Gate
Schematic of TTL NOT gate
RTL NOR Gate
Schematic, and truth table RTL NOR gate

X Y Z
0 0 1
0 1 0
1 0 0
1 1 0
TTL NAND Gate
Schematic of TTL NAND gate