第1章 命题逻辑

1、北京林业大学北京林业大学 理学院理学院教材：教材：1耿素云，屈婉玲，张立昂编著，离散数学，清华大学耿素云，屈婉玲，张立昂编著，离散数学，清华大学出版社出版社, 2008年年3月（第月（第4版）版）2耿素云耿素云,屈婉玲编著屈婉玲编著.离散数学离散数学(修订版修订版).高等教育出版社高等教育出版社, 2004年年参考资料：参考资料： 1 左孝凌编著，离散数学，上海科学技术出版社左孝凌编著，离散数学，上海科学技术出版社学习要求：学习要求：联系方式联系方式: Email: lihongjun_ Tel: 62338357基础楼：基础楼：204204知识结构图知识结构图数理逻辑数理逻辑集合论集合论代数

2、结构代数结构图图 论论离离 散散 数数 学学 命题逻辑命题逻辑命题命题：能判断真假能判断真假而不是可真可假的而不是可真可假的陈述句陈述句。命题的命题的真值真值：命题为命题为真真或者或者假假的判断的判断。真命题真命题：真值为真值为真真的命题的命题。假命题假命题：真值为真值为假假的命题的命题。注：任何命题的真值都是惟一的；注：任何命题的真值都是惟一的；用用“1”表示真，用表示真，用“0”表示假。表示假。例例 1.1 ：判断下列句子哪些是命题：判断下列句子哪些是命题.(1) 是有理数。是有理数。 (2) 2是素数。是素数。(3) XY10。(4) 请把头抬起来！请把头抬起来！(5) 火星上有生物。火

3、星上有生物。(6) 我可以请假吗？我可以请假吗？(7) 这句话是错的。这句话是错的。3假命题假命题真命题真命题不是命题不是命题不是命题不是命题命题命题不是命题不是命题不是命题不是命题复合命题复合命题原子命题原子命题(原子命题原子命题)：不能分解成更简单的命题：不能分解成更简单的命题的命题。的命题。命题标识符命题标识符：用字母用字母p、q、r、s、p1、来表示来表示命题，这些字母称为命题，这些字母称为命题标识符命题标识符。复合命题复合命题：由若干个原子命题用：由若干个原子命题用命题联结词命题联结词、标点符号标点符号联结起来的命题。联结起来的命题。PP10011. 否定否定 符号：符号： P是命题

4、，是命题， P读作读作“非非P”。P真值表为真值表为 2 合取合取 符号：符号：， pq 读作读作“p且且q”，“p合取合取q”。PQP Q000010100111同类关联词语有：既同类关联词语有：既又又，不但，不但而且；虽然而且；虽然但是，但是，P Q的真值表的真值表pqp q 0000111011113 析取析取 符号：符号： p q 读作读作“p或或q”，“p析取析取q”。 p q 真值表真值表同类关联词语有：要么同类关联词语有：要么要么，要么，注：注：“或或”分为分为“相容或相容或”和和 “排斥或排斥或”两种两种.4 蕴含蕴含 符号：符号： ， p q 读作读作“p蕴含蕴含q”，“如果

5、如果P则则q”，“当当p，则，则q”，“p是是q的充分条件的充分条件”。 P Q的真值表的真值表pqp q001011100111同类关联词语同类关联词语：q是是p的必要条件，只有的必要条件，只有才，只要才，只要就，就，除非除非才，才，练习：练习：1） 如果它是如果它是鸟，鸟，就就能飞。能飞。2) 只有只有是鸟，它是鸟，它才才能飞。能飞。3) 除非它除非它是鸟，是鸟，否则它否则它就不能飞。就不能飞。4) 除非明天不下雨，否则我就不去香山除非明天不下雨，否则我就不去香山.5) 我不玩游戏，除非我情绪不稳定我不玩游戏，除非我情绪不稳定.5 等价等价 符号：符号：，p q读作读作“p等价于等价于q”

