Statements have associated with them truth sets, for which the statement is true, when an element from the truth set is bound to the statement's variables. For S2, the truth set is empty. A statement is said to be satisfied by an assignment if the assignment is in the truth set, that is, if substitution of the values in the assignment for the variables in the statement produces a true statement. A binary relation R is just a set of ordered pairs, R contained in A X B. Often A and B are the same set. Some properties a relation may have are listed below.
Equivalence relations are especially important, and they partition a set into disjoint parts.
A function is a special type of relation, one for which the second element of each pair is uniquely determined by the first element. The range R of f, given a domain A, is the subset of the codomain B of the images of the elements of A under f. It cannot be stressed too strongly that these properties are relative to the domain and codomain defined. Languages Languages are sets of strings over a finite alphabet. Two important language operations are defined below.