Boolean algebra

Boolean algebra is a branch of algebra where operands are 0s and 1s (i.e., binary numbers), with fundamental operations: NOT ($\neg x$), AND ($x\wedge y$), OR ($x\vee y$) (in that order of precedence).

Boolean algebra finds considerable use in implementing digital circuits.

Representations

Boolean functions can be represented in several ways:

• Truth tables represent every possible combination of inputs and outputs.
• Venn diagrams are used to visually show Boolean expressions, similar to applications in probability theory.
• Timing diagrams are analogous to a visual representation of truth tables.

Additionally, functions can be expressed in different ways:

• Minterms and maxterms represent the outputs as a function (AND, OR) of the inputs.
• Sum-of-products and product-of-sums are closed form, compact representations of a function using minterms and maxterms.
• Karnaugh maps are used to minimise logic expressions.

Properties

Boolean algebra is commutative and associative:

$$x\wedge y=y\wedge x$$ $$x\wedge (y\wedge z)=(x\wedge y)\wedge z$$

Distributivity over OR and over AND:

$$x\wedge (y\vee z)=x(y+z)=xy+xz$$ $$x\vee (y\wedge z)=x+yz=(x+y)(x+z)$$

The absorption property:

$$x+xy=x$$

De Morgan’s laws are also foundational.

$$\neg (x\vee y)=\neg x\wedge \neg y$$ $$\neg (x\wedge y)=\neg x\vee \neg y$$

The combination property:

$$xy+x\bar{y}=x$$ $$(x+y)(x+\bar{y})=x$$

And the consensus property:

$$xy+yz+\bar{x}z=xy+\bar{x}z$$ $$(x+y)(y+z)(\bar{x}+z)=(x+y)(\bar{x}+z)$$