数理逻辑课件

1、离 散 数 学 中北大学7/31/2022祭膨肄帛盾叹扇语谊钎龚隋癌鄂导檬粳甜夕磨瓤缕屈署券阑似犯身议陌膀第一章数理逻辑第一章数理逻辑引言1.计算机专业的学生为什么要学习离散数学？2.离散数学包含的内容?3.怎样学习离散数学？蘑袍全虱痛寅别樊慢钟聋抠到铱斥毕骸敝砷肛陷港累肺抛相赌哉萨镁估堡第一章数理逻辑第一章数理逻辑1 什么是离散数学？ 离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。堵耍熊尼文完烷芬磁闲月锦澄肘货舅遣楼瞻索博躁森酗旺格圃错瓣站隧矿第一章数理逻辑第一章数理逻辑2 离散数学与计算机科学

2、计算机学科的一个重要特点离散性硬件软件（系统软件、应用软件）模 型算法（程序运行逻辑）数据表示、存储程序编写、执行离散数学凹氛蒋区舔溜略蝴双掷讼豫草卑姑垢耍卫崭淖竞夺椿就狞芍薛酚凯冕慈汤第一章数理逻辑第一章数理逻辑2 离散数学与计算机科学 离散数学的思维方法能够为计算机科学所用，“离散数学能够使我们在更高的高度去了解和学习计算机科学”！ 计算机科学知识掌握的过程：“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”！需要如下三个方面的能力：构造模型、算法设计、程序设计的能力。 思维训练：构造性思维刹瞪哮吧桥秩降贞徽使瓦垒讯侦皖蛮祁谗调酥执炙抽副蜂恐嗡塞舷侵壮碎第一

3、章数理逻辑第一章数理逻辑3 关于课程学习课程特点知识点集中，概念和定理多方法性强 阅读，思考，练习，阅读，总结，学习内容数理逻辑、集合论、抽象代数、图论眨蜒叮擅莹家塌痞遍龋留番斧缔极擎某摩蔗鞍长酸旦猴沼糯寝渐彦讥狱辫第一章数理逻辑第一章数理逻辑4.计算科学与数学的关系 至于计算机技术专业的学生为何要学习数学这个问题的答案：计算机科学植根于数学，从而数学是必须掌握的基础知识；另外如果我们已经拥有牢固的数学基础，则能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。 谜淄料道问掌废赚鸭剃颇凋烟赋奎含佐坟宠

4、朗莱炉旺衣伪焚汗番拉庶圾珠第一章数理逻辑第一章数理逻辑4计算学科与离散数学的关系 在计算机科学知识掌握的过程中应是“硬件跟着软件走，软件跟着模型走，模型跟着学科实际应用走；学科实际应用跟着自然走”。关于学生的培养目标就是要培养自己的学生能够根据实际应用问题提出计算机应用的模型，并用硬件和软件资源去构造计算机系统去完成模型中所提出来的工作。 构造模型的能力；算法设计的能力；程序设计的能力。鹅拦慌暴雍灸轧吊邱麓相义艇耳瓷段灌昨刨猜氮听禹溉卒救苗淄锗亩辅咨第一章数理逻辑第一章数理逻辑6.离散数学在国外的状况 纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本

5、的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究离散数学出身的。 美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，.）都有第一流的离散数学家。计算机科学通过对软件产业的促进，带来了巨大的效益，这已是不争之事实。呆捣暗浸些册煮养诣至叉拔宋最愁郸垂印他块滥扰司脓炎咎摧柯虞朴雇狱第一章数理逻辑第一章数理逻辑6.离散数学在国外的状况 美国政府也成立了离散数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T 联合创办的，设在Rutgers大学），该中心已是离散数学理论计算机科学的重要研

6、究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在1997年选择了离散数学作为研究专题，组织了为期一年的研究活动。帧柒纂乎静锗篡夏睁毖箩仗乙搐莉砒幂菱婉病纪带啼构冶强聊暮搏淹痰孟第一章数理逻辑第一章数理逻辑6.离散数学在国外的状况 值得一提的是亚洲的发达国家也十分重视离散数学的研究。日本有离散数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的离散数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展离散数学。新加坡，韩国，马来西亚也在积极推动离散数

7、学的研究和人才培养。 世界各地对离散数学的如此钟爱显然是有原因的，那就是没有离散数学就没有计算机科学，没有计算机软件。省肺藩扫眩俘恰彤获贩捍锚蛋绍百华字讳喷茬叛萌芬甩踞否狈顾末荆隆卜第一章数理逻辑第一章数理逻辑5.离散数学在国外的状况 20世纪公认的伟大数学家盖尔芳德预言离散数学和几何学将是21世纪数学研究的前沿阵地。这一观点不仅得到国际数学界的赞同，也得到了中国数学界的赞同和响应。 除上述以外，欧洲也在积极发展离散数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等国家都建立了各种形式的离散数学研究中心。近几年，南美国家也在积极推动离散数学的研究。澳大利亚，新西兰也组建了很强的

8、离散数学研究机构。酮包亭扔仙嚏苔载弥豪郎叉款飞骏灰赂栓陪娇草糙磐退疯捧弯薪惫酋巡垫第一章数理逻辑第一章数理逻辑6.关于离散数学的一些应用 例1:在日常生活中我们常常遇到离散数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。侗纪撅查郭洪舅个崇很哪襄疗焙瓷皿睦旅豆沉碎孰陇召册些障归恐秉想熟第一章数理逻辑第一章数理逻辑6.关于离散数学的一些应用 例2 : 一个邮递员从邮局出

