第3章命题逻辑.ppt

《第3章命题逻辑.ppt》由会员分享，可在线阅读，更多相关《第3章命题逻辑.ppt（120页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、长春工业大学离散数学课程组长春工业大学离散数学课程组离 散 数 学计算机科学与工程学院计算机科学与工程学院20112011年年 秋秋第二部分数理逻辑第3章 命题逻辑第4章 谓词逻辑逻辑学是研究思维形式及思维规律尤其是推理的逻辑学是研究思维形式及思维规律尤其是推理的学科学科,早在两千多年前就受到人们的重视。早在两千多年前就受到人们的重视。逻辑学逻辑学古希腊（逻辑）古希腊（逻辑）战国（名学）战国（名学）古印度（因明）古印度（因明）德国数学家、哲学家莱布尼茨德国数学家、哲学家莱布尼茨(16471716)(16471716)首先提出用数学方法研究逻辑首先提出用数学方法研究逻辑,就是建立一就是建立一套表

2、意符号体系套表意符号体系,在符号之间进行形式推理在符号之间进行形式推理.莱布尼茨是数理逻辑的创始人。也正因为这莱布尼茨是数理逻辑的创始人。也正因为这样样,数理逻辑又称为符号逻辑。数理逻辑又称为符号逻辑。数理逻辑概述数理逻辑概述数数理理逻逻辑辑是是一一门门新新兴兴的的边边缘缘性性学学科科，分分为为五五个个部部分分：即即逻逻辑辑演演算算、证证明明论论、公公理理集集合合论论、递递归归论论和和模模型型论论。从从创创始始至至今今约约有有300300年年的的历历史史。特特别别是是近近百百年年来来,它它取取得得了了长长足足的的发发展展,在在现现代代的的数数学学、计计算算机机科科学学以以及自然科学和社会科学中

3、都有广泛的应用。及自然科学和社会科学中都有广泛的应用。数理逻辑概述数理逻辑概述数数理理逻逻辑辑是是用用数数学学的的方方法法来来研研究究人人类类思思维维活活动动的的一一门门数学学科，其显著特征是：数学学科，其显著特征是：符号化、形式化符号化、形式化即即把把逻逻辑辑所所涉涉及及的的“概概念念、判判断断、推推理理”用用符符号号来来表表示示，用用公公理理体体系系来来刻刻划划,并并基基于于符符号号串串形形式式的的演演算算来来描描述推理过程的一般规律。述推理过程的一般规律。数理逻辑概述数理逻辑概述回回顾顾计计算算机机科科学学的的发发展展，我我们们可可以以清清晰晰地地发发现现数数理理逻辑一直是计算机科学的理

4、论基础和发展动力。逻辑一直是计算机科学的理论基础和发展动力。数理逻辑的起源与计算机科学数理逻辑的起源与计算机科学数数理理逻逻辑辑计计算算机机科科学学同一个人同一个人同一时间同一时间设想用机械模拟设想用机械模拟人的思维活动。人的思维活动。“这种算术机器所这种算术机器所进行的工作，比动进行的工作，比动物的行为更接近人物的行为更接近人类的思维类的思维”。让我们来让我们来算一下！算一下！思维机械化思维机械化逻辑的数学分析逻辑的数学分析思维规律的研究思维规律的研究关系逻辑关系逻辑德摩根定律德摩根定律数理逻辑的起源与计算机科学数理逻辑的起源与计算机科学概念演算概念演算 一种按算术语言构成的思维符号语言德德

5、国国G.W.Leibniz(1626-1716)把把数数学学引引入入形形式式逻逻辑辑，明明确确提提出出用用数学方法研究推理。数学方法研究推理。英英国国G.Boole(1815-1864)等等创创立立了了逻逻辑辑代代数数，1847年年Boole实实现现了了命题演算。命题演算。德国德国G.Frege(1848-1925)在在1879年建立了第一个谓词演算系统。年建立了第一个谓词演算系统。英英国国B.Russell(1872-1970)等等从从逻逻辑辑学学的的基基本本法法则则建建立立了了自自然然数数理理论、实数理论及解析几何学等。论、实数理论及解析几何学等。奥地利奥地利K.Godel(1906-19

6、78)在在1931年提出年提出Godel不完全性定理。不完全性定理。英英国国Alan M.Turing(1912-1954)在在1936年年提提出出一一种种抽抽象象计计算算模模型型（数学逻辑机），引入图灵机（数学逻辑机），引入图灵机一种理想的计算机。一种理想的计算机。数理逻辑发展史中的代表人物数理逻辑发展史中的代表人物数理逻辑的学习数理逻辑的学习“我我现现在在年年纪纪大大了了，搞搞了了这这么么多多年年的的软软件件，错错误误不不知知犯犯了了多多少少，现现在在觉觉悟悟了了。我我想想，假假如如我我早早年年在在数数理理逻逻辑辑上上好好好好下下点点工工夫夫的的话话，我我就就不不会会犯犯这这么么多多的的错

