Boolean Algebra

Boolean Algebra is about true and false and logic.

Not

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

And

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

Example: If we cut the grass and wash the car we get ice cream!

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

Or

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

Example: If we cut the grass or wash the car we get ice cream!

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.

Simplicity!

So we only have two possible values:

And only three basic operations:

We can combine them to work out logical things. That's it.

And, Or, ...

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:

Notation

But there are different ways of writing the same thing!

Here are different ways to write "not A":

A = ¬A = ~A = 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 (eXclusive Or) ⊕

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).

Equivalence ≡

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.

Implication →

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

Example: Guard "A" checks your ticket "B"

  • Without the Guard you can get in any time
  • With the Guard you need a ticket to get in

So you can get in except when there is a Guard and you do not have a ticket.


All Together Now

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.

Venn

This is how a Venn Diagram relates to a truth table:

venn parts
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:

venn and
venn or
venn xor
venn equiv
venn imply

Laws

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

Example: Boys' under-15 sprint.

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

Example: free burgers for students, parents or teachers!

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:

A = A

dog does not want brocolli

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
AB = A · B

Let us look at each in turn:

A · B = A + B
"not x and not y = not (x or y)"

Example: Small · Blue = Small + Blue

De Morgan and example

Example: "I don't want mayo and I don't want ham"

Is the same as "I don't want (mayo or ham)"

And the other De Morgan rule:

AB = A · B
"not x or not y = not (x and y)"

Example: SmallBlue = Small · Blue

De Morgan or example

Example: "I don't want mayo or I don't want ham"

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.

Example: Salad

You are making a salad. Your friend says "I only want what is not green or not small". What?

Let's decode that:

GreenSmall = Green · Small

which is actually the same as "not (green and small)"

In other words: not the olives.


Chaining

A series of "and"s compared to a series of "or"s"