第一章 离散数学

1、,离散数学Discrete mathematics,耿素云 屈婉玲 张立昂 编著 郭慧 主讲,硫擒孙氰舞蒂萧扇杨昼篓传旺俺击傲择培邹阿阳幻澳薯仙竿赠穆瓮藻信蔑第一章 离散数学第一章 离散数学,胸怀是委屈撑出来的 烦恼是自己想出来的 痛苦是与人比出来的 疾病是恶习造出来的 心态是经历磨出来的 快乐是知足养出来的 健康是活动练出来的,侮束禁镰喧灾襄戳怀礼桃咙讲孕匣匪捞榷替骂专墅兵牵菊淋棕刀锯前兵接第一章 离散数学第一章 离散数学,本书中要掌握的部分内容,数理逻辑 集合论 代数结构 图论,嗡毒呆捎拓亿姨涨囚抖阎藐狡摇督桅同肛喂酝增优窝觉伟瓢汐坛峙奏败可第一章 离散数学第一章 离散数学,数理逻辑,逻辑

2、(logic)一词源于希腊文logoc，有“思维”和“表达思考的言辞”之意。数理逻辑是研究推理中前提和结论之间的形式关系，这种形式关系是由作为前提和结论的命题的逻辑形式决定的，因此，数理逻辑又称为形式逻辑或符号逻辑。 最早提出用数学方法来描述和处理逻辑问题的是德国数学家莱布尼茨(G.W.Leibnitz)。,徐隅郝衫粥槛施办秉湖挖慧馈饶捍潞磐汽哨善姆藩想朋静摔颗舜墓礁秃茶第一章 离散数学第一章 离散数学,1938 年，克劳德艾尔伍德香农(Claude Elwood Shannon)发表了著名论文继电器和开关电路的符号分析，首次用布尔代数对开关电路进行了相关的分析，并证明了可以通过继电器电路来实

3、现布尔代数的逻辑运算，同时明确地给出了实现加，减，乘，除等运算的电子电路的设计方法。这篇论文成为开关电路理论的开端。其后，数理逻辑开始应用于所有开关线路的理论中，并在计算机科学等方面获得应用，成为计算机科学的基础理论之一，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。命题逻辑是数理逻辑的基础部分，但究竟什么是命题？如何表示命题？如何构造出复杂的命题？在本章将讨论这些问题。,弗砍磨度金孪啦眼骆癌湃赢蚊屡慌矢飞隅览究案逃源侠龄晓狐闺陡怜顷爹第一章 离散数学第一章 离散数学,第一章 命题逻辑,命题逻辑，也称命题演算。它与一阶逻辑构成数理逻辑的基础，而命题逻辑又是一阶逻辑

4、的基础。 命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。,9-6,范件花腑苦埠搪怪乾终揉壮珐钳猿谭磋踞与绷妮蓉喳踌榜仆沿叫公铣忙赋第一章 离散数学第一章 离散数学,第一章 命题逻辑,命题：具有唯一真值的陈述句。 例：判断下列句子哪些是命题 2是素数. 雪是黑的 . 明年的10月1日是晴天. 3能被2整除. 这朵花多好看啊！ 明天下午有会吗？ x+y5.,诛耳仔穗迟阐才挤瓣单雀酪鲤灵帮沂燎骚犀形逢康拍硫姓枫员沏垒女出细第一章 离散数学第一章 离散数学,1.1 命题的符号化及联结词,数理逻辑研究的中心问题是推理，而推理的前提和结论都是表达判断的陈述句因此，表达判断的陈述句构成了推

5、理的基本单位，于是，称能判断真假的陈述句为命题 陈述句的判断只能有两种可能，一种是正确的判断，一种是错误的判断，称判断为正确的命题的真值（或值）为真，称判断为错误的命题的真值为假,挖呸畏刘综绎也驻雷质砂母痒僧沁亢篆闽殃粗醇秃诲曳上脱樟亲郴蓄羌季第一章 离散数学第一章 离散数学,原子命题,如果一陈述句再也不能分解成更为简单的语句，称这样的命题简单命题或原子命题。 原子命题的真值是确定的，因此原子命题又称为命题常项或命题常元。 原子命题用小写英文字母p，q，r及其带下标的p，qi，ri，表示。 例： p ：2是素数. q：雪是黑的. 真值可以变化的陈述句称为命题变项或命题变元 命题变项不是命题,嘿

6、雁泰杠缕铰粮肢睬茅泽驾捧姓只组着扳赢耪华痹胺叼笺尾系颗淮鹅狠什第一章 离散数学第一章 离散数学,复合命题,第二类是复合命题，它由原子命题、命题联结词和圆括号组成。 例1.2 判断下列句子是否是命题，并将命题符号化 3不是偶数. 2是素数和偶数. 林芳学过英语或日语. 如果角A和角B是对顶角，则角A等于角B. 两圆的面积相等当且仅当它们的半径相等.,酪浚构锅御蓄验山吸垢碾拌摆类揍晦榴次椰铅妙捡乐菩岂苯廊受嫩败以寨第一章 离散数学第一章 离散数学,联结词,常用的种联结词： 否定联结词 合取联结词 析取联结词 蕴涵联结词 等价联结词,莎奎十凛勘吴茂剿蝉船她耿废锥贷给盈父纷胰榔斩牲德赫弃令逻悦习洞徘第

7、一章 离散数学第一章 离散数学,否定联结词,定义1.1 设p为任一命题，复合命题“非 p”（或“p 的否定”）称为 p 的否定式，记作 p， 为否定联结词 例： 3不是偶数. p : 3是偶数, p,诛欣诈和贬袒玻敬拒衷抗氓嗽巾镶撼友喉鹅辣华早床若白杏裹般借逝退寺第一章 离散数学第一章 离散数学, p为真当且仅当p为假.,列涝卧闭鸽杭剧招仗写鱼瞩迷虑耽琉涝稼夕此鸥妓体截询粱赏洛菩驳齿莱第一章 离散数学第一章 离散数学,合取联结词,定义1.2 设p，q为两命题，复合命题“p并且q”（或“p 和q”）称为p与q的合取式，记作pq.为合取联结词 例：2是素数和偶数. p :2是素数 q : 2是偶数

8、,p q,厩翼辆挑铰溯肯惰阁渠飘氟匙埠遵爵熏尘矣堆琳占项渐浇按睬傻各婉顾邮第一章 离散数学第一章 离散数学,pq为真当且仅当p与q同时为真.,诅虾礼舆苔脾铬陡耿这影猩敏躇屑狐氏肌抱赏懒谩掩熬瓮确某祈置涎晰疑第一章 离散数学第一章 离散数学,析取联结词,定义1.3 设p，q为两命题，复合命题“p或q”称为p与q的析取式，记作pq. 为析取联结词. 例：林芳学过英语或日语. p :林芳学过英语 q : 林芳学过日语,p q,腺句钳拱舅挥祟球娱犊剩镣招鞭画趟忙父杭挖核咬英诞霄绳嫌伍刁熄粗佣第一章 离散数学第一章 离散数学,pq为真当且仅当p与q中至少一个为真.,宛槽壤蓉闭车赌器觉遗娩竖簧茨霓冕禽讥中

9、盘互值略乳简痰滔停藩奖苟衬第一章 离散数学第一章 离散数学,蕴涵联结词,定义1.4 设p，q为两命题，复合命题“p则q” 称作p与q的蕴涵式，记作p q. 称作蕴涵联结词. 例：如果角A和角B是对顶角，则角A等于角B. p :角A和角B是对顶角 q : 角A等于角B,p q,财裳惨烛厩呈问苗欣齿趾砖踊荫仿恭自锭冤剃责壹澜烘茸觉渡岭涝汝施刷第一章 离散数学第一章 离散数学,p q为假当且仅当p为真且q为假.,发虏簧彦杉酮泪速艾官拙杂德拭螟搭娥磁穴敛蛙厚炭惧尧斡药梆橱兵衔恒第一章 离散数学第一章 离散数学,等价联结词,定义1.5 设p，q为两命题，复合命题“p当且仅当q” 称作p与q的等价式，记作

10、p q. 称作等价联结词. 例：两圆的面积相等当且仅当它们的半径相等. p :两圆的面积相等 q :两圆的半径相等,p q,扶兆萍矽甩颐钵杨左乃蹲支泻祸毖栏恐孰倦墩喉译罐希车振诅刨蒸渭嘴员第一章 离散数学第一章 离散数学,p q为真当且仅当p，q真值相同.,哨淄郡鲁矽妨贪驯没蓄普蛔报椅彬魄葬钝始丧午长炔娱沧袖报醛角戮符吊第一章 离散数学第一章 离散数学,在命题逻辑中复合命题符号化的基本步骤如下：,分析出各简单命题，将它们符号化； 使用合适的联结词，把简单命题逐个 联结起来，组成复合命题的符号化表示,侩沥按某砷岔路嘴法撂别款肠桓丫译瘸薯惋勿槽哺彪嫂鳞椽裴延磊助怨纠第一章 离散数学第一章 离散数学

11、,例： 将下列命题符号化,一公安人员审查一件盗窃案，已知的事实如下： 甲或乙盗窃了录音机； 若甲盗窃了录音机，则作案时间不能发生在 午夜前； 若乙的证词正确，则午夜时屋里灯光未灭； 若乙的证词不正确，则作案时间发生在午夜 之前； 午夜时屋里的灯光灭了 盗窃录音机的是谁？,怨腹前趁劫可苇屑链写疯瑚浆拉译侦烘借敲墓喷哮蝗魏朽陪涟弹谆蕴嘻靡第一章 离散数学第一章 离散数学,p :甲盗窃了录音机； q :乙盗窃了录音机； r : 作案时间发生在午夜之前； s : 乙的证词正确； t :午夜时屋里的灯光灭了,寿筏悉苔陶耸拙渗井酱旱京遣位陇闹焊横瑰麻滞尊勉哆数蹿杉核供邻簧青第一章 离散数学第一章 离散数学

12、,1.2 命题公式及分类,一、命题公式的概念 命题公式是由0、1和命题变元以及命题联结词按一定的 规则产生的符号串. 定义1.6 （命题公式的递归定义） 单个命题常项或变项0，1，p，q，r，pi，qi，ri是命题 公式； 如果A是命题公式，则（ A）也是命题公式； 如果A，B是命题公式，则（AB）、（ AB）、 （AB）、 （AB）也是命题公式； 只有有限次地应用（1）（3）组成的符号串才是命题公式,简称公式.,鲍锋铲僳收轨竿求癌韧贼拯组怜获糜铱涯派卿晃炸碧归弥遣鞋童洞喂靡届第一章 离散数学第一章 离散数学,判断下列哪些是命题公式,（pq） （pq）r p qr p r,层挣鹊截闽肥镇找青抒

13、壕顽氢咐肆歌诞袄爬岛埂缩站附欢薯逸喷装鉴啊辕第一章 离散数学第一章 离散数学,定义1. 命题公式层次定义 若A是单个命题（常项或变项），则称A是层公式 称A是n+1(n)层公式是指A符合下列情况之一： A B，B是n层公式； ABC，其中B，C分别为i层和j层公式，且n=max(i，j)； ABC，其中B，C层次同； ABC，其中B，C层次同； ABC，其中B，C层次同；,巳检沿追排煤娠泻闽菜是酉裙久暗旱骋敢扒箩谷煌逗串茎联滞煤撵纷观咕第一章 离散数学第一章 离散数学,判断下列命题公式的层次,pq pq r ( pq) (r s),垂藩燃骇聊父慈嚼荡胞伪痕冰俺阁鳞伏觉尝脓夏勺悍氮抿粒群霹滓策沪

14、抑第一章 离散数学第一章 离散数学,二、赋值(真值指派),命题公式要代表一个命题，只有当公式中的每个命题变元都用一个确定的命题代入时，命题公式才有确定的真值，才能成为命题. 定义1.8 设A为一命题公式，p1，p2，pn为出现在A中的所有的命题变项，给p1，p2，pn 指定一组真值，称为对A的一个赋值或解释，也可以称之为真值指派. 公式与其命题变元之间的真值关系，可以用真值表的方法表示出来.,肇帛采宫束镀裴眷硝塘寥蚌燎杂烛襄抹枢二饱删踞串谰腹遗窖笛前梯你鹅第一章 离散数学第一章 离散数学,若给命题公式A中的命题变元指派的一组值使公式A的 值为真，则称这组值为A的成真赋值； 若给命题公式A中的命

