数理逻辑命题逻辑.ppt

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

1、第一部分 数理逻辑概述概述:基本概念基本概念n逻辑学的分类逻辑学的分类:辩证逻辑辩证逻辑形式逻辑形式逻辑 n辩证逻辑辩证逻辑以辩证法认识论的世界观为基础的逻辑学以辩证法认识论的世界观为基础的逻辑学 n形式逻辑形式逻辑对思维的形式结构和规律进行研究的类似于语法的对思维的形式结构和规律进行研究的类似于语法的一门工具的学科一门工具的学科 2概述概述:基本概念基本概念n思维的形式结构思维的形式结构 包括概念、判断和推理之间的结构和联系包括概念、判断和推理之间的结构和联系 n形式逻辑的侧重点形式逻辑的侧重点与其说是注重论证本身，不如说注重的是论证形式与其说是注重论证本身，不如说注重的是论证形式 形式逻辑

2、的一般格式就是三段论。形式逻辑的一般格式就是三段论。例：例：苏格拉底三段论：苏格拉底三段论：所有的人都是要死的，所有的人都是要死的，苏格拉底是人，苏格拉底是人，所以，苏格拉底是要死的。所以，苏格拉底是要死的。3概述概述:基本概念基本概念n传统逻辑和数理逻辑传统逻辑和数理逻辑19世纪中叶以前的形式逻辑是传统逻辑世纪中叶以前的形式逻辑是传统逻辑19世纪中叶以后发展起来的现代形式逻辑，通常世纪中叶以后发展起来的现代形式逻辑，通常称为数理逻辑称为数理逻辑4什么是数理逻辑什么是数理逻辑n数理逻辑：数理逻辑：以数学的方法研究思维规律和推理过程的科学。以数学的方法研究思维规律和推理过程的科学。n它首先引进一

3、套它首先引进一套符号体系符号体系，规定，规定一些规则一些规则，导出，导出一些定律一些定律，然，然后借助于这些符号、规则、定律，将逻辑推理的过程在形式上后借助于这些符号、规则、定律，将逻辑推理的过程在形式上变得像代数演算一样，因此数理逻辑又称变得像代数演算一样，因此数理逻辑又称符号逻辑符号逻辑。n数理逻辑数理逻辑是传统逻辑的发展，是现代形式逻辑是传统逻辑的发展，是现代形式逻辑5微积分微积分力学、机械工程力学、机械工程人类体力劳动自动化人类体力劳动自动化数理逻辑数理逻辑人工智能、知识工程人工智能、知识工程脑力劳动自动化脑力劳动自动化6数理逻辑数理逻辑n命题逻辑命题逻辑（数理逻辑的基础，以命题为研究

4、对象，研究基（数理逻辑的基础，以命题为研究对象，研究基于命题的符号逻辑体系及推理规律，也称命题演算）。于命题的符号逻辑体系及推理规律，也称命题演算）。主要内容：主要内容：、命题与联结词、命题与联结词、命题公式、翻译和真值表、命题公式、翻译和真值表、重言式、重言式、命题联结词的扩充、命题联结词的扩充、范式、范式、命题演算的推理规则和证明方法、命题演算的推理规则和证明方法 n谓词逻辑谓词逻辑（对命题逻辑的深入研究）。（对命题逻辑的深入研究）。7第一章第一章 命题逻辑命题逻辑1 命题与联结词命题与联结词一、命题一、命题1、什么是命题？、什么是命题？命题是陈述客观外界发生事情的陈述句。命题是陈述客观外

5、界发生事情的陈述句。命题或为真或为假的陈述句。命题或为真或为假的陈述句。特征：特征：陈述句陈述句真假必居其一，且只居其一。真假必居其一，且只居其一。1 1 命题与联结词命题与联结词8 中国是一个发展中国家。中国是一个发展中国家。人是由猴进化而来的。人是由猴进化而来的。早上好！早上好！王侯将相，宁有种乎？王侯将相，宁有种乎？己所不欲，勿施于人！己所不欲，勿施于人！宇宙是大爆炸形成的。宇宙是大爆炸形成的。我正在说谎。我正在说谎。这道题太难。这道题太难。2、命题的真值。、命题的真值。一个命题的真或假称为命题的一个命题的真或假称为命题的真值真值，简称，简称值值。由于命题只有真假两个值，所以命题逻辑也称

6、由于命题只有真假两个值，所以命题逻辑也称二值逻辑二值逻辑。以以T（或（或1）表示命题的真值为真，）表示命题的真值为真，F（或（或0）表示命题的）表示命题的真值为假真值为假悖论模糊逻辑1 1 命题与联结词命题与联结词EX1：93、命题的分类与表示、命题的分类与表示 分类分类根据其真值分类：根据其真值分类：真命题。真命题。假命题。假命题。根据其复杂程度分类：根据其复杂程度分类：简单命题或原子命题。简单命题或原子命题。复合命题。复合命题。1 1 命题与联结词命题与联结词10命题的抽象表示命题的抽象表示在数理逻辑中，通常用大在数理逻辑中，通常用大(小小)写字母表示命题，写字母表示命题，P、Q、R，或用

7、带下标的大写字母，或用带下标的大写字母Pi、Qi、Ri 或者数字（或者数字（1）、）、（2）、）、。表示命题的符号称为命题标识符，如表示命题的符号称为命题标识符，如P、Q、R、Pi、Qi、Ri。EX2：P：4是偶数；是偶数；Q：煤是白的。：煤是白的。P1：离散数学考试，张三和李四都及格了。：离散数学考试，张三和李四都及格了。1 1 命题与联结词命题与联结词11 命题的抽象表示命题的抽象表示一个命题标识符如果表示确定的命题，就称为一个命题标识符如果表示确定的命题，就称为命题常量命题常量。如果命题标识符只表示任意命题的位置标志，就称为如果命题标识符只表示任意命题的位置标志，就称为命题变命题变元元。

8、则命题的抽象为：则命题的抽象为：取值为取值为T（或（或1）或）或F（或（或0）的）的P、Q、R等符号。等符号。若若P取值取值T（或（或1），则表示），则表示P为真命题；为真命题；若若P取值取值F（或（或0），则表示），则表示P为假命题；为假命题；1 1 命题与联结词命题与联结词12“复杂命题复杂命题”EX3：由简单命题能构造更加复杂的命题由简单命题能构造更加复杂的命题 期中考试，张三期中考试，张三没有没有考及格。考及格。期中考试，张三期中考试，张三和和李四李四都都及格了。及格了。期中考试，张三期中考试，张三和和李四中李四中有有人考人考90分。分。如果如果张三能考张三能考90分，分，那么那么李四

9、也能考李四也能考90分。分。张三能考张三能考90分分当且仅当当且仅当李四也能考李四也能考90分。分。1 1 命题与联结词命题与联结词13联结词和复合命题联结词和复合命题上述诸如上述诸如“没有没有”、“如果如果那么那么”等词称为等词称为联结词联结词。由联结词和命题连接而成的更加复杂命题称为由联结词和命题连接而成的更加复杂命题称为复合命题复合命题；相；相对地，不能分解为更简单命题的命题成为对地，不能分解为更简单命题的命题成为简单命题简单命题。（命题。（命题的分类）的分类）复合命题的真假完全由构成它的简单命题的真假所决定。复合命题的真假完全由构成它的简单命题的真假所决定。注：注：简单命题和复合命题的

10、划分是相对的。简单命题和复合命题的划分是相对的。1 1 命题与联结词命题与联结词141、否定联结词、否定联结词在在 EX3 EX3 中，中，“期中考试，张三没有考及格期中考试，张三没有考及格”。P P：“期中考试，张三考试及格了期中考试，张三考试及格了”，设设 P P 为一个命题，复合命题为一个命题，复合命题“非非P P”称为称为P P的否定式，记为的否定式，记为 P P，“”称为否定联结词。称为否定联结词。“P P”为真当且仅当为真当且仅当P P为假。为假。P P P PF F（0 0）T T（1 1）T T（1 1）F F（0 0）二、命题联结词二、命题联结词1 1 命题与联结词命题与联结

11、词151、否定联结词、否定联结词EX4EX4：求求“我们班上所有的同学都大于我们班上所有的同学都大于1818岁岁”的否定。的否定。P：我们班上所有的同学都大于我们班上所有的同学都大于1818岁。岁。P：我们班上所有的同学我们班上所有的同学不不都大于都大于1818岁。岁。P：我们班上所有的同学都我们班上所有的同学都不不大于大于1818岁。岁。1 1 命题与联结词命题与联结词162、合取联结词、合取联结词EX4EX4：“期中考试，张三和李四都及格了。期中考试，张三和李四都及格了。”P P 代表：代表：“期中考试张三考试及格了期中考试张三考试及格了”Q Q 代表：代表：“期中考试李四考试及格了期中考