7、错误误。不不少少东东西西逻逻辑辑学学家家早早就就说说过过了了，可可是是我我不不知知道道。要要是是我我能能年年轻轻二十岁的话，我就去学逻辑。二十岁的话，我就去学逻辑。”Edsger.W.Dijkstra 1972年年Turing奖获得者奖获得者 (1930-2002)单源点最单源点最短路径算短路径算法法学习数理逻辑学习数理逻辑曹雪芹是曹雪芹是红楼梦红楼梦的作者。的作者。曹雪芹是小说家。曹雪芹是小说家。小说家是文学家。小说家是文学家。数理逻辑是以数学的方法研究推理的形式结数理逻辑是以数学的方法研究推理的形式结构和规律的数学学科。所谓数学方法，是指构和规律的数学学科。所谓数学方法，是指建立一套符号，

8、其作用是为了避免用自然语建立一套符号，其作用是为了避免用自然语言讨论问题时所带来的歧义性。如，下面三言讨论问题时所带来的歧义性。如，下面三条语句均用条语句均用“是是”作谓语动词：作谓语动词：三个语句中的三个三个语句中的三个“是是”含义各不同。含义各不同。n曹曹雪雪芹芹是是红红楼楼梦梦的的作作者者。此此句句中中的的“是是”表表示示“”，其主语和谓语是对等的；，其主语和谓语是对等的；n曹曹雪雪芹芹是是小小说说家家。此此句句中中的的“是是”表表示示“”，小说家是集合，曹雪芹只是其中的一分子；小说家是集合，曹雪芹只是其中的一分子；n小小说说家家是是文文学学家家。此此句句中中的的“是是”表表示示“”，文

9、学家是包含着小说家的一个更大的集合。文学家是包含着小说家的一个更大的集合。显然，符号准确地表达了语句的含义。显然，符号准确地表达了语句的含义。学习数理逻辑学习数理逻辑玉龙雪山下的审判玉龙雪山下的审判在玉龙雪山脚下东巴谷的一条小路上立有一块木牌，请过路行人对一个案子在玉龙雪山脚下东巴谷的一条小路上立有一块木牌，请过路行人对一个案子进行审判。说的是有三个人，甲、乙、丙在玉龙山上射杀了一只老鹰，这三进行审判。说的是有三个人，甲、乙、丙在玉龙山上射杀了一只老鹰，这三个人的行为因违反个人的行为因违反野生动物保护法野生动物保护法而被警察拘捕，但是这三个人都否认而被警察拘捕，但是这三个人都否认老鹰是自己射杀

10、的。经过盘查和询问，警察得出如下三个结论：老鹰是自己射杀的。经过盘查和询问，警察得出如下三个结论：如果甲是无罪的，则乙和丙都有罪；如果甲是无罪的，则乙和丙都有罪；乙和丙中必有一人有罪；乙和丙中必有一人有罪；要么甲无罪，要么乙有罪（但两者不能同时成立）。要么甲无罪，要么乙有罪（但两者不能同时成立）。现在警方请求你协助判断甲、乙、丙三人谁有罪，谁没有罪，并在你认为有现在警方请求你协助判断甲、乙、丙三人谁有罪，谁没有罪，并在你认为有罪的人前面的筐里投入一块石头。笔者查看三个筐发现，乙的筐里石头最多，罪的人前面的筐里投入一块石头。笔者查看三个筐发现，乙的筐里石头最多，甲和丙的筐里则差不多。你认为游客们

11、的判断是否正确呢？甲和丙的筐里则差不多。你认为游客们的判断是否正确呢？第第3 3章章 命题逻辑命题逻辑命题公式及真值表命题公式及真值表3逻辑等值的命题公式逻辑等值的命题公式4命题的有关概念命题的有关概念1逻辑联结词逻辑联结词2命题公式的范式命题公式的范式5命题逻辑中的推理命题逻辑中的推理7本章学习要求本章学习要求重点掌握重点掌握熟练掌握熟练掌握了解了解11 1命题演算基础命题演算基础2 2命题演算的推命题演算的推理理3 3命题公式的标命题公式的标准化准化 31 1 对偶原理对偶原理2 2 命题符号化命题符号化21 1 命题的定义命题的定义2 2 联结词的含义联结词的含义3 3 真值表的使用真值

