Boolean algebra Study Guide

📖 Core Concepts Boolean algebra: algebraic system for logical truth values 0 (false) and 1 (true). Primary operators: AND (∧) – true only if both inputs true. OR (∨) – true if at least one input true. NOT (¬) – flips truth value. Secondary operators (derived): XOR, NAND, NOR, implication (→), equivalence (↔). Truth values ↔ GF(2): addition ≡ XOR, multiplication ≡ AND (mod 2). Duality principle: swapping 0↔1 and ∧↔∨ (leaving ¬ unchanged) yields another valid Boolean identity. Concrete Boolean algebra: collection of subsets of a set closed under ∪, ∩, complement (e.g., power set). Abstract Boolean algebra: any set with ∧, ∨, ¬ satisfying the Boolean laws. --- 📌 Must Remember Fundamental identities (hold for all Boolean algebras): Commutative: $x∧y = y∧x$, $x∨y = y∨x$ Associative: $x∧(y∧z) = (x∧y)∧z$, $x∨(y∨z) = (x∨y)∨z$ Distributive (both ways): $x∧(y∨z) = (x∧y)∨(x∧z)$, $x∨(y∧z) = (x∨y)∧(x∨z)$ Identity: $x∧1 = x$, $x∨0 = x$ Domination: $x∧0 = 0$, $x∨1 = 1$ Idempotent: $x∧x = x$, $x∨x = x$ Complement: $x∧¬x = 0$, $x∨¬x = 1$ Double‑negation: $¬¬x = x$ De Morgan’s laws: $¬(x∧y)=¬x∨¬y$, $¬(x∨y)=¬x∧¬y$ Implication: $x→y ≡ ¬x ∨ y$ XOR: $x⊕y ≡ (x∨y)∧¬(x∧y)$ (true when exactly one input true) NAND / NOR: $\operatorname{NAND}=¬(x∧y)$, $\operatorname{NOR}=¬(x∨y)$ --- 🔄 Key Processes Deriving a secondary operator (e.g., NAND): Start with primary definition → apply NOT: $\operatorname{NAND}(x,y)=¬(x∧y)$ Simplifying a Boolean expression (using identities): Replace $x∨¬x$ with 1 (complement law). Apply absorption: $x∧(x∨y) \rightarrow x$. Use De Morgan to move negations inward. Converting to arithmetic form (GF(2)): $x∧y \rightarrow xy$ (product) $x∨y \rightarrow x + y - xy$ $¬x \rightarrow 1 - x$ --- 🔍 Key Comparisons AND vs. OR: AND true only when both inputs = 1 → $xy$ → $\min(x,y)$. OR true when any input = 1 → $x + y - xy$ → $\max(x,y)$. NAND vs. NOR: NAND = NOT AND → false only when both inputs true. NOR = NOT OR → true only when both inputs false. XOR vs. Equivalence: XOR true for exactly one true: $x⊕y$. Equivalence true for same truth values: $¬(x⊕y)$. --- ⚠️ Common Misunderstandings Implication truth table: $x→y$ is true when $x=0$, regardless of $y$; many assume “if‑then” must have a causal link. XOR vs. OR: $x∨y$ is true when both are true, whereas XOR is false in that case. Duality misuse: swapping constants without swapping operators (or vice‑versa) breaks the principle. De Morgan’s direction: remember the negation distributes and flips the operator (∧↔∨). --- 🧠 Mental Models / Intuition 0/1 as “off/on” switches: AND = series circuit (both must close), OR = parallel circuit (any path closes). GF(2) addition = XOR: think of adding bits without carry—exactly the XOR behavior. Duality as “mirror image”: imagine a truth table flipped vertically (0↔1) and swapping ∧/∨ leaves the pattern unchanged. --- 🚩 Exceptions & Edge Cases Absorption does NOT hold for XOR: $x⊕(x∨y) \neq x$. Distributivity of XOR over AND/OR fails: $x⊕(y∧z) \neq (x⊕y)∧(x⊕z)$. Implication with false antecedent: $0→0$ and $0→1$ are both true (vacuous truth). --- 📍 When to Use Which Designing digital circuits: use NAND or NOR exclusively (they are functionally complete) to minimise gate types. Simplifying algebraic expressions: apply absorption and complement laws first; then use distributivity if it reduces term count. Proofs in propositional logic: convert complex formulas to conjunctive normal form (CNF) using De Morgan and distributivity, then apply resolution. Counting solutions (SAT problems): represent constraints with NAND/NOR because they map directly to SAT clauses. --- 👀 Patterns to Recognize $x∧¬x$ or $x∨¬x$ → instantly replace with 0 or 1 (complement law). Repeated variable inside a larger expression → apply idempotent ($x∧x = x$, $x∨x = x$). Form $¬(A∧B)$ or $¬(A∨B)$ → fire De Morgan to split the negation. Expressions like $x∧(x∨y)$ → spot absorption → simplifies to $x$. --- 🗂️ Exam Traps Choosing wrong operator precedence: remember NOT > AND > OR; missing parentheses often leads to swapped results. Treating XOR as “or”: answer choices that claim $x⊕y = x∨y$ are false when both inputs are 1. Misreading implication: $x→y$ is false only for $x=1, y=0$; any answer suggesting $0→0$ is false is a distractor. Negation of a compound: $¬(x∧y∨z)$ is not $¬x∧¬y∧¬z$ (wrong distribution); correct is $¬x∨¬y∧¬z$ after applying De Morgan step‑by‑step. Assuming distributivity both ways: $x∧(y∨z)= (x∧y)∨(x∧z)$ holds, but $x∨(y∧z)= (x∨y)∧(x∨z)$ is also true—both are valid, yet some students forget the second direction. ---