逻辑代数基础3

1、逻辑代数基础u课前预习课前预习u将手机调到静音将手机调到静音u认真做笔记认真做笔记u及时完成作业及时完成作业上课要求上课要求本节内容2022-6-19v命题与连接词（重点）命题与连接词（重点）v命题公式（重点）命题公式（重点）v命题代数（难点）命题代数（难点）v逻辑代数的等价律逻辑代数的等价律v逻辑代数的应用逻辑代数的应用v了解命题，原子命题，复合命题的概念了解命题，原子命题，复合命题的概念v掌握与、或、非三种复合命题（重点及难点）掌握与、或、非三种复合命题（重点及难点）v掌握逻辑代数的等价律掌握逻辑代数的等价律v掌握化简逻辑函数的方法掌握化简逻辑函数的方法 学习目标玉龙雪山下的审判玉龙雪山下

2、的审判在玉龙雪山脚下东巴谷的一条小路上立有一块木牌，请过路行人对一个案子在玉龙雪山脚下东巴谷的一条小路上立有一块木牌，请过路行人对一个案子进行审判。说的是有三个人，甲、乙、丙在玉龙山上射杀了一只老鹰，这三进行审判。说的是有三个人，甲、乙、丙在玉龙山上射杀了一只老鹰，这三个人的行为因违反个人的行为因违反野生动物保护法野生动物保护法而被警察拘捕，但是这三个人都否认而被警察拘捕，但是这三个人都否认老鹰是自己射杀的。经过盘查和询问，警察得出如下三个结论：老鹰是自己射杀的。经过盘查和询问，警察得出如下三个结论：如果甲是无罪的，则乙和丙都有罪；如果甲是无罪的，则乙和丙都有罪；乙和丙中必有一人有罪；乙和丙中

3、必有一人有罪；要么甲无罪，要么乙有罪（但两者不能同时成立）。要么甲无罪，要么乙有罪（但两者不能同时成立）。现在警方请求你协助判断甲、乙、丙三人谁有罪，谁没有罪，并在你认为有现在警方请求你协助判断甲、乙、丙三人谁有罪，谁没有罪，并在你认为有罪的人前面的筐里投入一块石头。笔者查看三个筐发现，乙的筐里石头最多罪的人前面的筐里投入一块石头。笔者查看三个筐发现，乙的筐里石头最多，甲和丙的筐里则差不多。你认为游客们的判断是否正确呢？，甲和丙的筐里则差不多。你认为游客们的判断是否正确呢？ 逻辑学是研究思维形式及思维规律尤其是推逻辑学是研究思维形式及思维规律尤其是推理的学科理的学科, 早在两千多年前就受到人们

4、的重视。早在两千多年前就受到人们的重视。逻辑学古希腊（逻辑）古希腊（逻辑）战国（名学）战国（名学）古印度（因明）古印度（因明） 德国数学家、哲学家莱布尼茨德国数学家、哲学家莱布尼茨(16471716)首先提出用数学方法研究逻辑首先提出用数学方法研究逻辑,就是建立一套表就是建立一套表意意符号体系符号体系,在符号之间进行在符号之间进行形式推理形式推理. 莱布尼茨是数理逻辑的创始人，也正因为这莱布尼茨是数理逻辑的创始人，也正因为这样样, 数理逻辑数理逻辑又称为又称为符号逻辑符号逻辑。 数理逻辑数理逻辑是一门新兴的是一门新兴的边缘性边缘性学科，分为五个部分：即学科，分为五个部分：即逻辑演算、证明论、公

5、理集合论、递归论和模型论。从创始逻辑演算、证明论、公理集合论、递归论和模型论。从创始至今约有至今约有300年的历史。年的历史。数理逻辑概述 数理逻辑数理逻辑是用数学的方法来研究人类思维活动的是用数学的方法来研究人类思维活动的一门数学学科，其显著特征是：一门数学学科，其显著特征是： 符号化符号化、形式化形式化 即即把逻辑所涉及的把逻辑所涉及的“概念、判断、推理概念、判断、推理”用用符号符号来来表示，用公理体系来刻划表示，用公理体系来刻划, 并基于符号串形式的演算来描并基于符号串形式的演算来描述推理过程的一般规律。述推理过程的一般规律。数理逻辑概述 回顾计算机科学的发展，我们可以清晰地发现数理回顾

