离散数学基础

tianxiaxueran

[size=一、课程内容
        •数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。
        •集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。
        •代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。
        •图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。
        •讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。
二、数理逻辑发展史
1.        目的
        •了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。
        •通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。
2.        数理逻辑的发展前期
        •前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论
        •初创时期——逻辑代数时期（17世纪末）
•资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。
•人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。
•莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想：
•提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。
•使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。
•布尔(G. Boole, 1815~1864)代数：将有关数**算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。
3.        数理逻辑的奠基时期
        •弗雷格(G. Frege, 1848~1925)：《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。
        •皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统。
        •罗素(Bertrand Russell, 1872~1970)：《数学原理》(与怀特黑合著，1910, 1912, 1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。
        •逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。
        •各种各样的非经典逻辑的发展：路易斯(Lewis, 1883~1964)的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。
4.         集合论的发展
        •看待无穷集合的两种观点：实无穷与潜无穷
        •康托尔(G. Cantor, 1845~1918)：以实无穷的思想为指导，建立了朴素集合论
                •外延原则（集合由它的元素决定）和概括原则（每一性质产生一集合）。
                •可数集和不可数集，确定无穷集合的本质在于集合本身能与其子集一一对应。能与正整数集合对应的集合是可数的，否则是不可数的。证明了有理数集是可数的，使用对角线法证明了实数集合是不可数的。
        •超穷基数和超穷序数
        •朴素集合论的悖论：罗素悖论
        •公理集合论的建立：ZFC系统
6.        第三次数学危机与逻辑主义、直觉主义与形式主义
        •集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。
        •罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。
        •布劳维尔(Brouwer, 1881~1966)的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。
        •希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将各门数学形式化，构成形式系统，并证明其一致性，这是希尔伯特的数学纲领。
7.        数理逻辑的发展初期
        •哥德尔(Godel, 1906~1978)不完全性定理：一个足够强大的形式系统，如果是一致的则不是完全的，即有的判断在其中是不可证的，既不能断定其为假，也不能证明其为真。
        •各种计算模型：哥德尔的递归函数理论，邱吉尔的演算，图灵机模型
        •这些计算模型是计算机科学的理论基础，是计算机的理论模型。

三、预备知识
1.        集合的基本概念
        •集合(set)：集合是数学中最基本的概念之一，不能以更简单的概念来定义(define)，只能给出它的描述(description)。一些对象的整体就称为一个集合，这个整体的每个对象称为该集合的一个元素(member或element)。
•用大写字母A, B, C等表示集合，用小写字母a, b, c等表示集合的元素
•aA表示：a是集合A的元素，或说a属于集合A
•aA表示：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。

        •子集(subset)：说集合A是集合B的子集，记为AB，如果a属于集合A则a也属于集合B。因此A=B当且仅当AB且BA。说集合A是集合B的真子集(proper subset)，如果AB且A不等于B(A  B)。
        •空集(empty set)：约定存在一个没有任何元素的集合，称为空集，记为，有时也用{}来表示。按子集的定义，空集是任何集合的子集(为什么？)。
        •幂集(power set)：集合A的幂集，记为P(A)，是A的所有子集所构成的集合，即：
                •(A) = { B | B  A }
                •例如，A = {0, 1}，则P(A) = { {}, {0}, {1}, {0, 1} }
                •显然，对任意集合A，有 P(A)和A(A)

        •补集(complement set)：集合A的补集，记为A，是那些不属于集合A的元素所构成的集合，即A = {x | xA}。通常来说，是在存在一个全集U的情况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。
        •集合的并(union)：集合A和B的并AB定义为：AB = {x | xA或者xB}，集合的并可推广到多个集合，设A1, A2, …, An都是集合，它们的并定义为：
                A1A2…An = {x | 存在某个i，使得xAi}
        •集合的交(intersection)：集合A和B的并AB定义为：AB = {x | xA而且xB}，集合的交也可推广到多个集合，设A1, A2, …, An都是集合，它们的交定义为：
                A1A2…An = {x | 对所有的i，都有xAi}
        •集合的差(difference)：集合A和B的差AB定义为：AB = {x | xA而且xB}。
2.        关系和函数的基本概念
        •有序对(ordered pair)：设A和B是两个集合，aA, bB是两个元素，a和b的有序对，记为<a, b>，定义为集合{{a}, {a, b}}。
                •设<a1, b1>和<a2, b2>是两个有序对，可以证明<a1, b1> = <a2, b2>当且仅当a1 = a2且b1 = b2。(如何证？)
                •有序对可推广到n个元素，设A1, A2, …, An是集合，a1A1, a2A2, …, anAn是元素，定义有序n元组(ordered n-tuple)<a1, a2, …, an>为<<a1, a2, …, an-1>, an>，注意这是一个归纳(inductive)定义，将有序n元组的定义归结为有序n-1元组的定义。
                •显然有<a1, a2, …, an> = <b1, b2, …, bn>当且仅当a1 = b1且a2 = b2且…且an = bn。

        •集合的笛卡尔积(cartesian product)：两个集合A和B的笛卡尔积AB定义为：
                        AB = {<a, b> | aA且bB}
                •例如，设A = {a, b, c}，B = {1, 2}，则：
AB = {<a, 1>, <a, 2>, <b, 1>, <b, 2>, <c, 1>, <c, 2>}
                •笛卡尔积可推广到多个集合的情况，集合A1, A2, …, An的笛卡尔积定义为：
                        A1A2…An = {<a1, a2, …, an> | a1A1且a2A2且…且anAn}

        •集合之间的关系(relation)：定义n个集合A1, A2, …, An之间的一个n元关系R为集合A1, A2, …, An的笛卡尔积A1A2…An的一个子集。设<a1, a2, …, an>A1A2…An，若<a1, a2, …, an>R，则称a1, a2, …, an间具有关系R，否则称它们不具有关系R。特别地：
                •当A1 = A2 = … = An = A时，称R为A上的n元关系。
                •当n = 2时，有RA1A2，称R为A1与A2间的一个二元关系(binary relation)。这时若<a1, a2>R则简记为a1Ra2，否则（即<a1, a2>R）记为a1Ra2。通常研究得最多的是二元关系，n元关系的许多性质可从二元关系的性质扩充而得到。如果没有特别指明的话，说R是一个关系则是指R是一个二元关系。
                •当n = 1时，这时可认为R是集合A上满足某种性质的子集。
        •关系的一些性质：设R是A上的二元关系：
                •说R是自反的(reflexive)，如果对任意的aA有aRa。
                •说R是反自反的(irreflexive)，如果对任意的aA有aRa。
                •说R是对称的(symmetric)，如果对任意的a, bA有若aRb则bRa。
                • 说R是反对称的(antisymmetric)，如果对任意的a, bA有若aRb且bRa则a = b。
                •说R是传递的(transitive)，如果对任意的a, b, c A有若aRb且bRc则aRc。
                •说R是等价关系(equivalence)，如果R是自反的、对称的和传递的。

        •集合之间的函数(function，或说映射mapping)：定义集合A到B的函数f是A和B的笛卡尔积AB的一个子集，且满足若<x, y>f及<x, z>f则y = z。因此函数是A和B之间的一个特殊的二元关系。通常记集合A到B的函数f为f : AB。
                •函数f : AB的定义域(domain)dom(f )定义为：
                        dom(f ) = {x | 存在某个yB使得<x, y>f }
                •函数f : AB的值域(range)ran(f )定义为：
                        ran(f ) = {y | 存在某个xA使得<x, y>f }
                •若<x, y>f，通常记y为f(x)，并称y为x在函数f下的像(image)，x为y在函数f下的原像。
        •函数也可推广到n元的情形：f : A1A2…AnB，意味着：
                •f是A1A2…AnB的一个子集，且
                •<x1, x2, …, xn, y> f且<x1, x2, …, xn, z> f则y = z。

        •函数的一些性质：设f : AB是集合A到B的函数：
                •说f是全函数(total function)，若dom(f )=A，否则称f是偏函数(partial function)。下面如果没有特别指明的话，都是指全函数。
                •说f是满射(surjection, 或说f maps A onto B)，如果ran(f ) = B，即对任意的yB都有原像。
                •说f是单射(injection，或说f is one-one)，如果有f (x1) = f(x2)则x1 = x2，即对任意的yB，如果它有原像的话，则有唯一的原像。
                •说f是双射(bijection，或说f是一一对应)，如果f既是满射，又是单射，即对任意的yB，都有唯一的原像，同样根据全函数的定义，对于任意xA都有唯一的像。这时可以定义f的逆函数(inverse function)，记为f -1 : BA，f -1(y) = x当且仅当f(x) = y。显然f -1也是双射。

        •集合的基数(cardinal number)或说势：集合A的基数记为|A|，且有：
                •对于有限集合A，令A的基数为A中元素的个数。
                •定义无限集合，不直接定义基数，而是通过定义两个集合之间的等势关系来刻划集合的基数或势，说集合A和集合B是等势的(equipotent)，如果存在一个从A到B的双射。根据双射的性质，可以证明等势是集合上的一个等价关系。
                •称与自然数集等势的集合为可列集(enumerable)，有限集和可列集统称为可数集(countable)。
                •设A和B是有限集合，有|P(A)| = 2|A|，|AB| = |A|  |B|。
3.        小结
        •下面以树的形式给出了以上主要概念之间的关系：
                              集合

       子集          集合的补、并、交、差              有序对

       幂集                                           笛卡尔积

                                                        关系

                      关系的自反、对称、传递性                      函数

                                                              单射、满射、双射
4.        归纳定义和归纳证明
        •一个集合的归纳定义(inductive definition)通常分为三步：
                •归纳基：一些基本的元素属于该集合；
                •归纳步：定义一些规则（或者说操作），从该集合中已有的元素来生成该集合的新的元素；
                •最小化：该集合中的所有元素都是通过基本元素以及所定义的规则生成的，换句话说，该集合是由基本元素及规则所生成的最小的集合。
        •自然数集N的归纳定义：
                [1].        归纳基：0是一个自然数，即0 N。
                [2].        归纳步：若n是自然数，则n的后继也是自然数。记n的后继为succ(n)，即若nN，则succ(n)N。为方便起见，后面也记n的后继为n+1。
                [3].        最小化：所有的自然都通过步骤[1]和[2]得到，或者说自然数集是通过步骤[1]和[2]得到的最小集合。

        •这种定义方式可推广到对其他一些概念的定义，例如上述多个集合的并、交、笛卡尔积以及多个元素的有序n元组都可通过递归的方式定义。例如，对于多个集合的并可定义为：
                •归纳基：A1A2 = {x | xA1或者xA2}
                •归纳步：A1A2…An = (A1A2…An-1)  An
                •这里不需要最小化，因为这里不是定义集合。

        •数学归纳法：关于自然数的许多性质都可通过数学归纳法来证明，对于性质R，如果它对0成立，而且如果对于n成立的话，能够得到它对于n+1也成立，那么性质R对所有的自然数成立。这种证明方法的正确性本身可通过自然数的归纳定义来得到证明：
                •定义集合S = {nN | 性质R对n成立}
                •归纳基：根据上面的定义有0S
                •归纳步：根据上面的定义有如果nS，则n+1S，所以S是满足上面自然数集的归纳定义中的1、2点的一个集合，而自然数集N是满足这两点的最小集合，所以有N S，而显然有SN，所以S = N。
        •数学归纳法举例：使用数学归纳法证明1 + 2 + … + n = (n * (n+1))/2
                •归纳基：当n = 0时显然成立。
                •归纳步：如果对于n成立，则有1 + 2 + … + n = (n * (n+1))/2（这称为归纳假设），现在要证对于n+1也成立。显然有：
1 + 2 + … + n + (n + 1) = (n * (n+1))/2 + (n+1)         // 根据归纳假设
= (n * (n+1) + 2 * (n+1))/2 = ((n+1) * ((n+1) + 1))/2
                因此要证的公式对于n+1成立，所以对于所有的自然数成立。
        •显然在数学归纳法中，对于归纳基改为R对于自然数k成立，归纳步不变的话，则可证明R对于所有大于k的自然数都成立。
        •在数学归纳法中，也可将归纳步改为如果R对于所有小于n的自然数成立，则推出R对于n也成立，即归纳步是假设对于所有小于n的自然数性质R成立来导出性质R对于自然数n成立。这种形式的数学归纳法通常称为第二数学归纳法。
5.        形式系统
        •形式系统的定义：一个形式系统S由下列4个集合构成：
                •一个非空集合S，称为形式系统S的字母表或说符号(Symbol)表；
                •一个由S中字母的有限序列（字符串）所构成的集合FS，称为形式系统S的公式(Formula)集；
                •从FS中选取一个子集AS，称为形式系统S的公理(Axiom)集；
                •FS上有一个部分函数集RS = {Rn | Rn : FS  FS … FS FS , n = 1, 2, …}，称为形式系统S的规则(Rule)集，其中Rn : FS  FS … FS FS是n元的部分函数，我们称其为n元规则。
        •形式系统中的定理(Theorem)：
                •归纳基：t  AS 是形式系统S中的定理。
                • 归纳步：t1, t2, …, tn是形式系统S中的定理，而Rn是S中的规则，那么Rn(t1, t2, …, tn)也是形式系统S中的定理。
        •对于形式系统中的规则Rn : FS  FS … FS FS，通常表示成下面的形式：
t1, t2, …, tn
Rn(t1, t2, …, tn)
        •形式系统具有两个特征：
                •形式化实际上是一个可机械实现的过程，在它里面，符号、规则和演算等被表示得严密、精确。在形式系统S中，只能使用字母表S中的符号，只承认公式集FS中的符号串的合理性，只能由公理集，根据规则推出有意义的东西来。
                •形式系统一旦完成，就成了符号串及根据规则进行的符号串的改写，系统与一切实际意义就毫不相干，或者说已经通过这种符号，从实际问题中抽象出了我们所需要研究的内容。在形式系统内部，所能认识的只能是符号串及其改写，只能在形式系统外对这种符号串及规则赋予意义。

        •对象语言(Object language)与元语言(Meta language)：
•数理逻辑所研究的是“数学推理”，而使用的方法也是数学推理，所以有必要区分这两个层次的推理。
•把作为研究对象的“推理”形式化，使用形式语言来表示作为研究对象的“推理”的前提、结论和规则等，这种形式语言是我们所研究的对象语言。
•另一方面，关于形式系统的性质、规律的表达和作为研究方面的推理方式使用另一种语言来表达，这个语言称为研究的元语言，通常使用半数学化的自然语言。
        •形式语言的语法(Syntax)与语义(Semantic)：
•形式语言的语法是构成形式系统的公式集、公理集和规则集的法则。
•形式语言的语义是关于形式系统的解释和意思。
•形式语言本身没有含义，但我们在构造它们时是假想它们能代表某种意义的，特别的当我们在选择形式系统的公理时，总是选择所研究的问题域中那些最为明显或最容易公认为正确的性质。
6.        习题
1.        令集合A = { n | n  10且n 是奇数}，B = {n | n  10且n是素数}，请回答下列问题：
        a)        请用列元素的方法列出集合A和集合B，请问集合B是否是集合A的子集？
        b)        请计算AB、AB、AB、AB以及P(A)(即A的幂集)。
2.        设关系R = {<a, b> | a和b是互质的自然数}，请问R是自反的吗？对称的吗？传递的吗？为什么？
3.        设f : AB是函数，R是A上的如下二元关系：R = {<a, b> | a, bA, f (a) = f (b) }，        证明R是A上的一个等价关系。
4.        使用数学归纳法证明：12 + 22 + 32 + … + n2 = (n * (n + 1) * (2n + 1)) / 6
5.        设有函数f : NN  N，f(n) = <n, n+1>，请问f是不是单射、满射或双射？
*6.        设R1和R2都是A上的等价关系，请问R1R2和R1R2是否还是A上的等价关系？如果是请证明，否则请举一反例。
*7.        设R是集合A上的等价关系，aA，可定义：
        a)        [a] = {bA | aRb }，称[a]为a关于R的等价类；
        b)        A/R = {[a] | aA}，称A关于R的商集。
        设函数f : AA/R定义为对任意aA有f(a) = [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？
5]