12、试李四考试及格了”。设设P P、Q Q为两个命题，复合命题为两个命题，复合命题“P P而且而且Q”Q”称为称为P P、Q Q的合取式，的合取式，记为记为P PQ Q，“”称为合取联结词。称为合取联结词。P PQ Q为真当且仅当为真当且仅当P P 与与 Q Q 为同时为真。为同时为真。P PQ QP PQ QT TT TT TT TF FF FF FT TF FF FF FF F1 1 命题与联结词命题与联结词173、析取联结词、析取联结词设设P P、Q Q为两个命题，复合命题为两个命题，复合命题“P P或者或者Q”Q”称为称为P P、Q Q的析取式，的析取式，记为记为P PQ Q，“”称为析取

13、联结词。称为析取联结词。P PQ Q为真当且仅当为真当且仅当P P与与Q Q为中至少有一个为真。为中至少有一个为真。P PQ QP PQ QT TT TT TT TF FT TF FT TT TF FF FF FEX4EX4：“期中考试张三或李四中有人考期中考试张三或李四中有人考90分。分。”P P 代表：代表：“期中考试期中考试张三考了张三考了9090分分”，Q Q 代表：代表：“期中考试期中考试李四考了李四考了9090分分”。1 1 命题与联结词命题与联结词18“可兼或可兼或”与与“排斥或排斥或”日常语言中日常语言中“或或”有三种标准用法，有三种标准用法，EX5EX5：张三或者李四考了张三

14、或者李四考了9090分。分。第一节课上数学课或者上政治课。第一节课上数学课或者上政治课。去教学楼需要去教学楼需要6 6分钟或分钟或8 8分钟。分钟。差异在于：差异在于：当构成他们的简单命题都真时，（当构成他们的简单命题都真时，（1 1）为真，（）为真，（2 2）为假。）为假。（1 1）称为）称为“可兼或可兼或”，（，（2 2）称为）称为“排斥或排斥或”，（，（3 3）非）非联结词，表示近似的数。联结词，表示近似的数。（1 1）可表示为）可表示为P PQ Q，（，（2 2）却不能。）却不能。注意：注意：不能见了不能见了“或或”就表示为就表示为P PQ Q。1 1 命题与联结词命题与联结词19EX

15、6EX6：求求“今天下雪且今天下雨今天下雪且今天下雨”的否定。的否定。P：今天下雪。今天下雪。Q：今天下雨。今天下雨。练习：练习：求求“今天不下雪且今天不下雨今天不下雪且今天不下雨”的否定的否定1 1 命题与联结词命题与联结词P PQ Q(P(PQ)Q)T TT TF FT TF FT TF FT TT TF FF FT T204、蕴含联结词、蕴含联结词EX4EX4：“如果张三能考如果张三能考90分，那么李四也考分，那么李四也考90分。分。”P P：“张三考张三考9090分分”。Q Q：“李四考李四考9090分分”。设设P P、Q Q为两个命题，复合命题为两个命题，复合命题“如果如果P P，则

16、，则Q”Q”称为称为P P对对Q Q的蕴含的蕴含式，记为式，记为PQPQ，其中又称，其中又称P P为此蕴含式的为此蕴含式的前件前件，称，称Q Q为此蕴含式为此蕴含式的的后件后件，“”“”称为蕴含联结词。称为蕴含联结词。“PQ”PQ”为假当且仅当为假当且仅当P P真而真而Q Q假。假。P PQ QPQPQT TT TT TT TF FF FF FT TT TF FF FT T1 1 命题与联结词命题与联结词21EX7EX7：如果你今年离散数学考如果你今年离散数学考100100分，那么就奖励你分，那么就奖励你100100元。元。P：你今年离散数学考你今年离散数学考100100分。分。Q：奖励你奖励

17、你100100元。元。1 1 命题与联结词命题与联结词1 1P PQ QPQPQ1 11 11 11 10 00 00 01 11 10 00 01 122pq 的逻辑关系：的逻辑关系：q 为为 p 的必要条件的必要条件“如果如果 p，则，则 q”的不同表述法很多：的不同表述法很多：若若 p，就，就 q 只要只要 p，就，就 q p 仅当仅当 q 只有只有 q 才才 p 除非除非 q,才才 p 或或 除非除非 q,否则非否则非 p，当当 p 为假时，为假时，pq 为真为真常出现的错误：不分充分与必要条件常出现的错误：不分充分与必要条件23 例例 设设 p p:天冷，天冷，q q:小王穿羽绒服，

18、小王穿羽绒服，将下列命题符号化将下列命题符号化 (1)只要天冷，小王就穿羽绒服只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候小王穿羽绒服仅当天冷的时候.注意：注意：p q与与 q p 等值（真值相同）等值（真值相同）pqpqpq

