《遵义师范学院《离散数学》课件-第1章 命题逻辑》由会员分享，可在线阅读，更多相关《遵义师范学院《离散数学》课件-第1章 命题逻辑（127页珍藏版）》请在金锄头文库上搜索。
1、内容：内容：命题，逻辑联结词，命题符号化(1)掌握命题概念(2)掌握联结词含义及真值表(3)掌握命题符号化方法 重点：重点：第一章命题逻辑第一节 命题与逻辑联结词命题与逻辑联结词遵义师范学院离散数学一、命题的概念一、命题的概念 命题：能判断真假的陈述句。注：(1)命题必须是一个完整的陈述句（2）命题的真值具有唯一性，确定性（3）真值的唯一性并不一定要求现在就能判断出命题的真假，要是在将来某时候能判断出真假也行，真值是否唯一与是否知道其真值是两回事真值真（记为T或1）假（记为F或0）例例1、判断下列语句中哪些是命题（1）人的血液是白色的（2）x+y5（3）你的大学英语四级考试通过了吗？（4）明年
2、六一儿童节是晴天（5）2+3=5（6）地球之外的星球上也有人类（7）请讲普通话！（8）很多人喜欢中央3台的星光大道节目（9）12是素数（10）九寨沟的风景真是美丽啊！判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一。表示。命题常项，命题变项均用二、逻辑联结词。二、逻辑联结词。这五种常用的联结词有命题简单命题（不能再分解成更简单的命题）复合命题（由简单命题用联接词联接而成的命题）真值表 1、“非”称为 的否定式，记作例如：11是素数；：11不是素数取值1，取值0。真值表 2、“并且”称为的合取式，记作。在例1（2）中，设 表示“2是素数”，表示“2是偶数”，则表示“2是素数和偶数”
3、，由于 的真值都是1，所以 的真值也是1例例2、将下列命题符号化（1）王教授不仅研究经济学而且研究管理学（2）王教授虽然研究经济学但不研究管理学（3）王教授研究经济学及管理学（4）王教授和李教授是大学校友解：解：设：王教授研究经济学，：王教授研究管理学，则（1）（2）（3）分别符号化为 ,.（4）是简单命题，符号化为：王教授和李教授是大学校友 真值表 3、“或者”称的析取式，记作。例如，：小明学过英语，：小明学过日语，则小明学过英语或日语可表示为真值表：4、“如果 那么”称的蕴涵式，记作其中为前件，为后件。(1)如果天不下雨，我就骑车上班。(2)只要天不下雨，我就骑车上班。(3)只有天不下雨，
4、我才骑车上班。(4)除非天下雨，否则我就骑车上班。(5)如果天下雨，我就不骑车上班。(或 )例例3、：天下雨，：我骑车上班。真值表：5、“当且仅当”称的等价式，记作。是的充要条件，也是的充要条件。例例4、：，：3是奇数(1)当且仅当3是奇数。(2)当且仅当3不是奇数。(3)当且仅当3是奇数。(4)当且仅当3不是奇数。6、逻辑联结词与自然语言中联结词的关系。否定不是，没有，非，不。合取并且，同时，和，既又，不但而且，虽然但是。析取或者，或许，可能。蕴涵若则，假如那么，既然那就，倘若就。等价当且仅当，充分必要，相同，一样。7、运算顺序 逻辑联结词也称逻辑运算符，规定优先级的顺，若有括号时，先进行括
5、号序为内运算。例如：三、命题符号化。三、命题符号化。步骤：(1)找出各简单命题，分别符号化。(2)找出各联结词，把简单命题逐个联结起来。例例5、将下列命题符号化（1）小王不富有但很快乐（2）小王现在乘坐公共汽车或坐飞机（3）如果明天有雾，他就不能坐轮船而是乘车过江（4）这个材料有趣，意味着这些习题很难，并且反之亦然（5）如果这个材料无趣或者习题不是很难，那么这门课程就不会让人喜欢（6）这门课程会让人喜欢，除非这个材料无趣并且习题很难解解：（1）设：小王富有，：小王很快乐，符号化为（2）设 ：小王现在乘坐公共汽车，：小王现在坐飞机，符号化为（3）设：明天有雾，：他坐轮船过江，：他乘车过江，符号化
6、为对于（4）、（5）、（6），设 ：这个材料有趣，：这些习题很难，：这门课程会让人喜欢，则符号化分别为，内容：内容：命题公式，重言式，矛盾式，可满足公式。重点：重点：(1)掌握命题公式的定义及公式的真值表。(2)掌握重言式和矛盾式的定义及使用真 值表进行判断。第二节第二节 命题公式与解释命题公式与解释一、命题公式一、命题公式 通俗地说，命题公式是由命题常项，命题变项，联结词，括号等组成的字符串。规定：公式中最外层的括号，及的括号可省略。例例1、判断以下字符串中哪些是命题公式。(1)(2)(3)(4)(5)(6)解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。二、，如公式，110(
7、按字典序)为的成假赋值，111，011，010等是的成真赋值。个命题变项的命题公式，共有含组不同赋值。公式的解释或赋值赋值成真赋值（使A为真的赋值）成假赋值（使A为假的赋值）三、真值表。的真值表指在所有赋值之下取值列成的表。构造命题公式的真值表的具体步骤如下：（1）找出公式 中包含的所有命题变项 （若无下角标就按字典顺序给出），列出所有可能的赋值（个）；（2）按照优先级的运算顺序：，进行运算如果出现括号，先进行括号中的运算，直到计算出公式的真值例例2、求下列命题公式的真值表。(1)解解：(2)解：解：四、命题公式的分类四、命题公式的分类 2、判定方法:真值表法。1、定义：设 是任意一个命题公式
8、（1）若 在它的各种赋值下取值均为假，则称为永假式或矛盾式；（2）若 在它的各种赋值下取值均为真，则称为永真式或重言式；（3）若 至少存在一组赋值是成真赋值，则称为可满足式；例例3、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)解：解：列出各题真值表如下(步骤简略)(1)、(2)、(5)、(6)、(9)为重言式；(3)、(8)为矛盾式；(4)、(7)、(10)及以上的重言式均为可满足式。内容：内容：等值关系，24个重要等值式，等值演算。重点：重点：(1)掌握两公式等值的定义。(2)掌握24个重要等值式，并能利用
9、其进行等值演算。第三节第三节 公式的等值演算公式的等值演算一、两命题公式间的等值关系。一、两命题公式间的等值关系。2、判定。1、定义：设为两命题公式，若等价式是重言式，则称与 是等值的，记作。是否重言式。是否等值，即判断判断两公式(1)，解：解：作真值表如下：例例1、判断两公式是否等值。解解：作真值表如下：(2)，二、重要等值式。二、重要等值式。2、结合律，3、分配律，1、交换律，4、德摩根律，6、吸收律，5、等幂律，7、零律，8、同一律，9、互否律(矛盾律)(排中律)，11、蕴涵等值式 12、等价等值式 13、假言易位 14、等价否定等值式 15、归谬论 10、双重否定律 三、等值演算。三、
10、等值演算。例例2、验证下列等值式。置换定理：如果。，则（1）（2）（3）（1）解：蕴涵等值式分配律 蕴涵等值式（2）蕴涵等值式 蕴涵等值式德摩根律双重否定律与分配律 蕴涵等值式解：（3）解：蕴涵等值式等价等值式 蕴涵等值式德 摩 根律交换律 分配律 排中律与同一律 分配律 排中律与同一律 考虑问题:能否利用等值式来化简，或判断公式的类型(重言，矛盾，可满足)。判断一个公式是否重言式，矛盾式，可满足式，或者判断两个命题公式是否等值。有两种方法，即真值表法真值表法和等值演算法等值演算法。例3、用两种方法证明:证法一 用真值表法 由最后两列真值完全相同，于是命题成立。证法二 用等值式法 蕴涵等值式
11、双重否定律 交换律 结合律 吸收律 例4、将下图所示的逻辑电路简化 解：将上述逻辑电路写成命题公式：利用等值式将公式化简 分配律 结合律 等幂律 所以，该电路可简化为下图：内容：内容：联结词的全功能集，极小功能集,对偶原理。了解：了解：全功能集，极小功能集。第四节第四节 联结词全功能集与对偶原理联结词全功能集与对偶原理重点：重点：掌握对偶式，对偶原理。真值表：由定义知：一、联结词一、联结词。记作1、“的排斥或(异或)，之间恰有一个成立”称。真值表：的与非式，记作并且2、“的否定”称。真值表：的或非式，记作3、“或者 的否定”称。二、全功能集，极小功能集。二、全功能集，极小功能集。全功能集全功能
12、集：若干个联结词的集合，其余的联结词均可由它们表示。最小全功能集最小全功能集：不含冗余联结词的全功能集。例如：等都是全功能集。等都是极小全功能集。三、对偶原理。三、对偶原理。1、对偶式。定义：设公式仅含联结词，则将分别用替代，所得的公式称的对偶式。与互为对偶式。例如：与，与，与2、对偶原理。所以可得：若。，则例如：已知(分配律)，与均为相互对偶式，且，与内容：内容：命题公式的范式。(2)掌握析取范式和合取范式的定义和求法步骤。(3)掌握极小项，极大项的概念及主范式的求法。第五节第五节 命题公式的范式命题公式的范式重点重点：（1）掌握简单合取式和简单析取式的概念。一、简单析取式，简单合取式。简单
13、析取式简单析取式:由有限个命题变项或其否定构成的析取式简单合取式简单合取式:由有限个命题变项或其否定构成的合取式例如：等都是简单析取式。，例如：等都是简单合取式。，二、析取范式，合取范式。例如：为析取范式，为合取范式。定义：定义：由有限个简单合取式构成的析取式称作析取范式析取范式。由有限个简单析取式构成的合取式称作合取范式合取范式。例如：为析取范式，显然，为合取范式，为合取范式。例如：为析取范式。范式存在定理：范式存在定理：任一命题公式都存在与之等值的析取范式和合取范式。求范式步骤：求范式步骤：(2)否定消去或内移。(3)利用分配律。(1)消去联结词 解：解：原式 消去 内移 消去 上式即析取
14、范式 例例1、求公式的析取范式。分配律 对(分配)解：解：原式 消去 内移 消去 上式即合取范式 例例2、求公式的合取范式。分配律(分配)对三、主范式。三、主范式。1、极小项，极大项。定义：定义：设命题公式含这个命题变项，则和分别称为极小项极小项和极大项极大项，其中为或。都是极小项，都是极大项，例如，对只含变项的命题公式中，但不是极小项。但不是极大项。极大项，极小项。下面分别讨论，即个命题变项的极小项 成真赋值(二进制数)000 001 010 011 100 101 110 111 对应十进制数 01234567记法 极大项 成假赋值(二进制数)000 001 010 011 1001011
15、10111 对应十进制数 01234567记法 2、主析取范式，主合取范式。主析取范式主析取范式每个简单合取式都是极小项的析取范式。主合取范式主合取范式每个简单析取式都是极大项的合取范式。两种求法，等值式法等值式法和真值表法真值表法。定理：定理：任何命题公式的主析取范式、主合取范式 都存在且都是唯一的。步骤：(3)消去重复的及永假项。2.1、利用等值式法求命题公式的主析取范式。(1)求，的析取范式(2)利用 补充变元，(4)按角码顺序排序，并用“”表示。解：解：由例1的析取范式为 例例3、求公式的主析取范式。(吸收律)步骤：(3)求每个成真赋值对应的十进制数，即极小项的角码，将极小项按序析取即
16、成。2.2、利用真值表求命题公式的主析取范式。(1)列出的真值表，(2)找出的所有成真赋值，解：解：(1)列真值表 例例4、用真值表求的主析取范式。(2)的成真赋值有010，100，101，110，111(3)对应的十进制数为2，4，5，6，7 所以的主析取范式为 步骤：(3)消去重复的及永真项；2.3、利用等值式法求命题公式的主合取范式。(1)求；的合取范式(2)利用 补充变元；(4)按角码顺序排序，并用符号“”表示；如。记为解：解：由例2，合取范式 例例4、求公式的主合取范式。2.4、利用真值表求命题公式的主合取范式。步骤：(3)求每个成假赋值对应的十进制数，即极大项的角码，将极大项按序合取即成。(1)列出的真值表，(2)找出的所有成假赋值，例例5、用真值表求的主合取范式。解：解：(1)由例3知真值表，的(3)对应的十进制数为0，1，3。(2)的成假赋值有000，001，011，所以的主合取范式：思考：思考：命题公式间有什么联系，能否通过其中一个求另一个？(观察例3，例5)的主合取范式，主析取范式由例3、例5知：2.5、已知命题公式的主析取范式(主合取范式)，求主合取范式(主析取范