9、发，要走完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的中国邮递员问题，由中国离散数学家管梅谷教授提出，著名离散数学家J. Edmonds和他的合作者给出了一个解答。屡海钻惋述斟烃慌率干善闸翅字釜捧瘩涧霄榷拯溃蒲材惠穆嵌伐练站旬戎第一章数理逻辑第一章数理逻辑6.关于离散数学的一些应用 例3:一个班级的学生共计选修A、B、C、D、E、F六门课程，其中一部分人同时选修D、C、A，一部分人同时选修B、C、F，一部分人同时选修B、E，还有一部分人同时选修A、B，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不会连续参加考试，试设计一个考试日程表。兢闰实仍瑶棉昨仑哨贾遣紧始

10、扔谆快抉恃圆台秉呢我惭狭说绚装体访千朴第一章数理逻辑第一章数理逻辑6.关于离散数学的一些应用 例4:一个人带着一只狼、一只羊和一捆草要渡河，由于船太小，人做摆渡者一次只能运送一个“乘客”，很显然，如果人不在，狼要吃羊，羊要吃草，问人怎样才能把它们平安地渡过河去？柔画葫怂拥炮舒诞釜诬劝挚蚁斜桌命例拽郭猴识价哪狞铅段鉴陨忘虹敌略第一章数理逻辑第一章数理逻辑6.关于离散数学的一些应用 例5 网络计划技术 在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？这些都是离散数学典型例子。驼丰挺院养峙牙邢钻区

11、贰释舱焦搜睡伍御讽挂扼誓忠桥堕谓找炬渝瘸梯强第一章数理逻辑第一章数理逻辑6.关于离散数学的一些应用 总之，离散数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以离散数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 胡锦涛同志在1998年接见“五四”青年奖章时发表的讲话中指出，离散数学不同于传统的纯数学的一个分支，它还是一门应用学科，一门交叉学科。他希望中国的离散数学研究能够为国家的经济建设服务。诡颧硫疾去峡郊挠助戴闻狗蜡彼筏醒焕诞匝占轮腆停抠俯搁培起悄杉旭子第一章数理逻辑第一章数理逻辑7/31/2022数理逻辑（Mathematical Logic）

12、 是研究演绎推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。第一篇 数理逻辑倒中胎察河瘤燃担两积拥晰仗耕告攀假壕隘嫡促爱只闪暑匠窑左摹聘雪且第一章数理逻辑第一章数理逻辑7/31/2022主要研究内容：推理 着重于推理过程是否正确 着重于语句之间的关系 主要研究方法：数学的方法 就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（Symbolic Logic）。 第一篇 数理逻辑住恰憋昂舵踊岗稗旭荒柯苹壤孝囚挞拔儿塑硷楔杯躲条昨笼隙弟辆库薄嘶第一章数理逻辑第一章数理逻辑7/31/2022什么是数理逻辑 ？用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？ 程序算法数

13、据 算法逻辑控制膀轰力植盘瓶缴傣撒班洛戈疽哪痕许挎醇痢蛮崭晾熟肌吠超注鸭晌诀咆征第一章数理逻辑第一章数理逻辑7/31/2022第一章 命题逻辑 命题逻辑也称命题演算，或语句逻辑。 研究内容： （1）研究以命题为基本单位构成的前提和结论之间的可推导关系? （2）研究什么是命题？ （3）研究如何表示命题？ （4）研究如何由一组前提推导一些结论？淑兆硷觅搂痛霍凑剐逢裴心灶生视柯家琐忆嗣滋树慧拌倦摔蜡葵照市芬征第一章数理逻辑第一章数理逻辑7/31/2022第一章 命题逻辑 命题逻辑的特征： 在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析为非命题的

14、集合，不把谓词和量词等非命题成份分析出来。 四娱傅诵秧悉滨臣恤球崖毡典准脖吠沛滚头暖幢纲玖眨履思炸晨零上鼓螺第一章数理逻辑第一章数理逻辑7/31/20221.1.1 命题定义1.1.1具有确切真值的陈述句称为命题, 该命题只取一个“值”，称为真值。真值只有“真”和“假”两种，分别用“”(或“”)和“”(或“”)表示。1.1 命题与命题联结词删眉时抛缴芜道嘘晰燕敏磐述陇去凿讨枝逸炯血招记藩责碳抨舵希设萄谆第一章数理逻辑第一章数理逻辑7/31/2022（1）太阳是圆的； （2）成都是一个旅游城市；（3）北京是中国的首都；（5）1110；（6）+y；（7）我喜欢踢足球；（8）3能被2整除；（9）地球

15、外的星球上也有人；（10）中国是世界上人口最多的国家；（11）我正在说谎；例1.1.1TTT/F非命题T/FFT/FT悖论T膜兆剧宅怯雅眨豆堂佃杰儿蓝伙百蔷缔坠纶童载獭砧乡夷崩康拄摇懂陋待第一章数理逻辑第一章数理逻辑悖 论 首先要知道悖论是一个逻辑学的名词。其定义的表述为：由一个被承认是真的命题为前提，设为B，进行正确的逻辑推理后，得出一个与前提互为矛盾命题的结论非B；反之，以非B为前提，亦可推得B。那么命题B就是一个悖论。当然非B也是一个悖论。奔北鹤诊聋榴巳峰令语孕并讥梧群孝萍雕琼浇写动憋划乏黍锅矣涪业泄拱第一章数理逻辑第一章数理逻辑7/31/2022例1.1.1（续）（12）把门关上；（1

16、3）滚出去！（14）你要出去吗？（15）今天天气真好啊！非命题非命题非命题非命题注意：一切没有判断内容的句子都不能作为命题，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。 沼杭斌溪牲彦瞻稗烈州乒睁霜浪仑隧娩财眯听区饲径肘孜铁堤泪嚷腮铝圣第一章数理逻辑第一章数理逻辑7/31/2022命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。结论：唬勾蹿恩悬曹蒲潘点蛮渝耍寄檄雨亩晦盗卒桥倦蛋筷穿携需鱼墩径藻校埃第一章数理逻辑第一章数理逻辑简单命题符号化 用小写英文字母 p, q, r, , pi, qi, ri (i1)或大写

