离散数学

本教材以离散数学课程重要知识点为纽带，夯实程序设计思路，拓展数据结构中数据和关系的表示方法，提高学生从实例计算到类计算的应用能力。使学生充分掌握“问题-形式化-自动化（计算机化）”方法，结合*知识分类方法和图论的相关研究成果拓展课程涉及的相关原理与方法，为培养创新研究型人才打下良好的基础。本教材为全国高等学校计算机教育研究会2018 年度课题。 

本书是全国高等学校计算机教育研究会支持的立项教材，较全面地介绍了离散数学的基本理论及基本方法。本书以离散数学课程重要知识点为纽带，夯实程序设计思路，拓展数据和关系的表示方法，强化从实例计算到模型计算和问题—形式化—自动化（计算机化）等方法，旨在为后续的科学研究打下良好的基础。全书由命题演算基础、命题演算的推理理论、谓词演算基础、谓词演算的推理理论、递归函数论、集合、关系、函数与集合的势、图论、树和有序树、群和环、格与布尔代数共12章组成。
本书可作为高等院校计算机科学与技术及相关专业离散数学课程教材，也可作为教师、研究生或软件技术人员的参考书。

目录 第1章命题演算基础1
1.1命题和联结词1
1.1.1命题1
1.1.2联结词2
1.1.3合式公式6
1.1.4命题逻辑的应用6
1.2真假性9
1.2.1解释9
1.2.2等价公式10
1.2.3联结词的完备集12
1.2.4对偶式和内否式13
1.3范式及其应用15
1.3.1范式15
1.3.2主范式17
1.3.3范式的应用20
1.4典型例题21
习题23
第2章命题演算的推理理论26
2.1命题演算的公理系统26
2.1.1公理系统的组成部分27
2.1.2公理系统的推理过程28
2.2若干重要的导出规则30
2.2.1分离规则的讨论30
2.2.2公理和定理的导出规则30
2.3命题演算的假设推理系统32
2.3.1假设推理系统的组成32
2.3.2假设推理系统的推理过程33〖1〗离 散 数 学 〖1〗目录 2.3.3额外假设推理法35
2.4命题演算的归结推理法37
2.4.1归结证明过程38
2.4.2归结证明示例39
2.5典型例题40
习题43
第3章谓词演算基础45
3.1谓词和个体45
3.1.1个体45
3.1.2谓词45
3.2函数项和量词48
3.2.1函数项48
3.2.2量词49
3.3自由变元和约束变元51
3.3.1自由出现和约束出现51
3.3.2改名和代入51
3.4永真性和可满足性53
3.4.1真假性53
3.4.2同真假性、永真性和可满足性55
3.4.3范式58
3.5唯一性量词和摹状词59
3.5.1唯一性量词59
3.5.2摹状词60
3.6典型例题61
习题62
第4章谓词演算的推理理论65
4.1谓词演算的永真推理系统65
4.1.1公理系统的组成部分65
4.1.2公理系统的推理过程67
4.2谓词演算的假设推理系统68
4.2.1假设推理系统的组成及证明方法68
4.2.2定理的假设推导过程69
4.3谓词演算的归结推理系统71
4.3.1置换72
4.3.2归结反演系统72
4.3.3霍恩子句逻辑程序75
4.4Prolog简介78
4.5典型例题80
习题82
第5章递归函数论85
5.1数论函数和数论谓词85
5.1.1数论函数85
5.1.2数论谓词和特征函数86
5.2函数的构造88
5.2.1迭置法88
5.2.2算子法90
5.2.3原始递归函数91
5.3典型例题92
习题92
第6章集合94
6.1集合的基本概念94
6.1.1集合的定义94
6.1.2集合的表示95
6.1.3集合的包含关系96
6.1.4集合的特点97
6.1.5多重集97
6.2集合的基本运算98
6.2.1集合的并、交、差98
6.2.2集合的对称差99
6.2.3文氏图100
6.2.4集合的幂集合101
6.2.5多个集合的并与交101
6.3全集和补集102
6.3.1全集和补集的定义102
6.3.2基本运算定理103
6.3.3集合的计算机表示104
6.4自然数与自然数集105
6.4.1后继105
6.4.2自然数和自然数集105
6.4.3皮亚诺公理假设106
6.4.4自然数集的性质107
6.4.5集合的递归定义与递归子程序108
6.5包含与排斥原理110
6.6典型例题112
习题113
第7章关系118
7.1集合的笛卡儿积集118
7.1.1有序二元组118
7.1.2笛卡儿积集118
7.1.3有序n元组、n个集合的笛卡儿积集119
7.2二元关系的基本概念120
7.2.1二元关系120
7.2.2二元关系的表示120
7.2.3二元关系与数据结构122
7.2.4二元关系的运算122
7.3n元关系及其运算125
7.3.1n元关系125
7.3.2n元关系的运算125
7.4二元关系的性质128
7.4.1自反性、反自反性、对称性、反对称性、传递性和反传递性128
7.4.2二元关系性质的判定定理130
7.5二元关系的闭包运算132
7.5.1自反闭包、对称闭包和传递闭包132
7.5.2闭包的判定定理132
7.6等价关系和集合的划分137
7.6.1等价关系和等价类137
7.6.2商集合138
7.6.3集合的划分138
7.7偏序关系和格141
7.7.1偏序关系和偏序集141
7.7.2哈斯图142
7.7.3链、反链、全序集142
7.7.4极大元、极小元、最大元和最小元143
7.7.5上界、下界、最小上界和最大下界143
7.7.6格144
7.7.7拓扑排序145
7.8粗糙集概论147
7.8.1知识与知识分类147
7.8.2集合近似与粗糙集概念150
7.9典型例题151
习题152
第8章函数与集合的势157
8.1函数的基本概念157
8.1.1函数(映射)的定义157
8.1.2函数的性质159
8.2函数的复合和逆函数160
8.2.1函数的复合160
8.2.2左可逆函数、右可逆函数和逆函数162
8.3无限集164
8.3.1势164
8.3.2有限集和无限集166
8.3.3可数无限集和不可数无限集166
8.4集合势大小的比较168
8.4.1集合势的大小168
8.4.2伯恩斯坦定理169
8.5鸽巢原理169
8.6典型例题171
习题172
第9章图论175
9.1图的基本概念175
9.1.1有向图和无向图176
9.1.2图的同构、子图和补图177
9.1.3顶点的度178
9.2图中的通路、图的连通性和图的矩阵表示179
9.2.1通路、回路和连通性179
9.2.2图的矩阵表示181
9.3带权图与带权图中的最短通路184
9.4欧拉图187
9.5哈密顿图190
9.6二部图194
9.7平面图与平面图的着色197
9.7.1平面图197
9.7.2平面图的着色200
9.8典型例题203
习题204
第10章树和有序树209
10.1树的基本概念209
10.2连通图的生成树和带权连通图的最小生成树211
10.3有序树214
10.3.1根树214
10.3.2根树的应用216
10.4前缀码和最优2分树218
10.4.1前缀码218
10.4.2最优2分树220
10.4.3赫夫曼编码222
10.5典型例题224
习题226
第11章群和环229
11.1代数运算的基本概念229
11.1.1代数运算229
11.1.2交换律、结合律230
11.1.3n元运算231
11.2代数系统和半群232
11.2.1代数系统232
11.2.2同态映射和同构映射233
11.2.3半群与含幺半群235
11.3群的基本概念236
11.3.1逆元236
11.3.2群的定义237
11.3.3群的同态、同构240
11.3.4无限群、有限群、交换群和元的阶242
11.4群的几个等价定义244
11.5变换群和置换群245
11.5.1变换群246
11.5.2置换群247
11.6循环群250
11.7子群252
11.7.1子群的定义252
11.7.2子群的判定定理252
11.8子群的陪集254
11.8.1按子群划分的剩余类254
11.8.2右陪集254
11.8.3左陪集256
11.8.4拉格朗日定理257
11.9正规子群和商群259
11.9.1正规子群259
11.9.2商群260
11.10环和域262
11.10.1环、子环与理想263
11.10.2交换环和整环264
11.10.3除环和域264
11.11典型例题265
习题268
第12章格与布尔代数271
12.1格定义的代数系统271
12.2格的代数定义273
12.2.1格的代数定义273
12.2.2子格275
12.2.3格的同态和同构275
12.3一些特殊的格276
12.3.1分配格276
12.3.2布尔格和布尔代数278
12.4有限布尔代数的唯一性279
12.4.1原子279
12.4.2有限布尔代数非零元素的表达279
12.4.3布尔代数的同构280
12.5布尔表达式和布尔函数282
12.5.1布尔表达式282
12.5.2布尔函数283
12.6典型例题285
习题286
参考文献288

