THE UNIVERSITY OF THE SOUTH PACIFIC

School of Information Technology, Engineering, Mathematics, and

Physics

EE222 - Digital Logic Design

Lab Report 4
Simple Boolean Function Implementation

Submitted By:

Naayaab Bin Sarfraaz – S11220096

Kaushal Kelvin Prasad – S11221044

Session: Friday 9am to 12am (ICT LAB)

Aim:
The aim of the lab was to design, connect and test a 3-bit Majority Logic Circuit
and prove the Simplification Theorem.
Introduction:
The concept of majority logic circuits aims to determine the most common input
amongst a range of binary inputs. Three binary inputs are evaluated in a 3-bit
majority logic circuit, which outputs a value according to whether the majority of
the inputs are low (0) or high (1). A 3-bit Majority Logic Circuit operates by
comparing the three input values' states to determine the majority input. The
decision determined by majority values will be expressed by high output if two or
more of the inputs are high (1). A low value for two or more inputs will result in a
low output. When there is no majority (all inputs are the same), the output can
either stay in the same condition as before or follow a set convention. Designing a
3-Bit Majority Logic Circuit, variables for input/output, propagation delays, power
consumption, and noise immunity have to be carefully taken into account. To
improve circuit efficiency and streamline the design process, methods including
gate-level optimization, Boolean simplification, and Karnaugh mapping are
implemented. 3-Bit Majority Logic Circuits find applications in fields, including
telecommunications, voting systems, fault-tolerant computing, and error detection
[1].
To be able to operate using true (1) or false (0) data, the Simplification Theorem
(X + X´ Y = X + Y) uses operations like AND, OR, and NOT. One variable (X)
OR with its complement (X´) AND another variable (Y) equates to the variable (X)
AND variable (Y), according to the theorem. This basic concept offers engineers a
systematic approach for reducing complicated logical expressions, making the
creation and evaluation of digital circuits simpler. It explains the inconsistency
present in Boolean logic, whereby a variable's complement acts as a negation
operator (referring to the relationship between a variable and its complement),
converting true to false and vice versa. Utilizing techniques such as Quine-
McCluskey algorithm, Karnaugh maps, and Boolean algebraic manipulation,
engineers can reduce propagation delays, lower the total amount of gates, and
simplify complex logical statements. Logical reduction is a process that increases
circuit efficiency while rendering digital system testing, debugging, and
maintenance easier [2].

1
Equipment:
Breadboard, 1 x Chip (74LS00) Quad 2-input NAND gates, 1 x Chip (74LS20)
Dual 4-input NAND gates, 3 x Resistors (~100 OHMS), 2 x LEDs, 1 x DIP
Switch, +5 Volts Power Supply, 1 x Chip 74LS32 Quad 2-input OR Gate, 1 x Chip
74LS08 Quad 2-input AND Gate and 1 x Chip 74LS04 NOT Gate.
Procedure:
Part I
1. The truth table with inputs A, B, C and output F was filled with 1s where 1
was the majority input and 0 where 0 was the majority input.
2. The sum-of-minterms expression in Σm notation and product-of-maxterms
expression in ΠM notation was written for F from the truth table.
3. The Karnaugh Map for F was filled and the simplified sum-of-product
expression for F was obtained.
4. The logic diagrams for F were drawn using 2-level AND-OR circuit and 2-
level NAND circuit.
5. The wiring plan for implementing the logic diagrams in hardware were
drawn.
6. The 2-level AND-OR circuit and 2-level NAND circuit were constructed in
hardware.
7. Exactly six 2-input NAND gates and one 3-input NAND gate was needed to
turn the 3-bit majority circuit into a 3-bit minority logic circuit (Totally 7
NAND gates).
8. The 3-bit minority logic diagram was drawn.
Part II
X + X´ Y = X + Y
The above Simplification Theorem was proven using Truth Tables (worked by
hand), fundamental Boolean Algebra and implementation of said Theorem in
Software simulations and Hardware experiments.

2
Results and Analysis:
Part I
3-bit Majority logic circuit
A B C F
0 0 0 0 A+B+C
0 0 1 0 A+B+C
0 1 0 0 A+ B+C
0 1 1 1 A BC
1 0 0 0 A +B+C
1 0 1 1 A BC
1 1 0 1 ABC
1 1 1 1 ABC
Table 1 shows the Truth Table for 3-bit majority logic circuit where the input bits
are A, B and C while the output bit is F
The sum of minterms expression in Σm notation for F
F = ∑ m(3 ,5 , 6 , 7)
The product-of-maxterms expression in ΠM notation for F
F = ∏ M (0 ,1 , 2 , 4)
Drawn below is the Karnaugh Map for F, where the circled parts are where the
simplified SOP expression was derived from:
AB AB AB AB

C 0 0 1 0

C 0 1 1 1

Simplified SOP expression for F:

F = AB + BC + AC (2-level AND-OR)
´ + AC (using De-Morgan’s Theorem)
= AB+ BC
= ( AB)(BC )( AC ) (2-level NAND)

3
Figure 1 shows the logic diagram to implement F using 2-level AND-OR circuit

Figure 2 shows the logic diagram to implement F using 2-level NAND circuit

4
Figure 3 shows the 2-level NAND circuit on the breadboard when output, F, is off
(0)