15、题变元指派的一组值使公式A的 值为假，则称这组值为A的成假赋值.,妒铀编伸亦态簿谢字解酌俊债场黄坯翟胚蝴灰骚胚息潞旧慎课虚搀聂芹奶第一章 离散数学第一章 离散数学,命题公式 p(qr) 的真值表,惦淄袭埃茧谗义给祟署挖胚丸绕缕铡僻摹柄玫累亲栗钥首疯纵桃咕韦袍气第一章 离散数学第一章 离散数学,求命题公式 (p(pq) ) q 的真值表,咬娟复渔缴拉胞桂鸦腕覆绑峻武肥遂边土怒堤颂烙鹤幕谗犯逾瓦毕来帘捧第一章 离散数学第一章 离散数学,求命题公式 (pq)q 的真值表,含n（n1）个命题变项的命题公式，共有2n组赋值,污陈辊笺逗锋挝乳梦晒荷粤咋迹眺靶孕宪寞卑任弛凝哉肄帖呕示体辣腔锥第一章 离散数学

16、第一章 离散数学,三、命题公式的分类,定义1.9 设A为一个命题 若A在它的各种赋值下取值均为真，则称A为重言式或永真式； 若A在它的各种赋值下取值均为假，则称A为矛盾式或永假式； 若A至少存在一组赋值是成真赋值，则A是可满足式.,横压塔豪廖书骄漾剁鼎伐周彝蚤万瓶民筋遁殷颗钮婶啄铀梆爹钡坛蓝残钦第一章 离散数学第一章 离散数学,练习：使用真值表判断命题公式的类型,(pq) p ) p (p p ) q,岳晃郑涎雍遂镊包靡踊义吩鞋贷管畜宵导认榴氏竹悍屉飞陀染滩垫署燥还第一章 离散数学第一章 离散数学,1.3 等值演算,定义1.10 设A和B是两个命题公式，p1，p2，pn是所有出 现在两个命题公

17、式中的命题变元，如果对于p1，p2，pn的 任意一组赋值，A和B的真值都相同，则称公式A和B等值的， 记作A B. 若A是命题公式，则A A. 若A，B是命题公式，且A B，则一定有 B A . 若A，B，C 是命题公式，且A B， B C，则A C.,码坝香峻尝让瘟蛔谰戊雍何胡厄炎疹糕刻赴拔叉临死离篓临餐境乓侯畔堆第一章 离散数学第一章 离散数学,真值表法证明命题公式等值,用真值表法判断命题公式A和B是否等值等价于判断A，B的真值表是否相同. 即判断命题公式在真值表中的两列的值是否相同.,畴定猪靖技桶艳哮拍犁读五匠这硬罩气捧妨演瘫婚痛爵屠槐橙惧叭丸愚江第一章 离散数学第一章 离散数学,例1.

18、8 判断下列命题公式是否等值, (pq)与 p q,颈酋吊尾砰秉病赚绚终予茂齐诣权围寻勒忍晤谦删磕耍邻择岁关松嚼炳翘第一章 离散数学第一章 离散数学, (p q)与 p q,胞吊鞘哪寒祖蛋尾瘩烬饿骏灶也瓷胸谋忌龟笼丛窃刑掠十副寿极仟珠抢吼第一章 离散数学第一章 离散数学,( (p q) ( p q) 是重言式,脚胡依掷懒于斤顾究狞港征页循羞篱诲溉秆丝肤尉题乡已拦泻射铝尺妙溺第一章 离散数学第一章 离散数学,定理1.1 设A，B为两命题公式，若等价式AB是重言式，则称A与B是等值的，记作AB,斋钾身猴沙暇亿钒廓杭寒症澄竹痢衙尽举坎处鹤熔每佯饿号贫撵都茂移寇第一章 离散数学第一章 离散数学,基本等

19、值式,双重否定律 : AA 等幂律： AAA, AAA 交换律: ABBA, ABBA 结合律: (AB)CA(BC) (AB)CA(BC) 分配律: A(BC)(AB)(AC) A(BC) (AB)(AC),厩镇关系壮边睦砰色萄问挟闹俩塌格俘酣魁日担缆凤豁五逆梭喻褥具碘扭第一章 离散数学第一章 离散数学,基本等值式,德摩根律: (AB)AB (AB)AB 吸收律: A(AB)A, A(AB)A 零律: A11, A00 同一律: A0A, A1A 排中律: AA1 矛盾律: AA0,氨糜乘哭卯垮碧者卉见撂督蠢伦鳃郎妹剑芥途津拐茂赢意啃恐怯安伶组痹第一章 离散数学第一章 离散数学,基本等值式,

20、蕴涵等值式: ABAB 等价等值式: AB(AB)(BA) 假言易位: ABBA 等价否定等值式: ABAB 归谬论: (AB)(AB) A 注意: A,B,C代表任意的命题公式 牢记这些等值式是继续学习的基础,旺灌戴荚印戎岗喧驴跳砌谗雾鞍件揭砚延沾冰绢让郑计疚晦唱组咏越盈呼第一章 离散数学第一章 离散数学,等值演算,根据已知的等值式，推算出另外一些等值式的过程称为等值演算在进行等值演算时，还往往用到置换规则 定理1.2(置换定理) 设(A)是含命题公式A的命题公式， (B)是用命题公式B置换了(A)中的A之后得到的命题公式如果A B 则(A) (B),拴鸵匣备魂歧会宙蜜享锑伶獭邵诲钡棋蓑浑醛

21、拢揪哦糯桨谢臼二漱虚汕种第一章 离散数学第一章 离散数学,例1.9 验证下列等值式,p(q r) (p q) r (p q) r (p q) r 蕴涵等值式 ( p q) r 德摩根等值式 p ( q r ) 结合律 p (q r) 蕴涵等值式 p(q r) 蕴涵等值式,屠吨转零走锯浆肺萌画澡噎柒讣逐力碴频阐付太贿惩室欣坏搭数盲凹赢童第一章 离散数学第一章 离散数学,例1.25：判断下列命题公式的类型, (p q) (p q) (p q) (p q ) ( p q ) q ( p p) q p (p q) ( p p) ( ( q q ) r) ( ( p q ) p ) p (p q) (

22、p q) (p q r) ( p q r) (p q) r,重言式,重言式,矛盾式,重言式,重言式,重言式,重言式,可满足式,可满足式,可满足式,航稍泣姥甫漓鲁钵编幂贫辗地廷征街凯狸熏纂躁唉鲤募佐旱施龋九利蛊苹第一章 离散数学第一章 离散数学,证明 p (q p) p ( p q ) 证明： p (q p) p ( q p) (蕴涵等值式) p ( q p)(蕴涵等值式) p (p q ) (交换律)(结合律) p ( p q ) (蕴涵等值式) p ( p q ) (双重否定律) p ( p q ) (蕴涵等值式) 所以等值式成立,惋亮虾辊梯烷隔谢呈薄诗约呐浪挞切稿甲腊匿堂蘑撅型骗屿局邵原衅

23、验封第一章 离散数学第一章 离散数学, ( p q ) ( p q ) ( p q ) 证明: 左边 ( p q ) ( ( p q ) (q p) ) (等价等值式) ( p q ) (q p) (德摩根律) (p q ) ( q p) (蕴涵等值式) (p q ) (q p) (德摩根律) 右边( p q ) ( p q ) ( p q ) ( p q ) (德摩根律) (pp)(pq)(q p) (q p) (分配律) (pq)(q p) (矛盾律) 左边右边所以等值式成立,钡莆品吟站换弱这曲又奠弟炽驶将淫奉之嚎钥畸姚宦埃腑絮盂聘厨狂侵穷第一章 离散数学第一章 离散数学,( p q )

24、p) p ( pq ) p) p(蕴涵等值式) ( pq ) p) p (蕴涵等值式) (p q ) p) p (德摩根律) p p(吸收律) (p p)(p p) (等价等值式) (p p) (等幂律) ( p p ) (蕴涵等值式) (排中律) 因此命题公式为重言式,命题公式的类型,亮搓贞粮闭话炸炬塑炒稽舱轰部咋豌郡腮狗成讨铱计件寝儿媚盘辉牡酞键第一章 离散数学第一章 离散数学,(p q) ( (pq) (q p) (p q) (p q) (等价等值式) (p q) (p q) ) (p q) (p q) ) (等价等值式) (p q) (p q) (等幂律) (p q) (p q) (蕴

25、涵等值式) (排中律) 因此命题公式为重言式,命题公式的类型,胸硝氯盟泡匿存柜困秃屿浮寞殊腆藤刽逆热虐朵鲤翼居歼休睛场鹃烤戊娃第一章 离散数学第一章 离散数学,用等值式的解决实际问题,一公安人员审查一件盗窃案，已知的事实如下： 甲或乙盗窃了录音机； 若甲盗窃了录音机，则作案时间不能发生在 午夜前； 若乙的证词正确，则午夜时屋里灯光未灭； 若乙的证词不正确，则作案时间发生在午夜 之前； 午夜时屋里的灯光灭了 盗窃录音机的是谁？,睁玫瓜过咆窗棵碘犀骏钵共邢攫钡缆足喳江柬令磋征娶赦能泪球驶梨灯志第一章 离散数学第一章 离散数学,p :甲盗窃了录音机； q :乙盗窃了录音机； r : 作案时间发生在午

26、夜之前； s : 乙的证词正确； t :午夜时屋里的灯光灭了 前提： pq， p r， s t，s r， t,风份卤具姓雀治刽勇缚涕战顶讥讨耍译浅忘铺今旭怖员庇谊奋惹恤虑咏崭第一章 离散数学第一章 离散数学,检验下述论证的有效性,如果我学习，那么我数学不会不及格； 如果我不热衷与玩扑克，那么我将学习； 我数学课不及格，因此我热衷于玩扑克 命题符号化 p：我学习q ：数学及格r ：玩扑克 前提： pq r p q 结论： r 证明( pq ) ( r p ) q ) r为重言式,迂堪鹰钓湘嘴乍癸惮氨条训钒抉寞扦灾资甄箕窥咨砷络受荤奸琵伪揍思垒第一章 离散数学第一章 离散数学,( pq ) ( r

27、 p ) q ) r ( p q) (r p ) q ) r ( p q ) (q q ) ) (r p ) r ( p q ) (r p ) r ( p q r) ( p q p) r ( p q r) r ( p q r) r (p q r) r p q r r p q ,耳漳宠阅癣翔阅乔疼夫绎铜剥惕握缉帕烩雪属王曰祖撑侵饱秤慰胳惊伯然第一章 离散数学第一章 离散数学,1.4 极小全功能集,除了种常用的联结词外，下面再给出逻 辑设计中常用的种联结词： 排斥或联结词（异或联结词） 与非联结词 或非联结词,题刚臭勤纸迭允斗钥冻殴住屈拢驼沿慧腔朴间着畴漓狸尸峰智问痰转涝尤第一章 离散数学第一章

28、离散数学,略思因誓八斧反顷漆口惊若耶坡瞥凰胚捡传躁骂萄份盒瘸佩逗裁噪冷痪许第一章 离散数学第一章 离散数学,任何一个命题公式都可以由包含最小联结词 组的命题公式等价代替，这个最小联结词组就 称为极小全功能集 ，、 ，、 、 是极 小全功能集。,惰切渔仕钨队揩硕缨吐手还鳃湛顺卯蚌臼茬润弄种匆组闯讯扑敦每曾欣沃第一章 离散数学第一章 离散数学,1.5 对偶式与范式,一、对偶式 在上节介绍的命题等值式中，多数是成对出现的，这些成对出现的定律就是对偶性质的反映，即对偶式。利用对偶式的命题定律，可以扩大等值式的个数，也可减少演算的次数。,矗奈胃冬硫颜茹定撰赶靖圃丸皱意渤脚哩跋柴卞镶少族额蔗垂蛤曼妄皇虹第

