Why logic and proof matter in computing

Most of computing science rests on a small set of mathematical ideas: statements that are true or false, rules for combining them, collections of objects, relationships between objects, and arguments that establish facts once and for all. This course, Logic and Discrete Structures, gives you those ideas and the habit of using them carefully. It follows CMPUT-174, where you learned to write and test Python programs, and it prepares you for CMPUT-204 (Algorithms I), where you will prove that algorithms are correct and analyze how fast they run, and for CMPUT-474 (Theory of Computation), where you will meet the limits of what any computer can do.

The word discrete is the key. Calculus studies continuous quantities that change smoothly. Computers, by contrast, work with values that come in separate, countable pieces: bits, integers, characters, list positions, nodes in a network, steps of an algorithm. Discrete mathematics is the mathematics of those countable things. You already used it informally in CMPUT-174 when you counted the comparisons a search made or reasoned about which branch of an if statement would run. Here you will learn to make that reasoning precise.

Testing shows the presence of bugs, proof shows their absence

In CMPUT-174 you tested programs by choosing inputs and checking outputs. Testing is essential, but it has a hard limit. A function that takes a single 64-bit integer has about \(1.8 \times 10^{19}\) possible inputs. Even at a billion tests per second, checking them all would take more than 500 years. A function of two such integers is hopeless. The computer scientist Edsger Dijkstra put it bluntly: testing can show the presence of bugs, but never their absence.

A proof is different. It is an argument that a statement holds for every case it covers, including the cases nobody tried. When you prove that a loop computes the sum of a list for every list, you have covered infinitely many inputs with a finite argument. That is why proof matters in computing: it is the only tool that gives certainty about unbounded sets of inputs.

# A plausible conjecture that testing seems to confirm
def f(n):
    return n * n + n + 41

def is_prime(m):
    if m < 2:
        return False
    d = 2
    while d * d <= m:
        if m % d == 0:
            return False
        d += 1
    return True

all_prime = all(is_prime(f(n)) for n in range(40))
print("f(n) prime for n = 0..39:", all_prime)
print("f(40) =", f(40), "prime?", is_prime(f(40)))
print("41 * 41 =", 41 * 41)

f(n) prime for n = 0..39: True
f(40) = 1681 prime? False
41 * 41 = 1681

The polynomial \(n^2 + n + 41\), studied by Euler, produces a prime number for every \(n\) from 0 to 39. A tester who checked those forty cases might conclude that it always produces primes. The forty-first case fails: \(f(40) = 40^2 + 40 + 41 = 1681 = 41^2\). In fact a short argument shows it must fail at \(n = 40\), because \(40 \cdot 40 + 40 + 41 = 40 \cdot 41 + 41 = 41 \cdot 41\). A single counterexample settles the question; no number of confirming examples could.

Where logic appears in everyday computing

Logic is not an abstract extra. It is built into the tools you already use, and the better you understand it the fewer mistakes you make with those tools.

Observe how often the same ideas recur. A SQL query that asks for every customer who has placed at least one order uses an existential quantifier (lesson 4). A database table is a relation in exactly the mathematical sense of lesson 9. A hash table distributes keys using modular arithmetic (lesson 11). A recursive function is correct for the same reason an inductive proof works (lesson 10). Learning the mathematics once lets you recognize it everywhere.

Statements, definitions and theorems

Mathematical writing has a vocabulary of its own, and reading proofs is much easier once you know it. A definition gives a precise meaning to a word: for example, an integer \(n\) is even if there is an integer \(k\) with \(n = 2k\). Definitions are not true or false; they are agreements. A theorem is a statement that has been proved from definitions and previously established facts. A lemma is a smaller theorem proved mainly to help prove a larger one, and a corollary is a statement that follows quickly from a theorem. A conjecture is a statement believed to be true but not yet proved, like the claim about \(n^2 + n + 41\) before we found the counterexample.

