Transcript PPT - University of Alberta

CMPUT 272
Formal Systems
Logic in CS
I. E. Leonard
University of Alberta
http://www.cs.ualberta.ca/~isaac/cmput272/f03
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
1
Quiz I (October
th
9 )
Coverage:
Everything up to and including October 7th lecture:
textbook  lectures  seminars
Focus on the overlapping part:
textbook  lectures
Format:
Problems similar in format to the assignments
50 minutes in-class
Open book, notes, etc.
Calculators are allowed
No team-work of ANY kind
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
2
ABOUT QUIZ 1
Exams were around the corner. During a lecture in mathematical
analysis the students questioned the professor about the contents
of the forthcoming paper.
“It will contain some interesting problems,” he said. “Right now
faculty members are busy working on one of them. If we solve it,
it will be included in the examination paper.”
Mathematics and Informatics Quarterly, Volume 6, No. 1, 1996
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
3
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
4
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
5
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
6
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
7
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
8
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
9
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
10
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
11
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
12
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
13
Today
Binary relations
Equivalence classes
Floor & ceiling
Proof by contradiction
and contraposition
Infinitude of primes
Irrationality of sqrt(p)
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
14
Binary Relations
A binary relation R from a set A to a set B is a
subset of the Cartesian Product AB, that is,
a set of ordered pairs (a,b) with aA and b B
A binary relation R on a set A is a subset of
the Cartesian product AA, that is, ordered
pairs of the form (a,b) where a A and b A
Instead of (x,y)  R AA
We use the shorthand notation: x R y
Examples:
3<4
Angela likes Belinda
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
15
Properties
Reflexivity
Irreflexivity
Symmetry
Asymmetry
Anti-symmetry
Transitivity
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
16
Questions
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
17
Equivalence Relation
A relation is an equivalence relation iff
it is reflexive, symmetric, and transitive
Examples:
=
on numbers, sets, etc.
 mod n
on integers
“logic equivalence”
on formulae
Counter examples:
<
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
18
Congruence Relation
Any two integers a,b are congruent modulo n
iff remainder(a,n) = remainder(b,n)
Alternatively: a,b are congruent modulo n
iff n divides a - b
Notation a
Examples:
 b (mod n)
 21 (mod 7)
15  22 (mod 7)
NOT 14  15 (mod 7)
6  0 (mod 2)
14
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
19
Congruence & Equivalence
Theorem. For any integer n > 0
 (mod n) is an equivalence relation
Properties to prove:
Reflexive:
for any a [a  a (mod n)]
Symmetric:
for any a,b [a  b (mod n)  b  a (mod n)]
Transitive:
for any a,b,c [a  b (mod n) & b  c (mod n)
a
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
 c (mod n)]
20
Equivalence Classes
Suppose Ris an equivalence relation on A
Then we can define subsets of A in this way:
[x] = {aA | a R x}, xA (a representative of the class)
Example:
A=N
R is
 (mod 2)
 0 (mod 2)}
