Sets, relations, logic & proof

Sets are the vocabulary of computer science: a set is a collection of distinct objects, and almost every CS idea — a database table, a language, a state space — is a set with structure on it. A relation between sets A and B is simply a subset of the Cartesian product A x B, and a function is a special relation in which every element of A is paired with exactly one element of B. Worked example: if |A| = 3 and |B| = 2, then |A x B| = 6, the number of relations from A to B is 2^6 = 64, and the number of functions from A to B is 2^3 = 8, because each of the 3 inputs independently chooses one of 2 outputs. Logic gives us the language for reasoning about such structures: a proposition has a truth value, connectives build compound propositions, and a proof turns a claim into a certainty.