《第1章 命题逻辑PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第1章 命题逻辑PPT讲稿.ppt（197页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第1章章 命题逻辑命题逻辑第1页，共197页，编辑于2022年，星期日逻辑逻辑形式逻辑形式逻辑辩证逻辑辩证逻辑归纳性归纳性演绎性演绎性数理逻辑研究对象数理逻辑研究对象 辩证逻辑研究思维的内涵即研究思维内在的语义辩证逻辑研究思维的内涵即研究思维内在的语义规律规律 形式逻辑研究思维的外延即研究思维外部表现的形式逻辑研究思维的外延即研究思维外部表现的规律规律第2页，共197页，编辑于2022年，星期日2、数理逻辑的研究方法、数理逻辑的研究方法用数学的方法研究演绎性形式逻辑推理的规律。用数学的方法研究演绎性形式逻辑推理的规律。所谓数学的方法，就是引进一套符号体系，组所谓数学的方法，就是引进一套符号体
2、系，组成一个形式系统，使得对形式逻辑的研究归结为对成一个形式系统，使得对形式逻辑的研究归结为对一整套符号所组成的形式系统的研究，因此数理逻一整套符号所组成的形式系统的研究，因此数理逻辑又称符号逻辑，辑又称符号逻辑，第3页，共197页，编辑于2022年，星期日 著名计算机软件大师狄克斯特著名计算机软件大师狄克斯特(Dijkstra)曾曾经说：经说：“我现在年纪大了，搞了这么多年软件，我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想假如我早错误不知犯了多少，现在觉悟了。我想假如我早年在数理逻辑上好好下点功夫的话，我就不会犯年在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误。
3、不少东西逻辑学家早就说了，可这么多的错误。不少东西逻辑学家早就说了，可我不知道。要是我能年轻我不知道。要是我能年轻20岁的话，我要回去学岁的话，我要回去学逻辑逻辑”。由此可见，数理逻辑对于计算机工作者。由此可见，数理逻辑对于计算机工作者来说是多么的重要。来说是多么的重要。第4页，共197页，编辑于2022年，星期日第一章第一章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联结词1.2 命题公式及分类命题公式及分类 1.3 等值演算等值演算 1.4 联结词全功能集联结词全功能集 1.5 对偶与范式对偶与范式 1.6 推理理论推理理论 1.7 命题演算的自然推理形式系统命题演算的自然推
4、理形式系统N 1.8 例题选解例题选解 习习 题题 一一第5页，共197页，编辑于2022年，星期日1.1 命题符号化及联结词命题符号化及联结词 命题逻辑是数理逻辑的基础，它以命题为研命题逻辑是数理逻辑的基础，它以命题为研究对象，研究基于命题的符号逻辑体系及推理规究对象，研究基于命题的符号逻辑体系及推理规律，也称为命题演算。命题是研究思维规律的科律，也称为命题演算。命题是研究思维规律的科学中的一项基本要素，它是一个判断的语言表达。学中的一项基本要素，它是一个判断的语言表达。第6页，共197页，编辑于2022年，星期日一、命题命题1、命题、命题:能唯一判断真假的陈述句。能唯一判断真假的陈述句。常
5、用常用P、Q、R 或或 p、q、r表示。表示。如果某个陈述句判断为真（与人们公认的客观事实相如果某个陈述句判断为真（与人们公认的客观事实相符），则我们称其为一真命题，并说此命题的真值为真，符），则我们称其为一真命题，并说此命题的真值为真，用用 T 或或 1 表示，否则称为假命题，并说此命题的真值为假，表示，否则称为假命题，并说此命题的真值为假，用用 F 或或 0 表示。表示。第7页，共197页，编辑于2022年，星期日【例【例1.1.1】下述各句均为命题：下述各句均为命题：（1）4是偶数。是偶数。（2）煤是白色的。）煤是白色的。（3）几何原本的作者是欧几里德。）几何原本的作者是欧几里德。（4）
6、2190年人类将移居火星。年人类将移居火星。（5）地球外也有生命存在。）地球外也有生命存在。第8页，共197页，编辑于2022年，星期日上述命题中（上述命题中（1）、（）、（3）是真命题，（）是真命题，（2）是假命）是假命题，其中的（题，其中的（3）可能有人说不出它的真假，但客观上）可能有人说不出它的真假，但客观上能判断真假。（能判断真假。（4）的结果目前谁也不知道，但到了时）的结果目前谁也不知道，但到了时候则真假可辨，即其真值是客观存在的，因而是命题。候则真假可辨，即其真值是客观存在的，因而是命题。同样，（同样，（5）的真值也是客观存在的，只是我们地球人）的真值也是客观存在的，只是我们地球人
7、尚不知道而已，随着科学技术的发展，其真值是可以尚不知道而已，随着科学技术的发展，其真值是可以知道的，因而也是命题。知道的，因而也是命题。第9页，共197页，编辑于2022年，星期日【例【例1.1.2】下列语句不是命题：下列语句不是命题：（1）你好吗？）你好吗？（2）好棒啊！）好棒啊！（3）请勿吸烟。）请勿吸烟。（4）x3。（5）我正在说谎。）我正在说谎。（1）、（）、（2）、（）、（3）均不是陈述句，因而不是命）均不是陈述句，因而不是命题。（题。（4）是陈述句，但它的真假取决于变量）是陈述句，但它的真假取决于变量x的取值，的取值，例如取例如取x为为4时其值为真，取时其值为真，取x为为2时其值为
8、假，即其真时其值为假，即其真值不唯一，因此不是命题。（值不唯一，因此不是命题。（5）也是陈述句，但它是）也是陈述句，但它是悖论，因而也不是命题。悖论，因而也不是命题。第10页，共197页，编辑于2022年，星期日从上面讨论可以看出，判断一个语句是否是命题的关从上面讨论可以看出，判断一个语句是否是命题的关键是：键是：(1)语句必须是陈述句。语句必须是陈述句。(2)陈述句必须具有唯一的真值。要注意两点：陈述句必须具有唯一的真值。要注意两点：一个陈述句在客观上能判断真假，而不受人的知一个陈述句在客观上能判断真假，而不受人的知识范围的限制。识范围的限制。一个陈述句暂时不能确定真值，但到了一定时候就一个
9、陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。可以确定，与一个陈述句的真值不能唯一确定是不同的。第11页，共197页，编辑于2022年，星期日以上所讨论的命题均是一些简单陈述句。在语言以上所讨论的命题均是一些简单陈述句。在语言学中称为简单句，其结构均具有学中称为简单句，其结构均具有“主语主语+谓语谓语”的形的形式，在数理逻辑中，我们将这种由简单句构成的命题式，在数理逻辑中，我们将这种由简单句构成的命题称为称为简单命题简单命题，或称为，或称为原子命题原子命题，用，用p、q、r等符号表示。等符号表示。如：如：p：4是偶数。是偶数。q：煤是白的。：煤是白的
10、。r：几何原本的作者是欧几里德。：几何原本的作者是欧几里德。2、原子命题与复合命题、原子命题与复合命题:第12页，共197页，编辑于2022年，星期日【例【例1.1.3】下列命题不是简单命题：下列命题不是简单命题：（1）4是偶数且是是偶数且是2的倍数。的倍数。（2）北京不是个小城市。）北京不是个小城市。（3）小王或小李考试得第一。）小王或小李考试得第一。（4）如果你努力，则你能成功。）如果你努力，则你能成功。（5）三角形是等边三角形，当且仅当三内角相等。）三角形是等边三角形，当且仅当三内角相等。第13页，共197页，编辑于2022年，星期日上面的命题除（上面的命题除（3）的真假需由具体情况客观
11、判断外，）的真假需由具体情况客观判断外，余者的真值均为余者的真值均为1。但是它们均不是简单命题，分别用了。但是它们均不是简单命题，分别用了“且且”、“非非”、“或或”、“如果如果则则”、“当当且仅当且仅当”等联结词。等联结词。由命题和联结词构成的命题称为由命题和联结词构成的命题称为复合命题复合命题。构成复合。构成复合命题的可以是原子命题，也可以是另一个复合命题。一个命题的可以是原子命题，也可以是另一个复合命题。一个复合命题的真值不仅与构成复合命题的命题的真值有关，复合命题的真值不仅与构成复合命题的命题的真值有关，而且也与所用联结词有关。下面我们给出几个基本的联结而且也与所用联结词有关。下面我们
12、给出几个基本的联结词。词。第14页，共197页，编辑于2022年，星期日二、命题联结词（或逻辑运算符）二、命题联结词（或逻辑运算符）1、否定词否定词：命题命题p加上否定词就形成一个新命题，加上否定词就形成一个新命题，记作记作p，读为非，读为非p，复合命题，复合命题p称为称为p的否定式。的否定式。p的真值由下表所示的称为的真值由下表所示的称为“真值表真值表”的表格确定。的表格确定。pp0110第15页，共197页，编辑于2022年，星期日【例【例1.1.4】(1)p：4是偶数。其真值为是偶数。其真值为1。p ：4不是偶数。其真值为不是偶数。其真值为0。(2)q：这些都是学生。：这些都是学生。q
13、：这些不都是学生。：这些不都是学生。第16页，共197页，编辑于2022年，星期日注：否定联结词使用的原则：将真命题变成假命注：否定联结词使用的原则：将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例如上例中的（个不字就能完成的。例如上例中的（2），），q的否定式的否定式就不能写成就不能写成“这些都不是学生这些都不是学生”。不过，一般地，自然语。不过，一般地，自然语言中的言中的“不不”、“无无”、“没有没有”、“并非并非”等词均等词均可符号化为可符号化为“”第17页，共197页，编辑于2022年，星期日2、合取、合取
14、“”设设 p、q 是任意两个命题，复合命题是任意两个命题，复合命题“p且且q”称为称为p与与q的合取式，记作：的合取式，记作：p q。“”是合取联结词。是合取联结词。P q的真值表如下表所示的真值表如下表所示p qp q0 0 00 101 001 11第18页，共197页，编辑于2022年，星期日【例【例1.1.5】(1)p：4是偶数。是偶数。q：3是素数。则是素数。则 pq：4是偶数且是偶数且3是素数。其真值为是素数。其真值为1。(2)r：煤是白的。则：煤是白的。则 pr：4是偶数且煤是白的。真值为是偶数且煤是白的。真值为0。第19页，共197页，编辑于2022年，星期日注：注：（1）日常
15、语言中的）日常语言中的联结词所联结的语句之间一般联结词所联结的语句之间一般都有一定的内在联系，但数理逻辑中都有一定的内在联系，但数理逻辑中的的联结词是联结词是对对日常语言中日常语言中联结词联结词的的逻辑抽象，因此它所联结的逻辑抽象，因此它所联结的命题其内容可能毫无关系，如上例中的（命题其内容可能毫无关系，如上例中的（2）。）。（2）自然）自然语言中常用的语言中常用的联结词如：联结词如：“既既又又”、“不仅不仅而且而且”、“虽然虽然但是但是”、“和和”等，都可以符号化为等，都可以符号化为“”。第20页，共197页，编辑于2022年，星期日（3）“”联结的是两个命题，并不能见到联结的是两个命题，并
16、不能见到“和和”、“与与”就用就用“”。如，。如，“张三和李四都是好学生张三和李四都是好学生”是是“张三是好学生张三是好学生”和和“李四是好学生李四是好学生”的合取式，但的合取式，但“张三和李四是好朋友张三和李四是好朋友”则是一个简单命题，其中则是一个简单命题，其中“张三和李四张三和李四”是句子的主语。是句子的主语。第21页，共197页，编辑于2022年，星期日3、析取、析取“”设设 p、q 是任意两个命题，复合命题是任意两个命题，复合命题“p p 或或 q q”称为称为p、q的的析取式，记作：析取式，记作：p q。“”称为析取联结词。称为析取联结词。P q的的真值表如下表所示：真值表如下表所
17、示：p qp q0 0 00 111 011 11第22页，共197页，编辑于2022年，星期日【例【例1.1.6】(1)p：小王喜欢唱歌。：小王喜欢唱歌。q：小王喜欢跳舞。则：小王喜欢跳舞。则 pq：小王喜欢唱歌或喜欢跳舞。：小王喜欢唱歌或喜欢跳舞。(2)p：明天刮风。：明天刮风。q：明天下雨。则：明天下雨。则 pq：明天或者刮风或者下雨。：明天或者刮风或者下雨。第23页，共197页，编辑于2022年，星期日注：自然语言中常用的联结词如：注：自然语言中常用的联结词如：“或者或者或者或者”、“可能可能可能可能”等，都可以符号化为等，都可以符号化为“”“”。但。但日常语言中的日常语言中的“或或”
18、是具有二义性的，用是具有二义性的，用“或或”联结的联结的命题有时是具有相容性的，如命题有时是具有相容性的，如【例【例1.1.6】中的二例，我们中的二例，我们称之为可兼或。而有时又具有排斥性，称为不可兼或（异或）称之为可兼或。而有时又具有排斥性，称为不可兼或（异或），如：，如：（1 1）小李明天出差去上海或去广州。）小李明天出差去上海或去广州。（2 2）张三这次考试可能是全班第一也可能是全班第二。）张三这次考试可能是全班第一也可能是全班第二。“不可兼或不可兼或”不能用不能用“”“”联结，这在后面联结，这在后面命题命题联结词的扩联结词的扩充中介绍。充中介绍。第24页，共197页，编辑于2022年，
19、星期日4 4、蕴涵、蕴涵“”“”设设 p p、q q 是任意两个命题，复合命题是任意两个命题，复合命题“如果如果 p p，则，则q q”称为称为 p p 与与q q 的蕴涵式，记作：的蕴涵式，记作：p p q q。p p 称为蕴涵式的前件，称为蕴涵式的前件，q q 称为蕴涵式的后件，称为蕴涵式的后件，称为蕴涵联结词。称为蕴涵联结词。P P q q 的真值的真值表如下表所示：表如下表所示：p qp q0 0 10 111 001 11第25页，共197页，编辑于2022年，星期日【例【例1.1.7】(1)p：天下雨了。：天下雨了。q：路面湿了。则：路面湿了。则 pq：如果天下雨，则路面湿。：如果
20、天下雨，则路面湿。(2)r：三七二十一。则：三七二十一。则 pr：如果天下雨，则三七二十一。：如果天下雨，则三七二十一。注：注：(1)(1)逻辑中，前件逻辑中，前件p p为假时，无论后件为假时，无论后件q q是真是假，是真是假，蕴涵式蕴涵式p pq q的真值均为的真值均为1 1。第26页，共197页，编辑于2022年，星期日（2 2）正如前面所说，数理逻辑中的联结词是对日常）正如前面所说，数理逻辑中的联结词是对日常语言中的联结词的一种逻辑抽象，日常语言中联结词语言中的联结词的一种逻辑抽象，日常语言中联结词所联结的句子之间是有一定内在联系的，但在数理逻所联结的句子之间是有一定内在联系的，但在数理
21、逻辑中，联结词所联结的命题可以毫无关系。如在日常辑中，联结词所联结的命题可以毫无关系。如在日常语言中语言中“如果如果则则”所联结的句子之间表现的所联结的句子之间表现的是一种因果关系，如是一种因果关系，如【例【例1.1.7】中的（中的（1 1）。但在数理）。但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的，如不相关的，如【例【例1.1.7】中的（中的（2 2）。）。第27页，共197页，编辑于2022年，星期日（3 3）p p q q 的逻辑关系是：的逻辑关系是：p p 是是 q q 的充分条的充分条件，件，q q 是是 p p 的必要
22、条件。在日常语言中，特别是的必要条件。在日常语言中，特别是在数学语言中，在数学语言中，q q 是是 p p 的必要条件还有许多不同的必要条件还有许多不同的叙述方式，如：的叙述方式，如：“p p 仅当仅当q q（仅当（仅当q q，则，则p p）”、“只有只有q q 才才p p”、“只要只要 p p 就就q q”、“除非除非q q，否则，否则非非p p（非（非p p，除非，除非q q）”等，均可符号化成等，均可符号化成 p p q q 的形的形式。式。第28页，共197页，编辑于2022年，星期日【例【例1.1.8】符号化下列命题：符号化下列命题：（1 1）只要天下雨，我就回家。）只要天下雨，我就
23、回家。（2 2）只有天下雨，我才回家。）只有天下雨，我才回家。（3 3）除非天下雨，否则我不回家。）除非天下雨，否则我不回家。（4 4）仅当天下雨，我才回家。）仅当天下雨，我才回家。解：解：设设 p p：天下雨。：天下雨。q q：我回家。则（：我回家。则（1 1）符号化为）符号化为p p q q。（。（2 2）、（）、（3 3）、（）、（4 4）均符号化为）均符号化为q q p p（或等（或等价形式：价形式：p p q q ）第29页，共197页，编辑于2022年，星期日5 5、等价、等价“”设设 p p、q q 是任意两个命题，复合命题是任意两个命题，复合命题“p p当且仅当当且仅当q q”
24、称称为为 p p 与与 q q 的等价式，记作：的等价式，记作：p p q q。“”称为等价联结称为等价联结词。词。p p q q的真值表如下表所示：的真值表如下表所示：p qp q0 0 10 101 001 11第30页，共197页，编辑于2022年，星期日【例【例1.1.9】(1)p：2+2=4。q：5是素数。则是素数。则 pq：2+2=4当且仅当当且仅当5是素数。是素数。(2)p：A=B。q：二角是同位角。则：二角是同位角。则 pq：A=B当且仅当二角是同位角。当且仅当二角是同位角。在（在（1）中的）中的p与与q并无内在关系，但因二者均为真，并无内在关系，但因二者均为真，所以所以pq的
25、真值为的真值为1。在（在（2）中由于相等的两角不一定是同位角，所以）中由于相等的两角不一定是同位角，所以真值为真值为0。第31页，共197页，编辑于2022年，星期日 以上定义了以上定义了5 种联结词，它们构成了一个联结词种联结词，它们构成了一个联结词集合集合 ，其中，其中 是一元是一元联结联结词，其余均为二词，其余均为二元元联结词。联结词。由原子命题通过命题联结词可构成各种形式的复合由原子命题通过命题联结词可构成各种形式的复合命题，在对自然语言形式化时，过程如下：命题，在对自然语言形式化时，过程如下：(1)用用p，q，r 等字母表示原子命题；等字母表示原子命题；(2)用命题联结词，将原子命题
26、联结起来，但用命题联结词，将原子命题联结起来，但5 个联结词的个联结词的含义由其真值表唯一确定，而不是由其自然语言的含义确含义由其真值表唯一确定，而不是由其自然语言的含义确定。定。第32页，共197页，编辑于2022年，星期日在使用括号时作下列规定：在使用括号时作下列规定：(1)括号均用圆括号；括号均用圆括号；(2)5 个联结词的结合能力强弱顺序为：个联结词的结合能力强弱顺序为：，凡符合此顺序者，括号均可除去；凡符合此顺序者，括号均可除去；(3)具有相同结合能力的联结词，按其出现的先后次具有相同结合能力的联结词，按其出现的先后次序，先出现先运算，凡符合此要求者，括号均可除去；序，先出现先运算，
27、凡符合此要求者，括号均可除去；(4)最外层括号可省去。最外层括号可省去。第33页，共197页，编辑于2022年，星期日【例【例1.1.10】将下列自然语言形式化】将下列自然语言形式化:（1）如果天不下雨并且不刮风，我就去书店。）如果天不下雨并且不刮风，我就去书店。（2）小王边走边唱。）小王边走边唱。（3）除非）除非a能被能被2整除，否则整除，否则a不能被不能被4整除。整除。（4）此时，小纲要么在学习，要么在玩游戏。）此时，小纲要么在学习，要么在玩游戏。（5）如果天不下雨，我们去打篮球，除非班上有）如果天不下雨，我们去打篮球，除非班上有会。会。第34页，共197页，编辑于2022年，星期日解解（
28、1）设）设 p：今天天下雨，：今天天下雨，q：今天天刮风，：今天天刮风，r：我：我去书店。则原命题符号化为：去书店。则原命题符号化为：p q r (2)设设 p：小王走路，：小王走路，q：小王唱歌。则原命题符号：小王唱歌。则原命题符号化为：化为：pq (3)设设 p：a 能被能被2整除，整除，q：a 能被能被4整除。则原命整除。则原命题符号化为：题符号化为：p q 或或 q p第35页，共197页，编辑于2022年，星期日(4)设设 p：小刚在学习，：小刚在学习，q：小刚在玩游戏。则原命题：小刚在玩游戏。则原命题符号化为：符号化为：(p q)(p q)或或 (p q)(p q)(5)设设 p：
29、今天天下雨，：今天天下雨，q：我们去打篮球，：我们去打篮球，r：今：今天班上有会。则原命题符号化为：天班上有会。则原命题符号化为：r (p q)第36页，共197页，编辑于2022年，星期日1.2 命题公式及分类命题公式及分类 为了用数学的方法研究命题，就必须像数学处理为了用数学的方法研究命题，就必须像数学处理问题那样将命题公式化，并讨论对于这些公式的演算问题那样将命题公式化，并讨论对于这些公式的演算（推理）规则，以期由给定的公式推导出新的命题公（推理）规则，以期由给定的公式推导出新的命题公式来。式来。第37页，共197页，编辑于2022年，星期日一、命题公式一、命题公式 命题常元与命题变元：
30、命题常元与命题变元：前面我们用前面我们用p、q、r等符号表示确定的简单命题，等符号表示确定的简单命题，通常称它们为命题常元，由于一个确定的命题是一个通常称它们为命题常元，由于一个确定的命题是一个常值命题，它们的真值只可能是常值命题，它们的真值只可能是1或或0，所以一般称所以一般称1和和0为为命题常元命题常元。第38页，共197页，编辑于2022年，星期日 为了更广泛地应用命题演算，我们用为了更广泛地应用命题演算，我们用p、q、r等符等符号表示一个任意的没有赋予具体内容的简单命题，就号表示一个任意的没有赋予具体内容的简单命题，就如同数学公式中的变量如同数学公式中的变量 x 一样，我们称其为一样，
31、我们称其为命题变元命题变元。即命题变元即命题变元 是一个不确指的（抽象的）命题，以真、是一个不确指的（抽象的）命题，以真、假为其变域，以假为其变域，以p、q、r等表之。等表之。第39页，共197页，编辑于2022年，星期日 命题公式命题公式 命题公式命题公式 ：由命题变元（常元）符、联结词和：由命题变元（常元）符、联结词和圆括号按一定逻辑关系联结起来的字符串。圆括号按一定逻辑关系联结起来的字符串。所谓按一定的逻辑关系，即字符串的构成要求所谓按一定的逻辑关系，即字符串的构成要求合理。合理的命题公式叫做合式公式，也称真值函合理。合理的命题公式叫做合式公式，也称真值函数。数。第40页，共197页，编
32、辑于2022年，星期日定义定义1.2.1：合式公式（或简称公式）的递归定义：合式公式（或简称公式）的递归定义：单个的命题变元（或常元）是合式公式。单个的命题变元（或常元）是合式公式。；如果如果A和和B是合式公式，则是合式公式，则A、AB、AB、AB、AB是是合式合式公式；公式；只有有限次应用条款只有有限次应用条款、生成的公式才是生成的公式才是合式合式 公式。公式。例：说明例：说明是合式公式。是合式公式。又如又如第41页，共197页，编辑于2022年，星期日定义定义1.2.2(1)若若A是单个命题（变元或常元），则称为是单个命题（变元或常元），则称为0层公式。层公式。(2)称称A为为n+1（n0
33、）层公式是指）层公式是指A符合下列诸情况之一：符合下列诸情况之一：A=B，B是是n层公式；层公式；A=BC，其中，其中B为为i层公式、层公式、C为为j层公式，层公式，n=max（i，j）；）；A=BC，其中，其中B、C的层次同的层次同；A=BC，其中，其中B、C的层次同的层次同；A=B C，其中，其中B、C的层次同的层次同。第42页，共197页，编辑于2022年，星期日【例【例1.2.1】：公式：公式：A=（p q）r。解释解释1：假设：假设 p：现在是白天，：现在是白天，q：现在是晴天，：现在是晴天，r：我：我们能看见太阳。则们能看见太阳。则 A：如果现在是白天且是晴天，则我们能看见太阳。其
34、：如果现在是白天且是晴天，则我们能看见太阳。其真值为真值为1。解释解释2：假设：假设 p、q如上，如上，r：我们能看见星星。则：我们能看见星星。则 A：如果现在是白天且是晴天，则我们能看见星星。其真：如果现在是白天且是晴天，则我们能看见星星。其真值为值为0。第43页，共197页，编辑于2022年，星期日由此可见，不同的解释可使公式有不同的真值。事实由此可见，不同的解释可使公式有不同的真值。事实上，对于命题变元无论做什么样的解释，它都只有两种结上，对于命题变元无论做什么样的解释，它都只有两种结果：或者是果：或者是“真真”，或者是，或者是“假假”。从而由变元和联结。从而由变元和联结词组成的公式所表
35、示的复合命题，也是或为词组成的公式所表示的复合命题，也是或为“真真”，或，或为为“假假”。因此命题公式可看成是一个以真、假为。因此命题公式可看成是一个以真、假为定义域，以真、假为值域的函数，故也称定义域，以真、假为值域的函数，故也称真值函数真值函数。不同的解释可看作是对命题变元不同的不同的解释可看作是对命题变元不同的“赋值赋值”。第44页，共197页，编辑于2022年，星期日如【例如【例1.2.1】中】中解释解释 1 实际上是对变元实际上是对变元 p、q、r 赋值赋值111，得，得A的真值为的真值为1；解释解释 2 实际上是对变元实际上是对变元 p、q、r 赋值赋值110，得，得A的真值为的真
36、值为0；公式公式A的真值是在对的真值是在对 p、q、r 的某种赋值下所得的真的某种赋值下所得的真值。值。第45页，共197页，编辑于2022年，星期日 真值表真值表1、赋值（或真值指派）：、赋值（或真值指派）：在合式公式中，每一个变元的一在合式公式中，每一个变元的一组确定的真值称为公式的一个赋值。组确定的真值称为公式的一个赋值。每一个赋值对应公式的一个确定的值每一个赋值对应公式的一个确定的值 有有n个变元的公式有个变元的公式有2n种不同的赋值。种不同的赋值。有有n个命题变元个命题变元 的公式的公式 称使称使A的真值为真的赋值为成真赋值，使的真值为真的赋值为成真赋值，使A的真值为假的真值为假的赋
37、值为成假赋值。的赋值为成假赋值。第46页，共197页，编辑于2022年，星期日如【例如【例1.2.1】中，】中，111是是A=（p q）r的成真的成真赋值，赋值，110是是A的成假赋值。根据前面对联结词的讨的成假赋值。根据前面对联结词的讨论知：论知：000、001、010、011、100、101也都是也都是A的成真赋值。的成真赋值。第47页，共197页，编辑于2022年，星期日 将公式将公式A在所有赋值情况下的取值列成表，称为在所有赋值情况下的取值列成表，称为A的真值表。的真值表。构造真值表的步骤如下：构造真值表的步骤如下：（1）找出命题公式中所含的所有命题变元并按下标或）找出命题公式中所含的
38、所有命题变元并按下标或字典顺序给出；字典顺序给出；（2）按从低到高的顺序写出各层次；）按从低到高的顺序写出各层次；（3）顺序列出所有的赋值（）顺序列出所有的赋值（2n个）；对应每个赋值，个）；对应每个赋值，计算命题公式各层次的真值，直到最后计算出命题公式计算命题公式各层次的真值，直到最后计算出命题公式的真值。的真值。2、真值表：、真值表：第48页，共197页，编辑于2022年，星期日【例【例1.2.2】：求下列命题公式的真值表：求下列命题公式的真值表：(1)(2)(3)解解:公式公式(1)、(2)、(3)的真值表分别如表的真值表分别如表1、表、表2、表表3所示。所示。第49页，共197页，编辑
39、于2022年，星期日pq p p q(p q)q00101011111000111001表表 1第50页，共197页，编辑于2022年，星期日表表 2pqp q(p q)qp q(p q)(p q)(p q)00101010011000101001110011100010第51页，共197页，编辑于2022年，星期日表表 3 pqr p q r(p q)r000111001100010111011100100010101000110111111100第52页，共197页，编辑于2022年，星期日 由上可知，有的公式在任何赋值情况下真值恒由上可知，有的公式在任何赋值情况下真值恒为为1，如（，如（
40、1）；有的公式在任何赋值情况下真值恒）；有的公式在任何赋值情况下真值恒为为0，如（，如（2）；有的公式某些赋值使其真值为）；有的公式某些赋值使其真值为1，而另一些赋值使其真值为而另一些赋值使其真值为0，如（，如（3）；因此可将公）；因此可将公式分为三类。式分为三类。第53页，共197页，编辑于2022年，星期日（一）、（一）、定义：定义：一个公式若对其所有赋值均取值为真，则称为一个公式若对其所有赋值均取值为真，则称为重言式重言式（或永真式）（或永真式）。一个公式若对其所有赋值均取值为假，则称为一个公式若对其所有赋值均取值为假，则称为矛盾矛盾式式（或永假式）。（或永假式）。一个公式若至少存在一个
41、赋值使其取值为真，则一个公式若至少存在一个赋值使其取值为真，则称为称为可满足式可满足式。二、公式的类型二、公式的类型 第54页，共197页，编辑于2022年，星期日重言式的特点重言式的特点 重言式的否定是矛盾式；矛盾式的否定是重言式的否定是矛盾式；矛盾式的否定是重言式。重言式。重言式的合取、析取、蕴含、等价都是重言式。重言式的合取、析取、蕴含、等价都是重言式。第55页，共197页，编辑于2022年，星期日 两种特殊的重言式两种特殊的重言式1、等价重言式（或恒等式）等价重言式（或恒等式）定义：定义：设设A、B是公式，若是公式，若AB是重言式，则称是重言式，则称AB是是等价重言式，记为等价重言式，
42、记为AB，也称逻辑恒等式。，也称逻辑恒等式。注意：注意：“”与与“”是两个完全不同的符号。是两个完全不同的符号。“”是联结词，是联结词，A AB B是一个公式。是一个公式。“”不是联结词，不是联结词，而是两个公式之间的关系符，而是两个公式之间的关系符，AB并不是一个公式，而并不是一个公式，而只是表示只是表示A A与与B B是两个真值相同的公式。是两个真值相同的公式。第56页，共197页，编辑于2022年，星期日 证明证明AB的方法的方法 用真值表证明；用真值表证明；用等值演算。用等值演算。定理：定理：AB为重言式，当且仅当为重言式，当且仅当A、B具有相同的真值具有相同的真值表。表。第57页，共
43、197页，编辑于2022年，星期日例例1：用真值表判断下列各组公式是否等价用真值表判断下列各组公式是否等价 pq pq p(q p)p q001100011011100100110100第58页，共197页，编辑于2022年，星期日 pqrp q p q(p q)rr(p q)rr00010010011011010100101110111000011101001111011001111111第59页，共197页，编辑于2022年，星期日(3)常用的逻辑恒等式（或基本等价重言式）常用的逻辑恒等式（或基本等价重言式）利用真值表我们可以证明许多恒等式利用真值表我们可以证明许多恒等式第60页，共197
44、页，编辑于2022年，星期日第61页，共197页，编辑于2022年，星期日第62页，共197页，编辑于2022年，星期日第63页，共197页，编辑于2022年，星期日2、蕴含重言式（或永真蕴含式）、蕴含重言式（或永真蕴含式）定义：定义：设设A、B是公式，若是公式，若AB是重言式，则称是重言式，则称AB是蕴含重言式，记为是蕴含重言式，记为AB。同样：同样：“”与与“”是两个完全不同的符号。是两个完全不同的符号。“”是联结词，是联结词，A A B B是一个公式。是一个公式。“”不是联结词，而不是联结词，而是两个公式之间的关系符，是两个公式之间的关系符，AB并不是一个公式，并不是一个公式，而只是表示
45、而只是表示 A AB B 是重言式是重言式。第64页，共197页，编辑于2022年，星期日例例2：试证：试证 pqp qp (p q)p (p q)q00101011011000111111 证明证明AB的方法的方法 用真值表证明用真值表证明第65页，共197页，编辑于2022年，星期日 用分析法证明用分析法证明）假设前件是真，若能推出后件是真，则）假设前件是真，若能推出后件是真，则AB。）假设后件是假，若能推出前件是假，则）假设后件是假，若能推出前件是假，则AB。例例3：用分析法证明：用分析法证明：用等值演算。用等值演算。第66页，共197页，编辑于2022年，星期日 基本的蕴含重言式。基本
46、的蕴含重言式。第67页，共197页，编辑于2022年，星期日3、等价重言式与蕴含重言式的性质、等价重言式与蕴含重言式的性质 自反性：对任意自反性：对任意A有：有：AA、AA 对称性：若对称性：若AB，则，则BA 反对称性：若反对称性：若AB且且BA，则，则AB 传递性：若传递性：若AB，BC，则，则AC 若若AB，BC，则，则AC(5)若若AB，AC，则，则ABC第68页，共197页，编辑于2022年，星期日1.3 等值演算等值演算 一、一、定义：定义：由已知的等值式推演出另一些等值式的由已知的等值式推演出另一些等值式的过程称为等值演算。过程称为等值演算。二、等值演算中使用的规则：二、等值演算
47、中使用的规则：1、代入规则：、代入规则：在重言式中，将某一命题变元全用同一命题公式代入后，在重言式中，将某一命题变元全用同一命题公式代入后，得到的公式仍是重言式得到的公式仍是重言式。第69页，共197页，编辑于2022年，星期日2、替换规则：、替换规则：子公式：子公式：设设 是命题公式且是命题公式是命题公式且是命题公式A的一部分，则称的一部分，则称 是是A的子公式。的子公式。替换规则：替换规则：设设 是含有子公式是含有子公式A的命题公式，的命题公式，BA，则可用则可用B替换替换 中的中的A，得，得，保证，保证 第70页，共197页，编辑于2022年，星期日例例1：用等值演算法验证下列重言式用等
48、值演算法验证下列重言式(1)(1)证明：证明：第71页，共197页，编辑于2022年，星期日(2)(2)证明：证明：第72页，共197页，编辑于2022年，星期日(3)(3)证明：证明：第73页，共197页，编辑于2022年，星期日(4)(4)证明：证明：第74页，共197页，编辑于2022年，星期日(5)(5)证明：证明：第75页，共197页，编辑于2022年，星期日(6)(6)证明：证明：第76页，共197页，编辑于2022年，星期日例例2：用等值演算法判断公式的类型，并求出公式的用等值演算法判断公式的类型，并求出公式的成真赋值和成假赋值。成真赋值和成假赋值。(1)(1)解：解：第77页，
49、共197页，编辑于2022年，星期日即公式是矛盾式，没有成真赋值，所有赋值都是成假即公式是矛盾式，没有成真赋值，所有赋值都是成假赋值，即成假赋值为赋值，即成假赋值为000，001，010，011，100，101，110，111。第78页，共197页，编辑于2022年，星期日(2)(2)即公式是重言式，没有成假赋值，所有赋值都是成真赋即公式是重言式，没有成假赋值，所有赋值都是成真赋值，即成真赋值为值，即成真赋值为00，01，10，11。第79页，共197页，编辑于2022年，星期日(3)(3)即公式是可满足式，成假赋值为即公式是可满足式，成假赋值为00，01，成真赋值为，成真赋值为10，11。第
50、80页，共197页，编辑于2022年，星期日 等值演算在计算机硬件设计，开关理论和电子元等值演算在计算机硬件设计，开关理论和电子元器件中都占据重要地位。器件中都占据重要地位。第81页，共197页，编辑于2022年，星期日1.4 联结词全功能集联结词全功能集 一、命题联结词的扩充一、命题联结词的扩充 1、异或、异或(不可兼或不可兼或)：命题：命题p与与q的异或的异或 记为记为2、与非：命题、与非：命题p与与q的与非记为的与非记为3、或非：命题、或非：命题P与与Q的或非记为的或非记为4、蕴含否定：命题、蕴含否定：命题P与与Q的蕴含否定记为的蕴含否定记为第82页，共197页，编辑于2022年，星期日