计算理论与算法16年CH0

1、CH0 绪论 2021-12-142 of 158n 元素、成员元素、成员n 单元集单元集n 不相交不相交n A1, A2, , An=A1 A2 An A1, A2, , An=A1 A2 Ann 幂集幂集2An 划分划分1 集合2021-12-143 of 158n 有序对有序对 (a, b)n 笛卡儿积笛卡儿积n 函数函数f：AB n BA = f | f：AB n函数函数 f：AB, AAnfA：值域、定义域的像：值域、定义域的像 3函数与关系:NNN,( , )( , )ffm nmnf m nmn2021-12-144 of 158n 一对一一对一n 满射满射n 双射双射n 逆函数

2、逆函数 3 关系与函数2021-12-145 of 158n合成合成Q R 3 函数与关系Q R = | c ( Q R) f g(a) = h(a) = g(f(a) 2021-12-146 of 158n自反、对称、反对称、传递自反、对称、反对称、传递3 特殊的二元关系自反自反对称对称反对称反对称传递性传递性关关系系图图各点各点都有都有环环无单无单向边向边无双向边无双向边xi到到xj有边有边, xj 到到xk有有边边, 则则xi到到xk也有边也有边 2021-12-147 of 158n 无向图（简称图）无向图（简称图）n 等价关系等价关系n 等价类等价类n 偏序偏序n 全序全序n 极小元

3、极小元3 特殊的二元关系2021-12-148 of 158n 等势等势n 有穷的、无穷的有穷的、无穷的 若有一个从集合 1, , n 到A 的双射函数,则称A 是有穷的; 若A 不是有穷的,则它是无穷的.n 无穷可数的：与无穷可数的：与N等势的等势的 n 可数的：有穷的或可数无穷的可数的：有穷的或可数无穷的n 不可数的不可数的3 有穷集合与无穷集合2021-12-149 of 158n 3 有穷集合与无穷集合2021-12-1410 of 158n 数学归纳法数学归纳法n 反证法反证法n 鸽巢原理鸽巢原理4 三个基本的证明技术2021-12-1411 of 158n由特定的符号组成的有限集合

4、称为由特定的符号组成的有限集合称为字母字母表表。常见的字母表是由。常见的字母表是由26个英文字母、个英文字母、10个阿拉伯数字、运算符号等组成的集个阿拉伯数字、运算符号等组成的集合。合。0和和1两个数字也可以组成字母表。两个数字也可以组成字母表。n设设是一个字母表，由是一个字母表，由上的符号组成的上的符号组成的有穷序列称为有穷序列称为上的上的字符串字符串。n空串空串: e或者或者.5 字母表与语言2021-12-1412 of 158n连接连接: x y 或者或者xy n前缀前缀.n后缀后缀.n子串子串.n反转反转. xR (wx)R= xRwR5 字母表与语言2021-12-1413 of

5、158n字母表字母表上满足一定条件的字符串的上满足一定条件的字符串的集合集合L，称为，称为上的一种上的一种语言语言。n例例 全体全体3位二进制数组成的字母表位二进制数组成的字母表0，1上的语言可用列举法表示出来：上的语言可用列举法表示出来：L000，001，010，011，100，101，110，111。5 字母表与语言2021-12-1414 of 158n正则运算正则运算:定义正则运算并定义正则运算并,连接连接,星号如下星号如下: 并并: A B=x|x A或或x B 连接连接: A B=xy|x A且且y B 星号星号: A*=x1x2xk|k 0且每个且每个xi A设字母表设字母表 由由标准的标准的2626个字母组成个字母组成A=good,bad, B=boy,gi