# Boolean Algebra

Boolean Algebra is about true and false and logic.

## Not

The simplest thing we can do is to "not" or "invert":

• not true is false
• not false is true

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:

• true
• false

And only three basic operations:

• and
• or
• not

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:

• and: must be both together
• or: can be either or both

## 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:

A B A · B A ＋ B A ⊕ B A ≡ B A → B and or xor equiv imply 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 Diagram Regions
In the outer region both A and B are false

And we can do pretty Venn Diagrams to illustrate and, or, etc:

## 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

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:

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: "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: "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.

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"

• A and B and C and D and ...  must all be true for the result to be true.
• A or B or C or D or ...  must all be false for the result to be false.