《数理逻辑发展教案高等教育统计学_高等教育-大学课件.pdf》由会员分享，可在线阅读，更多相关《数理逻辑发展教案高等教育统计学_高等教育-大学课件.pdf（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一讲 引言 一、课程内容 数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题
2、的解决，并培养其使用数学工具建立模型的思维方式。讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。二、数理逻辑发展史 1.目的 了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。2.数理逻辑的发展前期 前史时期古典形式逻辑时期：亚里斯多德的直言三段论理论 初创时期逻辑代数时期（17 世纪末）资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相
3、当重要的作用。人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。莱布尼兹(Leibniz,16461716)完善三段论，提出了建立数理逻辑或者说理性演算的思想：提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。布尔(G.Boole,18151864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。3.数理逻辑的奠基时期 弗雷格(G.F
4、rege,18481925)：概念语言一种按算术的公式语言构成的纯思维公式语言(1879)的出版标志着数理逻辑的基础部分命题演算和谓词演算的正式建立。皮亚诺(Giuseppe Peano,18581932)：用一种新的方法陈述的算术原理(1889)提出了自然数算术的一个公理系统。罗素(Bertrand Russell,18721970)：数学原理(与怀特黑合着，1910,1912,1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引推理这对程序设计等课程是极有用处的集合论数学的基础对
5、于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数出了数学（主要是算术）中的主要概念和定理。逻辑
6、演算的发展：甘岑(G.Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。各种各样的非经典逻辑的发展：路易斯(Lewis,18831964)的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。4.集合论的发展 看待无穷集合的两种观点：实无穷与潜无穷 康托尔(G.Cantor,18451918)：以实无穷的思想为指导，建立了朴素集合论 外延原则（集合由它的元素决定）和概括原则（每一性质产生一集合）。可数集和不可数集，确定无穷集合的本质在于集合本身能与其子集一一对应。能与正整数集合对应的集合是可数
7、的，否则是不可数的。证明了有理数集是可数的，使用对角线法证明了实数集合是不可数的。超穷基数和超穷序数 朴素集合论的悖论：罗素悖论 公理集合论的建立：ZFC 系统 6.第三次数学危机与逻辑主义、直觉主义与形式主义 集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，数学原理一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。布劳维尔(Brouwer,18811966)的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无推理这
8、对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数
9、穷集合。海丁(Heyting)的直觉主义逻辑。希尔伯特(D.Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将各门数学形式化，构成形式系统，并证明其一致性，这是希尔伯特的数学纲领。7.数理逻辑的发展初期 哥德尔(Godel,19061978)不完全性定理：一个足够强大的形式系统，如果是一致的则不是完全的，即有的判断在其中是不可证的，既不能断定其为假，也不能证明其为真。各种计算模型：哥德尔的递归函数理论，邱吉尔的演算
10、，图灵机模型 这些计算模型是计算机科学的理论基础，是计算机的理论模型。推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程
11、性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数三、预备知识 1.集合的基本概念 集合(set)：集合是数学中最基本的概念之一，不能以更简单的概念来定义(define)，只能给出它的描述(description)。一些对象的整体就称为一个集合，这个整体的每个对象称为该集合的一个元素(member或element)。用大写字母 A,B,C 等表示集合，用小写字母a,b,c等表示集合的元素 aA 表示：a是集合 A 的元素，或说a属于集合 A aA 表示：a不是集合 A 的元素，或说a不属于集合 A 集合中的元素是无序的，不重复的。通常使用两种方法来给出一个集合：列元素
12、法：列出某集合的所有元素，如：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 的子集，记为 AB，如果a属于集合 A 则a也属于集合 B。因此 A=B 当且仅当 AB 且 BA。说集合 A
13、是集合 B 的真子集(proper subset)，如果 AB 且 A 不等于 B(A B)。空集(empty set)：约定存在一个没有任何元素的集合，称为空集，记为，有时也用来表示。按子集的定义，空集是任何集合的子集(为什么)。推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模
14、型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 幂集(power set)：集合 A 的幂集，记为 P(A)，是 A 的所有子集所构成的集合，即：P(A)=B|B A 例如，A=0,1，则 P(A)=,0,1,0,1 显然，对任意集合 A，有 P(A)和 AP(A)补集(complement set)：集合 A 的补集，记为 A，是那些不属于集合 A 的元素所构成的集合，即 A=x|xA。通常来说，是在存
15、在一个全集 U 的情况下讨论集合的补集。全集U 是所讨论的问题域中所有元素所构成的集合。集合的并(union)：集合 A 和 B 的并 AB 定义为：AB=x|xA 或者xB，集合的并可推广到多个集合，设 A1,A2,An都是集合，它们的并定义为：A1A2An=x|存在某个i，使得 xAi 集合的交(intersection)：集合 A 和 B 的并 AB 定义为：AB=x|xA 而且xB，集合的交也可推广到多个集合，设 A1,A2,An都是集合，它们的交定义为：A1A2An=x|对所有的i，都有 xAi 集合的差(difference)：集合 A 和 B 的差 AB 定义为：AB=x|xA
16、而且xB。2.关系和函数的基本概念 有序对(ordered pair)：设 A 和 B 是两个集合，aA,bB 是两个元素，a和b的有序对，记为，定义为集合a,a,b。设 和是两个有序对，可以证明=当且仅当a1=a2且b1=b2。(如何证)有序对可推广到n个元素，设 A1,A2,An是集合，a1A1,a2A2,anAn是元素，定义有序n元组(ordered n-tuple)为,an，注意这是一个归纳(inductive)定义，将有序n元组的定义归结为有序n-1 元组的定义。推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有
17、用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 显然有 =当且仅当a1=b1且a2=b2且且an=bn。集合的笛卡尔积(cartesian product)：两个
18、集合 A 和 B 的笛卡尔积 AB 定义为：AB=|aA 且bB 例如，设 A=a,b,c，B=1,2，则：AB=,笛卡尔积可推广到多个集合的情况，集合 A1,A2,An的笛卡尔积定义为：A1A2An=|a1A1且a2A2且且anAn 集合之间的关系(relation)：定义n个集合 A1,A2,An之间的一个n元关系 R 为集合 A1,A2,An的笛卡尔积 A1A2An的一个子集。设A1A2An，若R，则称a1,a2,an间具有关系 R，否则称它们不具有关系 R。特别地：当 A1=A2=An=A 时，称 R 为 A 上的n元关系。当n=2 时，有 RA1A2，称 R 为 A1与 A2间的一个
19、二元关系(binary relation)。这时若R 则简记为a1Ra2，否则（即R）记为a1Ra2。通常研究得最多的是二元关系，n元关系的许多性质可从二元关系的性质扩充而得到。如果没有特别指明的话，说 R 是一个关系则是指 R 是一个二元关系。当n=1 时，这时可认为 R 是集合 A 上满足某种性质的子集。关系的一些性质：设 R 是 A 上的二元关系：说 R 是自反的(reflexive)，如果对任意的aA 有aRa。说 R 是反自反的(irreflexive)，如果对任意的aA 有aRa。说 R 是对称的(symmetric)，如果对任意的a,bA 有若aRb则bRa。说 R 是反对称的(
20、antisymmetric)，如果对任意的a,bA 有若aRb且bRa则a=推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术
21、或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数b。说 R 是传递的(transitive)，如果对任意的a,b,c A 有若aRb且bRc则aRc。说 R 是等价关系(equivalence)，如果 R 是自反的、对称的和传递的。集合之间的函数(function，或说映射mapping)：定义集合 A 到 B 的函数f是 A 和 B的笛卡尔积 AB 的一个子集，且满足若f及f则y=z。因此函数是 A 和 B 之间的一个特殊的二元关系。通常记集合 A 到 B 的函数f为f:AB。函数f:AB 的定义域(domain)dom(f)定义为：dom(f)=x|存在某
22、个yB 使得f 函数f:AB 的值域(range)ran(f)定义为：ran(f)=y|存在某个xA 使得f 若 f，通常记y为f(x)，并称y为x在函数f下的像(image)，x为y在函数f下的原像。函数也可推广到n元的情形：f:A1A2AnB，意味着：f是 A1A2AnB 的一个子集，且 f且 f则y=z。函数的一些性质：设f:AB 是集合 A 到 B 的函数：说f是全函数(total function)，若 dom(f)=A，否则称f是偏函数(partial function)。下面如果没有特别指明的话，都是指全函数。说f是满射(surjection,或说f maps A onto B)
23、，如果 ran(f)=B，即对任意的yB 都有原像。说f是单射(injection，或说f is one-one)，如果有f(x1)=f(x2)则x1=x2，即对任意的yB，如果它有原像的话，则有唯一的原像。推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两
24、个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 说f是双射(bijection，或说f是一一对应)，如果f既是满射，又是单射，即对任意的yB，都有唯一的原像，同样根据全函数的定义，对于任意xA 都有唯一的像。这时可以定义f的逆函数(inverse function)，记为f-1:BA，f-1(y)=x当且仅当f(x)=y。显然f-1也是双射。集合的基数(cardinal number)或说势：集合 A 的基数记为|A|，且有：对
25、于有限集合 A，令 A 的基数为 A 中元素的个数。定义无限集合，不直接定义基数，而是通过定义两个集合之间的等势关系来刻划集合的基数或势，说集合 A 和集合 B 是等势的(equipotent)，如果存在一个从 A 到 B 的双射。根据双射的性质，可以证明等势是集合上的一个等价关系。称与自然数集等势的集合为可列集(enumerable)，有限集和可列集统称为可数集(countable)。设 A 和 B 是有限集合，有|P(A)|=2|A|，|AB|=|A|B|。3.小结 下面以树的形式给出了以上主要概念之间的关系：集合 子集 集合的补、并、交、差 有序对 幂集 笛卡尔积 关系 关系的自反、对称
26、、传递性 函数 单射、满射、双射 4.归纳定义和归纳证明 一个集合的归纳定义(inductive definition)通常分为三步：推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的
27、全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 归纳基：一些基本的元素属于该集合；归纳步：定义一些规则（或者说操作），从该集合中已有的元素来生成该集合的新的元素；最小化：该集合中的所有元素都是通过基本元素以及所定义的规则生成的，换句话说，该集合是由基本元素及规则所生成的最小的集合。自然数集N的归纳定义：1.归纳基：0 是一个自然数，即 0 N。2.归纳步：若n是自然数，则n的后继也是自然数。记n的后继为 succ(n)，即若nN，则 succ(n)N。为方便起见，后面也记n的后继为n+1。3.最小化：
28、所有的自然都通过步骤1 和2 得到，或者说自然数集是通过步骤1和2 得到的最小集合。这种定义方式可推广到对其他一些概念的定义，例如上述多个集合的 并、交、笛卡尔积以及多个元素的有序n元组都可通过递归的方式定义。例如，对于多个集合的并可定义为：归纳基：A1A2=x|xA1或者xA2 归纳步：A1A2An=(A1A2An-1)An 这里不需要最小化，因为这里不是定义集合。数学归纳法：关于自然数的许多性质都可通过数学归纳法来证明，对于性质 R，如果它对 0 成立，而且如果对于n成立的话，能够得到它对于n+1 也成立，那么性质 R 对所有的自然数成立。这种证明方法的正确性本身可通过自然数的归纳定义来得
29、到证明：定义集合 S=nN|性质 R 对 n 成立 归纳基：根据上面的定义有 0S 归纳步：根据上面的定义有如果nS，则n+1S，所以 S 是满足上面自然数集的归推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解
30、有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数纳定义中的 1、2 点的一个集合，而自然数集N是满足这两点的最小集合，所以有N S，而显然有 SN，所以 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)形式系统 形式系统的定义：一个形式系统S由下
31、列 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)也
32、是形式系统S中的定理。对于形式系统中的规则Rn:FS FS FS FS，通常表示成下面的形式：t1,t2,tn Rn(t1,t2,tn)形式系统具有两个特征：推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关
33、的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 形式化实际上是一个可机械实现的过程，在它里面，符号、规则和演算等被表示得严密、精确。在形式系统S中，只能使用字母表S中的符号，只承认公式集FS中的符号串的合理性，只能由公理集，根据规则推出有意义的东西来。形式系统一旦完成，就成了符号串及根据规则进行的符号串的改写，系统与一切实际意义就毫不相干，或者说已经通过这种符号，从实际问题中抽象出了我们所需要研究的内容。在形式系统内部，所能认识的只能是符号串及其改写，只能在形式系统外对这种符号
34、串及规则赋予意义。对象语言(Object language)与元语言(Meta language)：数理逻辑所研究的是“数学推理”，而使用的方法也是数学推理，所以有必要区分这两个层次的推理。把作为研究对象的“推理”形式化，使用形式语言来表示作为研究对象的“推理”的前提、结论和规则等，这种形式语言是我们所研究的对象语言。另一方面，关于形式系统的性质、规律的表达和作为研究方面的推理方式使用另一种语言来表达，这个语言称为研究的元语言，通常使用半数学化的自然语言。形式语言的语法(Syntax)与语义(Semantic)：形式语言的语法是构成形式系统的公式集、公理集和规则集的法则。形式语言的语义是关于形
35、式系统的解释和意思。形式语言本身没有含义，但我们在构造它们时是假想它们能代表某种意义的，特别的当我们在选择形式系统的公理时，总是选择所研究的问题域中那些最为明显或最容易公认为正确的性质。6.习题 1.令集合 A=n|n 10 且 n 是奇数，B=n|n 10 且 n 是素数，请回答下列问题：推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本
36、概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 a)请用列元素的方法列出集合 A 和集合 B，请问集合 B 是否是集合 A 的子集 b)请计算 AB、AB、AB、AB 以及 P(A)(即 A 的幂集)。2.设关系 R=|a和b是互质的自然数，请问 R 是自反的吗对称的吗传递的吗为什么 3.设f:AB 是函数，R 是 A 上的如下二元关系：R=|a
37、,bA,f(a)=f(b)，证明 R 是 A 上的一个等价关系。4.使用数学归纳法证明：12+22+32+n2=(n*(n+1)*(2n+1)/6 5.设有函数f:NN N，f(n)=，请问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)=a，请问 R 满足怎样的条件时f是单射*8 请给出的集合
38、方式的定义。若定义：x,y,z=x,x,y,x,y,z，则如果有x1,y1,z1=x2,y2,z2是否意味着有x1=x2且y1=y2且z1=z2推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计
39、算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数第二讲 数理逻辑 一、命题逻辑(Propositional Logic)1.内容概述 简单命题与复合命题：什么是命题命题联结词及其含义。命题公式与赋值：命题逻辑公式的归纳定义，命题公式的真值表。等值演算：命题公式的等值赋值，重要的等值式。命题联结词的完备集：通过等值演算得到命题联结词的完备集和极小完备集。命题公式的范式：析取范式与合取范式。命题演算系统：使用命题逻辑公式进行推理的形式系统。命题演算系统的语义与命题演算系统的元性质：注意区别形式系统
40、的语法和语义。2.简单命题与复合命题 命题(proposition)：经典命题逻辑中，称能判断真假但不能既真又假的陈述句为命题。命题对于命题逻辑来说是一个原始的概念，不能在命题逻辑的范围内给出它的精确定义，只能描述它的性质。命题必须为陈述句，不能为疑问句、祈使句、感叹句等，例如下述句子为命题：1.3 是有理数 2.8 小于 10 3.2 是素数 4.乌鸦是黑色的 下列句子不是命题：1.这个小男孩多勇敢啊！2.乌鸦是黑色的吗 3.但愿中国队能取胜。4.请把门开一开！下列句子不可能判断其为真或为假，所以也不是命题：推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等
41、几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 1.x+y 10 2.我正在撒谎 命题必须具有真假值，从某种意义上来说，疑问
42、句、祈使句、感叹句没有真假之分。但能判断真假，并不意味着现在就能确定其是真还是假，只要它具有能够唯一确定的真假值即可，例如下述陈述句是命题：1.明年的中秋节的晚上是晴天 2.地球外的星球上存在生物 3.21 世纪末，人类将居住在太空 4.哥德巴赫猜想是正确的 经典命题逻辑不区分现在已确定为真，还是将来可能确定为真这种情况，处理与时间有关的真值问题是时态逻辑的任务。经典命题逻辑也不区分是在技术上可以确定为真，还是现在的技术条件下不可以确定为真的这种情况，只承认在技术上，或者说能给出某种方法确定为真的那些东西才为真是直觉逻辑的观点。真命题和假命题：命题是为真或为假的陈述句，称这种真假的结果为命题的
43、真值。如果命题的真值为真，则称为真命题，否则称为假命题。命题常量与命题变量：使用符号来表示命题，通常用p,q或带下标来表示命题常量或者变量。如果命题符号p代表命题常量则意味它是某个具体命题的符号化，如果p代表命题变量则意味着它可指代任何具体命题。如果没有特别指明，通常来说命题符号p等是命题变量，即可指代任何命题。简单命题与复合命题：不能分成更简单的陈述句的命题为简单命题或原子命题，否则称为复合命题，复合命题使用命题联结词联结简单命题而得到。复合命题的联结词通常包括：设p是任意命题，复合命题“非p”称为p的否定（非），记为 p。设p和q是任意命题，复合命题“p且q”称为p和q的合取（与），记为p
44、q。设p和q是任意命题，复合命题“p或q”称为p和q的析取（或），记为pq。推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术
45、或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 设p和q是任意命题，复合命题“如果p则q”称为p蕴涵q，记为pq。设p和q是任意命题，复合命题“p当且仅当q”称为p与q等价，记为pq。上 述 定 义 中 的 非(negation)、合 取(conjunction)、析 取(disjunction)、蕴 涵(implication)和等价(equivalence)是在命题逻辑中的术语，而引号中给出的复合命题是自然语言中的典型用法。当然，命题逻辑中符号化形式的复合命题在自然语言中有许许多多的表达方法，这也是为什么自然语言有歧义的原因，参见教材中的各例题，并注意以
46、下几点：pq的逻辑关系是pq为真当且仅当p和q中至少有一个为真。但自然语言中的“或”既可能具有相容性，也可能具有排斥性。命题逻辑中采用了“或”的相容性。pq的逻辑关系是pq为假当且仅当p为真，而q为假，称p为蕴涵式的前件，q为蕴涵式的后件。现实世界中的“如果则”与这种蕴涵有比较大的区别。简单命题逻辑中的这种蕴涵常常称为“实质蕴涵”，相对应地有“严格蕴涵（p严格蕴涵q，意味着p为真，则q不可能为假）”、“相干蕴涵”等。实质蕴涵意味着可从假的前提推出任何命题来，或两个不没有内在联系的命题之间存在蕴涵关系。将日常生活中的陈述句符号化为命题逻辑中的公式是在今后的程序编写等课程中应用数理逻辑知识的重要基
47、础。但就数理逻辑这门课程本身而言，我们只关心公式之间的真值关系，而不关心公式所具体指代的命题。复合命题与简单命题之间的真值关系可用下表给出，其中 0 代表假，1 代表真：p q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 3.命题逻辑公式 【定义】命题逻辑公式(propositional logic formula)由以下子句归纳定义：推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有用处熟练掌握有关集合函数关系等基本概念代数结
48、构对于抽象数据类型形式语义的研究很有结构的基本知识图论对于解决许多实际问题很有用处对于学习数据结构编译原理课程也很有帮助要求掌握有关图树的基本概念以及如何将图论用于实际问题的解决并培养其使用数学工建立模型的思维方式讲课时间为两个学期第一学内容和难度二数理逻辑发展史目的了解有关的背景加深对计算机学科的全面了解特别是理论方面的了解而不限于将计算机看成是一门技术或工程性的学科通过重要的历史事件了解计算机科学中的一些基本思维方式和一些基本问题数 1.归纳基：命题常量或命题变量是命题逻辑公式，称为命题逻辑公式的原子项。2.归纳步：如果 A,B 是逻辑公式，则(A)、(AB)、(AB)、(AB)和(AB)
49、也是命题逻辑公式。3.最小化：所有的命题逻辑公式都通过 1 和 2 得到。在这里我们隐含地使用的字母表是大小写的英文字母、命题联结符和园括号。英文字母还可带下标。其它的符号都不属于我们的符号表，即在命题逻辑公式中不能出现这些符号。后面我们将命题逻辑公式简称为命题公式，或在没有二义的情况下进一步简称为公式。【例子】(p q)(p)(q r)是命题公式，它通过以下步骤生成：1.p 是公式；q 是公式；(p q)是公式；(p)是公式；r 是公式；(q r)是公式；(p)(q r)是公式；(p q)(p)(q r)是公式。对于所有的原子项p，都满足性质 R；2.如果对任意的公式 A 和 B 都满足性质
50、 R，就有(A)、(AB)、(AB)、(AB)和(AB)也满足性质 R。那么，所有的公式 A 就都满足性质 R。该定理的证明类似数学归纳法的证明，很容易根据定义得到。【定义】命题公式 A 的复杂程度deg(A)定义为：1.如果 A 是原子项，则deg(A)=0；2.deg(A)=deg(A)+1;3.deg(A*B)=max(deg(A),deg(B)+1，其中*代表、之一。此定义等价于教材 p11 的定义。只不过我们在这里给出的是递归定义。使用归纳法，我们可证明下面定理：推理这对程序设计等课程是极有用处的集合论数学的基础对于学习程序设计数据结构编译原理等几乎所有计算机专业课程和数学课程都很有