计算理论与算法分析设计：CH1 集合、关系与语言

CH1集合、关系与语言

11/6/20221元素、成员集合是对象的汇集。例如:a,b,c,d的汇集是一个集合,记作L={a,b,c,d};

构成集合的所有对象叫做它的元素或成员。称b在L中，或者L包含b。在集合中,不区分元素的重复及顺序。{1,2,3}={1,3,3,2,2,2}。两个集合相等（即,相同）当且仅当它们有相同的元素。一个集合的元素之间不需要有（除去它们都是同一个集合的元素外）什么关系。例如{3,red,{a,blue}}是有3个元素的集合,其中一个元素的本身是一个集合。单元集集合只有一个元素,这样的集合叫做单元集。1.1集合11/6/20222集合运算定律1.1集合11/6/20223不相交如果两个集合没有共同的元素,即它们的交是空集,则称它们不相交。

广义并和广义交{A1,A2,…,An}=A1A2…An{A1,A2,…,An}=A1A2…An

S={{a,b},{b,c},{c,d}}，则S={a,b,c}S=空集

幂集2A1.1集合11/6/20224元素、成员单元集不相交

{A1,A2,…,An}=A1A2…An{A1,A2,…,An}=A1A2…An1.1集合11/6/20225划分

非空集合A的划分是2A

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

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

则Π是A的一个划分。

1.1集合11/6/202261.1集合11/6/202271.1集合11/6/202281.1集合11/6/20229有序对(a,b)a和b的有序对记作(a,b)，a和b称为它的分量。

笛卡儿积

A和B的笛卡儿积是a

A并且bB的所有有序对(a,b)组成的集合。

两个集合A和B上的二元关系是A×B的子集。1.2关系与函数11/6/202210函数f：A→B

BA={f|f：A→B}函数f：A→B,AAA在f下的象f[A]={f(a)|aA}

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

1.2关系与函数11/6/202211一对一满射双射逆函数合成Qº

R

1.2关系与函数Qº

R={<a,b>|

c(<a,c>Q<c,b>R)}

fº

g(a)=h(a)=g(f(a))11/6/202212自然同构当在两个集合之间规定一个特别简单的双射以后,有时能够把定义域中的对象与它在值域中的象看作在实质上是不可区分的：一个是另一个的换名或一种重写方式。例如,严格地说,单元集和有序一元组是不同的。但是,由于对每一个单元集{a},f({a})=(a)

是一个明显的双射,故偶尔地混淆两者的区别也没有多大影响。这样的双射叫做一个自然同构。1.2关系与函数11/6/202213自然同构

1.2关系与函数11/6/202214自然同构

1.2关系与函数11/6/202215自反、对称、反对称、传递1.3特殊的二元关系自反对称反对称传递性关系图各点都有环无单向边无双向边xi到xj有边,xj

到xk有边,则xi到xk也有边例如{(a,b):a,b

P且a是b的兄弟}

11/6/202216

无向图（简称图）等价关系P8图1-6

等价类偏序全序极小元1.3特殊的二元关系11/6/202217等势有穷的、无穷的若有一个从集合{1,…,n}到A的双射函数,则称A是有穷的;若A不是有穷的,则它是无穷的.

无穷可数的：与N等势的

可数的：有穷的或可数无穷的不可数的：不是可数的集合1.4有穷集合与无穷集合11/6/202218榫头1.4有穷集合与无穷集合11/6/202219证明N×N是可数无穷的。1.4有穷集合与无穷集合(4)在第n轮,访问第一个集合的第n个元素,第二个集合的n―1个元素,…,以及第n个集合的第一个元素。11/6/202220数学归纳法第一数学归纳法、第二数学归纳法1.5三个基本的证明技术11/6/202221鸽巢原理1.5三个基本的证明技术1.5.6：在任意一群至少有两个人的人群中,至少有两个人在这群人中相识的人数相同。（利用鸽巢原理。）11/6/202222对角化原理1.5三个基本的证明技术11/6/202223对角化原理1.5三个基本的证明技术11/6/202224对角化原理1.5三个基本的证明技术11/6/202225自反传递闭包算法1:1.6闭包与算法11/6/202226算法2:1.6闭包与算法11/6/202227算法3:1.6闭包与算法11/6/202228封闭性1.6闭包与算法11/6/202229闭包例1.6.9自然数集合N是集合{0,1}在加法下的闭包。N在加法和乘法下是封闭的，但在减法下不是封闭的。整数集合（正的、负的和零）是N在减法下的闭包。1.6闭包与算法11/6/202230由特定的符号组成的有限集合称为字母表。常见的字母表是由26个英文字母、10个阿拉伯数字、运算符号等组成的集合。0和1两个数字也可以组成字母表。设∑是一个字母表，由∑上的符号组成的有穷序列称为∑上的字符串。

01101111是字母表{0,1}上的字符串。空串:e或者ε.∑*

:字母表∑上所有字符串(包括空串)的集合.{0,1}*字符串的长度.|w|，例如|010010|=6.1.7字母表与语言11/6/202231连接:xº

y

或者xy01º001=01001前缀.后缀.子串.反转.

xR

(wx)R=xRwR1.7字母表与语言11/6/202232字母表∑上满足一定条件的字符串的集合L，称为∑上的一种语言。例

全体3位二进制数组成的字母表{0，1}上的语言可用列举法表示出来：L＝{000，001，010，011，100，101，110，111}。L*:连接L中0个或多个字符串得到的所有字符串的集合.1.7字母表与语言11/6/202233正则运算:定义正则运算并,连接,星号如下:

并: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语言的有穷表示11/6/202234在计算理论中的第一个结果：不论用来表示语言的方法怎样给力,只要表示的本身是有穷的,就只有可数多个语言能够被表示。总共有不可数多个语言,在任何有穷的表示方案下，它们中的绝大多数将不可避免地被遗漏掉。1.8语言的有穷表示11/6/202235正则表达式:称R为正则表达式,若R是

1)a,a;2);3);4)(R1R2),这里R1和R