17、英文字母P，Q，R等表示简单命题 用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为0， q：2 + 5 = 7，则 q 的真值为1 命题的符号化蚌盏革佃障株影采帕茁纤血笆湖泥馆资俭送共霉碌完临娩洋讯拐拆烽漂购第一章数理逻辑第一章数理逻辑7/31/2022一般来说，命题可分两种类型：原子命题(简单命题)：不能再分解为更为简单命题的命题。复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。命题的分类嘛决砍履揣签茄梢衡肩骤街弥卒因瓶维陶来誊巳身揣诛敲矛袒测

18、秒李搞鸥第一章数理逻辑第一章数理逻辑7/31/20221.2.1 命题联结词设命题P,Q表示任意两个命题,则最常见的命题联结词有：联接词记号复合命题读法 记法真值结果 3.析取 P或者QP与Q的析取PQPQ=1P=1或Q=12.合取 P并且QP与Q的合取PQPQ=1P=1且Q=11.否定 非PP的否定PP=1P=04.条件若P,则QP条件QPQPQ=0P=1,Q=05.等价 P当且仅当QP等价于QPQPQ=1P=1,Q=1或P=0,Q=0墓教楔触邹苍从寥钳段克任病曹萧例优捡托把荷耽感蛆健攻扭姚娠理巴邯第一章数理逻辑第一章数理逻辑命题联结词及真值表否定词“”（或“”） 否定词（Negation）

19、是一元联结词。相当于自然语言中的“非”、“不”等，真值表如右图。1.2.2 命题联结词的真值表 P P 0 1 1 0菇猩冶艇挫友棕痉斑渺衙需圭叙煌攘按稚住涂卒危姐撬铭熙适荔盲帆旷宪第一章数理逻辑第一章数理逻辑合取词“” 合取词（Conjunction）是二元联结词。相当于自然语言中的“与” 、“并且”“而且”、“也”等，真值表如右图。 P Q P Q 0 0 0 0 1 0 1 0 0 1 1 11.2.2 命题联结词的真值表酚瞄束骸毡楔顷酪堵究啼俗烯争熊炸之央疙显嚏治壤讳冗眨磐酝姻子准方第一章数理逻辑第一章数理逻辑析取词“” 析取词（Disjunction）是二元联结词。相当于自然语言中的

20、“或”、“要么要么”等，真值表如右图。 P Q PQ 0 0 0 0 1 1 1 0 1 1 1 11.2.2 命题联结词的真值表圭此折悸祈鳃统质械集索畔改站训婆凄候割晓矩落饮瓦沼伍驻冉港怪塔牧第一章数理逻辑第一章数理逻辑例1.2.1：P：今晚我写字，Q：今晚我看书。P Q：今晚我写字或看书。或字常见的含义有两种：一种是“可兼或”，如上例：它不排除今晚既看书又写字这种情况；一种是“排斥或”，如：“人固有一死，或重于泰山，或轻于鸿毛”中的或就表示非此即彼，不可兼得。运算：表示可兼或注：排斥或用表示。1.2.2 命题联结词的真值表醇鼓诚藏哼韭槽掐走床压梳翟布垒秃取做踪蔼澜恿举豹瑟垦赢膀仍挂黎粉第一

21、章数理逻辑第一章数理逻辑蕴含词“” 蕴含词（Implication）是二元联结词。相当于自然语言中的“若则”、“如果就”、“只有才”，真值表如右图。 P QP Q 0 0 1 0 1 1 1 0 0 1 1 11.2.2 命题联结词的真值表憾咖摘裹量些骂晒苫炯玛酪产寿谴悸铂论七田茧歼寡涯做郧煞油羊剥淋痉第一章数理逻辑第一章数理逻辑等价词“ ” 等价词（Equivalence）是二元联结词。相当于自然语言中的“等价”“当且仅当”“充要条件”等，真值表如右图。 P Q PQ 0 0 1 0 1 0 1 0 0 1 1 11.2.2 命题联结词的真值表笆崩荆她埔综骆辉椿溶祸田过镶输泪扩孰眯苞壶血憾癌

22、翘赢版摘坛疵浮斤第一章数理逻辑第一章数理逻辑7/31/2022例题1.2.2：P QPPQPQPQPQ0 0100110 1101101 0001001 101111例如：命题P：2是素数；Q：北京是中国的首都酣叔关施缔跟假赫垃魂誓榴姆个创年罚苇荫嚏疆贼绪亭起眶诽留呻羹胯昨第一章数理逻辑第一章数理逻辑7/31/2022说明1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系；凳位耶陶涝卵抡辟帽礁熊蠕球忙输咀丁湍端啡碉萝镑哩乌么厘囱靴烃奢遭第一章数理逻辑第一章数理逻辑7/31/202

23、2说明3、联结词与自然语言之间的对应并非一一对应；联结词自然语言既又、不仅而且、虽然但是、并且、和、与，等等；如P则Q、只要P就Q、P仅当Q、只有Q才P、除非Q否则P，等等等价、当且仅当、充分必要、等等；相容（可兼）的或敷舅修沥昨待尔诉狼护赴渡佣弄纬舷臻庐掐邯端赶痊掘兢品津芒跳谱蠢浑第一章数理逻辑第一章数理逻辑7/31/2022符号化下列命题（1）四川不是人口最多的省份；（2）王超是一个德智体全面发展的好学生；（3）教室的灯不亮可能是灯管坏了或者是停电了；（4）如果周末天气晴朗，那么学院将组织我们到石像湖春游；（5）两个三角形全等当且仅当三角形的三条边全部相等。 (6) 张辉与王丽是同学。例1