6、计算机科学的发展，我们可以清晰地发现数理逻辑一直是计算机科学的逻辑一直是计算机科学的理论基础和发展动力理论基础和发展动力。逻辑的数学分析逻辑的数学分析思维规律的研究思维规律的研究关系逻辑关系逻辑德摩根定律德摩根定律数理逻辑的起源与计算机科学概念演算概念演算 一种按算术语言构成的思维符号一种按算术语言构成的思维符号语言语言德国德国G.W. Leibniz(1626-1716)把数学引入形式逻辑把数学引入形式逻辑，明，明确提出用数学方法研究推理。确提出用数学方法研究推理。英国英国G. Boole(1815-1864)等等创立了逻辑代数创立了逻辑代数，1847年年Boole实现了命题演算。实现了命题

7、演算。德国德国G.Frege(1848-1925)在在1879年建立了第一个年建立了第一个谓词演谓词演算算系统。系统。英国英国Alan M. Turing (1912-1954)在在1936年提出一种抽年提出一种抽象计算模型（数学逻辑机），引入图灵机象计算模型（数学逻辑机），引入图灵机一种理想一种理想的计算机。的计算机。数理逻辑发展史中的代表人物数理逻辑的学习 Edsger. W. Dijkstra 1972年年Turing奖获得者奖获得者 (1930-2002) “我现在年纪大了，搞了这么多年的软我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。件，错误不知犯了多少，现在觉悟

8、了。我想，假如我早年在数理逻辑上好好下我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我不知道。要是我能年轻二十岁的话，我就去学逻辑。我就去学逻辑。”单源点最单源点最短路径算短路径算法法曹雪芹曹雪芹是是红楼梦红楼梦的作者。的作者。曹雪芹曹雪芹是是小说家。小说家。小说家小说家是是文学家。文学家。 数理逻辑是数理逻辑是以数学的方法以数学的方法研究推理的形式结构研究推理的形式结构和规律的数学学科。和规律的数学学科。 所谓数学方法，是指建立所谓数学

9、方法，是指建立一套符号一套符号，其作用是，其作用是为了避免用自然语言讨论问题时所带来的歧义性。为了避免用自然语言讨论问题时所带来的歧义性。如，下面三条语句均用如，下面三条语句均用“是是”作谓语动词：作谓语动词：学习数理逻辑三个语句中的三个三个语句中的三个“是是”含义各不同。含义各不同。n曹雪芹是曹雪芹是红楼梦红楼梦的作者。此句中的的作者。此句中的“是是”表表示示“”，其主语和谓语是对等的；，其主语和谓语是对等的；n曹雪芹是小说家。此句中的曹雪芹是小说家。此句中的“是是”表示表示“”，小说家是集合，曹雪芹只是其中的一分子；小说家是集合，曹雪芹只是其中的一分子；n小说家是文学家。此句中的小说家是文

10、学家。此句中的“是是”表示表示“ ”，文，文学家是包含着小说家的一个更大的集合。学家是包含着小说家的一个更大的集合。显然，符号准确地表达了语句的含义。显然，符号准确地表达了语句的含义。命题的定义命题命题 ：能判断出能判断出真假真假的语句的语句.（1）你妈喊你回家吃饭 . （2）盗墓笔记里面有大腕儿 .（3）北京是中国的首都.（4）火星上有生物.（5） x 3。（6）立正！（7）我说的都是假话。（8）你喜欢网络游戏吗? 特征特征 陈述句陈述句 真假性真假性: 可决定真或假，且真假不可兼可决定真或假，且真假不可兼 构成命题需要具备以下几个条件：构成命题需要具备以下几个条件：必须是一个必须是一个完整

11、完整的句子，包括用数学式子表的句子，包括用数学式子表达；达；句子必须具有真假意义（即有对错之分）；句子必须具有真假意义（即有对错之分）；句子能判断出是句子能判断出是真还是假真还是假。例例 下列句子都是命题吗？下列句子都是命题吗？1960年杭州下雪了。太阳系外有宇宙人。好大的雪啊！812。1+101=110。上海世博会开幕时天晴。大于2的偶数可表示成两个素数之和。AB。请勿吸烟。 姚明很帅。 具体命题的真假问题 在数理逻辑的学习中，不能去纠缠各种在数理逻辑的学习中，不能去纠缠各种具体命题的真假问题，而是将命题当成数学具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，概

