Discrete Math 05
What this is
Axioms
Today’s 2-value Boolean Algebra
menu: Boolean Algebra Laws
Boolean Boolean Functions
Algebra Canonic Forms & Standard Form
Applications in digital system
This is the formalized form of Proposition
Logic
Unlike Propositions, this uses no real-
What the based examples
junk it is We also simplify things using equivalence
principles to just the big three
• AND, OR, NOT
We use 0 and 1 in place of F and T (but
the operation is similar)
Let’s have a set B with two binary
operators (in this case, AND and OR), one
Boolean unary operator (NOT), and two constants
(0 and 1)
Algebra
Definition This set B will form a Boolean Algebra if
these axioms apply:
and
Axioms
• Identity
• Commutative
• Distributive
• Complement
Recall propositional logic, is same deal
Two- We can prove it with similar strategy aka
valued truth table
Boolean We can also expand this two-value
algebra into any value
Algebra Two Boolean expression is the equivalent
if they share the same value configuration
• Kinda like truth table, honest
• We can easily form the dual of any Boolean
Duality expression by doing the following:
• Swap add to multiply (and vice versa)
Principles • Swap 0 to 1 (and vice versa)
• Leave complements alone.
Identity
Idempotency
Complementary
Laws of Dominance
Involution
Boolean Absorption
Commutative
Algebra Associative
Distributive
DeMorgan
0/1 Law
Yes, bulk of this topic is very similar
to the propositional logic from
earlier this semester
Intermezzo
: This will apply to electronic
circuitry (no, not electrical as in
your home wall, but rather
electronic aka the ones hiding
inside your phone or laptop)
We can map Boolean function from an
ordered n-tuple to one value
Boolean Let us contemplate a handful of examples
Function
here (kinda hard to explain without example)
Filling the table of Boolean function is almost
identical to those in propositional logic, but
we need to do it the other way (fill with
zeroes first then ones)
Yes, you can do that
• The big three stays: Sums, Products, and Complements
Boolean As normal: sums would equal to OR, product equal to AND,
complement would equal to NOT
functions By the way, you can simplify this functions like you would in OG
Boolean functions using the Starting XI Boolean Algebra Laws
Operation Sums and Products are straightforward (simplification will be
covered later)
Complements, you have options: DeMorgan expanded or
Dualism
Before entering, we have this “term” thingy, basically each part
of the function is a “term”
This term must contain either (all products OR all sums) of
variables aka “literals”
Canonic In canonic form, each term MUST contain all variables, with or
without the complement
Form There are two kinds of terms
• Minterm (all products)
• Maxterm (all sums)
Remember that Boolean Functions has its dual? There is similar
terminology here: Sum-of-Products alongside Products-of-Sums
You can also convert the canonic form terms from
with variables to indexed minterm or maxterm
Canonic Kinda hard to do it without proper board…
Form part Here’s the gist:
Zwei • For minterms, zeroes get complement, ones go without
• For maxterms, the other way around
You can also switch across canonic forms (SOP
and POS)
The simplified canonic forms, basically
This form is designed for the
implementation in digital circuitry
Standard • Since you lot don’t get Digital Systems, this is
basically the fundamentals of what our computer is
Form made of
Standard forms contain two shapes: SOP
and POS
Unlike in canonic form, this form don’t
need complete literals
Switching Network
Boolean
Algebra Electronic Circuitry
Application • This is Digital System,
basically
Algebraically
Simplificatio
n of Boolean K-Map
Function
Quine-McClusky
Algorithm
Algebraic Boolean Function Simplification
• You use the Starting XI with some math prowess to do the job
• Yes, you need your math prowess back in high school calculus
• Inexact science (more like art of mathematical problem solving)
K-Map
• Officially, is called Karnaugh Map
• Made by someone named Maurice Karnaugh
• This uses some form of grid with some conditions
• Neighboring squares must be different by one bit (no more, no less)
• Generally, we talk about minterms in K-Map
• You can, THEORETICALLY, go YOLO and use arbitrary amount of variable here,
but you’ll fry your brain above 4, maybe 5 variables
• Some fun stuff:
• you can also contemplate overflow (yes, roll your map)
• There are also don’t care situation (which you may use, may not)
• The solution is not unique
Quine-McClusky Algorithm
• Is a step-by-step process (what an algorithm is, duh)
• This will involve some form of minterm combining if they’re similar
enough
• This is your reading assignment
• I dare you to implement this!