A logic gate is a tiny circuit that takes 1-bit inputs (0 or 1) and produces a 1-bit output. The basic gates: NOT (¬a): flips the bit. AND (a·b): 1 only if both inputs are 1. OR (a+b): 1 if at least one input is 1. A truth table lists the output for every combination of inputs.

Derived gates appear constantly: a b AND OR NAND NOR XOR 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 NAND = NOT(AND), NOR = NOT(OR), XOR = 1 when inputs differ. Notation: AND = a·b = a∧b; OR = a+b = a∨b; NOT = ¬a = a'.

Gates are built from relays (early) or transistors (modern, billions per chip — Moore's law). Field-effect transistors are voltage-controlled, hence more energy efficient. Each gate also restores signal levels: as long as the output voltage falls inside the required input range, small noise and voltage loss are corrected automatically — this is why digital logic is reliable and immune to cumulative analogue error. For n inputs a truth table has 2 n rows, and there are 2 (2^n) possible functions — already 65 536 functions for 4 inputs. Regularity, abstraction and hierarchy are needed to manage that explosion.

Every adder, multiplexer, memory cell and ALU in your phone is ultimately gates. A 64-bit addition would need a truth table of 2 64 rows — at a billion rows/second that is over 500 years, so engineers never enumerate it; they compose small reusable blocks.

Boolean algebra is the set of rules for simplifying logic expressions, just like ordinary algebra simplifies numbers. Two values: 1 (true) and 0 (false).

Key laws (each has an AND/OR dual — swap ∧↔∨ and 0↔1): Identity: x∨0 = x, x∧1 = x Zero/One: x∨1 = 1, x∧0 = 0 Idempotence: x∨x = x, x∧x = x Complement: x∨¬x = 1, x∧¬x = 0 Double negation: ¬(¬x) = x Commutativity, Associativity Distributivity: x∧(y∨z) = (x∧y)∨(x∧z), and dually x∨(y∧z) = (x∨y)∧(x∨z) Absorption: x∨(x∧y) = x, x∧(x∨y) = x Complement-absorption: x∨(¬x∧y) = x∨y De Morgan : ¬(x∨y) = ¬x∧¬y and ¬(x∧y) = ¬x∨¬y

Boolean algebra and propositional logic are two views of the same structure. A complete subset of rules (idempotence, zero, identity, double-negation, excluded-middle/contradiction in red on the slides) can derive all the others. De Morgan is what lets you convert between minterm/AND-OR and maxterm/OR-AND forms, and between AND-OR and NAND-NAND implementations.

Compilers and hardware synthesis tools apply exactly these laws to shrink circuits — fewer gates means less silicon, less power, less delay.

A circuit is combinational if its output depends only on the current inputs (no memory, no feedback loops). Given a truth table you can always build one.

Two systematic ways to write any function: Minterm : one product (AND) term per row where the output is 1. If a=1,b=0,c=1 gives 1, its minterm is a∧¬b∧c. Maxterm : one sum (OR) term per row where the output is 0. If a=0,b=1,c=0 gives 0, its maxterm is a∨¬b∨c. Disjunctive Normal Form (DNF) = OR of all minterms. Conjunctive Normal Form (CNF) = AND of all maxterms. Both are canonical (unique) but verbose.

Rules to read terms off a truth table: Minterm (row where f=1): input 0 → take ¬variable, input 1 → take variable, AND them. Maxterm (row where f=0): input 0 → take variable, input 1 → take ¬variable, OR them. Constraints on a valid combinational circuit: no cycles (an input must not depend directly or indirectly on its own output), and two gate outputs must never be wired together .

DNF/CNF are the front door to logic synthesis and to SAT solvers used in verification, AI planning and chip testing.

A Karnaugh map (K-map) is a grid that rearranges a truth table so that physically adjacent cells differ in exactly one input bit. Grouping adjacent 1s lets you read off a minimal formula by eye.

For 4 variables, label columns ab and rows cd in Gray-code order 00, 01, 11, 10 (only one bit changes between neighbours). The map wraps around: top↔bottom and left↔right edges are adjacent. Group rectangular blocks of 1s of size 2 N ×2 M (1,2,4,8…). Bigger groups = simpler terms. Each group drops the variable(s) that change inside it. Cover every 1 with as few, as large groups as possible (groups may overlap). Maxterm/dual approach: group the 0s instead to get a minimal product-of-sums.

Don't-cares (X) are input combinations that cannot occur or whose output is irrelevant; you may treat each X as 0 or 1 — whichever enlarges your groups — giving smaller circuits. Different valid groupings can yield equally minimal but different expressions; there is not always a single 'right' answer. 'Optimal' usually means fewest gate inputs overall, so double-check both the minterm and maxterm solution and pick the cheaper.

K-maps are the by-hand version of the Quine–McCluskey / Espresso algorithms inside every chip-design toolchain.

A set of gate types is functionally complete if you can build every Boolean function using only those gates.

Facts to know: {AND, OR, NOT} is complete (min/maxterm forms prove it). {AND, NOT} and {OR, NOT} are each complete (build the missing one via De Morgan). {NAND} alone is complete; {NOR} alone is complete. (NOT = a NAND a; AND, OR follow.) A multiplexer (MUX) picks one of several data inputs using select lines: 2-input f = a0∧¬s ∨ a1∧s. A 4-input MUX is built from three 2-input MUXes or directly. A MUX is a universal function block : feed constants/inputs to its data lines and it realises any function of the select variables. A PLA (Programmable Logic Array) = an AND-array (forming minterms) feeding an OR-array (summing them); 'programming' removes unwanted connections. Two-level AND-OR is equivalent to NAND-NAND.

Because two-level AND-OR equals NAND-NAND (and OR-AND equals NOR-NOR), any minimised K-map expression maps directly to a uniform NAND (or NOR) implementation — important since NAND/NOR are the cheapest gates in CMOS. The parity function is a classic case where two-level logic needs an exponential number of gates, but a tree of n−1 XOR gates does it in log₂n depth.

FPGAs implement logic as lookup tables (essentially MUX-based universal blocks); PLAs/PALs were the ancestors of today's programmable logic.