第3章节命题逻辑课件(1376KB).ppt

最小功能完备的联结词集. Def 3-12 设S是功能完备的联结词集,而S的任意非空真子集都不是功能完备的联结词集,则称S为最小的功能完备的联结词集. Theorem 3-11 下列联结词集是最小功能完备的: (1){?}. (2){?}. (3){?, ?}. (4){?, ?}. (5){?, ?}. 人们通常先介绍5种逻辑运算, 在命题公式的定义中也只用这5种. 实际上,这5种逻辑运算是不全面的,还有4种. 若从功能完备的角度去看,又有多余的联结词. 知道了逻辑运算的个数以及最小的功能完备的联结词集,对于我们进一步学习、研究逻辑演算形式系统是有帮助的. 在实际应用中,联结词“?”以及“?”可推广到多个命题变元上去, 如 “与或非门”等. 作业 习题3.6 2, 3, 4, 5. 3.7 命题逻辑中的推理 逻辑学的主要内容是研究推理，推理是从一些前提推出结论的思维过程. 实际问题中的推理，需要对前提做深入分析，才能得出结论，如由两直线平行，得出同位角相等以及由一元二次方程的判别式大于0得出方程有两个不相等的实数根等就是这样的一些推理. 数理逻辑主要是用数学的方法研究逻辑中的推理，它关心的是推理形式的有效性问题. 例如,下面两个不同的推理 (a)若两直线平行,则同位角相等, 这两直线是平行的, 所以,同位角相等. (b)若两个三角形全等,则其对应边相等, 这两个三角形全等, 所以,它们的对应边相等. 都具有如下的推理形式: 由p ? q, p 得出q. 所谓推理形式的有效性是指,如果前提全为真,那么所得结论必然真,而不考虑前提和结论的真实含义. 有效的推理形式是四海皆准的推理规则. 1.推理形式有效性的定义 Def 3-13 Theorem 的充要条件 “?”又是“永真蕴涵”或“逻辑蕴涵”符号,它与联结词蕴涵“?”是不同的. 定理3-12给出了等值式与永真蕴涵式之间的联系. 可以利用定理3-12去证明一些永真式. 从推理的角度看, 将“=”写成“?”更适合, 因为 Theorem 3-13(P104) 设A和B是命题公式, 则A = B的充要条件是A ? B且B ? A. Hint 可以证明, 命题公式间的永真蕴涵关系是偏序关系. 命题公式间的永真蕴涵关系还具有下面两条性质. Theorem 3-15 (1)若A ? C且B ? C, 则A ? B ? C. (2)若C ? A且C ? B, 则C ? A ? B . 由上述定理有 Theorem 3-16(P105) 设A, B是命题公式, 则对于命题公式间的永真蕴涵关系?, (1)sup{A, B} = A ? B. (2)inf{A, B} = A ? B. 2. 基本推理规则 下面举例说明,证明推理形式有效性的4种方法. 例3-29 设A和B是命题公式,证明: A ? B, A ? B. 分析: (p ? q) ? p ? q永真? Proof 1 真值表法. Proof 2 取值法—一种简易的真值表法. (p ? q) ? p = 1, q = 1? Proof 3 等值演算法. (p ? q) ? p ? q = 1? Proof 4 主范式法. 主析取范式: 主合取范式: ?. 基本推理规则或永真蕴涵式(P106). (1) (2) (3) (4) (5) (6) (7) (8) 基本等值式: 表3-24(P107) 3.命题逻辑的自然推理系统 自然推理的构造法是判定推理形式有效性的又一种方法,它主要是为今后进一步学习数理逻辑,尤其是逻辑的公理化推理系统做准备的. 自然推理的基本思想是,确定一些推理规则,然后根据这些推理规则从前提出发,把结论推出来. 作为推理系统,原则上有以下四个部分： 第一,它应有初始符号,它是系统中允许出现的字符. 自然推理系统的初始符号有3类: (1)命题变元; (2)5个联结词; (3)左右圆括号. 第二,定义推理系统中的公式,它是按一定的形成规则得到的有意义的符号串. 粗略地说,它就是命题公式, 但它原则上不出现除?, ?, ?, ?, ?外的其它联结词, 同时原则上不出现命题常量1和0. 第三,确定公理, 就是推理系统中不加推导就承认的公式. 从语义的角度看,它就是永真式. 自然推理系统中没有公理,这一点是与公理推理系统截然不同的. 第四,确定推理规则. 在自然推理系统中,把所有与5个联结词有关的基本逻辑蕴涵式都作为推理规则(见表1),同时,一个基本等值式(见下表2)相当于两个基本逻辑蕴涵式. 两个最基本的推理规则： P规则 所给的前提在证明过程中随时可以引用. T规则 已经推出的公式在以后的证明过程中可以随时引用. 自然