Boolean Algebra is about true and false and logic.
The simplest thing we can do is to "not" or "invert":
We can write this down in a "truth table" (we use T for true and F for false):
| A | | not A |
|---|---|---|
| F | | T |
| T | | F |
We can "and" two values together. Both must be true for the result to be true:
| A | B | | A and B |
|---|---|---|---|
| F | F | | F |
| F | T | | F |
| T | F | | F |
| T | T | | T |
| cut grass | wash car | | ice cream |
|---|---|---|---|
| F | F | | F |
| F | T | | F |
| T | F | | F |
| T | T | | T |
Only if we do both jobs do we get ice cream
We can "or" two values together. The result is true if either (or both) are true:
| A | B | | A or B |
|---|---|---|---|
| F | F | | F |
| F | T | | T |
| T | F | | T |
| T | T | | T |
| cut grass | wash car | | ice cream |
|---|---|---|---|
| F | F | | F |
| F | T | | T |
| T | F | | T |
| T | T | | T |
In this case we can do either job (or both) to get ice cream. Let's wash the car.
So we only have two possible values:
And only three basic operations:
We can combine them to work out logical things. That's it.
In English we use the words loosely. We say "I like apples and pears", but in Logic that means you like them when they are together!
Remember that Logic says:
But there are different ways of writing the same thing!
Here are different ways to write "not A":
And there are two main ways of writing "and" and "or":
You can choose which style you want by pressing this button:
| and: | · |
| or: | ＋ |
| (A and B) or C: | (A·B) ＋ C |
(Note: "dot plus" style has many similarities to multiply and add, whereas "up down" style has equivalents in set intersection ∩ and union ∪.)
Xor is the same as or except is false when both inputs are true:
| A | B | | A or B | A xor B |
|---|---|---|---|---|
| F | F | | F | F |
| F | T | | T | T |
| T | F | | T | T |
| T | T | | T | F |
We can have either one being true but not both.
Xor is like both your best friends fight. Life is fun with either one, but not both.
Think: "eXclusively yours" (no one else allowed).
Only true when the inputs match (are equivalent):
| A | B | | A ≡ B |
|---|---|---|---|
| F | F | | T |
| F | T | | F |
| T | F | | F |
| T | T | | T |
It is also the opposite of xor.
Is true except when A is true and B is false:
| A | B | | A → B |
|---|---|---|---|
| F | F | | T |
| F | T | | T |
| T | F | | F |
| T | T | | T |
So you can get in except when there is a Guard and you do not have a ticket.
Here they are together:
| | | | and | or | xor | equiv | imply |
| A | B | | A · B | A ＋ B | A ⊕ B | A ≡ B | A → B |
|---|---|---|---|---|---|---|---|
| F | F | | F | F | F | T | T |
| F | T | | F | T | T | F | T |
| T | F | | F | T | T | F | F |
| T | T | | T | T | F | T | T |
There are actually 16 possible combinations, but those are the most important.
This is how a Venn Diagram relates to a truth table:
Venn Diagram Regions
In the outer region both A and B are false
And we can do pretty Venn Diagrams to illustrate and, or, etc:
This is cool: assuming "and is multiply" and "or is add" we find Boolean Algebra shares these Laws of ordinary algebra:
Commutative Laws: we can swap values over in these cases:
A · B = B · A
A ＋ B = B ＋ A
You need to be a boy and under 15:
Boy and Under-15 is the same as Under-15 and Boy
Associative Laws: we can change, or remove, brackets in these cases:
A · (B · C) = (A · B) · C = A · B · C
A ＋ (B ＋ C) = (A ＋ B) ＋ C = A ＋ B ＋ C
These are all the same:
student or (parent or teacher)
(student or parent) or teacher
student or parent or teacher
Distribution of and over or:
A · (B ＋ C) = (A · B) ＋ (A · C)
Identity Laws: we get the original value back in these cases:
A · true = A
A ＋ false = A
Double negation: one "not" cancels another "not" and we get the original value:
Saying "Do NOT not eat!" is the same as saying "Eat!"
The following laws are also true in Boolean Algebra, but not in ordinary algebra:
Distribution of or over and:
A ＋ (B · C) = (A ＋ B) · (A ＋ C)
Absorption Laws: we can "absorb" the term in parentheses in these two cases:
A · (A ＋ B) = A
A ＋ (A · B) = A
Why? Using Identity and Distribution Laws, let us look at the first case:
Start with: A · (A ＋ B) Replace first A with A ＋ false: (A ＋ false) · (A ＋ B) Distribution of or over and: A ＋ (false · B) false · B is false: A ＋ false A ＋ false is A: A Idempotent Laws: we can simplify these cases also:A · A = A
A ＋ A = A
Complement Laws: simplify a value with its inverse in these cases:
A · A = false
A ＋ A = true
De Morgan: a very useful rule, especially when coding:
A · B = A ＋ B
A ＋ B = A · B
Let us look at each in turn:
A · B = A ＋ B
"not x and not y = not (x or y)"
Is the same as "I don't want (mayo or ham)"
And the other De Morgan rule:
A ＋ B = A · B
"not x or not y = not (x and y)"
Is the same as "I don't want (mayo and ham)"
In other words not mayo and ham together, but either on its own is fine.
You are making a salad. Your friend says "I only want what is not green or not small". What?
Let's decode that:
Green ＋ Small = Green · Small
which is actually the same as "not (green and small)"
In other words: not the olives.
A series of "and"s compared to a series of "or"s"