19、pqqp qpqpqp245、等价联结词、等价联结词EX4EX4：“张三能考张三能考90分当且仅当李四也能考分当且仅当李四也能考90分分。”P P：“张三考张三考9090分。分。”Q Q：“李四考李四考9090分。分。”设设P P、Q Q为两个命题，复合命题为两个命题，复合命题“P P当且仅当当且仅当Q”Q”称为称为P P、Q Q的等的等价式，记为价式，记为P PQ Q，“”称为等价联结词。称为等价联结词。P PQ Q为真当且仅为真当且仅当当P P与与Q Q同时为真或同时为假。同时为真或同时为假。P PQ QP PQ QT TT TT TT TF FF FF FT TF FF FF FT T1

20、 1 命题与联结词命题与联结词25“注意注意”上述五个联结词来源于日常使用的相应词汇，但并不完全上述五个联结词来源于日常使用的相应词汇，但并不完全一致，在使用时要注意：一致，在使用时要注意：以上联结词组成的复合命题的真假值一定要根据它们的以上联结词组成的复合命题的真假值一定要根据它们的定义去理解，而不能据日常语言的含义去理解。定义去理解，而不能据日常语言的含义去理解。不能不能“对号入座对号入座”，如见到，如见到“或或”就表示为就表示为“”。有些词也可表示为这五个联结词，如有些词也可表示为这五个联结词，如“但是但是”也可表示也可表示为为“”“”。u在今后我们主要关心的是命题间真的假值的关系，而不

21、讨在今后我们主要关心的是命题间真的假值的关系，而不讨论命题的内容。论命题的内容。1 1 命题与联结词命题与联结词26EX1EX1：铁和氧化合，但铁和氮不化合。铁和氧化合，但铁和氮不化合。如果我下班早，就去商店看看，除非我很累。如果我下班早，就去商店看看，除非我很累。李四是经管院的学生，他住在李四是经管院的学生，他住在312室或室或313室。室。1 1 命题与联结词命题与联结词三、复合命题三、复合命题27铁和氧化合，但铁和氮不化合。铁和氧化合，但铁和氮不化合。P：“铁和氧化合铁和氧化合”Q：“铁和氮化合铁和氮化合”则用符号表示则用符号表示:P(Q)如果我下班早，就去商店看看，除非我很累。如果我下

22、班早，就去商店看看，除非我很累。P：“我很累我很累”Q：“我下班早我下班早”R：“我去商店看看我去商店看看”则用符号表示则用符号表示:(P)(QR)或者可以表示为：或者可以表示为：(P)Q)R)命题公式、翻译和真值表命题公式、翻译和真值表28李四是经管院的学生，他住在李四是经管院的学生，他住在312室或室或313室。室。P：“李四是经管院的学生。李四是经管院的学生。”Q：“李四住李四住312室。室。”R：“李四住李四住313室。室。”则用符号表示则用符号表示:P(Q(R)(Q)R)或者可以表示为：或者可以表示为：P(Q R)(Q R)命题公式、翻译和真值表命题公式、翻译和真值表29复合命题复合

23、命题由原子命题经命题联结词可构成各种形式的复合命题，由原子命题经命题联结词可构成各种形式的复合命题，在复合命题中涉及到括号的使用问题，目前均使用圆括在复合命题中涉及到括号的使用问题，目前均使用圆括号，为减少括号的使用，在此作下列规定：号，为减少括号的使用，在此作下列规定：规定规定5个联结词的结合能力强弱顺序为：个联结词的结合能力强弱顺序为：“否定否定”、“合取合取”、“析取析取”、“蕴含蕴含”、“等价等价”，即，这五，即，这五个逻辑运算的优先顺序为个逻辑运算的优先顺序为、。凡符。凡符合此顺序者，括号均可除去。合此顺序者，括号均可除去。命题公式、翻译和真值表命题公式、翻译和真值表30小结小结命题

24、及其符号命题及其符号P P、Q Q、R R。构成复合命题的联结词构成复合命题的联结词、，以及由联，以及由联结词构成的复合命题及其真假值。结词构成的复合命题及其真假值。注意：注意：有了命题和命题联结词，为了进一步的研究，今有了命题和命题联结词，为了进一步的研究，今后，将只注重命题的真假值，而并不注意其内容含义，后，将只注重命题的真假值，而并不注意其内容含义，对命题联结词，只承认它由真值表定义，而不理会它的对命题联结词，只承认它由真值表定义，而不理会它的实际含义，这样，就可以在命题与命题联结词的基础上实际含义，这样，就可以在命题与命题联结词的基础上建立起一个形式系统。建立起一个形式系统。31命题联

25、结词的扩充命题联结词的扩充不可兼析取不可兼析取（排斥或）“”或或“”或或“”：设：设P和和Q是是两个命题，称两个命题，称P Q为为P和和Q的不可兼析取。的不可兼析取。规定：规定：P Q的值为真，当且仅当的值为真，当且仅当P、Q的真值不相同时，的真值不相同时，否则否则P Q的值为的值为F。其真值表如下：其真值表如下：PQP Q11010101100044命题联结词的扩充命题联结词的扩充32不可兼析取不可兼析取 “”有以下性质：有以下性质：P QQ P(P Q)RP (Q R)P(Q R)(PQ)(PR)(P Q)(PQ)(PQ)(P Q)(PQ)44命题联结词的扩充命题联结词的扩充33蕴含否定（

26、条件非蕴含否定（条件非）蕴含否定蕴含否定或或条件非条件非：设设P和和Q是两个命题，称是两个命题，称P Q为为P和和Q的的蕴含否定或条件非蕴含否定或条件非。规定：规定：P Q的值为的值为T，当且仅当，当且仅当P的真值为的真值为T，Q的真值为的真值为F。其真值表如下：其真值表如下：由上表可知：由上表可知：P Q(PQ)PQP Q11010101000044命题联结词的扩充命题联结词的扩充34谢佛（与非）谢佛（与非）谢佛谢佛或或与非与非“”：设：设P和和Q是两个命题，称是两个命题，称P Q为为P和和Q的的与非。与非。规定：规定：当且仅当当且仅当P和和Q真值都是真值都是T时，时，P Q为为F。其真值表

27、如下：其真值表如下：由真值表可得出：由真值表可得出：P Q(PQ)PQP Q11010101100144命题联结词的扩充命题联结词的扩充35与非与非“”有以下性质：有以下性质：P P (PP)P(P Q)(P Q)(P Q)PQ(P P)(Q Q)P Q(PQ)PQ44命题联结词的扩充命题联结词的扩充36魏泊（或非）魏泊（或非）魏泊魏泊或称作或称作或非或非“”：设：设P和和Q是两个命题，称是两个命题，称P Q为为P和和Q的或非的或非 规定：规定：当且仅当当且仅当P和和Q的真值都为的真值都为F时，时，P Q的真值为的真值为T其真值表如下：其真值表如下：由真值表可得出：由真值表可得出：P Q(PQ

28、)PQP Q11010001000144命题联结词的扩充命题联结词的扩充37或非（续）或非（续）“”有以下性质：有以下性质：P P(PP)P(P Q)(P Q)(P Q)PQ(P P)(Q Q)P QPQ44命题联结词的扩充命题联结词的扩充38是否每个符号串都是命题呢？是否每个符号串都是命题呢？PQ、P Q什么样的符号串才能表示命题呢？什么样的符号串才能表示命题呢？如下命题公式定义的符号串表示的才是命题。如下命题公式定义的符号串表示的才是命题。命题公式、翻译和真值表命题公式、翻译和真值表一、命题公式（合式公式或公式）一、命题公式（合式公式或公式）命题公式、翻译和真值表命题公式、翻译和真值表39

29、命题公式的定义命题公式的定义由命题变元经命题联结词可构成命题逻辑公式，亦可叫命题公由命题变元经命题联结词可构成命题逻辑公式，亦可叫命题公式或公式。式或公式。定义定义1:命题公式是由命题变元和联结词按以下规则组成的符号命题公式是由命题变元和联结词按以下规则组成的符号串串原子命题变元本身是一个命题公式；原子命题变元本身是一个命题公式；如果如果P是命题公式，则是命题公式，则 P 也是命题公式；也是命题公式；如果如果P、Q是命题公式，则是命题公式，则PQ、PQ、PQ和和PQ都是命题公式都是命题公式；只有有限次地应用只有有限次地应用构成的符号串才是命题公式。构成的符号串才是命题公式。命题公式是一个按上述

