第1章 命题逻辑优秀课件.ppt

《第1章 命题逻辑优秀课件.ppt》由会员分享，可在线阅读，更多相关《第1章 命题逻辑优秀课件.ppt（197页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第1章章 命题逻辑命题逻辑第1页，本讲稿共197页逻辑逻辑形式逻辑形式逻辑辩证逻辑辩证逻辑归纳性归纳性演绎性演绎性数理逻辑研究对象数理逻辑研究对象 辩证逻辑研究思维的内涵即研究思维内在的语义辩证逻辑研究思维的内涵即研究思维内在的语义规律规律 形式逻辑研究思维的外延即研究思维外部表形式逻辑研究思维的外延即研究思维外部表现的规律现的规律第2页，本讲稿共197页2、数理逻辑的研究方法、数理逻辑的研究方法用数学的方法研究演绎性形式逻辑推理的规律。用数学的方法研究演绎性形式逻辑推理的规律。所谓数学的方法，就是引进一套符号体系，组成所谓数学的方法，就是引进一套符号体系，组成一个形式系统，使得对形式逻辑的

2、研究归结为对一整一个形式系统，使得对形式逻辑的研究归结为对一整套符号所组成的形式系统的研究，因此数理逻辑又称套符号所组成的形式系统的研究，因此数理逻辑又称符号逻辑，符号逻辑，第3页，本讲稿共197页 著名计算机软件大师狄克斯特著名计算机软件大师狄克斯特(Dijkstra)曾曾经说：经说：“我现在年纪大了，搞了这么多年软件，我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想假如我早错误不知犯了多少，现在觉悟了。我想假如我早年在数理逻辑上好好下点功夫的话，我就不会犯年在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说了，可这么多的错误。不少东西逻辑学家早

3、就说了，可我不知道。要是我能年轻我不知道。要是我能年轻20岁的话，我要回去学岁的话，我要回去学逻辑逻辑”。由此可见，数理逻辑对于计算机工作者。由此可见，数理逻辑对于计算机工作者来说是多么的重要。来说是多么的重要。第4页，本讲稿共197页第一章第一章 命题逻辑命题逻辑 1.1 命题符号化及联结词命题符号化及联结词1.2 命题公式及分类命题公式及分类 1.3 等值演算等值演算 1.4 联结词全功能集联结词全功能集 1.5 对偶与范式对偶与范式 1.6 推理理论推理理论 1.7 命题演算的自然推理形式系统命题演算的自然推理形式系统N 1.8 例题选解例题选解 习习 题题 一一第5页，本讲稿共197页

4、1.1 命题符号化及联结词命题符号化及联结词 命题逻辑是数理逻辑的基础，它以命题为研命题逻辑是数理逻辑的基础，它以命题为研究对象，研究基于命题的符号逻辑体系及推理规究对象，研究基于命题的符号逻辑体系及推理规律，也称为命题演算。命题是研究思维规律的科律，也称为命题演算。命题是研究思维规律的科学中的一项基本要素，它是一个判断的语言表达。学中的一项基本要素，它是一个判断的语言表达。第6页，本讲稿共197页一、命题命题1、命题、命题:能唯一判断真假的陈述句。能唯一判断真假的陈述句。常用常用P、Q、R 或或 p、q、r表示。表示。如果某个陈述句判断为真（与人们公认的客观事如果某个陈述句判断为真（与人们公

5、认的客观事实相符），则我们称其为一真命题，并说此命题的真实相符），则我们称其为一真命题，并说此命题的真值为真，用值为真，用 T 或或 1 表示，否则称为假命题，并说此命表示，否则称为假命题，并说此命题的真值为假，用题的真值为假，用 F 或或 0 表示。表示。第7页，本讲稿共197页【例【例1.1.1】下述各句均为命题：下述各句均为命题：（1）4是偶数。是偶数。（2）煤是白色的。）煤是白色的。（3）几何原本的作者是欧几里德。）几何原本的作者是欧几里德。（4）2190年人类将移居火星。年人类将移居火星。（5）地球外也有生命存在。）地球外也有生命存在。第8页，本讲稿共197页上述命题中（上述命题中（

6、1）、（）、（3）是真命题，（）是真命题，（2）是假）是假命题，其中的（命题，其中的（3）可能有人说不出它的真假，但客）可能有人说不出它的真假，但客观上能判断真假。（观上能判断真假。（4）的结果目前谁也不知道，但）的结果目前谁也不知道，但到了时候则真假可辨，即其真值是客观存在的，因到了时候则真假可辨，即其真值是客观存在的，因而是命题。同样，（而是命题。同样，（5）的真值也是客观存在的，只）的真值也是客观存在的，只是我们地球人尚不知道而已，随着科学技术的发展，是我们地球人尚不知道而已，随着科学技术的发展，其真值是可以知道的，因而也是命题。其真值是可以知道的，因而也是命题。第9页，本讲稿共197页

7、【例【例1.1.2】下列语句不是命题：下列语句不是命题：（1）你好吗？）你好吗？（2）好棒啊！）好棒啊！（3）请勿吸烟。）请勿吸烟。（4）x3。（5）我正在说谎。）我正在说谎。（1）、（）、（2）、（）、（3）均不是陈述句，因而不是命）均不是陈述句，因而不是命题。（题。（4）是陈述句，但它的真假取决于变量）是陈述句，但它的真假取决于变量x的取值，的取值，例如取例如取x为为4时其值为真，取时其值为真，取x为为2时其值为假，即其真时其值为假，即其真值不唯一，因此不是命题。（值不唯一，因此不是命题。（5）也是陈述句，但它是）也是陈述句，但它是悖论，因而也不是命题。悖论，因而也不是命题。第10页，本讲

8、稿共197页从上面讨论可以看出，判断一个语句是否是命题的关键从上面讨论可以看出，判断一个语句是否是命题的关键是：是：(1)语句必须是陈述句。语句必须是陈述句。(2)陈述句必须具有唯一的真值。要注意两点：陈述句必须具有唯一的真值。要注意两点：一个陈述句在客观上能判断真假，而不受人的知识范一个陈述句在客观上能判断真假，而不受人的知识范围的限制。围的限制。一个陈述句暂时不能确定真值，但到了一定时一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是候就可以确定，与一个陈述句的真值不能唯一确定是不同的。不同的。第11页，本讲稿共197页以上所讨论的命题均是一些简单陈述句

9、。在语言学中称以上所讨论的命题均是一些简单陈述句。在语言学中称为简单句，其结构均具有为简单句，其结构均具有“主语主语+谓语谓语”的形式，在数理的形式，在数理逻辑中，我们将这种由简单句构成的命题称为逻辑中，我们将这种由简单句构成的命题称为简单命简单命题题，或称为，或称为原子命题原子命题，用，用p、q、r等符号表示。如：等符号表示。如：p：4是偶数。是偶数。q：煤是白的。：煤是白的。r：几何原本的作者是欧几里德。：几何原本的作者是欧几里德。2、原子命题与复合命题、原子命题与复合命题:第12页，本讲稿共197页【例【例1.1.3】下列命题不是简单命题：下列命题不是简单命题：（1）4是偶数且是是偶数且

10、是2的倍数。的倍数。（2）北京不是个小城市。）北京不是个小城市。（3）小王或小李考试得第一。）小王或小李考试得第一。（4）如果你努力，则你能成功。）如果你努力，则你能成功。（5）三角形是等边三角形，当且仅当三内角相等。）三角形是等边三角形，当且仅当三内角相等。第13页，本讲稿共197页上面的命题除（上面的命题除（3）的真假需由具体情况客观判断外，）的真假需由具体情况客观判断外，余者的真值均为余者的真值均为1。但是它们均不是简单命题，分别用了。但是它们均不是简单命题，分别用了“且且”、“非非”、“或或”、“如果如果则则”、“当且当且仅当仅当”等联结词。等联结词。由命题和联结词构成的命题称为由命题

11、和联结词构成的命题称为复合命题复合命题。构成复。构成复合命题的可以是原子命题，也可以是另一个复合命题。合命题的可以是原子命题，也可以是另一个复合命题。一个复合命题的真值不仅与构成复合命题的命题的真值一个复合命题的真值不仅与构成复合命题的命题的真值有关，而且也与所用联结词有关。下面我们给出几个基有关，而且也与所用联结词有关。下面我们给出几个基本的联结词。本的联结词。第14页，本讲稿共197页二、命题联结词（或逻辑运算符）二、命题联结词（或逻辑运算符）1、否定词否定词：命题命题p加上否定词就形成一个新命题，加上否定词就形成一个新命题，记作记作p，读为非，读为非p，复合命题，复合命题p称为称为p的否

