## Boolean Algebra

Let **C** be the set of all possible animals.

Let **A **be the subset of **C** that consists of all duck-billed animals.

Let **B** be the subset of **C** that consists of all mammals.

We illustrate these sets in the following diagram:

Now suppose we consider only animals that are either duck-billed, or are mammals.

This is the set "**A** or **B**," the disjunction of **A** and **B**, written as:

\[ A \cup B,\]

and illustrated in the following diagram:

This set, \( A \cup B,\) contains ducklings, and rabbits, and platypuses.

Suppose that the only information you have about a certain animal is that:

"This animal does not have a duck bill."

If **A** is the set of animals that have a duck bill, and **C** is the set of all animals, then the set of all animals that do not have a duck bill is the negation of **A** (with respect to **C**).

This is the set "not **A**," written as:

\[ \lnot A \]

Suppose we are looking for an animal, but all we know about it is that it either does not have a duck bill, or it is a mammal.

We write this as

"(not **A**) or **B**"

\[ = \left( \lnot A \right) \cup B\]

\[ = A \rightarrow B.\]

Now suppose that we know that **A** implies **B**, and that **B** implies** A**.

In symbols this is:

\[ \left( A \rightarrow B \right) \cap \left( B \rightarrow A \right)\]

\[ = \left( \left( \lnot A \right) \cup B \right) \cap \left( \left( \lnot B \right) \cup A \right)\]

\[ A \leftrightarrow B.\]

In this case we say that **A** is **equivalent** to **B**.

This relation is symmetric, so B is also **equivalent** to **A**.

If all we know is that **A** is not equivalent to **B**, we can write this as:

\[ \lnot \left( A \leftrightarrow B \right)\]

\[ = \lnot \left[ \left( \left( \lnot A \right) \cup B \right) \cap \left( \left( \lnot B \right) \cup A \right) \right] \]

The negation of the set (**A** and **B**):

\[ \lnot \left( A \cap B \right)\]

is called **A nand B**.

Suppose that you are playing a geussing game with a friend. You have both agreed that you will guess an animal.

Your friend thinks of an animal and you try to guess what it is.

Let's assume, for the sake of this lesson, that your friend always tells the truth.

He tells you that the animal that he is thinking of is a duck-billed animal.

If we call the set of all animals **C**, and the set of all duck-billed animals **A**, then you friend has told you that the animal he is thinking of is in **A**.

If x is the unkown animal, then the statement:

"x is a duck-billed animal"

is true.

That is: A is true.

We represent this fact graphically thus:

Suppose your friend tells you that he is thinking of an animal and that this animal is either duck-billed, or a mammal.

In other words he is telling you that \( A \cup B \) is true.

Assume that your friend is telling the truth.

He is telling you that whatever animal he is thinking of, it will be somewhere in the green area in the figure below.

Suppose that your firend is thinking of an animal, and you guess that he is thinking of a platypus.

You say:

"The animal is both duck-billed and a mammal."

In other words, you are saying that \( A \cap B\) is true.

You are saying that the animal will be in the green section of the figure below.

Truth values for negation are very simple:

If \(A\) is true, then \( \lnot A\) is false.

Imagine your friend tells you that the animal he is thinking of is either duck-billed or not duck-billed.

In other words, he is telling you that either \(A\) is true, or \( \lnot A\) is true.

Equivalently he is telling you that the statement:

\[ A \cup \lnot A\]

is true.

This is not very helpful in geussing which animal he is thinking of, but it does have the property of always being true.

In other words, the statement

\[ A \cup \lnot A\]

is true if \(A\) is true (and hence \(\lnot A\) is false);

it is also true if \(A\) is false (and hence \(\lnot A \) is true).

Such a statement is called a **tautology**.

Suppose your friend tells you:

"If the animal I am thinking of is duck-billed, then it is also a mammal."

Assume that he is telling you the truth (for now).

He is telling you that the statement:

\[ A \to B \]

is true.

Logically, this is the same as saying that the statement:

\[ ( \lnot A) \cup B\]

is true.

That is, the animal must be somewhere in the green area in the figure below, and cannot be in the red area.

Here is a table with truth values for various binary relations on Boolean algebras.