Math Foundations

Variables that are true or false, joined by not, and, or, if-then, and iff. A truth table lists every world and evaluates the formula in each: what is always true, never true, or sometimes true.

Every formula can be rewritten as an and of or-clauses, or an or of and-terms. Read the form off the truth table, or rewrite with De Morgan and distribution; CNF is the shape a SAT solver takes.

Is there an assignment that makes every clause true? Propagate what the clauses force, guess only when nothing is forced, and back out of a dead branch: the search behind every modern solver.

Start from the facts and fire each rule whose premises are known, until the goal appears or nothing new follows. For Horn clauses that is linear, sound, and complete: the heart of a rule engine.

Add the goal's negation to the clauses and resolve clashing pairs until the empty clause appears. One rule, complete for propositional logic, and the engine beneath every theorem prover and Prolog.

Relations over objects, variables bound by for-all and there-exists, and truth decided by checking a formula against a model. Why swapping two quantifiers changes the answer, one lookup at a time.

Find the bindings that make two terms with variables identical, and the most general ones. Robinson's algorithm, pair by pair, with the occurs check that keeps the answer finite.

Every number lands on an hour of a clock with m hours, and sums, products, and powers stay there. Squaring takes a 300-bit power in 600 steps; Fermat's theorem tells a prime clock from a composite.

Divide the larger by the smaller, keep the remainder, repeat: the last divisor is the gcd. Run backwards, the divisions write it as ax + my, and when it is 1, x is the inverse of a on the clock.

Find the bottom of a bowl you cannot see: measure the slope where you stand, step against it, repeat. The learning rate decides whether you crawl, arrive, bounce, or fly off.

A rare symbol tells you more than a common one. Price each symbol at minus log2 of its probability, weigh the prices by how often they are paid: the average is the entropy, the bits a source is worth.

Code words that decode without separators are paths in a tree. Kraft's inequality says which lengths fit, and the cost of any such code sits above the entropy; Shannon's lengths come within a bit.

A code built for the wrong distribution charges the wrong prices. The bits it wastes per symbol is the KL divergence: cross-entropy minus entropy, never negative, zero only when the model is right.

How far a joint table is from the product of its margins: the bits one variable tells you about another. Zero when they are independent, and the overlap of their entropies otherwise.

A wire that flips bits at random still carries information, and how much has a formula: the mutual information of input and output at its peak, 1 minus H(f) for a wire that flips with probability f.

Four-bit strings add without carries and multiply as polynomials reduced by a fixed quartic. Every nonzero element is a power of x, so a log table turns products into sums and every element divides.