《（本科）第3章 命题逻辑ppt课件.ppt》由会员分享，可在线阅读，更多相关《（本科）第3章 命题逻辑ppt课件.ppt（148页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程主讲人：（本科）第3章 命题逻辑ppt课件电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程离离 散散 数数 学学20222022年年5 5月月1616日星期一日星期一电子科技大学离散数学课程组电子科技大学离散数学课程组电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-3 32022-5-162022-5-16数理逻辑（数理逻辑（Mathematical LogicMathematical Logic）是研究演绎推理是研究演绎推理的一门学科；的一门学科；它的它的主要研究
2、内容主要研究内容是是推理推理，特别着重于，特别着重于推理过程是推理过程是否正确否正确；它不是研究某个特定的语句是否正确，而是着重于它不是研究某个特定的语句是否正确，而是着重于语句之间的关系。语句之间的关系。它的它的主要研究方法主要研究方法是采用是采用数学的方法数学的方法来研究来研究数学推数学推理、数学性质和数学基础理、数学性质和数学基础；而所谓而所谓数学方法数学方法就是就是引进一套符号体系的方法，所引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（以数理逻辑又叫符号逻辑（SymbolicSymbolic LogicLogic）。）。第二篇第二篇 数理逻辑数理逻辑电子科技大学离散数学课程组电子科
3、技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-4 42022-5-162022-5-16什么是数理逻辑什么是数理逻辑 ？用数学的方法来研究推理的规律统称为数理逻辑。用数学的方法来研究推理的规律统称为数理逻辑。为什么要研究数理逻辑？为什么要研究数理逻辑？程序算法数据程序算法数据 算法逻辑控制算法逻辑控制总结总结电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-5 52022-5-162022-5-16第二篇第二篇 数理逻辑数理逻辑命题逻辑命题逻辑 命题的基本概念命题的基本概念命题联结词
4、命题联结词命题公式命题公式命题的范式命题的范式命题逻辑推理理论命题逻辑推理理论主要主要研究内容研究内容谓词逻辑谓词逻辑谓词的基本概念谓词的基本概念谓词公式谓词公式公式的标准型公式的标准型谓词逻辑推理理论谓词逻辑推理理论推理与证明技术推理与证明技术定理证明的方法定理证明的方法数学归纳法数学归纳法按定义证明法按定义证明法电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-6 62022-5-162022-5-16第第3 3章章 命题逻辑命题逻辑 命题逻辑也称命题演算，或语句逻辑。命题逻辑也称命题演算，或语句逻辑。它研究它研究以命题
5、为基本单位构成的前提和结论之间的可推导以命题为基本单位构成的前提和结论之间的可推导关系，研究什么是命题？如何表示命题？如何由一关系，研究什么是命题？如何表示命题？如何由一组前提推导一些结论？组前提推导一些结论？ 命题逻辑的命题逻辑的特征：特征： 在研究逻辑的形式时，我们在研究逻辑的形式时，我们把一个命题只分析把一个命题只分析到其中所含的简单命题为止，不再分析下去到其中所含的简单命题为止，不再分析下去。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-7 72022-5-162022-5-163.0 3.0 内容提要内容提要命
6、题公式命题公式3命题范式命题范式4命题基本概念命题基本概念1集合的表示方法集合的表示方法2命题联结词命题联结词2命题逻辑推理理论命题逻辑推理理论5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-8 82022-5-162022-5-163.1 3.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1、五种基本联结词、五种基本联结词2 2、2424个基本的等价公式个基本的等价公式3 3、掌握求命题范式的方、掌握求命题范式的方法法4 4、掌握命题逻辑的推理、掌握命题逻辑的推理规则和公理规则和公理3联结词
7、的完备联结词的完备集的理解和学集的理解和学习习2公式的代入规公式的代入规则和替换规则则和替换规则电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-9 92022-5-162022-5-163.2.1 3.2.1 命题命题定义定义 具有具有确切确切真值真值的的陈述句陈述句称为称为命题命题, ,该命题可以该命题可以取一个取一个“值值”，称为，称为真值真值。真值只有真值只有“真真”和和“假假”两种，分别用两种，分别用“”( (或或“”) )和和“”( (或或“0 0”) )表示表示。3.2 3.2 命题与命题联结词命题与命题联结词
8、真假含义电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-10102022-5-162022-5-16 太阳是圆的；太阳是圆的； 成都是一个旅游城市；成都是一个旅游城市； 北京是中国的首都；北京是中国的首都； 1 11 11010； 我喜欢踢足球；我喜欢踢足球； 3 3能被能被2 2整除；整除； 地球外的星球上也有人；地球外的星球上也有人； 中国是世界上人口最多的国家；中国是世界上人口最多的国家； 今天是晴天；今天是晴天； +y0+y0；例例 1 1T T T TT TT/FT/FT/FT/FF FT/FT/FT TT T非
9、命题非命题电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-11112022-5-162022-5-16例例1(1(续续) ) 把门关上；把门关上； 滚出去！滚出去！ 你要出去吗？你要出去吗？ 今天天气真好啊！今天天气真好啊！ 这个语句是假的。这个语句是假的。非命题非命题非命题非命题非命题非命题非命题非命题非命题非命题悖论电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-1212说明说明注意：注意：一切没有判断内容的句子都不能作为命题一切没有判断内容的句子
10、都不能作为命题，如命令句、感叹句、疑问句、祈使句、二义性的陈如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。述句等。 结论：结论：命题一定是陈述句，但并非一切陈述句都是命题一定是陈述句，但并非一切陈述句都是命题。命题的真值有时可明确给出，有时还需要依命题。命题的真值有时可明确给出，有时还需要依靠靠环境、条件、实际情况时间环境、条件、实际情况时间才能确定其真值。才能确定其真值。约定：约定：在数理逻辑中像在数理逻辑中像字母字母“x x”、“y y”、“z z”等字等字母总是表示母总是表示变量。变量。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示
11、范课程1 147-47-13132022-5-162022-5-16 四川四川不不是一个国家；是一个国家； 3 3既既是素数是素数又又是奇数；是奇数； 张谦是大学生张谦是大学生或是或是运动员；运动员； 如果如果周末天气晴朗，周末天气晴朗，则则我们将到郊外旅游；我们将到郊外旅游； 2+2=42+2=4当且仅当当且仅当雪是白的。雪是白的。例例2 2 下列语句是否是命题？下列语句是否是命题？复合命题原子命题原子命题命题联结词命题联结词上面语句的真值是什么上面语句的真值是什么？电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-141
12、42022-5-162022-5-16约定：通常用约定：通常用大写的带或不带下标的英大写的带或不带下标的英文字母文字母、.P.P、Q Q、R R、. . A Ai i、B Bi i 、C Ci i、.P.Pi i、Q Qi i、R Ri i、.等表示等表示命题命题3.2.2 3.2.2 命题联结词命题联结词电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-15152022-5-162022-5-161 1、否定联结词、否定联结词定义定义 设设P P是任一命题，复合命题是任一命题，复合命题“非非P P”( (或或“P P的否的
13、否定定”) )称为称为P P的的否定式否定式(Negation)(Negation)，记作，记作 P P，“ ”为为否定联结词否定联结词。 若若 P P：四川是一个国家。：四川是一个国家。 则则 P P：四川不是一个国家。：四川不是一个国家。PPO11O P P为真当且仅当为真当且仅当P P为假为假。F FT T真值表真值表电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-16162022-5-162022-5-162 2、合取联结词、合取联结词定义定义 设设P P、Q Q是任两个命题，复合命题是任两个命题，复合命题“P P
14、并且并且Q Q”( (或或“P P和和Q Q”) )称为称为P P与与Q Q的的合取式合取式(Conjunction)(Conjunction)，记作记作PQPQ，“”为为合取联结词合取联结词。PQPQ为真当且仅当为真当且仅当P P，Q Q同为真同为真。 若若 P P：3 3是素数；是素数； Q Q：3 3是奇数。是奇数。 则则 PQPQ：3 3既是素数又是奇数。既是素数又是奇数。PQPQOOOO1O1OO111T TT TT T3是偶数F F偶数F F真值表真值表电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-17172
15、022-5-162022-5-163 3、析取联结词、析取联结词定义定义 设设P P、Q Q是任两个命题，复合命题是任两个命题，复合命题“P P或者或者Q Q”称为称为P P与与Q Q的的析取式析取式(Disjunction)(Disjunction)，记作，记作P PQ Q，“”为为析取联结词析取联结词。P PQ Q为真当且仅当为真当且仅当P P，Q Q中至少一个为真。中至少一个为真。若若 P P：张谦是大学生；：张谦是大学生； Q Q：张谦是运动员。：张谦是运动员。则则 PQPQ：张谦是大学生或是运动员。：张谦是大学生或是运动员。PQPQOOOO111O1111张谦是一班或二班的学生。T
16、TF FT T真值表真值表兼或与不可兼或。兼或与不可兼或。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-18182022-5-162022-5-164 4、蕴涵联结词、蕴涵联结词定义定义 设设P P、Q Q是任两个命题，复合命题是任两个命题，复合命题“如果如果P P，则，则Q Q”称为称为P P与与Q Q的的蕴涵式蕴涵式(Implication)(Implication)，记作，记作PQPQ，“”称为称为蕴涵联结词蕴涵联结词，P P称为蕴涵式的称为蕴涵式的前件前件，Q Q称为蕴涵式称为蕴涵式的的后件后件。PQPQ为假当且
17、仅当为假当且仅当P P为真且为真且Q Q为假为假。 若若P P：周末天气晴朗；：周末天气晴朗；Q Q：我们将到郊外旅游。：我们将到郊外旅游。则则PQPQ：如果周末天气晴朗，则我们将郊外旅游。：如果周末天气晴朗，则我们将郊外旅游。PQPQOO1O111OO111电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-19192022-5-162022-5-165 5、等价联结词、等价联结词定义定义 设设P P、Q Q是任两个命题，复合命题是任两个命题，复合命题“P P当且仅当且仅当当Q Q”称为称为P P与与Q Q的的等价式等价式(
18、Enuivalence)(Enuivalence)，记作，记作P PQ Q，“”称为称为等价联结词等价联结词。P PQ Q为真当且仅当为真当且仅当P P、Q Q同为真假。同为真假。 若若 P P：2+2=42+2=4；Q Q：雪是白的。：雪是白的。 则则 P PQ Q：2+2=42+2=4当且仅当雪是白的。当且仅当雪是白的。PQP QOO1O1O1OO111电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-20202022-5-162022-5-16总结总结联结词记号 复合命题 记法读法真值结果否定A是不对的 A非AA为真当
19、且仅当A为假合取A并且BABA合取BAB为真当且仅当A,B同为真析取A或者BABA析取BAB为真当且仅当A,B中至少一个为真蕴涵若A，则B ABA蕴涵BAB为假当且仅当A为真B为假等价A当且仅当BAB A等价于BAB为真当且仅当A,B同为真假电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-21212022-5-162022-5-16说明说明1 1、联结词是句子与句子之间的联结，而非单纯的、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结；名词、形容词、数词等地联结；2 2、联结词是两个句子真值之间的联结，
20、而非句子、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何的具体含义的联结，两个句子之间可以无任何地内在联系；地内在联系；PQPPQPQPQP QOO1OO11O1OO11O1OO1OO111111电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-22222022-5-162022-5-163 3、联结词与自然语言之间的对应并非一一对应；、联结词与自然语言之间的对应并非一一对应；（1 1）合取联结词）合取联结词“”对应了自然语言的对应了自然语言的 “既既又又”、“不仅不仅而且而且”, ,“虽然
21、虽然但是但是” 等等（2 2）蕴涵联结词）蕴涵联结词“”, ,“P PQ Q”对应了自然语言中对应了自然语言中的的“如如P P则则Q Q”、“只要只要P P就就Q Q”、“P P仅当仅当Q Q”等；等； 说明说明主要描述方法有：主要描述方法有： （1 1）因为）因为P P 所以所以Q Q； （2 2）只要）只要P P 就就 Q Q； （3 3）P P 仅当仅当 Q Q； （4 4）只有）只有Q Q，才，才P P； （5 5）除非）除非Q Q，才，才P P； （6 6）除非）除非Q Q，否则非，否则非P P； （7 7）没有）没有Q Q，就没有，就没有P P。电子科技大学离散数学课程组电子科技大
22、学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-23232022-5-162022-5-16（3 3）等价联结词）等价联结词“”对应了自然语言中的对应了自然语言中的“等价等价”、“当且仅当当且仅当”、“充分必要充分必要”等；等；（4 4）析取联结词）析取联结词“ ”对应的是相容（可兼）的或。对应的是相容（可兼）的或。说明说明4 4、为了不使句子产生混淆，、为了不使句子产生混淆，约定约定命题联结词之优先级为：命题联结词之优先级为：（1 1）否定）否定合取合取析取析取蕴涵蕴涵等价等价（2 2）同级的联结词）同级的联结词（合取与析取，蕴涵与等价合取与析取，蕴涵与等
23、价）按）按其出现的先后次序其出现的先后次序( (从左到右从左到右) )（3 3）若运算要求与优先次序不一致时，可使用）若运算要求与优先次序不一致时，可使用括号括号；同级符号相邻时，也可使用括号。同级符号相邻时，也可使用括号。括号中的运算为括号中的运算为最优先级最优先级。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-24242022-5-162022-5-16符号化下列命题符号化下列命题（1 1）四川）四川不不是人口最多的省份；是人口最多的省份；（2 2）王超是一个）王超是一个德智体德智体全面发展的好学生；全面发展的好学生
24、；（3 3）教室的灯不亮可能是灯管坏了）教室的灯不亮可能是灯管坏了或者或者是停电了；是停电了；（4 4）如果如果周末天气晴朗，周末天气晴朗，那么那么学院将组织我们到学院将组织我们到石像湖春游；石像湖春游；（5 5）两个三角形全等）两个三角形全等当且仅当当且仅当三角形的三条边全三角形的三条边全部相等。部相等。例例3.23.2. .4 4设：四川是人口最多的省份。设：四川是人口最多的省份。则命题（则命题（1 1）可表示为）可表示为。设：王超是一个思想品德好的学生；设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生；：王超是一个学习成绩好的学生； R R：王超是一个体育成绩好的学生。：王
25、超是一个体育成绩好的学生。则命题（则命题（2 2）可表示为）可表示为R R。设：教室的灯不亮可能是灯管坏了设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了：教室的灯不亮可能是停电了则命题（则命题（3 3）可表示为）可表示为。设：周末天气晴朗；设：周末天气晴朗； ：学院将组织我们到石像湖春游。：学院将组织我们到石像湖春游。则命题（则命题（4 4）可表示为）可表示为。设：两个三角形全等；设：两个三角形全等； ：三角形的三条边全部相等。：三角形的三条边全部相等。 则命题（则命题（5 5）可表示为）可表示为。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示
26、范课程双语示范课程1 147-47-25252022-5-162022-5-16设 命 题设 命 题P P ： 明 天 上 午 七 点 下 雨 ；： 明 天 上 午 七 点 下 雨 ；Q Q：明天上午七点下雪；：明天上午七点下雪；R R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句： 如果如果明天上午七点明天上午七点不不是雨是雨夹夹雪，雪，则则我将去学校我将去学校 如果如果明天上午七点明天上午七点不不下雨下雨并且并且不不下雪，下雪，则则我将去我将去学校学校 如果如果明天上午七点下雨明天上午七点下雨或或下雪，下雪，则则我将我将不不去学校去学校1.1. 明天上午七点我将明天上午七点我将
27、雨雪无阻雨雪无阻一定去学校一定去学校例例 5 5(PQ)R(PQ)R(PQ)R(PQ)R(PQ)R(PQ)R(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)R电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-26262022-5-162022-5-16例例 6 6设命题设命题 P P：你陪伴我；：你陪伴我； Q Q：你代我叫车子；：你代我叫车子； R R：我将出去。：我将出去。 符号化下述语句：符号化下述语句： 除非除非你陪伴我或代我叫车子，你陪伴我或代我叫
28、车子，否则否则我将我将不不出去出去 如果如果你陪伴我你陪伴我并且并且代我叫辆车子，代我叫辆车子，则则我将出去我将出去 如果如果你你不不陪伴我陪伴我或或不不代我叫辆车子，我将代我叫辆车子，我将不不出去出去R(PQ)R(PQ)或或 (PQ)R (PQ)R(PQ)R(PQ)R(PQ)R(PQ)R电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-27272022-5-162022-5-163.2.4 3.2.4 命题联结词的应用命题联结词的应用例例 7 7 用复合命题表示如下图所示的开关电路用复合命题表示如下图所示的开关电路：PQP
29、PQ设：设： ：开关闭合；：开关闭合。：开关闭合；：开关闭合。 ABABABABA A电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-28282022-5-162022-5-16用复合命题表示如下图所示的逻辑电路用复合命题表示如下图所示的逻辑电路：例例 8 8QPP P Q QQPP PQ QPP P解解: :设设P P：输入端为高电位，：输入端为高电位，Q Q：输入端为高电位：输入端为高电位, ,则则 “与门与门” 对应于对应于 PQPQ “或门或门” 对应于对应于 PQPQ “非门非门” 对应于对应于 P P电子科技大
30、学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-29292022-5-162022-5-16设命题设命题 P P：你陪伴我；：你陪伴我；Q Q：你代我叫车子；：你代我叫车子； R R：我将出去。：我将出去。则语句则语句“除非除非你陪伴我或代我叫车子，你陪伴我或代我叫车子，否则否则我将我将不不出去出去”符号化为：符号化为： R(PQ) R(PQ) 或或 (PQ)R (PQ)R3.3 3.3 命题公式、解释与真值表命题公式、解释与真值表命题公式命题公式真值函数真值函数F(P,Q,R)命题变元（变量）命题变元（变量）定义域定义域00，11
31、，值域，值域00，11电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-30302022-5-162022-5-163.3.1 3.3.1 命题公式命题公式定义定义3.3.2 (3.3.2 (命题公式命题公式) )命题变元本身命题变元本身是一个公式；是一个公式；如如G G是公式，则是公式，则( (GG) )也是公式；也是公式；如如G G，H H是公式，则是公式，则(GH)(GH)、(GH)(GH)、(GH)(GH)、(G(GH)H)也是公式；也是公式；命题公式命题公式是仅由是仅由有限步有限步使用使用规则规则1-31-3后产生
32、的结果。后产生的结果。该公式常用符号该公式常用符号G G、H H、等表示。等表示。基础基础归纳归纳极小性极小性合取式合取式析取式析取式 蕴含式蕴含式条件式条件式等价式等价式双条件式双条件式电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-31312022-5-162022-5-16例例 1 1 符号串：符号串： (P(QRP(QR)( (QQ(S)RS)R)； (P)QP)Q) )； ( (PP( ( (PQPQ)； ( (PQPQ) )( (RQRQ)( (PRPR)。 等都是命题公式。等都是命题公式。例例2 2 符号串：
33、符号串：( (PQPQ) )QQ) )；( (PQPQ；( (PQPQ( (R R； PQPQ。等都不是合法的命题公式。等都不是合法的命题公式。例例电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-32322022-5-162022-5-16约定约定对于公式中最外层的括号，常可省略。如对于公式中最外层的括号，常可省略。如(G)(G)可可写成写成G G，(GH)(GH)可写成可写成GHGH。但必须指出这仅仅。但必须指出这仅仅是一种约定，把程序输入计算机时，括号是不可随是一种约定，把程序输入计算机时，括号是不可随意省略的；意省略
34、的；否定联结词否定联结词“”“”只作用于邻接后的原子命题变元，只作用于邻接后的原子命题变元，如可把如可把(G)(G)H H写成是写成是 G GH H。相同相同联结词按其出现的先后次序联结词按其出现的先后次序, ,括号可以省略；括号可以省略；电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-33332022-5-162022-5-16R(PQ) R(PQ) 或或 (PQ)R (PQ)R命题公式命题公式真值函数真值函数F(P,Q,R)如果给定如果给定P,Q,RP,Q,R的取值，则的取值，则(PQ)R(PQ)R的值是多少呢？的值是
35、多少呢？若若P=1,Q=1,R=1P=1,Q=1,R=1，则，则(PQ)R=1(PQ)R=1公式的一个解释公式的一个解释3.3.2 3.3.2 公式的解释与真值表公式的解释与真值表电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-34342022-5-162022-5-163.3.2 3.3.2 公式的解释与真值表公式的解释与真值表定义定义3.3.3 3.3.3 设设P P1 1、P P2 2、P Pn n是出现在公式是出现在公式G G中的所中的所有命题变元，指定有命题变元，指定P P1 1、P P2 2、P Pn n一组真
36、值，则这组一组真值，则这组真值称为真值称为G G的一个的一个解释解释, ,常记为常记为。 一般来说，若有个命题变元，则应有一般来说，若有个命题变元，则应有2 2n n个不个不同的解释。同的解释。 如果公式如果公式G G在解释下是真的，则称在解释下是真的，则称满足满足G G；如；如果果G G在解释下是假的，则称在解释下是假的，则称弄假弄假G G。定义定义 将将公式公式G G在其所有可能解释下的在其所有可能解释下的真值情况列成真值情况列成的表，称为的表，称为G G的的真值表真值表。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47
37、-35352022-5-162022-5-16例例3 3求下面公式的真值表：求下面公式的真值表： (P(P( P PQ)R)QQ)R)Q 其中，、是的所有命题变元。其中，、是的所有命题变元。P Q R PPQ(PQ)RP(PQ)R)G0 0 0 10 0110 0 1 10 0110 1 0 1 1 01 10 1 1 1 1 1111 0 0 0 1 0001 0 1 0 1 1111 1 0 0 0 0011 1 1 0 0 001电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-3636P Q RP(PQ)R)Q0 0
38、 01 1 0 0 10 0 11 1 0 0 10 1 01 1 1 0 10 1 1 1 1 1 1 11 0 00 0 1 0 01 0 11 0 1 1 11 1 00 0 0 0 11 1 10 0 0 0 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-37372022-5-162022-5-16例例3 3（续）（续）P Q R(P(PQ)R)Q0 0 010 0 110 1 010 1 111 0 001 0 111 1 011 1 1 1进一步化简为：进一步化简为：电子科技大学离散数学课程组电子科技大学离
39、散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-38382022-5-162022-5-16例例4 4 P Q() ()() (Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面这组公式的真值表：求下面这组公式的真值表： 1 1 ( ()； 2 2( ()； 3 3 ( ( ) ) ( (Q)Q)。永真公式永假公式可满足公式电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-39392022-5-162022-5-16定义定义公式公式G G称为称为永真公式永真公式(
40、(重言式重言式) )，如果在它的，如果在它的所有所有解释解释之下都为之下都为“真真”。公式公式G G称为称为永假公式永假公式( (矛盾式矛盾式),),如果在它的如果在它的所有所有解释解释之下都为之下都为“假假”。公式公式G G称为称为可满足的可满足的，如果它，如果它不是永假不是永假的。的。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-40402022-5-162022-5-16从上述定义可知三种特殊公式之间的关系：从上述定义可知三种特殊公式之间的关系：永真式永真式G G的否定的否定 G G是矛盾式；矛盾式是矛盾式；矛盾式
41、G G的否定的否定 G G是永真式。是永真式。永真式一定是可满足式永真式一定是可满足式, ,可满足式不一定是永真可满足式不一定是永真式式可满足式的否定不一定为不可满足式可满足式的否定不一定为不可满足式( (即为矛盾即为矛盾式式) )结论结论电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-41412022-5-162022-5-16例例5 5写出下列公式的真值表，并验证其公式是重言式、写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。矛盾式、可满足公式。（1 1）G G1 1 = ( = () )( ( ) )
42、；（2 2）G G2 2 = ( = (Q)Q)( ( ( (Q)Q) (Q(Q)；（3 3）G G3 3 = (P = (P Q) Q) Q Q。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-42422022-5-162022-5-16解：解：P Q() ()( Q) (Q)(Q)(P Q) Q0 01 0 10 11 0 11 0 1 0 11 11 0 0永真公式永真公式可满足公式可满足公式永假公式永假公式可满足公式可满足公式三个公式的真值表如下：三个公式的真值表如下：电子科技大学离散数学课程组电子科技大学离散数学
43、课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-43432022-5-162022-5-16习题习题P95-9P95-96 63 3、(2)(3)(4)(7)(9)(2)(3)(4)(7)(9)4 4、(3)(4)(5)(3)(4)(5)5 5、(1)(3)(4)(1)(3)(4)7 7、(1)(3)(5)(7)(9)(1)(3)(5)(7)(9)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-44442022-5-162022-5-16P Q() ()( Q) (Q)(Q)(P Q) Q0 01
44、 0 10 11 0 11 0 1 0 11 11 0 0H=()G=()GH如果在任意解释下，G与H的真值相同G=H定义定义 设设G G、H H是是公式，公式，如果在任意解释下，如果在任意解释下，G G与与H H的的真值相同真值相同，则称公式，则称公式G G、H H是是等价的等价的，记作，记作G GH.H.公式等价公式等价定理定理3.3.1 3.3.1 公式G、H等价的充分必要条件是公式GH是永真公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-45452022-5-162022-5-16 （1 1）“”是一种逻辑联
45、结词，是一种逻辑是一种逻辑联结词，是一种逻辑运算，公式运算，公式G GH H是命题公式，其是命题公式，其结果仍是一个命结果仍是一个命题公式。题公式。 “”则是描述了两个公式则是描述了两个公式G G与与H H之间的之间的一种逻辑等价关系，一种逻辑等价关系，G GH H表示表示“命题公式命题公式G G等价等价于于命题公式命题公式H H”，G GH H 的结果的结果不是命题公式不是命题公式。 （2 2）如果要求用计算机来判断命题公式如果要求用计算机来判断命题公式G G、H H是否逻辑等价，即是否逻辑等价，即G GH H那是办不到的，然而计算那是办不到的，然而计算机却可机却可“计算计算”公式公式G G
46、H H是否是永真公式。是否是永真公式。 “” 与与“”的区别的区别电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-46462022-5-162022-5-16“= =”的性质的性质由于由于“= =”不是一个联结词，而是一种关系，为此，不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：这种关系具有如下三个性质：（1 1）自反性）自反性 G=GG=G；（2 2）对称性）对称性 若若G=HG=H，则，则H=GH=G；（3 3）传递性）传递性 若若G=HG=H，H=SH=S，则，则G=SG=S。这三条性质体现了这三条性
47、质体现了“= =”的实质含义。的实质含义。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-47472022-5-162022-5-16例例6 6 证明证明证明公式证明公式G G1 1( () )与公式与公式G G2 2(PQ)(QP)(PQ)(QP)之间是等价的。之间是等价的。 解：解：根据定理，只需判定公式根据定理，只需判定公式G G3 3( () ) (PQ)(QP)(PQ)(QP)为永真公式。为永真公式。P Q G3() (Q)(Q)0 0 1 1 1 1 10 1 0 1 1 0 0 1 0 0 1 0 0 11
48、 1 1 1 1 1 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-48482022-5-162022-5-16设设G G，H H，S S是任何的公式，则基本等价公式有：是任何的公式，则基本等价公式有：1 1：G(HS)G(HS)(GH)S(GH)S( (结合律结合律) )2 2: : G(HS) G(HS)(GH)S(GH)S3 3：GHGHHG HG ( (交换律交换律) )4 4：GHGHHGHG5 5：GGGGG G ( (幂等律幂等律) )6 6：GGGGG G7 7：G(GH)G(GH) G G ( (吸收
49、律吸收律) )8 8：G(GH)G(GH) G G3.3.4 3.3.4 命题公式的基本等价关系命题公式的基本等价关系电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-49492022-5-162022-5-169 9：G(HS)G(HS)(GH)(GS)(GH)(GS)( (分配律）分配律） 1010：G(HS)G(HS)(GH)(GS)(GH)(GS)1111：G0G0G G( (同一律同一律) ) 1212：GGG G 1313：GG( (零律零律) ) 1414：GG0 00 01515：GG GG ( (排中律排中
50、律) )1616：GG GG 0 0( (矛盾律矛盾律) )基本等价公式（续）基本等价公式（续）电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程1 147-47-50502022-5-162022-5-16基本等价公式（续）基本等价公式（续） 1717：(G)(G)G G( (双重否定律双重否定律) ) 1818：(GH)(GH)GHGH(De MoRGan(De MoRGan定律定律) ) 1919：(GH)(GH)GHGH 2020: : (G(GH)H)( (GH)(HGGH)(HG) )( (等价等价式式) ) 2121：(GH)(