Distributed Algorithms Contents Index

Review of Predicates

A predicate is a function from a set of objects to the Boolean constants \(\{True, False\}\). The set of objects is referred to as the universal set. In this course we restrict attention to objects that are states of a system. To begin with consider an example in which the universal set, \(V\), is the set of the following three students:

  1. name: Maya, age: 19, major: CS
  2. name: Liu, age: 20, major: Physics
  3. name: Eve, age: 21, major: CS

\(age > 19\) is a predicate because it is a function from elements of the set to \(\{True, False\}\). The result of applying this function to (Maya, 19, CS) is False, while applying this function to (Liu, 20, Physics) returns True.

Extension or Truth Set of a Predicate

A predicate \(R\) defines a set \(\{v | R(v) \}\) called its extension or its truth set. In the example, the extension of the predicate \(age > 19\) is the set \(\{ (Liu, 20, Physics), (Eve, 21, CS) \}\).

Predicates can be composed using Boolean operators. For a predicate \(X\), let \(e(X)\) denote its extension. Here are examples of extensions.

Examples

\( e((age > 19) \wedge (major = CS)) \; = \; e(age > 19) \cap e(major = CS) \)

So, \( e((age > 19) \wedge (major = CS)) \; = \; \{(Eve, 21, CS)\} \)

\( e((age > 20) \vee (major = physics)) = \{(Liu, 20, Physics), (Eve, 21, CS)\} \)

\( e(\neg (major = physics)) = \{(Maya, 19, CS), (Eve, 21, CS)\} \)

True, can be viewed as a predicate whose extension is the entire universal set \(V\). Similarly, False can be viewed as a predicate whose extension is the empty set.

Implication

\(P \Rightarrow Q\) is a predicate which is equivalent to \(\neg P \vee Q\).

Example

\((major = CS) \; \Rightarrow \; (age < 20) \) is a predicate which when applied to Maya is True; when applied to Liu is also True because the antecedent \(major = CS\) doesn't hold for Liu; and when applied to Eve is False because the antecedent is True whereas the consequent, \(age < 20\), is False.

Formula as a Predicate or a Boolean

We use Edsger W. Dijkstra's notation of square brackets, \([P]\), to refer to the boolean: \(P\) is universally True which means that the the extension of \(P\) is the universal set.

Example

\([(major = CS) \; \Rightarrow \; (age < 22)] \)

is a boolean - note the square brackets. It's value is the boolean constant, True, exactly when the formula holds universally. In our example, the predicate \((major = CS) \; \Rightarrow \; (age < 22)\) holds for all elements - Maya, Liu, and Eve. So, the boolean, \([(major = CS) \; \Rightarrow \; (age < 22)] \) is True.

Example

\(\neg [(major = CS) \; \Rightarrow \; (age < 20)] \)

because \((major = CS) \; \Rightarrow \; (age < 20)\) applied to Eve is False, and so the predicate is not universally True.

Equivalence

\(P \equiv Q\) is a predicate which holds exactly when both \(P\) and \(Q\) are True, or both are False.

\( (P \equiv Q) \quad \equiv \quad (P \wedge Q) \vee (\neg P \wedge \neg Q) \)

We usually use equivalence in formula that are universally True, denoted by \([P \equiv Q]\).

Example

Let \(odd\) be a function on integers that returns True exactly when the integer is an odd number.

\( odd(age) \; \equiv \; (major = CS) \)

is a predicate which when applied to Maya and Eve return True because both sides of the equivalence are True; and when applied to Liu returns True because both sides of the equivalence are False. Since the extension of this predicate is the universal set, we write:

\([odd(age) \; \equiv \; (major = CS)]\)

Predicates on States

This module is a review of predicates on states of programs.

In this course, a predicate is a function from states of a program to the Boolean constants \(\{True, False\}\). For example, for a program with variables x, y, the predicate x > y is true in the state (x, y) = (1, 0) and is false in the state (x, y) = (1, 1).

For a predicate \(P\) and a state \(s\), the value of the predicate at state \(s\) is written \(P(s)\), which is a Boolean. We say that "\(P\) holds in state \(s\)" exactly when \(P(s)\) is True.

Boolean operators such as disjunction (or) are "lifted" to be operators on predicates: the predicate \(P \vee Q\) holds in a state \(s\) exactly when \(P(s) \vee Q(s)\) holds. Likewise, the predicate \(P \wedge Q\) holds in a state \(s\) exactly when \(P(s) \wedge Q(s)\) holds.

Set of states corresponding to a predicate

Associated with a predicate \(P\) is a set of all the states of a program for which \(P\) holds; this set is called the extension of predicate \(P\) or the truth set of \(P\). The extension of \(P\) is the set \(\{s | P(s)\}\). We use the phrase "set of states corresponding to \(P\)" for the extension of \(P\).

Disjunction, conjunction, and negation of predicates correspond to the union intersection, and complement, respectively, of the corresponding sets of states. Let \(e(P)\) be the extension of \(P\). Then

  1. Disjunction: \(e(P \vee Q) \; = \; e(P) \cup e(Q)\)
  2. Conjunction: \(e(P \wedge Q) \; = \; e(P) \cap e(Q)\)
  3. Negation: \(e(\neg P) \; = \; \overline{e(P)}\)
The module on predicate examples has Venn diagrams illustrating these concepts.

Review

  1. What are predicates on states? What is the extension of a predicate?
  2. What are conjunction, disjunction, and negation of predicates?

K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology