Transcript PPT - UBC Computer Science

snick

snack
CPSC 121: Models of Computation
2012 Summer Term 2
Functions
Steve Wolfman, based on notes by
Patrice Belleville and others
1
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
2
Learning Goals: Pre-Class
By the start of class, you should be able to:
– Define the terms domain, co-domain, range,
image, and pre-image
– Use appropriate function syntax to relate
these terms (e.g., f : A  B indicates that
f is a function mapping domain A to codomain B).
– Determine whether f : A  B is a function
given a definition for f as an equation or
arrow diagram.
3
Learning Goals: In-Class
By the end of this unit, you should be able
to:
– Define the terms injective (one-to-one),
surjective (onto), bijective (one-to-one
correspondence), and inverse.
– Determine whether a given function is
injective, surjective, and/or bijective.
– Apply your proof skills to proofs about the
properties (e.g., injectiveness, surjectiveness,
bijectiveness, and function-ness) of functions
and their inverses.
4
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
5
What is this?
data1
output
data2
control
6
What is this?
data1
output
data2
control
7
What is this?
data1
output
data2
control
8
What is this?
In the lab, you implemented a multiplexer and then
used it as a piece in larger circuits.
You abstracted from the concrete implementation
to a description of its function:
f(control, data1, data2) = output
= (~control  data1) 
(control  data2)
= data1 if control is 0,
data1
but data2 otherwise
output
data2
9
control
Functions, Abstraction,
and CPSC 121
Computer scientists use many abstraction levels,
with reasoning and execution tools at each level.
In 121, we encounter abstraction levels like: wiring
physical gates, computer-based hardware
design techniques, propositional logic, predicate
logic, sets, …
Functions are a model that let us talk about how
computations work and fit together.
Bonus: functions alone are enough for10
all of
computation, using the “λ calculus”.
Functions We’ve Used
• Any combinational logic circuit
• Lists, as long as they’re immutable
(unchangeable): A(i) = the ith value in A.
• The Power Set operation (mapping a set
to another set)
• Addition, subtraction, multiplication, ...
Sequential circuits and mutable lists aren’t functions. Why 11not?
(Actually we can model them as functions by making time explicit)
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
12
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
What is a Function?
Mostly, a function is what you learned it was
all through K-12 mathematics, with strange
vocabulary to make it more interesting…
A function f:A  B maps values from its
domain A to its co-domain B.
Domain
f(x) = x3
f(x) = x mod 4
f(x) = x
Co-domain
13
Look, sets!
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
Plotting Functions
f(x) = x3
f(x) = x mod 4
f(x) = x
15
Not every function is easy to plot!
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
What is a Function?
Not every function has to do with numbers…
A function f:A  B maps values from its
domain A to its co-domain B.
Domain
Co-domain
f(x) = ~x
f(x,y) = x  y
f(x) = x’s phone #
17
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
What is a Function?
A function f:A  B maps values from its
domain A to its co-domain B.
f(control, data1, data2)
= (~control  data1) 
(control  data2)
Domain?
Co-domain?
19
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
What is a Function?
A function f:A  B maps values from its domain
A to its co-domain B.
Alan
Steve
111
Paul
121
Patrice
211
Karon
George
Domain?
Co-domain?
21
Other examples?
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
What is a Function?
A function f:A  B maps values from its
domain A to its co-domain B.
f can’t map one element of its domain to more
than one element of its co-domain:
x  A, y1,y2  B,
[(f(x) = y1)  (f(x) = y2)]  (y1 = y2).
f
Why insist on this?
A
B
23
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
Not a Function
Why isn’t this a function?
25
(The Laffer Curve: a non-functional tax policy.)
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
Function Terminology
A function f:A  B maps values from its
domain A to its co-domain B.
For f to be a function, it must map every
element in its domain:
x  A, y  B, f(x) = y.
f
Why insist on this?
A
Warning: some mathematicians
would say that makes f “total”.
B
27
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
Not a Function
Anne
Alan
Steve
111
Paul
121
Patrice
211
Karon
George
29
Foiled by sabbatical.
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
Function Terminology
A function f:A  B maps values from its
domain A to its co-domain B.
f(x) is called the image of x (under f).
x is called the pre-image of f(x) (under f).
f
x
A
B
y
31
CORRESPONDS TO TEXTBOOK READING
(NOT COVERED IN CLASS)
Trying out Terminology
f(x) = x2
What is the image of 16?
What is the range of f?
f(x)
x
33
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
35
Function Properties: Injective
A function f:A  B is injective (also oneto-one) if each image is associated with at
most one pre-image:
xA, yA, xy  f(x)  f(y).
Injective?
Alan
Steve
Paul
Patrice
Karon
George
111
121/202
121/203
121/BCS
211/201
211/202
211/BCS
Injective?
Alan
Steve
Paul
Patrice
Karon
George
111
121
211
36
Trying out Terminology
f(x) = x2
Injective?
What if f:R+  R+?
f(x)
x
37
Trying out Terminology
f(x) = |x| (the absolute value of x)
Injective?
a. Yes, if f:R  R+
b. Yes, if f:R+  R
c. Yes, for some other domain/co-domain
d. No, not for any domain/co-domain
e. None of these is correct
f(x)
x
38
Trying out Terminology
f:{s|s is a 121 student}  {A+, A, …, D, F}
f(s) = s’s mark in 121
Is f injective?
a. Yes
b. No
c. Not enough information
39
Trying out Terminology
f:{s|s is a 121 student}  {A+, A, …, D, F}
f(s) = s’s mark in 121
What if we didn’t know what f represented, only its “type”
and the fact that there are lots of 121 students:
f:{s|s is a 121 student}  {A+, A, …, D, F}
Is f injective?
a. Yes
b. No
c. Not enough information
40
Nifty Injective Function:
Error-Detecting Codes
41
Error-detecting codes must be injective. Why?
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
42
Function Properties: Surjective
f:A  B is surjective (also onto) if every
element of the co-domain has a pre-image:
y  B, x  A, y = f(x).
Surjective?
Alan
Steve
Paul
Patrice
Karon
George
111
121/202
121/203
121/BCS
211/201
211/202
211/BCS
Surjective?
Alan
Steve
Paul
Patrice
Karon
George
121
211
43
Can we define “surjective” in terms of “range” and “co-domain”?
Trying out Terminology
f(x) = x2
f:R  R0?
Surjective?
What if f:R  R?
What if f:Z  Z0?
f(x)
x
44
Trying out Terminology
f(x) = x
Is f surjective?
a. Yes, for f:R  R0?
b. Yes, for f:R0  R?
c. Yes, for f:R  Z?
d. No, not for any
domain/co-domain
e. None of these
is correct
f(x)
x
45
Trying out Terminology
f:{s|s is a 121 student}  {A+, A, …, D, F}
f(s) = s’s mark in 121
Is f surjective?
a. Yes
b. No
c. Not enough information
Could we ever know that f was surjective just by knowing f’s
domain and co-domain?
46
Trying out Terminology
Could we ever know that f was surjective just by knowing f’s
domain and co-domain (and their cardinalities)?
a. Yes
b. No
c. Not enough information
47
Nifty Surjective Function:
Cryptographic Hash
“Good” cryptographic hashes should be but don’t have 48
to be
surjective… but they must not be injective.
Surjective Functions So Far
Which combinational circuits with one output
are surjective?
a. Every such circuit.
b. Any such circuit that represents a
contingency (neither a tautology nor
contradiction).
c. Only the ones equivalent to an inverter.
d. No such circuit is surjective.
e. None of these is correct.
49
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
50
Function Properties: Bijective
A function f:A  B is bijective (also oneto-one correspondence) if it is both one-toone and onto (both injective and
surjective).
Every element in the domain has exactly
one unique image. Every element in the
co-domain has exactly one unique preimage.
51
Function Properties: Bijective
A function f:A  B is bijective (also oneto-one correspondence) if it is both one-toone and onto.
Bijective?
Alan
Steve
Paul
Patrice
Karon
George
Bijective?
121/202
121/203
121/BCS
211/201
211/202
211/BCS
Alan
Steve
Paul
Patrice
Karon
George
111
121
211
52
Trying out Terminology
f(x) = x2
f:?  ?
Bijective for what
domain/co-domain?
f(x)
x
53
Nifty Bijective Function:
Encryption/Lossless Compression
Two sets have the same cardinality if we can put them54in a
bijection. What does that say about lossless compression?
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
55
Function Operations: Inverse
The inverse of a function f:A  B is
f-1:B  A. f(x) = y  f-1(y) = x.
How can we tell whether f-1 is a function?
(Hint: what would make f-1 not a function?)
56
Can we prove it?
Trying out Terminology
What’s the inverse of each of these fs?
Alan
Steve
Paul
Patrice
Karon
George
121/202
121/203
121/BCS
211/201
211/202
211/BCS
Alan
Steve
Paul
Patrice
Karon
George
111
121
211
57
Trying out Terminology
f(x) = x2
What’s the inverse of f?
f(x)
What should the
domain/co-domain be?
x
58
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
59
Proving a function injective
Recall: A function f : A  B is injective
exactly when: xA, yA, xy 
f(x)  f(y).
A typical approach is to prove the
contrapositive by antecedent assumption:
assume f(x) = f(y) and show that x
= y.
60
Problem:
3
x
+ 5 is injective
Theorem: f(x) = x3 + 5 is injective,
where f : Z  Z.
61
Proving a function surjective
Recall: A function f : A  B is surjective
exactly when:
y  B, x  A, y = f(x).
That existential gives us a lot of freedom to
pick a witness!
A typical approach is to “solve for” the
necessary x given a y.
63
Problem: w + 2z is surjective
Theorem: f(w,z) = w + 2z is surjective,
where f : (Z  Z)  Z.
64
Proving a function bijective
Prove that it’s injective.
Prove that it’s surjective.
Done.
66
Proving a function has an
inverse
Prove that it’s bijective.
Done.
67
An Inverse Proof
Theorem: If f:A  B is bijective, then
f-1 : B  A is a function.
Recall that f-1(f(x)) = x.
68
Aside: Functions are Just Sets
We can define functions in terms of sets and
tuples (and we can define tuples in terms
of sets!).
The function f:A  B is the set
{(x, f(x)) | x  A}.
f is a subset of A  B!
70
Outline
•
•
•
•
•
•
•
Prereqs, Learning Goals, and Quiz Notes
Functions as “Computation Abstractions”
Terminology (out-of-class)
Properties: Injective, Surjective, Bijective
Inverse Operation
Function Proofs
Next Lecture Notes
71
Learning Goals: In-Class
By the end of this unit, you should be able
to:
– Define the terms injective (one-to-one),
surjective (onto), bijective (one-to-one
correspondence), and inverse.
– Determine whether a given function is
injective, surjective, and/or bijective.
– Apply your proof skills to proofs about the
properties (e.g., injectiveness, surjectiveness,
bijectiveness, and function-ness) of functions
and their inverses.
72
Learning Goals: “Pre-Class”
(REPEAT)
The pre-class goals are to be able to:
– Trace the operation of a deterministic finitestate automaton (represented as a diagram)
on an input, including indicating whether the
DFA accepts or rejects the input.
– Deduce the language accepted by a simple
DFA after working through multiple example
inputs.
73
snick

snack
Extra Slides…
74