E2011: Theoretical fundamentals of computer science
Topic 2: Boolean algebra - Exercises
Vlad Popovici, Ph.D.
Fac. of Science - RECETOX
Some useful tools:
Logic.ly: https://logic.ly/demo/ - demo version is enough to try
out some simple designs
LogiSim: http://www.cburch.com/logisim/download.html - a
free, portable (Java) application with many features
Digital: https://github.com/hneemann/Digital - another
educational tool for digital circuits
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises2 / 10
Exercise 1
Show that:
X(X + Y ) = X (law of absorption)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises3 / 10
Exercise 1
Show that:
X(X + Y ) = X (law of absorption)
Proof:
X(X + Y ) = X · X + X · Y
= X + X · Y
= X(1 + Y )
= X
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises3 / 10
Exercise 2
Show that:
XY + YZ + XZ = XY + XZ
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises4 / 10
Exercise 2
Show that:
XY + YZ + XZ = XY + XZ
Proof:
XY + YZ + XZ = XY + (X + X)YZ + XZ
= XY + XYZ + XYZ + XZ
= (XY + XYZ) + (XYZ + XZ)
= XY + XZ
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises4 / 10
Exercise 3
Prove de Morgan’s theorem using truth table.
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises5 / 10
Exercise 4
Using de Morgan’s theorem, expand
X + Y + Z
and construct the corresponding truth table.
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises6 / 10
Exercise 5
Identify the boolean function
corresponding to the
following truth table:
X Y Z W F(X, Y , Z, W )
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises7 / 10
Exercise 5 - cont’d
Function identification:
F(X, Y , Z, W ) = XY ZW + XY ZW + XY ZW + XYZW + XYZW
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises8 / 10
Exercise 6
Simplify previous function.
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises9 / 10
Exercise 6
Simplify previous function.
F(X, Y , Z, W ) = XY ZW + XY ZW + XY ZW + XYZW + XYZW
= XZW (Y + Y ) + XY Z(W + W ) + XYZW
= XZW + XY Z + XYZW
= XY Z + XZ(W + Y W )
= XY Z + XZ(Y + W )
= XY Z + XYZ + XZW
= XY (Z + Z) + XZW
= XY + XZW
= X(Y + ZW )
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises9 / 10
Exercise 7
Design the logic circuits
corresponding to the initial
and simplified forms of the
previous function,
respectively.
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises10 / 10
Exercise 7
Design the logic circuits
corresponding to the initial
and simplified forms of the
previous function,
respectively.
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra - Exercises10 / 10