12、表的使用4 4 基本等值式和基本等值式和蕴含式蕴含式5 5 命题公式的定命题公式的定义义3.1 命题的定义命题的定义命题命题 命题是能判断出真假的语句命题是能判断出真假的语句.你妈喊你回家吃饭.建国大业里面有大腕儿.北京是中国的首都.火星上有生物.x 3。立正！这朵花真漂亮！你喜欢网络游戏吗?我说的都是假话。雨上得泰山真火。3.1 命题的定义命题的定义必须是一个完整的句子，包括用数学式子表达；必须是一个完整的句子，包括用数学式子表达；句子必须具有真假意义（即有对错之分）；句子必须具有真假意义（即有对错之分）；句子能判断出是真还是假。句子能判断出是真还是假。特征特征 陈述句陈述句 真假性真假性:

13、可决定真或假，且真假不可兼可决定真或假，且真假不可兼 例例 下列句子都是命题吗？下列句子都是命题吗？1960年杭州下雪了。太阳系外有宇宙人。好大的雪啊！812。1+101=110。上海世博会开幕时天晴。大于2的偶数可表示成两个素数之和。AB。请勿吸烟。姚明很帅。具体命题的真假问题具体命题的真假问题在在数数理理逻逻辑辑的的学学习习中中，不不能能去去纠纠缠缠各各种种具具体体命命题题的的真真假假问问题题，而而是是将将命命题题当当成成数数学学概概念念来来处处理理，看看成成一一个个抽抽象象的的形形式式化化的的概概念念，把把命命题题定定义义成成非非真真必必假假的的陈陈述述句句公説公有理婆説婆有理 命题真值

14、命题真值 真真:用用T(或或1)表示表示假假:用用F(或或0)表示表示2.2.命题的真值命题的真值命题的真值就是命题的逻辑取值命题的真值就是命题的逻辑取值.原子命题（简单命题）原子命题（简单命题）若若一一个个命命题题不不包包含含有有更更小小的的命命题题，即即不不可可再再分分割割的的命命题题。小小写英文字母写英文字母p,q,r,s,或带下标或带下标p1,p2,p3,等来表示原子命题。等来表示原子命题。复合命题复合命题 若一个命题可以分解（分割）若干个原子命题。若一个命题可以分解（分割）若干个原子命题。精确的定义为：精确的定义为：设设A1,A2,An是是原原子子命命题题，用用逻逻辑辑联联结结词词将

15、将这这n个个命命题题联联结结起起来来，构成的一个新命题，则称这个新命题是复合命题。构成的一个新命题，则称这个新命题是复合命题。3.3.原子命题与复合命题原子命题与复合命题 把把1和和0称为逻辑常量称为逻辑常量.在在逻逻辑辑表表达达式式中中出出现现的的p,q,r或或p1,p2,p3 等等称称为为命题变元或逻辑变量或逻辑变量.命命题题变变元元可可以以代代表表任任意意命命题题,从从取取值值的的角角度度看看,命命题变元既可以取题变元既可以取1又可以取又可以取0.4.4.常量与逻辑变量常量与逻辑变量字母字母p表示表示命题命题具体的、特定的命题，有确定的真值具体的、特定的命题，有确定的真值 命题变元命题变

16、元任意命题，没有确定的真值任意命题，没有确定的真值 3.2 逻辑联结词逻辑联结词五种常用的联结词：否定联结词 合取联结词 析取联结词 蕴含联结词 等价联结词 命命题题逻逻辑辑中中出出现现更更多多的的是是复复合合命命题题.一一方方面面，复复合合命命题题是是由由原原子子命命题题构构成成的的，它它需需要要联联结结词词；另另一一方方面面，给给定定了了原原子子命命题题，使使用用逻辑联结词，可可以以将将它们构成一个复合命题它们构成一个复合命题.逻辑联结词就是逻辑运算逻辑联结词就是逻辑运算.1.否定词否定词 设P是一个命题，命题“P是不对的”称为P的否定，记以P，读作非P。P是真的当且仅当P是假的。p p1

17、 10 00 01 1否定联结词是一元逻辑运算；否定联结词是一元逻辑运算；若若P是原子命题，则是原子命题，则 P是复合命题。是复合命题。日常日常语语句中有：句中有：非非 不不 并非并非 否定联结词的例子例子 P：长春是中国的城市。P：长春不是中国的城市。P是真命题，P是假命题。P：雪是黑色的。P：雪不是黑色的。命题P是假的，命题P是真的。命题的真假，与其否定的真假，正好相反，这符合我们的直观。否定联结词使用的原则否定联结词使用的原则将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例例 P:这些都是学生。这些都是学生。P：这些不都是学生：这些不都是学生 这些都不是

18、学生这些都不是学生例例（阿契贝难题）下述两命题都是真命题：（阿契贝难题）下述两命题都是真命题：A:“本句是六字句本句是六字句”B:“本句本句不不是六字句是六字句”通常来讲，若通常来讲，若B是是A的否定式，即一个为真，另一个为假。的否定式，即一个为真，另一个为假。A与与B的前提条件不相同，的前提条件不相同，A的否定句应为的否定句应为“本句非六字句本句非六字句”。2.合取联结词合取联结词 设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以PQ，读作P且Q。规定PQ是真的当且仅当P和Q都是真的。pqp q1 11 11 11 10 00 00 01 10 00 00 00 0日常语句中有：日

19、常语句中有：并且并且 与与 和和 “”是一个是一个2元逻辑联结词；元逻辑联结词；若若P，Q是原子命题，则是原子命题，则P Q是复合命题；是复合命题；合取联结词的例子合取联结词的例子 P:225 Q：雪是白的。：雪是白的。P Q：225并且雪是白的。并且雪是白的。P:今天刮风。今天刮风。Q：今天下雨。：今天下雨。P Q：今天刮风并且今天下雨。：今天刮风并且今天下雨。注意：注意：“小王和小李是同学小王和小李是同学”是简单命题，这是简单命题，这里的里的“和和”没有合取的意思。没有合取的意思。3.析取析取联结联结词词 设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以PQ，读作P或Q。规定PQ

20、是真的当且仅当P，Q中至少有一个是真的。pqp q1 11 11 11 10 01 10 01 11 10 00 00 0“”是一个是一个2元逻辑联结词；元逻辑联结词；若若P，Q是原子命题，则是原子命题，则P Q是复合命题；是复合命题；日常语言中有：日常语言中有：或或 或者或者 析取联结词的例子析取联结词的例子 P:225 Q：雪是白的。：雪是白的。P Q：225或者雪是白的。或者雪是白的。P Q显然是一个真命题。显然是一个真命题。P:今天刮风。今天刮风。Q：今天下雨。：今天下雨。P Q：今天刮风或者今天下雨。：今天刮风或者今天下雨。显然，只有在今天刮了风，或者下了雨的情况显然，只有在今天刮了

21、风，或者下了雨的情况 下下，P Q这句话才算说对。这句话才算说对。4.4.异或联结词异或联结词 :p q设p，q是两个命题，命题“p异或q”称为p，q的异或，记以p q，读作p异或q。规定p q是真的当且仅当p，q中真值不同。pqp q1 11 10 01 10 01 10 01 11 10 00 00 0“”是一个是一个2元逻辑联结词；元逻辑联结词；若若p，q是原子命题，则是原子命题，则p q是复合命题是复合命题.日常语言中有：日常语言中有：或或 或者或者 注意：自然语言中的注意：自然语言中的“或或”可能是可能是“可兼或可兼或”，也可能是，也可能是“不可兼或不可兼或”（排斥或），而（排斥或）

22、，而析取表达的是可兼或。析取表达的是可兼或。异或联结词的例子异或联结词的例子 P：我明天到北京出差：我明天到北京出差 Q：我明天到广州去度假：我明天到广州去度假P Q：我明天到北京出差或者到广州去度假：我明天到北京出差或者到广州去度假但是我们知道但是我们知道“我明天到北京出差或者到广州去度假我明天到北京出差或者到广州去度假”表示的是二者只能居其一，不会同时成立。因此不表示的是二者只能居其一，不会同时成立。因此不用析取联结词表示用析取联结词表示，而是用，而是用异或联结词异或联结词。5.蕴含蕴含(条件条件)联结联结词词设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以PQ。规定，PQ是假的

23、当且仅当P是真的而Q是假的。pqp q111100011001日常语言中有：日常语言中有：如果如果则则 如果如果那么那么 在PQ中，称P为前件，Q为后件。蕴含联结词的例子蕴含联结词的例子用用表示下列命题：表示下列命题：只要天下雨，我就回家。只要天下雨，我就回家。只有天下雨，我才回家。只有天下雨，我才回家。除非天下雨，否则我不回家。除非天下雨，否则我不回家。仅当天下雨，我才回家。仅当天下雨，我才回家。解解 设设p：天下雨。：天下雨。q：我回家。：我回家。则则符号化为符号化为 pq。符号化为符号化为 qp，或：或：p q符号化为符号化为 qp，或：或：p q符号化为符号化为 qp，或：或：p q注

24、注1.1.前件为假时，命题为真前件为假时，命题为真如果蕴含前件P是假命题，那么不管Q是什么命题，命题“如果P则Q”在逻辑中都被认为是真命题。例：“如果张三能及格，那太阳从西边升起。”说话者当然知道两命题风马牛不相及，而一般人此时并没有说谎的必要，即这是真命题，它所要明确的是“张三能及格”是假命题。注注2.2.前件、后件可以毫不相关前件、后件可以毫不相关在日常语言中“如果那么（则）”所联结的句子之间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的。例：P：235 Q：雪是黑色的 PQ：如果235，则雪是黑色的命题PQ是真命题，这有点不符合日常生活中的直观，但这

