Boolean Algebra

Boolean Algebra is a branch of algebra that deals with variables that can have only two possible values:

• True, usually represented by 1
• False, usually represented by 0

Boolean algebra operates on the binary number system.

It deals with:

• Binary variables
• Logical operations
• Logical expressions

Boolean algebra is fundamental to the development of digital electronic systems because digital circuits use Boolean operations to perform logical tasks.

Boolean algebra is also used in:

• Digital Electronics
• Set Theory
• Statistics
• Other branches of Mathematics

Rules for Boolean Algebra

The basic rules of Boolean algebra include:

1. A Boolean variable can have only two values: 0 or 1.
2. The complement of a variable is represented by an overbar or prime symbol.
3. Logical OR is represented by the plus (+) sign.
4. Logical AND is represented by a dot (·) sign.

For example:

A + B represents OR.

A · B represents AND.

A′ represents the complement of A.

Boolean Laws

Boolean Laws are fundamental principles used to manipulate and simplify Boolean expressions.

These laws are important for:

• Simplifying logical expressions
• Analyzing digital circuits
• Designing logic circuits
• Solving logical problems

Basic Boolean Laws

The major Boolean laws discussed in the notes are:

1. Commutative Law
2. Associative Law
3. Distributive Law
4. Inversion Law

1. Commutative Law

The Commutative Law states that changing the order of variables does not affect the result.

For OR operation:

A + B = B + A

For AND operation:

A · B = B · A

This means that the order of inputs does not matter.

2. Associative Law

The Associative Law states that when more than two variables are used, changing their grouping does not affect the result.

For OR operation:

(A + B) + C = A + (B + C)

For AND operation:

(A · B) · C = A · (B · C)

3. Distributive Law

The Distributive Law allows Boolean expressions to be expanded or factored.

Examples:

A(B + C) = A · B + A · C

and:

A + (B · C) = (A + B)(A + C)

4. Inversion Law

The Inversion Law states that the double complement of a Boolean variable gives the original variable.

Example:

(A′)′ = A

Similarly:

((A + B)′)′ = A + B

Boolean Expression Rules

Boolean expression rules are used to construct and simplify logical expressions that produce true or false results.

Rule 1: A + 0 = A

When a variable is ORed with 0, the result is equal to the original variable.

If:

A = 0

then:

0 + 0 = 0

If:

A = 1

then:

1 + 0 = 1

Therefore:

A + 0 = A

Figure: Add Boolean Rule 1 diagram here.

Rule 2: A + 1 = 1

When a Boolean variable is ORed with 1, the result is always 1.

Therefore:

A + 1 = 1

Figure: Add Boolean Rule 2 diagram here.

Rule 3: A · 0 = 0

When a variable is ANDed with 0, the output is always 0.

Therefore:

A · 0 = 0

Figure: Add Boolean Rule 3 diagram here.

Rule 4: A · 1 = A

When a Boolean variable is ANDed with 1, the output remains equal to the original variable.

Therefore:

A · 1 = A

Figure: Add Boolean Rule 4 diagram here.

Rule 5: A + A = A

When a variable is ORed with itself, the result remains the same variable.

Therefore:

A + A = A

Figure: Add Boolean Rule 5 diagram here.

Rule 6: A + A′ = 1

When a variable is ORed with its complement, the result is always 1.

Therefore:

A + A′ = 1

Figure: Add Boolean Rule 6 diagram here.

Rule 7: A · A = A

When a variable is ANDed with itself, the result remains equal to the original variable.

Therefore:

A · A = A

Figure: Add Boolean Rule 7 diagram here.

Rule 8: A · A′ = 0

When a variable is ANDed with its complement, the result is always 0.

Therefore:

A · A′ = 0

Figure: Add Boolean Rule 8 diagram here.

Rule 9: A = (A′)′

When the complement of a variable is complemented again, the original variable is obtained.

Therefore:

A = (A′)′

Rule 10: A + AB = A

According to the provided notes:

A + AB = A

Solution:

A + AB

= A(1 + B)

= A · 1

= A

Rule 11

According to the provided notes, Rule 11 is stated as:

A + AB = A + B

The provided solution is:

= (A + AB) + AB

= (AA + AB) + AB

= AA + AB + AA + AB

