This appendix gives some definitions of fundamental mathematical concepts that are used in AI, but are traditionally taught in other courses. It also introduces some notation and data structures that are used in various parts of the book.

Discrete Mathematics

The mathematical concepts we build on include:

sets A set has elements (members). We write s ∈ S if s is an element of set S. The elements in a set define the set, so that two sets are equal if they have the same elements.

tuples An n-tuple is an ordered grouping of n elements, written 〈x1, …, xn〉. A 2-tuple is a pair, and a 3-tuple is a triple. Two n-tuples are equal if they have the same members in the corresponding positions. If S is a set, Sn is the set of n-tuples 〈x1, …, xn〉 where xi is a member of S. S1 × S2 × ··· × Sn is the set of n-tuples 〈x1, …, xn〉 where each xi is in Si.

relations A relation is a set of n-tuples. The tuples in the relation are said to be true of the relation.

functions A function, or mapping, f from set D, the domain of f, into set R, the range of f, written f : D → R, is a subset of D × R such that for every d ∈ D there is a unique r ∈ R such that 〈d, r〉 ∈ f.