25、是逻辑的需要。注注3.3.充分条件、必要条件充分条件、必要条件pq为真命题的逻辑关系是：为真命题的逻辑关系是：p是是q的的充分充分条件，条件，q是是p的的必要必要条件。条件。“q是是p的必要条件的必要条件”的叙述方式还有：的叙述方式还有：p仅当仅当q（仅当（仅当q，则，则p）只有只有q才才p 只要只要p就就q 除非除非q，否则非，否则非p（非（非p，除非，除非q）例：天下大雨（例：天下大雨（p)，地一定湿了，地一定湿了(q)。pq6.等价（双条件）等价（双条件）联结联结词词设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以PQ。规定，PQ是真的当且仅当P，Q或者都是真的，或者都是假的。

26、pqp q1 11 11 11 10 00 00 01 10 00 00 01 1“p当且仅当当且仅当q”有两层含义：有两层含义：“p当当q”是指是指q p.“p仅当仅当q”是指是指p q.日常语言中有：日常语言中有：当且仅当当且仅当 充分必要充分必要 等价联结词的例子等价联结词的例子 P:224 Q：雪是白色的。P Q：224当且仅当雪是白色的。显然，P Q是真的，这符合直观。P:225 Q：雪是黑色的。P Q：225当且仅当雪是黑色。显然，P Q是真的，这符合直观。注注4.4.充要条件充要条件p q为真命题的逻辑关系是：p是q的充分条件，q是p的必要条件。pqp q1 11 10 01 1

27、0 01 10 01 11 10 00 01 17.与非联结词与非联结词 :p q设p，q是两个命题，命题“p，q相与后否定”称为p与非q，记以p q。规定，p q是假的当且仅当p，q同时真的。pqp q1 11 10 01 10 00 00 01 10 00 00 01 18.或或非联结词非联结词 :p q设p，q是两个命题，命题“p，q相或后否定”称为p或非q，记以p q。规定，p q是真的当且仅当p，q同时为假的。判断命题的类型（1）Tom和和John是兄弟。是兄弟。（2）如果）如果x0，则则 x20。（3）如果两个三角形全等，则它们的面积相等。）如果两个三角形全等，则它们的面积相等。（

28、4）一一个个三三角角形形为为等等腰腰三三角角形形当当且且仅仅当当三三角角形形有有两两条边相等。条边相等。中学中学数学数学选修选修2-12-1：四种命题：四种命题中学中学数学数学选修选修2-12-1：充分、必要：充分、必要命题公式（合式公式，WFF），是如下定义的一个符号串：命题变元和命题常量(1和0)是命题公式；若G是命题公式，则（G）是命题公式。若G和H是命题公式，则（G）、（GH）、（GH）、（GH）、（GH）是命题公式。有限次应用、所得到的符号串是仅有的命题公式。3.3 命题公式及其真值表命题公式及其真值表1.命题公式定义命题公式定义设P为命题公式，Q为P中的一个连续的符号串，且Q为命题

29、公式，则称Q为P的子公式。子公式子公式试判断命题公式QR是不是命题公式 PQR的子公式，为什么？严格按照命题公式的定义，就会出现很多的括号。因此作如下一些可以省略括号的约定：最外层的括号可以省略；联结词运算的优先顺序依次为:、；同级运算从左至右依次进行。关于命题公式关于命题公式命题公式不再是一个复合命题，是复合命题的抽象，这种抽象表现在，符号串中大写的英文字母不代表一个具体的命题，而只是一个符号，这个符号可以用一个具体的来解释。2.命题的符号化命题的符号化所谓命题的符号化就是使用符号所谓命题的符号化就是使用符号命题变元、逻命题变元、逻辑联结词和括号将所给出的命题表示出来。辑联结词和括号将所给出

30、的命题表示出来。其意义在于：其意义在于：符号体系来源于实际问题；符号体系来源于实际问题；给出进一步学习逻辑演算系统的语义解释时的一给出进一步学习逻辑演算系统的语义解释时的一种标准模型。种标准模型。将命题符号化的步骤：将命题符号化的步骤：找找出出所所给给命命题题的的所所有有原原子子命命题题,并并用用小小写写英英文文字字母母或或带下标表示；带下标表示；确定应使用的联结词确定应使用的联结词,进而将原命题用符号表示出来进而将原命题用符号表示出来.命题符号化实例命题符号化实例如果你走路时看书，那么你一定会成为近视眼。解：令 P：你走路；Q：你看书；R：你是近视眼。于是，上述命题符号化为：（PQ）R。除非

