Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Predicates and Quantifiers
Motivating example
Consider the compound proposition:
If Zeph is an octopus then Zeph has 8 limbs
...

Q2: Is the proposition true or false?
Q3: Why?
A1: Let p = “Zeph is an octopus” and q = “Zeph has 8 limbs”
...

A2: True!
A3: Conditional always true when p is false!
Q: Why is this not satisfying?
A: We wanted this to be true because of the fact that octopi have 8 limbs and not because of some (important)
non-semantic technicality in the truth table of implication
...

Logical Quantifiers help to fix this problem
...

Expressions such as the previous are built up from propositional functions –statements that have a variable or
variables that represent various possible subjects
...
For example:
“For all x, if x is an octopus then x has 8 limbs
...

Semantics
If logical propositions are to have meaning, they need to describe something
...
Either they are
true or false, but no more
...
e
...

Q: What is the universe of discourse for the three propositions above?
A: There are many answers
...
The following predicates are
all italicized :
Johnny is tall
...

17 is a prime number
...
When an object from the universe is plugged in for x, y, etc
...
…e
...
plug in x = Johnny
y is structurally sound
...
g
...
…e
...
plug in n = 111
Multivariable Predicates
Multivariable predicates generalize predicates to allow descriptions of relationships between subjects
...
For example:
Johnny is taller than Debbie
...


Johnny is at least 5 inches taller than Debbie
...
The most obvious answers are:
For “Johnny is taller than Debbie” the universe of discourse of both variables is all people in the universe
For “17 is greater than one of 12, 45” the universe of discourse of all three variables is Z (the set of integers)
For “Johnny is at least 5 inches taller than Debbie” the first and last variable have people as their universe of
discourse, while the second variable has R (the set of real numbers)
...
In the
above examples, we have the following generalizations:
x is taller than y
a is greater than one of b, c
x is at least n inches taller than y
Quantifiers
There are two quantifiers

Existential Quantifier

“” reads “there exists”
Existential quantifiers synonyms:
“ some x ” ; “ there is an x ” ; “ there is at least x ” ; “ for some x ”

Universal Quantifier
“” reads “for all”
Universal quantifiers synonyms:
“ for every x ” ; “ all of x ” ; “ for each x ” ; “ given any x ” ; “ for arbitrary x ”
Each is placed in front of a propositional function and binds it to obtain a proposition with semantic value
...
Example
Consider a universe consisting of
Leo: a lion
Jan: an octopus with all 8 tentacles
Bill: an octopus with only 7 tentacles
And recall the propositional functions
P (x) = “x is an octopus”
Q (x) = “x has 8 limbs”
x ( P (x) Q (x) )
Q: Is the proposition true or false?
A: True
...

Leo is called a positive example
...

 x ( P (x) Q (x ) )
Q: Is the proposition true or false?
A: False
...
e
...

P (Bill) is true because Bill is an octopus, while Q (Bill) is false because Bill only has 7 tentacles, not 8
...

Illegal Quantifications

Once a variable has been bound, we cannot bind it again
...
The interior expression
(x P (x)) bounded x already and therefore made it
unobservable to the outside
...

Multivariate Quantification
Quantification involving only one variable is fairly straightforward
...

When two or more variables are involved each of which is bound by a quantifier, the order of the binding is
important and the meaning often requires some thought
...

Example
P (x,y,z ) = “y - x ≥ z ”
There is an x such that for all y there is a z such that y - x ≥ z
...

Q: If the universe of discourse for x, y, and z is the natural numbers {0,1,2,3,4,5,6,7,…} what’s the truth value
of xy z P (x,y,z )?
A: True
...

Since x is the first variable in the expression and is “existential”, we need a number that works for all other y, z
...

Now for each y we need to find a positive instance z such that y - x ≥ z holds
...

Q: Did we have to set z := y ?
A: No
...
Many other valid solutions
...
I
...
, the scope of x is higher than the
scope of y so as far as y can tell, x is a constant and cannot affect x
...

Let R (x,y ) = “x < y”
...

x y R (x,y ): “All numbers x admit a bigger number y ” --just set y = x + 1
y x R (x,y ): “Some number y is bigger than all numbers x” --y is never bigger than itself, so setting x = y is a
counterexample
Order matters –but not always
Q: What if we have two quantifiers of the same kind? Does order still matter?
A: No! If we have two quantifiers of the same kind order is irrelevant
...

EG: x y Q (x,y ) and y x Q (y,x ) are equivalent –names of variables don’t matter
...
The
opposite is that “some x does not admit a y greater or equal to x’s square”
Algebraically, one just flips all quantifiers from  to  and vice versa, and negates the interior propositional
function
...

(x A(x ))(x B(x ))x,y A(x )B(y )
CASE I) Assuming LHS true show RHS true
...
A) For all x, A(x ) true
...
B) For all x, B(x ) true… similar to case (I
...

Both x A(x ) false AND x B(x ) false
...

Thus there is an example x1 for which A(x1) is false and an example x2 for which B(x2) is false
...

Setting x = x1 and y = x2 gives a counterexample to x,y A(x )B(y ) showing the RHS false

---