figure 4 shows the 2-level NAND circuit on the breadboard when output, F, is on
(1)
5
3-bit minority logic circuit
A B C F
0 0 0 1 A BC
0 0 1 1 A BC
0 1 0 1 A BC
0 1 1 0 A+ B+C
1 0 0 1 AB C
1 0 1 0 A +B+C
1 1 0 0 A + B+C
1 1 1 0 A + B+C
Table 2 shows the Truth Table for 3-bit minority logic circuit where the input bits
are A, B and C while the output bit is F
The sum of minterms expression in Σm notation for F
F = ∑ m(0 ,1 , 2 , 4)
The product-of-maxterms expression in ΠM notation for F
F = ∏ M (3 ,5 , 6 , 7)
Drawn below is the Karnaugh Map for F, where the circled parts are where the
simplified SOP expression was derived from:
AB AB AB AB
C 1 1 0 1
C 1 0 0 0
Simplified SOP expression for F:
F = A B + BC + AC (2-level AND-OR)
´ + A C (using De-Morgan’s Theorem)
= A B+ BC
= ( A B)(B C )( A C) (2-level NAND)
= ( AB)(BC )( AC ) (Involution Theorem)

6
After observing the SOP, it is concluded that 3 more NAND gates will be needed
(Will be used as Inverters) to turn the 3-bit majority logic circuit into a 3-bit
minority logic circuit.

figure 5 shows logic circuit diagram after turning a 3-bit majority circuit into a 3-
bit minority circuit.
Part II
X Y X´ X´Y X + X´Y X+Y
0 0 1 0 0 0
0 1 1 1 1 1
1 0 0 0 1 1
1 1 0 0 1 1
Table 3 shows the Truth Table (worked by hand) of the Simplification Theorem
Using Fundamental Boolean Algebra:
X + X´Y = (X + X´) · (X + Y) = 1· (X + Y) = X + Y

7
Figure 6 shows implementation of simplification theorem on circuit maker and confirms Truth
Table

Figure 7 shows implementation of simplification theorem on hardware and confirms Truth Table

8
Discussion:
For part I, the output for the 3-bit majority logic circuit, for truth table, was filled
with “1” where there were two or more “1” inputs. The output was “0” when two
or more inputs were also “0”. The third line (starting from 0) and the last three
lines had “1” while the first three lines and the fourth line (starting from 0) had
“0”. The Karnaugh Map for the 3-bit majority circuit had three groups (each of two
bits) which results in a simplified Sum Of Product expression that had no
complementary terms. The 2-level AND-OR circuit had three 2-input AND gates
and one 3-input OR gate while the 2-level NAND circuit had three 2-input NAND
gates and one 3-input NAND gate (totally 4 NAND gates). The wiring plan was
drawn on paper before implementation of the 2-level NAND circuit on Hardware,
where the Vcc was located near the top right and Ground was in the bottom left
(when the notch is oriented vertically on the top of the Chip) and inputs was above
the output. Double bars were added to the simplified SOP and then De-Morgans
Theorem was applied to break the lower bar and change the operation from OR to
AND, hence giving the expression for 2-level NAND circuit [2]. Due to the
components and instructions provided, only the 2-level NAND circuit was
constructed on the breadboard using 4-input NAND gate chip instead of a 3-input
NAND gate chip. The fourth input of the 4-input NAND gate chip was wired with
“1”, since “1” is an identity for NAND gates and would not affect the output. A
common line for Ground and the Voltage source was adjusted on the breadboard
and three common lines were also made for A, B and C. Inputs A, B and C were
then wired into the 2-input NAND gate chip of which the three outputs were wired
into the 4-input NAND gate chip.
For a 3-bit minority circuit, it was observed that the outputs were complementary
of the 3-bit majority circuit (where F was “1” in 3-bit majority circuit, F was “0” in
3-bit minority circuit and vice versa). The Karnaugh Map had same number of
groups (each of 2 bits) with the result also being the complementary version of the
3-bit majority circuit Karnaugh Map. The logic diagram was exactly the same (2-
level NAND circuit) but with three NAND gates used as inverters as shown in
figure 5.

9
For part II, the Simplification Theorem was proven using 2-input Truth Tables as it
showed that the first output will always be “0” while the rest will be “1” for both
sides of the expression. The Simplification Theorem was also proven using
Fundamental Boolean Algebra such as Distributive, Complementary and Identity
Theorems [2]. Simulations were run on Circuit Maker where the left-hand side was
proven using NOT, AND, OR gates and right-hand side was proven using only a
OR gate. A LED was added to the output of the simulation to represent “1” when
it’s on and “0” when off. Then using three 2-input chips for the left-hand side (OR,
AND, NOT) and one 2-input chip for the right-hand side (OR), the theorem was
proven on hardware as well. A resister was added before the LED as the LED
cannot handle too much current. The results matched with no error.

Conclusion:
The aim of the lab was achieved as the students were able to design a 3-bit
majority circuit using Truth tables, Karnaugh Maps and logic diagrams. The
connection and testing of the circuit were also successful and students learnt how
to draw the wiring plan for the circuit, connect with the different types of chips and
improvise with the limited components provided. It was also observed that 3-bit
minority circuits are complementary to 3-bit majority circuits. The Simplification
Theorem was also repeated proven using Truth Tables, three Boolean Algebra
theorems (Distributive, Complementary and Identity) and constructed in Circuit
Maker and on Hardware. Students also learnt how LEDs are used to represent
output and how resisters are utilized to protect the LEDs.

References

[1] A. V. a. A. Kumar, "Design and Analysis of Majority Logic Based Fault Tolerant Systems,"
IEEE Transactions on Computers, vol. 64, no. 1, pp. 120-135, 2015.

[2] M. M. M. a. M. D. Ciletti, Digital Design, Boston: Pearson, 2019.

10
11