[1] = {nN | n  1 (mod 2)}
[0] = {nN | n
even numbers
odd numbers
Question: how many equivalence classes does
have?
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
 (mod 7)
21
Questions
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
22
Partitioning
A set A is partitioned into sets {Ai} iff
The union of all Ai equals to A
Sets Ai are disjoint (i.e., don’t intersect)
Examples:
{a,b,c} = {a,b}  {c}
N={0,1,…,9}  {10,…,19}…
N= [0]  [1]
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
23
Equivalence Classes & Partitioning
The last example demonstrated that
 (mod 2) with its two equivalence
classes [0] and [1] partitioned N
Will it always be the case?
In other words: are equivalence
classes always going to form a
partition of the set?
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
24
Theorem 1
For any set A and any equivalence
relation R defined on it, the equivalence
classes induced by R form a partition of
A
Example:
N= [0]  [1]  …  [n-1]
with respect to  (mod n)
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
25
Theorem 2: Converse
For any set A and any partition {Ai} of A
the binary relation R defined by
a R b iff a,bA & i st a,bAi}
is an equivalence relation on A
Proof structure:
Show that R is reflexive
Show that R is symmetric
Show that R is transitive
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
26
Questions
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
27
Floor & Ceiling
Definitions
Different from the textbook’s
floor(x) = max{nZ st nx}, that is
the greatest integer less than or equal to x
ceiling(x) = min{nZ st nx}, that is
the smallest integer greater than or equal to x
Examples
floor(5.75) = 5
floor(-5.75) = -6
ceiling(5.75) = 6
ceiling(-5.75) = -5
Oct 7, 2003
floor(x)
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
x
ceiling(x)
28
Equivalence to text’s defs and more
Theorem
For any xR\Z, floor(x) and ceiling(x) are defined,
unique, and ceiling(x)=floor(x)+1
Proof
Part 1: existence
Part 2: uniqueness
Part 3: relationship
Corollary
xR [floor(x)  x < floor(x)+1]
xR [ceiling(x)-1 < x  ceiling(x)]
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
29
Lemmata Galore…
mZ floor(m)=ceiling(m)=m
x,yR ceiling(x+y)ceiling(x)+ceiling(y)
xR mZ floor(x+m)=floor(x)+m
nZ floor(n/2)=n/2 iff n is even and
floor(n/2)=(n-1)/2 iff n is odd
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
30
Questions
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
31
Types of Proofs
Many interesting statements are of the
type:
n S(n)
Two primary proof methods:
Direct
Take an arbitrary n, prove S(n), generalize
If S(n)  P(n)Q(n)
Then can prove ~Q(n)~P(n) instead
Indirect
Show that n ~S(n) would lead to a contradiction
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
32
Contraposition & Contradiction
Suppose the statement to prove is:
n [ P(n)Q(n) ]
Direct proof by contraposition:
Take an arbitrary n
Show that if ~Q(n) holds for that n then ~P(n)
holds
Indirect proof (by contradiction):
Assume P(n) and ~Q(n) hold for some n
Show ~P(n)
Contradiction : cannot have P(n) and ~P(n)
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
33
Illustration
If n2 is even then n is even
n [ P(n)Q(n) ]
Direct proof by contraposition:
Assume ~Q(n) : n is not even
n is odd
Then n=2k+1
n2=4k2+4k+1
n2 is odd : n2 is not even : ~P(n)
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
34
Illustration
If n2 is even then n is even
n [ P(n)Q(n) ]
Indirect proof (by contradiction):
Assume P(n) and ~Q(n)
n2 is even
n is not even : n is odd
Then n=2k+1
n2=4k2+4k+1
n2 is odd : n2 is even : contradiction
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
35
The third proof
Theorem: n2 is even  n is even
How about a direct proof without
contraposition?
Proof
Assume n2 is even
2 | n2
p|ab  p|a v p|b (Euclid’s 1st theorem)
2|n v 2|n
Then n is even
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
36
Questions
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
37
Infinitude of Primes
There is no greatest prime:
n m [ prime(n)  m>n & prime(m) ]
Theorem 3.7.4 in the book
Will prove three lemmas first…
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
38
Lemma 0
If a|n and a|n+1 then a=1 v a=-1
Proof
direct
a|n  n=ka
a|n+1  n+1=ja
a(j-k)=1
a=+1 v a=-1
(proved before)
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
39
Lemma 1
For any integer a and any prime p
if p | a then ~(p | a+1)
Proof
indirect
Suppose such prime p exists
p|a and p|a+1
Then by Lemma 0: p=+1 or p=-1
p cannot be prime
contradiction
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
40
Lemma 2
A natural number n>1 is not prime iff there is a
prime p<n such that p|n
Proof (direct):

If n is not prime then it has non-trivial divisors (proved
before)
Then one of them has a prime factor p (proved before)

Know that p<n and p|n
Then p is a non-trivial factor of n
Thus n is not prime
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
41
Proof: Infinitude of Primes
Indirect (i.e., by contradiction)
Suppose not
Then
n m [ prime(n) & (mn v ~prime(m)) ]
(*)
Thus, denote the only primes as p1, …, pk=n
Then consider m=p1 * …* pk + 1
m>pi
m>n=pk
Is prime(m)?
None of the primes pi divides it (by lemma 2)
But there are no other prime numbers (by supposition)
Thus, m is a prime (by lemma 1)
This contradicts (*)
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
42
Questions
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
43
Lemma
If qQ then there exist n,mZ such that
q=n/m and gcd(n,m)=1
Proof
Suppose we have n/m=q and gcd(n,m)>1
Then compute n’, m’ :
n’=n/gcd(n,m)
m’=m/gcd(n,m)
q=n’/m’ and n’,m’ are less than n and m
Either gcd(n’,m’)=1 : then done
Or gcd(n’,m’)>1 : then repeat the process again
Must terminate since n’ and m’ are decreasing
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
44
Another proof ?
How about another constructive proof?
Hint:
Fundamental theorem of arithmetic
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
45
Irrationality of sqrt(2)
Define sqrt(x)=y such that yR, y*y=x
Let’s prove that sqrt(2) is irrational
Proof
Indirect (by contradiction)
Suppose not: sqrt(2)=n/m and gcd(n,m)=1
Then 2=n2/m2, 2m2=n2
n2 is even  n is even (proved earlier)
Then 2m2=4k2
Then m2 is even and so m is even
Thus, gcd(n,m) is at least 2
Contradiction
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
46
Questions
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
47
Irrationality of sqrt(p)
Claim: for any prime p, sqrt(p) is
irrational
How do we generalize the previous
proof for this?
Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
48
Questions

Oct 7, 2003
© Vadim Bulitko : CMPUT 272, Fall 2003, UofA
49