12、念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句。把命题定义成非真必假的陈述句。公説公有理婆説婆有理 原子命题（简单命题）原子命题（简单命题） 若一个命题不包含有更小的命题，即若一个命题不包含有更小的命题，即不可再分不可再分割割的命题。小写英文字母的命题。小写英文字母p, q, r, s,或带下标或带下标p1, p2, p3, 等来表示原子命题。等来表示原子命题。复合命题复合命题 若一个命题若一个命题可以分解（分割）可以分解（分割）若干个原子命题。若干个原子命题。精确的定义为：精确的定义为：设设A1,A2,An是原子命题，用是原子命题，用逻辑联结词逻辑联结词将这将这n个命题联

13、结起来，构成的一个新命题，则称这个个命题联结起来，构成的一个新命题，则称这个新命题是复合命题。新命题是复合命题。原子命题与复合命题命题真值命题真值 真真: 用用T(或或1)表示表示假假: 用用F(或或0)表示表示命题的真值命题的真值就是命题的逻辑取值命题的真值就是命题的逻辑取值. . 把把1和和0称为逻辑常量称为逻辑常量. 在逻辑表达式中出现的在逻辑表达式中出现的p, q, r或或p1, p2 , p3 等称为等称为命题变元命题变元或或逻辑变量逻辑变量. 命题变元可以代表任意命题命题变元可以代表任意命题, 从取值的角度看从取值的角度看, 命题变元既命题变元既可以取可以取1又可以取又可以取0.

14、常量与逻辑变量字母字母p表示表示命题命题具体的、特定的命题，有确定的真值具体的、特定的命题，有确定的真值 命题变元命题变元任意命题，没有确定的真值任意命题，没有确定的真值 逻辑联结词 命题逻辑中出现更多的是命题逻辑中出现更多的是复合命题复合命题. 一方面，复合命题是由原子命题构成的，一方面，复合命题是由原子命题构成的，它需要联结词；另一方面，给定了原子命题，它需要联结词；另一方面，给定了原子命题，使用逻辑联结词，可以将它们构成一个复合命使用逻辑联结词，可以将它们构成一个复合命题题. 逻辑联结词就是逻辑运算逻辑联结词就是逻辑运算.五种常用的联结词：五种常用的联结词： 否定联结词否定联结词 （非）

15、（非） 合取联结词合取联结词 （与）（与） 析取联结词析取联结词 （或）（或） 蕴含联结词蕴含联结词 等价联结词等价联结词 否定联结词否定联结词 （非）（非）当某一条件具备了，当某一条件具备了，事情不会发生；而此条件事情不会发生；而此条件不具备时，事情反而发生。不具备时，事情反而发生。这种逻辑关系称为非逻辑这种逻辑关系称为非逻辑关系，简称关系，简称非逻辑非逻辑。设设P是一个命题，命题是一个命题，命题 “P是不对的是不对的”称为称为P的否定，记以的否定，记以 P，读作非，读作非P。 P是真的是真的当且仅当当且仅当P是假的。是假的。p p1 10 00 01 1否定联结词是一元逻辑运算；否定联结词

16、是一元逻辑运算； 若若P是原子命题，则是原子命题，则 P是复合命题。是复合命题。 日常语句中有：日常语句中有： 非非 不不 并非并非 否定联结词的例子否定联结词的例子 P青岛青岛是是中国的城市。中国的城市。P：青岛：青岛不是不是中国的城市。中国的城市。 P是真命题，是真命题，P是假命题。是假命题。 P：雪：雪是是黑色的。黑色的。P：雪：雪不是不是黑色的。黑色的。 命题命题P是假的，命题是假的，命题P是真的。是真的。命题的真假，与其否定的真假，正好相反，这符命题的真假，与其否定的真假，正好相反，这符合我们的直观。合我们的直观。合取联结词合取联结词 只有决定某一事件的只有决定某一事件的所有条件全部

17、具备所有条件全部具备，这一事，这一事件才能发生。件才能发生。开关开关A 开关开关B灯灯F断 断断 合合 断合 合灭灭灭亮ABF1 01 10 10 00010设设P，Q是两个命题，命题是两个命题，命题 “P并且并且Q”称为称为P，Q的合取，记以的合取，记以P Q，读作，读作P且且Q。 规定规定P Q是真的是真的当且仅当当且仅当P和和Q都是真的。都是真的。pqp q1 11 11 11 10 00 00 01 10 00 00 00 0日常语句中有：日常语句中有： 并且并且 与与 和和 “ ”是一个是一个2元逻辑联结词；元逻辑联结词；若若P，Q是原子命题，则是原子命题，则P Q是复合命题；是复合

