02.6 Boolean Algebra

Boolean algebra can be used to efficiently describe logic circuits

Axioms

Like any algebra, boolean algebra is based on a set of rules derived from a small number of basic (and assumed true) assumptions — we call those axioms

$$\boxed{\begin{array}{cc}1a& 0\cdot 0=0\\ 1b& 1+1=0\end{array}}\boxed{\begin{array}{cc}2a& 1\cdot 1=1\\ 2b& 0+0=0\end{array}}\boxed{\begin{array}{cc}3a& 0\cdot 1=1\cdot 0=0\\ 3b& 1+0=0+1=1\end{array}}\boxed{\begin{array}{ccc}4a& x=0& \bar{x}=1\\ 4b& x=1& \bar{x}=0\end{array}}$$

Single-Variable Theorems

For a given variable, the following theorems hold:

$$\boxed{\begin{array}{cc}5a& x\cdot 0=0\\ 5b& x+1=x\end{array}}\boxed{\begin{array}{cc}6a& x\cdot 1=x\\ 6b& x+0=x\end{array}}\boxed{\begin{array}{cc}7a& x\cdot x=x\\ 7b& x+x=x\end{array}}\boxed{\begin{array}{cc}8a& x\cdot \bar{x}=0\\ 8b& x+\bar{x}=1\end{array}}\boxed{\overline{\stackrel{ˉ}{x}}=x}$$

But what’s the point?

The purpose of axioms, theorems and properties, is to

• Check for equivalence
• Simplify circuits

Two/Three variable properties

$$\boxed{\begin{array}{c}\text{Commutative}\\ \begin{array}{cc}10a& x\cdot y=y\cdot x\\ 10b& x+y=y+x\end{array}\end{array}}\boxed{\begin{array}{c}\text{Associative}\\ \begin{array}{cc}11a& x\cdot (y\cdot z)=(x\cdot y)\cdot z\\ 11b& x+(y+z)=(x+y)+z\end{array}\end{array}}\boxed{\begin{array}{c}\text{Distributive}\\ \begin{array}{cc}12a& x\cdot (y+z)=x\cdot y+x\cdot z\\ 12b& x+y\cdot z=(x+y)\cdot (x+z)\end{array}\end{array}}$$ $$\boxed{\begin{array}{c}\text{Absorption}\\ 13ax+x\cdot y=x\\ 13bx\cdot (x+y)=x\end{array}}\boxed{\begin{array}{c}\text{Combining}\\ 14ax\cdot y+x\cdot \bar{y}=x\\ 14b(x+y)\cdot (x+\bar{y})=x\end{array}}$$ $$\boxed{\begin{array}{c}\text{DeMorgan’s}\\ 15a\overline{x\cdot y}=\bar{x}+\bar{y}\\ 15b\overline{x+y}=\bar{x}\cdot \bar{y}\end{array}}\boxed{\begin{array}{c}\text{Redundancy}\\ 16ax+\bar{x}\cdot y=x+y\\ 16bx\cdot (\bar{x}+y)=xy\end{array}}$$ $$\boxed{\begin{array}{c}\text{Consensus}\\ 17ax\cdot y+y\cdot z+\bar{x}z=x\cdot y+\bar{x}\cdot z\\ 17b(x+y)\cdot (y+z)\cdot (\bar{x}+z)=(x+y)\cdot (\bar{x}+z)\end{array}}$$

02.7 Logic synthesis — Minterms - Maxterms