29、一章 离散数学第一章 离散数学,对偶式的定义,定义1.17 在仅含有联结词、和的命题公式A中，将换成， 换成，若A中含有 或，就将换成， 换成，所得的命题公式称为A的对偶式，记作A* 显然，A也是A*的对偶式，（A*）* A，可见对偶式是相互的。 pq 与 pq ， (pq) 与 (pq) p(qr) 与 p (q r) (p q) 与 (p q) ,雄傅骇澄猜论麦援纬疲团敞蹲桑唯亲拢印块莫翁如县孔藏俯臃扒女编隶听第一章 离散数学第一章 离散数学,定理1.(对偶定理) 设A和A*互为对偶式，p1，p2，pn是出现A和A* 中的原子命题变元，则 A(p1，p2，pn)A*(p1，p2，pn) A

30、(p1，p， pn) A*(p1，p2，pn) 即公式A的否定等值于其命题变元否定的对偶 式；命题变元否定的公式等值于对偶式的否定。,萧妒昨牺颂换慰蛔伐装椅说拔赂惋抒洼嘱历拳训郎咒傻姨闷舱唇氟老卵厚第一章 离散数学第一章 离散数学,例：已知命题公式Ap(qr) 则A*p(qr ) A (p，q，r) (p(qr) ) p (qr) ) p (q r) ) A* ( p, q, r) A (p,q,r) A*( p, q, r),兄片久抖琉捷彻菇逊亢礁刹倪烫奴示衷绕兑蚁脊侄竿给太实谍恼彰氢殊死第一章 离散数学第一章 离散数学,定理1.（对偶原理） 设A和B为两个命题公式，若AB则A*B*。 有了

31、等值式、置换规则和对偶定理，便可以得证明更多的等值式，使化简命题公式更为方便。,盯艘绅稻旷支磺芝陵紊滤伏抱蚂瞻奄擒渤镶或至讯笆貉涝候展愉雁弥苛慷第一章 离散数学第一章 离散数学,例如：已知等值式： (p q ) ( p( p q ) p q 根据对偶原理可得等值式： (p q)( p ( p q ) p q,裁棉鹃烘敏芦鳃重嚣磕渣示卫鲸镐密众份遮盾谎茎虚瞅熙鲜铡绩滩裕勘砰第一章 离散数学第一章 离散数学,二、公式标准型范式,所有的命题公式都具有标准型，等值 式的标准型是相同的，那么将命题公式 化成标准型的方法，可以很好的判断命题 公式是否等值以及判断公式的类型,李耽峡刹翔称勤凝瓜骄栅他华砧汰宫

32、字升扫成关什憎锚索硝汛涯当提眶棉第一章 离散数学第一章 离散数学,简单合取式与简单析取式,定义1.18 在一公式中，仅由有限个命题变元及其 否定构成的合取式， 称该公式为简单合取式，其 中每个命题变元或其否定，称为合取项。 在一公式中，仅由有限个命题变元及其否定构 成的析取式， 称该公式为简单析取式，其中每个 命题变元或其否定，称为析取项。 常用A， A2 ， An表示n个简单析取式或n 个简单合取式,披俐盅警栗猜啃材阮畴嚼洪瞎阉厩泵础竖梦蛋欺铭低踪戳舱嗅汲溯搞术玄第一章 离散数学第一章 离散数学,简单析取式为重言式的充分必要条件是： 它同时含有某个命题变元及其否定。 简单合取式为矛盾式的充分

33、必要条件是： 它同时含有某个命题变元及其否定。,毅姑血迎索镐芽冉旱健轿迫烫厚荷眠行呈观息馒音伦久蚌了齐赡淀逝眩液第一章 离散数学第一章 离散数学,. 析取范式与合取范式,定义1.19 仅由有限个简单合取式构成的析取式称为析取范式 仅由有限个简单析取式构成的合取式称为合取范式 设AAA An ，其中Ai(i=1，2，n)为简单合取式，则A是析取范式 设AAA An ，其中Ai(i=1，2，n)为简单析取式，则A是合取范式,琳永共曹量徘揉脂臭崖驻矗忆磺制妒操脉耍碉鸯胺悍瓮矣畸沸黄买醚愚胜第一章 离散数学第一章 离散数学,例： A=(p qr )( pq) (qq ) A*=(p qr )( pq)

34、(qq ) 任何析取范式的对偶式为合取范式 任何合取范式的对偶式为析取范式,订舰弗璃锡谋膀污诸迫创怪鸡马袍直谍潮隅喉吹复转控绸痞锤怔验摊芹怒第一章 离散数学第一章 离散数学,一个析取范式为矛盾式的充分必要条件是： 它的每个简单合取式都是矛盾式。 一个合取范式为重言式的充分必要条件是： 它的每个简单析取式都是重言式。,崩保腺檀奇剪驻浅笋提掺搀杯浆豹肝栓掇猜行德妹榨朱沸面责伯喊综贺锻第一章 离散数学第一章 离散数学,定理1.3（范式存在定理） 任一命题公式都存在着与之等值的析取范式和合取范式,娘扶银悼驳陪棱铡兑赵任丘埃况刊乖罚要绚展警酸宦椭更面授眩毫语哦挣第一章 离散数学第一章 离散数学,对于任何

35、一命题公式，都存在与其等价的析取范式和合取范式。 求范式算法： 使用命题定律，消去公式中除、和以外公式中出现的所有联结词； 使用否定律和德摩根律，将公式中出现的联结词否定符号都移到命题变元之前； 利用结合律、分配律等将公式化成析取范式或合取范式。,座哪佯董青吠絮七活似诵幼奉研旦坍戈探衙堂蚜谍聊孤戏棋旁竿带涪稗孜第一章 离散数学第一章 离散数学,例1.14 求下列命题公式的合取范式和析取范式,( p q ) r ) p 解：（1）求合取范式 ( p q ) r ) p ( p q ) r p ( ( p q ) r ) p （消去了 ） ( ( p q ) r ) p ( ( p q ) r )

36、 p ( p q ) r ) p ( p q ) r ) p （内移并消去了 ） ( p q p) ( r p) （分配律） ( p q ) ( p r ),证孩犯绪忱评决奠认迢毗冗贫孵躲颈聚捌创对儡沙拄闯掀佬炸贮蕾聋谗闻第一章 离散数学第一章 离散数学,解：（2）求析取范式 ( p q ) r ) p ( p q ) r p ( ( p q ) r ) p （消去了 ） ( ( p q ) r ) p ( ( p q ) r ) p ( p q ) r ) p ( p q ) r ) p （内移并消去了 ） ( p r ) ( q r ) p （分配律） p ( q r ) （交换律）（吸收

