数理逻辑 (4)课件

1、1,离数数学,主讲者:吝维军、赵俊,2,绪言,一、离散数学研究离散量的结构和相互间的关系 整数: .,-3,-2,-1,0,1,2,3,. 序 群 现实问题 能否从河的两岸或两个小岛中的任何一处出发, 经过每座桥一次且仅仅一次,再返回到出发点? 从任一点出发,经过每条边一次且仅次,回到起点? 二、离散数学是现代数学的一个分支（形成于70年代） 数理逻辑、集合论、代数系统、图论 三、离散数学与计算机科学的关系 离散数学是计算机科学与技术的理论基础，是计算机科学与技术的核心骨干课程 它给数据结构、编译系统、操作系统、数据库原理、人工智能提供必要的数学基础。 形式化、符号化的方法，培养和提高了学生的

2、抽象思维能力、逻辑推理能力。,3,绪言,四、离散数学学习要点 描述问题的方式：公式(符号)和图 公式：用符号描述对象或对象间的关联或概念 特点：严密、抽象、一般 图：用点和线描述对象或对象间的关联或概念 特点：直观、具体 重要性 有趣性 五、参考书目 离散数学，王遇科，北京理工大学 离散数学，李盘林等，高等教育出版社 离散数学及其在计算机中的应用，徐洁磐，人民邮电出版社,4,第一篇 数理逻辑,一、逻辑学 研究人的思维形式和规律的科学 形式逻辑_代表人：Hilbert 辩证逻辑_代表人物：罗素 数理逻辑 二、数理逻辑 形成于17世纪中叶 代表人物：莱布尼兹、布尔、哥德尔、德.摩根 研究推理：用数

