Discrete Math › Section B · Logic and proofs › Topic B.6
Logic in computing
The logic of the previous topics is not only for proofs: it runs every computer. The same connectives appear as conditions in code, as gates in chips, as filters in database queries and as the statements used to check that a program is correct.
Logic inside the machine
A computer stores everything as bits, and each bit is 0 or 1. Read 1 as true and 0 as false, and the connectives of logic become operations on bits, usually written AND, OR and NOT. This is Boolean logic, named after George Boole, the 19th-century mathematician who recast logic as a kind of algebra. Every rule from the topic Truth tables, equivalence, and deduction carries over unchanged: a truth table now describes what a circuit or a line of code outputs for each combination of inputs, and logical equivalence means two pieces of code always behave alike.
Logic in code
Programming languages build conditions from the same connectives. Python writes them as and, or and not; C, Java and JavaScript write &&, || and !. In Python, not binds most tightly, then and, then or, so "x > 3 or y > 3 and z > 3" means "x > 3 or (y > 3 and z > 3)". Most languages also use short-circuit evaluation: in "A and B", if A is false, B is never evaluated, because the result is already false. That is why "x != 0 and 10 / x > 2" is safe in Python: the division runs only when x is not 0.
Worked example: tidying a condition
A program rejects a customer with "if not (age >= 18 and has_id):". Rewrite it without the outer not. 1. Let P be "age >= 18" and Q be has_id; the condition is \(\neg(P \wedge Q)\). 2. De Morgan's law gives \(\neg P \vee \neg Q\). 3. The negation of age >= 18 is age < 18, not age <= 18. 4. Result: "if age < 18 or not has_id:". 5. Check all four cases: an adult with ID is accepted by both versions; an adult without ID, a minor with ID and a minor without ID are rejected by both. The two conditions are equivalent, and the new one reads more clearly.
Logic gates
In hardware, connectives are built as gates, tiny circuits with input and output wires. AND, OR and NOT match conjunction, disjunction and negation. Three more are common: NAND is NOT AND, NOR is NOT OR, and XOR, exclusive or, outputs 1 when exactly one input is 1.
Worked example: everything from NAND
Show that NAND gates alone can build NOT, AND and OR. 1. NOT: A NAND A is \(\neg(A \wedge A) = \neg A\). 2. AND: A AND B is the negation of A NAND B, so feed A NAND B into both inputs of another NAND: (A NAND B) NAND (A NAND B). 3. OR: by De Morgan's law, \(A \vee B \equiv \neg(\neg A \wedge \neg B)\), which is (NOT A) NAND (NOT B), that is (A NAND A) NAND (B NAND B). 4. Check OR with A = 0 and B = 0: both inner NANDs give 1, and 1 NAND 1 = 0, correct. Because NAND can build every gate, it is called universal; NOR is universal too.
From truth table to circuit
Any truth table can be turned into a circuit. For each row whose output is 1, write an AND of the inputs, negating those that are 0; then OR these terms together. Take the majority function of three inputs, which outputs 1 when at least two inputs are 1. Its 1-rows are 011, 101, 110 and 111, giving four AND terms. Using the laws of logic, these simplify to (A AND B) OR (A AND C) OR (B AND C). Designers simplify in this way because fewer gates make a chip cheaper, faster and less power-hungry.
Exclusive or and binary addition
XOR matches everyday either-or: \(A \oplus B \equiv (A \vee B) \wedge \neg(A \wedge B)\). It is the heart of binary addition. Adding two bits gives a sum bit, A XOR B, and a carry bit, A AND B; this circuit is a half adder. For 1 + 1 the sum bit is 0 and the carry is 1, which is binary 10, the number 2. XOR also undoes itself: applying the same key twice restores the original. With data 1011 and key 0110, 1011 XOR 0110 = 1101, and 1101 XOR 0110 = 1011 again. That property underlies simple encryption, and XOR also computes the parity bits used to detect errors.
Satisfiability
A formula is satisfiable if some assignment of truth values makes it true. Take \((A \vee B) \wedge (\neg A \vee C) \wedge \neg C\). The last part forces C false; then \(\neg A \vee C\) forces A false; then \(A \vee B\) forces B true. So A false, B true, C false satisfies it. A contradiction such as \(P \wedge \neg P\) is unsatisfiable. Deciding satisfiability, the SAT problem, was the first problem shown to be NP-complete, by Stephen Cook in 1971, and no fast method is known for every case. Even so, modern SAT solvers settle huge practical instances and are used to verify chip designs and build schedules.
Logic in database queries
Database queries select records with logical conditions. In SQL, AND binds more tightly than OR, so "WHERE country = 'Japan' AND age < 30 OR student = TRUE" means "(country = 'Japan' AND age < 30) OR student = TRUE": it returns every student in the table, wherever they live, not just young people in Japan. If the intended query was Japanese residents who are under 30 or students, write "WHERE country = 'Japan' AND (age < 30 OR student = TRUE)". When in doubt, add parentheses.
Program correctness
Programmers state what code should do as logical statements about its variables. A precondition must hold before the code runs, and a postcondition must hold after it; the claim is the implication "if the precondition holds, then the postcondition holds when the code finishes". For a loop, a loop invariant is a statement true before every pass. For a loop adding the items of a list, the invariant is "total equals the sum of the items seen so far". Showing that an invariant holds at the start and is kept by each pass is a form of proof by induction, the subject of the topic Proof by induction.
Common mistakes to avoid
First, negating "A and B" in code as "not A and not B"; De Morgan's law gives "not A or not B". Second, negating "age >= 18" as "age <= 18" instead of "age < 18". Third, assuming OR in code is exclusive; it is inclusive, and XOR is a separate operation. Fourth, forgetting that AND binds more tightly than OR in Python and SQL. Fifth, relying on the right side of a short-circuited condition always running. Sixth, thinking an unsatisfiable formula is merely hard to satisfy; it is false in every row.
Key takeaways
Bits make logic physical: 1 is true and 0 is false. Code conditions use AND, OR and NOT with fixed precedence and often short-circuit evaluation, and De Morgan's laws rewrite them safely. Gates implement connectives; NAND alone is universal, and any truth table becomes a circuit by ORing one AND term per 1-row, then simplifying. XOR gives the sum bit of binary addition and undoes itself. SAT asks whether a formula can be made true: hard in general, yet solved at scale in practice. Queries need parentheses, and preconditions, postconditions and loop invariants express program correctness.
Flashcards
Flashcard
True (1) or false (0)
Test your understanding
Question 1 of 5
Which expression is equivalent to NOT (A OR B)?
Question 2 of 5
In Python, how is the condition x > 3 or y > 3 and z > 3 evaluated?
Question 3 of 5
A half adder receives the bits A = 1 and B = 1. What are its outputs?
Question 4 of 5
Which formula is unsatisfiable?
Question 5 of 5
Using NAND gates only, which expression equals NOT A?
