湖南大学离散数学教案--命题逻辑.ppt

1、第一章 命题逻辑,杨圣洪引言 逻辑学是推理的基础，在社会学、自然科学尤其计算机学科中得到普遍应用。 数理逻辑是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在程序设计、数字电路设计、计算机原理、人工智能等计算机课程得到了广泛应用。 命题逻辑是数理逻辑的基础部分， 但究竟什么是命题？ 如何表示命题？ 如何构造出复杂的命题？ 在本章将讨论这些问题。,1.1 命题及联结词 对错确定的陈述语句称为命题。如： (1)湖南大学是一本学校。 (2)命题逻辑是计算机科学的基础课程。 (3)命题及联结词是命题逻辑

2、的最基础的内容。 (4)4是素数。 (5)湖南大学坐落于湘江以东。 (6)2011年湖南长沙轻轨通车。 其中(1)、(2)、(3) 与事实相符，是对的、正确的，称为真命题，或者称命题的值为“真”，简记为T或数字1。 而(4)、(5)明显与事实不相符，是错的、不正确，称为假命题，或称命题的值为“假”，简记为F或数字0。 陈述句(6)的正确性，到2011年12月时能确定的，若届时开通了则它是对的、为真命题，否为假命题。,1.1 命题及联结词 对错确定的陈述语句称为命题。如： (7) x与y之和为100，其中x为整数，y为整数 (8)1加1等于10 (7)的对错不确定的。当x为50、y为50时是对的

3、，当x为51、y为52时是错的。 (8)的对错是不确定的，为二进制时正确，当为八进制、十进制时是错的，因此这两个陈述句不是命题。 (9)岳麓山的红叶真美呀！ (10)动作快点！ (11)你是离散数学老师吗？ 这三个语句不是陈述语句，因此不是命题。,1.1 命题及联结词 对错确定的陈述语句称为命题。如： (12)我在说假话。 (13)我只给自己不能理发的人理发。 (14)派出所说:必须先房子再能上户口 单位后勤说:必须先有户口才能分房 你能上到户口与要到房子吗? 这是一个悖论，其真值不能确定，故不是命题。,1.1 命题及联结词 对错确定的陈述语句称为命题。如： (13)我既要学程序设计，又要学离

4、散数学。 (14)我们早餐在公寓食堂或外面早点摊上吃。 (15)我不是数学院的学生 这三个陈述句都与事实相符，是对的，是真命题，其值为真(T/1)。 其中(13)与(14)可分解为另外二句话的组合， 而(15)是对“我是数学院学生”的否定，这些语句称为“复合命题”，不能再分解的语句称为“简单命题”或“原子命题”，为了便于推理与书写，常用小写字母表示简单命题或原子命题。,1.1 命题及联结词 简单命题组合成复杂命题时所使用的辅助词称为“联结词”。 命题逻辑中的联结词归纳为以下5种。 合取：C语言中 期末考试后我为年级第8名，所以老爸应该给我买iphone4。这是假言推理。 A(AB)B 从形式上

5、看，结论B是AB的后件，推导的结果是将后件分离出来，故也称为分离原则。 利用假言推理规则或分离规则，结合析取、合取、否定的定义，只要不歉麻烦，几乎可推出所有的结论。 为了提高推理效率，还需要学习、掌握某些推理规则。,例题 求证 AAB 采用定义1来证明，即证明AAB为永真式。 AAB A(AB) (的等值式) (AA)B (结合律) 1B (析取的性质) 1 (析取的性质) 所以AAB,例题 求证 ABA ABA (AB)A (的等值式) (AB)A (德摩律) ABA (结合律) 1B (析取的性质) 1 (析取的性质) 类似 ABB 根据的定义可知AB为真时，A与B均为真，因此由推理定义2

