Logic in computing
The same logic that structures proofs runs inside every computer, from circuits to search queries to program correctness.
Boolean values and operations
Computers represent true and false as 1 and 0. Logical operations become Boolean operations: AND, OR, NOT. In code, conditions like if (age >= 18 && hasID) use exactly the connectives of propositional logic, and De Morgan's laws let programmers rewrite them clearly.
Logic gates
Hardware implements logic with gates: AND, OR, NOT, and combinations like NAND and XOR. Remarkably, NAND alone can build every other gate, so it is called universal. Circuits of millions of gates perform arithmetic, store memory, and execute instructions.
Truth tables and circuit design
A truth table specifies a circuit's output for every input combination. Designers derive a logical expression from the table and simplify it, using laws like distribution and De Morgan's, to minimise the number of gates. Fewer gates mean cheaper, faster, cooler chips.
Exclusive or
XOR, \(p \oplus q\), is true when exactly one input is true. It matches everyday 'either-or'. XOR is used in binary addition (the sum bit of two bits), in error detection, and in simple encryption, because applying the same XOR twice restores the original data.
p \oplus q \equiv (p \vee q) \wedge \neg(p \wedge q)Satisfiability
A formula is satisfiable if some assignment of truth values makes it true. Deciding satisfiability (SAT) for large formulas is computationally hard in general, yet modern SAT solvers handle millions of variables and are used to verify chips, schedule flights, and solve puzzles.
Logic in databases and search
Database queries filter records with logical conditions: WHERE country = 'Japan' AND (age < 30 OR student = true). Search engines support similar operators. Understanding precedence and parentheses prevents queries that return far more or far fewer results than intended.
Program correctness
Programmers reason with preconditions, postconditions, and loop invariants, which are logical statements about program state. Proving that a loop invariant holds before, during, and after a loop is a form of mathematical induction, the topic of a later unit.
Worked example
Simplify the condition NOT (x > 5 AND y = 0). By De Morgan's law, it becomes x <= 5 OR y != 0. The rewritten version is often easier to read and debug, and it is guaranteed to behave identically.
Key takeaways
Boolean logic underlies hardware gates, program conditions, and database queries. NAND is universal. XOR captures exclusive or and powers binary addition and error checking. SAT solvers tackle large logical problems, and logical reasoning is central to proving programs correct.
Flashcard
True (1) or false (0)
Check your understanding
What is NOT (A OR B) equivalent to?