4.3 : Complex Expressions
Now that we know our basic operators, we can form much larger expressions. We use larger expressions to do more math and create processors like the ones in your computer. But how do we evaluate these expressions?
(P ∨ Q)' ∧ (R ∧ (P' ∨ Q))
We have two options. In both options, we're going to build a truth table, but we're going to do it in different ways.
Option A
We can plug and chug. For each row of the truth table, we can plug in values for
P, Q, and R and simplify.
(P ∨ Q)' ∧ (R ∧ (P' ∨ Q)) |
|
(0 ∨ 0)' ∧ (0 ∧ (0' ∨ 0)) |
|
(0)' ∧ (0 ∧ (1 ∨ 0)) |
|
1 ∧ (0 ∧ (1)) |
|
1 ∧ 0 |
|
0 |
Then repeat for each row of the truth table
Option B
We break each expression into smaller expressions and add columns to our
truth table.
In the above expression, we cannot evaluate (P ∨ Q)' without
first evalulating P ∨ Q.
To make these operations easier, we add a column for P ∨ Q to
our truth table and find it's value for each row.
Now, when we add (P ∨ Q)', instead of needed to repeform the OR
calculation, we can just NOT the previous column.
We continue doing this for all of the parts of the expression and build our way
up:
| Inputs | Intermediate Steps | Output | |||||||
|---|---|---|---|---|---|---|---|---|---|
| P | Q | R | P ∨ Q | (P ∨ Q)' | P' | P' ∨ Q | R ∧ (P' ∨ Q) | (P ∨ Q)' ∧ (R ∧ (P' ∨ Q)) | |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
Simplifying Expressions
When we have these really long boolean expressions, they can get a little unwieldy. There are ways to simplify boolean expressions, similar to the ways we simplify algebraic expressions with the associative, commutative, and distributive properties. Note: I switched up my notation between sections. Sorry not sorry
| AND | OR | |
|---|---|---|
| Identity | 1a ≡ a |
0 + a ≡ a |
| Null Elements | 0a ≡ 0 |
1 + a ≡ 1 |
| Complement | aa' ≡ 0 |
a + a' ≡ 1 |
| Indempotent | aa ≡ a |
a + a ≡ a |
| Commutative | ab ≡ ba |
a + b ≡ b + a |
| Associative | (ab)c ≡ a(bc) |
(a + b) + c ≡ a + (b + c) |
| Distributive | a(b + c) ≡ ab + ac |
a + (bc) ≡ (a + b)(a + c) |
| Absorption | a(a + b) ≡ a |
a + ab ≡ a |
| De Morgan's Law | (ab)' ≡ a' + b' |
(a + b)' ≡ a'b' |
| Involution | (a')' ≡ a |
|
This may look extremely overwhelming at first, but I promise, it's not that bad. A lot of these are more intuitive than you'd think. Let's look at the truth tables for the identities:
| a | 1 | 1a | |
|---|---|---|---|
| 0 | 1 | 0 | |
| 1 | 1 | 1 |
| a | 1 | 0 + a | |
|---|---|---|---|
| 0 | 0 | 0 | |
| 1 | 0 | 1 |
As you can see, after both operations, our output is the same as our a input.
Go through the truth tables for the rest of these properties.
They're pretty neat.
Let's actually apply these rules and see them in action. Remember our really nasty boolean expression at the top? Let's see if we can make it a little less nasty with some simplification rules. First, let's fix that notation up:
(P ∨ Q)' ∧ (R ∧ (P' ∨ Q)) --> (P + Q)'(R(P' + Q))
Much better, let's see what we can do here:
| De Morgan's Law | (P + Q)'(R(P' + Q)) |
(P'Q')(R(P' + Q)) |
|---|---|---|
| Distributive AND | (P'Q')(R(P' + Q)) |
(P'Q')(RP' + RQ) |
| Distributive AND | (P'Q')(RP' + RQ) |
P'Q'RP' + P'Q'RQ |
| Commutative AND | P'Q'RP' + P'Q'RQ |
P'P'Q'R + P'Q'RQ |
| Indempotent AND | P'P'Q'R + P'Q'RQ |
P'Q'R + P'Q'RQ |
| Commutative AND | P'Q'R + P'Q'RQ |
P'Q'R + P'Q'QR |
| Complement AND | P'Q'R + P'Q'QR |
P'Q'R + P'0R |
| Null Elements AND | P'Q'R + P'0R |
P'Q'R + 0 |
| Identity OR | P'Q'R + 0 |
P'Q'R |
Well that's much easier to read, but how can we be sure that P'Q'R is
actually equivalent to (P + Q)'(R(P' + Q))?
With a truth table of course!
| P | Q | R | (P + Q)'(R(P' + Q)) | P'Q'R | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 1 | 1 | |
| 0 | 1 | 0 | 0 | 0 | |
| 0 | 1 | 1 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 0 |
Sum of Min Terms
You may find yourself thinking "Hmmm, I know how to turn an expression into a
truth table, but what if I have a truth table? How do I get an expression from
it?"
Well I'm glad you let me create hypothetical questions for you asked
Let's look at this completely random truth table:
| x | y | o | |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 |
You may recognize this as XOR, but as we covered before, XOR is a derived gate,
its a logic gate created by combining our basic AND, OR, and NOT operators.
How can we use this truth table to figure out how to compute o with only AND,
OR, and NOT gates?
We'll use a sum of min-terms.
A sum of min-terms is fairly self explanatory once you understand what it is.
We're going to find all the smallest (minimum) terms needed to create the
expression and use an OR (+) to combine them.
So how do we actually do this?
First, identify your true rows:
| x | y | o | |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 0 |
We'll notice o is true in two situations: when x=0,y=1 and when x=1,y=0.
Let's look at x=0,y=1 first.
I want to write an expression that is true for only this one case and false
for all other combinations.
What boolean operator is true in only one row?
If you thought AND, you're correct.
x AND y is only true when x=1,y=1.
However, we want an expression that's true only when x=0,y=1.
To get this, we'll simply apply a NOT to x to get:
| x | y | x'y | |
|---|---|---|---|
| 0 | 0 | 0 | |
| 0 | 1 | 1 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
Now we've isolated one of the true rows. We can apply this same concept to our
x=1,y=0 row to get xy'.
This gives us two min-terms: x'y and xy'.
We can now use an OR to combine these to get the resulting sum of min-terms
x'y + xy'.
Don't believe me?
Let's look at the truth table:
| x | y | x'y | xy' | o = x'y + xy' | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 1 | 0 | 1 | |
| 1 | 0 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 0 | 0 |
And there we go! We got the exact same thing we started with! This works for boolean expressions with more variables too. Later, you'll see the full adder which takes in three inputs. Once you've read that section, try to make a sum of min-terms for its truth table. Come back here to verify your answer:
Carry: x'yc + xy'c + xyc' + xyc
Sum: x'y'c + x'yc' + xy'c' + xyc