6、可知 ABA， AB B 。 同样由的定义可知A为真时 AB为真，故由推理定义2可知AAB。 然这3个推理式不必记忆！推理定义2效率较高,例题 求证 (AB)(BC)(AC) 根据定义1，要证明下式为永真式。 (AB)(BC) (AC) (AB)(BC) (AC) (的等值式) (AB)( BC) (AC) (的等值式) (AB) (BC) (AC) (德摩律) (A B)(A C )(B B) (BC) (AC) (分配律) (A B)(A C )1(BC) (AC) (析取的性质) (A B)(A C )(BC) (AC) (析取的性质) (A BAC)(A CAC )(BCAC) (分配

7、律) (1 BC)(1 CC )(BA1) (析取的性质) 111 (析取的性质) 1 (析取的性质) 判断公式的类型，除等值演算外，还有真值表与范式等方法。,例题 求证 (AB)(BC)(AC),由上表可知， (AB)(BC) (AC) 为重言式， 由定义1可知(AB)(BC) (AC)。 这是有名的传递律，要记住呀！,例题 求证 (AB)(CD)(AC)BD 利用定义1证明了假言推理规则(AB)AB,传递规则(AB)(BC)(AC)。 有了这2条规则后,可用定义2来证明推理式了。 由于这2条规则的结论中没有析取式，只有条件式，因此将题中结论转换为 BD,题设中转换为 (1)(AB)(CD)

8、(AC)为真前提条件(定义2的套路) (2) (AB)为真(1)及合取的性质 (3) (CD)为真(1)及合取的性质 (4) (AC)为真(1)及合取的性质 (5)(BA)为真(2)及(AB) (BA) (6) (AC)为真(4)及(AC) (AC) (7) (BC)为真(5)、(6)及推理传递律 (8) (BD)为真(7)、(3)及推理传递律 (9) BD为真(8)及(BD) BD,例题 求证 (AB)(CD)(BD)AC 可用传递律来证明，还有更高效的方法 由定义1只要证(AB)(CD)(BD)(AC)为重言式，而 (AB)(CD)(BD)(AC) (AB)(CD)(BD) (AC) (

9、(AB)(CD)(BD)A)C) (AB)(CD)(BD)A)C) (AB)(CD)(BD)A)C 故只需证 (AB)(CD)(BD)A)C为重言式 即只需证明(AB)(CD)(BD)AC A从结论中挪到前提中，这种技巧称为附加条件(CP)法，适合于结论为条件式的情形。,例题 求证 (AB)(CD)(BD)AC (1)(AB)(CD)(BD)A为真 CP规则及前提 (2)AB为真(1)及合取的性质 (3)A为真(1)及合取的性质 (4)B为真(2)(3)及假言推理式(AB)AB (5)BD为真(1)及合取的性质 (6)BD为真(5)及BDBD (7)D为真(4)(6)及假言推理式(BD)BD

10、(8)CD为真(1)及合取的性质 (9)DC为真(8)及原命题逆否命题 (10)C为真(7)(9)假言推理式(DC)DC 提示：熟练后可不写(1)式，直接引用(2)(3)(5)(8)！,例题 求证 (AB)(CD)(BD)AC (1)AB为真前提条件 (2)A为真附加前提 (3)B为真(1)(2)及假言推理式(AB)AB (4)BD为真前提条件 (5)BD为真(4)及BDBD (6)D为真(3)(5)及假言推理式(BD)BD (7)CD为真前提条件 (8)DC为真(7)及原命题逆否命题 (9)C为真 (6)(8)假言推理式(DC)DC,求证 (WR)V, V(CS),SU,C,UW 提示：此处

