Boolean Algebra

Properties

For all , we have:

Property	Explanation
	closed under addition
	closed under multiplication
	additive identity
	multiplicative identity
	addition is commutative
	multiplication is commutative
	addition is distributive
	multiplication is distributive
	addition is associative
	multiplication is associative
For all , there exists such that	additive inverse
For all . there exists such that	multiplicative inverse
There exists such that	at least 2 unique elements

(same table as Logical Operators#Properties, but with different notation)

De Morgan's law

De Morgan's Laws

Law

When expanding negation, the elements take the negation, and conjunction changes to disjunction and vice versa

For all ,

Remark

De Morgan's Laws work for an arbitrary number of variables:

absorption law

Absorption Law

Law

For all ,

Proof

Proof of (1):

Proof for (2):

partial distributive law

Partial Distributive Law

Law

For all ,

Intuition

This is just distributive law, but the first term gets lost

Proof

Proof for (1):

Proof (2):

combining law

Combining Law

Law

For all

Proof

Proof for (1):

Proof for (2):

consensus law

Consensus Law

Law

For all

Proof

Proof for (1):

Proof for (2):

Tip

A good way to remember this law is, if you can rearrange the elements into a "chain" with the first and last variables being complements of each other, then you can KILL the middle element.

I.e

Example

Prove:

proof

which is exactly the right hand side

(see tautology)

Example

Consider a four variable function (see maxterm), where represents the most significant bit. Use algebraic manipulation to derive a simplified POS expression for the function such that the cost is no more than 10 when implemented using basic gates.

solution
We have:

which gives:

but this isn't enough. Our cost will be 12 with this configuration. In order to simplify further, we need to find a function that resembles which we know will not affect the result of the function. That is, it must be one of our given maxterms. The maxterm with the curly brace on top matches everything but , so this will be a good choice.

now our cost is 10, as desired.

We could further simplify this to (cost 9), but this would no longer be POS.