Boolean Algebra

Digital Circuits

Advantages of digital circuits

• More reliable
• Specified accuracy
• Abstraction can be applied using simple mathematical model
• Ease design, analysis and simplification of digital circuit

Combinational

No memory, output depends solely on the input

• Gates
• Decoders, multiplexers
• Adders, multipliers

Sequential

With memory, output depends on both input and current state

• Counters, registers, memories

Boolean Values

true: 1 false: 0

Conjunction AND: Disjunction OR: Negation NOT:

Precedence of Operators

1. Parenthesis
2. NOT
3. AND
4. OR

Laws of Boolean Algebra

Identity laws

Inverse/complement laws

Commutative laws

Associative laws

Distributive laws

Duality

If the AND/OR operations and identity elements 0/1 in a Boolean equation are interchanged, the equation remains valid.

(x + y + z)' = x' \cdot y' \cdot z' \text{ is valid } \implies (x \cdot y \cdot z)' = x' + y'+ z' \text{ is valid }

Idempotency

One element/zero element

Involution

Absorption

Absorption

DeMorgan's

Consensus

Complement

Obtained by interchanging 1 with 0 in the function’s output values

Standard Forms

1. Sum-Of-Products (SOP)
2. Product-of-Sums (POS)

Literal

Boolean variable on its own

x, x'

Product term

Single literal or logical product AND of several literals

x, x \cdot y

Sum-of-products (SOP) expression

A product term or a logical sum OR of several product terms

x, (x \cdot y) + (x' \cdot y')

Sum term

Single literal or a logical sum OR of several literals

x, x + y

Product-of-sums (POS) expression

A sum term or a logical product AND of several sum terms

x, (x+y) \cdot (x'+y')

Minterms and Maxterms

Minterm

A product term that contains literals from all the variables.

for x, y, minterms: x' \cdot y', x' \cdot y, x \cdot y', x \cdot y

Maxterm

A sum term that contains literals from all the variables.

for x, y, minterms: x' + y', x' + y, x + y', x + y

For n variables, there is up to 2^{n} maxterms/minterms.

x	y	Minterms	Maxterms	Notation
				m/M0
				m/M1
				m/M2
				m/M3

Each minterm is the complement of the corresponding maxterm and vice versa.

Canonical forms

• Sum-of-minterms = Canonical sum-of-products
• Product-of-maxterms = Canonical product-of-sums

Sum-of-minterms

Obtain sum-of-minterms expression by gathering minterms of the function, where output is 1.

Product-of-maxterms

Obtain product-of-maxterms expression by gathering the maxterms of the function (where output is 0)

Conversion of Standard Forms

The conversion is just the opposite of the current result.

For example, given the example:

We can then also, derive :

Similarly from the product-of-maxterms: