Boolean Algebra and Logic - Lecture Notes

Course logistics and ZyBooks access

  • Discussion context included: students involved in setting up a drum show, drone team, and volunteering for the College of Engineering; compensation mentioned as cash via email announcements.
  • Experience shared: volunteers were among the first ~25 in a class to sign up; there were delays and questions about whether the setup moved or was completed.
  • Training/recap reminder: approximately two weeks before the exam, there is a self-signed business school checkpoint; questions about deadlines or requirements were invited.
  • ZyBooks access and Canvas linkage (technical setup):
    • To view content at higher resolution, you can go to zybooks.com and log in after the Canvas session.
    • Critical step: you must first access the material through Canvas to create the link between ZyBooks and Canvas.
    • Once you see a submission indicator in Canvas, you can navigate to zybooks.com and continue there.
    • Password creation and linking process might require some direct assistance from the instructor.
    • If you’ve linked it via Canvas, you can visit zybooks.com to view content without issues.
  • Practical tip given: after linking to Canvas and seeing submission status, you can use zybooks.com for an expanded view.
  • Instructor’s prompt: encourage students to come see the instructor if there are linking issues.
  • Recap question: reminder to revisit topics from last time (Truth tables, Boolean expressions, logic diagrams) and to be ready for Boolean algebra.
  • Quick check for questions about the above: space opened for student inquiries.
  • Signals about access continuity on campus: the lecture includes a note about how content is accessed and how to deal with potential technical hiccups.
  • Final reminder: the class previously covered truth tables, Boolean expressions, and logic diagrams; today starts Boolean algebra.

Boolean algebra: origins, purpose, and current use

  • Boolean algebra name origin:
    • Named after George Boole, who lived in the 17th–18th century (the age of enlightenment).
    • Boole sought a mathematics of human thought, aiming to formalize logic and reasoning mathematically.
    • He originally called his system switching algebra, not Boolean algebra.
  • Claude Shannon’s contribution:
    • In the 1920s–1930s, Claude Shannon, often considered the father of computer science, recognized that Boolean algebra is excellent for describing switching circuits.
    • This link predated the transistor era and described how circuits implement logical expressions.
  • Modern relevance:
    • Boolean algebra is now primarily used to describe and optimize digital systems and logic circuits.
    • The core question in Boolean logic: given a truth table (inputs and outputs), is there another Boolean expression (or logic circuit) that produces the same outputs?
  • Practical engineering motivation:
    • The main driver for finding alternate expressions is cost and efficiency: smaller, simpler circuits cost less to manufacture and operate.
    • In practice, the goal is to minimize resources while preserving behavior, balancing complexity, reliability, and manufacturing cost.

Truth tables and the motivation for Boolean algebra

  • Truth tables show the relationship between inputs and outputs for a Boolean expression.
  • In practice, truth tables become impractical as the number of inputs grows (exponential growth):
    • For n inputs, there are up to 2^n rows in a truth table.
    • With many inputs, truth tables become unwieldy; thus, we use algebraic laws to manipulate and simplify expressions instead.
  • Core question when given a truth table:
    • Is there another logic expression that yields the same truth table, and is it smaller (and therefore cheaper) to implement?
  • Conceptual note on size and cost in engineering:
    • Smaller circuits are cheaper to manufacture; the “size” is not just gate count but the total characteristics of the circuit (gates, inputs, wires, etc.).
    • A common practical metric is the number of literals in a Boolean expression (see below).
  • Truth tables as a teaching aid (and limitations):
    • Truth tables are foundational but not always the practical path for large systems.
    • In exams, students are often asked to recognize and apply Boolean laws to achieve the same outputs rather than to generate full truth tables for large inputs.

