計算理論與算法分析設計課件：集合、關系與語言

CH1集合、關系與語言

2024/7/12

of158

元素、成員集合是對象的匯集。例如:a,b,c,d的匯集是一個集合,記作L={a,b,c,d};

構成集合的所有對象叫做它的元素或成員。稱b在L中，或者L包含b。在集合中,不區(qū)分元素的重復及順序。{1,2,3}={1,3,3,2,2,2}。兩個集合相等（即,相同）當且僅當它們有相同的元素。一個集合的元素之間不需要有（除去它們都是同一個集合的元素外）什么關系。例如{3,red,{a,blue}}是有3個元素的集合,其中一個元素的本身是一個集合。單元集集合只有一個元素,這樣的集合叫做單元集。1.1集合2024/7/13

of158

集合運算定律1.1集合2024/7/14

of158不相交如果兩個集合沒有共同的元素,即它們的交是空集,則稱它們不相交。

廣義并和廣義交

{A1,A2,…,An}=A1

A2

…

An

{A1,A2,…,An}=A1

A2

…

An

S={{a,b},{b,c},{c,d}}，則

S={a,b,c}

S=空集

冪集2A1.1集合2024/7/15

of158

元素、成員單元集不相交

{A1,A2,…,An}=A1

A2

…

An

{A1,A2,…,An}=A1

A2

…

An1.1集合2024/7/16

of158劃分

非空集合A的劃分是2A

的一個子集Π,使得

不是Π的元素,并且A的每一個元素在且只在Π中的一個集合里,即,如果Π是A的子集的集合使得（1）Π的每一個元素非空,

（2）Π的不同元素是不交的,(3)

Π=A

則Π是A的一個劃分。

1.1集合2024/7/17

of1581.1集合2024/7/18

of1581.1集合2024/7/19

of1581.1集合2024/7/110

of158

有序對(a,b)a和b的有序對記作(a,b)，a和b稱為它的分量。

笛卡兒積

A和B的笛卡兒積是a

A并且b

B的所有有序對(a,b)組成的集合。

兩個集合A和B上的二元關系是A×B的子集。1.2關系與函數(shù)2024/7/111

of158函數(shù)f：A→B

BA={f|f：A→B}函數(shù)f：A→B,A

AA

在f下的象f[A

]={f(a)|a

A

}

f[A]：值域、定義域的像

1.2關系與函數(shù)2024/7/112

of158

一對一滿射雙射逆函數(shù)合成Qo

R

1.2關系與函數(shù)Qo

R={<a,b>|

c(<a,c>

Q

<c,b>

R)}

fo

g(a)=h(a)=g(f(a))2024/7/113

of158自然同構當在兩個集合之間規(guī)定一個特別簡單的雙射以后,有時能夠把定義域中的對象與它在值域中的象看作在實質上是不可區(qū)分的：一個是另一個的換名或一種重寫方式。例如,嚴格地說,單元集和有序一元組是不同的。但是,由于對每一個單元集{a},f({a})=(a)

是一個明顯的雙射,故偶爾地混淆兩者的區(qū)別也沒有多大影響。這樣的雙射叫做一個自然同構。1.2關系與函數(shù)2024/7/114

of158自然同構

1.2關系與函數(shù)2024/7/115

of158自然同構

1.2關系與函數(shù)2024/7/116

of158自反、對稱、反對稱、傳遞1.3特殊的二元關系

自反對稱反對稱傳遞性關系圖各點都有環(huán)無單向邊無雙向邊xi到xj有邊,xj

到xk有邊,則xi到xk也有邊例如{(a,b):a,b

P且a是b的兄弟}

2024/7/117

of158

無向圖（簡稱圖）等價關系P8圖1-6

等價類偏序全序極小元1.3特殊的二元關系2024/7/118

of158

等勢有窮的、無窮的若有一個從集合{1,…,n}到A的雙射函數(shù),則稱A是有窮的;若A不是有窮的,則它是無窮的.

無窮可數(shù)的：與N等勢的

可數(shù)的：有窮的或可數(shù)無窮的不可數(shù)的：不是可數(shù)的集合1.4有窮集合與無窮集合2024/7/119

of158

榫頭1.4有窮集合與無窮集合2024/7/120

of158

證明N×N是可數(shù)無窮的。1.4有窮集合與無窮集合(4)在第n輪,訪問第一個集合的第n個元素,第二個集合的n―1個元素,…,以及第n個集合的第一個元素。2024/7/121

of158

數(shù)學歸納法第一數(shù)學歸納法、第二數(shù)學歸納法1.5三個基本的證明技術2024/7/122

of158

鴿巢原理1.5三個基本的證明技術1.5.6：在任意一群至少有兩個人的人群中,至少有兩個人在這群人中相識的人數(shù)相同。（利用鴿巢原理。）2024/7/123

of158對角化原理1.5三個基本的證明技術2024/7/124

of158對角化原理1.5三個基本的證明技術2024/7/125

of158對角化原理1.5三個基本的證明技術2024/7/126

of158

自反傳遞閉包算法1:1.6閉包與算法2024/7/127

of158

算法2:1.6閉包與算法2024/7/128

of158

算法3:1.6閉包與算法2024/7/129

of158

封閉性1.6閉包與算法2024/7/130

of158閉包例1.6.9自然數(shù)集合N是集合{0,1}在加法下的閉包。N在加法和乘法下是封閉的，但在減法下不是封閉的。整數(shù)集合（正的、負的和零）是N在減法下的閉包。1.6閉包與算法2024/7/131

of158由特定的符號組成的有限集合稱為字母表。常見的字母表是由26個英文字母、10個阿拉伯數(shù)字、運算符號等組成的集合。0和1兩個數(shù)字也可以組成字母表。設∑是一個字母表，由∑上的符號組成的有窮序列稱為∑上的字符串。

01101111是字母表{0,1}上的字符串?？沾?e或者ε.∑*

:字母表∑上所有字符串(包括空串)的集合.{0,1}*字符串的長度.|w|，例如|010010|=6.1.7字母表與語言2024/7/132

of158連接:xo

y

或者xy01o001=01001前綴.后綴.子串.反轉.

xR

(wx)R=xRwR1.7字母表與語言2024/7/133

of158字母表∑上滿足一定條件的字符串的集合L，稱為∑上的一種語言。例

全體3位二進制數(shù)組成的字母表{0，1}上的語言可用列舉法表示出來：L＝{000，001，010，011，100，101，110，111}。L*:連接L中0個或多個字符串得到的所有字符串的集合.1.7字母表與語言2024/7/134

of158正則運算:定義正則運算并,連接,星號如下:

并:AB={x|xA或xB}

連接:AB={xy|xA且yB}

星號:A*={x1x2…xk|k0且每個xiA}設字母表

由標準的26個字母組成A={good,bad},B={boy,girl},則AB={good,bad,boy,girl}AB={goodboy,goodgirl,badboy,badgirl}A*={,good,bad,goodgood,goodbad,…}1.8語言的有窮表示2024/7/135

of158在計算理論中的第一個結果：不論用來表示語言的方法怎樣給力,只要表示的本身是有窮的,就只有可數(shù)多個語言能夠被表示。總共有不可數(shù)多個語言,在任何有窮的表示方案下，它們中的絕大多數(shù)將不可避免地被遺漏掉。1.8語言的有窮表示2024/7/136

of158正則表達式:稱R為正則表達式,若R是

1)a,a;2);3);4)