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

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

A · A = A

A ＋ A = A

A ·

A ＋ = true

＋ =

Let us look at each in turn:

*"not x and not y = not (x or y)"*

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

"not x or not y = not (x and y)"

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

＋ =

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