Functions

Math for CS · Axiom Academy

The formal definition of a function: domain, codomain, range, and notation Total: Every element in A must be mapped somewhere (no inputs without outputs) Well-defined: Each input maps to exactly one output (no input maps to two different outputs) Here f(1) = a , f(2) = a , f(3) = c . Two inputs can map to the same output — that is fine. But each input has exactly one arrow leaving it. The range is always a subset of the codomain, but may not equal it. In the diagram above, the codomain is \ a,b,c\ but the range is \ a,c\ since b is never hit. There are several ways to specify a function: The pair notation makes explicit that a function is a set of ordered pairs where no two pairs share the same first element. A relation R A B fails to be a function if: Missing input: Some a A has no pair (a, b) in R Ambiguous output: Some a A has two pairs (a, b_1) and (a, b_2) with b_1 b_2 Functions appear throughout CS under different names: Three functions used constantly in CS: Floor determines how many pages you need: if you have 47 items and 10 per page, you need 47/10 = 5 pages. Modulo drives hash tables, cyclic buffers, and clock arithmetic. A function f: A B maps each input in A to exactly one output in B Domain = inputs, Codomain = potential outputs, Range = actual outputs A function is a set of ordered pairs with unique first elements Hash functions, type conversions, and array lookups are all functions Floor, ceiling, and modulo are essential CS functions

This is the written version of the interactive lesson above. See the full Math for CS course.