12、定式。的否定式。p的真值由下表所示的称为的真值由下表所示的称为“真值表真值表”的表格确定。的表格确定。pp0110第15页，本讲稿共197页【例【例1.1.4】(1)p：4是偶数。其真值为是偶数。其真值为1。p ：4不是偶数。其真值为不是偶数。其真值为0。(2)q：这些都是学生。：这些都是学生。q ：这些不都是学生。：这些不都是学生。第16页，本讲稿共197页注：否定联结词使用的原则：将真命题变成假命题，将注：否定联结词使用的原则：将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例如上例中的（成的。例如上例中的

13、（2），），q的否定式就不能写成的否定式就不能写成“这这些都不是学生些都不是学生”。不过，一般地，自然语言中的。不过，一般地，自然语言中的“不不”、“无无”、“没有没有”、“并非并非”等词均可符号化为等词均可符号化为“”第17页，本讲稿共197页2、合取、合取“”设设 p、q 是任意两个命题，复合命题是任意两个命题，复合命题“p且且q”称为称为p与与q的合取式，记作：的合取式，记作：p q。“”是合取联结词。是合取联结词。P q的真值表如下表所示的真值表如下表所示p qp q0 0 00 101 001 11第18页，本讲稿共197页【例【例1.1.5】(1)p：4是偶数。是偶数。q：3是素数

14、。则是素数。则 pq：4是偶数且是偶数且3是素数。其真值为是素数。其真值为1。(2)r：煤是白的。则：煤是白的。则 pr：4是偶数且煤是白的。真值为是偶数且煤是白的。真值为0。第19页，本讲稿共197页注：注：（1）日常语言中的）日常语言中的联结词所联结的语句之间一般联结词所联结的语句之间一般都有一定的内在联系，但数理逻辑中都有一定的内在联系，但数理逻辑中的的联结词是对联结词是对日常语言中日常语言中联结词联结词的的逻辑抽象，因此它所联结的命逻辑抽象，因此它所联结的命题其内容可能毫无关系，如上例中的（题其内容可能毫无关系，如上例中的（2）。）。（2）自然）自然语言中常用的语言中常用的联结词如：联

15、结词如：“既既又又”、“不仅不仅而且而且”、“虽然虽然但是但是”、“和和”等，都可以符号化为等，都可以符号化为“”。第20页，本讲稿共197页（3）“”联结的是两个命题，并不能见到联结的是两个命题，并不能见到“和和”、“与与”就用就用“”。如，。如，“张三和李四都是好学张三和李四都是好学生生”是是“张三是好学生张三是好学生”和和“李四是好学生李四是好学生”的的合取式，但合取式，但“张三和李四是好朋友张三和李四是好朋友”则是一个简则是一个简单命题，其中单命题，其中“张三和李四张三和李四”是句子的主语。是句子的主语。第21页，本讲稿共197页3、析取、析取“”设设 p、q 是任意两个命题，复合命题

16、是任意两个命题，复合命题“p p 或或 q q”称为称为p、q的析取式，记作：的析取式，记作：p q。“”称为析取联结词。称为析取联结词。P q的真值表如下表所示：的真值表如下表所示：p qp q0 0 00 111 011 11第22页，本讲稿共197页【例【例1.1.6】(1)p：小王喜欢唱歌。：小王喜欢唱歌。q：小王喜欢跳舞。则：小王喜欢跳舞。则 pq：小王喜欢唱歌或喜欢跳舞。：小王喜欢唱歌或喜欢跳舞。(2)p：明天刮风。：明天刮风。q：明天下雨。则：明天下雨。则 pq：明天或者刮风或者下雨。：明天或者刮风或者下雨。第23页，本讲稿共197页注：自然语言中常用的联结词如：注：自然语言中常

17、用的联结词如：“或者或者或者或者”、“可可能能可能可能”等，都可以符号化为等，都可以符号化为“”“”。但日常语言中。但日常语言中的的“或或”是具有二义性的，用是具有二义性的，用“或或”联结的命题有时是具有相联结的命题有时是具有相容性的，如容性的，如【例【例1.1.6】中的二例，我们称之为可兼或。而有中的二例，我们称之为可兼或。而有时又具有排斥性，称为不可兼或（异或），如：时又具有排斥性，称为不可兼或（异或），如：（1 1）小李明天出差去上海或去广州。）小李明天出差去上海或去广州。（2 2）张三这次考试可能是全班第一也可能是全班第二。）张三这次考试可能是全班第一也可能是全班第二。“不可兼或不可兼

18、或”不能用不能用“”“”联结，这在后面联结，这在后面命题命题联结词的联结词的扩充中介绍。扩充中介绍。第24页，本讲稿共197页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页【例【例1.1.7

