《离散数学》电子教案

离散数学教案课程名称离散数学课程代码学时（学分）54学时（4学分）授课年级、专业授课教师所属系别参考教材《离散数学》PAGE1-目录课次：1 2课次：2 7课次：3 13课次：4 19课次：5 26课次：6 31课次：7 35课次：8 39课次：9 42课次：10 45课次：11 49课次：12 53课次：13 57课次：14 61课次：15 65课次：16 69课次：17 74课次：18 80课次：19 86课次：20 91课次：21 97课次：22 103课次：23 107课次：24 113课次：25 117课次：26 119课次：27 123第=1\*Arabic1课课程章节第一章绪论第二章命题逻辑§2.1命题逻辑概述§2.2命题及命题连结词课次：1教学目的了解离散数学的地位和作用掌握命题的判定方法掌握命题连结词的含义及真值教学重点命题的判定方法命题连结词的含义及真值教学难点命题的判定方法教学过程备注课程导入：问题：1、什么是离散数学2、计算机为什么能解决问题3、什么是命题课程内容：1.1离散量与离散数学离散数学是包含数理逻辑、数论、代数、图论等多个数学分支内容的一门学科，它的研究对象是离散量及其结构和相互关系。【离散数学与计算机数学】离散数学是在计算机科学与技术的发展过程中派生出来的一门学科。而不是在数学的研究过程中从某个数学领域（或数学专题）分离出来的一个数学分支。离散数学的诞生是计算机科学和技术发展的需要。1.2离散数学的地位和作用许多计算机课程都包含大量的数学内容。举例说明如下：1.在“C程序设计”中用到数理逻辑的知识。2.在“数据结构”中用到集合论、图论、递归方法等知识。3.在“数据库系统”中用到集合论和谓词逻辑等知识。4.在“编译原理”中用到形式语言、逻辑演算、图论、布尔代数等知识。5.在“数字电路与逻辑设计”中用到逻辑演算、布尔代数（也称逻辑代数）等知识。6.在“编码理论”中用到抽象代数、线性代数、数论、布尔代数等知识。7.“操作系统”、“算法设计与分析”、“人工智能”、“计算机网络”等许多计算机专业课程都用到离散数学知识。1.3计算机为什么要依赖数学1.计算机只能处理“0,1代码”。2.计算机只能理解形式语言。3.计算机只能接受用数学结构表示的数据。4.只有数学算法才是计算机的有效算法。1.4计算机求解问题举例2007年全国大学生数学建模竞赛题目─B题：乘公交，看奥运(具体内容见教材)，说明离散数学与计算机问题求解之间的密切联系。一笔画问题。2.1命题逻辑概述2.2命题及命题联结词【命题】定义2.1能够判断真假的陈述句称为命题。猪八戒是猪么？香格里拉真是太美丽了！李是个。这手太亮！请椅搬屋。我正在说假话【命题的真值】每个命题都有一个反映命题的真假特征的属性，这个反映命题的真假特征的属性就称之为命题的“真值”。每个命题都有一个且只有一个“真值”属性值，非真即假。在计算机科学中常用表示“真值”的属性值。所以，命题是一个真命题当且仅当的真值为;命题是一个假命题当且仅当的真值为.【命题联结词】用于把一个或多个命题联结起来构成复杂命题形式的词语称为命题联结词。【联结词】称为否定联结词，用于表示一个命题的否定。设p是一个命题，则也是一个命题，读作“非”，表示命题的否定。【联结词】联结词称为合取联结词，用于表示两个命题的合取。设都是命题，则也是一个命题，称为命题与命题的合取式，读作“并且”；和都称为的合取项。【联结词】联结词称为析取联结词，用于表示两个命题的析取。设都是命题，则也是一个命题，称为命题与命题的析取式，读作“或者”；和都称为的析取项。【联结词】联结词称为蕴涵联结词，用于表示两个命题的蕴涵关系。设都是命题，则也是一个命题，称为与的蕴涵式，读作“如果，则”；称为的前件，称为的后件。例如，用表示命题：“今天是星期三”；用表示命题：“今天有英语课”，那么表示：“如果今天是星期三，则今天有英语课”。【联结词】联结词称为同真假联结词，用于表示两个命题的同真同假关系。设都是命题，则也是一个命题，称为与的同真式，读作“与同真假”。例如，用表示命题：“蓝球大于排球”；用表示命题：“羽毛球拍小于网球拍”，那么表示：“蓝球大于排球当且仅当羽毛球拍小于网球拍”。巩固练习：内容总结：1.离散数学的意义及作用2.命题的概念，如何判断命题的真假，区分简单命题与复合命题。3.命题连结词及其表达的含义 作业：网络教学平台完成作业1.课后小结：第一章内容是离散数学的导入内容，学生通过此节学习，了解了离散数学的作用和地位，对离散数学将要学习的内容有个初步的了解。第二章2.1~2.2学习内容是数理逻辑的基础，基本连结词及其真值表为后续内容奠定了基础。本节内容较简单，学生掌握很好。第2课课程章节§2.4用命题公式描述实际问题§2.3命题公式及其赋值课次：2教学目的掌握用命题公式描述实际问题熟悉命题公式的概念了解公式的层次掌握公式的真值表教学重点命题公式描述实际问题、公式的真值表教学难点命题公式描述实际问题，区分自然语言的语义表述教学过程备注课程导入：问题：这些语句含义相同么？用什么连结词来表示？课程内容：2.4用命题公式描述实际问题【命题符号化的步骤】下面给出命题符号化常用的方法和步骤：(1)把复合命题中所包含的简单命题分解出来(注意：简单命题是肯定式的陈述句)；(2)用自然语言联结词把分解出来的简单命题联系起来，得到与原命题等价的新命题；(3)用字母表示简单命题，并用逻辑联结词表示自然语言联结词，把新命题表示成合式公式。例2.7用命题公式表示下列命题：(1)李明这学期选修了三门计算机课和一门英语课。(2)李明这学期选修了数据库原理、数据结构、离散数学和英语四门课。(3)如果明天不下雨，我就上街买书。解：令表示：李明这学期选修了三门计算机课；表示：李明这学期选修了一门英语课，则原命题可表示为：.(2)令表示：李明这学期选修了数据库原理；表示：李明这学期选修了数据结构；表示：李明这学期选修了离散数学；表示：李明这学期选修了英语，则原命题可表示为：.(3)令表示：明天下雨；表示：我上街买书，则原命题可表示为：.一些常见的自然语言词语与逻辑联结词之间的对应关系。【与对应的词语】汉语中表示否定的词语有：不、非、没、无、否等。例2.8将下列命题符号化：(1)安娜是一个女生。(2)玛丽不是男生。(3)查理不是没有钱，而是不想买汽车。解：(1)令表示：安娜是一个女生，则原命题可表示为：.(2)令表示：玛丽是男生，则原命题可表示为：.(3)令表示：查理有钱，表示：查理想买汽车，则原命题可表示为：.【与对应的词语】汉语中表示同时并存性判断的联结词有：并且、也、不但…而且…、既…又…、不仅…而且…、虽然…但是…等等，逗号“，”也可以用来表示同时并存的判断。例2.9将下列命题符号化：(1)布朗和卡特都是大学生。(2)乔治与马克是大学同学。(3)林德今天参加了三项活动：打蓝球，听报告和做实验。解：(1)令表示：布朗是大学生；表示：卡特是大学生，则原命题可表示为：.(2)令表示：乔治与马克是大学同学，则原命题可表示为：.(3)令表示：林德今天打了蓝球；表示：林德今天听了报告；表示：林德今天做了实验，则原命题可表示为：.注意：(1)包含了两个简单命题，而(2)只包含一个简单命题。【与对应的词语】汉语中表示选择性判断的联结词有：“或者…或者…”、“可能…也可能…”、“要么…要么…”、“不是…就是…”等。选择性判断有两种：一是相容选择，二是不相容选择。相容选择是指在列出的几种选择中至少有一种选择成立，也可以有多个选择成立；不相容选择是指在列出的几种选择中有且只有一种选择成立，不能有多种选择同时成立。相容选择对应的命题公式是，不相容选择对应的命题公式是.例2.10将下列命题符号化：(1)考试答题可用钢笔或圆珠笔。(2)格林是北京大学的学生或清华大学的学生。(3)杯子里不是矿泉水就是纯净水。解：(1)令表示：考试答题可用钢笔；表示：考试答题可用圆珠笔，则原命题可表示为：.(2)令表示：格林是北京大学的学生；表示：格林是清华大学的学生，则原命题可表示为：.(3)令表示：杯子里是矿泉水；表示：杯子里是纯净水，则原命题可表示为：.注意：用命题公式表示一个不相容选择判断时，是否要选用不相容类型公式，可视所讨论的语句是否强调不相容的因素而定，如例2.10中的(3)就可以选用相容类型的公式.当然，选择不相容类型的公式也没有错，但显得有点累赘。【与对应的词语】汉语中表示蕴涵关系判断的联结词有：如果…，则…、只要…就…、有…就…、一旦…就…、只有…才…、除非…才…，等等。蕴涵关系判断有两类：一是充分条件型蕴涵，二是必要条件型蕴涵。充分条件型蕴涵对应的命题公式类型是，汉语中常见的联结词有：如果…，则…、只要…就…、有…就…、一旦…就…；必要条件型蕴涵对应的命题公式类型是，汉语中常见的联结词有：只有…才…、除非…才…，等等。例2.11将下列命题符号化：(1)如果是奇数，则一定是偶数。(2)只要，就有.(3)只有输入的密码是正确的，保险箱才能打开。(4)除非能被2整除，否则不能被4整除。(5)除非能被2整除，才能被4整除。解：(1)令表示：是奇数；表示：是偶数，则原命题可表示为：.(2)令表示：；表示：，则原命题可表示为：.(3)原命题包含两个简单命题：输入的密码是正确的；保险箱能打开。原命题等价于：如果输入的密码不正确，则保险箱不能打开。令表示：输入的密码是正确的；表示：保险箱能打开，则原命题可表示为：.(4)原命题包含两个简单命题：能被2整除；能被4整除。原命题等价于：如果不能被2整除，则不能被4整除。令表示：能被2整除；表示：能被4整除，则原命题可表示为：.(5)令表示：能被2整除；表示：能被4整除，则原命题可表示为：.【与对应的词语】汉语中表示同真同假判断的联结词有：当且仅当、充分必要条件等。例2.12将下列命题符号化：(1)的充分必要条件是.(2)当且仅当石头会走路。解：(1)令表示：；表示：，则原命题可表示为：.(2)令表示：；表示：石头会走路，则原命题可表示为：.2.3命题公式及其赋值【合式公式】定义2.6命题逻辑中合法的命题结构称为合式公式，或命题公式。在不引起混淆时简称公式。合式公式归纳定义如下：(1)单个命题常项是合式公式；(2)单个命题变元是合式公式；(3)若是合式公式，则()也是合式公式；(4)若是合式公式，则()，()，()，()都是合式公式；(5)所有的合式公式都是有限次应用(1)～(4)而产生的，除此之外，没有别的合式公式。注：合式公式最外层的括号可以省略不写。例2.2设都是公式，请问下列符号串中哪些是合式公式？哪些不是合式公式？(1)(2)(3)(4)(5)(6)解：(1)、(2)、(3)是合式公式，(4)、(5)、(6)不是合式公式。【联结词优先次序与括号的应用】在公式中使用括号和联结词的优先次序是为了使公式表达式更简洁、公式的层次结构更分明，应该以可读性好、易于理解为原则。【子公式】定义2.7设是一个公式，是的一个子符号串，若本身构成一个公式，则称为的一个子公式。例2.3请写出公式的所有子公式。解：公式共有九个子公式：，，，，，.【公式的层次】定义2.8设是一个合式公式，则按公式的结构将公式的层数定义如下：(1)若是不带联结词的命题公式，则是0层公式；(2)若，且是层公式，则是层公式；(3)若，或，或，或，且是层公式，是层公式，，则是层公式。例2.4设都是命题变元，请指出下列公式的层数:;;.解：是0层公式;是3层公式;是2层公式.【原子公式与复合公式】定义2.9不带任何联结词的合式公式称为原子公式，带有联结词的合式公式称为复合公式。【公式的赋值】设公式，令的真值分别为1,0,0，则这组指派就是对公式的一组赋值。若令,,，则这组指派是对公式的另一组赋值。【公式的真值表】定义2.11设是一个命题公式，把公式及其所有子公式的真值按一种直观、方便的顺序列成一张表，这样的表称为公式的真值表。例2.5列出公式的真值表。解：按公式层次从低到高排列子公式:,,,；【命题公式的分类】定义2.12设是一个命题公式，(1)若的每一组赋值都使的真值为1，则称为重言式，也称永真式；(2)若的每一组赋值都使的真值为0，则称为矛盾式，也称永假式；(3)若至少存在一组赋值使的真值为1，则称为可满足式。例2.6指出下列公式的类型：(1)；(2)；(3)；(4)；(5).解：公式(1)、(2)、(3)、(4)、(5)的真值表分别如表2.8、2.9、2.10、2.11、2.12所示。表2.8表2.9表2.10的真值表的真值表的真值表0110001000101010101110011011111111表2.11表2.12的真值表的真值表001000000101100001111000001011110100111110000101111101111111由真值表可以看出(1)和(2)都是重言式；(4)是矛盾式；(3)和(5)都是可满足式。巩固练习：内容总结：1.用命题公式描述实际问题要注意连结词的恰当选取2.公式的真值表很重要3.利用公式的真值表可以判断公式的类型：重言式、矛盾式、可满足式。 注意：在例2.11中，(1)和(2)是充分条件型蕴涵命题，选用公式；而(3)，(4)和(5)是必要条件型蕴涵命题，所以选用公式.注意：用命题公式表示一个命题时，只是把原命题写成公式的形式，不必分析命题是真的还是假的，也不必分析命题是否有实用意义。例如，公式的运算次序是明确的，若写成，则公式就更简明。若将公式写成，则用括号太多，让人眼花缭乱。例如，按联结词的优先次序对符号串加括号，得.因为不是一个子公式，因此，可以判断不构成一个公式。作业：课后习题2.34题、5题网络教学平台完成作业1课后小结：命题公式化是数理逻辑的基础，必须准确的用相应连结词表达出来，部分学生对此知识点不熟练，还需要课后练习。第3课

第4课课程章节§2.5命题公式的等值演算课次：3教学目的掌握公式的等值演算方法掌握常用等值式教学重点常用等值式教学难点支配律、同一律等常用等值式教学过程备注课程导入：问题：(1)与.(2)与.真值表怎样列出？两组公式有什么关系？相同么？课程内容：2.5命题公式的等值演算【公式的等值】定义2.13设A，B为两个命题公式，若公式是重言式，则称A与B等值，记作。注意：与的区别，是一个合式公式；而只是一个记号，用来代表“与等值”。不能把当合式公式使用。【公式的等值演算】命题公式的等值演算是命题公式的一种等值变形，即把命题公式从一种形式变换为另一种形式，同时保持公式的真值不变。也就是说，对于给定的一组赋值，公式变形前与变形后的真值是一样的。演算就是一种变形方法。例2.13判断下列公式是否等值：(1)与.(2)与.解：真值表(见表2.13)，可知，(1)中的与不是等值的；而(2)中的与等值。即有.表2.13,和的真值表00011111011010101010011011100000【常用的等值式】若公式与公式等值，即成立，则称为一个等值式。1.【的双重否定律】.2.【的交换律】.3.【的交换律】.容易验证运算满足交换律。4.【的结合律】.5.【的结合律】.6.【的幂等律】.7.【的幂等律】.容易验证运算满足幂等律。8.【对的分配律】;.9.【对的分配律】;.10.【与及的德•摩根律】;.11.【与的吸收律】，.12.【0对的支配律】.13.【1对的支配律】.14.【1对的同一律】.15.【0对的同一律】.16.【排中律】.17.【矛盾律】.18.【蕴涵-析取等值式】.19.【同真-双向蕴涵等值式】.20.【逆否蕴涵等值式】.【置换规则】定理2.1(置换定理，也称置换规则)设是含子公式的一个命题公式，是用公式取代中的一些或所有的之后得到的公式，若，则.证明：参看教材板书。置换规则是推理过程中经常用到的一个规则，这个规则可简单地表述为：若公式中的某个子公式被一个等值的公式所替换，那么，所得到的新公式与原公式等值。例如，用公式替换公式中的，所得到的新公式与原公式等值。【等值演算】利用联结词的运算律、已知的等值式及置换规则进行公式的等值变换，称为等值演算。例2.14用等值演算验证下列等值式：(1).(2).解：(1)蕴涵-析取等值式蕴涵-析取等值式，置换规则结合律德•摩根律，置换规则蕴涵-析取等值式(2)同一律排中律，置换规则分配律例2.15判断下列公式的类型(重言式，矛盾式，可满足式)：(1).(2).(3).解：(1)因为德•摩根律，置换规则德•摩根律，置换规则双重否定律，置换规则分配律，置换规则分配律结合律，置换规则排中律，置换规则1的支配律，置换规则同一律所以，(1)是重言式。(2)排中律，置换规则矛盾律，置换规则0的支配律，置换规则蕴涵-析取等值式置换规则幂等律所以，(2)是矛盾式。(3)蕴涵-析取等值式，置换规则吸收律当的真值为1时，(3)的真值为0，当为0时，(3)的真值为1.所以，(3)是可满足式。例2.16用等值演算解决下面问题：有四人参加百米赛跑，观众甲、乙、丙预测比赛的名次为：甲说：C第一，B第二；乙说：C第二，D第三；丙说：A第二，D第四；比赛结束后发现甲、乙、丙每人的预测都只对一半，试问实际名次如何(假定没有并列者)？解：设分别表示A为第一名、第二名、第三名、第四名；分别表示B为第一名、第二名、第三名、第四名；分别表示C为第一名、第二名、第三名、第四名；分别表示B为第一名、第二名、第三名、第四名。因为没有名次并列者，所以，，，中各有一个真命题。由于每人的预测都只对一半，所以，以下3式成立，；(1)；(2).(3)于是有;巩固练习：内容总结：1.判断两个公式等值的方法有真值表法和等值演算法2.等值演算的公式很重要3.等值演算可以判断公式的类型。注意：不是每一种运算都满足交换律的。联结词就不满足交换律。类似地，实数中的加法运算和乘法运算满足交换律，但减法和除法就不满足交换律。在今后的公式等值演算中，若在合取式中发现有一个合取项等值于0，则可直接用0替换该合取式；若在析取式中发现有一个析取项为1，则可用1替换该析取式。 作业：网络教学平台完成作业1.课后小结：本节内容公式繁多，学生不能快速的掌握，需要多做练习，加以巩固。第5课

课程章节§2.6公式的范式（析取范式）课次：4教学目的掌握范式、析取范式的概念熟悉主析取范式的求解方法了解主席取范式的意义教学重点主析取范式求法教学难点主析取范式求法教学过程备注课程导入：问题：怎样判断两个公式不等值？等值演算的结果不同就是不等值么？课程内容：2.6公式的范式范式是一种正规形式，或标准形式，“范式”对应于英语中的normalform.【简单析取式】定义2.14设是由有限个命题变元或命题变元的否定构成的析取式，则称为简单析取式。，，都是简单析取式，而不是简单析取式。【简单合取式】定义2.15设是由有限个命题变元或命题变元的否定构成的合取式，则称为简单合取式。，，都是简单合取式，而不是简单合取式。定理2.2(1)一个简单析取式是重言式当且仅当它同时含有一个命题变元及其否定；(2)一个简单合取式是矛盾式当且仅当它同时含有一个命题变元及其否定。【析取范式】定义2.16由有限个简单合取式构成的析取式称为析取范式。(简单合取式1)(简单合取式2)…(简单合取式).【合取范式】定义2.17由有限个简单析取式构成的合取式称为合取范式。(简单析取式1)(简单析取式2)…(简单析取式).定理2.3(1)一个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式。(2)一个合取范式是重言式，当且仅当它的每个简单析取式都是重言式。【求公式的析取范式的步骤】：假定公式不含以外的联结词.(1)用同真-双向蕴涵等值式消去联结词：；(2)用蕴涵-析取等值式消去联结词：；(3)用双重否定律消去连续出现的多个联结词：；(4)用德摩根律将括号外的否定联结词内移，直至紧靠命题变项或消去：;.(5)用对的分配律及,的结合律将公式整理为析取范式。【求公式的合取范式的步骤】：以上求公式的析取范式的步骤(1)～(4)完全可用于求公式的合取范式，只需将第(5)步改为：“(5)用对的分配律及,的结合律将公式整理为合取范式。”例2.17求下列公式的合取范式和析取范式：解：(1)求原公式的合取范式：.(2)求原公式的析取范式：.由以上求析取范式和合取范式的步骤不难得到以下范式存在定理。【范式存在定理】定理2.4对于任何一个命题公式，都存在着与之等值的析取范式和合取范式。【公式的极小项】定义2.18设是个互不相同的命题变元，令，则形如的简单合取式，称为由产生的极小项。若是公式中所有互不相同的命题变元，则由产生的极小项称为公式的极小项。例2.18求3个命题变元产生的所有极小项。解：由产生的所有极小项为：，，，，，，，.共8个。【极小项的真值】下面是由个命题变元产生的所有极小项所分别对应的使其真值为1的赋值：，000，001，010，011，100，101，110，111【极小项的编号】【主析取范式】定义2.19设A是含个命题变元的公式，是的一个析取范式，若中每个简单合取式都是极小项，则称是的主析取范式。【析取范式与主析取范式的区别】公式的析取范式要求析取式的每一个析取项都是简单合取式，而的主析取范式要求析取式的每一个析取项都是的极小项；简单合取式可以只含一个命题变元，也可以含多个命题变元，而公式的极小项恰好含有中所有个不同的命题变元。【求公式的主析取范式的步骤】例2.19求的主析取范式。解：所以，的主析取范式为.【公式的主析取范式与真值表之间的关系】【用主析取范式判断两个公式是否等值】当且仅当与有相同的主析取范式。【用主析取范式判断公式的类型】设是任意一个命题公式,则(1)是重言式当且仅当的主析取范式包含的所有极小项。(2)是矛盾式当且仅当的主析取范式不含的任何极小项。(3)是可满足式当且仅当的主析取范式至少包含一个的极小项。巩固练习：内容总结：1.范式是公式的标准形式，主析取范式是唯一的2.主析取范式的简单求法3.主析取范式的应用是一个析取范式；不是析取范式。，，都是合取范式，不是合取范式。 作业：习题2.610、11、12、13、14、15网络教学平台完成作业2.课后小结：主析取范式很重要，其中等值演算法步骤繁多，学生很难掌握，简单求法是两种方法的结合，既应用等值演算又应用到真值表的知识，可以方便求解主析取范式。学生练习时应用该方法较容易，易掌握。第5课课程章节§2.6公式的范式（合取范式）课次：5教学目的熟悉每个命题公式的极大项掌握主合取范式的求法了解主合取范式与主析取范式的区别教学重点极大项主合取范式主合取范式的意义教学难点主合取范式的求法教学过程备注课程导入：问题：1.3个命题变元的极小项有哪些？2.如何求公式的主析取范式？3.主析取范式的意义是什么？课程内容：【公式的极大项】定义2.20设是个不同的命题变元，令，则形如的简单析取式称为由产生的极大项。若是公式中所有互不相同的命题变元，则由产生的极大项称为公式的极大项。例2.20求3个命题变元产生的所有极大项。解：由产生的所有极大项为：，，，，，，，.共8个。【极大项的真值】下面是由个命题变元产生的所有极大项所分别对应的使其真值为0的赋值：，000，001，010，011，100，101，110，111【极大项的编号】由个命题变元产生的所有极大项可分别记为：【主合取范式】定义2.21设A是含个命题变元的公式，是的一个合取范式，若中每个简单析取式都是的极大项，则称是的主合取范式。【合取范式与主合取范式的区别】公式的合取范式要求合取式的每一个合取项都是简单析取式，而的主合取范式要求合取式的每一个合取项都是的极大项；简单析取式可以只含一个命题变元，也可以含多个命题变元。而公式的极大项恰好含有中所有个不同的命题变元。【求公式的主合取范式的步骤】例2.21求的主合取范式。解：.【公式的主合取范式与真值表之间的关系】由公式的真值表写出的主合取范式：设是含个命题变元的公式，从的真值表中找出它的所有真值为0的赋值，这些真值为0的赋值对应的极大项构成的合取式就是该公式的主合取范式。由公式的真值表(表2.6)知，该公式的所有真值为0的赋值为：，，，所以，公式的主合取范式为：或写成：.【公式的主析取范式与主合取范式之间的关系】主析取范式与主合取范式是一个对偶的概念，主析取范式代表公式的真值为1的赋值，而主合取范式代表公式的真值为0的赋值。若已求得公式的主析取范式，则把不出现在主析取范式中的极小项改成极大项，这些极大项构成的合取式就是公式的主合取范式。反之亦然。【用主合取范式判断两个公式是否等值】对于任意两个公式和，当且仅当与有相同的主合取范式。【用主合取范式判断公式的类型】设是任意的含个命题变元的公式，则(1)是重言式当且仅当的主合取范式不含任何的极大项。(2)是矛盾式当且仅当的主合取范式包含所有的极大项。(3)是可满足式当且仅当的主合取范式所包含的的极大项的数目小于个。注意：若是重言式，则的主合取范式不含任何极大项，这时记的主合取范式为1；若是矛盾式，则的主析取范式不含任何极小项，这时记的主析取范式为0.【主范式存在定理】定理2.5任何命题公式都存在与其等值的主析取范式和主合取范式，并且公式的主析取范式和主合取范式是唯一的。巩固练习：内容总结：1.主合取范式与主析取范式正好相反。2.主合取范式的简单求法。3.主合取范式的意义。在公式的真值表、主析取范式和主合取范式中，只要知道其中的一个就可求出另外两个。在例2.21中，原公式的主合取范式为：.据此，可直接写出原公式的主析取范式：. 作业：网络教学平台完成作业1.课后小结：在主析取范式的基础上学习主合取范式就比较容易了，只需区分二者即可。学生掌握较好。第6课第6课PAGEPAGE121教学章节§2.7命题逻辑的推理理论课次：6教学目的掌握命题逻辑的推理规则教学重点常用推理规则教学难点推理规则的证明及应用教学过程备注课程导入：问题：马芳去看电影或去游泳.因为她没去看电影，所以她去游泳了如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草这两个推理正确么？怎样将推理形式化？课程内容：2.7命题逻辑的推理理论【推理】推理是指从前提推出结论的思维过程。前提是事先给定的（或假定的）条件，结论是一个断言，是推理的目标。【命题逻辑中的推理】命题逻辑中的推理是指在命题逻辑系统中从前提推出结论的过程。前提是给定的若干个命题公式；结论是一个命题公式；推理是从前提出发，应用命题逻辑中的推理规则得到结论的过程。【逻辑结论】定义2.22若公式为重言式，则称B是的逻辑结论。【形式证明】定义2.24在证明B是的逻辑结论的形式推理中，形式推理的每一步都产生一个公式，整个推理过程产生一个公式序列，这个公式序列称为(从到B的)一个形式证明。【命题逻辑中常用的推理规则】：(1)前提引入规则：在证明的任何步骤上，都可以引入前提。即随时都可以用已知条件。(2)结论引入规则：在证明的任何步骤上，已证明的结论都可以作为后续证明的前提。(3)置换规则：在证明的任何步骤上，命题公式中的子公式可用与之等值的子公式置换。(4)附加规则：╞.(5)化简规则：╞.(6)合取引入规则：，╞.(7)假言推理规则：，╞B.(8)拒取式规则：，╞.(9)假言三段论规则：，╞.(10)析取三段论规则：，╞.例2.22构造下列推理的形式证明：(1)前提：，，结论：(2)前提：，，，，结论：在证明中不用二难推理规则。eq\o\ac(○,1)前提引入规则eq\o\ac(○,2)eq\o\ac(○,1)置换规则（蕴涵-析取等值式）eq\o\ac(○,3)eq\o\ac(○,2)附加规则eq\o\ac(○,4)eq\o\ac(○,3)置换规则（结合律）eq\o\ac(○,5)前提引入规则eq\o\ac(○,6)eq\o\ac(○,5)置换规则（蕴涵-析取等值式）eq\o\ac(○,7)eq\o\ac(○,6)附加规则eq\o\ac(○,8)eq\o\ac(○,7)置换规则（结合律）eq\o\ac(○,9)eq\o\ac(○,8)置换规则（交换律）eq\o\ac(○,10)eq\o\ac(○,4)eq\o\ac(○,9)合取引入规则eq\o\ac(○,11)eq\o\ac(○,10)置换规则(分配律)eq\o\ac(○,12)eq\o\ac(○,11)置换规则(德•摩根律)eq\o\ac(○,13)eq\o\ac(○,12)置换规则（蕴涵-析取等值式）eq\o\ac(○,14)前提引入规则eq\o\ac(○,15)eq\o\ac(○,13)eq\o\ac(○,14)假言推理规则.(2)eq\o\ac(○,1)前提引入规则eq\o\ac(○,2)前提引入规则eq\o\ac(○,3)eq\o\ac(○,1)eq\o\ac(○,2)拒取式规则eq\o\ac(○,4)前提引入规则eq\o\ac(○,5)eq\o\ac(○,4)eq\o\ac(○,3)假言推理规则eq\o\ac(○,6)eq\o\ac(○,5)置换规则（双重否定律）eq\o\ac(○,7)前提引入规则eq\o\ac(○,8)eq\o\ac(○,6)eq\o\ac(○,7)拒取式规则eq\o\ac(○,9)前提引入规则eq\o\ac(○,10)eq\o\ac(○,8)eq\o\ac(○,9)析取三段论规则【附加前提证明法】要证明从前提推出结论，可以把加到前提中，使新的前提变成，而新结论是.只要证明了由新前提可推出新结论，就证明了由原前提可推出原结论.因为，所以，是重言式当且仅当是重言式。因此，要证明╞，只要证明╞即可。例2.24构造下列推理的形式证明。前提：，，；结论：证明：用附加前提法证明。①前提引入规则②附加前提引入③①②析取三段论规则④前提引入规则⑤③④假言推理规则⑥前提引入规则⑦⑤⑥假言推理规则由附加前提证明法知，题中所给推理得证。巩固练习：内容总结：1.形式证明的方法2.常用推理规则3.自然推理过程和附加前提推理法数学证明可以用文字、数学符号及图表等辅助语言来描述推理过程；而形式证明只能用形式语言（如命题逻辑中的公式等）来描述推理过程。 作业：网络教学平台作业2课后小结：推理是一项有意思的工作，在给定若干前提后，按推理规则推出结论。学生对此部分内容很感兴趣，但推理规则稍有些复杂，学生在课堂上能掌握一部分推理规则。形式推理的过程要求较高，必须明确步骤。第7课教学章节§2.7命题逻辑的推理理论（2）课次：7教学目的了解二难推理规则掌握归谬法教学重点归谬法教学难点二难推理规则教学过程备注课程导入：问题：1.推理规则有哪些？2.上一节学习了哪些推理方法？3.已知前提不够用或者没有突破点怎么办？课程内容：【二难推理规则】二难推理是由两个蕴涵式和一个析取式作为前提，由一个单一公式或一个析取式作为结论构成的推理。具体结构如下：(11)简单构成式二难推理规则：，，╞.(12)简单破坏式二难推理规则：，，╞.(13)复杂构造式二难推理规则：，，╞.(14)复杂破坏式二难推理规则：，，╞.例2.22构造下列推理的形式证明：(1)前提：，，结论：在证明中用二难推理规则。①前提引入规则②前提引入规则③前提引入规则④①②③复杂构造式二难推理规则；二难推理举例：1.真假话与被恨父亲对他那喜欢到处游说的儿子说，“你不要到处游说。如果你说真话，那么富人恨你；如果你说假话，那么穷人恨你。既然游说只会招致大家恨你，你又何苦为之呢?”在这里，父亲劝儿子就使用了一个二难推理，形式是：如果你说真话，那么富人恨你；如果你说假话，那么穷人恨你；或者你说真话，或者你说假话；总之，有人恨你。2.林妹妹致疾《红楼梦》第六十四回载：贾宝玉从林黛玉的丫环雪雁处得知林黛玉在私室内用瓜果私祭时想：“大约必是七月，因为瓜果之节，家家都上秋季的坟，林妹妹有感于心，所以在私室自己奠宗……”，怎么呢?贾宝玉又想：“但我此刻走去，见她伤感，必极力劝解，又怕她烦恼郁结于心；若不去，又恐她过于伤感，无人劝止，两件皆足致疾……”如果我们将贾宝玉的后一段想法稍加简化，那么，就可构成如下一个简单构成式的二难推理：如果我去林妹妹处，足以致疾；如果我不去林妹妹处，也足以致疾，或者我去林妹妹处，或者我不去林妹妹处，总之，皆足以致疾。3.东方朔偷酒东方朔偷饮了汉武帝求得的据说饮了能够不死的酒，汉武帝要杀他，他说：“如果这酒真能使人不死，那么你就杀不死我；如果这酒不能使人不死(你能杀得死我)，那么它就没有什么用处；这酒或者能使人不死，或者不能使人不死；所以你或者杀不死我，或者不必杀我。”这就是一个二难推理。汉武帝认为他说得有理，就放了他。p：这酒使人不死¬p：这酒不能使人不死r：不杀我s：杀不死我前提：p®sØp®rpÚØp结论：rÚs【归谬证明法】要证明╞，只要证明是是矛盾式即可。也就是说，把结论的否定加到前提中进行推理，如果在证明过程中推出矛盾式，则证明了原结论是原前提的逻辑结论。这就是平常所说的反证法。因为所以，是重言式当且仅当是重言式当且仅当是矛盾式。例2.25构造下列推理的形式证明。前提：，，；结论：证明：用归谬法证明。①结论的否定引入②①置换规则（双重否定律）③前提引入规则④②③假言推理规则⑤前提引入规则⑥④⑤拒取式规则⑦前提引入规则⑧⑦化简规则⑨⑥⑧合取引入规则因为是一个矛盾式，由归谬证明法知，题中所给推理得证。【观察法】如果从给定的前提和结论之间看不出明显的联系，则可采用一些较为“笨拙”的方法进行试探性推导。步骤如下：(1)引入所有的前提，对前提中的公式应用“假言推理规则”、“拒取式规则”，“析取三段论规则”，“化简规则”等推理规则从前提中分离出新的公式。(2)观察这些新公式及已有的前提与结论之间有何联系，具体地说，就是观察已有的前提及新导出的公式中是否含有表示结论的公式（包括子公式），或与表示结论的公式（包括子公式）等值的公式，或已有公式与结论之间是否存在某种蕴涵关系。(3)对已导出的新公式及已有的前提多次应用推理规则导出更多的新公式，这样就容易看出前提和结论之间的联系。巩固练习：内容总结：1.二难推理可以作为推理规则的补充2.归谬法作业：习题2.74、6网络教学平台完成作业3课后小结：二难推理规则较复杂，不容易记忆，但可以找出其规律帮助学生记住。归谬法较容易掌握。

第8课教学章节§2.8命题逻辑的归结演绎推理课次：8教学目的熟悉命题逻辑的归结演绎推理教学重点归结演绎推理过程教学难点归结演绎推理过程中子句的分割及归结方法教学过程备注课程导入：问题：1.推理规则有哪些？2.归谬法的关键之处。课程内容：2.8命题逻辑的归结演绎推理【归结演绎推理】在命题逻辑中，有一种推理方法可用算法实现，称为归结演绎推理。下面介绍该算法涉及到的概念及操作步骤。【命题逻辑中的子句】定义2.26由若干个文字组成的析取式称为一个子句。例如，公式是一个子句，而不是子句。【空子句】定义2.27不包含任何文字的子句称为空子句，用表示空子句。下面要做的工作是：把一些子句归结为空子句，由此说明这些子句的合取式是一个矛盾式。再利用前面介绍的归谬法可得到要证明的结论。【互补文字】定义2.28设是一个原子公式，则与称为互补文字。【子句的归结】定义2.29设和是任意的两个子句，如果中的文字与中的文字互补，那么，从和中分别消去和，并将两个子句余下的部分做析取运算，构成一个新子句，这一过程称为对和的一种归结，并称为和的一个归结式，而和称为的亲本子句。定理2.6若是子句和的一个归结式，则是的逻辑结论。【用归结原理证明逻辑结论的步骤】归结原理可用于证明命题逻辑中的一些推理。一般地，命题逻辑中的推理可表示为：给定前提和结论，要证明是的逻辑结论。前面已经介绍过，若用归谬法，只需证明是矛盾式即可。用归结原理证明是矛盾式的步骤如下：(1)分别将和化为合取范式；(2)用逗号代替各合取范式中的合取联结词，分别将和的合取范式表示为子句的形式；(3)把和的所有子句放在一起构成一个子句集；(4)对进行归结，遇到空子句，则断定是不可满足的，证明结束。例2.26证明是，，的逻辑结论。证明：用归结原理。(1)分别将，，和化为合取范式得：，，，；(2)分别将，，和的合取范式写成子句的形式：，，，；(3)构造子句集；(4)对中的子句编号并进行归结：①子句引入②子句引入③子句引入④子句引入⑤子句引入⑥子句引入⑦子句引入⑧①③归结⑨⑥⑧归结由归结原理，结论得证。例2.27证明下列推理是正确的：如果小王来，那么小张或小李至少来一人；如果小张来，则小赵就不来．所以，如果小赵来了，但小李没来，则小王没来．证明：令表示：小王来了；表示：小张来了；表示：小李来了；表示：小赵来了，则题中给出的前提条件可表示为：，；结论为：.下面用归结原理证明从前提可推出结论：(1)分别将，，化为合取范式，得：，，；(2)将合取范式写成子句形式，得：，，，，；(3)构造子句集；(4)对子集进行归结：①子句引入②子句引入③子句引入④子句引入⑤子句引入⑥①⑤归结⑦②③归结⑧⑥⑦归结⑨④⑧归结由归结原理知，推理正确。巩固练习：内容总结：1.归结法其实是一种易于实现的算法2.归结法推理的步骤。空子句实际上指矛盾式 作业：习题2.81、2网络教学平台完成作业3课后小结：归结法在归谬法的基础上较容易掌握，只是过程稍复杂，需要将前提演算为范式，学生在实际应用中一般不选此方法。第10课第9课教学章节第三章谓词逻辑§3.1谓词逻辑概述课次：9教学目的熟悉谓词逻辑的概念了解个体、个体域等概念掌握全称量词、存在量词的表达方法教学重点掌握全称量词、存在量词教学难点掌握全称量词、存在量词的应用教学过程备注课程导入：问题：所有的人都会呼吸有的人会唱歌在前面学习的逻辑中可以表达这两句的含义么？课程内容：3.1谓词逻辑概述【谓词逻辑】谓词逻辑是命题逻辑的扩充，是数理逻辑的一部分。谓词逻辑包含了命题逻辑的全部内容，此外，还包含对命题中个体对象的性质和个体对象之间关系的描述及推理。在谓词逻辑中，简单命题不再是最小的研究单位。简单命题可分解为更小的成分：个体词和谓词。谓词逻辑主要研究命题中涉及到的全体对象与特定对象、部分对象与特定对象及全体对象与部分对象之间的逻辑关系。【研究谓词逻辑的意义】把命题逻辑扩充到谓词逻辑有三方面的意义：增加了表达问题的能力。在谓词逻辑中，可描述命题中的个体的性质及命题之间的一些共同特性。增加了描述问题的范围。在谓词逻辑中，可描述命题中的个体变化的范围。增加了推理能力。在谓词逻辑中，可以做比命题逻辑更多的推理。【个体】个体是一个哲学概念，指可独立存在的对象，类似于集合的元素。在谓词逻辑中，个体是指所要讨论的某个领域中的对象。【全总个体域】在讨论实际应用问题时，如果没有指明个体论域的范围，则默认为全总个体域。所谓全总个体域是一个大集合，该集合包含了谓词逻辑中所涉及到的所有个体。这是为了方便讨论所做的一个约定。【个体常量】个体域中特定的个体对象称为个体常量，通常用(可以带下标)表示。例如，在语句“罗兰是一个大学生”中，“罗兰”是一个个体常量；又如，在语句“格林与比尔是同学”中，“格林”和“比尔”都是个体常量。如果用集合表示一个个体论域，则中的每一个元素都是一个个体常量。【个体变元】在个体论域内取值的变元称为个体变元，通常用可以带下标）表示。例如，对于语句“是一个实数”，令实数集是个体论域，在实数集中取值，则是一个个体变元。又如，在语句“”中，和都是个体变元，和的论域可以有多个，可以是整数集，也可以是有理数集，还可以是实数集。在具体应用时要指明个体变元的论域。【个体词】定义3.1用于描述个体对象的词称为个体词。在谓词逻辑中，个体词是指个体常量、个体变元和项。【谓词】定义3.2用于描述个体对象的性质或个体对象之间的关系的词称为谓词，通常用大写字母（可以带下标）表示。在命题“布朗是一个学生”中，“布朗”是个体词，“…是一个学生”是谓词；在在命题“与是同学”中，和是个体词，“…与…是同学”是谓词。【谓词常项】特定的谓词称为谓词常项。例如，在语句“”中，“…大于…”是一个谓词常项，它表示一种特定的关系。【谓词变元】在谓词集合中取值的变元称为谓词变元。例如，设是一个表示二元关系的谓词，但并没有指定是什么二元关系，即可以代表任何一个二元关系，这时就是一个谓词变元。【一元谓词】表示单个个体的性质的谓词称为一元谓词。在谓词逻辑中，一个个体的性质、特征、状态、处境等特性统称为性质，两个或两个以上的个体之间的联系统称为关系。例如，在语句“5是一个整数”中，“…是整数”就是一个一元谓词。又如，在语句“林肯吃过饭了”中，“…吃过饭了”也是一元谓词。【二元谓词】表示二个个体之间的关系的谓词称为二元谓词。例如，在语句“比尔与马奇是同学”中，“…与…是同学”是一个二元谓词。【三元谓词】表示三个个体之间的关系的谓词称为三元谓词。例如，在语句“武汉位于北京与广州之间”中，“…位于…与…之间”是一个三元谓词。【元谓词】表示个个体之间的关系的谓词称为元谓词。【量词】定义3.3用于描述个体变元量化特征的词称为量词。所谓个体变元的量化是指对个体变元的量进行描述，量化特征是指满足谓词所述条件的个体有多少。谓词逻辑可以描述两种量化特征：一种是论域中的所有个体对象都满足谓词所述条件；另一种是论域中有部分个体对象满足谓词所述条件。所以，在谓词逻辑中有两种量词：全称量词和存在量词。【全称量词】表示个体变元取遍个体论域中的每一个值的量词称为全称量词，用符号加上一个个体变元表示。如等都是全称量词，其中，表示“全称”，读作：“对所有的”，或“对每一个”，而是个体变元。例如，可用带量词的的数学表达式将语句“对所有的实数，都有”写为：，其中，表示“是实数”。注意：符号不能单独使用，其后必须紧跟着一个个体变元。量词作为一个整体看待。【存在量词】表示个体变元在个体论域中取某个值的量词称为存在量词，用符号加上一个个体变元表示。如都是存在量词，其中，表示“存在”，读作：“存在”，或“有这样的”。例如，可用带量词的的数学表达式将语句“有的实数既不大于0，也不小于0”写为：，其中，表示“是实数”。注意：符号不能单独使用，其后必须紧跟着一个个体变元。量词作为一个整体看待。巩固练习：课后习题：内容总结：谓词逻辑的意义量词的概念全称量词和存在量词 作业：网络教学平台完成作业1.课后小结：本节内容较易是谓词逻辑的基本概念，学生掌握较好。第11课

教学章节§3.2谓词公式课次：10教学目的熟悉谓词公式的定义掌握量词的辖域、约束变元、自由变元教学重点辖域、约束变元、自由变元教学难点辖域、约束变元、自由变元的区分教学过程备注课程导入：问题：1.谓词逻辑的意义2.量词的概念3.全称量词和存在量词举例课程内容：3.2谓词公式谓词逻辑是一个形式系统，谓词逻辑中使用的语言是一种形式语言，谓词逻辑中的符号、合式公式、推理规则、证明形式等都有严格的语法规定。例如，原子谓词公式一定是形如的公式。【谓词逻辑中的项】例如，设是个体常量，是个体变元，和是函数，则都是项。【原子谓词公式】定义3.5设是一个元谓词，是项，则构成一个谓词公式，称为原子谓词公式。一个原子谓词公式包含谓词和项两个部分。个体常量、个体变元和项统称为个体词，所以原子谓词公式由两部分构成：谓词和个体词。这两个部分是相互独立的，但两者联合使用才有意义。单独的谓词、单独的个体词、单独的项都不能构成谓词公式，而且原子谓词公式的结构必须写成的形式。【谓词逻辑中的合式公式】定义3.6谓词逻辑中的合式公式定义如下：(1)任何一个原子谓词公式都是合式公式；(2)若A是合式公式，则也是合式公式；(3)若A，B是合式公式，则，，，都是合式公式；(4)若A是合式公式，则，也是合式公式；(5)仅由(1)—(4)在有限步内产生的公式才是合式公式。【量词在公式运算中的优先次序】在谓词公式中，量词和的优先次序是最高的，量词与紧跟其后的公式(或子公式)优先结合。量词的优先次序高于所有的逻辑联结词。逻辑联结词的优先次序与命题逻辑中的优先次序相同。利用量词和逻辑联结词与公式结合的优先次序可以适当省略公式中的一些括号。例如，公式可写成.【公式的量化】在谓词公式前面加上量词(或)得到公式(或)，称为用量词(或)对公式量化。量化是针对某个个体变元进行的。例如，是对中的量化，而不对量化；是对中的量化，而不对量化。的意义是：无论在个体域中取什么值，把的具体值代入中都能使为真；的意义是：无论在个体域中取什么值，把的具体值代入中都能使为真；的意义是：存在个体域中的某个个体，当取值为该个体时，把的具体值代入中能使为真。量化可对整个公式进行，也可对公式中的子公式进行。例如，在公式中，被量词量化。确切地说，是中的变元被量化，而中的变元没有被量化；而且，中和都没有被量化。【量词的辖域】在含有量词的公式中，被某个量词量化的子公式(或整个公式)称为该量词的辖域。例如，在公式中，的辖域是，的辖域是.【约束变元】定义3.7在谓词公式中，出现在量词(或)辖域中的变元称为约束变元。【自由变元】定义3.8不是约束变元的变元称为自由变元。例3.1指出下列公式的约束变元、自由变元及量词的辖域。(1)；(2);(3).解：(1)在公式中，和都是约束变元，的辖域是，的辖域是.(2)在公式中，中的是约束变元，的辖域是；中的和都是自由变元。(3)在公式中，子公式中的和都是约束变元，是自由变元。的辖域是，的辖域是；子公式中的是约束变元，是自由变元。的辖域是.【闭公式】定义3.9设是一个谓词公式，若中没有自由变元，则称为闭公式。例如，是闭公式，而不是闭公式。【闭公式与命题之间的关系】任何一个闭公式都表示一个命题；一个含有自由变元的公式不能表示一个命题。令表示：是实数；表示大于，则公式是一个真命题；公式不表示一个命题；公式表示一个真命题。巩固练习：习题3.21、2内容总结：1.谓词公式的定义2.量词的辖域3.约束变元和自由变元4.闭公式的判断递归定义谓词公式注意量化的范围注意量词的辖域作业：习题3.23课后小结：在谓词逻辑中，量词的辖域、约束变元和自由变元的判断很重要，量词不同的辖域则代表含义不同。内容不难，但需要学生认真细心。教学章节§3.3用谓词公式表示命题§3.4谓词公式的解释课次：11教学目的掌握谓词公式表示命题熟悉谓词公式的解释教学重点谓词公式表示命题时量词的选取公式解释时论域的选取教学难点全称量词与存在量词表示公式时的区别教学过程备注课程导入：问题：1.谓词公式的定义2.量词的辖域3.约束变元和自由变元4.闭公式的意义：任何一个闭公式都表示一个命题；一个含有自由变元的公式不能表示一个命题课程内容：3.3用谓词公式表示命题用谓词公式表示命题的方法，也叫做在谓词逻辑中将命题符号化。【如何确定个体词?】如果选用一元谓词表示命题的谓语，则可确定谓词所描述的那个对象为主要个体对象，其他对象为次要对象【选用量词的基本原则】如果一个命题描述了个体论域中的所有个体，则使用全称量词；如果命题描述个体论域中的部分个体，则使用存在量词；如果命题没有描述个体的范围，则不用量词。例3.2用谓词公式表示下列命题：(1)3是素数。(2)2是奇数。(3)张明和刘浩是同学。(4)李岚是长跑冠军。解：(1)令表示：3；表示：是素数，则原命题可表示为：.(2)令表示：；表示：是奇数，则原命题可表示为：.(3)令表示：张明；表示：刘浩；表示：与是同学，则原命题可表示为：.(4)令表示：李岚；表示：是长跑冠军，则原命题可表示为：.例3.3用谓词公式表示下列命题：(1)2是素数且是偶数。(2)如果杨庆是北京大学的学生，陈明也是北京大学的学生，那么杨庆与陈明是校友。解：(1)令表示：2；表示：是素数；表示：是偶数；则原命题可表示为：，也可以表示为：.(2)令表示：杨庆；表示：陈明；表示：是北京大学的学生；表示：与是校友；则原命题可表示为：.3.用谓词公式表示含量词的命题的方法和步骤：(1)找出命题中的各个不同的量词，确定这些量词的辖域；(2)用谓词公式分别表示各个不同的全称量词及其辖域所描述的命题，具体操作如下：a)选择一个带自由变元的附加谓词公式表示个体对象的变化范围；b)用带自由变元的谓词公式表示去掉量词后的命题；c)用形如的公式表示原命题，其中，是表示个体对象的变化范围的附加谓词公式，是表示去掉量词后的命题的谓词公式；(3)用谓词公式分别表示各个不同的存在量词及其辖域所描述的命题，具体操作如下：a)选择一个带自由变元的附加谓词公式表示个体对象的变化范围；b)用带自由变元的谓词公式表示去掉量词后的命题；c)用形如的公式表示原命题，其中，是表示个体对象的变化范围的附加谓词公式，是表示去掉量词后的命题的谓词公式；(4)用逻辑联结词联结各个子公式。(5)检查所写的谓词公式是否表达了原命题的内容。例3.4用谓词公式表示下列命题：(1)每个计算机系的学生都学离散数学。(2)有人喜欢吃苹果。解：..3.4谓词公式的解释【谓词公式的类型】一个谓词公式可以有多个解释，有的解释使公式为真，有的解释使公式为假。但也有一些公式在任何解释下都为真，而有些公式在任何解释下都为假。根据公式与解释的关系，可以把谓词公式分为三种类型：永真式、矛盾式和可满足式。【永真式】定义3.13若公式在任何解释下均为真，则称为永真式。【矛盾式】定义3.14若公式在任何解释下均为假，则称为矛盾式(或永假式)。【可满足式】定义3.15若(至少)存在一个解释使公式为真，则称为可满足式。例3.9判断下列公式的类型：(1).(2).(3).解：(1)是永真式。(2)是矛盾式。(3)是可满足式。巩固练习：习题3.31、2内容总结：1.利用谓词公式表示命题2.谓词公式的解释3.谓词公式的类型判断注意：全称量词常与蕴涵式公式配合使用，而存在量词常与合取式公式配合使用。(1)解释中给定的非空个体域划定了谓词公式讨论的范围。也就是说，谓词公式只在给定的个体域范围内讨论，不讨论个体域以外的问题。(2)解释中给出的模型是判断命题真假的依据，无论给出的模型是否符合实际情况，都必须按模型的内容进行判定。 容易看出，有了公式的解释就可以根据模型判定公式所表示的命题的真假。这种具有数学结构的解释也称为公式的模型。作业：习题3.36课后小结：本节内容有些复杂，特别是设计个体论域的问题，同一个谓词公式在不同的环境下解释也不同，真值也不同，但有些公式无论怎样解释都是真，有些无论怎样解释都是假，这就是谓词公式类型的判断。学生对此处知识掌握程度一般，还需要进一步练习巩固。第12课

第12课教学章节§3.5谓词公式的等值演算课次：12教学目的熟悉谓词公式等值演算规则教学重点量词变换等值式量词辖域收缩与扩张等值式量词分配等值式教学难点量词辖域收缩与扩张等值式教学过程备注课程导入：问题：(1)兔子比乌龟跑得快．(2)并非所有的兔子比所有的乌龟跑得快．(3)有的兔子比有的乌龟跑得快．以上三个命题如何表示为谓词公式，这三种表述的意义相同么？课程内容：3.5谓词公式的等值演算【谓词公式的等值式】定义3.16设,是两个谓词公式，若是永真式，则称与是等值的，记为.【代换实例】定义3.17设是含命题变元的命题公式，是个谓词公式，在中用()处处代换，所得公式称为的一个代换实例。例如，和都是命题公式的代换实例。定理3.1重言式的所有代换实例都是永真式，矛盾式的所有代换实例都是矛盾式。推论3.1命题逻辑中的所有等值式的代换实例都是谓词逻辑中的等值式，所以命题逻辑中的所有等值演算方法都可在谓词逻辑中使用。【置换规则】设是含子公式的一个谓词公式，是用公式取代中的一些或所有的之后得到的公式，若，则.【约束变元换名规则】设是一个谓词公式，是的子公式，是未在中出现过的个体变元符号，将公式中的换成(即把中的所有都换成)，公式中其余部分不变，换名后所得到的公式记为，则.同样地，设是的子公式，是未在中出现过的个体变元符号，将公式中的换为(即把中的所有都换成)，公式中其余部分不变，换名后所得到的公式记为，则.(1)公式换名的目的是为了能清楚地区分公式中各个子公式是否真正受某个量词的约束，以便在进行逻辑推理或逻辑运算时不会出错.(2)约束变元的换名以量词及其辖域为操作单元，即对公式中的某个量词换名就要对量词及其辖域中出现的所有相同变元都换为同一个新的变元，而辖域以外的所有变元保持不变。(3)要特别注意带嵌套量词公式的换名。例如，可把公式换名为，因为量词的辖域是，所以要把辖域中的所有，包括及中的都要为.【自由变元换名规则】将谓词公式中的某个自由变元处处替换成在中未出现过的个体变元符号，的其