Boolean algebra cheat sheet
I saw a lecture on Youtube about Digital Circuit Design from The University of New South Wales, Australia. It is mostly about Boolean algebra. Even though I am familiar with the basics, it contains enough I don’t know. So here’s my small cheat sheet.
Precedence (from highest to lowest)
() (grouping, parenthesis) * (logical and) + (logical or) ' (logical not)
X + 0 = X X * 1 = X
X + 1 = 1 X * 0 = 0
X + X = X X * X = X
X + X' = 1 X * X' = 0
X'' = X
X + Y = Y + X X * Y = Y * X
X + (Y + Z) = (X + Y) + Z X * (Y * Z) = (X * Y) * Z
X * (Y + Z) = X * Y + X * Z X + Y * Z = (X + Y) * (X + Z)
(X + Y)' = X' * Y' (X * Y)' = X' + Y'
0 <-> 1 + <-> *
If you prove a theorem, its dual theorem (replacing 0 with 1, + with *, and vice versa) is also true.
X + X * Y = X X * (X + Y) = X
X * Y + X * Y' = X (X + Y) * (X + Y') = X
X + X' * Y = X + Y X * (X' + Y) = X * Y
X * Y + X' * Z + Y * Z = X * Y + X' * Z (X + Y) * (X' + Z) * (Y + Z) = (X + Y) * (X' + Z)
Proving a theorem with perfect induction just means, spell out each side of an equation in a truth table and compare the results. If the results match, the theorem is valid.