19、】(1)p：天下雨了。：天下雨了。q：路面湿了。则：路面湿了。则 pq：如果天下雨，则路面湿。：如果天下雨，则路面湿。(2)r：三七二十一。则：三七二十一。则 pr：如果天下雨，则三七二十一。：如果天下雨，则三七二十一。注：注：(1)(1)逻辑中，前件逻辑中，前件p p为假时，无论后件为假时，无论后件q q是真是假，是真是假，蕴涵式蕴涵式p pq q的真值均为的真值均为1 1。第26页，本讲稿共197页（2 2）正如前面所说，数理逻辑中的联结词是对日常）正如前面所说，数理逻辑中的联结词是对日常语言中的联结词的一种逻辑抽象，日常语言中联结词语言中的联结词的一种逻辑抽象，日常语言中联结词所联结的句

20、子之间是有一定内在联系的，但在数理逻所联结的句子之间是有一定内在联系的，但在数理逻辑中，联结词所联结的命题可以毫无关系。如在日常辑中，联结词所联结的命题可以毫无关系。如在日常语言中语言中“如果如果则则”所联结的句子之间表现的所联结的句子之间表现的是一种因果关系，如是一种因果关系，如【例【例1.1.7】中的（中的（1 1）。但在数理逻）。但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的，如关的，如【例【例1.1.7】中的（中的（2 2）。）。第27页，本讲稿共197页（3 3）p p q q 的逻辑关系是：的逻辑关系是：p p 是是

21、q q 的充分条件，的充分条件，q q 是是 p p 的必要条件。在日常语言中，特别是在数学语的必要条件。在日常语言中，特别是在数学语言中，言中，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页【例【例1.1.8】符号化下列命题：符号化下列命题：（1 1）

22、只要天下雨，我就回家。）只要天下雨，我就回家。（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页5 5、等价、等价“”设设 p p、q q 是任意两个命题，复合命题是任意两个命题，复合命题“p p当且

23、仅当当且仅当q q”称为称为 p p 与与 q q 的等价式，记作：的等价式，记作：p p q q。“”称为等价联结称为等价联结词。词。p p q q的真值表如下表所示：的真值表如下表所示：p qp q0 0 10 101 001 11第30页，本讲稿共197页【例【例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的

24、真值为的真值为1。在（在（2）中由于相等的两角不一定是同位角，所以真值）中由于相等的两角不一定是同位角，所以真值为为0。第31页，本讲稿共197页 以上定义了以上定义了5 种联结词，它们构成了一个联结词集合种联结词，它们构成了一个联结词集合 ，其中，其中 是一元是一元联结词，联结词，其余均为二其余均为二元元联结词。联结词。由原子命题通过命题联结词可构成各种形式的复由原子命题通过命题联结词可构成各种形式的复合命题，在对自然语言形式化时，过程如下：合命题，在对自然语言形式化时，过程如下：(1)用用p，q，r 等字母表示原子命题；等字母表示原子命题；(2)用命题联结词，将原子命题联结起来，但用命题联

25、结词，将原子命题联结起来，但5 个联结个联结词的含义由其真值表唯一确定，而不是由其自然语言词的含义由其真值表唯一确定，而不是由其自然语言的含义确定。的含义确定。第32页，本讲稿共197页在使用括号时作下列规定：在使用括号时作下列规定：(1)括号均用圆括号；括号均用圆括号；(2)5 个联结词的结合能力强弱顺序为：个联结词的结合能力强弱顺序为：，凡符合此顺序者，括号均可除去；凡符合此顺序者，括号均可除去；(3)具有相同结合能力的联结词，按其出现的先后次序，先具有相同结合能力的联结词，按其出现的先后次序，先出现先运算，凡符合此要求者，括号均可除去；出现先运算，凡符合此要求者，括号均可除去；(4)最外

26、层括号可省去。最外层括号可省去。第33页，本讲稿共197页【例【例1.1.10】将下列自然语言形式化】将下列自然语言形式化:（1）如果天不下雨并且不刮风，我就去书店。）如果天不下雨并且不刮风，我就去书店。（2）小王边走边唱。）小王边走边唱。（3）除非）除非a能被能被2整除，否则整除，否则a不能被不能被4整除。整除。（4）此时，小纲要么在学习，要么在玩游戏。）此时，小纲要么在学习，要么在玩游戏。（5）如果天不下雨，我们去打篮球，除非班上有会。）如果天不下雨，我们去打篮球，除非班上有会。第34页，本讲稿共197页解解（1）设）设 p：今天天下雨，：今天天下雨，q：今天天刮风，：今天天刮风，r：我：