离散数学是计算机科学与技术重要的理论基础课程，它不仅是计算机科学的核心课程，而且已成为电子信息类专业的热门选修课。离散数学与计算机科学有着十分密切的关系。无论是数字计算机雏形的图灵机，还是数字电路的布尔代数，以及程序设计语言、关系数据库、知识表示、人工智能等领域均离不开离散数学；同时两者的相互渗透推动了离散数学的发展。因此，学好离散数学对计算机科学与理论的研究有着重要的作用。
离散数学以研究离散量的结构和相互间的关系为主要目标，旨在介绍离散数学各个分支的基本概念、基本理论和基本方法。本书以离散数学课程重要知识点为纽带，夯实程序设计思路，拓展数据和关系的表示方法，强化从实例计算到模型计算的应用能力，使读者充分掌握问题—形式化—自动化（计算机化）方法，为后续的学习和科学研究打下良好的基础。
本书基于全国高等学校计算机教育研究会的教材规范对离散数学教学内容进行编著，强化了离散数学的相关概念及其应用，注重相关课程内容的相互渗透。本书共12章，主要内容包括命题演算基础、命题演算的推理理论、谓词演算基础、谓词演算的推理理论、递归函数论、集合、关系、函数与集合的势、图论、树和有序树、群和环、格与布尔代数。
本书第1、2、3、5、7、9、10章由朱保平编写，第6、8、12章由金忠编写，第4章由陆建峰编写，第11章由叶有培编写，第6～12章由叶有培统一策划。张琨教授参与了部分内容的编写。
由于作者水平有限，书中难免存在疏漏和不足之处，恳请读者批评指正。

