MAT104-BOOLEAN-ALGEBRA

Math 104: Discrete Mathematics - Module 2: Boolean Algebra

Lesson: Circuits and Boolean Functions

Learning Objectives

At the end of the lesson, students should be able to:

  1. Define Boolean functions, Boolean expressions, and bit operations.

  2. Describe the three basic gates: inverter, AND gate, and OR gate.

  3. Evaluate bits using bit operations.

  4. Find the value of a Boolean expression with different operations.

  5. Construct a circuit that represents its Boolean function.

  6. Find the output of a given circuit.

  7. Construct combinatorial circuits using inverters, AND gates, and OR gates.

  8. Design circuits for real-life applications.

  9. Describe procedures that simplify sum-of-products expansions.

  10. Produce Boolean sums of Boolean products representing a Boolean function with the fewest products of literals.

Introduction

  • Historical Context:

    • George Boole's contributions to logical thinking formalization.

    • C. E. Shannon's observation in 1938 that Boolean algebra can analyze electrical circuits.

  • Importance:

    • Boolean algebra is essential for analyzing and designing electronic computers.

    • Models circuitry of electronic devices, where inputs and outputs are members of the set {0, 1}.

Logic and Bit Operations

  • Definition of a Bit:

    • A symbol with two possible values: 0 (false) and 1 (true).

  • Truth Values:

    • 1 represents True (T), 0 represents False (F).

  • Bit Operations:

    • Correspond to logical connectives: AND (^), OR (V), and XOR (+).

  • Truth Table for Bit Operators:

    X | Y | X ^ Y | X V Y | X + Y
0 | 0 |   0   |   0   |   0
0 | 1 |   0   |   1   |   1
1 | 0 |   0   |   1   |   1
1 | 1 |   1   |   1   |   0

Boolean Functions and Expressions

  • Boolean Algebra Operations:

    • Complementation: Denoted by a bar (e.g., 0̅ = 1, 1̅ = 0).

    • Boolean Sum: Denoted by + (OR).

    • Boolean Product: Denoted by . (AND).

  • Example:

    • Find the value of 1.0 + (0 + 1) = 0 + 1 = 1.

Combinatorial Circuits

  • Definition:

    • Output is uniquely defined for every combination of inputs; no memory.

  • Logic Gates:

    • Inverter (NOT Gate): Outputs the negation of the input.

    • OR Gate: Outputs true if at least one input is true.

    • AND Gate: Outputs true only if all inputs are true.

  • Example Circuit:

    • Construct a circuit for the output (p V -r) ∧ (-p V (q V -r)).

Minimization of Combinatorial Circuits

  • Goal:

    • Create circuits with the fewest gates and inputs.

  • Process:

    • Use sum-of-products expansion to find a set of logic gates.

    • Combine terms in the expansion that differ in only one variable.

Adders

  • Half Adder:

    • Accepts two bits and produces a binary sum (CS).

    • Outputs: Sum bit (S) and Carry bit (C).

  • Full Adder:

    • Accepts three bits and produces a binary sum (CS).

  • Example:

    • Half adder truth table and circuit design.

Exercises

  1. Determine the bitwise NOT of given bit strings.

  2. Find bitwise OR, AND, and XOR for pairs of bit strings.

  3. Evaluate Boolean expressions.

  4. Convert decimal numbers to binary and vice versa.

  5. Find the sum-of-products expansions for given Boolean functions.

This note summarizes the key concepts and objectives of the lesson on Boolean Algebra, focusing on circuits and Boolean functions, while providing a structured