6、，“ p当且仅当且仅当当q”，“p是是q的充要条件的充要条件”。pqp q001010100111p q的真值表为的真值表为1 晓红和元元是朋友晓红和元元是朋友2 老王或小李中有一人去上海老王或小李中有一人去上海3 除非天下大雨，否则她不在室内运动除非天下大雨，否则她不在室内运动4 不经一事，不长一智不经一事，不长一智p:晓红和元元是朋友晓红和元元是朋友.（简单命题）（简单命题）p:老王去上海，老王去上海，q:小李去上海小李去上海(pq)( pq)p:天下大雨天下大雨 q:她在室内运动她在室内运动pqpq或者或者p:经一事经一事 q:长一智长一智pqpqqp或者或者qpqp命题常项命题常项(命

7、题常元命题常元)：真值惟一确定的命题：真值惟一确定的命题. 记为：记为：p,q,命题变项命题变项(命题变元命题变元)：真值可以变化的陈述句：真值可以变化的陈述句. 记为记为:p,q,如如p: 海子是诗人海子是诗人.q命题变元命题变元命题常元命题常元命题公式命题公式 将将命题常项和命题变项，用逻辑联结命题常项和命题变项，用逻辑联结词和圆括号按照一定的逻辑关系连接起来的符号词和圆括号按照一定的逻辑关系连接起来的符号串称为串称为合式公式合式公式，简称，简称公式公式。命题公式的命题公式的递归定义递归定义如下：如下：1. 单个命题变项（或常项单个命题变项（或常项）是合式公式。）是合式公式。2. 如果如果

8、A是合式公式，则是合式公式，则A是合式公式。是合式公式。3. 如果如果A、B是合式公式，则是合式公式，则AB、AB、AB B、A AB也是合式公式。也是合式公式。当且仅当当且仅当有限有限次运用（次运用（1）（）（2）（）（3）所得到的）所得到的符号串是合式公式。符号串是合式公式。 1 公式的最外层括号可以省略；公式的最外层括号可以省略；2 联结词的优先级：联结词的优先级： 最高；最高； , 其次；其次； ， 最低最低.3 对于优先级相同的联结词，按从左到右对于优先级相同的联结词，按从左到右的顺序运算的顺序运算.命题公式的赋值命题公式的赋值指派（赋值）指派（赋值）：命题公式中出现：命题公式中出现

9、n n个不同的命题变个不同的命题变项项P1Pn ，对这，对这n个命题给定一组真值指定称为个命题给定一组真值指定称为这个公式的一个这个公式的一个指派指派或或赋值赋值或或解释解释。成假赋值成假赋值成真赋值成真赋值若一个公式中出现若一个公式中出现n个不同的命题变项，每个变项个不同的命题变项，每个变项分别可以取成分别可以取成1、0，那么该公式共有个，那么该公式共有个2n不同的指不同的指派派。 真值表真值表将命题公式将命题公式A在所有赋值下取值情况列成表在所有赋值下取值情况列成表试考虑求公式试考虑求公式A的真值表的步骤？的真值表的步骤？例例1 求下列公式的真值表，并求出成真赋值和成假赋值求下列公式的真值

10、表，并求出成真赋值和成假赋值.1) p(rq)2) (pq)(p q)3) p (p(qp)命题公式的类型命题公式的类型永真式永真式（重言式重言式）：公式在）：公式在一切一切赋值下的真值均为赋值下的真值均为真真永假式永假式（矛盾式矛盾式）：公式在）：公式在一切一切赋值下的真值均为赋值下的真值均为假假可满足式可满足式： 如公式如公式不是矛盾式不是矛盾式就是就是可满足式可满足式，即至，即至少存在一个赋值使公式为真少存在一个赋值使公式为真永真式仅可满足式可满足式矛盾式公式1、怎样判定公式的类型？、怎样判定公式的类型？2、怎样求公式的成真赋值和成假赋值？、怎样求公式的成真赋值和成假赋值？3、含有、含有

11、n个命题变元的公式的真值表有多少行？个命题变元的公式的真值表有多少行？4、含、含2、3个命题变元的命题公式至多形成多个命题变元的命题公式至多形成多少个不同的真值表？含少个不同的真值表？含n个命题变元呢？个命题变元呢？1 等值定义等值定义 给定两公式给定两公式A、B，若公式若公式AB B是重言式是重言式，则称，则称A与与B等值，记为等值，记为AB. 说明：说明： 等值与等价不是一回事。等价是命题联结等值与等价不是一回事。等价是命题联结词，是公式，在某些指派下为真，某些指派下词，是公式，在某些指派下为真，某些指派下为假；等值不是逻辑联结词，而是公式关系符，为假；等值不是逻辑联结词，而是公式关系符，

12、A B描述了描述了A ，B两公式之间的关系，两公式之间的关系， 只有只有“成立成立”，“不成立不成立”的区别。的区别。 简单判定简单判定:A与与B的真值表相同的真值表相同.A B 充要条件是充要条件是例例1 判定下列两公式是否等值？判定下列两公式是否等值？1) p 与与 ( P)2) (p q) r 与与 p (q r)常见的等值式常见的等值式1)双重否定律双重否定律 ： ( A)A 2) 幂等律幂等律: A A A, A A A3) 交换律交换律: AB BA, 4) 结合律结合律: (AB)CA(BC)，5) 分配律：分配律： A(BC) (AB)(AC) A (BC) (A B)(A C

13、)6)德德.摩根律摩根律: (A B) A B, (A B) A B7) 吸收律吸收律 : A (A B) A, A(AB) A8) 零律零律 : A 1 1 , A 00 9) 同一律：同一律： A 0 A, A 1 A10) 排中律：排中律： A A 1 11) 否定律：否定律： A A 012) 蕴含等值式：蕴含等值式：AB AB13) 等价等值式：等价等值式：AB (AB)(BA)14) 假言易位：假言易位： AB B A15) 等价否定等值式：等价否定等值式： AB A B16) 归缪论归缪论: (AB) ( A B) A 例例2 用等值演算法验证等值式用等值演算法验证等值式教材教材

14、p1012 例例1.9，1.10，1.111.4 联结词全功能集联结词全功能集 称称F:0,1n0,1为为n元真值函数元真值函数.n元真值函元真值函数数至多可以定义多少个二元联结词？至多可以定义多少个二元联结词？ 与非联结词与非联结词 或非联结词或非联结词 排斥或联结词排斥或联结词一个联结词集合，若对于任何一个公式均可以用该一个联结词集合，若对于任何一个公式均可以用该集合中的联结词来等值比较，就称他为集合中的联结词来等值比较，就称他为全功能联全功能联结词组结词组（功能完备集功能完备集）如如: ， 如果一个联结词的如果一个联结词的功能完备集功能完备集中中不含不含冗余的联结词冗余的联结词，就不再具

15、备这种特性，就称为就不再具备这种特性，就称为极小全功能联结词组极小全功能联结词组（极小的功能完备集极小的功能完备集） 如：如： , , , 1 定义定义 在仅含有联结词在仅含有联结词 , ， ，的命令题公式，的命令题公式A中，中，将将 换成换成 ，将，将 换成换成 ，同时，同时T和和F（既（既0和和1）互相）互相替代，所得公式替代，所得公式A*称为称为A的对偶式。显然的对偶式。显然A与与A*互互为对偶式。为对偶式。例例1 试写出下列命题公式的对偶式试写出下列命题公式的对偶式A：（：（p q） r，A：（：（p q） （p（qs）则则A*为（为（p q） r则则A*为（为（p q） （p（qs）

16、一一 对偶式对偶式 A和和A*是互为对偶式，是互为对偶式，P1，P2 ，Pn是出现在是出现在A和和A*的原子变元，则的原子变元，则 A（P1，Pn） A*（ P1， Pn） A（ P1， Pn） A*（P1，Pn）即公式的否定等值于其变元否定的对偶式。即公式的否定等值于其变元否定的对偶式。例：例：A为为P Q，则，则A*为为P Q，则则 （P Q） PQ 设设A* ，B*分别是分别是A和和B的对偶式，的对偶式，如果如果A B，则，则A* B*。这就是对偶原理。如果证明了一个等值公式，其对这就是对偶原理。如果证明了一个等值公式，其对偶式的等值式同时也成立。可以起到事半功倍的效偶式的等值式同时也成

17、立。可以起到事半功倍的效果。果。例如：例如：A（P Q） （ P （ P Q） B P Q 可以证明可以证明AB而而A的对偶式为的对偶式为A*（P Q） （ P （ P Q）B的对偶式为的对偶式为B* P Q根据对偶原理，则根据对偶原理，则A* B*也成立。也成立。1 文字文字:命题变项及其否定统称作文字。命题变项及其否定统称作文字。2 简单析取式简单析取式 仅由有限个仅由有限个文字文字的的析取析取构成的析构成的析取式称为取式称为简单析取式简单析取式。 简单合取式简单合取式 仅由有限个仅由有限个文字文字的的合取合取构成的合构成的合取式称为取式称为简单合取式简单合取式。 注注：单个文字既是简单析

18、取式，又是简单合取式。单个文字既是简单析取式，又是简单合取式。二二 范式范式例：指出下列式子哪些是简单析取式哪例：指出下列式子哪些是简单析取式哪些是简单合取式？些是简单合取式？1)、P P 2)、 p Q3.P Q R4. P (Q R)5. P Q R S6. P Q R简单析取式简单析取式简单合取式简单合取式简单合取式简单合取式都不是都不是简单合取式简单合取式都不是都不是3 范式的概念范式的概念析取范式析取范式：由有限个：由有限个简单合取式简单合取式的的析取析取构成的析取构成的析取式称为式称为析取范式析取范式。范式范式：析取范式和合取范式统称为析取范式和合取范式统称为范式范式。 一个析取范

19、式是矛盾式当且仅当它的每个简单合一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。取式都是矛盾式。 一个合取范式是重言式当且仅当它的每个简单析一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。取式都是重言式。范式的性质范式的性质合取范式合取范式：由有限个：由有限个简单析取式简单析取式的的合取合取构成的合取构成的合取式称为式称为合取范式。合取范式。4 范式存在定理：范式存在定理：任意一个命题公式均存在一个与之等值的析取范任意一个命题公式均存在一个与之等值的析取范式和合取范式式和合取范式 1、消去联结词：、消去联结词： 和和 2、内移或消去否定号；、内移或消去否定号；3、利用分配律

20、。、利用分配律。注：公式的范式不唯一。注：公式的范式不唯一。求范式的一般步骤求范式的一般步骤：5 主析取范式主析取范式极小项极小项 公式中共有公式中共有n个命题变项个命题变项p1，pn这这n个变项的合取式中，每个变项个变项的合取式中，每个变项pi和其否定和其否定 pi，均，均出现且两者仅出现一个出现且两者仅出现一个，并且按命题变，并且按命题变项的下标排列（字母按字典序列）这样的项的下标排列（字母按字典序列）这样的简单简单合取式合取式称为称为极小项极小项，又称布尔合取。，又称布尔合取。 主析取范式主析取范式 若干个不同的若干个不同的极小项极小项的的析析取式，取式，称为称为主析取范式主析取范式 。

21、定理定理 任何一个命题公式均存在一个与之等值的主任何一个命题公式均存在一个与之等值的主析取范式，而且是唯一的析取范式，而且是唯一的。求主析取范式方法求主析取范式方法 ：1、真值表法真值表法 ；2、等值演算法、等值演算法 ；6 主合取范式主合取范式极大项极大项 公式中共有公式中共有n个命题变项个命题变项P1，Pn这这n个变项的简单个变项的简单析析取式中，每个变项取式中，每个变项Pi或其否定或其否定 Pi，必必出现且两者仅出现出现且两者仅出现一个，并且按命题变项的下一个，并且按命题变项的下标排列（字母按字典序列）这样的简单析取式称标排列（字母按字典序列）这样的简单析取式称为为极大项极大项。 主合取

22、范式主合取范式 若干个不同的极大项的合取式，称为主若干个不同的极大项的合取式，称为主合取范式合取范式定理定理5：任何一个命题公式均存在一个与之等值的任何一个命题公式均存在一个与之等值的主合取范式，而且是唯一的。主合取范式，而且是唯一的。求主合取范式的方法：求主合取范式的方法：1、等值演算法；、等值演算法；2、真值表法；、真值表法；3、利用主析取范式来得出主合取范式、利用主析取范式来得出主合取范式。 主范式有何作用？主范式有何作用？ 永真式、永假式的主析取和主合取范永真式、永假式的主析取和主合取范式有何特点？式有何特点？例例1 奥运会短跑比赛现场，三位观众预测比赛结果：奥运会短跑比赛现场，三位观