30、法则由命题变元、命题联结词及圆命题公式是一个按上述法则由命题变元、命题联结词及圆括号组成的符号串或字符串。括号组成的符号串或字符串。命题公式、翻译和真值表命题公式、翻译和真值表40下列符号串都是下列符号串都是命题公式：命题公式：PP(Q)P(P)P(P)P(P)(P(P)(P)(P R)命题公式、翻译和真值表命题公式、翻译和真值表41下列符号串是否为下列符号串是否为命题公式？命题公式？PQ P Q PQ R 命题公式、翻译和真值表命题公式、翻译和真值表42一些注意一些注意定义定义2是归纳定义，而不是循环定义是归纳定义，而不是循环定义。（1）是奠基，（）是奠基，（2）、（）、（3）是归纳步骤，（

31、）是归纳步骤，（4）是界限。）是界限。如果我们规定联结词运算的优先次序为：如果我们规定联结词运算的优先次序为：、，则，则，PQR也是命题公式。也是命题公式。有了联结词和命题公式概念，我们就可以把自然语言中的有有了联结词和命题公式概念，我们就可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。些语句，翻译成数理逻辑中的符号形式。命题公式、翻译和真值表命题公式、翻译和真值表43二、命题的翻译二、命题的翻译EX1：将下列语句翻译为命题公式将下列语句翻译为命题公式他既聪明，又用功。他既聪明，又用功。他虽聪明但不用功。他虽聪明但不用功。张明正在睡觉或游泳。张明正在睡觉或游泳。除非他通知我，否则我不参

32、加会议。除非他通知我，否则我不参加会议。张明与李强都可以做这件事。张明与李强都可以做这件事。命题公式、翻译和真值表命题公式、翻译和真值表44二、命题的翻译二、命题的翻译EX2：设设P：“李明是男生李明是男生”；Q：“李明是足球队队员李明是足球队队员”；R：“李明是班干部李明是班干部”用日常语言叙述下列命题：用日常语言叙述下列命题：PQQRPQRPQR 命题公式、翻译和真值表命题公式、翻译和真值表45三、指派和真值表三、指派和真值表命题公式的真假由其中命题变元的值完全确定。命题公式的真假由其中命题变元的值完全确定。n命题公式中所有命题变元的一组确定的取值称为公式的命题公式中所有命题变元的一组确定

33、的取值称为公式的一组一组真值指派真值指派。n公式值的确定是按公式中联结词出现的先后次序及括号顺序公式值的确定是按公式中联结词出现的先后次序及括号顺序逐步应用命题联结词的真值表规定而得到的，逐步应用命题联结词的真值表规定而得到的，所有的指派构所有的指派构成的公式的值成的公式的值即组成了此即组成了此公式的真值表公式的真值表。命题公式、翻译和真值表命题公式、翻译和真值表46EX3：构造构造(PQ)R的真值表的真值表 PQR(PQ)R(PQ)R000111001100010111011100100010101000110111111100 命题公式、翻译和真值表命题公式、翻译和真值表47EX4：构造构

34、造(PQ)(P Q)的真值表的真值表 PQPQ P P Q(PQ)(P Q)001111011111100001111011 命题公式、翻译和真值表命题公式、翻译和真值表48EX5：构造构造(P Q)P的真值表的真值表 PQ(P Q)P(P Q)P00010010101000011100 命题公式、翻译和真值表命题公式、翻译和真值表493 3 等价重言式和蕴含重言式等价重言式和蕴含重言式PQR(PQ)(QR)(PQ)(QR)(PR)0001111100111111010100110111111110001001101010111101000111111111练习：练习：构造构造(PQ)(QR)

35、(PR)的真值表的真值表(PQ)(QR)(PR)50命题公式的类型命题公式的类型定义定义2：一个公式如果对其所有指派均取值为真，则称此类一个公式如果对其所有指派均取值为真，则称此类型公式为型公式为永真公式或叫重言式永真公式或叫重言式。反之，一个公式如果对其反之，一个公式如果对其所有指派均取假值，则称此类型公式为所有指派均取假值，则称此类型公式为永假公式或叫矛盾永假公式或叫矛盾。定义定义3：一个公式如果至少存在一个指派使其取值为真，则一个公式如果至少存在一个指派使其取值为真，则称此公式为称此公式为可满足公式可满足公式。重言式特性重言式特性重言式的否定是矛盾，矛盾的否定是重言式。重言式的否定是矛盾

36、，矛盾的否定是重言式。两个重言式的合取、析取、蕴含、等价均为重言式。两个重言式的合取、析取、蕴含、等价均为重言式。若两个公式的等价是重言式，则此两公式对任何指派若两个公式的等价是重言式，则此两公式对任何指派必同真假必同真假(EX4)。命题公式、翻译和真值表命题公式、翻译和真值表51命题公式的类型命题公式的类型命题公式命题公式可满足公式可满足公式永真式（或重言式）永真式（或重言式）可真可假式可真可假式不可满足公式不可满足公式 （永假式或矛盾式）（永假式或矛盾式）命题公式、翻译和真值表命题公式、翻译和真值表52判断下列公式的类型 例例 A=(qp)qp p q qp (qp)q (qp)qp 0

37、00 11 01 1 1011 0001 111153例例 B=(p q)q p q p p q (p q)(p q)q0 00 11 01 1 110011010010000054例例 C=(p q)r p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 111010105533 等价重言式和蕴含重言式等价重言式和蕴含重言式EX1：构造构造PQ与与PQ的真值表的真值表PQPQ P P Q(PQ)(P Q)001111011111100001111011(PQ)(PQ)3 3 等价重言

38、式和蕴含重言式等价重言式和蕴含重言式56等价重言式等价重言式设设A、B为两个命题公式，为两个命题公式，P1，P2Pn是所有出现于是所有出现于A和和B的的命题变元，如果对于命题变元命题变元，如果对于命题变元P1，P2Pn的任何一组真值指的任何一组真值指派，公式派，公式A和和B都相同，即都相同，即AB是永真式，则称是永真式，则称A与与B是等是等价重言式或是等价的（逻辑等价的），记作价重言式或是等价的（逻辑等价的），记作AB。由上例知：由上例知：(PQ)(PQ)3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式57EX2：证明证明 PQ (PQ)(QP)PQ(P Q)(PQ)(QP)(PQ)(QP

39、)001111010100100010111111两者的真值表相等，故两者的真值表相等，故PQ(PQ)(QP)不难验证：不难验证：P P PP P (P P)Q Q P P Q Q3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式58注意：注意：“”，“”的区别和联系：的区别和联系：区别：区别：（1）“”是命题联结词，是命题联结词，AB是一个命题公式，该是一个命题公式，该公式取值可以是真，可以是假。公式取值可以是真，可以是假。（2）“”不是命题联结词，而是公式的等价关系符，不是命题联结词，而是公式的等价关系符，AB不代表命题，而表示的是命题不代表命题，而表示的是命题A、B有完全相同的有完全相

40、同的真值。真值。联系：联系：AB当且仅当当且仅当AB是永真式。是永真式。3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式59等价公式的性质等价公式的性质 自反性：即对任意公式自反性：即对任意公式A，有，有AA；对称性：即对任意公式对称性：即对任意公式A和和B，若，若AB，则，则BA；传递性：即对任意公式传递性：即对任意公式A和和B，C，若，若AB，BC,则则AC。3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式60设设P、Q、R是命题变元，下表中列出了是命题变元，下表中列出了24个最基本的等值式个最基本的等值式:编号公公 式式E1E1E2E2E3E3E4E4E5E5E6E7E7 PQQ

41、P 交换律交换律 PQQP 交换律交换律(PQ)R P(QR)结合律结合律(PQ)R P(QR)结合律结合律 P(QR)(PQ)(PR)分配律分配律 P(QR)(PQ)(PR)分配律分配律 PFP 同一律同一律 PTP 同一律同一律 P PT 互否律互否律 P PF 互否律互否律 （P）P 双重否定律双重否定律 PPP 等幂律等幂律 PP P 等幂律等幂律 命命题题逻逻辑辑的的基基本本等等式式3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式61命题逻辑的基本等式命题逻辑的基本等式编号编号 公公 式式E8E8E9E9E10E10E11E12E13E14E15PTT 零一律零一律 PFF 零一

42、律零一律P（PQ）P 吸收律吸收律P（PQ）P 吸收律吸收律 （PQ）P Q 德德.摩根定律摩根定律 （PQ）P Q 德德.摩根定律摩根定律PQ PQPQ(PQ)(P Q)P(QR)(PQ)RPQ(PQ)(QP)PQ Q P基基本本的的等等值值式式3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式62命题联结词的归约命题联结词的归约(完备集完备集)由由(PQ)(PQ)(QP)。故可把包含。故可把包含的公式等价变的公式等价变换为包含换为包含“”和和“”的公式。的公式。由由PQ P Q，说明包含，说明包含“”的公式可以变换为包含的公式可以变换为包含“”和和“”的公式。的公式。由由PQ(P Q)，

43、P Q(P Q），说明），说明“”和和“”可以相互代替、故由可以相互代替、故由“”、“”、“”、“”、“”这五个联结词组成命题公式，必这五个联结词组成命题公式，必可以由可以由 、或、或 、组成的命题公式所代替。组成的命题公式所代替。故任意命题公式都可由仅包含故任意命题公式都可由仅包含 、或或 、的命题的命题公式等价代换。公式等价代换。命题联结词的归约命题联结词的归约63定义定义 在一个联结词的集合中，如果一个联结词可在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为由集合中的其他联结词定义，则称此联结词为冗余冗余的联结词的联结词，否则称为，否则称为独立的联结词独立的

44、联结词.例如例如,在联结词集在联结词集,中，由于中，由于 pqp q,所以，所以，为冗余的联结词为冗余的联结词;类似地，类似地，也是冗余的也是冗余的联结词联结词.又在又在,中，由于中，由于 p q(pq)，所以，所以，是冗余的联结词是冗余的联结词.类似地，类似地，也是冗余的联也是冗余的联结词结词.64定义定义 设设S是一个联结词集合，如果任何是一个联结词集合，如果任何n(n 1)元元命题公式都可以由仅含命题公式都可以由仅含S中的联结词构成的公式表中的联结词构成的公式表示，则称示，则称S是是联结词联结词完备集完备集.说明：说明：若若S是联结词全功能集，则任何命题公式都可用是联结词全功能集，则任何

45、命题公式都可用S中的联结词表示中的联结词表示.若若S1,S2是两个联结词集合，且是两个联结词集合，且S1 S2.若若S1是是完备完备集集，则，则S2也是也是完备集完备集.65联结词的联结词的完备集完备集实例实例(1)S1=,(2)S2=,(3)S3=,(4)S4=,(5)S5=,而而,等则不是联结词等则不是联结词完备集完备集.66等价公式的代入规则与替换规则等价公式的代入规则与替换规则 代入规则：代入规则：在等价式中，将某一命题变元在等价式中，将某一命题变元(原子原子)出现的出现的每处每处用用另一个命题公式代入所得到的公式仍是等价式。另一个命题公式代入所得到的公式仍是等价式。EX3:求证求证(

46、PQ)(PQ)为永真式为永真式 证：证：R RT，即，即R R为永真式为永真式现用公式现用公式PQ代入上述公式中的命题变元代入上述公式中的命题变元R则得则得(PQ)(PQ)T故故 (PQ)(PQ)为永真式。为永真式。如：如：在在PQ P Q 中，中，若用公式若用公式(S R)代替代替P，则得到新的等价公式：，则得到新的等价公式：(S R)Q (S R)Q 3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式67替替(置置)换规则：换规则：设设A1是命题公式是命题公式A的子公式，若的子公式，若A1B1，如果，如果将将A中的中的A1用用B1来替换得到公式来替换得到公式B，则，则AB。（如果。（如果

47、A1是命是命题公式的一部分，且题公式的一部分，且A1本身也是一个命题公式，则称本身也是一个命题公式，则称A1为公为公式式A的子公式）的子公式）EX4:求证求证:(PQ)(RQ)(PR)Q证：证：(PQ)(RQ)(P Q)(RQ)(P Q)(RQ)(P R)Q (PR)Q(PR)Q3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式68“代入规则代入规则”和和“替换规则替换规则”的的区别区别：代入只对永真式适用，而替换可以对任何公式进行；代入只对永真式适用，而替换可以对任何公式进行；代入必须处处进行，而替换可以处处替换也可以部分替换；代入必须处处进行，而替换可以处处替换也可以部分替换；代入只针对

48、命题变元进行，而替换则可以针对任何子公式、代入只针对命题变元进行，而替换则可以针对任何子公式、包括命题变元而进行。包括命题变元而进行。3 3 等价重言式和蕴含重言式等价重言式和蕴含重言式69应用举例证明两个公式等值 例例 证明证明 p(qr)(p q)r证证 p(qr)p(q r)（蕴涵等值式，置换规则）（蕴涵等值式，置换规则）(pq)r （结合律，置换规则）（结合律，置换规则）(p q)r （德摩根律，置换规则）（德摩根律，置换规则）(p q)r （蕴涵等值式，置换规则（蕴涵等值式，置换规则）说明说明:也可以从右边开始演算（请做一遍）也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故

49、可不写出因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出熟练后，基本等值式也可以不写出 70应用举例证明两个公式不等值例例 证明证明:p(qr)(pq)r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证明两证明两个公式不等值的基本思想是找到一个赋值使一个成个公式不等值的基本思想是找到一个赋值使一个成真真,另一个成假另一个成假.方法一方法一 真值表法（自己证）真值表法（自己证）方法二方法二 观察赋值法观察赋值法.容易看出容易看出000,010等是左边的等是左边的成真赋值，是右边的成假赋值成真赋值，是右边的成假赋值.方法三方法三 用等值演算先化简两个

50、公式，再观察用等值演算先化简两个公式，再观察.71应用举例判断公式类型 例例 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德摩根律）（德摩根律）p(qq)（交换律，结合律）（交换律，结合律）p 0 （矛盾律）（矛盾律）0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.72例(续)(2)(pq)(qp)解解 (pq)(qp)(p q)(qp)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.问