11、用逗号简写前述各例中的合取式，从而鼓励大家直接引用前提。 利用假言推理、传递律及前面所学的等值式，可以推出结论。在黑板上演示一番 考虑到本题的结论是W，可采用反证法。 根据定义2可知“当前提为真时结论也为真”， 反证法是“前提为真时，假设结论不为真即结论的否定为真”。 即基于前提、结论否定进行推理。 如果推出了一个矛盾的结论出来，则说明“假设结论不为真”是错误的，即表示结论只能为真了,求证 (WR)V, V(CS),SU,C,UW (1)W为真假设结论W为0即 W为1(真) (2)W为真 (1)与否定的性质 (3)(WR)为真 (2)与析取的性质 (4)(WR)V为真前提条件 (5)V为真(4

12、)(3)假言推理(WR)V)(WR) V (6)V(CS)为真前提条件 (7) (CS)为真(5)(6)假言推理(V(CS)V(CS) (8) CS为真 (7)与条件式的等值式CSCS (9)C为真前提条件 (10)S为真(8)(9)与假言推理(CS)( C)S (11) SU为真前提条件 (12)U为真(10)(11)假言推理(SU)SU (13) U为真前提条件 显然(12)与(13)矛盾，故假设有误！,应用题 天气情况要么天晴，要么天下雨；如果天晴我去爬山，如果我去爬山那么我回来后不做饭， 结论是：如果我已做饭那么肯定天下雨了。 解：用M表示天晴， R表示天下雨， C表示爬山， F表示做

13、饭，则问题可表示为 MR，MC，CFFR (MR)(MR) ，MC，CFFR,应用题MR，MC，CFFR (1)F为真附件前提 (2)CF为真前提条件 (3)FC为真(2)的等值式 (4) FC为真(3)的等值式 (5) C为真(1)(4)的假言推理 (6) MC为真前提条件 (7)CM为真(6)的等值式 (8) M为真(5)(7)的假言推理 (9) MR为真前提条件 (10) MR为真(9)的等值式 (11) R为真(8)(10)的假言推理,应用题MR，MC，CFFR (1)F为真附件前提 (2)CF为真前提条件 (3)FC为真(2)的等值式 (4) FC为真(3)的等值式 (5) C为真(

14、1)(4)的假言推理 (6) MC为真前提条件 (7)CM为真(6)的等值式 (8) M为真(5)(7)的假言推理 (9) (MR)(MR)为真前提条件 (10) (MR) (MR)为真(9)的等值式 (11) MR (MR)为真(10)的等值式 (12) MR为真(8)与析取的定义 (13) (MR)为真(11)(12)的假言推理 (14) R为真(13)与合取的定义,定义2证明推理式的规律 (1)利用“条件等值式”，尽可能将前提、中间结论及最终结论中的“析取式”转换为“条件式”，以便可引用假言推理、传递律。 (2)如果结论为条件式，则将条件式的前件做为附加前提。CP原则 (3)如果结论的否

15、定在前提中多次出现，可采 用反证法。 (4)每一步的推理理由可简化，如“前提条件”简写为“P”，“假言推理”可简写“M”，等值式只写“等值”或简写“E”。 (5)这种从前提出发，应用已证明的推理式，不断推出中间结论，最后推出结论的方式，称为自然推理，这是最常见的方式。,1.7消解规则 证明(AC)(BC)AB (1) (AC)为真前提条件 (2) A C为真与(1)等值 (3) BC为真前提条件 (4) C B为真与(3)等值 (5)CB为真与(4)等值 (6) AB为真(2)(5)传递律 (7) AB为真与(6)等值 因此当(AC)(BC)为真时，AB为真。 由于(AC(BC)中互补的公式C

16、、C同时消失了，称“AB”为 “(AC)，(BC)”的消解式。 因此在采用定义2进行推理时，只要(AC)、(BC)同时为真，则可直接写出AB为真，从而节省大量的中间环节，提高了证明效率。,1.7消解规则 例题 (AB)(CD)(BD)AC 利用条件式的等值式，则此题等价于证明 (AB)(CD)(BD)AC (1) (AB)为真前提条件 (2) (BD)为真前提条件 (3) AD为真 当(1)(2)为真消解式AD为真 (4) CD为真前提条件 (5) AC为真当(3)(4)为真消解式AC为真 采用假言推理原则时，尽可能将析取转换为条件式。 采用消解法时，尽可能将条件式转换为析取。 消解法是一种高效的方法。 消解法可完成1.6节中所有推理式,1.7消解规则 采用定传递律证明了(AC)(BC)AB 因AB AB,故可用假言推理及CP原则证明 (1) A为真附加前提 (2) (AC)为真前提条件 (3) A C为真与