第1章 命题逻辑优秀PPT.ppt

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