南京大学：Strings and Languages Preliminaries（PPT课件讲稿）Preliminaries、Languages

大房 NANJING UNIVERSITY Preliminaries Mathematical preliminaries Strings and Languages

Mathematical Preliminaries Strings and Languages Preliminaries 1

Mathematical preliminaries

Mathematical Preliminaries

44 Mathematical Preliminaries Sets Functions Relations Graphs Proof Techniques

Mathematical Preliminaries • Sets • Functions • Relations • Graphs • Proof Techniques

SETS a set is a collection of elements A={1,2,3} B=train, bus, bicycle, airplane We write 1∈A Shi∈B

A ={1,2,3} A set is a collection of elements SETS B ={train,bus,bicycle,airplane} We write 1 A shipB

Set representations C=a,b,c,d,e,f,g, h, i,j, k C={a,b,…,k finite set S={2,4,6,…} infinite set s=:j>0, and j=2k for k>0) s=j: j is nonnegative and even j

Set Representations C = { a, b, c, d, e, f, g, h, i, j, k } C = { a, b, …, k } S = { 2, 4, 6, … } S = { j : j > 0, and j = 2k for k>0 } S = { j : j is nonnegative and even } finite set infinite set

A={1,2,3,4,5} U 6 A 23 8 45 10 Universal Set: all possible elements 10

A = { 1, 2, 3, 4, 5 } Universal Set: all possible elements U = { 1 , … , 10 } 1 2 3 4 5 A U 6 7 8 9 10

Set operations A=(1,2,3}B={2,3,4,5} Union AUB={1,2,3,4,5} 5 Intersection A∩B={2,3} Difference A-B={1} B-A={4,5}

Set Operations A = { 1, 2, 3 } B = { 2, 3, 4, 5} • Union A U B = { 1, 2, 3, 4, 5 } • Intersection A B = { 2, 3 } • Difference A - B = { 1 } B - A = { 4, 5 } U A B 2 3 1 4 5 2 3 1

Complement Universal set={1,…,7 A=({1,2,3}>A={4,5,6,7} 4 A 6 5 7 A=A

A • Complement Universal set = {1, …, 7} A = { 1, 2, 3 } A = { 4, 5, 6, 7} 1 2 3 4 5 6 7 A A = A

f even integers)= odd integers j Integers 1 odd even 5 0 4 7

0 2 4 6 1 3 5 7 even { even integers } = { odd integers } odd Integers

DeMorgan s Laws A∪B=A∩B A∩B=A∪B

DeMorgan’s Laws A U B = A BU A B = A U B U