第1章 命题逻辑精选PPT.ppt

《第1章 命题逻辑精选PPT.ppt》由会员分享，可在线阅读，更多相关《第1章 命题逻辑精选PPT.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页，此课件共

4、197页哦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页，此

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

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

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

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

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

12、，复合命题p称为称为p的否定式。的否定式。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)

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

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

16、”设设 p、q 是任意两个命题，复合命题是任意两个命题，复合命题“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 1

19、1第25页，此课件共197页哦【例【例1.1.7】(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

21、 q q 的逻辑关系是：的逻辑关系是：p p 是是 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页哦【例【例

22、1.1.8】符号化下列命题：符号化下列命题：（1 1）只要天下雨，我就回家。）只要天下雨，我就回家。（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 是任

23、意两个命题，复合命题是任意两个命题，复合命题“p p当且仅当当且仅当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并无内在关系，但

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

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

26、均可除去；出现先运算，凡符合此要求者，括号均可除去；(4)最外层括号可省去。最外层括号可省去。第33页，此课件共197页哦【例【例1.1.10】将下列自然语言形式化】将下列自然语言形式化:（1）如果天不下雨并且不刮风，我就去书店。）如果天不下雨并且不刮风，我就去书店。（2）小王边走边唱。）小王边走边唱。（3）除非）除非a能被能被2整除，否则整除，否则a不能被不能被4整除。整除。（4）此时，小纲要么在学习，要么在玩游戏。）此时，小纲要么在学习，要么在玩游戏。（5）如果天不下雨，我们去打篮球，除非班上有）如果天不下雨，我们去打篮球，除非班上有会。会。第34页，此课件共197页哦解解（1）设）设 p

27、：今天天下雨，：今天天下雨，q：今天天刮风，：今天天刮风，r：我：我去书店。则原命题符号化为：去书店。则原命题符号化为：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：我

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

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

30、个不确指的（抽象的）命题，以真、假为其变域，以以真、假为其变域，以p、q、r等表之。等表之。第39页，此课件共197页哦 命题公式命题公式 命题公式命题公式 ：由命题变元（常元）符、联结词和：由命题变元（常元）符、联结词和圆括号按一定逻辑关系联结起来的字符串。圆括号按一定逻辑关系联结起来的字符串。所谓按一定的逻辑关系，即字符串的构成要求合理。所谓按一定的逻辑关系，即字符串的构成要求合理。合理的命题公式叫做合式公式，也称真值函数。合理的命题公式叫做合式公式，也称真值函数。第40页，此课件共197页哦定义定义1.2.1：合式公式（或简称公式）的递归定义：合式公式（或简称公式）的递归定义：单个的命题

31、变元（或常元）是合式公式。单个的命题变元（或常元）是合式公式。；如果如果A和和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层公式、层公

32、式、C为为j层公式，层公式，n=max（i，j）；）；A=BC，其中，其中B、C的层次同的层次同；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的成假赋值。根据前面对联结词的的成假赋值。根据前面对

36、联结词的讨论知：讨论知：000、001、010、011、100、101也都是也都是A的成真赋值。的成真赋值。第47页，此课件共197页哦 将公式将公式A在所有赋值情况下的取值列成表，称为在所有赋值情况下的取值列成表，称为A的的真值表。真值表。构造真值表的步骤如下：构造真值表的步骤如下：（1）找出命题公式中所含的所有命题变元并按）找出命题公式中所含的所有命题变元并按下标或字典顺序给出；下标或字典顺序给出；（2）按从低到高的顺序写出各层次；）按从低到高的顺序写出各层次；（3）顺序列出所有的赋值（）顺序列出所有的赋值（2n个）；对应每个赋值，个）；对应每个赋值，计算命题公式各层次的真值，直到最后计算

37、出命题公式的计算命题公式各层次的真值，直到最后计算出命题公式的真值。真值。2、真值表：、真值表：第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页

38、哦表表 3 pqr p q r(p q)r000111001100010111011100100010101000110111111100第52页，此课件共197页哦 由上可知，有的公式在任何赋值情况下真值恒为由上可知，有的公式在任何赋值情况下真值恒为1，如（如（1）；有的公式在任何赋值情况下真值恒为）；有的公式在任何赋值情况下真值恒为0，如，如（2）；有的公式某些赋值使其真值为）；有的公式某些赋值使其真值为1，而另一些赋值使，而另一些赋值使其真值为其真值为0，如（，如（3）；因此可将公式分为三类。）；因此可将公式分为三类。第53页，此课件共197页哦（一）、（一）、定义：定义：一个公式若对其

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

40、此课件共197页哦 两种特殊的重言式两种特殊的重言式1、等价重言式（或恒等式）等价重言式（或恒等式）定义：定义：设设A、B是公式，若是公式，若AB是重言式，则称是重言式，则称AB是是等价重言式，记为等价重言式，记为AB，也称逻辑恒等式。，也称逻辑恒等式。注意：注意：“”与与“”是两个完全不同的符号。是两个完全不同的符号。“”是联结词，是联结词，A AB B是一个公式。是一个公式。“”不是联结不是联结词，而是两个公式之间的关系符，词，而是两个公式之间的关系符，AB并不是一个公并不是一个公式，而只是表示式，而只是表示A A与与B B是两个真值相同的公式。是两个真值相同的公式。第56页，此课件共19

41、7页哦 证明证明AB的方法的方法 用真值表证明；用真值表证明；用等值演算。用等值演算。定理：定理：AB为重言式，当且仅当为重言式，当且仅当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是一个公式。是一个公式。“”不是联结不是联结词，而是两个公式之间的关系符，词，而是两

43、个公式之间的关系符，AB并不是一个公并不是一个公式，而只是表示式，而只是表示 A AB B 是重言式是重言式。第64页，此课件共197页哦例例2：试证：试证 pqp qp (p q)p (p q)q00101011011000111111 证明证明AB的方法的方法 用真值表证明用真值表证明第65页，此课件共197页哦 用分析法证明用分析法证明）假设前件是真，若能推出后件是真，则）假设前件是真，若能推出后件是真，则AB。）假设后件是假，若能推出前件是假，则）假设后件是假，若能推出前件是假，则AB。例例3：用分析法证明：用分析法证明：用等值演算。用等值演算。第66页，此课件共197页哦 基本的蕴含

44、重言式。基本的蕴含重言式。第67页，此课件共197页哦3、等价重言式与蕴含重言式的性质、等价重言式与蕴含重言式的性质 自反性：对任意自反性：对任意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页，此课

46、件共197页哦(2)(2)证明：证明：第72页，此课件共197页哦(3)(3)证明：证明：第73页，此课件共197页哦(4)(4)证明：证明：第74页，此课件共197页哦(5)(5)证明：证明：第75页，此课件共197页哦(6)(6)证明：证明：第76页，此课件共197页哦例例2：用等值演算法判断公式的类型，并求出公式的成真用等值演算法判断公式的类型，并求出公式的成真赋值和成假赋值。赋值和成假赋值。(1)(1)解：解：第77页，此课件共197页哦即公式是矛盾式，没有成真赋值，所有赋值都是成假即公式是矛盾式，没有成真赋值，所有赋值都是成假赋值，即成假赋值为赋值，即成假赋值为000，001，010

47、，011，100，101，110，111。第78页，此课件共197页哦(2)(2)即公式是重言式，没有成假赋值，所有赋值都是成真赋值，即公式是重言式，没有成假赋值，所有赋值都是成真赋值，即成真赋值为即成真赋值为00，01，10，11。第79页，此课件共197页哦(3)(3)即公式是可满足式，成假赋值为即公式是可满足式，成假赋值为00，01，成真赋值为，成真赋值为10，11。第80页，此课件共197页哦 等值演算在计算机硬件设计，开关理论和电等值演算在计算机硬件设计，开关理论和电子元器件中都占据重要地位。子元器件中都占据重要地位。第81页，此课件共197页哦1.4 联结词全功能集联结词全功能集

48、一、命题联结词的扩充一、命题联结词的扩充 1、异或、异或(不可兼或不可兼或)：命题：命题p与与q的异或的异或 记为记为2、与非：命题、与非：命题p与与q的与非记为的与非记为3、或非：命题、或非：命题P与与Q的或非记为的或非记为4、蕴含否定：命题、蕴含否定：命题P与与Q的蕴含否定记为的蕴含否定记为第82页，此课件共197页哦pq000110011100101101110000第83页，此课件共197页哦二、九个联结词穷尽了一切命题间的联结词二、九个联结词穷尽了一切命题间的联结词 命题联结词定义表命题联结词定义表 pq命题联结词命题联结词00011011其中其中 分别取分别取1，0，故可得，故可得

49、16张表，张表，即命题联结词最多可有即命题联结词最多可有16个。个。第84页，此课件共197页哦命题联结词命题联结词16个真值表个真值表 pq联结词联结词1联结词联结词2联结词联结词3联结词联结词4联结词联结词5联结词联结词6111011001010100101100110001000111 0pq第85页，此课件共197页哦pq联结词联结词7联结词联结词8联结词联结词9联结词联结词10联结词联结词111110101100110001011010001011第86页，此课件共197页哦pq联结词联结词12联结词联结词13联结词联结词14联结词联结词15联结词联结词161101010101011

50、001001010001010第87页，此课件共197页哦三、联结词全功能集三、联结词全功能集 定义定义1：设设D为联结词集合，若为联结词集合，若D中一个联结词可以由中一个联结词可以由D中的其它联结词表示，则此联结词称为冗余联结词，否中的其它联结词表示，则此联结词称为冗余联结词，否则称为独立联结词。则称为独立联结词。定义定义2：设设D为联结词集合，若任何命题公式总可以用为联结词集合，若任何命题公式总可以用含有含有D中的联结词的等值式表示，则称中的联结词的等值式表示，则称D为全功能集为全功能集合。合。定义定义3：不含冗余联结词的全功能集，称为极小全不含冗余联结词的全功能集，称为极小全功能集。功能