Operations on Predicates and the Parallel with Sets
Learning Objectives
- Extend the five classical connectives to operations on predicates
- Identify the correspondence between predicate operations and set operations
- State and apply De Morgan’s Laws for sets
- Formalise the negation of quantified statements
- Translate freely between logical, predicate, and set-theoretic formulations
Recalling Predicates and Truth Domains
In Unit 1, Lesson 3, we introduced predicates: expressions containing free variables, which become propositions upon substitution of values from a domain of discourse \(\mathcal{D}\). For a unary predicate \(P(x)\), we defined its truth domain as
\[\mathcal{D}_P = \{x \in \mathcal{D} \mid P(x) = T\}\]
— the set of elements of \(\mathcal{D}\) for which \(P\) evaluates to true.
In this lesson we ask: given two predicates \(P(x)\) and \(Q(x)\) over the same domain, what does it mean to combine them with \(\neg\), \(\land\), \(\lor\), \(\to\), or \(\leftrightarrow\)? And what happens to the truth domains when we do?
Operations on Predicates
Let \(P(x)\) and \(Q(x)\) be predicates over a common domain \(\mathcal{D}\). We define their combinations pointwise: for each \(x \in \mathcal{D}\), the value of the compound predicate is obtained by applying the corresponding propositional connective to the truth values \(P(x)\) and \(Q(x)\).
Negation: \((\neg P)(x) \;=\; \neg(P(x))\)
Conjunction: \((P \land Q)(x) \;=\; P(x) \land Q(x)\)
Disjunction: \((P \lor Q)(x) \;=\; P(x) \lor Q(x)\)
Implication: \((P \to Q)(x) \;=\; P(x) \to Q(x)\)
Equivalence: \((P \leftrightarrow Q)(x) \;=\; P(x) \leftrightarrow Q(x)\)
Each of these is again a predicate over \(\mathcal{D}\): upon substituting a concrete element \(a \in \mathcal{D}\), the compound predicate yields a proposition whose truth value is computed by the rules we established in Lessons 1 and 2 of this unit.
Operations on Predicates — Examples
Let \(\mathcal{D} = \mathbb{Z}\). Consider the predicates:
\(P(x)\): “\(x\) is even”
\(Q(x)\): “\(x > 0\)”
Then:
\((\neg P)(x)\): “\(x\) is not even” — equivalently, “\(x\) is odd.”
\((P \land Q)(x)\): “\(x\) is even and \(x > 0\).” Substituting \(x = 4\): \(T \land T = T\). Substituting \(x = -2\): \(T \land F = F\).
\((P \lor Q)(x)\): “\(x\) is even or \(x > 0\).” True for \(x = 3\) (odd but positive), false for \(x = -3\) (odd and negative).
\((P \to Q)(x)\): “If \(x\) is even, then \(x > 0\).” False for \(x = -2\); true for \(x = 4\); vacuously true for \(x = 3\) (since the hypothesis fails).
The Bridge: Predicates as Truth Domains
Every unary predicate \(P(x)\) over a domain \(\mathcal{D}\) determines a subset of \(\mathcal{D}\) — its truth domain \(\mathcal{D}_P\). Conversely, every subset \(A \subseteq \mathcal{D}\) determines a predicate:
\[P_A(x) \;=\; (x \in A)\]
The truth domain of \(P_A\) is precisely \(A\), and the predicate associated with \(\mathcal{D}_P\) is precisely \(P\).
This correspondence — between predicates and subsets — is the key that unlocks the entire parallel between propositional logic and set theory. Every operation we perform on predicates has an exact counterpart performed on their truth domains.
Set Operations
Let \(A, B \subseteq \mathcal{D}\) be subsets of a common domain \(\mathcal{D}\). We recall the fundamental set operations:
Complement (relative to \(\mathcal{D}\)): \(\;\complement_\mathcal{D} A \;=\; \{x \in \mathcal{D} \mid x \notin A\}\)
Intersection: \(\;A \cap B \;=\; \{x \in \mathcal{D} \mid x \in A \text{ and } x \in B\}\)
Union: \(\;A \cup B \;=\; \{x \in \mathcal{D} \mid x \in A \text{ or } x \in B\}\)
When the ambient domain \(\mathcal{D}\) is clear from context, the complement of \(A\) is often written simply as \(A^c\) or \(\overline{A}\).
The Correspondence Between Predicates and Sets
Let \(P\) and \(Q\) be unary predicates over a domain \(\mathcal{D}\), with truth domains \(\mathcal{D}_P\) and \(\mathcal{D}_Q\). Then:
\[\mathcal{D}_{\neg P} \;=\; \complement_\mathcal{D}\,\mathcal{D}_P\]
\[\mathcal{D}_{P \land Q} \;=\; \mathcal{D}_P \cap \mathcal{D}_Q\]
\[\mathcal{D}_{P \lor Q} \;=\; \mathcal{D}_P \cup \mathcal{D}_Q\]
In words:
The truth domain of \(\neg P\) is the complement of the truth domain of \(P\).
The truth domain of \(P \land Q\) is the intersection of their truth domains.
The truth domain of \(P \lor Q\) is the union of their truth domains.
These identities are not merely analogies. They are equalities between sets, and they follow directly from the pointwise definitions of the connectives combined with the definition of truth domain.
Connection to Computer Science
This correspondence is the theoretical foundation of databases. When a database is asked to return the rows satisfying some condition, it is computing the truth domain of a predicate. Combining conditions with “and,” “or,” and “not” corresponds exactly to intersecting, uniting, and complementing subsets — the operations we have just defined.
Verifying the Correspondence
We verify the second identity, \(\mathcal{D}_{P \land Q} = \mathcal{D}_P \cap \mathcal{D}_Q\), by chasing the definitions. An element \(x \in \mathcal{D}\) belongs to \(\mathcal{D}_{P \land Q}\) if and only if \((P \land Q)(x) = T\). By the pointwise definition of \(\land\):
\[(P \land Q)(x) = T \;\iff\; P(x) = T \text{ and } Q(x) = T\]
By the definition of truth domain, \(P(x) = T\) means \(x \in \mathcal{D}_P\), and \(Q(x) = T\) means \(x \in \mathcal{D}_Q\). So:
\[x \in \mathcal{D}_{P \land Q} \;\iff\; x \in \mathcal{D}_P \text{ and } x \in \mathcal{D}_Q \;\iff\; x \in \mathcal{D}_P \cap \mathcal{D}_Q\]
The two sets have the same elements, so they are equal. The other two identities are verified analogously.
A Concrete Illustration
Let \(\mathcal{D} = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}\), \(P(x)\): “\(x\) is even,” and \(Q(x)\): “\(x \geq 5\).”
Truth domains:
\(\mathcal{D}_P = \{2, 4, 6, 8, 10\}\)
\(\mathcal{D}_Q = \{5, 6, 7, 8, 9, 10\}\)
Combinations:
\(\mathcal{D}_{\neg P} = \complement_\mathcal{D}\,\mathcal{D}_P = \{1, 3, 5, 7, 9\}\) — the odd numbers in \(\mathcal{D}\).
\(\mathcal{D}_{P \land Q} = \mathcal{D}_P \cap \mathcal{D}_Q = \{6, 8, 10\}\) — even numbers at least 5.
\(\mathcal{D}_{P \lor Q} = \mathcal{D}_P \cup \mathcal{D}_Q = \{2, 4, 5, 6, 7, 8, 9, 10\}\) — numbers that are even, or at least 5, or both.
De Morgan’s Laws for Sets
For any subsets \(A, B\) of a domain \(\mathcal{D}\):
\[\complement_\mathcal{D}(A \cap B) \;=\; \complement_\mathcal{D}\,A \;\cup\; \complement_\mathcal{D}\,B\]
\[\complement_\mathcal{D}(A \cup B) \;=\; \complement_\mathcal{D}\,A \;\cap\; \complement_\mathcal{D}\,B\]
These laws are the exact set-theoretic counterparts of De Morgan’s Laws for propositions, established in Lesson 3. The parallel is not coincidental: they are the same laws, viewed through the correspondence between predicates and sets.
Connection to Computer Science
De Morgan’s Laws are applied constantly in computing, whenever a system needs to simplify or rewrite a logical condition. Database systems, for instance, use these laws to transform the conditions in a query into forms that can be evaluated more efficiently.
Deriving De Morgan for Sets from De Morgan for Propositions
Let \(P\) and \(Q\) be predicates whose truth domains are \(A = \mathcal{D}_P\) and \(B = \mathcal{D}_Q\). By the correspondence:
\[A \cap B = \mathcal{D}_{P \land Q} \quad \text{and} \quad \complement_\mathcal{D}(A \cap B) = \mathcal{D}_{\neg(P \land Q)}\]
By De Morgan’s Law for propositions:
\[\neg(P \land Q) \;\equiv\; \neg P \lor \neg Q\]
Logically equivalent predicates have equal truth domains. Therefore:
\[\mathcal{D}_{\neg(P \land Q)} = \mathcal{D}_{\neg P \lor \neg Q} = \mathcal{D}_{\neg P} \cup \mathcal{D}_{\neg Q} = \complement_\mathcal{D}\,A \cup \complement_\mathcal{D}\,B\]
Combining the two chains:
\[\complement_\mathcal{D}(A \cap B) \;=\; \complement_\mathcal{D}\,A \cup \complement_\mathcal{D}\,B\]
The derivation of the second De Morgan law for sets from the second De Morgan law for propositions is analogous.
A Dictionary of Correspondences
The relationship between propositional logic, predicates, and sets is summarised in the following dictionary:
Propositional logic | Predicate operation | Set operation |
|---|---|---|
\(\neg P\) | \((\neg P)(x)\) | \(\complement_\mathcal{D}\,\mathcal{D}_P\) |
\(P \land Q\) | \((P \land Q)(x)\) | \(\mathcal{D}_P \cap \mathcal{D}_Q\) |
\(P \lor Q\) | \((P \lor Q)(x)\) | \(\mathcal{D}_P \cup \mathcal{D}_Q\) |
\(P \to Q\) is a tautology | \(P(x) \to Q(x)\) holds for all \(x\) | \(\mathcal{D}_P \subseteq \mathcal{D}_Q\) |
\(P \leftrightarrow Q\) is a tautology | \(P(x) \leftrightarrow Q(x)\) holds for all \(x\) | \(\mathcal{D}_P = \mathcal{D}_Q\) |
The last two rows are particularly useful in mathematical practice: to show that one predicate implies another for all \(x\), one shows that the truth domain of the first is a subset of the truth domain of the second. This is why so much of mathematics reduces, upon close inspection, to proving set inclusions.
Negation of Quantified Statements
Let \(P(x)\) be a predicate over a domain \(\mathcal{D}\). Then:
\[\neg(\forall x \in \mathcal{D},\; P(x)) \;\equiv\; \exists x \in \mathcal{D},\; \neg P(x)\]
\[\neg(\exists x \in \mathcal{D},\; P(x)) \;\equiv\; \forall x \in \mathcal{D},\; \neg P(x)\]
In words:
The negation of “every \(x\) satisfies \(P\)” is “there exists an \(x\) that does not satisfy \(P\).”
The negation of “there exists an \(x\) satisfying \(P\)” is “every \(x\) fails to satisfy \(P\).”
These are often called the quantifier duality laws, or the De Morgan laws for quantifiers — a name that is no accident, as we will see.
Why the Duality Deserves the Name De Morgan
Consider a finite domain \(\mathcal{D} = \{a_1, a_2, \ldots, a_n\}\). On such a domain, universal and existential quantification reduce to finite conjunction and disjunction:
\[\forall x \in \mathcal{D},\; P(x) \;\equiv\; P(a_1) \land P(a_2) \land \cdots \land P(a_n)\]
\[\exists x \in \mathcal{D},\; P(x) \;\equiv\; P(a_1) \lor P(a_2) \lor \cdots \lor P(a_n)\]
Applying De Morgan’s Laws to the negation of a long conjunction produces a disjunction of negations, and vice versa. The quantifier duality is the natural extension of De Morgan’s Laws to arbitrary domains — including infinite ones, where a true conjunction or disjunction over all elements cannot be written out explicitly but the logical behaviour persists.
Connection to Computer Science
Databases make quantifiers explicit in their query languages: there are standard ways to ask “does there exist a row such that...” (existential) or “do all rows satisfy...” (universal). The duality between these two forms is exactly what we have just proved, and it allows a database to rewrite a query from one form into the other when one is cheaper to evaluate.
Negating Quantified Statements — Examples
Original: “\(\forall x \in \mathbb{R},\; x^2 \geq 0\)”
Negation: “\(\exists x \in \mathbb{R},\; x^2 < 0\)”
The original is true, so the negation is false — no real number has a negative square.Original: “\(\exists n \in \mathbb{N},\; n > 1000\)”
Negation: “\(\forall n \in \mathbb{N},\; n \leq 1000\)”
The original is true, so the negation is false.Original: “\(\forall x \in \mathbb{Z},\; x \text{ is even}\)”
Negation: “\(\exists x \in \mathbb{Z},\; x \text{ is odd}\)”
The original is false (counterexample \(x = 3\)); the negation is true.Original: “\(\exists x \in \mathbb{R},\; x^2 = -1\)”
Negation: “\(\forall x \in \mathbb{R},\; x^2 \neq -1\)”
The original is false; the negation is true.
Negating Nested Quantifiers
The duality rules apply one quantifier at a time. To negate a statement with several quantifiers, apply the rules from the outside in, pushing the negation through each quantifier until it reaches the atomic predicate at the core. For example:
\[\neg(\forall x,\, \exists y,\; P(x,y)) \;\equiv\; \exists x,\, \neg(\exists y,\; P(x,y)) \;\equiv\; \exists x,\, \forall y,\; \neg P(x,y)\]
The rule is mechanical: each \(\forall\) flips to \(\exists\), each \(\exists\) flips to \(\forall\), and the negation settles on the innermost predicate. In practice, this is how one formally produces the negation of statements like “every continuous function on a closed interval attains its maximum” or “there exists a prime greater than every given integer.”
Exercise 1
For each scenario, determine the truth domain of the compound predicate.
Exercise 2
For each quantified statement, select its negation.
Exercise 3
Decide whether each statement is true.
A student is asked to negate the statement:
“Every student in the class passed the exam.”
They answer: “No student in the class passed the exam.” Is the negation correct?
Analysis
It is not. The student has produced not the negation, but a far stronger statement — a contrary rather than a contradictory, in the terminology we introduced in Unit 2, Lesson 1.
Let \(\mathcal{D}\) be the class and \(P(x)\): “\(x\) passed the exam.” Then:
The original statement is \(\forall x \in \mathcal{D},\; P(x)\).
The student’s proposed negation is \(\forall x \in \mathcal{D},\; \neg P(x)\) — a universal statement, not an existential one.
The correct negation, by the quantifier duality, is \(\exists x \in \mathcal{D},\; \neg P(x)\) — “there exists at least one student who did not pass.”
Consider a class in which nine out of ten students passed. Then:
The original statement (“every student passed”) is false.
The correct negation (“at least one student did not pass”) is true.
The student’s proposed negation (“no student passed”) is false.
Both the original and the student’s version are false in this scenario — a negation that shares a truth value with the statement it is meant to negate cannot be correct. A proper negation is always true exactly when the original is false.
The deeper lesson: universal statements are refuted by a single counterexample, never by asserting a universal opposite. “Every swan is white” is not refuted by claiming “every swan is non-white.” It is refuted by exhibiting one black swan. The quantifier duality is precisely the formalisation of this fact.
Summary
The five classical connectives extend pointwise to predicates: \((P \land Q)(x) = P(x) \land Q(x)\), and similarly for the others.
Each unary predicate \(P\) over \(\mathcal{D}\) determines a subset \(\mathcal{D}_P \subseteq \mathcal{D}\) (its truth domain), and each subset \(A \subseteq \mathcal{D}\) determines a predicate.
Correspondence: predicate negation is set complement, conjunction is intersection, disjunction is union.
De Morgan’s Laws for sets: \(\complement(A \cap B) = \complement A \cup \complement B\) and \(\complement(A \cup B) = \complement A \cap \complement B\).
Quantifier duality: \(\neg(\forall x,\, P(x)) \equiv \exists x,\, \neg P(x)\) and \(\neg(\exists x,\, P(x)) \equiv \forall x,\, \neg P(x)\).
The quantifier duality is the natural extension of De Morgan to arbitrary domains; on finite domains, it reduces to the propositional De Morgan laws applied to finite conjunctions and disjunctions.
Universal implication \(\forall x,\, P(x) \to Q(x)\) corresponds to set inclusion \(\mathcal{D}_P \subseteq \mathcal{D}_Q\). Universal equivalence corresponds to set equality.