40
Formal Logic
The predicates we have seen so far, involving properties of a single variable,
are unary predicates. Predicates can be binary, involving properties of two variables, ternary, involving properties of three variables, or, more generally, n-ary,
involving properties of n variables.
The existential quantifier is symbolized by a backward E, E, and is read
“there exists one,” “for at least one,” or “for some.” Thus the expression
(E x)(x > 0)
is read “there exists an x such that x is greater than zero.”
Again, the truth value of this expression depends on the interpretation. If the
domain of interpretation contains a positive number, the expression has the value
true; otherwise, it has the value false. The truth value of (E x)P(x), if the domain
consists of all the books in your local library and P(x) is the property that x has a
red cover, is true if there is at least one book in the library with a red cover.
ReMIndeR
all, every, each, any—use 4
some, one, at least one—
use E
pRaCtiCe 16
a. Construct an interpretation (i.e., give the domain and the meaning of P(x)) in which (4x)P(x)
has the value true.
b. Construct an interpretation in which (4x)P(x) has the value false.
c. Can you find one interpretation in which both (4x)P(x) is true and (E x)P(x) is false?
d. Can you find one interpretation in which both (4x)P(x) is false and (E x)P(x) is true?
eXAMPLe 20
The expression (4x)(E y)Q(x, y) is read “for every x there exists a y such that
Q(x, y).” Note that there are two quantifiers for the two variables of the binary
property. In the interpretation where the domain consists of the integers and Q(x, y)
is the property that x < y, this just says that for any integer, there is a larger integer.
The truth value of the expression is true. In the same interpretation, the expression
(E y)(4x)Q(x, y) says that there is a single integer y that is larger than any integer x.
The truth value here is false.
pRaCtiCe 15 What is the truth value of the expression (5x)P(x) in each of the following interpretations?
a. P(x) is the property that x is yellow, and the domain of interpretation is the collection of
all daffodils.
b. P(x) is the property that x is yellow, and the domain of interpretation is the collection of all flowers.
c. P(x) is the property that x is a plant, and the domain of interpretation is the collection of all
flowers.
d. P(x) is the property that x is either positive or negative, and the domain of interpretation consists
of the integers.
Example 20 illustrates that the order in which the quantifiers appear is
important.
Formal Logic
The predicates we have seen so far, involving properties of a single variable,
are unary predicates. Predicates can be binary, involving properties of two variables, ternary, involving properties of three variables, or, more generally, n-ary,
involving properties of n variables.
The existential quantifier is symbolized by a backward E, E, and is read
“there exists one,” “for at least one,” or “for some.” Thus the expression
(E x)(x > 0)
is read “there exists an x such that x is greater than zero.”
Again, the truth value of this expression depends on the interpretation. If the
domain of interpretation contains a positive number, the expression has the value
true; otherwise, it has the value false. The truth value of (E x)P(x), if the domain
consists of all the books in your local library and P(x) is the property that x has a
red cover, is true if there is at least one book in the library with a red cover.
ReMIndeR
all, every, each, any—use 4
some, one, at least one—
use E
pRaCtiCe 16
a. Construct an interpretation (i.e., give the domain and the meaning of P(x)) in which (4x)P(x)
has the value true.
b. Construct an interpretation in which (4x)P(x) has the value false.
c. Can you find one interpretation in which both (4x)P(x) is true and (E x)P(x) is false?
d. Can you find one interpretation in which both (4x)P(x) is false and (E x)P(x) is true?
eXAMPLe 20
The expression (4x)(E y)Q(x, y) is read “for every x there exists a y such that
Q(x, y).” Note that there are two quantifiers for the two variables of the binary
property. In the interpretation where the domain consists of the integers and Q(x, y)
is the property that x < y, this just says that for any integer, there is a larger integer.
The truth value of the expression is true. In the same interpretation, the expression
(E y)(4x)Q(x, y) says that there is a single integer y that is larger than any integer x.
The truth value here is false.
pRaCtiCe 15 What is the truth value of the expression (5x)P(x) in each of the following interpretations?
a. P(x) is the property that x is yellow, and the domain of interpretation is the collection of
all daffodils.
b. P(x) is the property that x is yellow, and the domain of interpretation is the collection of all flowers.
c. P(x) is the property that x is a plant, and the domain of interpretation is the collection of all
flowers.
d. P(x) is the property that x is either positive or negative, and the domain of interpretation consists
of the integers.
Example 20 illustrates that the order in which the quantifiers appear is
important.