Something to Ponder…
All roses are flowers.
Some flowers fade quickly.
Therefore some roses fade quickly.
IS THE ARGUMENT VALID?
Lecture 2: Logic II
Learning Objectives:
The students be able to identify the predicate logic
The students be able to understand the universal and
existential quantification.
The students be able to determine modus ponens and
modus tollen.
Symbols
The set of all integers
Z = {…, -2, -1, 0, 1, 2, …}
Z is the first letter of German word for integer, Zahlen
Countably infinite
or
The set of all rational numbers Countable
Q (quotients of integers or “fractions”)
The set of all nonnegative integers
N = {1, 2, 3, …} (often used)
N = {0, 1, 2, 3, …} (in Maurer & Ralston)
Uncountably infinite or Uncountable
The set of all real numbers, R.
Predicates and Quantified
Statements I
Predicates
A predicate is a sentence that
contains a finite number of variables, and
becomes a statement when values are substituted for the
variables.
Domains of Predicate Variables
The domain D of a predicate variable x is the set of all
values that x may take on.
Let P(x) be the predicate.
x is a free variable.
The truth set of P(x) is the set of all values of x D
such that P(x) is true.
{
The Universal Quantifier:
The symbol is the universal quantifier.
The statement
x D, P(x)
means “for all x in D, P(x)”.
x is a bound variable, bound by the quantifier .
The statement is true if P(x) is true for all x in D.
The statement is false if P(x) is false for at least
one x in D.
Examples
Statement
“7 is a prime number” is true.
Predicate
“x is a prime number” is neither true nor false.
Statements
“x {2, 3, 5, 7}, x is a prime number” is true.
,
x D, P(x)
“x {2, 3, 6, 7}, x is a prime number” is false.
Examples of Universal Statements
x {1, …, 10}, x2 > 0.
x {1, …, 10}, x2 > 100.
x R, x3 – x 0.
x R, y R, x2 + xy + y2 0.
x , x2 > 100.
The Existential Quantifier:
The symbol is the existential quantifier.
The statement
x D, P(x)
means “there exists x in D such that P(x)”.
In logic, “there exists” or “some” means “at least
one”.
x is a bound variable, bound by the quantifier .
The statement is true if P(x) is true for at least one x
in D.
The statement is false if P(x) is false for all x in D.
Examples of Existential Statements
x {1, …, 10}, x2 > 0.
x {1, …, 10}, x2 > 100.
x R, x3 – x 0.
x R, y R, x2 + xy + y2 0.
x , x2 > 100.
Predicates and Quantified
Statements II
Negations of Universal Statements
The negation of
x D, Q(x)
is the statement
x D, Q(x)
Symbolically,
x D, Q(x)
If “x R, x2 > 10” is false, then “x R, x2 10” is
true.
Example: Negation of a Universal
Statement
P(x) = “Person x likes me.”
“Everybody likes me”
x , P(x)
“Somebody does not like me”
x , ~P(x)
Negations of Existential Statements
The negation of
x D, Q(x)
is the statement
x D, Q(x).
Symbolically,
x D, Q(x)
If “x R, x2 < 0” is false, then “x R, x2 0” is true.
Example: Negation of an Existential
Statement
P(x) = “Person x like me.”
“Somebody likes me.”
x , P(x).
“Everybody does not like me”
x , ~P(x)
Counterexample
A
counterexample is an example which proves that a
universally quantified statement is false.
x ,
Get a counterexample by finding
a value of x such that x , ~P(x)
Counterexample: take , then x
Hence “x , ” is false
Universal Conditional Statements
x, if P(x), then Q(x)
Example: For all real number x, if x is an integer, the x is
a rational number.
x , if x then x
Negations of Universal Conditional Statements
x such that P(x) and Q(x)
𝒑 → 𝒒 ≡ p ∨𝑞 ( 𝒑 ˅ 𝒒)≡ 𝒑˄ 𝒒
people p, if p is blonde, then p has blue eyes.
a person p such that p is blonde and p does not has blue eyes.
If a computer program has more than 100,000 lines, then it
contains a bug
There is at least one computer program that has more than 100,000
lines and does not contain a bug.
Negation of Universal Conditional
Statements
Negate the statement
x R, x < 10 x2 < 100.
(x R, x < 10 x2 < 100)
x R, (x < 10 x2 < 100)
x R, ((x < 10) ˅ (x2 < 100))
x R, (x < 10) (x2 100)
( 𝒑 ˅ 𝒒)≡ 𝒑˄ 𝒒
Universal Conditional Statements
A universal conditional statement is of the form
x S, P(x) Q(x).
The converse is
x S, Q(x) P(x).
The inverse is
x S, P(x) Q(x).
The contrapositive is
x S, Q(x) P(x).
Multiply-Quantified
Statements
Multiply-Quantified Statements
Multiply-quantified universal statements
x D, y E, P(x, y)
The order does not matter.
Multiply-quantified existential statements
x D, y E, P(x, y)
The order does not matter.
Multiple Quantified Statements
Mixed universal and existential statements
x D, y E, P(x, y)
y E, x D, P(x, y)
The order does matter.
What is the difference?
Compare
x R, y Z, x + y = 0.
y Z, x R, x + y = 0.
Multiple Quantified Statements
The order does matter!
Compare
x R, y Z, x + y = 0.
y Z, x R, x + y = 0.
The Generalized de Morgan Laws
What happens if we negate an expression involving predicates and
quantifiers?
The Generalized de Morgan Laws
~ [x, P( x)] x, ~ P( x)
~ [x, P( x)] x, ~ P( x)
Examples:
1. “It’s not true that all food is delicious” is the same as “there exists some
food which is not delicious.”
2. “It’s not true that some dogs bite” is the same as “there aren’t any dogs
who bite” or equivalently “all dogs don’t bite”.
Combining Quantifiers
A predicate can have numerous variables, each of which
may be quantified.
Example
x, y, z , P( x, y, z )
Negation
~ [x, y, z, P( x, y, z )] x, y, z, ~ P( x, y, z )
It can be difficult to interpret expressions involving 3 or
more quantifiers.
Negation of Multiply Quantified Statements
Negate the statement
x R, y R, z R, x + y + z = 0.
(x R, y R, z R, x + y + z = 0)
x R, (y R, z R, x + y + z = 0)
x R, y R, (z R, x + y + z = 0)
x R, y R, z R, (x + y + z = 0)
x R, y R, z R, x + y + z 0
Example
Suppose P(x, y) means x ≥ y. Let D be the set
N - {0} = {1, 2, 3, …}.
The discussion is in the following slides.
xy P ( x, y )
For all x and (for all) y, P(x, y) is true.
This says that no matter which numbers x and y we choose from N -
{0}, it will always happen that x ≥ y.
Is this true?
No. For example, x = 1 and y = 2.
xy P( x, y )
For all x there exists y such that x ≥ y.
Here y can depend on x.
A different choice of x may lead to a different value of y.
Is this true?
Yes. For example, given x we can take y = x. Then x ≥ y.
Or, we could take y = 1 when x = 1, and take y = x – 1 for all other values of x.
Or we could take y = 1 always.
xy P( x, y )
There exists x such that for all y, x ≥ y.
This says that x is a constant, and every choice of y makes x ≥ y.
Is this true?
No. There is no such constant. (It would have to be the biggest integer
– the largest element of N - {0}. But this set has no largest element.)
xy P( x, y )
There exists x and there exists y such that x ≥ y.
Is this true?
Yes. For example, take x = 2 and y = 1.
yx P( x, y )
For all y there exists x such that x ≥ y.
This says that for every choice of y it’s possible to find an x which is ≥ y.
Is this true?
Yes. For example, put x = y + 1 (or take x = y)
yx P( x, y )
There exists y such that for all x, x ≥ y.
This says that there is a constant y which is less than or equal to all
values of x.
Is this true?
Yes: y = 1 has this property. It’s the smallest element of the set.
Universal Modus Ponens
The rule of universal instantiation can be combined with
modus ponens to obtain the valid form of argument called
universal modus ponens.
If p then q.
p
q
Note that the first, or major, premise of universal modus
ponens could be written “All things that make P(x) true make
Q(x) true”
The if-then form is more natural to use in the majority of
mathematical situations.
Example:
If
an integer is even, then its square is even.
k is a particular integer that is even.
is even.
Let E(x) = “x is an even integer”
S(x) = “ is even”
x, if E(x) then S(x)
E(k), for a particular k,
S(k).
Universal Modus Tollens
The rule of universal instantiation can be combined with modus
tollens to obtain the valid form of argument called universal
modus tollens.
If p then q.
~q
~p
Example:
All
human beings are mortal.
Zeus is not mortal.
Zeus is not human.
Let H(x) = “ is human”
M(x) = “ is mortal”
Z stands for Zeus
x, if H(x) then M(x)
~M(Z)
~H(Z).