作者
2018年12月
于南京理工大学离散数学

第5章递归函数论
递归函数是数论函数，以自然数为研究对象，定义域和值域均为自然数。它为能行可计算函数找出各种理论上的、严密的类比物，即某个函数能否用若干可计算函数通过某种已有的算法（如迭置或算子）在有限步内递归产生，若能，说明该函数为可计算函数，否则为不可计算函数，因此，递归函数论又称为可计算性理论。
下面举几个例子说明函数的可计算性。
例5.1：  g(n)=n表示取自然数n的平方根的整数部分。
将n依次与12，22，32，…作比较，总可求得g(n)的值，所以g(n)是可计算的。
例5.2：  g(n)=0π的展开式中有n个连续的9
1否则
因π的展开式是一个无穷序列，要计算上述函数可能是一个无限过程，故函数g(n)为不可计算函数。
5.1数论函数和数论谓词〖1〗5.1.1数论函数定义5.1：  数论函数是指以自然数集为定义域及值域的函数。
下面简单介绍常用的数论函数，其中x、y均为自然数域中的变元。
x y指x与y的和。
xy指x与y的积。
x·-y指x与y的算术差，即x≥y时，其值为x-y，否则为0。
x··-y指x与y的绝对差，即大数减小数。
x指x的平方根的整数部分。
x/y指x与y的算术商。
rs(x，y)指y除x的余数，约定y=0时，rs(x，y)=x。
dv(x，y)指x与y的最大公约数，约定xy=0时，其值为x y。
lm(x，y)指x与y的最小公倍数，约定xy=0时，其值为0。第5章递归函数论离 散 数 学I(x)=x指函数值与自变量的值相同，称为幺函数。
Imn(x1，x2，…，xn，…，xm)=xn，即函数值与第n个自变量的值相同，此函数称为广义幺函数。
O(x)=0，即函数值永为0，称为零函数。
S(x)=x 1，称为后继函数。
D(x)指x的前驱，称为前驱函数。当x=0时，其值为0；当x>1时，其值为x-1。
Ca(x)=a，即函数值永为a，这个函数称为常值函数。
函数xNy、xN2y的定义如下：  xNy=x当y=0时
0当y≠0时xN2y=0当y=0时
x当y≠0时特例，当x=1时有Ny=1当y=0时
0当y≠0时N2y=0当y=0时
1当y≠0时
eq(x，y)=0当x=y时
1当x≠y时特别地，把广义幺函数、零函数和后继函数称为本原函数，它们是构造函数的最基本单位。
5.1.2数论谓词和特征函数1. 数论谓词和特征函数在第3章中提到的谓词是以个体为定义域，以真假为值域的函数，而含有变元的语句是指含有个体变元的谓词填式或由它们利用真值联结词和量词组成的式子，即谓词演算公式。
定义5.2：  数论谓词是指以自然数集为定义域,以真假为值域的谓词。由数论谓词利用联结词和量词构成的式子称为数论语句。例如，“2为质数”“8>7且9为平方数”等均为数论语句。
定义5.3：  设A(x1，x2，…，xn)是一个含有n个变量的语句，f(x1，x2，…，xn)是一个数论函数，若对于任何变元组均有
A(x1，x2，…，xn)为真时，f(x1，x2，…，xn)=0；
A(x1，x2，…，xn)为假时，f(x1，x2，…，xn)=1。
则称f(x1，x2，…，xn)是语句A(x1，x2，…，xn)的特征函数，记为ctA(x1，x2，…，xn)。
定理5.1：  任何一个语句均有唯一的特征函数。
证明：  
（1） 存在性。对于任何一个语句A，恒可以按如上定义一个函数f(x1，x2，…，xn)，此函数必为语句A的特征函数，故存在性得证。
（2） 唯一性。设f和g为语句A的两个特征函数，由上定义知
当A(x1，x2，…，xn)为真时，f(x1，x2，…，xn)=g(x1，x2，…，xn)=0当A(x1，x2，…，xn)为假时，f(x1，x2，…，xn)=g(x1，x2，…，xn)=1再由函数的相等性知，f(x1，x2，…，xn)=g(x1，x2，…，xn)，即语句A(x1，x2，…，xn)的特征函数是唯一的。
定理5.2：  如果有一个函数f(x1，x2，…，xn)满足下列条件：  A(x1，x2，…，xn)为真当且仅当f(x1，x2，…，xn)=0则N2f(x1，x2，…，xn)为语句A(x1，x2，…，xn)的特征函数。
证明：  当A(x1，x2，…，xn)为真时，由于f(x1，x2，…，xn)=0，所以N2f(x1，x2，…，xn)=0；当A(x1，x2，…，xn)为假时，由已知条件知f(x1，x2，…，xn)≠0，所以N2f(x1，x2，…，xn)=1。
由特征函数的定义知N2f(x1，x2，…，xn)为语句A(x1，x2，…，xn)的特征函数。
此时把函数f(x1，x2，…，xn)称为A(x1，x2，…，xn)的准特征函数。
2. 简单语句的特征函数
表5.1是一些包含变量的语句的特征函数。  表5.1一些包含变量的语句的特征函数
语句特 征 函 数语句特 征 函 数x为0N2xx不等于0Nxx为y的倍数N2rs(x，y) x小于yN2((x 1)·-y)x与y互质N2(dv(x，y)··-1)3. 复合语句的特征函数
定理5.3：  设A、B为任意两个语句，则有ctA=1·-ctA=NctA
ct(A∨B)=ctA·ctB=min(ctA，ctB)
ct(A∧B)=N2(ctA ctB)=max(ctA，ctB)
ct(A→B)=ctB·NctA
ct(AB)=ctA··-ctB例5.3：  给出“a为b的倍数且a为平方数”的特征函数。
解：  “a为b的倍数”的特征函数为N2rs(a，b)，“a为平方数”的特征函数为N2(a·-[a]2)
由定理5.3知原句的特征函数为N2(N2rs(a，b) N2(a·-[a]2))例5.4：  给出“x≥2且由a除尽x可推出a=1或a=x”的特征函数。
解：  令
A表示“x≥2”，其特征函数为N2(2·-x)；
B表示“a除尽x”，其特征函数为N2rs(x，a)；
C表示“a=1”，其特征函数为N2(a··-1)；
D表示“a=x”，其特征函数为N2(a··-x)。
原句译为A∧(B→(C∨D))其特征函数为ct(A∧(B→(C∨D)))=N2(ctA ctC·ctD·NctB)则原句的特征函数为N2(N2(2·-x) N2(a··-1)·N2 (a··-x)·Nrs(x，a))下面简单讨论用量词构成的语句的特征函数。
x→nA(x)表示对于任何0到n的一切x均使得A(x)成立。此量词称为受限全称量词。
x→nA(x)表示对于任何0到n至少有一个x使A(x)成立。此量词称为受限存在量词。
定理5.4：   设A(x)为任意一个含有x的语句，则有
（1） ct(x→nA(x))=max(ctA(0)，ctA(1)，ctA(2)，…，ctA(n))
=N2(ctA(0) ctA(1) ctA(2) … ctA(n))
（2） ct(x→nA(x))=min(ctA(0)，ctA(1)，ctA(2)，…，ctA(n))
=ctA(0)·ctA(1)·ctA(2)·…·ctA(n)
5.2函数的构造
前面介绍了一些常用的简单函数，这些简单函数均可采用直接定义的方法来产生。显然直接定义的方法只能产生少量简单的函数，而对于绝大多函数来说，无法用直接定义的方法产生，为此，必须利用已定义的函数（称为旧函数）来构造新函数，这种方法称为派生法。派生法有两类：   一类是迭置法，另一类是算子法。
5.2.1迭置法
定义5.4：   设新函数在某一变元处的值与诸旧函数的n个值有关，如果n不随新函数的变元组的变化而变化，则称该新函数是由旧函数利用迭置而得的。
例如，设有函数S(x)，a为常数。现构造一元函数Sa(x)，显然Sa(x)在x0处的值与S(x)在Sa-1(x0)，Sa-2(x0)，…，S(x0)，x0等a个值有关，而且a为常量与x0无关，所以Sa(x)可由S(x)利用迭置而得。
1. (m，n)标准迭置
设有一个m元函数f(x1，x2，…，xm  )，m个n元函数g1(x1，x2，…，xn)、g2(x1，x2，…，xn)、…、gm(x1，x2，…，xn)，由f和gi(i=1，2，…，n)构造如下的函数：   h(x1，x2，…，xn)=f(g1(x1，x2，…，xn  )，g2(x1，x2，…，xn  )，…，
gm(x1，x2，…，xn))称为(m，n)标准迭置。称函数h是由m个g对f作(m，n)标准迭置而得的，简记为：   h(x1，x2，…，xn)=f(g1，g2，…，gm)(x1，x2，…，xn)注意，通常的迭置并不满足上述条件，但可以采用本原函数把它们化为(m，n)标准迭置。
例5.5：   利用本原函数把下面的迭置化为(m，n)标准迭置。h(x1，x2，x3，x5，x6)=f(g1(x1，3)，4，g2(x2，x3)，x5，g3(x6，x2)) 解：   h(x1，x2，x3，x5，x6)=f(h1，h2，h3，h4，h5)(x1，x2，x3，x5，x6)
其中：  h1(x1，x2，x3，x5，x6)=g1(I51，S3OI51)(x1，x2，x3，x5，x6)
h2(x1，x2，x3，x5，x6)=S4OI51(x1，x2，x3，x5，x6)
h3(x1，x2，x3，x5，x6)=g2(I52，I53)(x1，x2，x3，x5，x6)
h4(x1，x2，x3，x5，x6)=I54(x1，x2，x3，x5，x6)
h5(x1，x2，x3，x5，x6)=g3(I55，I52)(x1，x2，x3，x5，x6)故函数h(x1，x2，x3，x5，x6)是由函数h1、h2、h3、h4、h5对f作(5，5)标准迭置而得的。
2. 凑合定义法
所谓凑合定义法是指如下构造函数的方法：   h(x1，x2，…，xn)=f1(x1，x2，…，xn)当A1(x1，x2，…，xn)为真时
f2(x1，x2，…，xn)当A2(x1，x2，…，xn)为真时

