第一讲 引言
1、课程内容
数理逻辑：是计算机科学的基础，应熟练学会将现实日常的条件化成逻辑公式，并能做适合的推理，这对程序设计等课程是极有用处的。
集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都非常有用处。熟练学会有关集合、函数、关系等基本定义。
代数结构：对于抽象数据种类、形式语义的研究非常有用处。培养数学思维，将以前学过的常识系统化、形式化和抽象化。熟练学会有关代数系统的基本定义，与群、环、域等代数结构的入门知识。
图论：对于解决很多实质问题非常有用处，对于学习数据结构、编译原理课程也非常有帮助。需要学会有关图、树的基本定义，与怎么样将图论用于实质问题的解决，并培养其用数学工具打造模型的思维方法。
讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和困难程度，但讲课内容不限于书中的内容和困难程度。
2、数理逻辑进步史
1.目的
知道有关的背景，加深对计算机学科的全方位知道，尤其是理论方面的认知，而不限于将计算机看成是一门技术或工程性的学科。
通过要紧的历史事件，知道计算机科学中的一些基本思维方法和一些基本问题。
2.数理逻辑的进步前期
前史时期古典形式逻辑时期：亚里斯多德的直言三段论理论
初创时期逻辑代数时期（17世纪末）
资本主义生产力大进步，自然科学获得了长足的进步，数学在认识自然、进步技术方面起到了相当要紧有哪些用途。
大家期望用数学的办法来研究思维，把思维过程转换为数学的计算。
莱布尼兹健全三段论，提出了打造数理逻辑或者说理性演算的思想：
提出将推理的正确性化归于计算，这种演算能使大家的推理不依靠于对推理过程中的命题的意思内容的考虑，将推理的规则变为演算的规则。
用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从非常大程度上取决与符号的组合规律，而与其含义无关。
布尔代数：或有关数学运算的研究的代数系统推广到逻辑范围，布尔代数既是一种代数系统，也是一种逻辑演算。
3.数理逻辑的奠基时期
弗雷格：《定义语言一种按算术的公式语言构成的纯思维公式语言》的出版标志着数理逻辑的基础部分命题演算和谓词演算的正式打造。
皮亚诺：《用一种新的办法陈述的算术原理》提出了自然数算术的一个公理系统。
罗素：《数学原理》从命题演算和谓词演算开始，然后通过一元和二元命题函项概念了类和关系的定义，打造了抽象的类演算和关系演算。由此出发，在种类论的基础上用连续概念和证明的方法引出了数学（主如果算术）中的主要定义和定理。
逻辑演算的进步：甘岑的自然推理系统，逻辑演算的元理论：公理的独立性、一致性、完全性等。
各种各样的非经典逻辑的进步：路易斯的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。
4.集合论的进步
看待无穷集合的两种看法：实无穷与潜无穷
康托尔：以实无穷的思想为指导，打造了朴素集合论
外延原则（集合由它的元素决定）和概括原则（每一性质产生一集合）。
可数集和不可数集，确定无穷集合的本质在于集合本身能与其子集一一对应。能与正整数集合对应的集合是可数的，不然是不可数的。证明了有理数集是可数的，用对角线法证明了实数集合是不可数的。
超穷基数和超穷序数
朴素集合论的悖论：罗素悖论
公理集合论的打造：ZFC系统
6.第三次数学危机与逻辑主义、直觉主义与形式主义
集合论的悖论使得大家感觉数学产生了第三次危机，提出了数学的基础到底是什么如此的问题。
罗素等的逻辑主义：数学的基础是逻辑，主张所有数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑种类论。
布劳维尔的直觉主义：数学是心灵的架构，只承认同架构的数学，强调架构的能行性，与计算机科学有要紧的联系。坚持潜无穷，强调排中律不可以用于无穷集合。海丁的直觉主义逻辑。
希尔伯特的形式主义：公理化办法与形式化办法，元数学和证明论，倡导将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按肯定法则排列的一堆公式。为了消除悖论，要数学打造在公理化基础上，将各门数学形式化，构成形式系统，并证明其一致性，这是希尔伯特的数学纲领。
7.数理逻辑的进步初期
哥德尔不完全性定理：一个足够强大的形式系统，若是一致的则不是完全的，即有些判断在其中是不可证的，既不可以判定其为假，也不可以证明其为真。
各种计算模型：哥德尔的递归函数理论，邱吉尔的l演算，图灵机模型
这类计算模型是计算机科学的理论基础，是计算机的理论模型。
3、预备常识
1.集合的基本定义
集合：集合是数学中最基本的定义之一，不可以以更简单的定义来概念，只能给出它的描述。一些对象的整体就称为一个集合，这个整体的每一个对象称为该集合的一个元素。
用大写字母A, B, C等表示集合，用小写字母a, b, c等表示集合的元素
aA表示：a是集合A的元素，或说a是集合A
aA表示：a不是集合A的元素，或说a不是集合A
集合中的元素是无序的，不重复的。一般用两种办法来给出一个集合：
列元素法：列出某集合的所有元素，如：
A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}表示所有小于10的自然数所构成的集合
B = {a, b, , z} 表示所有小写英文字母所构成的集合
性质概括法：用某个性质来概括集合中的元素，如：
A = { n | n 是小于10的自然数}
C = { n | n 是质数} 表示所有质数所构成的集合
集合由它的元素所决定，换句话说，两个集合A和B相等，记为A = B，假如A和B具备相同的元素，即a是集合A当且仅当a是集合B。
子集：说集合A是集合B的子集，记为AB，假如a是集合A则a也是集合B。因此A=B当且仅当AB且BA。说集合A是集合B的真子集，假如AB且A不等于B。
空集：约定存在一个没任何元素的集合，称为空集，记为f，有时也用{}来表示。按子集的概念，空集是任何集合的子集。
幂集：集合A的幂集，记为P，是A的所有子集所构成的集合，即：
P = { B | BA }
比如，A = {0, 1}，则P = { {}, {0}, {1}, {0, 1} }
显然，对任意集合A，有f P和AP
补集：集合A的补集，记为A，是那些不是集合A的元素所构成的集合，即A = {x | xA}。一般来讲，是在存在一个全集U的状况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。
集合的并：集合A和B的并AB概念为：AB = {x | xA或者xB}，集合的并可推广到多个集合，设A1, A2, , An都是集合，它们的并概念为：
A1A2An = {x | 存在某个i，使得xAi}
集合的交：集合A和B的并AB概念为：AB = {x | xA而且xB}，集合的交也可推广到多个集合，设A1, A2, , An都是集合，它们的交概念为：
A1A2An = {x | 对所有些i，都有xAi}
集合的差：集合A和B的差A-B概念为：A-B = {x | xA而且xB}。
2.关系和函数的基本定义
有序对：设A和B是两个集合，aA, bB是两个元素，a和b的有序对，记为a, b，概念为集合{{a}, {a, b}}。
设a1, b1和a2, b2是两个有序对，可以证明a1, b1 = a2, b2当且仅当a1 = a2且b1 = b2。
有序对可推广到n个元素，设A1, A2, , An是集合，a1A1, a2A2, , anAn是元素，概念有序n元组a1, a2, , an为a1, a2, , an-1, an，注意这是一个总结概念，或有序n元组的概念归结为有序n-1元组的概念。
显然有a1, a2, , an = b1, b2, , bn当且仅当a1 = b1且a2 = b2且且an = bn。
集合的笛卡尔积：两个集合A和B的笛卡尔积AB概念为：
AB = {a, b | aA且bB}
比如，设A = {a, b, c}，B = {1, 2}，则：
AB = {a, 1, a, 2, b, 1, b, 2, c, 1, c, 2}
笛卡尔积可推广到多个集合的状况，集合A1, A2, , An的笛卡尔积概念为：
A1A2An = {a1, a2, , an | a1A1且a2A2且且anAn}
集合之间的关系：概念n个集合A1, A2, , An之间的一个n元关系R为集合A1, A2, , An的笛卡尔积A1A2An的一个子集。设a1, a2, , anA1A2An，若a1, a2, , anR，则称a1, a2, , an间具备关系R，不然称它们不具备关系R。特别地：
当A1 = A2 == An = A时，称R为A上的n元关系。
当n = 2时，有RA1A2，称R为A1与A2间的一个二元关系。这个时候若a1, a2R则简记为a1Ra2，不然（即a1, a2R）记为a1Ra2。一般研究得最多的是二元关系，n元关系的很多性质可从二元关系的性质扩充而得到。假如没特别指明的话，说R是一个关系则是指R是一个二元关系。
当n = 1时，这个时候可觉得R是集合A上满足某种性质的子集。
关系的一些性质：设R是A上的二元关系：
说R是自反的，假如对任意的aA有aRa。
说R是反自反的，假如对任意的aA有aRa。
说R是对称的，假如对任意的a, bA有若aRb则bRa。
说R是反对称的，假如对任意的a, bA有若aRb且bRa则a = b。
说R是传递的，假如对任意的a, b, c A有若aRb且bRc则aRc。
说R是等价关系，假如R是自反的、对称的和传递的。
集合之间的函数：概念集合A到B的函数f是A和B的笛卡尔积AB的一个子集，且满足若x, yf及x, zf则y = z。因此函数是A和B之间的一个特殊的二元关系。一般记集合A到B的函数f为f : AB。
函数f : AB的概念域dom概念为：
dom = {x | 存在某个yB使得x, yf }
函数f : AB的值域ran概念为：
ran = {y | 存在某个xA使得x, yf }
若x, yf，一般记y为f，并称y为x在函数f下的像，x为y在函数f下的原像。
函数也可推广到n元的情形：f : A1A2AnB，意味着：
f是A1A2AnB的一个子集，且
x1, x2, , xn, y f且x1, x2, , xn, z f则y = z。
函数的一些性质：设f : AB是集合A到B的函数：
说f是全函数，若dom=A，不然称f是偏函数。下面假如没特别指明的话，都是指全函数。
说f是满射，假如ran = B，即对任意的yB都有原像。
说f是单射，假如有f= f则x1 = x2，即对任意的yB，假如它有原像的话，则有唯一的原像。
说f是双射，假如f既是满射，又是单射，即对任意的yB，都有唯一的原像，同样依据全函数的概念，对于任意xA都有唯一的像。这个时候可以概念f的逆函数，记为f -1 : BA，f -1 = x当且仅当f = y。显然f -1也是双射。
集合的基数或说势：集合A的基数记为|A|，且有：
对于有限集合A，令A的基数为A中元素的个数。
概念无限集合，不直接概念基数，而是通过概念两个集合之间的等势关系来刻划集合的基数或势，说集合A和集合B是等势的，假如存在一个从A到B的双射。依据双射的性质，可以证明等势是集合上的一个等价关系。
称与自然数集等势的集合为可列集，有限集和可列集统称为可数集。
设A和B是有限集合，有|P| = 2|A|，|AB| = |A||B|。
.总结概念和总结证明
一个集合的总结概念一般分为三步：
总结基：一些基本的元素是该集合；
总结步：概念一些规则（或者说操作），从该集合中已有些元素来生成该集合的新的元素；
最小化：该集合中的所有元素都是通过基本元素与所概念的规则生成的，换句话说，该集合是由基本元素及规则所生成的最小的集合。
自然数集N的总结概念：
[1]. 总结基：0是一个自然数，即0 N。
[2]. 总结步：若n是自然数，则n的后继也是自然数。记n的后继为succ，即若nN，则succN。为便捷起见，后面也记n的后继为n+1。
[3]. 最小化：所有些自然都通过步骤[1]和[2]得到，或者说自然数集是通过步骤[1]和[2]得到的最小集合。
这种概念方法可推广到对其他一些定义的概念，比如上述多个集合的并、交、笛卡尔积与多个元素的有序n元组都可通过递归的方法概念。比如，对于多个集合的并可概念为：
总结基：A1A2 = {x | xA1或者xA2}
总结步：A1A2An = An
这里无需最小化，由于这里不是概念集合。
数学总结法：关于自然数的很多性质都可通过数学总结法来证明，对于性质R，假如它对0成立，而且假如对于n成立的话，可以得到它对于n+1也成立，那样性质R对所有些自然数成立。这种证明办法的正确性本身可通过自然数的总结概念来得到证明：
概念集合S = {nN | 性质R对n成立}
总结基：依据上面的概念有0S
总结步：依据上面的概念有假如nS，则n+1S，所以S是满足上面自然数集的总结概念中的1、2点的一个集合，而自然数集N是满足这两点的最小集合，所以有N S，而显然有SN，所以S = N。
数学总结法举例：用数学总结法证明1 + 2 ++ n = )/2
总结基：当n = 0时显然成立。
总结步：假如对于n成立，则有1 + 2 ++ n = )/2（这称为总结假设），目前要证对于n+1也成立。显然有：
1 + 2 ++ n += )/2 +// 依据总结假设
=+ 2 * )/2 =*+ 1))/2
因此要证的公式对于n+1成立，所以对于所有些自然数成立。
显然在数学总结法中，对于总结基改为R对于自然数k成立，总结步不变的话，则可证明R对于所有大于k的自然数都成立。
在数学总结法中，也可将总结步改为假如R对于所有小于n的自然数成立，则推出R对于n也成立，即总结步是假设对于所有小于n的自然数性质R成立来导出性质R对于自然数n成立。这种形式的数学总结法一般称为第二数学总结法。
5.形式系统
形式系统的概念：一个形式系统S由下列4个集合构成：
一个非空集合SS，称为形式系统S的字母表或说符号表；
一个由SS中字母的有限序列（字符串）所构成的集合FS，称为形式系统S的公式集；
从FS中选取一个子集AS，称为形式系统S的公理集；
FS上有一个部分函数集RS = {Rn | Rn : FSFSFS FS , n = 1, 2, }，称为形式系统S的规则集，其中Rn : FSFSFS FS是n元的部分函数，大家称其为n元规则。
形式系统中的定理：
总结基：tAS 是形式系统S中的定理。
总结步：t1, t2, , tn是形式系统S中的定理，而Rn是S中的规则，那样Rn也是形式系统S中的定理。
对于形式系统中的规则Rn : FSFSFS FS，一般表示成下面的形式：
t1, t2, , tn
Rn
形式系统具备两个特点：
形式化事实上是一个可机械达成的过程，在它里面，符号、规则和演算等被表示得严密、精准。在形式系统S中，只能用字母表SS中的符号，只承认公式集FS中的符号串的合理性，只能由公理集，依据规则推出有意义的东西来。
形式系统一旦完成，就成了符号串及依据规则进行的符号串的改写，系统与所有实质意义就毫不相干，或者说已经通过这种符号，从实质问题中抽象出了大家所需要研究的内容。在形式系统内部，所能认识的只能是符号串及其改写，只能在形式系统外对这种符号串及规则赋予意义。
对象语言与元语言：
数理逻辑所研究的是数学推理，而用的办法也是数学推理，所以有必要区别这两个层次的推理。
把作为研究对象的推理形式化，用形式语言来表示作为研究对象的推理的首要条件、结论和规则等，这种形式语言是大家所研究的对象语言。
其次，关于形式系统的性质、规律的表达和作为研究方面的推理方法用另一种语言来表达，这个语言称为研究的元语言，一般用半数学化的自然语言。
形式语言的语法与语义：
形式语言的语法是构成形式系统的公式集、公理集和规则集的法则。
形式语言的语义是关于形式系统的讲解和意思。
形式语言本身没含义，但大家在架构它们时是假想它们能代表某种意义的，特别的当大家在选择形式系统的公理时，一直选择所研究的问题域中那些最为明显或最易公觉得正确的性质。
6.习题
1.令集合A = { n | n10且n 是奇数}，B = {n | n10且n是素数}，请回答下列问题：
a)请用列元素的办法列出集合A和集合B，请问集合B是不是是集合A的子集？
b)请计算AB、AB、A-B、AB与P。
2.设关系R = {a, b | a和b是互质的自然数}，请问R是自反的吗？对称的吗？传递的吗？为何？
3.设f : AB是函数，R是A上的如下二元关系：R = {a, b | a, bA, f= f}，证明R是A上的一个等价关系。
4.用数学总结法证明：
12 + 22 + 32 ++ n2 =* ) / 6
5.设有函数f : NNN，f = n, n+1，请问f是否单射、满射或双射？
*6.设R1和R2都是A上的等价关系，请问R1R2和R1R2是不是还是A上的等价关系？若是请证明，不然请举一反例。
*7.设R是集合A上的等价关系，aA，可概念：
a)[a] = {bA | aRb }，称[a]为a关于R的等价类；
b)A/R = {[a] | aA}，称A关于R的商集。
设函数f : AA/R概念为对任意aA有f = [a]，请问R满足什么样的条件时f是单射？
*8请给出x, y, z的集合方法的概念。若概念：[x, y, z] = {{x}, {x, y}, {x, y, z}}，则假如有[x1, y1, z1] = [x2, y2, z2]是不是意味着有x1 = x2且y1 = y2且z1 = z2？
3.命题逻辑公式
【概念1.1】命题逻辑公式由以下子句总结概念：
[1]. 总结基：命题常量或命题变量是命题逻辑公式，称为命题逻辑公式的原子项。
[2]. 总结步：假如A, B是逻辑公式，则、、、和也是命题逻辑公式。
[3]. 最小化：所有些命题逻辑公式都通过1和2得到。
在这里大家隐含地用的字母表是大小写的英文字母、命题联结符和园括号。英文字母还可带下标。其它的符号都不是大家的符号表，即在命题逻辑公式中不可以出现这类符号。后面大家将命题逻辑公式简称为命题公式，或在没二义的状况下进一步简称为公式。
【例子1.1】))是命题公式，它通过以下步骤生成：
1.p是公式；// 依据概念1.1的[1]
2.q是公式；// 依据概念1.1的[1]
3.是公式；// 依据概念1.1的[2]
4.是公式；// 依据概念1.1的[2]
5.r是公式；// 依据概念1.1的[1]
6.是公式；// 依据概念1.1的[2]
7.)是公式；// 依据概念1.1的[2]，与4, 6
8.))是公式。// 依据概念1.1的[2]，与3, 7
【定理1.2】设R是某个性质，假如有：
[1]. 对于所有些原子项p，都满足性质R；
[2]. 假如对任意的公式A和B都满足性质R，就有、、、和也满足性质R。
那样，所有些公式A就都满足性质R。□
该定理的证明类似数学总结法的证明，比较容易依据概念1.1得到。
【概念1.3】命题公式A的复杂程度deg概念为：
[1]. 假如A是原子项，则deg = 0；
[2]. deg = deg + 1;
[3]. deg = max, deg) + 1，其中*代表、、、之一。
此概念等价于教程p11的概念1.7。只是大家在这里给出的是递归概念。用总结法，大家可证明下面定理：
【定理1.4】deg小于等于命题公式A中的命题联结符号的数目。
【证明】依据命题公式A的结构进行总结证明：
1. 总结基：假如A是原子项，则依据概念1.3有deg = 0，显然定理成立。
2. 总结步：假设定理对于命题公式A和B成立（总结假设），记命题公式A中的命题联结符号数为Sym，即有degSym和degSym。那样因为deg = deg + 1，而Sym = Sym + 1，所以定理对于A也成立。同样因为deg = max, deg) + 1，而Sym = Sym + Sym + 1，因而有deg Sym，从而定理对所有些命题公式都成立。
【定理1.5】任意命题逻辑公式A中出现相等数目的左右园括号，事实上，左右园括号的个数都等于A中的命题联结符号数。
【定理1.6】任意命题逻辑公式A具备下列6种形式之一，且只具备其中一种形式：
[1]. A为原子项；[2]. [3].
[4]. [5]. [6].
【定理1.6】的确切含义包含以下几个方面：
1. 任意命题公式势必具备上述6中形式之一；
2. 这6中形式都互不相同；
3. 假如与相同，则必有A与A1相同；
4. 假如与相同，则必有A与A1相同，且B与B1相同。
依据定理1.5和定理1.6，大家不难了解例子1.1是怎么样得到该其中命题公式的语法剖析树的。事实上每一个命题公式的最左侧都是左园括号，假如从第二个符号不是左园括号，那样这个公式只有一个命题联结符。不然找与第二个左园括号配对的右园括号，从而将命题公式划分为如此的形式： * )，假如原来的命题公式为根的话，那样左右两边的两个命题公式分别为它的左右子树了，而且对这两个公式可作类似的剖析，最后到原子项。
在后面，为了书写便捷起见，大家省略最外边的括号，并规定每个命题联结符的优先级别为大于，大于，大于，大于，从而可省略命题公式中一些非必须的园括号，比如例子1.1中的公式可写为：pqpqr。不过在后面大家书写公式的原则是尽可能方便，但又能让读者容易理解。而有关命题公式的性质的讨论，则只针对可由上面概念1.1所能生成的公式形式。
上面讨论的命题公式的语法结构，下面讨论命题公式的赋值。
【概念1.7】 对命题公式的一次真值赋值t是从所有命题变量所组成的集合到集合{0, 1}的函数。事实上，对于某个命题公式A来讲，大家只关心t在A中的命题变量上的值。这里大家假定存在一个所有命题变量所组成的集合U，或者说大家所有命题公式中的变量都取之于集合U，大家记命题公式A中的所有命题变量所组成的集合为Var。设有一个真值赋值t : U{0, 1}，而对于命题公式A的真值赋值来讲，大家只关心t在Var上的值。
【例子1.3】对于命题公式A = ))，有：
Var = {p, q, r}
这里可以假定U = Var，真值赋值就是一个函数t : {p, q, r}{0, 1}，比如可令：
t = 0, t = 1, t = 0
【概念1.8】命题公式A在真值赋值t : U{0, 1}下的真值t递归概念如下：
[1].假如命题公式A是一个命题常量p，则假如p为真，t = 1，不然t = 0；
[2].假如命题公式A是一个命题变量p，则t = t
[3].若t = 0则t = 1，不然t = 0。
[4].若t = t = 1，则t = 1，不然t = 0。
[5].若t = t = 0，则t = 0，不然t = 1。
[6].若t = 0或者t = 1，则t = 1，不然t = 0。
[7].若t = t，则t = 1，不然t = 0。
【例子1.3，续】对于命题公式A = ))，及真值赋值函数t：
t = 0, t = 1, t = 0
有：
1.t = 0, t = 1;
2.t = 1;// 依据概念1.8的[5]
4.t = 1;// 依据概念1.8的[3]