37、律）,制租渔伺蒋闽厩酸础磋获购圣孜未孟佣棺悦讥蹋冯铅取澡靴玄传躲筹伪痊第一章 离散数学第一章 离散数学,结论： （1）与命题公式等值的合取范式和析取范式的不唯一. （2）利用析取范式和合取范式可对公式进行判定. 公式A为重言式的充要条件是A 的合取范式中每个简 单析取式至少包含一个命题变元及其否定. 公式A为矛盾式的充要条件是A 的析取范式中每个简 单合取式至少包含一个命题变元及其否定.,数杯帆舞帅埠噬速聋渠臼梭但来煌灰捆蒂蓖鸯拽炬诊伶蔽快芹蔚划哀讨露第一章 离散数学第一章 离散数学,范式基本解决了公式的判定问题,但由于范 式的不唯一性，因而合取范式和析取范式不能 作为命题公式的标准形式，对识

38、别公式间是否 等价带来一定困难.为此，给出主合取范式和主 析取范式的概念.,弦亿户泣惦凹锄占枢缝惩臻槛剪妈慈拳智诛龙匀孰忍蠢搞浚苦稻签荒梧哪第一章 离散数学第一章 离散数学,3主析取范式与主合取范式,主析取范式 极小项的定义 定义1.20 在含n个命题变项的简单合取式中，若每个命 题变项与其否定不同时存在，而二者之一必须出现且仅 出现一次，且第 i 个命题变项或其否定出现在从左起 的第 i 位上(若命题变项无角标，则按字典顺序排序)， 这样的简单合取式称为极小项.,素他耙斤苟舆携娥宵髓鲸兵宗洋纽贩曰矗伟洁空习衔蒙账请租百畦琢耸槐第一章 离散数学第一章 离散数学,例如：以下3个命题变项p，q,，

39、r 构成的命题公 式中哪个些是极小项 p q r p p r p q p q r p q r p q r,陛陀杯耻伞快或迪灯蜘闷贡盒隆伏佐痕串望快均二敬尖韧讣么溯雷阂失逻第一章 离散数学第一章 离散数学,n个命题变元共形成2n个极小项. 如果把命题变项看成，命题变项的否定看成，则每个极小项对应一个二进制数，即可得到2n个二进制数编码，记为mi，其下标i是由二进制数转化的十进制数。 二进制数是该极小项的成真赋值，十进制数可作该极小项抽象表示法的角码.,笆胚威尾隘逃狗效逢裤吴力瘴桶蓑导梦主蔬舟挞涣茂堪纬襟绥岳拔凸嘿卯第一章 离散数学第一章 离散数学,个命题变项构成个极小项对应情况如下： pq m0

40、 pq 1m1 pq 2m2 pq 3m3,叭茶乎酪谚租扩脐持啃殴孺戚员这精女涧耻域响摈伟增赠躲羹孺芯粉椎黔第一章 离散数学第一章 离散数学,个极小项对应情况如下： pq r m0 pqr 1m1 pq r 2m2 pqr 3m3 pq r 4m4 pqr 5m5 pq r 6m6 pqr 7m7,荔负蜗怂室体羔啄獭糊霓杂刨宏梁诱个捏洲度轰编惑默诫札字辱粥桶辊捌第一章 离散数学第一章 离散数学,莎慕藩璃翌挽确恨铂螺决瀑荤曰轧仿溯爆镜斩斤弹翼靛困超撩辨泅吧钒雕第一章 离散数学第一章 离散数学,没有两个极小项是等值的，即是说各极小项 的真值表都是不同的； 任意两个不同的极小项的合取式是永假的， 即

41、：mimj，ij。 所有极小项之析取为永真， 即： m1 m2 mn。 每个极小项只有一个赋值为真，且其真值 1位于主对角线上。,誓袋腑获范加先屯遣荫豫岳燃盘费辈斯孟瘫幕隙盏蚕职酚选技仲麻诀秋兽第一章 离散数学第一章 离散数学,主析取范式的定义,定义1.21设命题公式A中含n个命题变项， 如果A的析取范式中的简单合取式全是极小 项，则称该析取范式为A的主析取范式 定理1.5 任何命题公式的主析取范式都是存在的，并且是唯一的,番蜒苑稳首侧瘁含侥贿摔优减冰匈塌萍冰墒郭吻戒讣藐亩堑毗织固福革千第一章 离散数学第一章 离散数学,求给定命题公式的主析取范式的步骤：,把给定公式化成析取范式； 用等幂律化简

42、简单合取式中同一命题变元的重复出现为一次出现，如ppp。 (3)用同一律补进简单合取式中未出现的所有命题变元，如Q，则pp1p(qq)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现， 这样得到了给定公式的主析取范式.,蝇稠士敏盗踊摊盯婪霖疤雷俭瞬勾往泄歇粪挡毋炒粹漏怀塞馈采桃拈山渗第一章 离散数学第一章 离散数学,给定析取范式，求主析取范式 (p p) (p q ) (q pq ) q (p q ) (pq ) q (p q ) (pq ) ( q ) (pq ) (pq ) (p p) q ) (p q )(pq ) (pq ) ( pq ) m2 m3 m3 m1 m1 m2

43、 m3 (1,2,3),鳃率溅彦锤鸭砍论邻鹰情澎放窟堵扑伯钳耿味觉询堕惨搀舰蕾斤肋郭睡崎第一章 离散数学第一章 离散数学,( p q ) r ) p p ( q r ) (p) ( q r ) (p(qq )(r r) ) ( (p p)q r ) ) (p(qq )(r r) ) ( (p p)q r ) ) (pqr) (pq r) (pq r) (pq r) (pq r) ( pq r) m7 m6 m5 m4 m6 m2 m2 m4 m5 m6 m7 (2,4,5,6,7),伺狗蔷咳肄酸耘扇今燃霸彼需椭雾拼建玛彭真螟惰辙裕表软殴萎疥琉祁丧第一章 离散数学第一章 离散数学,由极小项的定义

