ECE 2020 Digital Design
Prof. Matthieu Bloch
Monday August 18, 2025 (v1.0)
Boolean Algebra
- 1854: George Boole creates a two-valued algebraic
system
- 1938: Claude Shannon shows how the binary
properties of electrical switches could perform logic functions
- Boolean algebra differs from elementary algebra
- variables are truth values (true/false or 1/0)
- operators are logical operators, NOT , AND, OR
- What's special about the combination of operators (NOT, AND,
OR)?
Possible Boolean Functions
| \(A\) |
\(B\) |
\(F_0\) |
\(F_1\) |
\(F_2\) |
\(F_3\) |
\(F_4\) |
\(F_5\) |
\(F_6\) |
\(F_7\) |
\(F_8\) |
\(F_9\) |
\(F_{10}\) |
\(F_{11}\) |
\(F_{12}\) |
\(F_{13}\) |
\(F_{14}\) |
\(F_{15}\) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Operator precedence
- Operator precedence: there is a rule of precedence
(similar to our usual rules)
- Example: \[
F =
(A\overline{(C+\overline{B}D)}+\overline{B\overline{C}})\overline{E}
\]
Evaluation of functions
- Example 1: evaluate \(F=C+\overline{C}B+B\overline{A}\) with
\(A=1\), \(B-0\), \(C=1\)
- Example 2: evaluate \(F=D(B\overline{C}A+\overline{(A\overline{B}+C)}+C)\)
with \(A=0, B=0, C=1, D=1\)
Axiomatic construction of Boolean algebra
- Objective: define rules to manipulate functions and
variables without directly evaluating
- Axioms:
- If \(X\neq 1\) then \(X=0\) and vice versa
- Tables of NOT, AND, OR
- We can now prove a lot of "theorems" that make the manipulation of
boolean functions easier
Simplifications of functions
- Example 1: \(F =
BC+B\overline{C} + BA\)
- Example 2: \(F=A +
\overline{A}B+\overline{A}\overline{B}C +
\overline{A}\overline{B}\overline{C}D+\overline{A}\overline{B}\overline{C}\overline{D}E\)
- Example 3: Show that \(\overline{A(\overline{B}\overline{C}+BC)}=\overline{A}+(B+C)(\overline{B}+\overline{C})\)
Until next time
- To be effectively prepared for Thursday August 21, 2025, you
should:
- Read textbook Sections 1.2, 1.4, 3.0-3.1 (we have not covered
everything yet)
- Read your notes and review the examples
- Next time
- We will introduce standard forms of functions as
"products of sum" and "sum of products"
- We might have time to introduce devices that
implement boolean functions