Predicate Logic
Problem with propositional logic: how does one say, "Everyone in this class is a student"?- not very useful to use that as a proposition: it says too much!
- propositions should talk about one thing: "person $X$ is in this class", "person $X$ is a student"
- so we could say "$X_1$ is in this class $\wedge$ $X_1$ is a student $\wedge$ $X_2$ is in this class $\wedge$ $X_2$ is a student $\wedge \cdots$"
- two propositions per person: this is a lot of work!
Idea: "being a student" and "being in this class" are properties that people can have, and "everyone" quantifies which people have the property. We can define a propositional function that asserts that a predicate is true about some object.
Suppose $S$ denotes the predicate "is a student". Then $S(x)$ means "$x$ is a student" for some object $x$. This works for all predicates: "is greater than", "is shorter than", "is a boat", $\ldots$
Once we have defined a propositional function, any object we give to it produces a truth value. For example, if $P(x)$ means "$x$ is greater than $3$", then:
- $P(2)$ is false
- $P(3)$ is false
- $P(4)$ is true
- $P(1,2)$ is false
- $P(2,1)$ is true
Universe of Discourse
Before we can think about quantifiers, we need to think about the universe of discourse. In the above example about students, there are at least two possible universes of discourse. If the universe is "all people in the class", then saying $x_1$ is in this class" is redundant. However, if the universe of discourse is "all people", then it is important!
As another example, consider $P(x)$ to denote "$x$ is greater than $3$". Here, the universe is assumed to be, say, the set of all real numbers. If the universe of discourse was the set of all people, we would have statements like "John is greater than $3$", which makes no sense.
It is important to define a universe of discourse! Think of the universe of discourse as the set of all values (names) that you can plug into the propositional functions being considered.
Universal Quantification
Given a propositional function $P(x)$, the \emph{universal quantification} of $P(x)$ is the proposition "$P(x)$ is true for all values $x$ in the universe of discourse." We write $\forall x\; {P(x)}$ and say "for all $x$, $P(x)$" or "for every $x$, $P(x)$." The symbol $\forall$ is the universal quantifier.
This notation is essentially shorthand. If the universe of discourse consists of the objects $x_1,x_2,\ldots$, then $\forall x\;{P(x)}$ means $P(x_1) \wedge P(x_2) \wedge \cdots$. Of course, if the universe of discourse is infinite (for example, the integers or real numbers), then such shorthand becomes necessary.
Observe that since $\forall x\;{P(x)}$ is essentially a conjunction, it must be the case that it has truth value $T$ precisely when the predicate is true for all objects in the universe of discourse and $F$ otherwise. Therefore, if the predicate $P$ is false for at least one object in the universe of discourse, then $\forall x\;{P(x)}$ has truth value $F$. Here are some examples that use universal quantification:
- Let $P(x)$ denote "$x$ is greater than $5$", where the universe of discourse is the set of integers. Then the truth value of $\forall x\;{P(x)}$ is $F$, since, for example, $P(4)$ is $F$. Note that if the universe of discourse had been the set of all integers greater than or equal to $6$, then $\forall x \;{P(x)}$ would have truth value $T$.
- Let $P(x)$ denote "$x^2 \ge x$" where the universe of discourse is the set of real numbers. Is $\forall x\;{P(x)}$ true? What if the universe of discourse is the set of integers? Observe that $x^2 \ge x$ if and only if $x^2 - x \ge 0$, which is true if and only if $x(x-1) \ge 0$, which is true if and only if $x \le 0$ or $x \ge 1$. Therefore, if the universe of discourse is the set of real numbers, any real number strictly between $0$ and $1$ gives an example where the statement is false. For example, $(1/2)^2 = 1/4 \lt 1/2$. Therefore, $\forall x\;{P(x)}$ is false if the universe of discourse is the set of real numbers.If the universe of discourse is the set of integers, however, $\forall x\;{P(x)}$ is true, since there is no integer strictly between $0$ and $1$.
Exisential Quantification
Given a propositional function $P(x)$, the existential quantification of $P(x)$ is the proposition "$P(x)$ is true for at least one value $x$ in the universe of discourse." We write $\exists x\;{P(x)}$ and say "there exists an $x$ such that $P(x)$" or "for some $x$, $P(x)$." The symbol $\exists$ is the existential quantifier.
Again, this notation is essentially shorthand. If the universe of discourse consists of the objects $x_1,x_2,\ldots$, then $\exists x \;{P(x)}$ means $P(x_1) \vee P(x_2) \vee \cdots$.
Observe that since $\exists x\;{P(x)}$ is essentially a disjunction, it must be the case that it has truth value $T$ precisely when the predicate is true for at least one object in the universe of discourse and $F$ otherwise. Therefore, if the predicate $P$ is false for all objects in the universe of discourse, then $\exists x\;{P(x)}$ has truth value $F$. Here are some examples that use existential quantification:
- Let $P(x)$ denote "$x$ is greater than $5$", where the universe of discourse is the set of integers. Then the proposition $\exists x\;{P(x)}$ has truth value $T$, since, for example, $P(6)$ is true. If the universe of discourse had been the set of all integers less than or equal to $5$, then $\exists x\;{P(x)}$ would have truth value $F$.
- Let $P(x)$ denote "$x = x + 1$", where the universe of discourse is the set of integers. Then the truth value of $\exists x\;{P(x)}$ is $F$, because no integer has this property (since it implies that $0 = 1$).
Binding of Quantifiers
The scope of a quantifier is the smallest proposition following it: $$ \underbrace{\exists x\;{P(x)}}_{\text{$x$ applies here}} \wedge \underbrace{Q(x)}_{\text{but $x$ has no meaning here}} $$ We would instead write $\exists x\;{(P(x) \wedge Q(x))}$.
It is valid to write, for example, $\exists x\;{P(x)} \wedge \exists x\;{Q(x)}$, but the $x$ in each quantifier could be completely different elements of the universe of discourse! Conversely, we might want to make sure they are not the same: $\exists x \;{\exists y\;{(P(x) \wedge Q(y) \wedge (x \neq y))}}$.
For example, if the universe of discourse is the set of integers, $E(x)$ means "$x$ is a even", and $O(x)$ means "$x$ can odd":
- $\exists x\;{E(x)}$ is true, since (for example) $4$ is an even integer
- $\exists x\;{O(x)}$ is true, since (for example) $3$ is an odd integer
- $\exists x\;{E(x)} \wedge \exists x\;{O(x)}$ is true, since the $x$s can be different
- $\exists x\;{(E(x) \wedge O(x))}$ is false, since no integer is both even and odd
Negating Quantifiers
How do we negate a quantified statement?- What is the negation of "all people like math"?
- "it is not the case that all people like math"
- $\equiv$ true when at least one person does not like math
- $\equiv$ there exists one person who does not like math
- What is the negation of "at least one person likes math"?
- "it is not the case that at least one person likes math"
- $\equiv$ true when there are no people who like math
- $\equiv$ every person does not like math
We have the following quantifier negation rules:
- $\neg \forall x\;{P(x)} \equiv \exists x\;{\neg P(x)}$
- $\neg \exists x\;{P(x)} \equiv \forall x\;{\neg P(x)}$
- The negation of $\forall x\;{(x^2 > x)}$ is $\neg \forall x\;{(x^2 > x)} \equiv \exists x\;{\neg(x^2 > x)} \equiv \exists x\;{(x^2 \le x)}$
- Then negation of $\exists x\;{(x^2 = 2)}$ is $\neg \exists x\;{(x^2 = 2)} \equiv \forall x\;{\neg(x^2 = 2)} \equiv \forall x\;{(x^2 \neq 2)}$
Translating Sentences with Predicates and Quantifiers
- Universal quantifiers: look for keywords like "every", "all"
- Existential quantifiers: look for keywords like "some", "at least one"
- "Every student in this class will learn about logic"
- Let $S(x)$ denote "$x$ is a student in this class" and $L(x)$ denote "$x$ will learn about logic".
- The sentence is $\forall x\;{(S(x) \rightarrow L(x))}$.
- Note: the answer is not $\forall x\;{S(x)} \rightarrow L(x)$ because the $x$ in $L(x)$ is not bound.
- Note: the answer is not $\forall x\;{(S(x) \wedge L(x))}$ because this is saying every person is a student in this class and will learn about logic (too strong!)
- "Some student in this class will learn about calculus"
- Let $S(x)$ denote "$x$ is a student in this class" and $C(x)$ denote "$x$ will learn about calculus".
- The sentence is $\exists x\;{(S(x) \wedge C(x))}$.
- Note: the answer is not $\exists x\;{S(x)} \wedge L(x)$ because the $x$ in $C(x)$ is not bound.
- Note: the answer is not $\exists x\;{(S(x) \rightarrow C(x))}$ because this does not assert the existence of any students in this class (too weak!)
- Let $I(x)$ denote "$x$ is an instructor" and $K(x)$ denote "$x$ knows everything." Then the statement "no instructor knows everything" can be translated as $\neg \exists x\;{(I(x) \wedge K(x))}$.
- We can apply quantifier negation to this to get $\forall x\;{\neg(I(x) \wedge K(x))}$.
- Applying De Morgan's Law, we get $\forall x\;{(\neg I(x) \vee \neg K(x))}$.
- Applying Implication Equivalence, we get $\forall x\;{(I(x) \rightarrow \neg K(x))}$ ("if you are an instructor, then you don't know everything").
- The statement "some instructors don't know everything" can be translated as $\exists x\;{(I(x) \wedge \neg K(x))}$.
- Let $F(x,y)$ denote "$x$ and $y$ are friends." Then $\forall a\;{\exists b\;{F(a,b)}}$ means "everyone has at least one friend." Note that this is not the same as $\exists b\;{\forall a\;{F(a,b)}}$, since this means "there is one person who is friends with everyone."
- Let $M(x)$ denote "$x$ is male", $F(x)$ denote "$x$ is female", $L(x)$ denote "$x$ is a student in this class" and $K(x,y)$ denote "$x$ knows $y$." Then the statement "every female student in this class knows at least one male student in this class" can be translated as $\forall x\;{((F(x) \wedge L(x)) \rightarrow \exists y\;{(M(y) \wedge L(y) \wedge K(x,y))})}$.
- Let the universe of discourse be all Olympic athletes. Let $D(x)$ denote "$x$ uses performance enhancing drugs" and $M(x)$ denote "$x$ wins a medal." The direct translation of $\neg \forall x\;{(\neg M(x) \rightarrow \neg D(x))}$ is awkward. Applying some logical equivalences, we get \begin{array}{llll} \neg \forall x\;{(\neg M(x) \rightarrow \neg D(x))}$ & \equiv & \exists x\;{\neg(\neg M(x) \rightarrow \neg D(x))} & \text{Quantifier Negation} \\ & \equiv & \exists x\;{\neg(\neg \neg M(x) \vee \neg D(x))} & \text{Implication Equivalence} \\ & \equiv & \exists x\;{(\neg \neg \neg M(x) \wedge \neg \neg D(x))} & \text{De Morgan's Law} \\ & \equiv & \exists x\;{(\neg M(x) \wedge D(x))} & \text{Double Negation Law} \\ \end{array} This translates much more cleanly to "there is at least one olympic athlete who uses performance enhancing drugs but does not win a medal."
- Let the universe of discourse be all people. Let $F(x)$ denote "$x$ is female", $P(x)$ denote "$x$ is a parent" and $M(x,y)$ denote "$x$ is the mother of $y$." Then the statement "if a person is female and a parent, then that person is someone's mother" can be translated as $\forall x\;{((F(x) \wedge P(x)) \rightarrow \exists y\;{M(x,y)})}$, or equivalently, $\forall x\;{\exists y\;{((F(x) \wedge P(x)) \rightarrow M(x,y))}}$.
- Let the universe of discourse be all people and let $B(x,y)$ denote "$y$ is the best friend of $x$." To translate the statement "everyone has exactly one best friend", note that to have exactly one best friend, say $y$, then no other person $z$ is that person's best friend, unless $y = z$. The statement can therefore be translated as $\forall x\;{\exists y\;{(B(x,y) \wedge \forall z\;{((z \neq y) \rightarrow \neg B(x,z)))}}}$.