EppDm4_07_01

Август 23, 2022

Содержание

2. Copyright © Cengage Learning. All rights reserved. Functions Defined on General Sets SECTION 7.1
3. Functions Defined on General Sets We have already defined a function as a certain type of
4. Arrow Diagrams
5. Arrow Diagrams We have known that if X and Y are finite sets, you can define
6. Arrow Diagrams This arrow diagram does define a function because 1. Every element of X has
7. Example 2 – A Function Defined by an Arrow Diagram Let X = {a, b, c}
8. Example 2 – Solution a. domain of co-domain of b. c. range of d. Yes, No
9. Arrow Diagrams In Example 2 there are no arrows pointing to the 1 or the 3.
10. Arrow Diagrams Earlier we have given a test for determining whether two functions with the same
11. Example 3 – Equality of Functions a. Let J3 = {0, 1, 2}, and define functions
12. Example 3 – Solution a. Yes, the table of values shows that f (x) = g(x)
13. Examples of Functions
14. Example 4 – The Identity Function on a Set Given a set X, define a function
15. Example 4 – Solution Whatever is input to the identity function comes out unchanged, so and
16. Examples of Functions
17. Example 8 – The Logarithmic Function with Base b Find the following: a. b. c. d.
18. Example 8 – Solution d. because the exponent to which 2 must be raised to obtain
19. Examples of Functions We have known that if S is a nonempty, finite set of characters,
20. Example 9 – Encoding and Decoding Functions Digital messages consist of finite sequences of 0’s and
21. Example 9 – Encoding and Decoding Functions The receiver of the message decodes it by replacing
22. Example 9 – Encoding and Decoding Functions The encoding function E is the function from A
23. Example 9 – Encoding and Decoding Functions The advantage of this particular coding scheme is that
24. Boolean Functions
25. Boolean Functions We have discussed earlier that how to find input/output tables for certain digital logic
26. Boolean Functions
27. Example 11 – A Boolean Function Consider the three-place Boolean function defined from the set of
28. Example 11 – Solution The rest of the values of f can be calculated similarly to
29. Checking Whether a Function Is Well Defined
30. Checking Whether a Function Is Well Defined It can sometimes happen that what appears to be
31. Checking Whether a Function Is Well Defined For instance, when x = 2, there is no
32. Example 12 – A Function That Is Not Well Defined We know that Q represents the
33. Example 12 – Solution The function f is not well defined. The reason is that fractions
34. Example 12 – Solution But applying the formula for f, you find that and so This
35. Checking Whether a Function Is Well Defined Note that the phrase well-defined function is actually redundant;
36. Functions Acting on Sets
37. Functions Acting on Sets Given a function from a set X to a set Y, you
38. Example 13 – The Action of a Function on Subsets of a Set Let X =
40. Скачать презентацию

Слайд 2

Copyright © Cengage Learning. All rights reserved.
Functions Defined on General

Sets

SECTION 7.1

Слайд 3

Functions Defined on General Sets
We have already defined a function as

a certain type of relation. The following is a restatement of the definition of function that includes additional terminology associated with the concept.

Слайд 4

Arrow Diagrams

Слайд 5

Arrow Diagrams
We have known that if X and Y are finite

sets, you can define a function f from X to Y by drawing an arrow diagram.
You make a list of elements in X and a list of elements in Y, and draw an arrow from each element in X to the corresponding element in Y, as shown in Figure 7.1.1.

Figure 7.1.1

Слайд 6

Arrow Diagrams
This arrow diagram does define a function because
1. Every element

of X has an arrow coming out of it.
2. No element of X has two arrows coming out of it that point to two different elements of Y.

Слайд 7

Example 2 – A Function Defined by an Arrow Diagram
Let X

= {a, b, c} and Y = {1, 2, 3, 4}. Define a function f from X to Y by the arrow diagram in Figure 7.1.3.
a. Write the domain and co-domain of f.
b. Find f (a), f (b), and f (c).
c. What is the range of f ?
d. Is c an inverse image of 2? Is b an inverse image of 3?
e. Find the inverse images of 2, 4, and 1.
f . Represent f as a set of ordered pairs.

Figure 7.1.3

Слайд 8

Example 2 – Solution
a. domain of co-domain of
b.
c. range of
d.

Yes, No
e. inverse image of
inverse image of
inverse image of (since no arrows point to 1)
f.

Слайд 9

Arrow Diagrams
In Example 2 there are no arrows pointing to the

1 or the 3.
This illustrates the fact that although each element of the domain of a function must have an arrow pointing out from it, there can be elements of the co-domain to which no arrows point.
Note also that there are two arrows pointing to the 2—one coming from a and the other from c.

Слайд 10

Arrow Diagrams
Earlier we have given a test for determining whether two

functions with the same domain and co-domain are equal, saying that the test results from the definition of a function as a binary relation.
We formalize this justification in Theorem 7.1.1.

Слайд 11

Example 3 – Equality of Functions
a. Let J3 = {0, 1,

2}, and define functions f and g from J3 to J3 as follows: For all x in J3,
Does f = g?
b. Let F: R → R and G: R → R be functions. Define new functions F + G: R → R and G + F: R → R as follows: For all x ∈ R,
Does F + G = G + F?

Слайд 12

Example 3 – Solution
a. Yes, the table of values shows that

f (x) = g(x) for all x in J3.
b. Again the answer is yes. For all real numbers x,
Hence F + G = G + F.

Слайд 13

Examples of Functions

Слайд 14

Example 4 – The Identity Function on a Set
Given a set