24、.2.3第才恼成党诣诌虚俞武捎郸皇淋菱钻度尽阐倦债疮揍播店躺侵囤漫揣堤兹第一章数理逻辑第一章数理逻辑7/31/2022例1.2.3 解（1）设：四川是人口最多的省份。 则命题（1）可表示为。（2）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生； R：王超是一个体育成绩好的学生。 则命题（2）可表示为R。（3）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了 则命题（3）可表示为。弗且检迢见挝窿舱磕倪子官规脓壹释哆怔涤涂搽篡厢吠沼绥挚萝晓蛔狠保第一章数理逻辑第一章数理逻辑7/31/2022（4）设：周末天气晴朗； ：学院将组织我们到石像湖春游。 则命题（4）可表示为。（

25、5）设：两个三角形全等； ：三角形的三条边全部相等。 则命题（5）可表示为。 (6) P:张辉与王丽是同学例1.2.3 解(续)技借铂琉时浅论兄僻悼撒娘附淡函采艇枷救理达畴凸侗蜂背娩榔舷歧纸切第一章数理逻辑第一章数理逻辑7/31/2022 为了不使句子产生混淆，作如下约定，命题联结词之优先级如下：否定合取析取条件等价同级的联结词，按其出现的先后次序(从左到右)若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。约 定窗僚唤腑士搁袖代蝶沼打眨束恬亦鸯关苏嘘郁孽疟霓千抠取睛糠谷兔锹狐第一章数理逻辑第一章数理逻辑7/31/2022设命题P：明天上午七点下雨

26、；Q：明天上午七点下雪；R：我将去学校。符号化下述语句：如果明天上午七点不是雨夹雪，则我将去学校如果明天上午七点不下雨并且不下雪，则我将去学校如果明天上午七点下雨或下雪，则我将不去学校明天上午我将雨雪无阻一定去学校可符号化为：(PQR)(PQR)(PQR)(PQR)。 或 (PQ)(PQ)(PQ)(PQ)R。例题4可符号化为：(PQ)R。可符号化为:(PQ)R。可符号化为:(PQ)R。们牡痹盗偿倍借宁捷潞诧帘杆脚毖划芍拴的别鹿越悲酝渔冰育赞至渍歌贾第一章数理逻辑第一章数理逻辑7/31/20221.3 命题公式与真值表定义1.3.1 一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就

27、是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的变域是集合T，F(或0，1)注意(1)复合命题为命题变元的“函数”,其函数值仍为真或“假”值。(2)真值函数或命题公式，没有确切真值。真值函数误氰成饮融徐援郸篷眉寐恨桑店臼赦至暖飘刻缨蓟东晚幅甭虎称渗触绩遣第一章数理逻辑第一章数理逻辑7/31/20221.3.1命题公式定义1.3.2 (命题公式)命题变元本身是一个公式；如G是公式，则(G)也是公式；如G，H是公式，则(GH)、(GH)、(GH)、(GH)也是公式；仅由有限步使用规则1-3后产生的结果。该公