23、众预测比赛结果：甲：甲：“美国第一，中国第三美国第一，中国第三.”乙：乙：“日本第一，美国第三日本第一，美国第三.”丙：丙：“中国第一，美国第二中国第一，美国第二.”比赛结束，三位观众各猜对了一半，并且没有并列名次比赛结束，三位观众各猜对了一半，并且没有并列名次.问：中问：中国、美国、日本的各排名第几？国、美国、日本的各排名第几？设设z1:中国第一中国第一;z2 :中国第三；中国第三；r1:日本第一；日本第一； m1:美国第一；美国第一；m2:美国第二；美国第二； m3:美国第三美国第三.131 zm131 mr121 mz131 zm131 mr121 mz)(131111mrmmm)()(

24、3111mmrm00013z1021mz从而因此，比赛结果为日本第一，美国第二，中国第因此，比赛结果为日本第一，美国第二，中国第三三.某班欲派李光，王明，张正，刘大，赵五去某班欲派李光，王明，张正，刘大，赵五去西客站接新生。派人方案满足下列条件：西客站接新生。派人方案满足下列条件：(1) 若李光去，则王明也去若李光去，则王明也去.(2) 刘大和赵五中必有一人去刘大和赵五中必有一人去.(3) 王明和张正两人中恰有一人去；王明和张正两人中恰有一人去；(4) 张正和刘大两人同去或者同不去；张正和刘大两人同去或者同不去；(5) 若赵五去，则李光和王明也同去若赵五去，则李光和王明也同去. p1 :李光去

25、李光去; p2 :王明去；王明去； p3 :张正去；张正去； p4 :刘大去刘大去 p5 :赵五去赵五去.21pp 54pp 2323()()pppp 43pp 215ppp)(21pp )(54pp 2323()()pppp )(43pp )(215ppp)(54321ppppp)(54321ppppp因此，选派方案为因此，选派方案为方案一：李光，王明，赵五方案一：李光，王明，赵五方案二：张正，刘大方案二：张正，刘大1.6 命题逻辑的推理理论命题逻辑的推理理论推理正确推理正确 设设A1、A2、Ak，B是命题公式，如果是命题公式，如果（A1 A2 Ak）B是重言式是重言式，则称则称B是是前提集

26、合前提集合 A1、A2、Ak 的有效结论（或称逻辑结论），或称由的有效结论（或称逻辑结论），或称由 A1、A2、Ak 推出结论推出结论B的推理正确。的推理正确。判断推理正确与否的方法有以下几种判断推理正确与否的方法有以下几种：记作（记作（A1 A2 Ak）B 或或A1 , A2, , Ak B B 1、真值表法；、真值表法； 2、等值演算法；、等值演算法；3、主析取范式法；、主析取范式法；推理示例（推理示例（1）例例1 判断下面的推理是否正确：判断下面的推理是否正确： 若若a能被能被4整除，整除，则则a能被能被2整除。整除。a能被能被2整除，所以整除，所以a能被能被4整除。整除。解：设解：设p

27、: a能被能被4整除；整除；q: a能被能被2整除。整除。真值表法（略）真值表法（略）等值演算法得等值演算法得( (pq)q)p qp所以前提：所以前提：pq, q. 结论：结论：p.推理的形式结构：推理的形式结构：p q, q p或者或者(p q)q p (p q)q p学习一种新的办法学习一种新的办法构造证明。构造证明。9条推理定律条推理定律I 1： A AB 附加附加 I 2： A B A 化简化简I 3： A （AB） B 假言推理假言推理 I 4：（：（AB） B A 拒取式拒取式 I 5：（A B） B A 析取三段论析取三段论 I 6：（：（ AB) (BC) (AC) 假言三段论假言三段论 I 7：( AB)(B C) (A C) 等价三段论等价三段论 I 8：(A B) (C D) ( AC) (BD) 构造性二难构造性二难 I 9：(A B) (C D) (BD) (AC) 破坏性二难破坏性二难注：前面所学的等值式（见等值演算一节）都可以用。注：前面所学的等值式（见等值演算一节）都可以用。构造证明的推理规则构造证明的推理规则1、前提引入规则前提引入规则：任何步骤都可引入前提；任何步骤都可引入前提；2、结论引入规则结论引入规则：得到的结论可以作为后续证得到的结论可以作为后续证明的前提，加以引用；明的前提，加以引