3、学方法（形式化、公理化）研究前提和结论之间的形式关系。 特别是数学中的推理的科学。 各门学科中都要进行推理，从具体的前提出发，得出具体的结论。 例 （1）函数f(x)在闭区间a,b上连续 （2）f(a).f(b)0 （3）存在c(a,b)使f(c)=0. 又如： （1）a=0或a0 （2）a不等于0 （3）a0 数理逻辑研究的推理的特点：不注重内容，注重形式关系 (1）A B （2）A （3）B,5,三、数理逻辑的内容 集合论 模型论 递归论 证明论 共同的逻辑基础：逻辑演算（命题逻辑和谓词逻辑） 也是本课程学习的内容 四、学习的要点 掌握使用符号形式地刻划概念、推理和思维的基本思想和方法 掌

4、握形式的描绘和直观念义之间的关系 形意相通,6,第一章 命题逻辑,1-1 命题及其表示 数理逻辑研究的中心问题是推理 推理的前题和结论都是表达判断的陈述句。 表达判断的陈述句构成了推理的基本单位 称能判断真假的陈述句为命题 注： 真值，命题的值 判断为正确的命题的真值为真，用T表示 判断为错误的命题的真值为假，用F表示,7,例1:判断下列句子哪些是命题？,请止步! 你听懂了吗？ 我是学生 不是自然数 张校长的头发有一万根 我所说的是假的 如果天气好，那么我去散步 哥德巴赫猜想是正确的,不是命题 不是命题 是命题 是命题，假命题 是命题 不是命题，是悖论 是命题 是命题,8,几个概念,命题的种类

5、 原子命题（简单命题）、复合命题 命题的表示 大写英文字母：A、B、C、P、Q、 带下标的大写英文字母： P1、Q1、 数字加方括号：1、2、 命题标识符：表示命题的符号 命题常量：T、F 命题变元、原子变元,9,1-2 联结词,否定联结词 P 读作:非 P的真值为T当且仅当P为F 合取联结词 PQ 读作:与、P合取Q PQ为T当且仅当P和Q均为T 析取联结词 PQ 读作: P或Q、要么P要么Q PQ为F当且仅当P和Q均为F,条件联结词（蕴涵联结词） PQ 读作:如果P那么Q PQ为F当且仅当P为T，Q为F 双条件联结词（等值联结词） PQ 读作: P当且仅当Q PQ为T当且仅当P和Q的真值相

6、同,联结词是逻辑联结词或命题联结词的抽象 是自然语言中连词的抽象,10,五种联结词的定义,P,P,T,F,F,T,P,Q,PQ,T,T,T,F,F,T,F,F,T,F,F,F,P,Q,PQ,T,T,T,F,P,Q,PQ,T,F,T,T,P,Q,P Q,T,F,F,T,11,注,析取联结词是“或”的抽象 可兼或：a.b=0即a=0或b=0或a=b=0 (至少有一发生) 排斥或：他的死或重于泰山或轻于鸿毛 表示近似的或:去文昌楼需6分钟或8分钟 条件联结词 PQ,P称为前件,Q称为后件 当前件为F时,PQ为T 复合命题的真值只取决于构成它们的各原子命题的真值，而与其内容、含义无关 联结词有操作或运

7、算的含义 可看作一元运算符、二元运算符，,12,例2：将下列命题符号化,(1)他既聪明又用功。 (2)他虽聪明但不用功。 (3)如果2+2=4,太阳将从东方升起 (4)除非你努力，否则你将失败。 (5)除非天气好，我才骑自行车上班。 (6)张明正在睡觉或游泳。 (7)A中没元素，A就是空集。,解： (1) P：他聪明。 Q：他用功。 则(1)可表示为：PQ (2)可表示为：PQ (3) P： 2+2=4。 Q：太阳将从东方升起。 (3)可表示为: PQ (4) P:你努力. Q:你将失败. 则(4)可表示为：PQ (5) P:我骑自行车上班。 Q:天气好。 则(5)可表示为PQ 或QP (6)

8、 P:张明在睡觉. Q:张明在游泳. 则(6)可表示为(PQ)(PQ) (7) P: A中没元素. Q: A是空集. 则(7)可表示为：PQ,13,1-3命题公式与翻译,定义1-3.1命题演算的合式公式（wff）: (1)单个命题变元是合式公式. (2)如果A是合式公式,则(A)是合式公式. (3)如果A和B是合式公式,则(AB),(AB),(AB),(AB)是合式公式. (4)有限次地使用(1),(2),(3)所得到的结果是合式公式. 注: (1) 定义是以递归形式给出的 (2) 合式公式有无穷多个 (3) 合式公式没有真值,只有对其命题变元指派真值后,方有真值.,14,约定: (1) 公式

9、最外层的括号可省略 (2) 联结词运算的优先次序:, (3) 结合性 右结合 , 左结合,15,命题翻译,文字叙述的命题 由命题标识符,联结词,括号所组成的合式公式. 步骤: (1)分析出各原子命题,并用符号表示 (2)使用合适的联结词,将原子命题联结起来,并加适当的括号,来组成复合命题的符号化表示.,16,例3: 将下列命题符号化,(1)如果我上街,我就去书店看看,除非我很累. P:我上街. Q: 我去书店. R:我很累. (1)可符号化为: R (PQ) (2)王一乐是数学系的学生,他生于1968年或1969年,他是三好学生. P:王一乐是数学系的学生. Q:他生于1968年. R:他生于

10、1969年. S:他是三好学生. (2)可符号化为: P(QR)S,17,1-4,5 真值表 等价公式 重言式 蕴涵公式,1.真值表 定义1-4.1 在命题公式中,对于分量指派真值的各种可能组合,就确定了这个命题公式的各种真值情况,把它汇成表,就是命题公式的真值表.,18,例4:给出下列公式的真值表,(1) (PQ)P,P,Q,PQ,(PQ)P,F,F,F,F,P,Q,PQ,PQ,(2),(2) (PQ)(PQ),解: (1)的真值表如下:,解: (2)的真值表如下:,19,(3) (PQ) (PQ),P,Q,(PQ),PQ, (PQ) (PQ),注: 10:有一类公式无论命题变元作何种指派,

11、其真值为永真(永假) 20:含n个命题变元的命题公式，其真值表有2n行,20,2.重言式 矛盾式,定义1-5.1 给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为T,则称该命题公式为重言式或永真公式. 定义1-5.2 给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为F,则称该命题公式为矛盾式或永假公式. 定理1-5.1 任何两个重言式的合取或析取,仍是重言式.,21,3. 等价公式,定义1-4.2 设A和B是两个命题公式,若AB是重言式,则称A和B是等价的或逻辑相等. 记作AB. 例5 证明: (1) PQPQ (2) PQ (PQ)(QP),注: AB 即对A和B的任一真

12、值指派,有A和B的真值相同. 在逻辑相等意义下,含n 个原子变元的公式的个数为 与的区别 是逻辑符号 是语义符号 基本特性 AA 若AB则BA 若AB且BC则AC,22,P P,PP P, PP P,(PQ)R P(QR) (PQ)R P(QR),PQ QP, PQ QP,P(QR) (PQ)(PR) P(QR) (PQ)(PR),P(PQ) ,PF ,PT ,PP T, PP F,常用的命题定律,P(PQ) ,P,P,P,P,PT ,F,T,PF ,23,4.蕴涵公式(逻辑蕴涵),定义1-5.3 设A,B是公式,若AB是重言式,则称A蕴涵B,记作AB. 定理 1-5.4 设A,B是命题公式.

13、 AB的充要条件是AB且BA. 证明:利用A B (AB)(BA)来证.,24,注:,与的区别. 几个类似的公式 PQ, QP, PQ, QP 称为 逆换式 反换式 逆反式 有PQQP PQ的证明方法 真值表 假设前件真,推出后件真 假设后件假,推出前件假 的特性 若AB且A为重言式,则B为重言式. AB,BC则AC AB,AC则ABC AB,CB则ACB,25,PQP, PQQ,PPQ,PPQ,QPQ,(PQ) P,(PQ) Q,P(PQ) ,Q(PQ) ,P(PQ) ,(PQ)(QR) ,(PQ)(PR)(QR) ,(PQ)(RS) (PR)(QS),(P Q)(Q R) (P R),常用

14、的蕴涵式,Q,P,Q,(PR),R,26,例5 推证Q(PQ) P,证明: 法一: 设Q(PQ)为T, 则Q为T 从而Q为F 由(PQ)为T及Q为F 可知P为F 故P为T.,法二: 设P为F,则P为T. 若Q为F,则(PQ)为F 从而Q(PQ)为F. 若Q为T,则Q为F, 从而Q(PQ)为F. 综上有 Q(PQ) P 法三:列真值表,27,5.替换规则 代入规则,替换(置换)规则 定义1-4.3 若X是合式公式A的一部分且为合式公式,则称X为A的子公式. 定理1-4.1 设X是合式公式A的子公式,Y是一公式.若XY,如果将A中的X用Y来置换所得公式B,则A B. 注 满足定理1-4.1的置换称

15、为等价转换或等价代换. 替换规则又提供了一种证明公式等价的方法.,28,例7 证明: Q(P(PQ) QP 证明: 因为P(PQ) P, (吸收律) 故有 Q(P(PQ) QP (替换规则),例8 证明: (PQ)(PQ) P 证明: (PQ)(PQ) P(QQ) (分配律) PT (否定律,替换规则) P (同一律),29,例9 证明 P(QR) Q(PR) R(QP) 证明: P(QR) P(QR) P(QR) Q(PR) Q(PR) Q(PR),核心: PQ PQ,R(QP) R(QP) R(QP) P(QR) P(QR),30,例10 证明 (PQ) (P(QR)(PQ)(PR) T

16、证明: (PQ) (P(QR)(PQ)(PR) (PQ)(P(QR)(PQ)(PR) (德.摩根律) (PQ)(PQ)(PR)(PQ)(PR) (分配律) (PQ)(PR)(PQ)(PR) (结合律, 幂等律) (PQ)(PR) (PQ) (PR) (德.摩根律) (PQ)(PR) (PQ)(PR) (德.摩根律) T (否定律),31,代入规则,定理1-5.2(代入规则) 一个重言式,对同一分量全部用同一合式公式代换所得结果为重言式. 注: 全部代 又提供了判定重言式的方法 例:已知PP为重言式,则有下列重言式: (PQ)(PQ) (PQR)(PQR) AA,32,1-6 其它联结词,联结词

17、 符号 复合命题 含义,不可兼析取,条件否定,与非,合非,或非,谢孚竖,33,与非的特性,合非的特性,(1),(2),(3),(1),(2),(3),34,2.最小联结词组(联结词的完全集),T F P Q P Q,问:在逻辑相等意义下,两个命题变元P和Q可构成的不同的命题公式有多少个?,由T,F,P,Q及9个命题联结词可以表示16个命题公式. 但有几个就够了?,35,(2),(3),(4),结论: , ,是最小联结词组 ,也是最小联结词组 ,V均不是最小联结词组,36,1-7对偶和范式,1.对偶 定义1-7.1 在给定的仅用联结词,和的命题公式A中,若把和互换,F和T互换,所得公式A*称为A

18、的对偶式. 例1:写出下列公式的对偶式. (1) (PQ)R (2) (PQ)T (3) (PQ)(P (QS) 例2:求PQ,PQ的对偶式. PQ的对偶式为PQ PQ的对偶式为PQ,37,定理1-7.1 若A和A*是对偶式,P1,P2,Pn是出现在A和A*中的原子变元, 则 A(P1,P2,Pn) A*(P1, P2, Pn) A(P1, P2, Pn) A*(P1,P2,Pn) 注: 德.摩根律的推广 (P1P2Pn) P1P2Pn 设A1,A2,An是任意命题变元,则 (A1A2An) A1A2An 例3. 设A*(S,W,R)是S(WR), 验证: A*(S, W, R) A(S,W,

19、R) 例4. 如果A(P,Q,R)是P(Q(RP), 求它的对偶式A*(P,Q,R), 分别求与A及A*等价,但仅包含联结词,和的公式.,38,定理1-7.2 设P1,P2,Pn是出现在公式A和B中的所有原子变元,如果AB,则A*B*. 证明: 由于AB, 则A(P1,P2,Pn) B(P1,P2,Pn)是重言式, 故A(P1, P2, Pn) B(P1, P2, Pn)是重言式. 即A(P1, P2, Pn) B(P1, P2, Pn) 由定理1-7.1 A(P1, P2, Pn) A*(P1,P2,Pn) B(P1, P2, Pn) B*(P1,P2,Pn) 故A*B*,39,2.范式-公

20、式的标准型,(1)析取范式,合取范式 定义 1-7.2 一个命题公式称为合取范式,当且仅当它具有型式: A1A2An (n1) 其中A1，A2，An都是由命题变元或其否定所组成的析取式 定义 1-7.3 一个命题公式称为析取范式,当且仅当它具有型式: A1A2An (n1) 其中A1，A2，An都是由命题变元或其否定所组成的析取式,40,例5. 求(P(QR)S的合取范式. 解: (P(QR)S (P(QR)S (P(QR)S P (Q R)S (PS)(QR) (PSQ)(PSR),41,例6.求(PQ) (PQ)的析取范式. 解: (PQ) (PQ) (PQ) (PQ)(PQ) (PQ)

21、(PQ) (PQ)(PQ) (PQ) (PQ) (PQ)(PQ) (PQ) (PQ) (PQ) (PQ) P)(PQ)Q) (PP)(QP)(PQ)(QQ) (QP)(PQ),42,(2) 主析取范式,定义1-7.4 n个命题变元的合取式,称作布尔合取式或小项,其中每个变元与它的否定出现且仅出现一个. 注: 三个命题变元P,Q,R其小项: PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR n个命题变元的小项共有2n个 一小项仅对应一组真值指派使其真值为真. 任两个小项均不等价,且其合取为假. 全体小项的析取永为真.,43,小项的编码表示,命题变元P,Q,R的小项 m

22、000= PQR, m001= PQR m010 = PQR, m011 =PQR m100 = PQR, m101 = PQR m110 = PQR, m111 = PQR, 记真值T和F分别为1和0,小项的真值指派与编码相同时,真值为. 小项也可记为:m0, m1, m2, m3, m4, m5, m6, m7.,44,主析取范式,定义1-7.5 对于给定的命题公式，如果有一个等价公式，它仅有小项的析取所组成，则该等价式称作原式的主析取范式 例6.求(PQ)的主析取范式. 解:列出其真值表: (PQ)(PQ)(PQ) (PQ),定理1-7.5 (主析取范式的求法) 在真值表中,公式的真值为

23、T的指派所对应的小项的析取即为此公式的主析取范式.,45,例8. 求(PQ)(PR)(QR)的主析取范式.,解:首先列出其真值表:,(PQ)(PR)(QR),T,T,F,F,T,F,T,F,真值为T所对应的小项为: PQR PQR PQR PQR 故原公式的主析取范式为: (PQR)(PQR)(PQR)(PQR),46,法二: (PQ)(PR)(QR) (PQ)(RR)(PR)(QQ)(QR)(PP) (PQR)(PQR)(PRQ) (PRQ)(QRP)(QRP) (PQR)(PQR)(PQR)(PQR),47,(3) 主合取范式,定义1-7.6 n个命题变元的析取式,称作布尔析取式或大项,其

24、中每个变元与它的否定出现且仅出现一个. 注: n个命题变元的大项共有2n个 三个命题变元P,Q,R其大项: M000=PQR, M001=PQR, M010=PQR, M011=PQR, M100=PQR, M101=PQR, M110=PQR, M111=PQR 一大项仅对应一组真值指派使其真值为假. 任两个大项均不等价,且其析取为真. 全体大项的合取永为假.,48,主合取范式,定义1-7.7 对于给定的命题公式，如果有一个等价公式，它仅有大项的合取所组成，则该等价式称作原式的主合取范式 定理1-7.4 (主合取范式的求法) 在真值表中,公式的真值为F的指派所对应的大项的合取即为此公式的主合

25、取范式.,49,例10. 求(PQ)(PR)的主合取范式与主析取范式.,解:首先列出其真值表:,(PQ)(PR),T,T,F,F,T,F,T,F,真值为F所对应的大项为: PQR PQR PQR PQR 故原公式的主合取范式为: (PQR)(PQR)(PQR)(PQR) 同理,原公式的主析取范式为(PQR)(PQR)(PQR)(PQR),50,例10:化(PQ)(PR)为主合取范式. 解: (PQ)(PR) (PQ)P)(PQ)R) (PP)(QP)(PR)(QR) (QP)(PR)(QR) (QP)(R R)(PR)(Q Q) (QR)(P P) (QPR)(QPR)(PRQ) (PRQ)(

26、QRP)(QRP) (QPR)(QPR)(PRQ)(PRQ),51,(4)主析(合)取范式的简洁表达,表示小项的析取, i,j,k表示mimjmk 表示大项的合取, i,j,k表示ijk 例10可表示为 (PQ)(PR) (PQR)(PQR)(PQR)(PQR) m111m110m011 m001 1,3,6,7 (PQ)(PR) (PQR)(PQR)(PQR)(PQR) M101M100M010 M000 0,2,4,5 命题公式A主析取范式为i1,i2,ik 命题公式A主合取范式为 1,2, i1-1, i1+1,i2-1, i2+1, ik-1, ik+1,2n-1,52,1-8 推理理

27、论,定义1-8.1 设A和C是两个命题公式,若AC,称C是A的有效结论.或称C可由A逻辑地推出. 称C是一组前提H1,H2,Hn的有效结论,当且仅当 H1H2HnC 记作: H1,H2,Hn C 判别有效结论的过程就是论证过程 常用的论证方法： 真值表法,真接证法, 间接证法. (1)真值表法,53,例1.一份统计表格的错误或者是由于材料不可靠,或者是由于计算有错误;这份统计表格的错误不是由于材料不可靠,所以这份统计表格是由于计算有错误. 解: 设各命题变元为 P:统计表格的错误是由于材料不可靠. Q:统计表格的错误是由于计算有错误. 本例可译为:Q是前提PQ, P的有效结论,即 P(PQ)

28、Q. 为此列出真值表如下:,由真值表可看到,仅在第三行,前提PQ, P均为真,而此时结论Q为T. 故P(PQ) Q成立,54,例2. 如果张老师来了,这个问题可以得到解答,如果李老师来了,这个问题也可以得到解答,总之张老师或李老师来了,这个问题就可以得到解答. 解: 若设 P:张老师来了. Q:李老师来了. R:这个问题可以得到解答. 上述语句可译成下述命题关系式: (PR)(QR)(PQ) R 通过真值表可验证上述关系式成立.,55,(2)直接证法,直接证法就是由一组前提,利用一些公认的推理规则,根据已知的等价或蕴涵重言式,推演得到有效的结论. 推理规则 P规则(也称前提引入规则) 在推导过

29、程中,前提可视需要引入使用 T规则(也称结论引入规则) 在推导过程中,前面导出的有效结论都可作为后继推导的前提引入 CP规则(也称条件证明引入规则) 若推出的有效结论为条件式RC,只需将前件R加入到前提中作为附加前提,再推出后件C即可. 事实上,若H1H2HnRC则H1H2HnRC 常用的蕴涵式和等价式 P43,56,例1. 证明(PQ)(PR)(QS) SR,证明: (1) PQ P (2) PQ T(1) E (3) QS P (4) PS T(2)(3), I (5) PR P (6) SP T(4),E (7) SR T(6) (5) E (8) SR T(7) E,证明(二) (1) PR P (2) PQRQ T(1),I (3) QS P (4) QRSR T(3),I (5) PQSR T(2)(4),I (6) PQ P (7) SR T(5)(6), I,57,例2.WRV,VCS,SU,CUW,证明: CU P C T(1),I U T(1),I SU P US T(4), I S T(3)(5),I C S T(2)(7),E (CS)