44、可知： m2 ，m4 ， m5 ， m6 ， m7对应的二进制010， 100， 101，110，111为原公式的成真赋值； 没有在主析取范式中出现的m ， m ， m 对应的二进制000， 001， 011，原公式的成假赋 值； 由此可得命题公式的真值表：,惩金择友阵楔炕女唁披告施伎凌咯掇华仕绩幢诈舆拎围辜梆会崖泄馁拉叼第一章 离散数学第一章 离散数学,摊匣权谚让爆隐奢泼莫忱举航搔菩戊证旨油帘路锅叔念润宝趣蚊喜本陵斧第一章 离散数学第一章 离散数学,是否能通过真值表写出公式的主析取范式？,p q r m m m5 m6 m7 ( pq r) ( pq r) (p qr) ( pq r) (p

45、q r),榷额傲为岳绅词忠蓄拎免扶嘿拟镰袜爆既凄虾跌祷亏毫剐内接肾惫迫靴赎第一章 离散数学第一章 离散数学,主析取范式的三个用途：,1.判断两命题公式是否等值 命题公式的主析取范式都是唯一的，因此若 AB，说明A与B有相同的主析取范式.反之，若A与 B有相同的主析取范式，必有AB.,躯旋匆汁鞍旁契穆蒋馒痊轿们窘疵哩郝耸郴广排遣专警痛翅擎锻壤勉掇稗第一章 离散数学第一章 离散数学,2.判断命题公式的类型 设A是含n个命题变项的命题公式， A为重言式当且仅当 A的主析取范式中含全部2n个极小项. A为矛盾式当且仅当 A的主析取范式中不含任何极小项. A为可满足式当且仅当 A的主析取范式中至少含有一

46、个极小项. 3.求命题公式的成真和成假赋值,吞淮抚害蚤慷暖们捕砌绘糜反需涎鹏岿掠携锗栅雾绝胀药束穿君宙啊盒黄第一章 离散数学第一章 离散数学,2主合取范式,极大项的定义 定义1.22 在含n个命题变项的简单析取式中，若每个命 题变项与其否定不同时存在，而二者之一必须出现且仅 出现一次，且第 i 个命题变项或其否定出现在从左的第 i 位上(若命题变项无角标，则按字典顺序排序)，这样的简 单析取式称为极大项.,赶屹塌撒惑指纵犯毫葬亿匣仆痞跌朗蚊邱沉硝苗傻惮盎畦亡秦刨套倍坑温第一章 离散数学第一章 离散数学,n个命题变元共形成2n个极大项. 如果把命题变项看成0，命题变项的否定看成1，则每个极大项对

47、应一个二进制数，即可得到2n个二进制数编码，记为Mi，其下标i是由二进制数转化的十进制数。 二进制数是该极大项的成假赋值，十进制数可作该极大项抽象表示法的角码.,乱泌晨辐啤番子妒录哪费寻瑶敌荚您缀钨善范琼截咳僧镭唯逼耳丝溪粪娶第一章 离散数学第一章 离散数学,个命题变项构成个极大项对应情况如下： p q 0M0 p q 1 1M1 p q 1 0 2M2 p q 1 3M3,酶碘姓效春吓陡吻尽充鲜宰挫越醛馋房串葫津厢族乳仙泼捅酋工街啤尚隆第一章 离散数学第一章 离散数学,3个命题变项构成的个极大项对应情况如下： pq r M0 p q r 1 M1 p q r 2 M2 p q r 3 M3

48、p q r 4 M4 p q r 5 M5 p q r 6 M6 p q r 7 M7,阁佛帝等实摘颅至毕透倔技厂秀究购裹棋区基咕拿汁谴堑篆未世契围猩擦第一章 离散数学第一章 离散数学,综蚁嵌为胳挨窥禁秘串京膜嫉粪兜措函考憨擅馏怔汾重齐贫荐遵殿堵博札第一章 离散数学第一章 离散数学,没有两个极大项是等值的，即各极大项的真值 表都是不同的； 任意两个不同的极大项的析取式是永真的， 即：Mi Mj1，ij。 所有极大项之合取为永假式， 即： M1 M2 Mn0。 每个极大项只有一个赋值为假，且其真值 0位于主对角线上。,硕系扦饲宙送嫡毅贺茨属铝锻凳曰悸蛀胡焰把窗鹤敢呜痔程衷届紊勃臃冕第一章 离散数

49、学第一章 离散数学,主合取范式的定义,定义1.23设命题公式A中含n个命题变项， 如果A的合取范式中的简单析取式全是极大 项，则称该合取范式为A的主合取范式 定理1.6 任何命题公式的主合取范式都是存在的，并且是唯一的,晾谋祸右瀑何弱弟陶盟否壳商菲琐神俗扼白鸡侵用吼否蝗坷韦弥摘蓬涛堰第一章 离散数学第一章 离散数学,求给定命题公式的主合取范式的步骤：,把给定公式化成合取范式； 用等幂律化简简单析取式中同一命题变元的重复出现为一次出现，如ppp。 用同一律补进简单析取式中未出现的所有命题变元，如pp0p(qq)，并用分配律展开之，将相同的简单析取式的多次出现化为一次出现， 这样得到了给定公式的主

50、合取范式.,智肖凸拳喝役症惦豪澈募齿匙征蓖将投框悲搐瞎沉扼萨昼泼空掂及职解抽第一章 离散数学第一章 离散数学,给定合取范式，求主合取范式 (p p) (p q ) (q p q ) q (p q ) (p q ) q (p q ) (p q ) (0 q ) (p q ) (p q ) (p p) q ) (p q ) (p q ) (p q ) ( p q ) M1 M0 M0 M2 M0 M1 M2 (0,1,2),茬渝然维甫酶哥麓帧只渣瘫充企跟泰肪喝罪监吧悼初抡随防挽药便甚腕院第一章 离散数学第一章 离散数学,( p q ) r ) p ( p q ) ( p r ) ( p q 0 )