18、命题； 合取联结词的例子合取联结词的例子 P: 225 Q：雪是白的。：雪是白的。 PQ：225并且雪是白的。并且雪是白的。 P: 今天刮风。今天刮风。 Q：今天下雨。：今天下雨。 PQ：今天刮风并且今天下雨。：今天刮风并且今天下雨。 注意：注意：“小王和小李是同学小王和小李是同学”是简单命题，这是简单命题，这里的里的“和和”没有合取的意思。没有合取的意思。析取析取联结联结词词 只有决定某一事件的有一个或一个以上具备，只有决定某一事件的有一个或一个以上具备，这一事件才能发生。这一事件才能发生。开关开关A开关开关B灯灯Y断开断开断开断开灭灭断开断开闭合闭合亮亮闭合闭合断开断开亮亮闭合闭合闭合闭合

19、亮亮设设P，Q是两个命题，命题是两个命题，命题 “P或者或者Q”称为称为P，Q的的析取，记以析取，记以P Q，读作，读作P或或Q。规定。规定P Q是真的当是真的当且仅当且仅当P，Q中中至少有一个是真的至少有一个是真的。pqp q1 11 11 11 10 01 10 01 11 10 00 00 0 “ ”是一个是一个2元逻辑联结词；元逻辑联结词；若若P，Q是原子命题，则是原子命题，则P Q是复合命题；是复合命题； 日常语言中有：日常语言中有： 或或 或者或者 析取联结词的例子析取联结词的例子 P: 225 Q：雪是白的。：雪是白的。 PQ：225或者雪是白的。或者雪是白的。 PQ显然是一个真

20、命题。显然是一个真命题。 P: 今天刮风。今天刮风。 Q：今天下雨。：今天下雨。 PQ ：今天刮风或者今天下雨。：今天刮风或者今天下雨。 显然，只有在今天刮了风，或者下了雨的情况显然，只有在今天刮了风，或者下了雨的情况 下下， P Q这句话才算说对。这句话才算说对。异或联结词异或联结词 : p q设设p，q是两个命题，命题是两个命题，命题 “p异或异或q”称为称为p，q的异的异或，记以或，记以p q，读作，读作p异或异或q。规定。规定p q是真的当是真的当且仅当且仅当p，q中中真值不同真值不同。pqp q1 11 10 01 10 01 10 01 11 10 00 00 0 “ ”是一个是一

21、个2元逻辑联结词；元逻辑联结词；若若p，q是原子命题，则是原子命题，则p q是复合命题是复合命题. 日常语言中有：日常语言中有： 或或 或者或者 注意：自然语言中的注意：自然语言中的“或或”可能是可能是“可兼或可兼或”，也可能是，也可能是“不可兼或不可兼或”（排斥或），而析取表达的是可兼或。（排斥或），而析取表达的是可兼或。异或联结词的例子异或联结词的例子 P：我明天到北京出差：我明天到北京出差 Q ：我明天到广州去度假：我明天到广州去度假 P Q：我明天到北京出差或者到广州去度假：我明天到北京出差或者到广州去度假 “我明天到北京出差或者到广州去度假我明天到北京出差或者到广州去度假”表示的表示

22、的是二者只能居其一，不会同时成立。因此不用析取是二者只能居其一，不会同时成立。因此不用析取联结词表示联结词表示 ，而是用，而是用异或联结词异或联结词。蕴含蕴含(条件条件)联结联结词词设设P，Q是两个命题，命题是两个命题，命题 “如果如果P，则，则Q”称为称为P蕴涵蕴涵Q，记以，记以PQ。 规定，规定，PQ是假的当且仅当是假的当且仅当P是真的而是真的而Q是假的。是假的。 pqp q1 11 11 11 10 00 00 01 11 10 00 01 1日常语言中有：日常语言中有： 如果如果则则 如果如果那么那么 在在PQ中，称中，称P为为前件前件，Q为为后件后件。 蕴含联结词的例子蕴含联结词的例

23、子用用表示下列命题：表示下列命题：只要天下雨，我就回家。只要天下雨，我就回家。只有天下雨，我才回家。只有天下雨，我才回家。除非天下雨，否则我不回家。除非天下雨，否则我不回家。仅当天下雨，我才回家。仅当天下雨，我才回家。解解 设设p：天下雨。：天下雨。 q：我回家。：我回家。 则则符号化为符号化为 pq。符号化为符号化为 qp，或：或： p q符号化为符号化为 qp，或：或： p q符号化为符号化为 qp，或：或： p q注注1. 前件为假时，命题为真前件为假时，命题为真如果蕴含前件如果蕴含前件P是假命题，那么不管是假命题，那么不管Q是什么命题，是什么命题，命题命题“如果如果P则则Q”在逻辑中都

