# MandysNotes

## Boolean Algebra

### Sets and Subsets

By

Let C be the set of all possible animals.

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

### Disjunction and Conjunction

By

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.

### Negation

By

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$

### Implication

By

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

### Equivalence

By

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.

### Xor: Exclusive Or

By

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]$

### Nand

By

The negation of the set (A and B):

$\lnot \left( A \cap B \right)$

is called A nand B.

### Truth Values

By

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:

### Truth Values for Disjunction

By

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.

### Truth Values for Conjunction

By

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

By

Truth values for negation are very simple:

If $$A$$ is true, then $$\lnot A$$ is false.

### Tautology

By

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.

### Truth Values for Implication

By

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

### Table of Truth Values

By

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