fk(x1，x2，…，xn)当Ak(x1，x2，…，xn)为真时称新函数h由旧函数f1，f2，…，fk及数论语句A1，A2，…，Ak利用凑合定义而得。注意，数论语句A1，A2，…，Ak互相不可兼，即对任何一个变元组(x1，x2，…，xn)，有且仅有一个条件Ai成立。
可以看出，此种定义方法不利于计算机的符号处理，为此，利用前面定义的一些简单函数，如xNy等函数，把新函数化归为迭置。即h(x1，x2，…，xn)=f1(x1，x2，…，xn)·NctA1(x1，x2，…，xn)
f2(x1，x2，…，xn)·NctA2(x1，x2，…，xn) …
fk(x1，x2，…，xn)·NctAk(x1，x2，…，xn)例5.6：   试用凑合定义法定义函数lm(x，5)，并把它化为迭置。
解：    
lm(x，5)=x当x为5的倍数时
5x当x不为5的倍数时
根据凑合定义法知lm(x，5)=xNN2rs(x，5) 5xNNrs(x，5)
=xNrs(x，5) 5xN2rs(x，5)
=xNrs(x，5) xN2rs(x，5) 4xN2rs(x，5)
=x(Nrs(x，5) N2rs(x，5)) 4xN2rs(x，5)
=x 4xN2rs(x,5)5.2.2算子法
定义5.5：   设新函数在某一变元组处的值与诸旧函数的n个值有关，如果n随新函数的变元组的变化而变化，则称该新函数是由旧函数利用算子而得的。
例如，设有函数S(x)，现构造函数Sy(x)，显然Sy(x)在(x0，y0)处的值与S(x)在Sy0-1(x0)，Sy0-2(x0)，…，S(x0)，x0等y0个值有关，而且y0随着变元组(x0，y0)的变化而变化，所以Sy(x)可由S(x)利用算子而得。
算子的类型很多，下面介绍迭函算子和原始递归式两种算子。
1. 迭函算子
定义5.6：   设有一个二元函数A(x，y)和一个一元函数f(x),利用它们构造如下函数：   g(0)=f(0)
g(1)=A(g(0)，f(1))=A(f(0)，f(1))
g(2)=A(g(1)，f(2))=A(A(f(0)，f(1))，f(2))=A2(f(0)，f(1)，f(2))