Every proof starts from definitions. When you are stuck on a proof, the most useful question is almost always: what exactly do the words in this statement mean? Writing out the definitions turns a vague claim into concrete equations or conditions you can manipulate.

How this course works

The course moves from logic, to proof, to structures, to counting, and finishes by applying everything to programs. Each lesson has worked examples and short Python programs that let you experiment. Python is used as a laboratory: it can check a truth table, search for a counterexample or count the elements of a set. It cannot replace proof, but it can quickly tell you whether a claim is worth trying to prove.

Mathematical notation can look intimidating at first. Each symbol in this course is introduced with a plain-language reading. For example, \(\forall x\, P(x)\) is read as for every x, P of x, and \(A \subseteq B\) is read as A is a subset of B. When you meet a formula, read it aloud in words before trying to work with it. A good habit is to translate every line of a proof into an ordinary sentence; if you cannot, you have found the line you do not yet understand.

Using Python to explore, not to prove

A computer is an excellent partner for discrete mathematics because it can enumerate small cases quickly. Suppose someone claims that for every positive integer \(n\), the number \(2^n\) is greater than \(n^2\). Before trying to prove it, check small values.

for n in range(1, 11):
    print(f"n = {n:2d}   2**n = {2**n:5d}   n**2 = {n*n:4d}   2**n > n**2: {2**n > n*n}")

n =  1   2**n =     2   n**2 =    1   2**n > n**2: True
n =  2   2**n =     4   n**2 =    4   2**n > n**2: False
n =  3   2**n =     8   n**2 =    9   2**n > n**2: False
n =  4   2**n =    16   n**2 =   16   2**n > n**2: False
n =  5   2**n =    32   n**2 =   25   2**n > n**2: True
n =  6   2**n =    64   n**2 =   36   2**n > n**2: True
n =  7   2**n =   128   n**2 =   49   2**n > n**2: True
n =  8   2**n =   256   n**2 =   64   2**n > n**2: True
n =  9   2**n =   512   n**2 =   81   2**n > n**2: True
n = 10   2**n =  1024   n**2 =  100   2**n > n**2: True

The table shows the claim is false as stated: it holds for \(n = 1\) but fails at \(n = 2\), 3 and 4, then holds from \(n = 5\) onward. Exploration has told us what to prove: for every integer \(n \ge 5\), \(2^n > n^2\). That corrected statement is true, and in lesson 10 you will prove it by induction. This pattern of explore, conjecture, then prove is how mathematicians and computer scientists actually work.

Precision in language

Ordinary language is ambiguous in ways that matter for computing. Consider a requirement written as: users may log in with a password or a security key and a one-time code. Does the one-time code apply to both methods, or only to the security key? The sentence can be read as (password or key) and code, or as password or (key and code). A system built on the wrong reading is a security flaw. Logic gives us notation with exactly one reading, and lesson 2 will make the precedence rules explicit.

Similarly, everyday English uses or in two senses. Would you like tea or coffee usually means one or the other but not both, the exclusive or. In logic and programming, or is inclusive: true when either or both parts are true. Many arguments in specifications, contracts and bug reports come down to this distinction.

Proof as communication

A proof is written for a reader. In professional work that reader might be a colleague reviewing an algorithm, an auditor checking a safety argument, or your future self. A good proof states what is being proved, says which technique it uses, introduces every variable before using it, and justifies each step by a definition, an earlier result or algebra. It ends by saying clearly that the goal has been reached. In this course you will practice writing proofs in complete sentences, which is the standard expected in later courses and in research.

Computer science has also built tools that check proofs mechanically. Proof assistants such as Coq, Isabelle and Lean have been used to verify a C compiler (CompCert), an operating system microkernel (seL4) and large parts of mathematics. Satisfiability solvers, which you will meet in lesson 3, routinely check hardware designs with millions of logic gates. These tools rely on exactly the logic you will learn here, applied at enormous scale.