31、他以书面或口头的方式正式通知我，否则我不参加明天的会议。解：令 P：他书面通知我；Q：他口头通知我；R：我参加明天的会议。于是，上述命题符号化为：（PQ）R。命题符号化实例命题符号化实例只有努力学习、认真复习，才能取得好成绩。解：令P表示“努力学习”；Q表示“认真复习”；R表示“取得好成绩”。则原句译为R（PQ）。该语句能不能译为（该语句能不能译为（P Q）R？翻译是一定要考虑条件的必要性和充分性翻译是一定要考虑条件的必要性和充分性！命题符号化实例命题符号化实例 将下列语句形式化狗急跳墙。可表示为pq，其中p：狗急了，q：狗跳墙。如果他不来,那么他或者是生病了,或者是不在本地。可表示为p(qr

32、)，其中p：他来，q：他生病，r：他在本地。命题符号化实例命题符号化实例提示：根据命题的实际含义，不拘泥于原句形式地确提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词。定原子命题和选用联结词。在语句符号化时，在语句符号化时，一定要分解至原子命题，而不能把某个复合命一定要分解至原子命题，而不能把某个复合命题直接用命题变元题直接用命题变元P来表示，如此不能完整表来表示，如此不能完整表达语句的意思，也不便于计算机处理相关语句达语句的意思，也不便于计算机处理相关语句及其产生的知识。及其产生的知识。(1)天气很好或很热天气很好或很热.(2)如果张三和李四都不去如果张三和李四都不去,那

33、么我就去那么我就去.(3)仅当你走仅当你走,我留下我留下.(4)我今天进城我今天进城,除非天下雨除非天下雨.(5)你只有刻苦学习你只有刻苦学习,才能取得好成绩才能取得好成绩.练习：将下列命题符号化练习：将下列命题符号化.3.命题公式的真值表命题公式的真值表解释解释设设A是命题公式，是命题公式，A1，An是在是在A中出现的所中出现的所有原子。指定有原子。指定A1，An的一组真值，则这组真的一组真值，则这组真值称为值称为A的一个解释（也称为一种真值指派）。的一个解释（也称为一种真值指派）。记作记作I。设设G是公式，是公式，I是是G的一个解释，显然，的一个解释，显然，G在在I下下有真值，通常记为有真

34、值，通常记为TI(G)。如，如，G=P Q，设解释，设解释I为：为：I：P Q 1 1则则TI(G)=1对一个公式对一个公式A，将，将A在其所有解释下取得的真值列在其所有解释下取得的真值列成一个表，称为成一个表，称为A的真值表。的真值表。构造命题公式构造命题公式A的真值表的具体步骤为：的真值表的具体步骤为：找出找出A中所有命题变元中所有命题变元A1，An（一般按字典（一般按字典顺序给出），列出所有可能的解释；顺序给出），列出所有可能的解释；按从低到高的顺序写出各层次的子公式；按从低到高的顺序写出各层次的子公式；对应每个解释，计算命题公式的各层次的子公式对应每个解释，计算命题公式的各层次的子公式

35、的真值，直到最后计算出命题公式的真值，直到最后计算出命题公式A的真值。的真值。3.命题公式的真值表命题公式的真值表真值表真值表例：命题公式G=(PQ)R的真值表 P Q RP QG=(P Q)R0 0 0010 0 1010 1 0010 1 1011 0 0011 0 1011 1 0101 1 111一般来说一般来说,含含n个命题变元的命题公式的不同的真值指个命题变元的命题公式的不同的真值指派有派有2 2n种种.练习：命题公式 的真值表 p q r p p q(p q)r1 1 10111 1 00101 0 10011 0 00010 1 11110 1 01100 0 11110 0

36、01104.命题公式的类型命题公式的类型如果命题公式G在它的所有解释下都是真的，则称G为永真的(或有效的，也称为重言式)。如果命题公式G在它的所有解释下都是假的，则称公式G为永假的(或不可满足的，也称为了矛盾式)。如果命题G不是恒假的，则称公式G为可满足的。如果命题G至少有一种指派使其为真同时至少有一种指派使其为假，则称G为非永真式或中性式。判断命题公式的类型判断命题公式的类型p qpq p q1 11111 00010 11110 0111利用真值表可以判断一个命题公式的类型。利用真值表可以判断一个命题公式的类型。判断命题公式的类型判断命题公式的类型证明：结论：结论：由由A=1可推出可推出B

37、=1,则则A B永真永真.由由B=0可推出可推出A=0,则则A B永真永真.利用取值法可以判断一个命题公式的类型。利用取值法可以判断一个命题公式的类型。代入定理代入定理设命题公式G包含n个不同命题变元p1，p2，pn，用命题公式A1，A2，An同时分别取代p1，p2，pn的每一个出现，所得到的命题公式称为G的一个代入实例。代入定理：对于永真式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是永真式；对于永假式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是永假式。证明：证明：G1:（P Q）(P Q)是永真式，是永真式，G2:（PQ)(PQ)是永假式。是永假式。证明：用命