27、我去书店。则原命题符号化为：去书店。则原命题符号化为：p q r (2)设设 p：小王走路，：小王走路，q：小王唱歌。则原命题符号：小王唱歌。则原命题符号化为：化为：pq (3)设设 p：a 能被能被2整除，整除，q：a 能被能被4整除。则原命题符整除。则原命题符号化为：号化为：p q 或或 q p第35页，本讲稿共197页(4)设设 p：小刚在学习，：小刚在学习，q：小刚在玩游戏。则原命：小刚在玩游戏。则原命题符号化为：题符号化为：(p q)(p q)或或 (p q)(p q)(5)设设 p：今天天下雨，：今天天下雨，q：我们去打篮球，：我们去打篮球，r：今：今天班上有会。则原命题符号化为：

28、天班上有会。则原命题符号化为：r (p q)第36页，本讲稿共197页1.2 命题公式及分类命题公式及分类 为了用数学的方法研究命题，就必须像数学为了用数学的方法研究命题，就必须像数学处理问题那样将命题公式化，并讨论对于这些公处理问题那样将命题公式化，并讨论对于这些公式的演算（推理）规则，以期由给定的公式推导式的演算（推理）规则，以期由给定的公式推导出新的命题公式来。出新的命题公式来。第37页，本讲稿共197页一、命题公式一、命题公式 命题常元与命题变元：命题常元与命题变元：前面我们用前面我们用p、q、r等符号表示确定的简单命等符号表示确定的简单命题，通常称它们为命题常元，由于一个确定的命题题

29、，通常称它们为命题常元，由于一个确定的命题是一个常值命题，它们的真值只可能是是一个常值命题，它们的真值只可能是1或或0，所所以一般称以一般称1和和0为为命题常元命题常元。第38页，本讲稿共197页 为了更广泛地应用命题演算，我们用为了更广泛地应用命题演算，我们用p、q、r等符号表示一个任意的没有赋予具体内容的简单命等符号表示一个任意的没有赋予具体内容的简单命题，就如同数学公式中的变量题，就如同数学公式中的变量 x 一样，我们称其为一样，我们称其为命题变元命题变元。即命题变元。即命题变元 是一个不确指的（抽象的）命是一个不确指的（抽象的）命题，以真、假为其变域，以题，以真、假为其变域，以p、q、

30、r等表之。等表之。第39页，本讲稿共197页 命题公式命题公式 命题公式命题公式 ：由命题变元（常元）符、联结词：由命题变元（常元）符、联结词和圆括号按一定逻辑关系联结起来的字符串。和圆括号按一定逻辑关系联结起来的字符串。所谓按一定的逻辑关系，即字符串的构成要所谓按一定的逻辑关系，即字符串的构成要求合理。合理的命题公式叫做合式公式，也称真求合理。合理的命题公式叫做合式公式，也称真值函数。值函数。第40页，本讲稿共197页定义定义1.2.1：合式公式（或简称公式）的递归定义：合式公式（或简称公式）的递归定义：单个的命题变元（或常元）是合式公式。单个的命题变元（或常元）是合式公式。；如果如果A和和

31、B是合式公式，则是合式公式，则A、AB、AB、AB、AB是是合式合式公式；公式；只有有限次应用条款只有有限次应用条款、生成的公式才是生成的公式才是合式合式 公式。公式。例：说明例：说明是合式公式。是合式公式。又如又如第41页，本讲稿共197页定义定义1.2.2(1)若若A是单个命题（变元或常元），则称为是单个命题（变元或常元），则称为0层公式。层公式。(2)称称A为为n+1（n0）层公式是指）层公式是指A符合下列诸情况之一：符合下列诸情况之一：A=B，B是是n层公式；层公式；A=BC，其中，其中B为为i层公式、层公式、C为为j层公式，层公式，n=max（i，j）；）；A=BC，其中，其中B、C

32、的层次同的层次同；A=BC，其中，其中B、C的层次同的层次同；A=B C，其中，其中B、C的层次同的层次同。第42页，本讲稿共197页【例【例1.2.1】：公式：公式：A=（p q）r。解释解释1：假设：假设 p：现在是白天，：现在是白天，q：现在是晴天，：现在是晴天，r：我：我们能看见太阳。则们能看见太阳。则 A：如果现在是白天且是晴天，则我们能看见太阳。：如果现在是白天且是晴天，则我们能看见太阳。其真值为其真值为1。解释解释2：假设：假设 p、q如上，如上，r：我们能看见星星。则：我们能看见星星。则 A：如果现在是白天且是晴天，则我们能看见星星。其真：如果现在是白天且是晴天，则我们能看见星

33、星。其真值为值为0。第43页，本讲稿共197页由此可见，不同的解释可使公式有不同的真值。由此可见，不同的解释可使公式有不同的真值。事实上，对于命题变元无论做什么样的解释，它都只事实上，对于命题变元无论做什么样的解释，它都只有两种结果：或者是有两种结果：或者是“真真”，或者是，或者是“假假”。从而由。从而由变元和联结词组成的公式所表示的复合命题，也是变元和联结词组成的公式所表示的复合命题，也是或为或为“真真”，或为，或为“假假”。因此命题公式可看成是一个。因此命题公式可看成是一个以真、假为定义域，以真、假为值域的函数，故也称以真、假为定义域，以真、假为值域的函数，故也称真值真值函数函数。不同的解

34、释可看作是对命题变元不同的。不同的解释可看作是对命题变元不同的“赋值赋值”。第44页，本讲稿共197页如【例如【例1.2.1】中】中解释解释 1 实际上是对变元实际上是对变元 p、q、r 赋值赋值111，得，得A的真值为的真值为1；解释解释 2 实际上是对变元实际上是对变元 p、q、r 赋值赋值110，得，得A的真值为的真值为0；公式公式A的真值是在对的真值是在对 p、q、r 的某种赋值下所得的真值。的某种赋值下所得的真值。第45页，本讲稿共197页 真值表真值表1、赋值（或真值指派）：、赋值（或真值指派）：在合式公式中，每一个变元的在合式公式中，每一个变元的一组确定的真值称为公式的一个赋值。

35、一组确定的真值称为公式的一个赋值。每一个赋值对应公式的一个确定的值每一个赋值对应公式的一个确定的值 有有n个变元的公式有个变元的公式有2n种不同的赋值。种不同的赋值。有有n个命题变元个命题变元 的公式的公式 称使称使A的真值为真的赋值为成真赋值，使的真值为真的赋值为成真赋值，使A的真值为假的真值为假的赋值为成假赋值。的赋值为成假赋值。第46页，本讲稿共197页如【例如【例1.2.1】中，】中，111是是A=（p q）r的成的成真赋值，真赋值，110是是A的成假赋值。根据前面对联结词的的成假赋值。根据前面对联结词的讨论知：讨论知：000、001、010、011、100、101也都是也都是A的成真

36、赋值。的成真赋值。第47页，本讲稿共197页 将公式将公式A在所有赋值情况下的取值列成表，称为在所有赋值情况下的取值列成表，称为A的真值表。的真值表。构造真值表的步骤如下：构造真值表的步骤如下：（1）找出命题公式中所含的所有命题变元并按下标或）找出命题公式中所含的所有命题变元并按下标或字典顺序给出；字典顺序给出；（2）按从低到高的顺序写出各层次；）按从低到高的顺序写出各层次；（3）顺序列出所有的赋值（）顺序列出所有的赋值（2n个）；对应每个赋值，个）；对应每个赋值，计算命题公式各层次的真值，直到最后计算出命题公式计算命题公式各层次的真值，直到最后计算出命题公式的真值。的真值。2、真值表：、真值

37、表：第48页，本讲稿共197页【例【例1.2.2】：求下列命题公式的真值表：求下列命题公式的真值表：(1)(2)(3)解解:公式公式(1)、(2)、(3)的真值表分别如表的真值表分别如表1、表、表2、表、表3所示。所示。第49页，本讲稿共197页pq p p q(p q)q00101011111000111001表表 1第50页，本讲稿共197页表表 2pqp q(p q)qp q(p q)(p q)(p q)00101010011000101001110011100010第51页，本讲稿共197页表表 3 pqr p q r(p q)r0001110011000101110111001000

38、10101000110111111100第52页，本讲稿共197页 由上可知，有的公式在任何赋值情况下真值恒为由上可知，有的公式在任何赋值情况下真值恒为1，如（，如（1）；有的公式在任何赋值情况下真值恒为）；有的公式在任何赋值情况下真值恒为0，如（，如（2）；有的公式某些赋值使其真值为）；有的公式某些赋值使其真值为1，而另一，而另一些赋值使其真值为些赋值使其真值为0，如（，如（3）；因此可将公式分为三）；因此可将公式分为三类。类。第53页，本讲稿共197页（一）、（一）、定义：定义：一个公式若对其所有赋值均取值为真，则称为一个公式若对其所有赋值均取值为真，则称为重言式重言式（或永真式）（或永真

39、式）。一个公式若对其所有赋值均取值为假，则称为一个公式若对其所有赋值均取值为假，则称为矛盾矛盾式式（或永假式）。（或永假式）。一个公式若至少存在一个赋值使其取值为真，则称为一个公式若至少存在一个赋值使其取值为真，则称为可满足式可满足式。二、公式的类型二、公式的类型 第54页，本讲稿共197页重言式的特点重言式的特点 重言式的否定是矛盾式；矛盾式的否定是重言式。重言式的否定是矛盾式；矛盾式的否定是重言式。重言式的合取、析取、蕴含、等价都是重言式。重言式的合取、析取、蕴含、等价都是重言式。第55页，本讲稿共197页 两种特殊的重言式两种特殊的重言式1、等价重言式（或恒等式）等价重言式（或恒等式）定

40、义：定义：设设A、B是公式，若是公式，若AB是重言式，则称是重言式，则称AB是是等价重言式，记为等价重言式，记为AB，也称逻辑恒等式。，也称逻辑恒等式。注意：注意：“”与与“”是两个完全不同的符号。是两个完全不同的符号。“”是联结词，是联结词，A AB B是一个公式。是一个公式。“”不是联结不是联结词，而是两个公式之间的关系符，词，而是两个公式之间的关系符，AB并不是一个并不是一个公式，而只是表示公式，而只是表示A A与与B B是两个真值相同的公式。是两个真值相同的公式。第56页，本讲稿共197页 证明证明AB的方法的方法 用真值表证明；用真值表证明；用等值演算。用等值演算。定理：定理：AB为

41、重言式，当且仅当为重言式，当且仅当A、B具有相同的真具有相同的真值表。值表。第57页，本讲稿共197页例例1：用真值表判断下列各组公式是否等价用真值表判断下列各组公式是否等价 pq pq p(q p)p q001100011011100100110100第58页，本讲稿共197页 pqrp q p q(p q)rr(p q)rr00010010011011010100101110111000011101001111011001111111第59页，本讲稿共197页(3)常用的逻辑恒等式（或基本等价重言式）常用的逻辑恒等式（或基本等价重言式）利用真值表我们可以证明许多恒等式利用真值表我们可以证明

42、许多恒等式第60页，本讲稿共197页第61页，本讲稿共197页第62页，本讲稿共197页第63页，本讲稿共197页2、蕴含重言式（或永真蕴含式）、蕴含重言式（或永真蕴含式）定义：定义：设设A、B是公式，若是公式，若AB是重言式，则称是重言式，则称AB是蕴含重言式，记为是蕴含重言式，记为AB。同样：同样：“”与与“”是两个完全不同的符号。是两个完全不同的符号。“”是联结词，是联结词，A A B B是一个公式。是一个公式。“”不是联结不是联结词，而是两个公式之间的关系符，词，而是两个公式之间的关系符，AB并不是一个公式，并不是一个公式，而只是表示而只是表示 A AB B 是重言式是重言式。第64页

43、，本讲稿共197页例例2：试证：试证 pqp qp (p q)p (p q)q00101011011000111111 证明证明AB的方法的方法 用真值表证明用真值表证明第65页，本讲稿共197页 用分析法证明用分析法证明）假设前件是真，若能推出后件是真，则）假设前件是真，若能推出后件是真，则AB。）假设后件是假，若能推出前件是假，则）假设后件是假，若能推出前件是假，则AB。例例3：用分析法证明：用分析法证明：用等值演算。用等值演算。第66页，本讲稿共197页 基本的蕴含重言式。基本的蕴含重言式。第67页，本讲稿共197页3、等价重言式与蕴含重言式的性质、等价重言式与蕴含重言式的性质 自反性：

44、对任意自反性：对任意A有：有：AA、AA 对称性：若对称性：若AB，则，则BA 反对称性：若反对称性：若AB且且BA，则，则AB 传递性：若传递性：若AB，BC，则，则AC 若若AB，BC，则，则AC(5)若若AB，AC，则，则ABC第68页，本讲稿共197页1.3 等值演算等值演算 一、一、定义：定义：由已知的等值式推演出另一些等值式的过由已知的等值式推演出另一些等值式的过程称为等值演算。程称为等值演算。二、等值演算中使用的规则：二、等值演算中使用的规则：1、代入规则：、代入规则：在重言式中，将某一命题变元全用同一命题公式在重言式中，将某一命题变元全用同一命题公式代入后，得到的公式仍是重言式

