Last time we covered the "rules of the game" for first-order logic. Now it's time to play it. We'll cover how to translate complex statements into first-order logic, explore the nuances of nested quantifiers, and discuss how to negate formulas.
Readings
File Attachments
Lecture Recording
The complete archive of this quarter's lecture recordings is available on Canvas.
đź“ť Lecture Summary and Key Take-Aways
The Aristotelian Forms:
- It's worth committing these patterns to memory. They form the backbone of many first-order logic translations.
| English | First-Order Logic |
| “All As are Bs.” | $\forall x. (A(x) \rightarrow B(x))$ |
| “No As are Bs.” | $\forall x. (A(x) \rightarrow \neg B(x))$ |
| “Some As are Bs.” | $\exists x. (A(x) \wedge B(x))$ |
| “Some As aren’t Bs.” | $\exists x. (A(x) \wedge \neg B(x))$ |
Key translation examples:
- “Every person loves someone else.”
$\forall p. (Person(p) \rightarrow$
$\exists q. (Person(q) \wedge p \neq q \text{ } \wedge$
$Loves(p, q)$
$)$
$)$
- “There is a person whom everyone else loves.”
$\exists p. (Person(p) \text{ } \wedge$
$\forall q. (Person(q) \wedge p \neq q \text{ } \rightarrow$
$Loves(q, p)$
$)$
$)$
- “For every natural number $m$, there's a larger natural number $n$.” (true)
$\forall m. \exists n. m < n$
- “There is a natural number $n$ that's larger than every natural number $m$.” (false)
$\exists n. \forall m. m < n$
Key take-aways from the translation examples above:
-
Note that changing the order of our quantifiers produces drastically different meanings in these statements.
-
Note that because of operator precedence, the major connective for the universal quantifier in the second FOL example above is implication ($\rightarrow$), not conjunction ($\wedge$). The expression is of the form $\forall x. r \wedge s \rightarrow t$, which is equivalent to $\forall x. (r \wedge s) \rightarrow t$.
-
The statement $\forall x. \exists y. P(x, y)$ means, "for any choice of $x$, there's some choice of $y$ where P(x, y) is true." The choice of $y$ can be different every time and can depend on $x$.
-
The statement $\exists x. \forall y. P(x, y)$ means, "there is some $x$ where for any choice of $y$, we get that P(x, y) is true." Since the inner part has to work for any choice of $y$, this places a lot of constraints on what $x$ can be.
-
Among the most important things to take away from today's lecture were the process and intuitions we explored for translating from English to FOL. For that, be sure to refer back to today's extended lecture slides, the lecture video, and the supplemental documents linked at the top of this page.
Negation Mechanics (✨ An Extremely Important Table ✨)
| When is this true? | When is this false? | |
| $\forall x. P(x)$ | For all objects x, P(x) is true. | $\exists x. \neg P(x)$ |
| $\exists x. P(x)$ | There is an x where P(x) is true. | $\forall x. \neg P(x)$ |
| $\forall x. \neg P(x)$ | For all objects x, P(x) is false. | $\exists x. P(x)$ |
| $\exists x. \neg P(x)$ | There is an x where P(x) is false. | $\forall x. P(x)$ |
- A key take-away here is that we have the following equivalences that can be applied fairly mechanically when negating statements in FOL. Simply push the negation across the quantifier and change the quantifier from $\forall$ to $\exists$ (or vice-versa):
$\neg \forall x. A$ is equivalent to $\exists x. \neg A$
$\neg \exists x. A$ is equivalent to $\forall x. \neg A$
Two other incredibly useful equivalences:
- The following come up all the time when negating statements in FOL because of our penchant for using conjunction with existentials ($\exists x. A(x) \wedge B(x)$) and implication with universals ($\forall x. A(x) \rightarrow B(x)$):
$\neg (p \wedge q)$ is equivalent to $p \rightarrow \neg q$
$\neg (p \rightarrow q)$ is equivalent to $p \wedge \neg q$
-
We know from DeMorgan's Laws that we can also write $\neg (p \wedge q)$ as $\neg p \vee \neg q$, but using the forms above helps ensure that we continue to use conjunction with existential quantifiers and implication with universals when performing negations on statements in FOL.
-
For examples and applications, see the lecture slides.
Quantifying over sets:
- We express “for any element $x$ of set $S$, $P(x)$ holds” (which is vacuously true if $S$ is empty) like so:
$\forall x \in S. P(x)$
- We express “there is an element $x$ of set $S$ where $P(x)$ holds” (which is false if $S$ is empty) like so:
$\exists x \in S. P(x)$
Expressing uniqueness:
- Using the predicate
$WayToFindOut(w):$ $w$ is a way to find out,
we can express “there is only one way to find out” as follows:
$\exists w. (WayToFindOut(w) \text{ } \wedge$
$\forall x. (WayToFindOut(x) \rightarrow x = w)$
$)$
- See today's extended slide deck (and/or today's lecture) for the derivation.