南京大学：《程序设计语言的形式语义》课程教学资源（课件讲稿）03_Math

Outline Sets Relations Functions Products Sums 2/40

Outline Sets Relations Functions Products Sums 2 / 40

Sets -Basic Notations x∈S membership SCT subset SCT proper subset S Cfin T finite subset S=T equivalence 0 the empty set N natural numbers Z integers B [true,false 4/40

Sets – Basic Notations x ∈ S membership S ⊆ T subset S ⊂ T proper subset S ⊆fin T finite subset S = T equivalence ∅ the empty set N natural numbers Z integers B {true,false} 4 / 40

Sets -Basic Notations SnT intersection sr{xIx∈S and x∈T} SUT union s{x xES orx∈T} S-T difference 些{xIx∈S and x年T} P(S) powerset ef{TlT≤S} [m,n] integer range s{x|m≤x≤n 5/40

Sets – Basic Notations S ∩ T intersection def = {x | x ∈ S and x ∈ T} S ∪ T union def = {x | x ∈ S or x ∈ T} S − T difference def = {x | x ∈ S and x 6∈ T} P(S) powerset def = {T | T ⊆ S} [m, n] integer range def = {x | m ≤ x ≤ n} 5 / 40

Generalized Unions of Sets US s{x|3T∈S.x∈T} U5(i) d UfS(i)Iiel iel 050些 U s(i) i=m ie[m,n Here S is a set of sets.S(i)is a set whose definition depends on i. For instance,we may have S(i)={x|x>i+3} Given i=1,2,...,n,we know the corresponding S(i). 6/40

Generalized Unions of Sets S S def = {x | ∃T ∈ S. x ∈ T} S i∈I S(i) def = S {S(i) | i ∈ I } Sn i=m S(i) def = S i∈[m,n] S(i) Here S is a set of sets. S(i) is a set whose definition depends on i. For instance, we may have S(i) = {x | x > i + 3} Given i = 1, 2, . . . , n, we know the corresponding S(i). 6 / 40

Generalized Unions of Sets Example(1) AUB=A,B} Proof? Example (2) LetS(i)=[i,i+1]andI={U2Ij∈[1,3]}，then US(i)={1,2,4,5,9,10} iel 1/40

Generalized Unions of Sets Example (1) A ∪ B = [ {A, B} Proof? Example (2) Let S(i) = [i, i + 1] and I = {j 2 | j ∈ [1, 3]}, then [ i∈I S(i) = {1, 2, 4, 5, 9, 10} 7 / 40

Generalized Intersections of Sets ∩S 些{x VTES.xeT} ∩S(i) def ∩{S()|i∈} iel 50些∩50 i三m ie m,n 8/40

Generalized Intersections of Sets T S def = {x | ∀T ∈ S. x ∈ T} T i∈I S(i) def = T {S(i) | i ∈ I } Tn i=m S(i) def = T i∈[m,n] S(i) 8 / 40

Generalized Unions and Intersections of Empty Sets From USgf{xI3T∈S.xeT} ∩Sg{x|TeS.xeT} we know U0=0 ∩0 meaningless 0is meaningless,since it denotes the paradoxical "set of everything". 9/40

Generalized Unions and Intersections of Empty Sets From S S def = {x | ∃T ∈ S. x ∈ T} T S def = {x | ∀T ∈ S. x ∈ T} we know S ∅ = ∅ T ∅ meaningless T ∅ is meaningless, since it denotes the paradoxical ”set of everything”. 9 / 40

Outline Sets Relations Functions Products Sums 10/40

Outline Sets Relations Functions Products Sums 10 / 40

Relations We need to first define the Cartesian product of two sets A and B: A×B={(x,y)Ix∈A and y∈B} Here (x,y)is called a pair. Projections over pairs: πo(x,y）=xand1(x,y)=y. Then.p is a relation from A to B if pC Ax B,or pEP(Ax B) 11/40

Relations We need to first define the Cartesian product of two sets A and B: A × B = {(x, y) | x ∈ A and y ∈ B} Here (x, y) is called a pair. Projections over pairs: π0(x, y) = x and π1(x, y) = y. Then, ρ is a relation from A to B if ρ ⊆ A × B, or ρ ∈ P(A × B). 11 / 40

Relations p is a relation from A to B if pAx B,orp∈P(A×B). p is a relation on S if pSx S. We say p relates x and y if(x,y)Ep.Sometimes we write it as xpy. p is an identity relation if∀x,y）∈p.x=y. 12/40

Relations ρ is a relation from A to B if ρ ⊆ A × B, or ρ ∈ P(A × B). ρ is a relation on S if ρ ⊆ S × S. We say ρ relates x and y if (x, y) ∈ ρ. Sometimes we write it as x ρ y. ρ is an identity relation if ∀(x, y) ∈ ρ. x = y. 12 / 40