Core Boolean algebra concepts and symbols

  • Basic operators (commonly written as):
    • Conjunction (AND): A \,\land\, B
    • Disjunction (OR): A \,\lor\, B
    • Complement/NOT: A' (or \lnot A)
  • Fundamental identity elements and null elements:
    • Null elements (absorb completely in a trivial way):
    • A \land 0 = 0
    • A \lor 1 = 1
    • Identity elements (leave the other operand unchanged):
    • A \land 1 = A
    • A \lor 0 = A
  • Idempotent laws:
    • A \land A = A
    • A \lor A = A
  • Complement laws:
    • A \land A' = 0
    • A \lor A' = 1
  • De Morgan’s laws:
    • (A \land B)' = A' \lor B'
    • (A \,\lor\, B)' = A' \land B'
  • Distributive laws (two forms):
    • OR distributes over AND: A \,\lor\, (B \land C) = (A \lor B) \land (A \lor C)
    • AND distributes over OR: A \land (B \lor C) = (A \land B) \lor (A \land C)

Theorems and common manipulation patterns (laws vs theorems)

  • Distinction between laws and theorems (practical use):
    • Laws are the basic equalities that always hold (e.g., De Morgan’s, Commutative, etc.).
    • Theorems are often higher-level patterns (macros) that summarize common manipulation sequences to simplify work quickly.
    • The instructor notes: many theorems are like subroutines or macros built from underlying laws.
  • Examples of commonly used theorems (as described in class):
    • Absorption theorem: A \lor (A \land B) = A and A \land (A \lor B) = A
    • Elimination theorem (a specific distribution pattern): A \lor (A' \land B) = (A \lor B)
    • Uniting/combining idea (used to show simplification when a term is complemented with its pair): A \land (B \lor B') = A (a combination that collapses due to complementing pair $B \lor B' = 1$)
  • Practical note on naming: the instructor emphasizes recognizing names (e.g., De Morgan, absorption, elimination) and the pattern of applying them rather than memorizing arbitrary steps.

Important laws, with explicit statements (for quick reference)

  • Commutative laws:
    • A \land B = B \land A
    • A \lor B = B \lor A
  • Associative laws:
    • (A \land B) \land C = A \land (B \land C)
    • (A \lor B) \lor C = A \lor (B \lor C)
  • Distributive laws (two forms):
    • A \land (B \lor C) = (A \land B) \lor (A \land C)
    • A \lor (B \land C) = (A \lor B) \land (A \lor C)
  • Identity and null elements:
    • A \land 1 = A, \quad A \lor 0 = A
    • A \land 0 = 0, \quad A \lor 1 = 1
  • Idempotent laws:
    • A \land A = A, \quad A \lor A = A
  • Complement laws:
    • A \land A' = 0, \quad A \lor A' = 1
  • De Morgan’s laws (re-stated):
    • (A \land B)' = A' \lor B'
    • (A \lor B)' = A' \land B'
  • Absorption laws:
    • A \lor (A \land B) = A
    • A \land (A \lor B) = A
  • Elimination theorem (specific form):
    • A \lor (A' \land B) = (A \lor B)
  • Combining/unity theorem (informal name used in class):
    • A \land (B \lor B') = A

Worked example: proving and/or forms and distributive manipulations

  • Goal: illustrate the distributive law in action and show how to simplify to a smaller form.
  • Example 1: Prove that A \lor (B \land C) = (A \lor B) \land (A \lor C)
    • Step 1: Apply the distributive law to expand the left-hand side:
    • A \lor (B \land C) = (A \lor B) \land (A \lor C)
    • Step 2: Recognize that this is exactly the right-hand side; no extra steps needed if starting from the identity form.
  • Example 2 (a common simplification pattern): prove that A \land (B \lor B') = A
    • Step 1: Note that B \lor B' = 1 (the law of the excluded middle or complement law with a pair).
    • Step 2: Substitute: A \land (B \lor B') = A \land 1
    • Step 3: Apply identity law: A \land 1 = A
  • Example 3 (a more explicit path to a simplified form using factoring): show that
    • (A \land B) \lor (A \land B') = A \land (B \lor B') = A
    • Step 1: Distribute as needed and factor out A:
    • (A \land B) \lor (A \land B') = A \land (B \lor B')
    • Step 2: Use the complement law: B \lor B' = 1
    • Step 3: Then A \land 1 = A
  • Note on the step-by-step approach in practice:
    • In class, students demonstrated distributing and then factoring, and sometimes applying a complement law to collapse toward a simpler expression.
    • There is a discussion about whether every intermediate step is required on an exam; the instructor emphasizes recognizing the laws and naming them rather than writing every explicit justification.

Quantifying and comparing Boolean expressions

  • The literal count (a practical metric):
    • A literal is an occurrence of a variable in the Boolean expression.
    • Example: counting literals in two expressions to compare size.
    • In the discussed example, both the top and bottom expressions had four literals each, indicating comparable size in that specific comparison.
  • Circuit implementation considerations:
    • NAND gates are often emphasized because they can realize the fewest transistors for a given function, though context matters (layout, fan-in, and other factors).
    • The choice between reducing literals, reducing gate count, and minimizing transistors is a multi-criteria optimization problem in hardware design.
  • Takeaway: when evaluating a compression or simplification, consider literals, gate count, transistor count, and practical constraints; NAND often provides hardware efficiency, but the best choice depends on the specific circuit and design goals.

Practical workflow and exam tips from the lecture

  • Distinguish laws from theorems:
    • Laws are fundamental equalities (e.g., De Morgan, distribution, idempotence).
    • Theorems are commonly used patterns or macro steps that speed up proofs and simplifications (e.g., combining or elimination patterns).
  • On exams:
    • You’ll be expected to recognize which law is used in a given step and name the law, not necessarily to write a full, scratch-work derivation for every problem.
    • Multiple-choice questions may test recognition of laws and the correctness of a given manipulation, rather than requiring a full derivation proof.
  • Tooling and study strategy:
    • Practice both algebraic manipulation and truth-table verification for small cases to cement understanding of equivalence.
    • Be comfortable with both directions of distributive law and with De Morgan's laws to switch between forms as convenient.
  • Final note on the learning trajectory:
    • The course plans to move from listing laws to applying them in actual circuit simplification (planning for Friday’s session).

Connections to broader themes and real-world relevance

  • Conceptual bridge to digital electronics:
    • Boolean algebra provides the foundation for designing and optimizing digital circuits and logic gates (AND, OR, NOT, NAND, NOR, etc.).
  • Practical engineering mindset:
    • Optimization often involves reducing the number of literals, gates, or transistors while preserving behavior, balancing manufacturing cost, power, latency, and area.
  • Ethical/practical implications (implicit):
    • Efficient circuit design reduces resource usage and energy consumption, which has environmental and economic implications in large-scale hardware deployment.
  • Foundational synthesis workflow:
    • Start from truth table or target behavior, apply Boolean algebra to derive a minimal equivalent expression, and then implement with practical hardware constraints (often via NAND-only or other universal gate forms).

Quick reference formulas (LaTeX)

  • Commutative:
    • A \land B = B \land A
    • A \lor B = B \lor A
  • Associative:
    • (A \land B) \land C = A \land (B \land C)
    • (A \lor B) \lor C = A \lor (B \lor C)
  • Distributive:
    • A \land (B \lor C) = (A \land B) \lor (A \land C)
    • A \lor (B \land C) = (A \lor B) \land (A \lor C)
  • Identity / Null:
    • A \land 1 = A, \quad A \lor 0 = A
    • A \land 0 = 0, \quad A \lor 1 = 1
  • Idempotent:
    • A \land A = A, \quad A \lor A = A
  • Complement:
    • A \land A' = 0, \quad A \lor A' = 1
  • De Morgan:
    • (A \land B)' = A' \lor B'
    • (A \lor B)' = A' \land B'
  • Absorption:
    • A \lor (A \land B) = A
    • A \land (A \lor B) = A
  • Elimination (specific form):
    • A \lor (A' \land B) = A \lor B
  • Combining theorem (informal name from lecture):
    • A \land (B \lor B') = A