Boolean Algebra
Boolean algebra, named for the 19th century English mathematician George Boole, is a branch of algebra where we use only two values. For our purposes, these are HIGH and LOW or 1 and 0. These are often also denoted as TRUE and FALSE or \top and \bot.
We have previously looked at some basics, and we wil now see how we can use some rules of algebra to simplify things.
Some Notation:
We will be treating our inputs and outputs as variables: x, y, z, a, b, c etc.
Each variable can take a value of 1 or 0.
We will represent each gate with a symbol. a EQUALS b can be denoted a \equiv b. Additionally:
- NOT a \equiv \bar a
- a AND b \equiv a \cdot b \equiv ab
- a OR b \equiv a + b
- a XOR b \equiv a \oplus b
- a IMPLIES b \equiv a \rightarrow b
This will make it easier to represent more complicated expressions:
- p \rightarrow q \equiv \overline{p \bar q}
- x \oplus y \equiv x \bar y + \bar x y
Algebraic Identities
For each of the following, predict what the output will be. Then, build and verify each circuit.
Note that these exercises are all about simplifying circuits. We looked at ways to create a circuit given a truth table in the last exercise, and now we can simplify the circuits we made.
The following two exercises are about what are known as de Morgan's laws:
