Chapter 3

Quantifiers, Predicates, and Validity

Variables and Statements
• Variables: A variable is a symbol that stands for an
individual in a collection or set. For example, the variable x
may stand for one of the days. We may let x =
Monday, x = Tuesday, etc.
• We normally use letters at the end of the alphabet as
variables, such as x, y, z.
• A collection of objects is called the domain of objects.
For the above example, the days in the week is the domain of
variable x.
 Quantifiers
• Quantifiers: Quantifiers are phrases that refer to given
quantities, such as "for some" or "for all" or "for
every",
indicating how many objects have a certain property.
• Two kinds of quantifiers:
– Universal Quantifier: represented by Ʉ, “for all”, “for
every”, “for each”, or “for any”.
– Existential Quantifier: represented by Ǝ, “for some”,
“there exists”, “there is a”, or “for at least one”.
 Predicates
• Predicate: It is the verbal statement which describes the
property of a variable. Usually represented by the letter P, the notation
P(x) is used to represent some unspecified property or predicate that x
may have.
– P(x) = x has 30 days.
– P(April) = April has 30 days.
– What is the truth value of (Ʉx)P(x) where x is all the
months and P(x) = x has less than 32 days
• Combining the quantifier and the predicate, we get a
complete statement of the form (Ʉx)P(x) or (Ǝx)P(x)
• The collection of objects is called the domain of interpretation, and it
must contain at least one object.
 Truth Values of the Expressions
• What is the truth value of (Ʉx)P(x) in the following
interpretations?
– P(x): x is yellow; the domain of interpretation is the collection of
all flowers.
– P(x): x is a plant; the domain of interpretation is the collection of
all flowers.
– P(x): x is either positive or negative; the domain of interpretation
consists of the integers.
• Can you find one interpretation in which (Ʉx)P(x) is true
and (Ǝx)P(x) is false?
• Can you find one interpretation in which (Ǝx)P(x) is true
and (Ʉx)P(x) is false?
Unary, Binary,…, N-ary Predicates
• Predicates involving properties of a single variable:
unary
predicates
• Binary, ternary and n-ary predicates are also possible
• (Ʉx) (Ǝy)Q(x,y) is a binary predicate. This expression
reads as
“for every x there exists a y such that Q(x,y)”
• Constants are also allowed in expressions, such as a, b,
c, 0, 1, 2, etc.
 Interpretation
• Formal definition: An interpretation for an expression involving predicates consists of
the following:
– A collection of objects, called domain of interpretation, which must include at least
one object.
– An assignment of a property of the objects in the domain to each predicate in the
expression.
– An assignment of a particular object in the domain to each constant symbol in the
expression.
• Predicate wffs can be built similar to propositional wffs using logical connectives with
predicates and quantifiers.
• Must obey the rules of syntax to be considered a wff
• Examples of predicate wffs
– (Ʉx)[P(x) →Q(x)]
– (Ʉx) ((Ǝy)[P(x,y) V Q(x,y)] →R(x))
– S(x,y) Λ R(x,y)
 Scope of a Variable in an Expression
• The parentheses or brackets are used wisely to identify the scope
of the variable.
– (Ʉx) ((Ǝy)[P(x,y) V Q(x,y)] → R(x))
• Scope of (Ǝy) is P(x,y) V Q(x,y) while the scope of (Ʉx) is the
entire expression
– (Ʉx)S(x) V (Ǝy)R(y)
• Scope of (Ʉx) is S(x) while the scope of (Ǝy) is R(y)
– (Ʉx)[P(x,y) → (Ǝy) Q(x,y)]
• Scope of variable y is not defined for P(x,y) hence y is called a
free variable. Such expressions might not have a truth value at all.
• P(x): x > 0; P(y)^ P(5), P(y) V P(5).
 Translation of Verbal Statements to Symbolic
Form Using Intermediate Statements
“Every person is nice” can be rephrased as “For any thing, if it is a
person, then it is nice”. So, if P(x) is “x is a person” and Q(x) be “x is
nice”, the statement can be symbolized as
– (Ʉx)[P(x) → Q(x)]
Variations: “All persons are nice” or “Each person is nice”.
“There is a nice person” can be rewritten as “There exists something
that is both a person and nice” in symbolic form (Ǝx)[P(x) Λ Q(x)]
Variations: “Some persons are nice” or “There are nice persons”
So almost always, Ǝ goes with Λ (conjunction) and Ʉ goes with
→(implication)
Can be confusing, so remember to frame the statement in different
forms as possible
 More On Translation
The word “only” can be tricky depending on its presence in the statement:
– X loves only Y ↔ If X loves anything, then that thing is Y
– Only X loves Y ↔ If anything loves Y, then it is X
– X only loves Y ↔ If X does anything to Y, then it is love
Example for forming symbolic forms from predicate symbols:
– D(x) is “x is dog”
– R(x) is “x is a rabbit”
– C(x,y) is “x chases y”
All dogs chase all rabbits ↔
– For anything, if it is a dog, then for any other thing, if it is a rabbit, then the dog chases it ↔
(Ʉx)[D(x) → (Ʉy)(R(y) → C(x,y))]
Some dogs chase all rabbits ↔
– There is something that is a dog and for any other thing, if that thing is a rabbit, then the dog
chases it ↔ (Ǝx)[D(x) Λ (Ʉy)(R(y) → C(x,y))]
Only dogs chase rabbits ↔
– For anything, if it is a rabbit then, if anything chases it, that thing is a dog ↔ (Ʉy) [R(y) →
(Ʉx) (C(x, y) → D(x))]
– Or, for any two things, if one is a rabbit and the other chases it, then the other is a dog ↔
(Ʉy) (Ʉx)[R(y) Λ C(x,y) → D(x)]
 Negation of Statements
• A(x): Everything is beautiful
– Negation will be “it is false that everything is beautiful”, i.e.
“something is not beautiful”
– In symbolic form, [(Ʉx)A(x)]’ ↔ (Ǝx)[A(x)]’
– Similarly, negation of “Something is beautiful” is “Nothing is beautiful”
or “Nothing is beautiful”
– Hence, [(Ǝx)A(x)]’ ↔ (Ʉx)[A(x)]’
• What is the negation of “Everybody loves somebody sometime”
 Everybody hates somebody sometime
 Somebody loves everybody all the time
 Everybody hates everybody all the time
 Somebody hates everybody all the time
 More Examples on Negation
• What is the negation of the following statements?
– Some pictures are old and faded.
• Every picture is not old or not faded.
– All people are tall and thin.
• Someone is short or fat.
– Some students eat only pizza.
• Every student eats something which is not a pizza
– Only students eat pizza.
• There is a non-student who eats pizza.
 Validity
• Analogous to a tautology of propositional
logic
• Truth of a predicate wff depends on the
interpretation
• A predicate wff is valid if it is true in all
possible interpretations just like a
propositional wff is true if it is true for all rows
of the truth table
• A valid predicate wff is intrinsically true
Validity cont…
 Validity Examples
• (Ʉx)P(x) → (Ǝx)P(x)
– This is valid because if every object of the domain has a certain property, then
there exists an object of the domain that has the same property. Therefore, whenever
the antecedent is true, so is the consequent, and the implication is therefore true.
• (Ʉx)P(x) → P(a)
– Valid – quite obvious since a is a member of the domain of X.
• (Ǝx)P(x) → (Ʉx)P(x)
– Not valid since the property cannot be valid for all objects in the domain if it is
valid for some objects of than domain. Can use a mathematical context to check as
well. Say P(x) = “x is even”, then there exists an integer that is even but not every
integer is even.
• How about (Ʉx)[P(x) V Q(x)] → (Ʉx)P(x) V (Ʉx)Q(x)
– Invalid, can prove by mathematical context by taking P(x) = x is even, Q(x) = x is
odd. In that case, the hypothesis is true but not the conclusion is false because it is
not the case that every integer is even or that every integer is odd.
 Assignments
1.Translate the following verbal statement in to Intermediate statement and write symbolic Form
• S(x): x is a student
• I(x):x is intelligent
• M(x):x likes music
a) All students are intelligent.
b) Some intelligent students like music.
c) Everyone who likes music is a stupid student.
d) Only intelligent students like music
2. • Using predicate symbols and appropriate quantifiers, write the symbolic form of the
following English statement:
• D(x) is “x is a day”; M is “Monday”; T is “Tuesday”.
• S(x) is “x is sunny”; R(x) is “x is rainy”.
e) Some days are sunny and rainy
f) It is always a sunny day only if it is a rainy day
g) It rained both Monday and Tuesday
h) Every day that is rainy is not sunny
 Chapter 4
predicate logic
Valid Argument
(P1 Λ P2 Λ ... Λ Pn)  Q
– where the wffs are built from predicates and quantifiers as well as logical
connectives and grouping symbols
– no equivalent of the truth table exists to prove validity
– the meaning and the structure of the quantifiers and predicates determines the
interpretation and the validity of the arguments
– Predicate logic: 4 more new derivation rules to build a proof sequence leading from
the hypothesis to the conclusion
– The equivalence rules and inference rules still applies
• Why predicate logic? More rules?
– A valid argument for predicate logic need not be a tautology to be valid
– Example: (Ʉx)P(x) → (Ǝx)P(x)
– Hence: we need to learn 4 new rules
Inference Rules in Predicate Logic
 Universal Instantiation (1)
• This rule says if P is true for every element of the domain, we can name such an
element by an arbitrary variable name like x, y, or z, or we can specify a particular
constant in the domain, and P is still true for all these things.
• Example:
– All flowers are plants. Sunflower is a flower. Therefore, sunflower is a plant.
– P(x) is “ x is a plant”
– a is a constant symbol (Sunflower)
– F(x) is “x is a flower”
– The argument is (Ʉx)[F(x) →P(x)] Λ F(a) → P(a)
• The proof sequence is as follows:
1. (Ʉx)[F(x) → P(x)] hyp
2. F(a) hyp
3.F(a) P(a) 1, ui
4. P(a) 2, 3, mp