38、题公式P Q取代永真式取代永真式P P得得到到G1，即，即G1是永真式是永真式P P的一个代入实例，的一个代入实例，因此因此G1是永真的。是永真的。证明：用命题公式P Q 取代永假式取代永假式P P得得到到G2，即，即G2是永假式是永假式P P的一个代入实例，的一个代入实例，因此因此G2是永假的。是永假的。3.4 逻辑等值的命题公式逻辑等值的命题公式命题公式逻辑等值命题公式逻辑等值：给定命题公式命题公式A,B，若在，若在任何真值指派任何真值指派I下，其真值相同。则称命题公式下，其真值相同。则称命题公式A,B是逻辑等值的，或逻辑等价，简称等值或相等。是逻辑等值的，或逻辑等价，简称等值或相等。记作

39、记作A=B。=和和区别区别?=与与表达的表达的含义不同。含义不同。=表示两个公式间关系的符号；表示两个公式间关系的符号；是是命题联结词，是运算符号；命题联结词，是运算符号；=与与表达的结果表达的结果不同。不同。=表示两个公式有等值关系，联结后表示两个公式有等值关系，联结后结果不表示一个公式，即不代表命题，而结果不表示一个公式，即不代表命题，而联结两个公式的联结两个公式的后仍是一个公式，表示某个命题；后仍是一个公式，表示某个命题；=与与有密切的联系。有密切的联系。命题公式A，B是等值的当且仅当AB为永真式。设A、B、C是命题公式，则有自反性：A=A；对称性：若A=B，则B=A；传递性：若A=B，

40、B=C，则A=C。命题公式逻辑等值定理命题公式逻辑等值定理证明：p q pq p p q1 11 11 10 01 11 01 00 00 00 00 10 11 11 11 10 00 01 11 11 1命题公式逻辑等值定理命题公式逻辑等值定理定理：基本逻辑等值式基本逻辑等值式 G=G；(对合律对合律)G G=G，G G=G ；(幂等律幂等律)G H=H G，G H=H G；(交换律交换律)G(H S)=(G H)S,G(H S)=(G H)S；(结合结合律律)G(G H)=G，G(G H)=G；(吸收律吸收律)G(H S)=(G H)(G S)，G(H S)=(G H)(G S)；(分配

41、分配律律)G 0=G，G 1=G；(同一律同一律)G 0=0，G 1=1;(零一律零一律)(G H)=GH,(G H)=GH；(De Morgan律律)G G=1,GG=0;(互补律互补律)其它逻辑等值式其它逻辑等值式 (AB)=(AB)(BA)；(AB)=(A B)；等值置换：设C是命题公式A的子公式且C=D，则将A中的C部分或全部替换成D所得到的命题公式与A等值。等值演算法等值演算法等值置换定理等值置换定理利用基本等值式以及等值置换定理求解问题利用基本等值式以及等值置换定理求解问题的方法称为的方法称为“等值演算法等值演算法”.化简下列命题公式并将最后结果用只含化简下列命题公式并将最后结果用

42、只含 和和 表示表示.等值演算法应用等值演算法应用公式化简公式化简解：设设A,B,C是任意的命题公式是任意的命题公式,判断下列命题公判断下列命题公式的类型式的类型.等值演算法应用等值演算法应用判断公式类型判断公式类型解：等值演算法应用等值演算法应用证明两个命题公式相等证明两个命题公式相等设设A,B,C是任意的命题公式是任意的命题公式,证明下列等值式证明下列等值式.证：置换和代入的区别置换和代入的区别u代入是命题公式取代变元，置换是命题公式取代子公式；u代入必须用同一命题公式取代同一变元的每一处出现，而置换不必“每一处”取代；u代入可用任意命题公式代变元，置换只能是等价置换；u置换后得到的新命题

43、公式与原命题公式等价，而代入后得到的新命题公式不一定与原命公式等价。置换和代入的区别置换和代入的区别代入定理 置换定理 使用对象 任意恒真（假）式 任一命题公式 代入对象 任一命题变元 任一子公式 代换物 任一命题公式 任一与代入对象等值的命题公式 代入方式 代换同一命题变元的所有出现 代换子公式的某些出现 代入结果 仍为恒真（假）式 与原公式等值 练习练习化简命题公式化简命题公式 设A,B,C为任意命题公式,化简命题公式:A B （C A）使其最结果只含和表示。解解：A B （C A）=（A B）（C A）=（A B C）（A B A）=（A B C）练习练习判断公式类型判断公式类型 设A,