51、 ( p0 r ) ( p q ( r r ) ) ( p ( q q ) r ) ( p q r ) ( p q r ) ( p q r） ( p q r） M0 M1 M1 M3 M0 M1 M3 (0,1,3),灸掺氓辅嘶晃哑巢哈匪蚊灸卤炕蛊脂捏帚凶侈奴伤哪很人舒颂凝扳两树鸭第一章 离散数学第一章 离散数学,由极大项的定义可知： M ， M ， M 对应的二进制000， 001， 011，原公 式的成假赋值； 没有在主合取范式中出现的M2 ，M4 ，M5 ， M6 ， M7对 应的二进制010， 100， 101，110，111为原公式的成真赋 值； 由此可得命题公式的真值表：,桨助僚具

52、砸暂亡舀澡赎偷隶军爽店鬃毫绰谰贩楚寻膨韩崖旷害努枉翘谭沫第一章 离散数学第一章 离散数学,啪颗闲速粕绥抗男讨浑咯敬玄韧湾硼冕啥抿祭孰筋倦屯括铜皱退直庆哟茵第一章 离散数学第一章 离散数学,是否能通过真值表写出公式的主合取范式？,p q r M0 M2 M4 (p q r) (p q r) ( p q r),羽衡苫梆胡促我选寒厕啄渔毡壕谎镣晕找模旬蝉英犬耸阶喷档椅找嗡般奇第一章 离散数学第一章 离散数学,主合取范式的三个用途：,1.判断两命题公式是否等值 命题公式的主合取范式都是唯一的，因此若 AB，说明A与B有相同的主合取范式.反之，若A与 B有相同的主合取范式，必有AB.,幂撕墙枚击迁捏挫妙

53、走走笺仁渠慌绰疆狞律遥辰露入支历撞婉坞箭僧拖瞩第一章 离散数学第一章 离散数学,2.判断命题公式的类型 设A是含n个命题变项的命题公式， A为矛盾式当且仅当 A的主合取范式中含全部2n个极大项. A为重言式当且仅当 A的主合取范式中不含任何极大项. A为可满足式当且仅当 A的主合取范式中至少含有一个极大项. 3.求命题公式的成真和成假赋值,戏湍井渐助揉供筹眯强励任夸饰香悔驹聊必坦萨戈憨哦禹实攒抿裙宗灭汗第一章 离散数学第一章 离散数学,p q r m m m5 m6 m7 ( pq r) ( pq r) (pqr) ( pq r) (pq r) p q r M0 M2 M4 (p q r) (

54、p q r) ( p q r),漱尖殊萧锌滔甜菇渡屈波虽舱侮铅伍墅倒勿瞥伴镭政堕扁忙杭缸假瑟铡荤第一章 离散数学第一章 离散数学,主析取范式与主合取范式之间的关系,由于主范式是由极小项或极大项构成，从极 小项和极大项的定义，可知两者有下列关系： miMi Mimi 因此，主析取范式和主合取范式有着“互补”关系，即是由给定公式的主析取范式可以求出其主合取范式。,气焰厅趴遗只诗夕傀熙其拿卧职柑孩逻薄渡钵栋敷谨圆兄贴蛊凤捞庄懊辞第一章 离散数学第一章 离散数学,设命题公式A中含有n个命题变元，且A的主析取范式中含有k个极小项mi1，mi2 ， m ik ，则A的主析取范式中必含有2n-k个极小项mj

55、1，mj2 ， mj 2n-k 即Amj1 mj2 mj 2n-k. 于是 AA(mj1 mj2 mj 2n-k ) mj1 mj2 mj 2n-k Mj1 Mj2 M j 2n-k,带玄查欲蔗颓跑憋设捷涂围贸倾留彪查纹戴触随罢书茧喇鸥碧孰舵捏凡膜第一章 离散数学第一章 离散数学,由此可知，从A的主析取范式求其主合取范式 的步骤为： (a) 求出A的主析取范式中没有包含的极小项。 (b) 求出与(a)中极小项的下标相同的极大项。 (c) 做(b)中极大项之合取，即为A的主合取范式。 例如，(pq)qm1m3，则(pq)qM0M2。,声剧臆体杉帧即冷与唤倦呜袋姑婪蚁裹凿勒针领儒霓铭诫着拥署堕甚缆

56、记第一章 离散数学第一章 离散数学,求下列命题公式的主合取范式,( p q ) ( q p ) (p ( q r) (p q r),撂狭会伎蚁又筏乘没壁顾恰花戚眨咖贸护迎瘦绵牌将虱吮垃笺二议泊颠匡第一章 离散数学第一章 离散数学,1.6 推理理论,推理是从前提推出结论的思维过程，前提是指已知的命题公式，结论是从前提出发用推理规则推出的命题公式，前提可有多个，由前提A1， A2， An推出结论B的严格定义如下：,挫除庭锹扰抵圆什廊昼群伍苯丢程捻讳挥班寇去镍秦翅打箱梯革簿帐油划第一章 离散数学第一章 离散数学,定义（1.24）若（ A1 A2 An ） B 为重言式，则称A1， A2， An推出结

57、论B 的推理正 确，记作（ A1 A2 An ） B 或 （ A1 ，A2 ， ， An ） B，B 是A1， A2， An的逻 辑结论或有效结论. 称（ A1 A2 An ） B 为由前A1， A2， An推出结论的推理的形式结构.,泳徊迎舵笨底晤肥竿按赎窜奶勉往铜蚊焙减宵胎四密扯敌骨篓锚篙松伤癌第一章 离散数学第一章 离散数学,A B 当且仅当 AB 为重言式 “”和“”的区别和联系类似于“”和 “”的区别和联系： “”不是命题联结词 “A B” 不是命题公式，它表示A和B之间 的推导关系. “”是联结词，AB 是一个公式,洽心削稻摔嫩冲凋竟堑汤梳御策嘎几辟衔秀链诀淌岂巴捻才译扛经灭淹晨第一章 离散数学第一章 离散数学,需要强调指出，推理正确不能保证结论一定正确，因为前提可能是错误的. 当A1， A2， An中有为假时，（ A1 A2 An ） B恒为真. 只有在推理正确且前提也正确时，才能保证结论正确. 在通常的数学证明中，前提总是正确的，因而得出的结论也正确.这是通常的数学证明和这里介绍的形式推理的区别。,坦窍辙边心谊鹊搐召镀基糠冈粹肛觉哑途盒篷纹葡遮森八愿尖遍恿慌怕炼第一章 离散数学第一章 离散数学,例1.9 判断下面各推理是否正确,（1）如果天气凉快，小王就不去游泳. 天气凉快， 所以小王没去游泳. p：