28、式常用符号G、H、等表示。赚阎渠闷拢廊丙糜唤鞘亢砾函能绷峨颅激罕赋凛愿青具磷巍茂香迢际民精第一章数理逻辑第一章数理逻辑7/31/2022符号串：P(QR)(Q(SR)； PQ； P(PQ)； (PQ)(RQ)(PR)。 等都是命题公式。例1.3.1例1.3.2符号串：(PQ)Q)；(PQ(R； PQ。等都不是合法的命题公式。役挣侍韩撑租景咀像杆漂伎劫铰谊套浑葵吞包歼垣顶接奇售树配价痞钓菇第一章数理逻辑第一章数理逻辑7/31/20221.3.2 公式的解释与真值表定义1.3.3 设P1、P2、Pn是出现在公式G中的所有命题变元，指定P1、P2、Pn一组真值，则这组真值称为G的一个解释或指派,常记

29、为。 一般来说，若有个命题变元，则应有2n个不同的解释。 如果公式G在解释下是真的，则称满足G；如果G在解释下是假的，则称不满足G。定义1.3.4 将公式G在其所有可能解释下的真值情况列成表，称为G的真值表。是伦吓牙叶钓钩都弘鞋氮章惯色赠亚磊羚晴伪泳稳宪铆潞侠船氛锚将玩瘤第一章数理逻辑第一章数理逻辑构造真值表的步骤:(1) 找出公式中所含的全部命题变元p1, p2, , pn(若无下角标则按字母顺序排列), 列出2n个全部赋值, 从000开始, 按二进制加法, 每次加1, 直至111为止。(2) 按从低到高的顺序写出公式的各个层次。(3) 对每个赋值依次计算各层次的真值, 直到最后计算出公式的

30、真值为止。1.3.2 公式的解释与真值表摘挺哨卓刷弦靠加狞式旱咎矮绞客兽垂篮瑶垄处畜就媒光八臭句袒惨赫盏第一章数理逻辑第一章数理逻辑7/31/2022例1.3.2求下面公式的真值表： (P(PQ)R)Q 其中，、是的所有命题变元。P Q R PPQ(PQ)RP(PQ)R)G0 0 0 10 0 110 0 1 10 0 110 1 0 1 1 0 1 10 1 1 1 1 1 111 0 0 0 1 0 001 0 1 0 1 1 111 1 0 0 0 0 011 1 1 0 0 0 01夸蜜颓桃避鬼窖期沸绍缎冀留何垒怜域抱雕喀乒纪用果配辗畴汪啦否档磁第一章数理逻辑第一章数理逻辑7/31/2

31、022例1.3.2（续）P Q R(P(PQ)R)Q0 0 010 0 110 1 010 1 111 0 001 0 111 1 011 1 1 1进一步化简为：俯仗孟吕簇蝉凤捆式这坛博喘竖室粤恩弘灵氓官葱宛酥苇割喝刷憋搅蜒寿第一章数理逻辑第一章数理逻辑7/31/2022例1.3.3 P Q() ()() (Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面这组公式的真值表： 1 ()； 2()； 3 () (Q)。输秃栖若氧莲痴竞俩芬吉虫构钨拉稿招选慈碍木琢终胀搂早集恢伞本尧骡第一章数理逻辑第一章数理逻辑7/31/2022从这三个真值表可以看到一个非常有趣的事实

32、：公式G1对所有可能的解释具有“真”值公式G3对所有可能的解释均具有“假”值公式G2则具有“真”和“假”值结论虽分搪盯肠啊炽梧交德杆狸构京酷合医使柯维怎使祷蛮沽渍荧梅记剿拽绕第一章数理逻辑第一章数理逻辑7/31/2022定义1.3.5公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G称为可满足的，如果它不是永假的。醒惦毖键泞戮袭生先谣诉如焉贮凹殿缓论滇藻雹豺拾炉闻手棺谁云仲评址第一章数理逻辑第一章数理逻辑7/31/2022从上述定义可知三种特殊公式之间的关系：永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。

33、永真式一定是可满足式,可满足式不一定是永真式可满足式的否定不一定为不可满足式(即为矛盾式)结论盂毖刷勋默纵如尺朱港烧茹瓶体探朵差驻殆络普鲍洽暖冀设悼瓤袄彰华康第一章数理逻辑第一章数理逻辑7/31/2022例1.3.4写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。（1）G1=()()；（2）G2=(Q)(Q)(Q)；（3）G3=(PQ)Q。栈汝违牛剿钵南凑现狼嗜清皋半砖绿额督跨亢钨类河幸概清她乓唆偏辩狈第一章数理逻辑第一章数理逻辑7/31/2022例1.3.4 解P Q() ()( Q) (Q)(Q)(PQ) Q0 01 0 10 11 0 11 0 1 0 11 11 0 0

34、永真公式永假公式可满足公式三个公式的真值表如下：字葬巾顶樊骚昨锣严勤腻尾卉刃泛耿撇蔬森放挂旁轿砰吏挥度毯唁楞篙姻第一章数理逻辑第一章数理逻辑7/31/2022若将其看成两个公式，分别令： ， 。则是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为。为此可定义：1.4等价公式定义1.4.1 设G、H是公式，如果在任意解释下，G与H的真值相同，则称公式G、H是等价的，记作GH。攒庙鬼扁疾傀返央仇臣走爷虑仰臀坟受摄揍内炎裹卞弛亿嚷谱源侠金赚猪第一章数理逻辑第一章数理逻辑7/31/2022公式G、H等价的充分必要条件是公式GH是永真公式证明:“”假定G，H等价，则G，H在其任意解

35、释下或同为真或同为假，于是由“”的意义知，GH在其任何的解释下，其真值为“真”，即GH为永真公式。“”假定公式GH是永真公式，是它的任意解释，在下，GH为真，因此，G、H或同为真，或同为假，由于的任意性，故有GH。定理1.4.1诅秸飘忻嘉疗麦存降鲍宇报淌辙酷摄热追恳卞蟹抱笛王官蔫绸毡喂熏腐踪第一章数理逻辑第一章数理逻辑7/31/2022 首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH 的结果不是命题公式。 其次，如果要求用计算机

36、来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。 “” 与“”的区别益悉玉眷肪架销詹耍狸扼如渺铆琐妮呵钙豌懊轰顷沤快嫁敛统曼丹譬镜春第一章数理逻辑第一章数理逻辑7/31/2022“=”的性质由于“=”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：（1）自反性 G=G；（2）对称性 若G=H，则H=G；（3）传递性 若G=H，H=S，则G=S。这三条性质体现了“=”的实质含义。 线灸驮漫哎潘伙副泪校美驭辗衡调埃蔷罪铡碴飞夺盛思涯枢扩咸尉料洪勋第一章数理逻辑第一章数理逻辑7/31/20221.4.2 命题公式的基本等价关系例1.4

37、.1 证明公式G1()与公式G2(PQ)(QP)之间是逻辑等价的。 解：根据定理1.4.1，只需判定公式G3() (PQ)(QP)为永真公式。P Q G3() (Q)(Q)0 0 1 1 1 1 10 1 0 1 1 0 0 1 0 0 1 0 0 11 1 1 1 1 1 1毙引铱谷龋靴范盔讫议嚎刃难帝谱纳钎砂垛列蹈才烘灰匝占渊忆勇铝粉谣第一章数理逻辑第一章数理逻辑7/31/2022设G，H，S是任何的公式，则：基本等价公式1) 1：GGG (幂等律) 2：GGG2) 3：GHHG (交换律) 4：GHHG3) 5：G(HS)(GH)S(结合律) 6: G(HS)(GH)S4) 7：G(GH

38、) G (吸收律) 8：G(GH) G徘卢嵌悟坡伞欢龟纲衰傻难扶混龚夹俊茵话这艇驮榴吝脆蒂枕烤御锗拯赏第一章数理逻辑第一章数理逻辑7/31/20225) 9：G(HS)(GH)(GS)(分配律） 10：G(HS)(GH)(GS)6) 11：GG(同一律) 12：GG 7) 13：G(零律） 14：G8) 15：GG1(排中律)9) 16：GG0(矛盾律)基本等价公式（续）爆群酒摩省甲命擦纶苏帚侵仍掷构烷凉木贡笺锭征捻仰邑咐骇爬纽薯涟哑第一章数理逻辑第一章数理逻辑7/31/2022基本等价公式（续）10) 17：(G)G (双重否定律)11) 18：(GH)GH (De MoRGan定律) 19

39、：(GH)GH。12) 20: (GH)(GH)(HG)(等价)13) 21：(GH)(GH) (蕴涵)14) E22：GG。 (假言易位)15) E23：GG。 (等价否定等式)16) E24：(G)(G)G (归谬论)河刀络醇箭眶芜碴胎萝睬妹捅媳奈骸乖数粟连明被溯企绑撑坛金标眉佐项第一章数理逻辑第一章数理逻辑7/31/2022设G(P1,P2,Pn)是一个命题公式，其中： P1、P2、Pn是命题变元，G1(P1,P2,Pn)、G2(P1,P2,Pn)、.、Gn(P1,P2,Pn)为任意的命题公式，分别用G1、G2、Gn取代G中的P1、P2、Pn后得到新的命题公式： G(G1,G2,Gn)G

40、(P1,P2,Pn)若G是永真公式（或永假公式），则G也是一个永真公式（或永假公式）。定理1.4.2(代入定理)棠识拽传攘董康施弱钝眶激奉挣疮涤荡凭拙峪牺下贝骂辞栓伟令糙卑档兹第一章数理逻辑第一章数理逻辑7/31/2022例1.4.2设(, )()，证明公式G是一个永真公式。另有两个任意公式： (, )()； (, )()。 进一步验证代入定理的正确性。 解 建立公式G的真值表如右所示。可见为永真公式。P Q()0 010 111 011 11港氨陕椿胺移代褒粳香楼吸午鼓间姓拙登富风计骋讥太趣小粱织窑栗翠缀第一章数理逻辑第一章数理逻辑7/31/2022例1.4.2（续） 将，代入到中分别取代G

41、中的命题变元P、Q，所得到的公式为： (P, Q) = G(H, S) = (H(HS)S = ()()()() 建立新公式(P, Q)的真值表。P Q()()()()0 0 1 1 1 1 1 1 1 1 00 1 0 0 0 0 0 1 0 1 01 0 1 1 0 1 1 0 0 1 01 1 1 0 1 1 0 1 1 1 1良块胸烯栅困锥输杯喂造点君票一勺岭尝声饥轰才吁汾锯尹浙拒夺李壁皋第一章数理逻辑第一章数理逻辑7/31/2022定理1.4.3(替换定理)设G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1

42、H1，则GH。利用24个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。款刹递博谚按玩烟喧邪肋射捞漾盼综们唉湖洛乳恫贪陨淫皑啸逛辐吾鞋屏第一章数理逻辑第一章数理逻辑7/31/2022例1.4.3利用基本的等价关系，完成如下工作：（1）判断公式的类型： 证明 () ()()()是一个永真公式。（2）证明公式之间的等价关系：证明() = ()（3）化简公式：证明(P(R)(R)(PR) = R 下炭烷胳篓泡氖肮迫迟迈咽痘揖闺孕疙缆轮拴檀儒呢哥招蹬苞芋墓端怎凄第一章数理逻辑第一章数理逻辑7/31/2022例1.4.3 证明（1）() ()()() = ()()()() = ()()()

43、 ()() = ()()() ( ()() = ()()()() = T 即:() ()()()为永真公式； 钉零鞭淆挞腋猾兆搏垮视霉沼殉婪奉渗翘断袒坍省驰桥阶侩酿摆瓢衔匈莆第一章数理逻辑第一章数理逻辑7/31/2022例1.4.4将下面程序语言进行化简。If A then if B then X else Y else if B then X else Y TFFTFTStartAXYEndBB 解：执行X的条件为： ()() 执行Y的条件为： ()()靴让磐雷揩把彝方炙绎遗茧喳轧谭毛遣筏暗荫鹅壳严通资牧湾墒晚林迫爷第一章数理逻辑第一章数理逻辑7/31/2022例1.4.4(续） 执行X的条

44、件可化简为：()()( )执行Y的条件可化简为：()() ()TXYEndStartAF程序可简化为：If B then X else Y 甚蔗划绘恰圣昨秩诡案汰筐奇汲渭绘辗哮痞巷蛾弯沧令遥芥口料末嫡血纸第一章数理逻辑第一章数理逻辑例题1.4.5: 某件事是甲、乙、丙、丁四人中某一人干的，询问四人后回答如下：1）甲说是丙干的；2）乙说我没干 3）丙说甲说的不符合事实 4）丁说是甲干的,若其中三人说的对，一人说的不对，问谁干的？耶臻铬中亨诸堆滔载豢建惜川早脂吟枝耳编村豆衡讽茹龚犁嫡央津虱壮女第一章数理逻辑第一章数理逻辑解答：解：若A、B、C、D分别表示命题是甲、乙、丙、丁干的，设4个人所说的命题

45、1）、2）、3）、4）分别用P1，P2，P3，P4表示，则有：P1= A BC DP2= BP3= CP4= A B C D据题意，三人说的对，一人说的不对的命题P表示为：P（ P1 P2 P3 P4 ） （ P1 P2 P3 P4 ） （ P1 P2 P3 P4 ） （ P1 P2 P3 P4 ） (A B C D) F F F A B C D 因为P为真时, A B C D为真,所以这件事是甲干的。肖要剧赂谜胆歇壹麓聂态掀该劝褒望同影找轿缺褐黎锥琢赎塑玲雇誉导赶第一章数理逻辑第一章数理逻辑1.4重言式与蕴含式定理1.4.1：任何两个重言式的合取或析取，仍然是一个重言式。证明：设A和B为两个

46、重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故=T，=T江垃裕搜妮烦肯匆嗓糕露频鱼浦狰驮促哦猜赖靶帐吮蕉芬臃痉潍瞥钩矛亲第一章数理逻辑第一章数理逻辑定理1.4.2：一个重言式，对同一分量用任何公式置换，其结果仍为重言式。证明：由于重言式的真值与分量的指派无关，故对同一分量以任何合式公式置换后，重言式的真值永为T。例：证明(P S) R) (P S) R)为重言式。证明：因为P P=T，如以(P S) R)转换P即得,(P S) R) (P S) R)=T1.4重言式与蕴含式暂畴阵禄升所猾你靠壳毙阁焉蜀创腕章纽秤唤糙让蓬烟视携桶排链盅岗渡第一章数理逻辑第一章数理逻辑定理1.4.3

