第3章命题逻辑课件.ppt

Chapter 3 命题逻辑 逻辑学是研究思维形式及思维规律尤其是推理的学科, 早在两千多年前就受到人们的重视, 古希腊著名逻辑学家亚里士多德(Aristotle, 公元前384~公元前322)是形式逻辑的创始人. 德国数学家、哲学家莱布尼茨(G. Leibniz, 1647~1716)首先提出用数学方法研究逻辑,就是建立一套表意符号体系,在符号之间进 3.1 命题的有关概念 计算机的计算过程就是推理过程,而每一步推理离不开判断,判断的对象就是命题. 1. 什么是命题? 命题(proposition, statement)是能判断出真假的语句.可以从三个方面去理解：(1)命题必须是一个完整的句子，包括用数学式子如代表的语句. 这一点在后面的命题符号化时要注意; (2)所给语句具有真假意义，即有对错之分. 一般来说，只有陈述句才具有真假意义，祈使句、疑问句和感叹句不具有真假意义; (3)能判断出是真还是假. 不过，要是将来某时候能判断出真假也行. 3.2 逻辑联结词 命题逻辑中出现的命题，除原子命题外，更多的是复合命题. 一方面，复合命题是由原子命题构成的，它需要联结词；另一方面，给定了原子命题，使用逻辑联结词(logical connectives)可以将它们构成一个复合命题,这也是逻辑联结词的作用之一. 逻辑联结词类似于自然语言中的连词，但逻辑联结词就是逻辑运算，除在本节对其进行严格定义外，还需要在其后讨论其运算性质. 3.3 命题公式及其真值表 有了前面的两节内容, 就可以得到命题逻辑的符号体系. 由于所讲内容侧重于在后继课程中的应用, 我们不给出逻辑演算系统的形式语言的定义. 1.命题公式的定义 这里的命题公式就是逻辑函数或逻辑表达式, 其中的常量是逻辑常量1和0, 其中的变元是命题变元或逻辑变量. 3.4 逻辑等值的命题公式 我们经常将一个命题, 如“四边形的对边平行”转换成与之逻辑等价的命题 “四边形的对边相等”, 所谓逻辑等价是指由“四边形的对边平行”可得出“四边形的对边相等”, 且由“四边形的对边相等”可得出“四边形的对边平行”. 显然, 这两个命题的真值是相同的，这时称这两个命题是逻辑等值的. 下面讨论两个命题公式逻辑等值. 3.5 命题公式的范式 给定一个命题公式，根据其真值表显然可以方便地得出其在每种指派下的真值，从理论上讲，这是一个能行可判定问题. 但随着所给公式中命题变元个数的增加，在实际计算中就变成不可行的了,例如含100个命题变元的命题公式其真值指派就有2100种. 由3.4节知，一个命题公式有各种形式的与其等值的命题公式，在它们中间欲找到一种标准形式或规范形式，也就是命题公式的范式，使其不用写出真值表就能确定在何真值指派下取真以及在何真值指派下取假. 3.6 联结词集合的功能完备性 在3.2节中介绍了9个联结词,我们想知道(1)联结词一共有多少个, (2)哪些联结词集合具有功能完备性. 这些内容可以从一定的理论高度帮助理解逻辑门电路的种类及其按一定要求化简逻辑函数等问题. 1.联结词的个数 3.7 命题逻辑中的推理 逻辑学的主要内容是研究推理，推理是从一些前提推出结论的思维过程. 实际问题中的推理，需要对前提做深入分析，才能得出结论，如由两直线平行，得出同位角相等以及由一元二次方程的判别式大于0得出方程有两个不相等的实数根等就是这样的一些推理. 数理逻辑主要是用数学的方法研究逻辑中的推理，它关心的是推理形式的有效性问题. 最小功能完备的联结词集. Def 3-12 设S是功能完备的联结词集,而S的任意非空真子集都不是功能完备的联结词集,则称S为最小的功能完备的联结词集. Theorem 3-11 下列联结词集是最小功能完备的: (1){?}. (2){?}. (3){?, ?}. (4){?, ?}. (5){?, ?}. 人们通常先介绍5种逻辑运算, 在命题公式的定义中也只用这5种. 实际上,这5种逻辑运算是不全面的,还有4种. 若从功能完备的角度去看,又有多余的联结词. 知道了逻辑运算的个数以及最小的功能完备的联结词集,对于我们进一步学习、研究逻辑演算形式系统是有帮助的. 在实际应用中,联结词“?”以及“?”可推广到多个命题变元上去, 如 “与或非门”等. 作业 习题3.6 2, 3, 4, 5. (1)主析取范式 Def 对于给定的命题变元,若由命题变元或其否定组成的合取式满足(1) 每个命题变元或其否定二者之一只出现一次；(2)按字典顺序或按下标从小到大顺序出现, 称这样的合取式为由所给命题变元产生的最小项(minimal term). 对于每一个最小项只有一种指派使其取1. 可以根据这个结论对最小项编码. 最小项用表示mi,其下标是由成真指派得到的二