g(n 1)=A(g(n)，f(n 1))=An 1(f(0)，f(1)，…，f(n))显然，g(n)的值依赖于函数A(x，y)和函数f(x)。若把A(x，y)固定，而把函数f(x)看作被改造函数，则称g(n)是由旧函数f(x)利用迭函算子而得的。例如，把A分别固定为加法和乘法时可得不同的迭函算子。
（1） 迭加算子：   取A为加法，记为∑x→n。例如：  ∑x→nf(x)=f(0) f(1) … f(n)(2) 迭乘算子：   取A为乘法，记为∏x→n。例如：  ∏x→nf(x)= f(0)×f(1)×…×f(n)2. 原始递归式
递归的概念在前面已经多次提到，如阶乘的函数n!=1                    当n=0时
n(n-1)!    当n≥1时有了此例子，下面来定义原始递归式。
（1） 不含参数的原始递归式：  g(0)=a
g(n 1)=B(n，g(n))其中，a为常数，B(x，y)为已知函数。此式称为不含参数的原始递归式的标准形式。
例如，g(n)=n!可用递归式表示如下：   g(0)=1
g(n 1)=(n 1)×g(n)=B(n，g(n))其中，函数B(x，y)为×(SI21，I22)，它是已知函数。
（2） 含参数的原始递归式:g(u1，u2，…，uk，0)=A(u1，u2，…，uk)
g(u1，u2，…，uk，n 1)=B(u1，u2，…，uk，n，g(u1，u2，…，uk，n))其中，A(u1，u2，…，uk)和B(u1，u2，…，uk，x，y)为已知函数。此式称为含参数的原始递归式的标准形式。
5.2.3原始递归函数1. 原始递归函数的构造方法根据上面介绍的内容，可知构造原始递归函数的方法如下：   
（1） 本原函数为原始递归函数。
（2） 对已建立的原始递归函数利用迭置而得的函数仍为原始递归函数。
（3） 对已建立的原始递归函数利用原始递归式而得的函数仍为原始递归函数。
所以，原始递归函数是由本原函数出发，利用迭置和原始递归式而得的函数。
2. 原始递归函数的构造过程
下面是若干递归函数的例子，以便说明原始递归函数的构造过程，其他函数可依此类推。
（1） S(x)=x 1，为本原函数。
（2） Imn(x1，x2，…，xn，…，xm)=xn，为本原函数。
（3） f(x，y)=x y。
可用原始递归式表示如下：   f(x，0)=x
f(x，y 1)=x y 1=B(x，y，f(x，y))其中，B为SI33，它们为函数的迭置。
（4） f(x，y)=xy。
可用原始递归式表示如下：   f(x，0)=x0=1
f(x，y 1)=xy 1=xy×x=B(x，y，f(x，y))其中，B为×(I33，I31)，它们为函数的迭置。
（5） f(x)=ax。
可用原始递归式表示如下：   f(0)=a0=1
f(x 1)=ax 1=ax×a=B(x，f(x))其中，B为×(I22，SaOI21)，它们为函数的迭置。
（6） f(x)=D(x)。
可用原始递归式表示如下：   f(0)=D(0)=0
f(x 1)=D(x 1)=x=B(x，f(x))其中，B为I21。
（7） max(x，y)。
因为max(x，y)=x (y·-x)，又因为x y和x·-y是原始递归函数，由它们的迭置所得的函数仍为原始递归函数。故max(x，y)为原始递归函数。
5.3典型例题
例5.7：   给出“x为质数”的特征函数。
解：   “x为质数”可理解为2至x-1都不是x的因子。
其特征函数可表示为N2∑t→xNrs(x，t)··-2例5.8：   把下面利用凑合定义法定义的函数化为迭置。f(x)=x当x≤10时
2x当103x当x>20时解：   “x≤10”的特征函数为N2(x·-10)。
“10“x>20”的特征函数为N2(21·-x)。
将上述函数化为迭置：  f(x)=x·NN2(x·-10) 2x·NN2(N2(11·-x)
N2(x·-20)) 3x·NN2(21·-x)
=x·N(x·-10) 2x·N(N2(11·-x)
N2(x·-20)) 3x·N(21·-x)习题
5.1写出下列函数的特征函数。
（1） a大于或等于b。
（2） a为b、c的公倍数。
（3） x异于0且x为平方数。
（4） a为非负数或a为奇数。
（5） 在a、b间的一切x均使得A(x)成立。
（6） 在a、b间有一个x使得A(x)成立。
5.2把下列函数化为标准迭置。
（1） h(x1，x2，x3，x5)=f(g1(x1，x3，3)，a，g2(x2，x3)，x5) （其中a为正整数）
（2） h(x1，x2，x3，x4)=f(x1，3，g1(x2，x3)，g2(x4，2))
5.3用凑合定义法定义函数dv(x，5)，并把它化为迭置。
5.4证明下列函数为原始递归函数。
（1） xy
（2） rs(x，2)
（3） O(x)
（4） min(x，y)
（5） x··-y
（6） ∏x→nf(x)