Transcript §4 谓词演算的性质

 RA×B,R
is a relation from A to B，
DomRA。
 (a,b)R (a, c)R
 (a,b)R (a, c)R unless b=c
 function
 DomR=A， (everywhere)function。
Chapter 3 Functions
 3.1

Introduction
Definition3.1: Let A and B be nonempty sets. A
relation is a (everywhere)function from A to B,
denoted by f : AB, if for every aA, there is one
and only b B so that (a,b) f, we say that b=f (a).
The set A is called the domain of the function f. If
XA, then f(X)={f(a)|aX} is called the image of X.
The image of A itself is called the range of f, we write
Rf. If YB, then f -1(Y)={a|f(a)Y} is called the
preimage of Y. A function f : AB is called a
mapping. If (a,b) f so that b= f (a), then we say that
the element a is mapped to the element b.
 (everywhere)function:
 (1)Domf=A；
(a,b) and (a,b')f, then b=b‘
 Relation: (a,b),(a,b')R,
 function : if (a,b) and (a,b')f, then b=b‘
 Relation: DomRA
 (everywhere)function: DomR=A
 (2)if
 Example：Let A={1,2,3,4},B={a,b,c},
 R1={(1,a),(2,b),(3,c)},
 R2={(1,a),(1,b),(2,b),(3,c),(4,c)},
 R3={(1,a),(2,b),(3,b),(4,a)}
 Example: Let A ={-2,-1, 0,1,2} and
B={0,1,2,3,4,5}.
 Let f={(-2,0),(-1,1), (0,0),(1,3),(2,5)}. f is a
(everywhere)function.
 X={-2,0,1}, f(X)=?
 Y={0,5}, f -1(Y)=?
 Theorem
3.1: Let f be a (everywhere)
function from A to B, and A1 and A2 be
subsets of A. Then
 (1)If A1A2, then f(A1) f(A2)
 (2) f(A1∩A2) f(A1)∩f(A2)
 (3) f(A1∪A2)= f(A1)∪f(A2)
 (4) f(A1)- f(A2) f(A1-A2)
(3)(a) f(A1)∪f (A2) f(A1∪A2)
 (b) f(A1∪A2) f(A1)∪f (A2)
 Proof:
 (4)
f (A1)- f (A2) f (A1-A2)
 for any y f (A1)-f (A2)

Theorem 3.2：Let f be a (everywhere) function
from A to B, and AiA(i=1,2,…n). Then
n
n
i 1
i 1
(1) f (  Ai )   f ( Ai )
n
n
i 1
i 1
( 2) f (  Ai )   f ( Ai )
2. Special Types of functions
 Definition 3.2：Let A be an arbitrary nonempty set.
The identity function on A, denoted by IA, is
defined by IA(a)=a.
 Definition 3.3.: Let f be an everywhere function
from A to B. Then we say that f is onto(surjective)
if Rf=B. We say that f is one to one(injective) if we
cannot have f(a1)=f(a2) for two distinct elements a1
and a2 of A. Finally, we say that f is one-to-one
correspondence(bijection), if f is onto and one-toone.
 The definition of one to one may be restated in the
following equivalent form:
 If f(a1)=f(a2) then a1=a2 for all a1, a2A Or
 If a1a2 then f(a1)f(a2) for all a1, a2A

 Example:1)
Let f: R(the set of real
numbers)→C(the set of complex number),
f(a)=i|a|;
 2)Let g: R(the set of real numbers)→C(the
set of complex number), g(a)=ia;
 3)Let h:Z→Zm={0,1,…m-1}, h(a)=a mod m
 onto ,one to one?
 3.2
Composite functions and Inverse functions
 1.Composite functions
 Relation ,Composition,
 Theorem3.3: Let g be a (everywhere)function
from A to B, and f be a (everywhere)function
from B to C. Then composite relation f g is a
(everywhere)function from A to C.
 Proof:
(1)For any aA, there exists cC such
that (a,c) f g?
 (2)For every aA, If there exist x,yC such
that (a,x) f gand (a,y) f g，then x=y?
 Definition 3.4: Let g be a (everywhere)
function from A to B, and f be a (everywhere)
function from B to C. Then composite
relation f g is called a (everywhere) function
from A to C, we write f g:A→C. If aA,
then(f g)(a)=f(g(a)).
 Since
composition of relations has been shown
to be associative (Theorem 2.), we have as a
special case the following theorem.
 Theorem 3.4: Let f be a (everywhere) function
from A to B, and g be a (everywhere) function
from B to C, and h be a (everywhere) function
from C to D. Then h(gf )=(hg)f
 Exercise:
P176 2,9,10,13,14,
 28,37,38
 Next:
Inverse functions
 The Characteristic function of the set
P178 5.2
Cardinality
Paradox