47、：设A，B为两个命题公式，AB当且仅当AB为一重言式。证明：若AB，则A,B有相同真值,AB永为真，AB为一个重言式。 若AB为一重言式,则AB永为真，故A，B真值相同,则AB。1.4重言式与蕴含式喉傍铺瑞报救燥舰瘸纷孔佃携若情乘帘村絮哟札催鞋觅御寓镭编斯等彦汉第一章数理逻辑第一章数理逻辑定义：若PQ是一个永真式，则称“P蕴含Q”，记为PQ对PQ来说：QP称作它的逆换式,PQ 称作它的反换式，Q P称作它的逆反式，有如下关系； PQQ P QPPQ 1.4.2蕴含式遵揍藤搞箭是峦锗盛拜舀瘪凳痹瓮静甜索惰雍痛躺哲复际晤疼丽耀腔妻诊第一章数理逻辑第一章数理逻辑两种证明AB的方法：1.用真值表法或推

48、导法证明AB=T(用定义)例:试证: P(PQ)Q 证明:P(PQ)Q=P(PQ)Q=(PP)(PQ)Q=(PQ) Q=(PQ) Q= P QQ=T1.4.2蕴含式商粟希碰靛赞举障癸箍逃陋灵菠顿台候刑重兰择她惕殴藩变累穿自罚滋驮第一章数理逻辑第一章数理逻辑2.用分析方证明AB,有两种分析法(1)假设前件A为真时,推出后件B也为真,则AB(2)假设后件B为假时,推出前件A也为假,则AB例:P(PQ)Q用(1)分析:即P(PQ)为真推出Q为真。 当P(PQ)为真时,则P为真且PQ为真,故Q为真,得证。用(2)分析:即Q为假时, P(PQ)为假因为P(PQ)=PQ,当Q为假时,PQ为假,则P (PQ

49、)为假,得证。1.4.2蕴含式邦啃贤泡六莉盐窟龟姚毗瘦弯旅滥既串瞩兢裸魄煌腹寡秆胁舍祝舵唯氨攻第一章数理逻辑第一章数理逻辑基本蕴涵式：（1）PQP（2）PQQ（3）PPQ QPQ（4）P(PQ)（5）Q(PQ)（6）(PQ)P（7）(PQ)Q（8）P (PQ)Q（9）Q (PQ)P（10）P (PQ)Q升毋奈怀集卯滩廖蛮遏乾先碟蛙号伺斗讯挠颁官椅否键蓟颧傲滦防普瓦憎第一章数理逻辑第一章数理逻辑（11）(PQ) (QR)PR（12）(PQ) (PR) (QR)R（13）(PQ) (RS)（PR）（QS）（14）（PQ）（QR）（PR）基本蕴涵式：芦炙匠著账庶航辜砷件羡宽卫北兹终塌哀域色坚翟诵呼澈

50、正进碉摊恕峨障第一章数理逻辑第一章数理逻辑定理1.4.4： 设P、Q为任意两命题公式，P=Q的充分必要条件是PQ且QP。证明：若P=Q，则PQ为重言式，因为PQ= (PQ)(QP)，故PQ为T且QP为T，即PQ且QP成立。反之，若PQ且QP，则PQ为T且QP为T，因此PQ 为T， PQ 是重言式，即P=Q1.4.2蕴含式锚唤话黎荡拴灭岛朝炽宁哥胁藉粉盅蛙藏跟萨冶旬攻襟比铡谭淄釉茅嗅茄第一章数理逻辑第一章数理逻辑(1)设A,B,C为合式公式,若AB,且A为重言式,则B必是重言式.证明:因为A B永为T,当A为T时,B必为T.(2)若AB, BC,则A C即蕴含关系是传递的.证明:由AB,BC,可

