Factoring

Quick! what is

8 * 27

We can use the distributive property to break this down into something simpler:

8 * (20 + 7)

160 + 56 = 216

You could have did long multiplication, but the point is that, as long as we retain equality, we can re-arrange pieces of the problem and tease out certain parts, which allows us to more easily reason about a solution, and this is the essence of algebra.

#Boolean Algebra

Boolean algebra has similar properties to regular algebra on numbers, and they are:

Communative Laws:

(x * y) = (y * x)

(x + y) = (y + x)

that is to say, it doesn’t matter how you order the inputs for * (AND) and + (OR)

Associative Laws:

(x * (y * z)) = ((x * y) * z)

(x + (y + z)) = ((x + y) + z)

that is to say the order in which you group operations doesn’t matter for * (AND) and + (OR)

Distributive Laws:

(x * (y + z)) = (x * y) + (x * z)

(x + (y * z)) = (x + y) * (x + z)

The major difference in boolean algebra is that there’s a 2nd distributive law, which says that we can distribute +(or) over *(and), unlike regular algebra.

2 + (3 * 4) = 14

(2 + 3) * (2 + 4) = 30

14 != 30

DeMorgan Laws:

!(x * y) = !(x) + !(y)

!(x + y) = !(x) * !(y)

that is to say we can distribute nots(!). Notice how +(OR) turns into *(AND) and vice versa when a not(!) is distributed.

Idempotence Law:

x + x = x

x * x = x

!x * !x = !x

xy + xy + z = xy + z

In other words, if an expression is just repeating operations on itself, you can simplify it to itself.

#Example Simplification

Simplify the following expression:

!(!x * !(x + y))

Using DeMorgans law on the inner !(x + y), we can turn it into this:

!(!x * !(x + y))

!(!x * (!x * !y))

Now the entire expression is only using *(ANDs), we can use the associative law to group and do the left part first:

!(!x * (!x * !y))

!((!x * !x) * !y)

Apply Idempotence Law (!x * !x) which simplifies to itself

!((!x * !x) * !y)

!(!x * !y)

Apply DeMorgans Law again to distribute the outer ! to get:

!(!x * !y)

Finally:

(x + y)

We took something that initially took 5 logic gates, and simplified it to using only 1.

Another way to simplify is if you were given a truth table, you could pattern match against known logic gates

Further boolean simplification

If you enjoy optimizing for the smallest number of logic gates possible, check out Karnaugh maps. In real life, with real hardware, reducing the amount of logic gates you use could save you money and make things run more efficently, but since we’re going to be using a simulator, you don’t have to worry about it. If you find that you’re having fun optimizing, don’t let me stop you!