= (A + A)(A + B)

= 1 · (A + B)

= A + B

Rule 12: (A + B)(A + C) = A + BC

Solution:

(A + B)(A + C)

= AA + AC + AB + BC

= A + AC + AB + BC

= A(1 + C) + AB + BC

= A · 1 + AB + BC

= A(1 + B) + BC

= A · 1 + BC

= A + BC

Boolean Functions

In Boolean algebra, logical operations and binary variables are used to create Boolean Functions.

A Boolean function is represented using a Boolean Expression.

A Boolean expression may contain:

• Binary variables
• Logical operators
• Constants 0 and 1

Important Terms in Boolean Functions

The important terms are:

1. Variables
2. Prime Implicant
3. Essential Prime Implicant
4. Literal
5. Product Terms
6. Min-Terms
7. Max-Terms

1. Variables

Variables are the input values of a Boolean function.

They normally represent binary values.

Boolean variables are usually represented by letters such as:

• A
• B
• C
• D

2. Prime Implicant

A Prime Implicant is a product term that covers one or more min-terms of a Boolean function.

It is considered prime if removing a variable from it would prevent it from covering the required min-terms.

Prime implicants are useful when simplifying Boolean expressions.

3. Essential Prime Implicant

An Essential Prime Implicant is a prime implicant that covers at least one min-term that is not covered by any other prime implicant.

Essential prime implicants are important when finding minimum representations of Boolean functions.

They are used in:

• Sum of Products (SOP)
• Product of Sums (POS)

4. Literal

A Literal is a Boolean variable or its complement.

Examples:

• A
• A′
• B
• B′

5. Product Terms

Product Terms are Boolean terms formed by ANDing literals.

Example:

A · B · C

6. Min-Terms

A Min-Term represents a row in a truth table where the Boolean function output is:

1

Min-terms contain variables in either:

• True form
• Complemented form

7. Max-Terms

A Max-Term represents the logical OR of literals.

A max-term corresponds to a row in a truth table where the Boolean function output is:

0

Canonical and Standard Form

Boolean functions can be represented in different forms.

The notes discuss:

1. Canonical Form
2. Standard Form

Canonical Form

A Boolean function can be expressed in:

• Canonical Disjunctive Normal Form
• Canonical Conjunctive Normal Form

Canonical Disjunctive Normal Form is based on Min-Terms.

Canonical Conjunctive Normal Form is based on Max-Terms.

For min-terms, we consider the combinations where the output is:

1

For max-terms, we consider the combinations where the output is:

0

The Sum of Min-Terms is also known as:

Sum of Products (SOP)

The Product of Max-Terms is also known as:

Product of Sums (POS)

A Boolean function written as a sum of min-terms or product of max-terms is said to be in Canonical Form.

Standard Form

A Boolean variable can appear in either:

• True form
• Complemented form

According to the provided notes, in standard form a Boolean function contains variables in true or complemented form, whereas the canonical representation depends on the SOP or POS form of the function.

Sum of Products (SOP) Form

The Sum of Products (SOP) form is a method used to represent and simplify Boolean expressions.

In SOP:

1. Variables are ANDed together to form product terms.
2. The product terms are then ORed together.

For example:

AB + A′C + BC

Here:

• AB is a product term.
• A′C is a product term.
• BC is a product term.

The terms are joined using OR.

SOP is also called:

• Disjunctive Normal Form
• Standard SOP

According to the notes, SOP representation is suitable for applications such as FPGA (Field Programmable Gate Array) implementation.

SOP Representation

According to the provided notes:

A = 1

A′ = 0

SOP is denoted by:

Σ

Steps to Obtain SOP Form

Step 1: Find each input combination for which the output is HIGH or 1.

Step 2: Write an AND term for each combination.

Step 3: If an input variable has the value 1, write it in normal form.

Step 4: If the input variable has the value 0, write its complement.

Step 5: OR all the AND terms to obtain the final output function.

SOP Example

The notes provide the following majority function:

F = A′BC + AB′C + ABC′ + ABC

Product of Sums (POS) Form

The Product of Sums (POS) form is another method of representing Boolean expressions.

It is the opposite or dual of SOP.

In POS:

1. Variables are ORed to create sum terms.
2. The sum terms are then ANDed together.