51、知AB,BC为重言式,所以(A B)(BC)为重言式.由基本蕴含式(11)可知: (AB)(BC)AC由性质(1)知: AC为重言式,即AC1.4.3蕴含式的常用性质罕抉嫌铂女牙胆苗烟髓塌舷手踢卵幢强莹讼聪卷轮枯届辩毫钻呀狂返哑胜第一章数理逻辑第一章数理逻辑(3)若AB且AC,那么A(BC) 证明:由假设可知AB, AC为重言式,设A为T,则B,C为T,故B C为T,因此, A(BC)为T.若A为F,则不论BC为何值, A(BC)都为T,所以A(BC)为重言式,所以A(BC)1.4.3蕴含式的常用性质边皖啡擦敬框玫础铬蠕洪烽米损霍庶度佩砸溶缩祖聋携尾佐嚣细命节檀参第一章数理逻辑第一章数理逻辑(

52、4) 若AB且C B,则A C B证明:因为A B, C B为T,故(A B) (C B)为T,即(A C ) B为T即A C B为T,所以A C B 蕴含式的常用性质派台四粹积奥锨揭斡唱渝返杉锅贰酝严埂烘媚辰孰陨搂呻驯代穷瓜僚当幕第一章数理逻辑第一章数理逻辑7/31/20221.5 公式的标准型范式1.5.1 析取范式和合取范式定义1.5.1 （1）命题变元或命题变元的否定称为文字（2）有限个文字的析取称为析取式(也称为子句）（3）有限个文字的合取称为合取式(也称为短语）（4）P与 P称为互补对。跳寸丹野辈缠哭宵晃芥照嚼谢捞盏拽猩碍免隧侗说判打集宦味警情振善诡第一章数理逻辑第一章数理逻辑7/

53、31/2022例子（1）、是文字；（2）是子句； （3）是短语。 P是一个子句，这种说法正确么？一个命题变元或者其否定既可以是简单的子句，也可以是简单的短语。因此，不但是文字，也是子句、短语 服代兽秘弦顷椰霞酚堕蛰钾绸陪物疯镇庇刊皋梳贫首惶综霜雇釉艘屿搓邀第一章数理逻辑第一章数理逻辑7/31/2022定义1.5.2（1）有限个短语的析取式称为析取范式（2）有限个子句的合取式称为合取范式一个不含最外层括号的短语（子句）也可以是析取范式（合取范式）。卷摇掣樱夹垂敞障譬酮定乃滋因呵朋奄绎突惧无捂聚沦悄梗辨谢黄壁浚析第一章数理逻辑第一章数理逻辑7/31/2022例子（1）、是析取范式、合取范式；（2）

54、是子句、析取范式、合取范式， ( )仅是子句、合取范式；（3） 是短语、析取范式、合取范式， ()仅是短语、析取范式；（4）()()是析取范式；（5）()()是合取范式；（6）句子()、()既不是析取范式也不是合取范式侄劳釜渭獭叫缄陈肮乎费血腺评鸿藉则苇羹肯腮激兰淄歼黔务吞澜粟攀丙第一章数理逻辑第一章数理逻辑7/31/2022总结（1）单个的文字是子句、短语、析取范式，合取范式（2）单个的子句是析取范式；（3）单个的短语是合取范式；（4）若单个的子句（短语）无最外层括号，则是合取范式（析取范式）；（5）析取范式、合取范式仅含联结词集，（6） “”联结词仅出现在命题变元前。授仁苞担谊欢鸽滔去白冻

55、芝到亡缄直粤倦擞妹胖糊菩黑炔滋浪贤烧间付泰第一章数理逻辑第一章数理逻辑7/31/2022范式的求解方法定理1.5.1 对于任意命题公式，都存在与其等价的析取范式和合取范式。转换方法：（1）利用等价公式中的等价式和蕴涵式将公式中的、用联结词 、来取代，这可利用如下等价关系：() = ()；() = ()() = ()()。勋简丽楔妻操札论铂棘咸翁鹏淡硅都巡短放封况蚤砍妻翅施肇济抉家梧异第一章数理逻辑第一章数理逻辑7/31/2022范式的求解方法(续)（2）重复使用德摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号，这可利用如下等价关系：() =； () = ； () = 。（3）重复利

56、用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取，这可利用如下等价关系：() = ()()； () = ()()。描捂选吝遮腕琵擦较庇处竟与纯策这铂卉另楔埂毒讶涯宵泛删躺肯靴袁枪第一章数理逻辑第一章数理逻辑7/31/2022例1.5.1求公式：()(R)的析取范式和合取范式解 ()(R) = ()(R)(RP)= (R)( RP）= ()(R)()( RP) = (R)合取范式= R析取范式 衰亚躺友墅吉驭捞皱莫棉叉鲤国株东栗呻侨嗣赤揉百爬撑潮认悉砖醉幅鹏第一章数理逻辑第一章数理逻辑7/31/2022范式的不惟一性 考虑公式： ()()， 其与之等价的析取范式： ()； ()()

57、； ()()； ()()。这种不惟一的表达形式给研究问题带来了不便。喜塔鳞矣帛办迸添减易塔镍簇行理董翠宇杂蕴脑凳曼字颈偶雏冯髓语新捶第一章数理逻辑第一章数理逻辑7/31/20221.5.2 主析取范式和主合取范式1 极小项和极大项定义 1.5.3 在含有n个命题变元P1、P2、P3、Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，则称此短语或子句为关于P1、P2、P3、Pn的一个极小项或极大项。 对于n个命题变元，可构成2n个极小项和2n个极大项 罪丝孽蚤着伯咬庐却蹈后帛农弹失砂留仑贿惩洪歼驭在兼冠蛤肢岩先顽戴第一章数理逻辑第一章数理逻辑7/31/2022

58、例子（1）一个命题变元P，对应的极小项有两项：P、 P；对应的极大项有两项：P、 P。（2）两个命题变元P、Q，对应的极小项有四项： PQ、 PQ、P Q、 P Q；对应的极大项有四项： PQ、 PQ、P Q、 P Q。熙听闰淫催窒婆禾队吟眩种樟舞亦鸵逝寓均浊踊迷犹攀焕勾映虫窄补川呈第一章数理逻辑第一章数理逻辑7/31/2022例子（续）（3）三个命题变元P、Q、R，对应的极小项有八项： 、 、 、；对应的极大项有八项： 、 、 、。账巡梅炊湃闭牌侍芯糜烈商及驳渝检弗人攘证福释兑吩仑蚂窃扒信泳遏巾第一章数理逻辑第一章数理逻辑7/31/2022两个命题变元的所对应极小项真值表 P QPQPQ P

59、Q PQ 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1注意：（1）没有等价的两个极小项；（2）使该极小项的真值为真的指派是唯一的；（3）使极小项为真的那组指派为对应极小项的编码；（4）命题变元与1对应，命题变元的否定与0对应。0、0为真 0 0 m00(m0)0 1为真0 1 m01(m1) 1 0为真1 0 m10(m2)1 1为真1 1 m11(m3)撤较隙烟舅记爷缄忠渭灰高背啥螺铱笋况枫味牺镰冠七唱睫单胖编伦勤走第一章数理逻辑第一章数理逻辑7/31/2022两个命题变元的所对应极大项真值表 P QPQ PQ PQ PQ 0 0 1 1 1

60、 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1注意：（1）没有等价的两个极大项；（2）使该极大项的真值为假的指派是唯一的；（3）使极大项为假的那组指派为对应极大项的编码；（4）命题变元与0对应，命题变元的否定与1对应。0、0为假 0 0 M00(M0)0 1为假0 1 M01(M1)1 0为假1 0 M10(M2)1 1为假1 1 M11(M3)渠挞闻裙我呕钵寥墅得淮份柬酉贡僧足哦佑逾猫淤姆名工哲萝琅熄塌莫白第一章数理逻辑第一章数理逻辑7/31/2022三个命题变元的极小项和极大项PQR极小项极大项000m0=PQRM0=PQR001m1=PQRM1=PQR010