44、B,C为任意命题公式,试判断命题公式:（A（BC）（AB）C）的类型。解：（解：（A（BC）=A（B C）=A（B C）=（AB）C=（A B）C=（A B）C(A(BC)(A B)C)是永真式。是永真式。练习练习判断公式等值判断公式等值 G=（PQ）（RQ），H=（PR）Q，试判定G和H是否等值。（PQ）（RQ）=(P Q)（R Q）=(P Q)R)(P Q)Q)=(P R)(Q R)Q (P Q)=(P R)Q=(P R)Q G和和H逻辑等值。逻辑等值。对偶原理对偶原理 设命题公式设命题公式G中只含有中只含有3个逻辑联结词个逻辑联结词，将，将G中的符号中的符号 换成符号换成符号，符号符号

45、换成符换成符号号，符号，符号1换成符号换成符号0，符号，符号0换成符号换成符号1，其，其他符号（原子符号和否定符号）不变，所得他符号（原子符号和否定符号）不变，所得到的命题公式称为到的命题公式称为G的对偶式，记作的对偶式，记作G*。对偶原理：设A和B是命题公式，若A=B，则A*=B*。设命题公式设命题公式G=（p q）1，Q=p（q r），分别求），分别求G，Q的对偶式。的对偶式。解：解：G=（p q）1的对偶式为的对偶式为:G*=（p q）0；Q=p（q r）的对偶式为）的对偶式为:Q*=p（q r）。）。对偶原理实例对偶原理实例3.5 命题公式的范式命题公式的范式命题公式是千变万化的，这给

46、研究命题演算命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这样命题演式化归为一个标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问算的研究问题就归结为对标准形式的研究问题，题，这种标准形式就叫范式这种标准形式就叫范式。1.析取范式和合取范式设设A是命题公式是命题公式,若若A=A1 A2 An(n 1),其中其中Ai(1 i n)是由命题变元或其否定组成的是由命题变元或其否定组成的合取式合取式,则称则称A1 A2 An为为A的析取范式的析取范式.Ai是由命题变元或其否定组成的合取式应满足

47、：是由命题变元或其否定组成的合取式应满足：命题变元及其否定不同时出现；命题变元及其否定不同时出现；命题变元及其否定按字典顺序出现或按下标从小命题变元及其否定按字典顺序出现或按下标从小到大顺序出现；到大顺序出现；相同的合取式中不重复出现。相同的合取式中不重复出现。n=1时由单个命题变元或其否定组成的合取式看时由单个命题变元或其否定组成的合取式看成一个整体是析取范式。成一个整体是析取范式。设设A是命题公式是命题公式,若若A=A1 A2 An(n 1),其中其中Ai(1 i n)是由命题变元或其否定组成的是由命题变元或其否定组成的析取式析取式,则称则称A1 A2 An为为A的合取范式的合取范式.Ai

48、是由命题变元或其否定组成的析取式应满足：是由命题变元或其否定组成的析取式应满足：命题变元及其否定不同时出现；命题变元及其否定不同时出现；命题变元及其否定按字典顺序出现或按下标从小命题变元及其否定按字典顺序出现或按下标从小到大顺序出现；到大顺序出现；相同的析取式中不重复出现。相同的析取式中不重复出现。n=1时由单个命题变元或其否定组成的析取式看时由单个命题变元或其否定组成的析取式看成一个整体是合取范式。成一个整体是合取范式。1.析取范式和合取范式对于任意命题公式，都存在等价于它的析取对于任意命题公式，都存在等价于它的析取范式和合取范式。范式和合取范式。定理证明：对于公式证明：对于公式G，通过如下

49、算法即可得出等价，通过如下算法即可得出等价于于G的范式：的范式：使用基本等价式，将使用基本等价式，将G中的逻辑联结词中的逻辑联结词，等归约为等归约为，。利用利用(H)=H和和De Morgan律，将律，将G中所有的中所有的否定号否定号 都放在原子之前。都放在原子之前。反复使用分配律，即可得到等价于反复使用分配律，即可得到等价于G的范式。的范式。G(H S)=(G H)(G S)G(H S)=(G H)(G S)证明过程给出了求析证明过程给出了求析取范式和合取范式的取范式和合取范式的的步骤。的步骤。求求G=(P(QR)S的析取范和合取范式。的析取范和合取范式。解：解：G=(P(QR)S =(P(

50、Q R)S =P(Q R)S =P(QR)S (析取范式析取范式)=P(QR)(S(QQ)=P(QR)(S Q)(SQ)(析取析取范式范式)=(P S)(QR)=(P S Q)(P SR)(合取范合取范式式)u根据命题公式的析取范式及合取范式可分别得根据命题公式的析取范式及合取范式可分别得出该命题公式取真、假的指派出该命题公式取真、假的指派.析取范式及合取范式的应用析取范式及合取范式的应用析取范式及合取范式的应用析取范式及合取范式的应用从从p,q,r,s四人中选派四人中选派2人出差人出差,求满足下列求满足下列3个条件的个条件的选派方法有哪几种选派方法有哪几种.(1)若若p去去,则则r和和s中只