6.042J Lecture Notes - Lecture 4: Binary Relation, Partial Function, Total Relation
Document Summary
A function assigns an element of one set (the domain) to an element of another set (the codomain) The notation : a > b indicated that is a function with domain a and codomain b. The familiar notation f(a) = b indicated that assigns the element b b to a. A function can be described in logic terms: (p, q) ::= [p implies q] A function might also be de ned by a procedure for computing its value at any element of its domain or by some other kind of speci cation. For example, de ne (y) to be length of a left to right search of the bits in the binary string unit a 1 appears. So, (0010) = 3, (100) = 1, (0000) is unde ned. Functions may be partial functions, meaning that there may be domain elements for which the function is not de ned.