What is Boolean Algebra?

• Definition: Mathematical system for logic operations using binary values (0 and 1)

• Developed by: George Boole (1854) - "An Investigation of the Laws of Thought"

• Binary Values:

  • 0 = False, Low, Off

  • 1 = True, High, On

• Applications:

  • Digital circuit design

  • Computer programming logic

  • Decision-making systems

Why Study Boolean Algebra?

• Circuit Simplification: Reduces hardware complexity and cost

• Logic Analysis: Helps understand and design digital systems

• Problem Solving: Foundation for programming and algorithm design

• Real-world Applications:

  • Microprocessor design

  • Control systems

  • Database queries

  • Search engines

The Three Fundamental Operations

• AND Operation (Conjunction)

  • Symbol: \(A \cdot B\) or \(A \land B\) or \(AB\)

  • Logic: Output is 1 only when all inputs are 1

  • Truth: \(1 \cdot 1 = 1\), all others = 0

• OR Operation (Disjunction)

  • Symbol: \(A + B\) or \(A \lor B\)

  • Logic: Output is 1 when at least one input is 1

  • Truth: \(0 + 0 = 0\), all others = 1

• NOT Operation (Negation/Complement)

  • Symbol: \(\overline{A}\) or \(A'\) or \(\sim A\)

  • Logic: Inverts the input (0\(\to\)1, 1\(\to\)0)

  • Truth: \(\overline{1} = 0\), \(\overline{0} = 1\)

Truth Tables for Basic Operations

Memory Aid: AND is like multiplication, OR is like addition (but 1+1=1), NOT flips the bit

Basic Boolean Laws (Part 1)

• Commutative Laws:

  • \(A \cdot B = B \cdot A\) (AND is commutative)

  • \(A + B = B + A\) (OR is commutative)

• Associative Laws:

  • \((A \cdot B) \cdot C = A \cdot (B \cdot C)\)

  • \((A + B) + C = A + (B + C)\)

• Distributive Laws:

  • \(A \cdot (B + C) = (A \cdot B) + (A \cdot C)\)

  • \(A + (B \cdot C) = (A + B) \cdot (A + C)\)

Basic Boolean Laws (Part 2)

• Identity Laws:

  • \(A \cdot 1 = A\) (AND with 1)

  • \(A + 0 = A\) (OR with 0)

• Null Laws:

  • \(A \cdot 0 = 0\) (AND with 0)

  • \(A + 1 = 1\) (OR with 1)

• Idempotent Laws:

  • \(A \cdot A = A\)

  • \(A + A = A\)

• Complement Laws:

  • \(A \cdot \overline{A} = 0\)

  • \(A + \overline{A} = 1\)

  • \(\overline{\overline{A}} = A\) (Double negation)

De Morgan’s Theorems

• Extended Form: \(\overline{A \cdot B \cdot C} = \overline{A} + \overline{B} + \overline{C}\)

• Memory Aid: "Break the line, change the sign"

• Applications: Converting between AND/OR gates, logic simplification

Proof of De Morgan’s First Theorem

Theorem: \(\overline{A \cdot B} = \overline{A} + \overline{B}\)

Since columns 4 and 7 are identical, the theorem is proved!

Boolean Expressions

• Definition: Mathematical expressions using Boolean variables and operations

• Examples:

  • Simple: \(F = A \cdot B\)

  • Complex: \(F = A \cdot B + \overline{C} \cdot D + A \cdot \overline{B}\)

• Standard Forms:

  • Sum of Products (SOP): \(F = A \cdot B + \overline{A} \cdot C\)

  • Product of Sums (POS): \(F = (A + B) \cdot (\overline{A} + C)\)

• Canonical Forms:

  • Minterms: Each product term contains all variables

  • Maxterms: Each sum term contains all variables

Logic Simplification Techniques

• Algebraic Method:

  • Apply Boolean laws systematically

  • Look for common factors

  • Use complement laws

• Example 1: Simplify \(F = A \cdot B + A \cdot \overline{B}\)

  \[\begin{aligned} F &= A \cdot B + A \cdot \overline{B} \\ &= A \cdot (B + \overline{B}) \quad \text{(Factor out A)} \\ &= A \cdot 1 \quad \text{(Complement law)} \\ &= A \quad \text{(Identity law)} \end{aligned}\]

More Simplification Examples

Example 2: Simplify \(F = A \cdot B + A \cdot B \cdot C\)

Example 3: Simplify \(F = \overline{A \cdot B} + A \cdot \overline{B}\)

Constructing Truth Tables

Steps to create a truth table:

1. List all possible input combinations (\(2^n\) rows for n variables)

2. Evaluate intermediate expressions

3. Calculate final output

Example: \(F = A \cdot B + \overline{C}\)

Deriving Boolean Expressions from Truth Tables

Method 1: Sum of Minterms (SOP)

• Find rows where output = 1

• Write minterm for each row

• OR all minterms together

Method 2: Product of Maxterms (POS)

• Find rows where output = 0

• Write maxterm for each row

• AND all maxterms together

From previous example:

• SOP: \(F = \overline{A}\overline{B}\overline{C} + \overline{A}B\overline{C} + A\overline{B}\overline{C} + AB\overline{C} + ABC\)

• Simplified: \(F = AB + \overline{C}\) \(\checkmark\)

Real-World Applications

• Digital Circuit Design:

  • Minimize gates in logic circuits

  • Reduce power consumption and cost

• Computer Programming:

  • Conditional statements (if-then-else)

  • Logical operators in code

• Database Systems:

  • Query optimization using Boolean logic

  • Search conditions with AND/OR/NOT

• Control Systems:

  • Traffic light controllers

  • Industrial automation

Example: Alarm System Logic

Problem: Design logic for a home security system

Inputs:

• A = Door sensor (1 = open, 0 = closed)

• B = Window sensor (1 = open, 0 = closed)

• C = Motion detector (1 = motion, 0 = no motion)

• D = System armed (1 = armed, 0 = disarmed)

Output: F = Alarm (1 = sound alarm, 0 = no alarm)

Logic: Alarm sounds when system is armed AND (door OR window is open OR motion detected)

Boolean Expression:

Expanded:

Key Takeaways

• Boolean Algebra Fundamentals:

  • Three basic operations: AND, OR, NOT

  • Binary system with values 0 and 1

• Essential Laws:

  • Commutative, Associative, Distributive laws

  • De Morgan’s theorems for logic conversion

  • Identity, Null, and Complement laws

• Practical Skills:

  • Simplifying Boolean expressions

  • Creating and interpreting truth tables

  • Converting between different forms (SOP/POS)

• Applications: Circuit design, programming, databases, control systems

What’s Next?

• Logic Gates: Physical implementation of Boolean operations

• Universal Gates: NAND and NOR gates

• Karnaugh Maps: Systematic simplification method

• Combinational Circuits: Building complex logic systems