## Boolean Algebra and Operators

Boolean algebra is a branch of algebra where the values of variables can only be `true`

or `false`

(often denoted by `1`

and `0`

respectfully). We use boolean algebra in circuits, general two-valued logic (such as in mathematics), and boolean operations.

There are multiple operations in boolean algebra, but the ones we will focus on are `AND`

and `OR`

. We denote `AND`

through multiplication (ex: `AB`

) and we denote `OR`

through addition (ex: `A+B`

). These operations follow the commutative property, meaning that the order in which we place the operands does not matter. We also have `NOT`

, denoted by `'`

operator, which flips the sign, for example `A'`

.

## Truth Tables

Whenever we have a boolean expression, we can express it as a function. Similar to `F(x)`

we can express a two variable function: `F(AB)`

, where we can say our domain is `{A,B}`

. Since our input values can only be `true`

or `false`

, we can create a truth table that will show all possible cases with their inputs to the function and the result. Let's take a look at a simple two variable expression, and see how the logic gates `AND`

and `OR`

work.

For example, let's take the equation `F(AB) = AB`

and generate the truth table:

F(AB) | A | B |
---|---|---|

0 | 0 | 0 |

0 | 0 | 1 |

0 | 1 | 0 |

1 | 1 | 1 |

We can also take the equation `F(AB) = A+B`

and generate the truth table:

F(A+B) | A | B |
---|---|---|

0 | 0 | 0 |

1 | 0 | 1 |

1 | 1 | 0 |

1 | 1 | 1 |

Truth tables are important because we can easily evaluate for the behavior of a function. For user input, it is easier to input truth tables because we can specify cases such as `Don't Cares`

, which will be discussed later on.

## Sum of Product Expressions (SOP)

Let's consider a more complicated expression `F(ABCD)= AB'C+BD+CD+D`

and generate its truth table:

F(AB'C+BD+CD+D) | A | B | C | D |
---|---|---|---|---|

0 | 0 | 0 | 0 | 0 |

1 | 0 | 0 | 0 | 1 |

0 | 0 | 0 | 1 | 0 |

1 | 0 | 0 | 1 | 1 |

0 | 0 | 1 | 0 | 0 |

1 | 0 | 1 | 0 | 1 |

0 | 0 | 1 | 1 | 0 |

1 | 0 | 1 | 1 | 1 |

0 | 1 | 0 | 0 | 0 |

1 | 1 | 0 | 0 | 1 |

0 | 1 | 0 | 1 | 0 |

1 | 1 | 0 | 1 | 1 |

1 | 1 | 1 | 0 | 0 |

1 | 1 | 1 | 0 | 1 |

0 | 1 | 1 | 1 | 0 |

1 | 1 | 1 | 1 | 1 |

This example was definately more involved than the previous expressions. An interesting observation is that we are doing a sum of product evaluation, that is, `AB'C+BD+CD+D`

is a sum of products. The significance of a sum of product is that when we are doing `+`

we are in fact invoking the `OR`

operator.

Moreover, the `OR`

operator returns `true`

so long as any one of its arguements returns `true`

. Therefore, if *any* of the terms in the sum of product (SOP) expressions is `true`

, then we know that the final expression is `true`

for certain.

## Example Algebraic Simplification

Let's simplify our expression from the previous truth table example. We can apply ordinary algebra tricks such as factoring. Remember that the `+`

operator invokes the `OR`

gate, and that `true or x`

always returns `true`

regardless of `x`

(as shown in our first truth table).

```
AB'C+BD+CD+D // Initial expression
AB'C+BD+D(C+1) // Factor out a D
AB'C+BD+D // Since (C+1) is always true, as C OR true is always true
AB'C+D(B+1) // Factor out a D again
AB'C+D // Since (B+1) is always true, as B OR true is always true
=AB'C+D // Final expression
```

As an exercise to the reader, complete the truth table to show that they are logically equivalent.

## Undefined Input & Don't Cares

The definition of a "Don't care" is a combination of input values that is not known, and could be either `0`

or `1`

. For the purposes of variable simplification, we would choose the greedy approach of picking between {`0`

, `1`

} such that the simplified expression has less terms.

Let's consider the following truth-table:

F(AB) | A | B |
---|---|---|

1 | 0 | 0 |

1 | 0 | 1 |

? | 1 | 0 |

1 | 1 | 1 |

We observe that we have a *Don't care*. Let's observe the differences in cases for `F(1,0)`

:

```
Case #1: F(1, 0) = 0
=> F(AB) = A'B' + A'B + AB
Case #2: F(1, 0) = 1
=> F(AB) = A'B' + A'B + AB' + AB
Simplifying the cases...
F(AB) = A'B' + A'B + AB
= A'(B' + B) + AB
= A' + AB
F(AB) = A'B' + A'B + AB' + AB
= A'(B' + B) + A (B' + B)
= A' + A
= 1
```

We can clearly see, if we set `F(1, 0) = 1`

, we get a true value for any input. Therefore, for the purposes of variable simplification, we can simply let `F(1, 0) = 1`

thus implying `F(AB) = 1`

.

## Additional Logic Gates

So far we covered the `NOT`

unary operator, in addition to the binary operators `OR`

and `AND`

.