X, define a function IX from X to X by
for all x in X.
The function IX is called the identity function on X because it sends each element of X to the element that is identical to it. Thus the identity function can be pictured as a machine that sends each piece of input directly to the output chute without changing it in any way.
Let X be any set and suppose that and are
elements of X. Find and .

Слайд 15

Example 4 – Solution
Whatever is input to the identity function comes

out unchanged, so and

Слайд 16

Examples of Functions

Слайд 17

Example 8 – The Logarithmic Function with Base b
Find the following:
a.

b. c.
d. e.
Solution:
a.
b.
c.

Слайд 18

Example 8 – Solution
d. because the exponent to which 2 must

be raised to obtain 2m is m.
e. because log2 m is the exponent to which 2 must be raised to obtain m.

cont’d

Слайд 19

Examples of Functions
We have known that if S is a nonempty,

finite set of characters, then a string over S is a finite sequence of elements of S.
The number of characters in a string is called the length of the string. The null string over S is the “string” with no characters.
It is usually denoted ∈ and is said to have length 0.

Слайд 20

Example 9 – Encoding and Decoding Functions
Digital messages consist of finite

sequences of 0’s and 1’s. When they are communicated across a transmission channel, they are frequently coded in special ways to reduce the possibility that they will be garbled by interfering noise in the transmission lines.
For example, suppose a message consists of a sequence of 0’s and 1’s. A simple way to encode the message is to write each bit three times. Thus the message
would be encoded as

Слайд 21

Example 9 – Encoding and Decoding Functions
The receiver of the message

decodes it by replacing each section of three identical bits by the one bit to which all three are equal.
Let A be the set of all strings of 0’s and 1’s, and let T be the set of all strings of 0’s and 1’s that consist of consecutive triples of identical bits.
The encoding and decoding processes described above are actually functions from A to T and from T to A.

cont’d

Слайд 22

Example 9 – Encoding and Decoding Functions
The encoding function E is

the function from A to T defined as follows: For each string s ∈ A,
E(s) = the string obtained from s by replacing each
bit of s by the same bit written three times.
The decoding function D is defined as follows: For each string t ∈ T,
D(t) = the string obtained from t by replacing each consecutive triple of three identical bits of t by a single copy of that bit.

cont’d

Слайд 23

Example 9 – Encoding and Decoding Functions
The advantage of this particular

coding scheme is that it makes it possible to do a certain amount of error correction when interference in the transmission channels has introduced errors into the stream of bits.
If the receiver of the coded message observes that one of the sections of three consecutive bits that should be identical does not consist of identical bits, then one bit differs from the other two.
In this case, if errors are rare, it is likely that the single bit that is different is the one in error, and this bit is changed to agree with the other two before decoding.

cont’d

Слайд 24

Boolean Functions

Слайд 25

Boolean Functions
We have discussed earlier that how to find input/output tables

for certain digital logic circuits.
Any such input/output table defines a function in the following way: The elements in the input column can be regarded as ordered tuples of 0’s and 1’s; the set of all such ordered tuples is the domain of the function.
The elements in the output column are all either 0 or 1; thus {0, 1} is taken to be the co-domain of the function. The relationship is that which sends each input element to the output element in the same row.

Слайд 26

Boolean Functions

Слайд 27

Example 11 – A Boolean Function
Consider the three-place Boolean function defined

from the set of all 3-tuples of 0’s and 1’s to {0, 1} as follows: For each triple (x1, x2, x3) of 0’s and 1’s,
Describe f using an input/output table.
Solution:

Слайд 28

Example 11 – Solution
The rest of the values of f can

be calculated similarly to obtain the following table.

cont’d

Слайд 29

Checking Whether a Function Is Well Defined

Слайд 30

Checking Whether a Function Is Well Defined
It can sometimes happen that

what appears to be a function defined by a rule is not really a function at all. To give an example, suppose we wrote, “Define a function f : R → R by specifying that for all real numbers x,
There are two distinct reasons why this description does not define a function. For almost all values of x, either (1) there is no y that satisfies the given equation or (2) there are two different values of y that satisfy the equation.

Слайд 31

Checking Whether a Function Is Well Defined
For instance, when x =

2, there is no real number y such that 22 + y2 = 1, and when x = 0, both y = –1 and y = 1 satisfy the equation 02 + y2 = 1.
In general, we say that a “function” is not well defined if it fails to satisfy at least one of the requirements for being a function.

Слайд 32

Example 12 – A Function That Is Not Well Defined
We know

that Q represents the set of all rational numbers. Suppose you read that a function f : Q → Z is to be defined by the formula
for all integers m and n with n ≠ 0.
That is, the integer associated by f to the number is m. Is f well defined? Why?

Слайд 33

Example 12 – Solution
The function f is not well defined.
The reason

is that fractions have more than one representation as quotients of integers.
For instance, Now if f were a function, then the
definition of a function would imply that since

Слайд 34

Example 12 – Solution
But applying the formula for f, you find

that
and so
This contradiction shows that f is not well defined and, therefore, is not a function.

cont’d

Слайд 35

Checking Whether a Function Is Well Defined
Note that the phrase well-defined

function is actually redundant; for a function to be well defined really means that it is worthy of being called a function.

Слайд 36

Functions Acting on Sets

Слайд 37

Functions Acting on Sets
Given a function from a set X to

a set Y, you can consider the set of images in Y of all the elements in a subset of X and the set of inverse images in X of all the elements in a
subset of Y.

Слайд 38

Example 13 – The Action of a Function on Subsets of

a Set

Let X = {1, 2, 3, 4} and Y = {a, b, c, d, e}, and define F : X → Y by the following arrow diagram:
Let A = {1, 4}, C = {a, b}, and D = {c, e}. Find F(A), F(X), F−1(C), and F−1(D).