Definition: A predicate is a function from a given set (domain) to \(\{T,F\}\). A predicate can be applied, or evaluated at, an element of the domain. Usually, a predicate describes a property that domain elements may or may not have. Two predicates over the same domain are equivalent means they evaluate to the same truth values for all possible assignments of domain elements to the input. In other words, they are equivalent means that they are equal as functions. To define a predicate, we must specify its domain and its value at each domain element. The rule assigning truth values to domain elements can be specified using a formula, English description, in a table (if the domain is finite), or recursively (if the domain is recursively defined).