哈工大离散数学概念定理总结

1 / 58 哈工大离散数学概念定理总结 离散数学总结 班级： 学号： 姓名： 临近期末各科课程已经结束，随之而来就是总结各科学习总结和对这门学科的建议。离散 数学这门课程当然也不会例外了。经过一个学期的学习我发现离散数学是一门理论性非常强的课程，而且知识点非常多，定义和定理以及定律是数之不尽。 离散数学顾名思义就是一门数学，它是数学众多领域中的一个小分支，即使是一个小小的分支，但是它的内容也非常之多，同时也非常抽象。自认我的数学成绩还是不错的，但是面对离散数学我就头痛，书本里面很多知识点我都是似懂非懂地。但鉴于离散数学在计算科学中的 重要性，这是一门必须牢牢掌握的课程。因此我也很无奈，只好硬着头皮去学好它了。 离散数学是理论性较强的学科，学习离散数学的关键是对离2 / 58 散数学 (集合论、数理逻辑和图论 )有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 离散数学的特点是： 1、知识点集中，概念和定理多。离散数学是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。离散数学的证明题多，不同的题型会需要不同的证明方法，同一个题也可能有几种方法。但是离散数学证明 题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法，再 者要善于3 / 58 总结。 在学习离散数学的过程中，我明白了理解概念是至关重要的。只有概念明确，才有可能将离散数学学好。但是初学者往往不能够将概念与现实世界中的事物联系起来，这是学好离散数学的基础，因此也是初学者面临的一个困难。只有克服它，你才能有可能学好离散数学。 学完这门课后，我总结 到了，如果你想学得更好 你可以在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。而且必须及时复习和总结。 离散数学是一门数学科，大家都知道学数学就是要大量做数学，因此离散数学也不会例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学的思维方法。这一点非常重要。 课程虽然是上完了，但是老师你的教学方法独 特而新颖，思想开化而先进，是个容易沟通的老师。有你带着我们学习离散数学就是我们不想学好，我想也是很难吧！就我来说每次上课时在我快要与 周公 会面之际，你突然一个笑话和雷人的语录，我和 周公 迫不得已就分开了。当我再次看4 / 58 到周公时，耳边 已响起 铛铛铛 。老师你知道么同学们背后都忍不住夸你可爱。 下面是我对老师你的建议： a) 我认为老师你讲课时，可以在结合理论前提下多针对一些实际问题， 特别是与计算机有关的问题，这样既提高了学生的学习兴趣，又 使 的学生更好地体会离散数学对研究计算机科学的重要性。 b) 注重归纳总结，掌握规律，使学生能够理清头绪，加深印象，从而 提高学习效率。虽然这么说，但是我认为老师你这方面 做得很好， 你不仅每节课总结上一节课学习的内容，而且每一章结束后5 / 58 也会给 我们总结这一章的内容。 c) 离散数学中一些概念很多，也很容易混淆，虽然我自己喜欢总 结一些它们的共同点和不同点。但是我想老师你如果为我们总结一 下的话，我想我们会学得更多。在教学过程中，如能充分利用比较 的方法，讲清它们的共同点和不同点，能让我们加深对概念的理解 ， 从而减少判断的错误。 d) 离散是一门数学科，数学就离不开做题。最好适量的布置课堂作业， 并要求学生按时按量完成。批改后将作业中暴露出来的普遍6 / 58 问题通 过讲评，帮助学生澄清模糊和错误的认识。再者老师你可以在上课 时多找学生回答问题或者上黑板做题，我想这样可以增加学生的压 力，从而更加用心的去听课。 通过离散数学的学习，我明白了一个道理，凡事开头难，学习也是如此。在以后的学习中，我想比离散数学这么课程难的一定还有很多很多。但是学习了这门课后，我想我一定不会再怕了。离散教会了我理论与实际必须相结合，概念是学习一门课的基础，只有完全明白概念，才能够挖掘更多的 宝藏 ，进而收获得更多。 只要下足功夫，我想每个人都能有扎 实的基础，学好离散可以大大提高我们的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上思维理解上的困难。 7 / 58 离散数学课程总结 姓名： 学号： 班级： 级计科系软件工程班 近年来，计算机科学与技术有了飞速发展，在生产与生活的各个领域都发挥着越来越重要的作用。离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程。 一、课程总结 本书的主要内容有数理逻辑、集合论、代数结构、组合数学、图论以及初等数论六部分，而我们主要学习的有第一部分数理逻辑、第二部分集合论以及第五部分图论，第三部分代数结构也学习了一部分。 第一部分：数理逻辑 8 / 58 数理逻辑是 研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演 算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。 1. 在命题逻辑的基本概念中学习了命题的真值及真值表、命题与联结词、命题及其分类、联结词与复合命题、命题公式及其赋值。 2. 在命题逻辑的等值演算中主要学习了等值式与基本的等值式模式、等值演算与置换规则、析取范式与合取范式，极大值和极小值，主析取范式与主合取范式、联结词完备集。 3. 在命题逻辑的推理理论中主要学习了推理的正确与错误、推理的形式结构、判断推理正确的方法、推理定律；自然推理系统 P、形式系统的定义与分类、自然推理系统 P，在 P 中构造证明：直接证明法、附加前提证明法、归谬法。 4. 在一阶逻辑基本概念中主要学习了一阶逻辑命题符号化、个体词、谓词、量词、一阶逻辑公式及其解释、一阶语9 / 58 言、合式公式及合式公式的解释、永真式、矛盾式、可满足式。 5. 在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统 N 及其推理规则。 第二部分：集合论 在集合论中，主要学习了集合代数、二元关系和 函数。 1. 在集合代数中，学习了集合的基本概念：属于、包含、空集、元集、幂集、全集；集合的基本运算：并、交、补相对、对称差等；集合恒等式：集合运算的主要算律、恒等式的证明方法。 2. 在二元关系中学习了有序对与笛卡儿积、二元关系的定义与表示法、关系的运算、关系的性质、关系的闭包、等价关系与划分、偏序关系。 第三部分：代数结构 10 / 58 在代数结构中，主要学习了代数 系统、群与环。 1、 在代数系统中学习了二元运算及其性质：一元和二元运算定义 及其实例、二元运算的主要性质、代数系统：代数系统定义及其实例、子代数、积代数。 2、 在群与 环中学习了群的定义与性质：半群、独异点、群、阶。 第五部分：图论 在图论中主要学习了图的基本概念、欧拉图与哈密顿图、树。 1. 在图的基本概念中学习了图、通路与回路、图的连通性，图的矩阵表示、图的运算。 2. 在欧拉图与哈密顿图中学习了欧拉图、哈密顿图。 3. 在树中学习了无向树及其性质、生成树、根数及其应用。 二、对课程的建议 11 / 58 离散数学 是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性 质。在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念真正的含义 。 另外，离散这门课程我觉得每一个部分之间并没有什么太大的联系，可以说都是独立的，所以我们可以对内容侧重讲解，虽然说这对以后的数据结构有一定的影响。所以更应该对一些有用的内容进行选择性的部分详细讲解。 更重要的一点就是加强实践，因为本书多是概念，我们不能仅仅只是纸上谈兵，例如在数理逻 辑中，我们可能对一些命题逻辑公式熟练于心，但是解决实际问题时可能有各种问题。因此我们要加强训练，多做一些证明题，这样才能把理念用于实践之中。后面的图论就更不用说了，只有结合实际的题目才能够掌握和理解。 三、对老师的建议 12 / 58 老师讲课很认真，对每一个知识点讲的也很是详细，但是我觉得老师不够严厉。另外，我希望老师可以穿插介绍一些知识点在计算机科学中的应用，将之与离散数学理论结合介绍给学生，使学生更重视这一课程的学习。 第一章 1、只有努力学习，认真复习 ，才能取得好成绩。 解： P ： 努力学习。 Q ：认真复习。 R：取得好成绩。 ?R =?R = R 2、范式 例：求公式 ）的和取范式 13 / 58 原式 = ） ） = = = 第二章 1、公理 证明 ） 公理 用 代入 ） ） 公理 ） ） ） 14 / 58 ） ） 对 用分离规则 证明 ） 3、例 证明 公理 14 P 用 ? P， Q用 ?代入 ? ? P P 公理 15 加头规则用 式得 传递规则 P ? ? P 定理 Q ? ? Q P 用 Q 代入 加头规则用 式得 15 / 58 传递规则 4.假设法 例 证明 ） R ） P 假设 P Q 假设 P 公理 8 Q 公理 9 P 分离规则 Q 分离规则 Q R 分离规则 R 分离规则 16 / 58 由假设推理过程的定义知 P ， P Q R 由推理定理知 ） R ） 第三章 1、谓词演算公式 例：把下列语句翻译为谓词演算公式 注意： ?x 后的主联结词用 ； ?x后的主联结词用 。 并非 人不为己，天诛地灭 我为人人，人人为我。 17 / 58 有些 学生喜欢所有的老师。 有些作家没写过小说。 令表示为人；集合名词 表示为； 表示诛； 表示灭； 表示天，表示地； 则原句译为： ? ?x ? ） ） 我为人人，人人为我。 18 / 58 令表示为人；集合名词 表示为； a 表示我； 则原句译为： ?x ） ） 有些学生喜欢所有的老师。 令 S 表示为学生；集合名词 L 表示喜欢； T 表示 e为老师；集合名词 则原句译为： ?x表示为作家；集合名词 19 / 58 W 表示写； N 表示 e为小说；集合名词 则原 句译为： ?x (?zY(z) Z(x) ) ?x ?y ?z(X(x,y,z) (?uY(u,x) ?xW(y,x) ? ?x ? ） ） 解： 消去 、 ? ?x (?zY(z) Z(x) ) 否定深入 20 / 58 ?x (?zY(z) Z(x) ) 前移量词 ?x ?y ?z (Y(z) Z(x) ) 化为 SKOLEM标准形 ?y (Y(f(y) Z(a) ) 解： 消去 、 ? ?x ?y ?z(X(x,y,z) (?(?uY(u,x) ?xW(y,x) 否定深入 ?x ?y ?z(X(x,y,z) ( ? u ? Y(u,x) ?xW(y,x) 改名 21 / 58 ?x ?y ?z(X(x,y,z) ( ? u ? Y(u,x) ?vW(y,v) 前移量词 ?x ?y ?z ? u ?v(X(x,y,z) (? Y(u,x)W(y,v) 化为 SKOLEM标准形 ?y ?z ? u (X(a,y,z) (? Y(u,a)W(y,f(y,z,u) 第四章 1、例 ：已知知识： 桌子上的每本书均是杰作； 写出杰作的人是天才； 某个不出名的人写了桌上某本书。 结论 某个不出名的人是天才。 22 / 58 解：先把知识翻译为符号公式： 令 A(e)表示 e 为书 ； B(e)表示 e 为杰 作 ； C(e)表示 e 为天才 ； D(e)表示 e 出名 ； P(e)表示 e 为人 ； W(e1,e2)表示 e1 写了 e2 。 ?x (A(x) B(x) ?x ?y(P(x) B(y) W(x,y) C(x) ?x ?y(P(x) A(y) ?D(x) W(x,y) 23 / 58 结论： ?x (P(x) ?D(x) C(x) 1.归结法 ? A(x1) B(x1) ? P(x2) ? B(y) ? W(x 2,y) C(x2) P(a) A(b) ?D(a) W(a,b) ? P(x3) D(x3) ? C(x3) 结论的否定 ? P(a) ? C(a) a/x3 归结 ? C(a) 24 / 58 归结 ? P(a) ? B(y) ? W(a,y) a/x2 归结 ? B(y) ? W(a, y) 归结 ? A(y) ? W(a,y) y/x1 归结 ? W(a,b) b/ y 归结 归结 2.假设推理法 ?x (A( x) B(x) 假设 ?x ?y(P(x) B(y) W(x,y) C(x) 25 / 58 假设 ?x ?y(P(x) A(y) ?D(x) W(x,y) 假设 P(a) A(b) ?D(a) W(a,b) 额外假设 (P(a) ?D(a) ) (A(b)W(a,b) (P(a) ?D(a) 公理 8 (P(a) ?D(a) ) (A(b)W(a,b) (A(b) W(a,b) 公理 9 P(a) ?D(a) 分离 (4)(5) A(b) W(a,b) 分离 (4)(6) 26 / 58 (P(a) ?D(a) P(a) 公理 8 (A(b)W(a,b) A(b) 公理 8 (A(b)W(a,b) W(a,b) 公理 9 P(a) 分离 (7)(9) A(b) 分离 (8)(10) W(a,b) 分离 (8)(11) A(b) B(b) 全称量词消去规则 (1) A(b) B(b) 全称量词消去规则 (1) B(b) 分离 (1)(15) P(a) (B(b) (P(a) B(b) ) 公理 10 27 / 58 B(b) (P(a) B(b) ) 分 离 (12)(17) P(a) B(b) 分离 (16)(18) (P(a) B(b) ( W(a,b) (P(a) B(b) ) W(a,b) ) 公理 10 (21) W(a,b) (P(a) B(b) ) W(a,b) 分离 (19)(20) (22) (P(a) B(b) ) W(a,b) 分离 (14)(21) (23) (P(a) B(b) ) W(a,b) C(a) 全称量词消去规则 (2) 28 / 58 (24) C(a) 分离 (22)(23) (25) (P(a) ?D(a) ) (C(a) (P(a) ?D(a) ) C(a) ) 公理 10 (26) C(a) (P(a) ?D(a) ) C(a) ) 分离 (7)(25) (27) P(a) ?D(a) C(a) 分离 (24)(26) (28) P(a) ?D(a) C(a) ?x (P(x) ?D(x) C(x) ) 公理 21 (29) ?x (P(x) ?D(x) C(x) ) 分离 (27)(28) 由存在推理定理得 : 29 / 58 ?x (A(x) B(x) ;?x ?y(P(x) B(y) W(x,y) C(x) ; ?x ?y(P(x) A(y) ?D(x) W(x,y) ?x (P(x) ?D(x) C(x) ) 由假设推理定理得： ?x (P(x) ?D(x ) C(x) ) 3.霍恩子句逻辑程序 B(x1) A(x1) C(x) (P(x) B(y) W(x,y) P(a) 1、设 A为任意非空集合， *是集合 A 上的二元运算。 封闭性： 结合律： a*=*c 30 / 58 交换律： a*b=b*a 幂等率： a*a=a 分配律： a# (b*c)=(a# b)*(a #c) # a=* 吸收率： a*b=b*a a #(b*c)=a 和 a* (b# c)=a，则称 和*运算时可吸收 的。 2、左幺元： e*x=x 右幺元： x*e=x。 幺元： x*e=e*x=x 3、左零元： *x = 右零元： x* = 零元： *x =*x = 4、在 A 中有关于运算 *的左幺元 和右幺元 ，则 A 中幺元 e是惟一的。 5、在 A中有关于运算 *的左零元 和右零元， 则 A中零元 是惟一的。 6 代数系统中， A 的元素个数多于 1 个， e 。 是关于 *的幺元，若对 A中某个元素 a， b 31 / 58 左逆元： b*a=e 右逆元： a*b=e 逆元： a*b=b*a=e 8、 A中存在幺元 e，且每一个元素都有左逆元， *是可结合运算，左逆元 =右逆元，逆元惟一。 9、半群： 封闭 (a*b)*c=a*(b*c) 10：半群 +含有幺元 e = 独异点 =*运算的任何两行两列均不同 11、是独异点， a， b均有逆元 ?1 ?1=? a*b 有逆元， ? ?1= ?1?1。 定义 设是一个代数系统，其中 G是非空集合， *是 G 上一个二元运算， 如果 *是封闭的； 32 / 58 运算 *时可结合的； 存在幺元 e； 对于每一个元素 ，存在它的逆元；则称是一个群。 定义 设是一个群，如果 G 是有限群，那么称为有限群， G中元素的个数统称称为该有限群的阶数，记为 。 定义 若群 G 中，只含有一个元素，即 G=|e|， |G|=1，则称G 为平凡群。 ， G 关于 *运算，构成一个群，这个群称为 Klein 四元群。 定义 设是一个群，若运算 *在 G上满足交换律，则称 G 为交换群或 Abel 群。 定义 设是群，若 ，使得成立的最小正整数 k称 为 a 的阶，记作 |a|。 定理 设为群， 有： ； ； ；若 G为 Abel群 ， 。 33 / 58 定理 对 |G|1 的群不可能有零元。 定理 设是一个群，对于 。必存在惟一的，使 a*x=b。 定义 设为群，若在 G 中存在一个元素 a，使得 G 中存在一个元素 a，使得 G 中的任意元素都由 a 的幂组成，则称该群为循环群，元素 a称为循环群 G的生成元。 定义 设是一个群， S 是 G的非空子集，如果也构成群，则称是的一个子群，记作 SG 。 子群判别定理： 定理 设是群， H是 G 的非空子集，则 HG iff 。 a， bH ，有 a*bH ； aH ，有 a-1H 。 定理 设是群， H是 G 的非空子集， iff a， bH ，则 a*b-1H 。 34 / 58 定理设是群， H 是 G 的有穷非空子集，则 H 是 G的子群 iff a，bH ，有 a*bH 。 设是群， C=a|aG ，且对 xG 有 a*x=x*a， C又称 CentG. 定义 设是一个代数系统，如果满足 是阿贝尔群； 是半群； 运算 *对于运算 是可分配的； 则称是环。 定理 设是一个环，则对任意 a， bA 有 ； ； ； ； 其中 是加法幺元， -a 是 a 的加法逆元， a+记为 a-b，注意35 / 58 上面各式中不能只理解是实数上的加法与乘法。 定义 设是环，对 a， bR ， a0 ， b0 ，但 ab=0 ；则称 a是 R 中的一个左零因子， b 是 R 中一个右零因子；若一个元素既是左零因子，又是右零因子，则称它是一个零因子。 定义 设 R 是一个环，对于任意的 a， bR ，若 ab=0 ，则a=0或 b=0，就称 R 是一个无零因子环。 定理 设是环， R 是无零因子环的充分必要条件，是在 R 中乘法适合消去律，即对任意 a， b， cR ， a0 ，若有 ab=ac ，则有 b=c。 定 义 设是环。如果是可交换的，则称是可交换环。 如果含幺元，则称是含幺元。 定义 设是一个代数系统，如果满足： 是阿贝尔群； 是可交换独异点，且无零因子，即对任意 a， bA ， a ， b 36 / 58 必有 ab ； 运算 对于运算 +是可分配的。 则称是整环。 定义 设是一个环，且 |R|2 ， R有幺元；每个非零元有逆元；则称这个环是除环。如果一个除环是 可交换的，称为域。 当为域时，及是阿贝尔群，其中 R*=R-|0|。 定义 设是一个偏序集，如果 A 中任意两个元素都有最小上界和最大下界，则称为格。 定义 设是一个格， P 是由 格中元素及 ， =， ， ， 等符合所表示的命题，如果将 P中的分别换成 ， ， ， 得到的命题 P*，称 P*为 P的对偶命题，简称对偶。 格的对偶原理：如果命题 P 对一切格 L为真，则 P的对偶命题业对一切格为真。 定义 设是一个格，如果在 A 上定义两个二元运算 和 ，使得对任意 a， bA ， ab 等于 a和 b 的最小上界， ab 等37 / 58 于 a 和 b 的最大下界。称为由格所诱导的代数系统。二元运算 和 分别称为并运算和交运算。 定理 在格中，对任意 a， bA ，都有： aab ， bab ， aba ， abb 。 定理 设是格， a， bA ， ab ，且 ac=abc ； ab且 ac =bc 。 定理 在格中，对于 a， b， c， dA ，如果 ab ， cd ，则 acbd ， acbd 。 定理 设是一个格，由所诱导的代数系统为，则对于任意 a，b， c， dA ，有： ； ；结合律 aa=a ； aa=a 38 / 58 a(a b)=a ； a (ab)=a ； 定理 设是一个代数系统，其中 和 都是二元运算，且满足交换性，结合性和吸收性，则 A 上存在偏序关系 ，使是一个格。 定义 设是代数系统，其中 和 是二元运算，若 和 运算满足交换律，结合律，吸收律，则称是一个格。 定理 设是格，则 a， b， cL 有 ab=acbc ，且 acbc ； a， b，c， dL 有 ab 且 cd=acbd ，且 acbc ； 定理 设是格， S是 L 的非空子集，若 S 关于运算 和 是封闭的，则称是格 L 的子格。 定义 设是由格所诱导的代数系统，如果对任意 a， b， cA满足：，称是分配格。 定义 设和是两个格，由它们分别诱导的代数系统为和，如果存在着一个从 A1到 A2的映射 f，使得对任意 a， bA1 有： 39 / 58 ，称 f为从到格同态，也可称是的格同态 象。当 f 是双射时，格同态也称为格同构。 定理 格 L 是分配格，当且仅当 L 既不含有与五角格同构的子格，也不含有与钻石格同构的子格。 每一条链都是分配格。小于五个元素的格都是分配格。 定义 设是一个格，如果存在元素 aA 对于任意 xA ，都有ax ，则称 a为格的全下界。记作 0。 存在全上界和全下界的格称为有界格，记作。 定义 设是有界格 aA ，若存在 bA ，使得 ab=1 ，且ab=0 ，称 b 是 a 的补元。 定义 在一个有界格中，如果每个元素至少有一个补元，则称此格为有补格。 定义 一个有补格称为布尔格。 定理 设有代数系统，其中 B至少包含 两个元素， ， 为 B40 / 58 上两个二元运算， 为 B 上一元运算，对任何 a， bB 满足 ab=ba ， ab=ba 离散数学 第一章 命题逻辑 定义 1。设 P为一命题， P 的否定是一个新的命题，记作 ?P。若 P 为 T， ?P为 F；若 P 为 F， ?P为 T。联结词 ? 表示命题的否定。否定联结词有时亦可记作 。 定义 2。两个命题 P 和 Q 的合取是一个复合命题，记作 PQ 。当且仅当 P,Q同时 为 T时， PQ 为 T，在其他情况下， PQ 的真值都是 F。 定义 3。两个命题 P 和 Q 的析取是一个复合命题，记作 PQ 。当且仅当 P， Q同时为 F时， PQ 的真值为 F，否则 PQ 的真值为 T。 定义 4。给定两个命题 P 和 Q，其条件命题是一个复合命题，41 / 58 记作 PQ ，读作 如果 P，那么 Q 或者 若 P 则 Q 。当且仅当 P 的真值为 T， Q 的真值为 F 时， PQ 的真值为 F，否则 PQ 的真值为 T。我们称 P为前件， Q 为后件。 定义 5。给定两个命题 P 和 Q，其复合命题 P?Q的真值为 F。 定义 6。命题演算的合式公式，规定为： 单个命题变元本身是一个合式公 式。 如果 A是合式公式，那么 ?A是合式公式。 如果 A 和 B是合式公式，那么，和都是合式公式。 当且仅当能够有限次地应用，所得到的包含命题变元，联结词和括号的符号串是合式 公式。 定义 7。在命题公式中，对于分量指派真值得各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。 定义 8。给定两个命题公式 A 和 B，设 P1， P2， ?， Pn 为所42 / 58 有出现于 A和 B中的原子变元，若给 P1， P2， ?， Pn任一组真值指派， A 和 B 的真值都相同，则 称 A 和 B 是等价的或逻辑相等。记作 A?B。 定义 9。如果 X 是合式公式的 A 的一部分，且 X 本身也是一个合式公式，则称 X 为公式 A的字公式。 定理 1。设 X 是合式公式 A 的字公式，若 X?Y，如果将 A 中的 X 用 Y 来置换，所得到公式 B与公式 A 等价，即 A?B。 定义 10。给定一命题公式，若无论对分量做怎样的指派，其对应的真值永为 T，则称该命题公式为重言式或永真公式。 定义 11。给定一命题公式，若无论对分量做怎样的指派，其对应的真值永为 F，则称该命题公式为矛盾式或永假公式。 定理 2。任何两个重言式的合取或析取，仍然是一个重言式。 定理 3。一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。 定理 4。设 A， B 为两个命题公式，A?B当且仅当 A?B 为一个重言式。 43 / 58 定义 12。当且仅当 PQ是一个重言式时，我们称 P 蕴含 Q ，并记作 P?Q。 定理 5。设 P， Q为任意两个命题公式， P?Q 的充分必要条件是 P?Q 且 Q?P。 定义 13。设 P 和 Q 是两个命题公式，复合命题 P?Q 称作 P 和 Q 的不可兼析取。 P?Q 的真值为 T，当且仅当 P 与 Q 的真值不相同时为 T，否则， PQ 的真值为 F。 定理 6。设 P， Q， R为命题公式。如果 P?Q?R，则 P?R?Q， Q?R?P，且 P?Q?R 为一矛盾式。 定义 14。设 P 和 Q 是两个命题公式，复合命题 P Q 称作命题P 和 Q 的条件否定， P Q的真值为 T，当且仅当 P的真值为 T，Q 的真值为 F，否则 P Q的真值为 F。 ? 定义 15。设 P 和 Q 是两个命题公式，复合命题 PQ 称作 P和 Q 的 与非 。当且仅当 P 和 Q 的真值都是 T时， PQ 为F，否则 PQ 的真值都为 T。 定义 16。设 P 和 Q 是两个命题公式，复合命题 PQ 称作 P和 Q 的 或非 ，当且仅当 P 和 Q 的真值都为 F时， PQ 的真值为 T，否则 PQ 的真值都是 F。 44 / 58 定义 17。在给定的命题公式中，将联结词 换成 ，将 换成 ，若有特殊变元 F 和 T亦互相取代，所得公 式 A*成为 A的对偶式。 定理 5。设 A 和 A*是对偶式， P1， P2， ?， Pn 是出现在 A 和A*中的原子变元，则 ?A?A* A?A* 定理 6。设 P1， P2， ?， Pn 是出现在公式 A 和 B 中的所有原子变元，如果 A?B，则 A*?B*。 定义 18。一个命题公式成为合取范式，当且仅当它具有型式：A1A2?An 其中 A1， A2， ?， An 都是由命题变元或其否定所组成的析取式。 定义 19。一个命题公式成为析取范式，当且仅当它具有型式：A1A2?An 其中 A1， A2， ?， An 都是由命题变元或其否定所组成的合取式。 45 / 58 定义 20。 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 定 义 21。对于给定的命题公式，如果有一个等价公式，它仅有小项的析取所组成，则该等价式称作原式的主析取范式。 定理 7。在真值表中，一个公式的真值为 T 的指派所对应的小项的析取，即为此公式的主析取范式。 定义 22。 n个命题变元的析取式，称作布尔析取或大项。其中每个变元与它的否定不能同时存在， 但两者必须出现且仅出现一次。 定义 23。对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。 定理 8。在真值表中，一个公式的真值为 F 的指派所对应的大项的合取，即为此主式的主和取范式。 定义 24。设 A 和 C 是两个命题公式，当且仅当 AC 为一重言式，即 A?C，称 C 是 A 的有效结论。或 C 可由 A 逻辑地推46 / 58 出。 定义 25。假设公式 H1， H2， ?， Hm中的命题变元为 P1， P2， ?，Pn，对于 P1， P2， ?， Pn 的一些真值指派，如果能使H1H2?Hm 的真值为 T，则称公式 H1， H2， ?， Hm 是相容的。如果对于 P1， P2， ?， Pn 的每一 组真值指派使得H1H2?Hm 的真值均为 F，则称公式 H1， H2， ?， Hm 是不相容的。 第二章 谓词逻辑 定义 1。由一个谓词和一些客体变元组成的表达式，称为简单命题函数。 定义 2。谓词演算的合成公式，可由下述各条组成： 原子谓词公式是合成公式。 若 A 是合式公式，则 ?A是一个合式公式。 若 A 和 B 都是合式公式，则，和是合式公式。 47 / 58 如果 A 是合式公式， x 是 A 中出现的任何变元，则 A 和 A 都是合式公式。 只有经过有限次地应用规则，所得到的公式是合式公式。 定义 3。给定任何两个谓词公式 wffA 和 wffB，设它们有共同的个体域 E，若对 A 和 B 的任一组变元进行赋值，所得命题的真值相同，则称谓词公式 A和 B 在 E 上是等价的，并记作： A?B。 定义 4。给定任意谓词公式 wffA，其个体域为 E，对于 A 的所有赋值， wffA都为真，则称 wffA 在 E 上是有效的。 定义 5。一个谓词公式 wffA，如果在所有赋值下都为假，则称 该 wffA为不可满足的。 定义 6。一个谓词公式 wffA，如果至少在一种赋值下为真，则称该 wffA为可满足的。 定义7。一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则该公式叫做前束范式。 定理 1。任意一个谓词公式，均和一个前束范式等价。 定义 8。一个 wffA， 如果具有如下形式称为前束合成范式。 48 / 58 ? ?其中， ?可能是量词 ?或 ?， v 是客体变元， Aij是原子公式或其否定。 ii=1， 定义 9。每一个 wffA 都可转化为与其 等价的前束合取范式。 定义 10。一个 wffA 如具有如下形式则称为前束析取范式。 ? 其中， ?， vi与 Aij 的概念与定义 8 中相同。 定理 2。每一个 wffA都可以转换为与它等价的前束析取范式。 第三章 集合与关系 外延性原理：两个集合是相等的，当且仅当它们有相同的成员。 定义 1。设 A， B是任意两个集合，假如 A 的每一个元素是 B的成员，则称 A为 B 的子集，或 A 包含在 B 内，或 B 包含在49 / 58 A。记作 A?B，或 B?A，即有 A?B?x(x?A?x?B)。 定理 1。集合 A 和集合 B相等的充分必要条件是这两个集合互为子集。 定义 2。如果集合 A 的每一个元素都属于 B，但集合 B 中至少有一个元素不属于 A，则称 A为 B 的真子集，记作 A?B。 定义 3。不包含任何元素的集合是空集，记作 ?。 定理 2。对于任意一个集合 A， ?A。 定义 4。在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作 E。对于任一 x?A，因 A?E，故 x?E，即恒真。 定义 5。给定集合 A，由集合 A 的所有子集为元素组成的集合，称为集合 A的幂集，记为 ? 。 定理 3。如果有限集合 A 有 n 个元素，则其幂集 ?有 2n 个元素。 50 / 58 定义 5。设任意两个集合 A 和 B，由集合 A 和 B 的所有共同元素组成的集合 S，称为 A 和 B的交集，记作 A?B。 定义 6。设任意两个集合 A 和 B，所有属于 A 或属于 B 的元素组成的集合 S，称为 A 和 B的并集，记作 A?B。 定理 4。设 A， B， C 为三个集合，则下列分配律成立。 a） A?=?。 b） A?=?。 定理 5。设 A， B为任意两个集合，则下列关 系式成立。 a） A?= A。 b） A?= A。 定理 6。 A?B，当且仅当 A?B=B 或 A?B=A。 定义 7。设 A， B为任意两个集合，所有属于 A而不属于 B 的一切元素组成的集合 S称为 B对于 A 的补集，或相对补，记51 / 58 作 A B。 定义 8。设 E为全集，对任一集合 A 关于 E的补 E A，称为集合 A 的绝对补，记作 A。 定理 7。设 A， B 为任意两个集合，则下列关系式成立 。 a） = A?B。 b） = A?B。 定理 8。设 A、 B为任意两个集合，则下列关系式成立。 a） A B = A?B。 b） A B =A 。 定理 9。设 A， B， C 为三个集合，则 A?= 。 定理 10。设A， B为两个集合，若 A?B，则 a） B?A。 b） ?A = B。 52 / 58 定义 9。设 A， B为任意两个集合， A 和 B的对称差为集合 S，其元素或属于 A，或属于 B，但不能既属于 A 又属于 B，记作A?B。 定理 11。设 A1， A2 为有限集合，其元素个数分别为 |A1|，|A2|，则 |A1?A2|=|A1|+|A2|-|A1?A2|。 定理 12。设 A1， A2， ?， An为有限集合，其元素个数分别为|A1|， |A2|， ?， |An|，则 |A1?A2?An|= ? ? ? ? + ?=11? 定义 10。两个序偶相等， = ， iff x=u,y=v。 定义 11。令 A和 B 是任意两个集合，若序偶的第一个成员是A 的元素，第二个成员是 B 的元素，所有这样的序偶集合，称为集合 A和 B的笛卡尔乘积或直积，记作 A?B。 定理 13。53 / 58 设 A， B， C为任意三个集合，则有 a） A?=? b） A?=? c） ?C=? d） ?C=? 定理 14。若 C?，则 A?B?。 定理 15。设 A， B， C， D 为四个非空集合，则 A?B?C?D 的充要条件为 A?C， B?D。 定义 12。任一序偶的集合确定了一个二元关系 R， R 中任一序偶可记作 ?R 或 xRy。不在 R 中的任一序偶可记作 ?R或。 定义 13。令 R 为二元关系，由 ?R 的所有 x 组成的集合