45、代入后，得到的公式仍是重言式。第69页，本讲稿共197页2、替换规则：、替换规则：子公式：子公式：设设 是命题公式且是命题公式是命题公式且是命题公式A的一部分，则称的一部分，则称 是是A的子公式。的子公式。替换规则：替换规则：设设 是含有子公式是含有子公式A的命题公式，的命题公式，BA，则可用则可用B替换替换 中的中的A，得，得，保证，保证 第70页，本讲稿共197页例例1：用等值演算法验证下列重言式用等值演算法验证下列重言式(1)(1)证明：证明：第71页，本讲稿共197页(2)(2)证明：证明：第72页，本讲稿共197页(3)(3)证明：证明：第73页，本讲稿共197页(4)(4)证明：证

46、明：第74页，本讲稿共197页(5)(5)证明：证明：第75页，本讲稿共197页(6)(6)证明：证明：第76页，本讲稿共197页例例2：用等值演算法判断公式的类型，并求出公式用等值演算法判断公式的类型，并求出公式的成真赋值和成假赋值。的成真赋值和成假赋值。(1)(1)解：解：第77页，本讲稿共197页即公式是矛盾式，没有成真赋值，所有赋值都是即公式是矛盾式，没有成真赋值，所有赋值都是成假赋值，即成假赋值为成假赋值，即成假赋值为000，001，010，011，100，101，110，111。第78页，本讲稿共197页(2)(2)即公式是重言式，没有成假赋值，所有赋值都是成真赋即公式是重言式，没

47、有成假赋值，所有赋值都是成真赋值，即成真赋值为值，即成真赋值为00，01，10，11。第79页，本讲稿共197页(3)(3)即公式是可满足式，成假赋值为即公式是可满足式，成假赋值为00，01，成真赋值为，成真赋值为10，11。第80页，本讲稿共197页 等值演算在计算机硬件设计，开关理论和等值演算在计算机硬件设计，开关理论和电子元器件中都占据重要地位。电子元器件中都占据重要地位。第81页，本讲稿共197页1.4 联结词全功能集联结词全功能集 一、命题联结词的扩充一、命题联结词的扩充 1、异或、异或(不可兼或不可兼或)：命题：命题p与与q的异或的异或 记为记为2、与非：命题、与非：命题p与与q的

48、与非记为的与非记为3、或非：命题、或非：命题P与与Q的或非记为的或非记为4、蕴含否定：命题、蕴含否定：命题P与与Q的蕴含否定记为的蕴含否定记为第82页，本讲稿共197页pq000110011100101101110000第83页，本讲稿共197页二、九个联结词穷尽了一切命题间的联结词二、九个联结词穷尽了一切命题间的联结词 命题联结词定义表命题联结词定义表 pq命题联结词命题联结词00011011其中其中 分别取分别取1，0，故可得，故可得16张表，张表，即命题联结词最多可有即命题联结词最多可有16个。个。第84页，本讲稿共197页命题联结词命题联结词16个真值表个真值表pq联结词联结词1联结词

49、联结词2联结词联结词3联结词联结词4联结词联结词5联结词联结词61110110010101001011001100010001110pq第85页，本讲稿共197页pq联结词联结词7联结词联结词8联结词联结词9联结词联结词10联结词联结词111110101100110001011010001011第86页，本讲稿共197页pq联结词联结词12联结词联结词13联结词联结词14联结词联结词15联结词联结词161101010101011001001010001010第87页，本讲稿共197页三、联结词全功能集三、联结词全功能集 定义定义1：设设D为联结词集合，若为联结词集合，若D中一个联结词可以由中一

50、个联结词可以由D中的其它联结词表示，则此联结词称为冗余联结词，中的其它联结词表示，则此联结词称为冗余联结词，否则称为独立联结词。否则称为独立联结词。定义定义2：设设D为联结词集合，若任何命题公式总可以用含有为联结词集合，若任何命题公式总可以用含有D中的联结词的等值式表示，则称中的联结词的等值式表示，则称D为全功能集合。为全功能集合。定义定义3：不含冗余联结词的全功能集，称为极小全功不含冗余联结词的全功能集，称为极小全功能集。能集。第88页，本讲稿共197页定理定理1：，是全功能集。是全功能集。定理定理2：，都是都是极小极小全功能集。全功能集。证明：由范式可知，仅有三个联结词证明：由范式可知，仅