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).
| Input | Output | ||
| \(V(x)\) | \(N(x)\) | \(Mystery(x)\) | |
| \(x\) | \([x]_{2c,3} > 0\) | \([x]_{2c,3} < 0\) | |
| \(000\) | \(F\) | \(T\) | |
| \(001\) | \(T\) | \(T\) | |
| \(010\) | \(T\) | \(T\) | |
| \(011\) | \(T\) | \(F\) | |
| \(100\) | \(F\) | \(F\) | |
| \(101\) | \(F\) | \(T\) | |
| \(110\) | \(F\) | \(F\) | |
| \(111\) | \(F\) | \(T\) | |
The domain for each of the predicates \(V(x)\), \(N(x)\), \(Mystery(x)\) is .
Fill in the table of values for the predicate \(N(x)\) based on the formula given.
Definition: The truth set of a predicate is the collection of all elements in its domain where the predicate evaluates to \(T\).
Notice that specifying the domain and the truth set is sufficient for defining a predicate.
The truth set for the predicate \(V(x)\) is \(\underline{\phantom{\{ x ~\mid~ V(x) = T\} = \{ 001, 010, 011 \}}}\).
The truth set for the predicate \(N(x)\) is \(\underline{\phantom{\{ x ~\mid~ N(x) = T\} = \{ 101, 111 \}}}\).
The truth set for the predicate \(Mystery(x)\) is \(\underline{\phantom{\{ x ~\mid~ Mystery(x) = T\} = \{ 000, 001, 010, 101, 111 \}}}\).
Example predicates on \(S\), the set of RNA strands (an infinite set)
\(H: S \to \{T, F\}\) where \(H(s) = T\) for all \(s\).
Truth set of \(H\) is
\(F_{\texttt{A}}: S \to \{T, F\}\) defined recursively by:
Basis step: \(F_{\texttt{A}}(\texttt{A}) = T\), \(F_{\texttt{A}}(\texttt{C}) = F_{\texttt{A}}(\texttt{G}) = F_{\texttt{A}}(\texttt{U}) = F\)
Recursive step: If \(s \in S\) and \(b \in B\), then \(F_{\texttt{A}}(sb) = F_{\texttt{A}}(s)\).
Example where \(F_{\texttt{A}}\) evaluates to \(T\) is
Example where \(F_{\texttt{A}}\) evaluates to \(F\) is