For example:

(A + B)(A′ + C)(B + C′)

POS is also known as:

• Conjunctive Normal Form
• Standard POS

POS Representation

According to the notes:

A = 0

A′ = 1

POS is denoted by:

π

Steps to Obtain POS Form

Step 1: Identify each input combination where the output is LOW or 0.

Step 2: Write an OR term for each such combination.

Step 3: Write the variable normally if its value is 0.

Step 4: Write the complement of the variable if its value is 1.

Step 5: AND all the OR terms to obtain the output function.

POS Example

The provided notes give:

F = (A + B + C)(A + B + C′)(A + B′ + C)(A′ + B + C)

K-Map (Karnaugh Map)

A Karnaugh Map, commonly called a K-Map, is a systematic graphical method used to simplify Boolean expressions.

Using a K-Map, we can obtain simplified:

• SOP expressions
• POS expressions

The simplified result is often called the Minimum Expression.

A K-Map contains all possible combinations of input variables and their corresponding output values.

Unlike a truth table, K-Map values are arranged inside cells of a grid.

K-Maps can be used with expressions containing:

• 2 variables
• 3 variables
• 4 variables
• 5 variables

The K-Map grid is filled using:

• 0
• 1

The expression is simplified by forming groups of adjacent cells.

Steps to Solve Expressions Using K-Map

The following steps are used:

Step 1: Select the appropriate K-Map based on the number of variables.

Step 2: Identify min-terms and max-terms in the given expression.

Step 3: For SOP, fill the respective min-term cells with 1.

Step 4: For POS, fill the respective max-term cells with 0.

Step 5: Create rectangular groups containing a number of cells in powers of two, such as:

• 2
• 4
• 8

Try to include as many cells as possible in each group.

Step 6: Use these groups to find simplified product or sum terms.

A K-Map can therefore be considered a graphical representation of a truth table.

Types of K-Map

The notes discuss:

1. 2-Variable K-Map
2. 3-Variable K-Map
3. 4-Variable K-Map

1. 2-Variable K-Map

A 2-Variable K-Map uses two variables.

It contains 4 cells, representing all possible combinations of the two binary variables.

Figure: Add 2-Variable K-Map diagram here.

2. 3-Variable K-Map

A 3-Variable K-Map contains:

8 cells

The variables may be represented by:

• A
• B
• C

According to the notes, the binary values of variables are arranged along the rows and columns of the K-Map.

Each cell represents one possible combination of the three variables.

For example:

• One cell may represent 000.
• Another cell may represent 101.

Figure: Add 3-Variable K-Map diagram here.

3. 4-Variable K-Map

A 4-Variable K-Map contains:

16 cells

The four variables may be:

• A
• B
• C
• D

According to the notes, values of A and B may be arranged along one side, while C and D are arranged along the top.

Each cell represents a unique combination of the four variables.

Figure: Add 4-Variable K-Map diagram here.

Terms of K-Map

Important grouping terms used in K-Map are:

1. Pair
2. Quad
3. Octet

Pair

A Pair is formed when two adjacent 1s are grouped together in a K-Map.

Figure: Add K-Map Pair example here.

Quad

A Quad is a group of four adjacent cells.

A quad can be arranged:

• Horizontally
• Vertically
• In a rectangular or square form

Quads help simplify Boolean expressions by combining four related terms.

Figure: Add K-Map Quad example here.

Octet

An Octet is a group of eight adjacent cells.

It can have arrangements such as:

• 4 × 2
• 2 × 4

Octets are larger groups used to obtain greater simplification.

Figure: Add K-Map Octet example here.

Plotting on K-Map

K-Map values can be plotted using either:

1. SOP Form
2. POS Form

Plotting in SOP Form

For SOP:

Step 1: Place 1 in each cell corresponding to a min-term in the SOP expression.

Step 2: Fill the remaining cells with 0 or leave them empty.

According to the notes:

A = 1

A′ = 0

Figure: Add SOP K-Map plotting example here.

Plotting in POS Form

For POS:

Step 1: Place 0 in each cell corresponding to a max-term in the POS expression.

Step 2: Fill the remaining cells with 1 or leave them empty.

According to the notes:

A = 0

A′ = 1

Figure: Add POS K-Map plotting example here.