Properties of Boolean algebra
Boolean algebra on {0, 1}: sum, product, complement, its laws (distributivity, neutral and absorbing elements, idempotence, complementation, absorption, De Morgan, duality) and algebraic simplification.
- 24 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- Understand
A few cards from the deck
Boolean algebra: what is it?
Show the answer
A structure on {0, 1} equipped with sum (+), product (·) and complement (written ā or ¬a), obeying a fixed set of laws.
Here 1 + 1 = 1, not 2: the sum is "or" and the product is "and". Everything can be checked by trying the values 0 and 1.
What is a·b + a·b̄?
aa·b1b
Show the answer
aFactor out a: a·(b + b̄) = a·1 = a. Complementation b + b̄ = 1 makes b vanish.
De Morgan's laws: ¬(a + b) = … and ¬(a · b) = ….
Show the answer
De Morgan's laws: ¬(a + b) = ā · b̄ and ¬(a · b) = ā + b̄.
The complement swaps sum and product while complementing each variable. Two lines of a truth table verify them.
Absorbing element: what is it?
Show the answer
A value that forces the result whatever the other operand: 1 for the sum (a + 1 = 1), 0 for the product (a · 0 = 0).
Not to be confused with the neutral element, which leaves a unchanged: 0 for the sum (a + 0 = a), 1 for the product (a · 1 = a).
How do we show that (a + b)·(a + c) = a + b·c?
- Expand, then the cross terms cancel by complementation (a·ā = 0)
- Expand, then a·a = a and a·(1 + b + c) = a absorb the cross terms
- Expand as in arithmetic, then a + a = 2a simplifies
- Set every variable to 1 and observe that both sides equal 1
Show the answer
Expand, then a·a = a and a·(1 + b + c) = a absorb the cross terms
(a + b)·(a + c) = a + a·c + a·b + b·c = a·(1 + c + b) + b·c = a + b·c. No complement appears, 2a does not exist here, and a single row of the table proves nothing: all eight would be needed.