24、被认为是真命题。在逻辑中都被认为是真命题。例：例：“如果张三能及格，那太阳从西边升起。如果张三能及格，那太阳从西边升起。”说话者当然知道两命题风马牛不相及，而一般人此说话者当然知道两命题风马牛不相及，而一般人此时并没有说谎的必要，即这是真命题，它所要明确时并没有说谎的必要，即这是真命题，它所要明确的是的是“张三能及格张三能及格”是假命题。是假命题。注注2. 前件、后件可以毫不相关前件、后件可以毫不相关在日常语言中在日常语言中“如果如果那么（则）那么（则）”所联结的句子之间所联结的句子之间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后

25、件，但件，但两个命题可以是毫不相关的两个命题可以是毫不相关的。 例：例： P：235 Q：雪是黑色的：雪是黑色的 PQ：如果：如果235，则雪是黑色的，则雪是黑色的 命题命题PQ是真命题，这有点不符合日常生活中的直观，但是真命题，这有点不符合日常生活中的直观，但这是逻辑的需要。这是逻辑的需要。注注3. 充分条件、必要条件充分条件、必要条件pq为真命题的逻辑关系是：为真命题的逻辑关系是： p是是q的的充分充分条件，条件， q是是p的的必要必要条件。条件。“q是是p的必要条件的必要条件”的叙述方式还有：的叙述方式还有： p仅当仅当q（仅当（仅当q，则，则p） 只有只有q才才p 只要只要p就就q 除

26、非除非q，否则非，否则非p（非（非p，除非，除非q）例：天下大雨（例：天下大雨（p)，地一定湿了，地一定湿了(q)。 pq等价（双条件）等价（双条件）联结联结词词设设P，Q是两个命题，命题是两个命题，命题 “P当且仅当当且仅当Q”称为称为P等等价价Q，记以，记以PQ。规定，。规定，PQ是真的当且仅当是真的当且仅当P，Q或者或者都是真的，或者都是假的都是真的，或者都是假的。pqp q1 11 11 11 10 00 00 01 10 00 00 01 1“p当且仅当当且仅当q”有两层含义：有两层含义：“p当当q”是指是指q p. “p仅当仅当q”是指是指p q.日常语言中有：日常语言中有： 当且

27、仅当当且仅当 充分必要充分必要 等价联结词的例子等价联结词的例子 P: 224 Q：雪是白色的。：雪是白色的。 P Q：224当且仅当雪是白色的。当且仅当雪是白色的。 显然，显然，P Q是真的，这符合直观。是真的，这符合直观。 P: 225 Q：雪是黑色的。：雪是黑色的。 P Q：225当且仅当雪是黑色。当且仅当雪是黑色。 显然，显然，P Q是真的，这符合直观。是真的，这符合直观。注注4. 充要条件充要条件p q为真命题的逻辑关系是：为真命题的逻辑关系是：p是是q的的充分充分条件，条件，q是是p的的必要必要条件。条件。命题公式（合式公式，命题公式（合式公式，WFF），是如下定义的一个符号串：）

28、，是如下定义的一个符号串：命题变元和命题常量命题变元和命题常量(1和和0)是命题公式；是命题公式；若若G是命题公式，则（是命题公式，则（ G）是命题公式。）是命题公式。若若G和和H是命题公式，则（是命题公式，则（ G）、（）、（G H）、（）、（G H）、）、（GH）、（）、（GH）是命题公式。）是命题公式。有限次应用、所得到的符号串是仅有的命题公式。有限次应用、所得到的符号串是仅有的命题公式。命题公式及其真值表 设设P为命题公式，为命题公式，Q为为P中的一个连中的一个连续的符号串，且续的符号串，且Q为命题公式，则称为命题公式，则称Q为为P的子公式。的子公式。（G H）为）为 （G H）的子公

29、式。）的子公式。子公式子公式 严格按照命题公式的定义，就会出现很多的括严格按照命题公式的定义，就会出现很多的括号。因此作如下一些可以省略括号的约定：号。因此作如下一些可以省略括号的约定： 最外层的括号可以省略；最外层的括号可以省略； 联结词运算的联结词运算的优先顺序优先顺序依次为依次为: 、 、 、； 同级运算同级运算从左至右从左至右依次进行。依次进行。关于命题公式关于命题公式命题的符号化命题的符号化所谓命题的符号化就是所谓命题的符号化就是使用符号使用符号命题变元、逻命题变元、逻辑联结词和括号将所给出的命题表示出来。辑联结词和括号将所给出的命题表示出来。将命题符号化的步骤：将命题符号化的步骤：

