Youtube

Simplifying logic gates

Simplifying boolean expressions will help you build more efficient logic gates. In the real world this can save power, money, and make your chips smaller and faster. You will need to use some of these techniques in the upcoming projects.

#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 some, but not all, 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 x or y 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 ALL * (AND) and + (OR) operation groupings.

Distributive Laws

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

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

Example of why addition distributive law doesn’t work for regular numbers

2 + (3 * 4) = 14

If we apply the distributive law in boolean algebra law to real numbers, it won’t work ❌

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

Compliment Law:

!x * x = 0

!x + x = 1

Identity Law

x + 0 = x

x * 1 = x

The identity law says that there are values that leave a Boolean expression unchanged—just like multiplying by 1 or adding 0 in ordinary arithmetic.

#Boolean Laws Cheatsheet


Law	OR Form	AND Form
Identity	`x + 0 = x`	`x * 1 = x`
Domination (Null)	`x + 1 = 1`	`x * 0 = 0`
Idempotent	`x + x = x`	`x * x = x`
Complement	`x + !x = 1`	`x * !x = 0`
Double Complement	`!!x = x`	—
Commutative	`x + y = y + x`	`x * y = y * x`
Associative	`(x + y) + z = x + (y + z)`	`(x * y) * z = x * (y * z)`
Distributive	`x * (y + z) = (x * y) + (x * z)`	`x + (y * z) = (x + y) * (x + z)`
Absorption	`x + (x * y) = x`	`x * (x + y) = x`
De Morgan's	`!(x + y) = !x * !y`	`!(x * y) = !x + !y`

#Derived Boolean Laws Cheatsheet


Derived Law	Expression	Notes
Absorption Variant	`x + (!x * y) = x + y`	Very common simplification
Dual Absorption Variant	`x * (!x + y) = x * y`	Dual of the above
Consensus Theorem	`(x * y) + (!x * z) + (y * z) = (x * y) + (!x * z)`	Eliminates the redundant consensus term
Dual Consensus	`(x + y) * (!x + z) * (y + z) = (x + y) * (!x + z)`	Dual of the Consensus Theorem
Redundancy	`(x * y) + (x * !y) = x`	Factor then apply Complement
Dual Redundancy	`(x + y) * (x + !y) = x`	Dual of Redundancy
Complement Expansion	`x = (x * y) + (x * !y)`	Useful for proofs and canonical forms
Dual Complement Expansion	`x = (x + y) * (x + !y)`	Dual of the above
Exclusive-OR	`x ⊕ y = (!x * y) + (x * !y)`	Definition of XOR
Exclusive-NOR	`x ⊙ y = (x * y) + (!x * !y)`	Definition of XNOR

#Example Simplification

1. Simplify the following expression:

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

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

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

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

3. 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)

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

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

!(!x * !y)

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

!(!x * !y)

6. Finally:

(x + y)

Conclusion:

We went from this:

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

To this:

(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 and recognize it’s an OR gate.

!(!x * !(x + y))
x	y	f (x, y)
0	0	0
0	1	1
1	0	1
1	1	1

#Practice Problem C

The following is a boolean function from the previous section Problem B. Simplify it using the laws above:
f(x, y) = (!x * !y) + (!x * y) + (x * !y)

You are going to have to apply:

deductive reasoning
boolean algebra and the laws
expanding and factoring
combining like terms

Problem C Answer:

Given the original function:

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

Step 1: Factor out common terms
Notice that the first two terms both have !x:
f(x, y) = !x * (!y + y) + (x * !y)

Step 2: Apply Complement Law
!y + y = 1 (Complement Law)
f(x, y) = !x * 1 + (x * !y)
Anything * 1 is itself, so we just get:
f(x, y) = !x + (x * !y)

Step 3: Apply Absorption Law (or Distributive Law)
Using the Identity Law: A + (!A * B) = A + B (this is a form of the Absorption/Reduction law)
f(x, y) = !x + (x * !y)
Turns into:
f(x, y) = !x + !y

Step 4: Apply De Morgan’s Law
f(x, y) = !(x * y)

Answer
!(x * y)

More Practice

I recommend you prompt AI:
Generate me a boolean expression that involves 3 or 4 variables and simplify it using boolean laws, and explain the boolean laws you used.

Further boolean simplification

The future projects will warn you when your boolean expressions aren’t optimized, that’s when you can either use your knowledge of boolean laws, or check out
Karnaugh maps