Transcript Introduction to Database Systems

Proofs in Predicate Logic
, , ~, , 
•
Purpose of Section: The theorems in the previous section included
quantifiers although the theorems were not stated explicitly in the
language of predicate logic. In this section we state theorems in
rigorous predicate logic language (theorems involving quantifiers)
and show different theorems in predicate logic relate to one another.
Instructor: Hayk Melikya
Introduction to Abstract Mathematics
[email protected]
1
├ (xU)P(x)
To prove a theorem of the form
(xU)P(x)
which states “for all elements x in a given universe U, the
proposition P(x) is true” we select an arbitrary aU from the
universe, and then prove the assertion P(a) .
Let a be an arbitrary constant from the universe U. If P(a)
contains no particular constant from U then
P(a)├ (xU)P(x)
This is called Universal Generalization
Introduction to Abstract Mathematics
2
Example 1 (Universal Direct Proof)
Show that all integers divisible by 6 are even.
Proof: In the language of predicate logic, we write
(x Z) ( 6 divides x  x is even)
where Z = {0,±1,± 2,...} is the universe of integers. Letting a be
an integer, we assume a is divisible by 6, which means there
exists an integer y which satisfies a = 6y . Rewriting this as
a= 2(3y) we have a = 2k for some integer k = 3y ,
which proves that a is an even integer. ▌
Introduction to Abstract Mathematics
3
Universal Instantiation (UI) (xU)P(x)├ P(a)
If a is an arbitrary constant from the universe U then
(xU)P(x)├ P(a)
This is refered as Universal Instantiation rule.
Existential Instantiation (EI)
(xU)P(x)├ P(a)
where a is a paricular contant from univers
Existantial Generalization(EG)
P(a) ├ (xU)P(x)
This rule says that if P(a) true for some constan from the
universe U then (xU)P(x) is true
Introduction to Abstract Mathematics
4
├ (xU)P(x)
To prove a theorem of the form (xU)P(x) which states “there
exists an element x in a given universe U that satisfies the
proposition P(x) ” the strategy is to show one or more elements
xU satisfy the assertion P(x).
Example 2 (Proof by Demonstration)
Show there exists an even prime integer.
Proof:
In language of predicate logic, we would write
(x N)(x is even  x is prime)
The proof is simple because 2 is both prime and even
Introduction to Abstract Mathematics
5
Proof of (x)P(x) by Contradiction:
To prove the theorem (x)P(x) which says “for all x , P(x) is
true” by contradiction, assume the contrary; i.e.
~(x)P(x) which is equivalent to (x) ~P(x) , which says “there
exists an x such that P(x) is not true”. One then continues the
Proof until arriving at a contradiction.
Introduction to Abstract Mathematics
6
Example 4: (Proof by Contradiction)
Show if m, n are integers, then 14m+ 21n  1.
Proof:
In the language of predicate logic this theorem becomes
(mZ)( nZ) (14m+ 21n  1).
Assuming the contrary, we have
(mZ)( nZ) (14m+ 21n = 1).
But the equation 14m+ 21n = 1 cannot hold since 7 divides the
left side of the equation and not the right. Hence, the denial is
false so the theorem is true. ▌
Introduction to Abstract Mathematics
7
Proof of (x) P(x) by Contradiction:
To prove “there exists an x such that P(x) is true” assume the
theorem is not true: i.e.
~(x) P(x)  (x) ~P(x)
which states“for all x the assertion P(x) is not true. You then
continue the proof until you arrive at a contradiction of some
kind.
Introduction to Abstract Mathematics
8
Proving Unique Existential Theorems:
To prove a theorem of the form
(!x U )P(x)
which states “there exists a unique element x such that P(x) is
true” the strategy is to show first that some element x satisfies
P(x) , then show that if two elements y, z U satisfy the
assertion, then in fact they are the same; i.e. y = z. In predicate
logic language, we must show
(xU )P(x)  (yU )(zU )[P( y) P(z)  y = x]
Introduction to Abstract Mathematics
9
Important Relations in Predicate Logic
a) (x)(y)P(x, y)  (y)(x)P(x, y)
b) (x)(y)P(x, y)  (y)(x)P(x, y)
c) (x)[P(x)  Q(x)]  [ (x)P(x)  (x)Q(x) ]
d) (x)[P(x)  Q(x)]  [(x)P(x)  (x)Q(x)]
e) [(x)P(x)  (x)Q(x)]  (x)[P(x)  Q(x)]
f) (x)(y)P(x, y)  (y)(x)P(x, y)
Introduction to Abstract Mathematics
10