30、找出所给命题的所有找出所给命题的所有原子命题原子命题, 并用小写英文字母并用小写英文字母或带下标表示；或带下标表示； 确定应使用的确定应使用的联结词联结词,进而将原命题用符号表示出进而将原命题用符号表示出来来.命题符号化实例命题符号化实例如果你走路时看书，那么你一定会成为近视眼。如果你走路时看书，那么你一定会成为近视眼。解：令解：令 P：你走路；：你走路； Q：你看书；：你看书； R：你是近视眼。：你是近视眼。于是，上述命题符号化为：于是，上述命题符号化为：（P Q）R。除非他以书面或口头的方式正式通知我，否则我不参加明除非他以书面或口头的方式正式通知我，否则我不参加明天的会议。天的会议。解：

31、令解：令 P：他书面通知我；：他书面通知我； Q：他口头通知我；：他口头通知我； R：我参加明天的会议。：我参加明天的会议。于是，上述命题符号化为：于是，上述命题符号化为：（P Q）R。命题符号化实例命题符号化实例 将下列语句形式化将下列语句形式化狗急跳墙。狗急跳墙。 可表示为可表示为pq， 其中其中p：狗急了，：狗急了，q：狗跳墙。：狗跳墙。如果他不来如果他不来,那么他或者是生病了那么他或者是生病了,或者是不在本地。或者是不在本地。 可表示为可表示为p(qr)， 其中其中p：他来，：他来，q：他生病，：他生病，r：他在本地。：他在本地。命题符号化实例命题符号化实例只有努力学习、认真复习，才能

32、取得好成绩。只有努力学习、认真复习，才能取得好成绩。解：令解：令P表示表示“努力学习努力学习”； Q表示表示“认真复习认真复习”； R表示表示“取得好成绩取得好成绩”。则原句译为则原句译为R（P Q）。）。该语句能不能译为（该语句能不能译为（P Q） R？ 翻译是一定要考虑条件的必要性和充分性翻译是一定要考虑条件的必要性和充分性！对一个公式对一个公式A，将，将A在其所有解释下取得的在其所有解释下取得的真值列真值列成一个表成一个表，称为，称为A的真值表。的真值表。构造命题公式构造命题公式A的真值表的具体步骤为：的真值表的具体步骤为：找出找出A中所有命题变元中所有命题变元A1，An（一般按字典（一

33、般按字典顺序给出），列出所有可能的解释；顺序给出），列出所有可能的解释；按从低到高的顺序写出各层次的子公式；按从低到高的顺序写出各层次的子公式；对应每个解释，计算命题公式的各层次的子公对应每个解释，计算命题公式的各层次的子公式的真值，直到最后计算出命题公式式的真值，直到最后计算出命题公式A的真值。的真值。命题公式的真值表命题公式的真值表真值表真值表例：命题公式例：命题公式G=(P Q)R的真值表的真值表 P Q RP QG=(P Q)R0 0 0010 0 1010 1 0010 1 1011 0 0011 0 1011 1 0101 1 111一般来说一般来说,含含n个命题变元的命题公式的不

34、同的真值个命题变元的命题公式的不同的真值指派有指派有2n种种.rqp)( 练习：命题公式练习：命题公式 的真值表的真值表 p q r p p q( p q) r1 1 10111 1 00101 0 10011 0 00010 1 11110 1 01100 0 11110 0 01102022-6-19练习：练习：P58，综合题，综合题1,2题。题。命题公式等价：如果两个不同的命题公式命题公式等价：如果两个不同的命题公式P和和Q，无论其，无论其命题变元取什么值它们的真值都相同，则称该两个命题命题变元取什么值它们的真值都相同，则称该两个命题公式等价，记为公式等价，记为PQ。例例2-25证明证明 （AB）与）与A B是等价的。是等价的。 A AB B（ABAB）ABABT TT T F F F F T T F F T TT T F F T T F F F F F F F F F F F F 命题公式的等价律 其中其中A A、B B、C C等为命题变元，等为命题变元，T T表示表示“真真”，F F表示表示“假假”v零律：零律： AFAFA A AF AFF Fv幺律：幺律： ATATT TA TA TA A v幂等律：幂等律：AAAAA A A A A AA Av求补律：求补律：AAAAT T AA AAF Fv交换律：交换律：ABABBABA AB