逻辑代数基础3

1、,逻辑代数基础,课前预习将手机调到静音认真做笔记及时完成作业,上课要求,本节内容,2020/6/18,命题与连接词（重点）命题公式（重点）命题代数（难点）逻辑代数的等价律逻辑代数的应用,了解命题，原子命题，复合命题的概念掌握与、或、非三种复合命题（重点及难点）掌握逻辑代数的等价律掌握化简逻辑函数的方法,学习目标,玉龙雪山下的审判,在玉龙雪山脚下东巴谷的一条小路上立有一块木牌，请过路行人对一个案子进行审判。说的是有三个人，甲、乙、丙在玉龙山上射杀了一只老鹰，这三个人的行为因违反野生动物保护法而被警察拘捕，但是这三个人都否认老鹰是自己射杀的。经过盘查和询问，警察得出如下三个结论：如果甲是无罪的，则

2、乙和丙都有罪；乙和丙中必有一人有罪；要么甲无罪，要么乙有罪（但两者不能同时成立）。现在警方请求你协助判断甲、乙、丙三人谁有罪，谁没有罪，并在你认为有罪的人前面的筐里投入一块石头。笔者查看三个筐发现，乙的筐里石头最多，甲和丙的筐里则差不多。你认为游客们的判断是否正确呢？,逻辑学是研究思维形式及思维规律尤其是推理的学科,早在两千多年前就受到人们的重视。,逻辑学,古希腊（逻辑）,战国（名学）,古印度（因明）,德国数学家、哲学家莱布尼茨(16471716)首先提出用数学方法研究逻辑,就是建立一套表意符号体系,在符号之间进行形式推理.莱布尼茨是数理逻辑的创始人，也正因为这样,数理逻辑又称为符号逻辑。,数

3、理逻辑是一门新兴的边缘性学科，分为五个部分：即逻辑演算、证明论、公理集合论、递归论和模型论。从创始至今约有300年的历史。,数理逻辑概述,数理逻辑是用数学的方法来研究人类思维活动的一门数学学科，其显著特征是：符号化、形式化即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划,并基于符号串形式的演算来描述推理过程的一般规律。,数理逻辑概述,回顾计算机科学的发展，我们可以清晰地发现数理逻辑一直是计算机科学的理论基础和发展动力。,逻辑的数学分析思维规律的研究,关系逻辑德摩根定律,数理逻辑的起源与计算机科学,概念演算,一种按算术语言构成的思维符号语言,德国G.W.Leibniz(1626

4、-1716)把数学引入形式逻辑，明确提出用数学方法研究推理。英国G.Boole(1815-1864)等创立了逻辑代数，1847年Boole实现了命题演算。德国G.Frege(1848-1925)在1879年建立了第一个谓词演算系统。英国AlanM.Turing(1912-1954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机一种理想的计算机。,数理逻辑发展史中的代表人物,数理逻辑的学习,Edsger.W.Dijkstra1972年Turing奖获得者(1930-2002)“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的

5、话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。”,单源点最短路径算法,曹雪芹是红楼梦的作者。曹雪芹是小说家。小说家是文学家。,数理逻辑是以数学的方法研究推理的形式结构和规律的数学学科。所谓数学方法，是指建立一套符号，其作用是为了避免用自然语言讨论问题时所带来的歧义性。如，下面三条语句均用“是”作谓语动词：,学习数理逻辑,三个语句中的三个“是”含义各不同。曹雪芹是红楼梦的作者。此句中的“是”表示“”，其主语和谓语是对等的；曹雪芹是小说家。此句中的“是”表示“”，小说家是集合，曹雪芹只是其中的一分子；小说家是文学家。此句中的“是”表示“

6、”，文学家是包含着小说家的一个更大的集合。显然，符号准确地表达了语句的含义。,命题的定义,命题：能判断出真假的语句.,（1）你妈喊你回家吃饭.（2）盗墓笔记里面有大腕儿.（3）北京是中国的首都.（4）火星上有生物.,（5）x3。（6）立正！（7）我说的都是假话。（8）你喜欢网络游戏吗?,构成命题需要具备以下几个条件：必须是一个完整的句子，包括用数学式子表达；句子必须具有真假意义（即有对错之分）；句子能判断出是真还是假。,例下列句子都是命题吗？,1960年杭州下雪了。太阳系外有宇宙人。好大的雪啊！812。1+101=110。上海世博会开幕时天晴。大于2的偶数可表示成两个素数之和。AB。请勿吸烟。

7、姚明很帅。,具体命题的真假问题,在数理逻辑的学习中，不能去纠缠各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句。,公説公有理婆説婆有理,原子命题（简单命题）若一个命题不包含有更小的命题，即不可再分割的命题。小写英文字母p,q,r,s,或带下标p1,p2,p3,等来表示原子命题。复合命题若一个命题可以分解（分割）若干个原子命题。精确的定义为：设A1,A2,An是原子命题，用逻辑联结词将这n个命题联结起来，构成的一个新命题，则称这个新命题是复合命题。,原子命题与复合命题,命题的真值,命题的真值就是命题的逻辑取值.,把1和0称为逻辑常量.

8、在逻辑表达式中出现的p,q,r或p1,p2,p3等称为命题变元或逻辑变量.命题变元可以代表任意命题,从取值的角度看,命题变元既可以取1又可以取0.,常量与逻辑变量,字母p表示,命题具体的、特定的命题，有确定的真值,命题变元任意命题，没有确定的真值,逻辑联结词,命题逻辑中出现更多的是复合命题.一方面，复合命题是由原子命题构成的，它需要联结词；另一方面，给定了原子命题，使用逻辑联结词，可以将它们构成一个复合命题.逻辑联结词就是逻辑运算.,五种常用的联结词：否定联结词（非）合取联结词（与）析取联结词（或）蕴含联结词等价联结词,否定联结词（非）,当某一条件具备了，事情不会发生；而此条件不具备时，事情反

9、而发生。这种逻辑关系称为非逻辑关系，简称非逻辑。,开关与灯并联电路,设P是一个命题，命题“P是不对的”称为P的否定，记以P，读作非P。P是真的当且仅当P是假的。,否定联结词是一元逻辑运算；若P是原子命题，则P是复合命题。,日常语句中有：非不并非,否定联结词的例子,P青岛是中国的城市。P：青岛不是中国的城市。P是真命题，P是假命题。P：雪是黑色的。P：雪不是黑色的。命题P是假的，命题P是真的。命题的真假，与其否定的真假，正好相反，这符合我们的直观。,合取联结词,只有决定某一事件的所有条件全部具备，这一事件才能发生。,开关A,开关B,灯F,断断断合合断,合合,灭灭灭,亮,A,B,F,10,11,0

10、1,00,0,0,1,0,设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以PQ，读作P且Q。规定PQ是真的当且仅当P和Q都是真的。,日常语句中有：并且与和,“”是一个2元逻辑联结词；若P，Q是原子命题，则PQ是复合命题；,合取联结词的例子,P:225Q：雪是白的。PQ：225并且雪是白的。,P:今天刮风。Q：今天下雨。PQ：今天刮风并且今天下雨。,注意：“小王和小李是同学”是简单命题，这里的“和”没有合取的意思。,析取联结词,只有决定某一事件的有一个或一个以上具备，这一事件才能发生。,设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以PQ，读作P或Q。规定PQ是真的当且仅当P

11、，Q中至少有一个是真的。,“”是一个2元逻辑联结词；若P，Q是原子命题，则PQ是复合命题；,日常语言中有：或或者,析取联结词的例子,P:225Q：雪是白的。PQ：225或者雪是白的。PQ显然是一个真命题。,P:今天刮风。Q：今天下雨。PQ：今天刮风或者今天下雨。显然，只有在今天刮了风，或者下了雨的情况下，PQ这句话才算说对。,异或联结词:pq,设p，q是两个命题，命题“p异或q”称为p，q的异或，记以pq，读作p异或q。规定pq是真的当且仅当p，q中真值不同。,“”是一个2元逻辑联结词；若p，q是原子命题，则pq是复合命题.,日常语言中有：或或者,注意：自然语言中的“或”可能是“可兼或”，也可

12、能是“不可兼或”（排斥或），而析取表达的是可兼或。,异或联结词的例子,P：我明天到北京出差Q：我明天到广州去度假PQ：我明天到北京出差或者到广州去度假“我明天到北京出差或者到广州去度假”表示的是二者只能居其一，不会同时成立。因此不用析取联结词表示，而是用异或联结词。,蕴含(条件)联结词,设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以PQ。规定，PQ是假的当且仅当P是真的而Q是假的。,日常语言中有：如果则如果那么,在PQ中，称P为前件，Q为后件。,蕴含联结词的例子,用表示下列命题：只要天下雨，我就回家。只有天下雨，我才回家。除非天下雨，否则我不回家。仅当天下雨，我才回家。解设p：天下

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

14、题PQ是真命题，这有点不符合日常生活中的直观，但这是逻辑的需要。,注3.充分条件、必要条件,pq为真命题的逻辑关系是：p是q的充分条件，q是p的必要条件。“q是p的必要条件”的叙述方式还有：p仅当q（仅当q，则p）只有q才p只要p就q除非q，否则非p（非p，除非q）,例：天下大雨（p)，地一定湿了(q)。pq,等价（双条件）联结词,设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以PQ。规定，PQ是真的当且仅当P，Q或者都是真的，或者都是假的。,“p当且仅当q”有两层含义：“p当q”是指qp.“p仅当q”是指pq.,日常语言中有：当且仅当充分必要,等价联结词的例子,P:224Q：雪是白

15、色的。PQ：224当且仅当雪是白色的。显然，PQ是真的，这符合直观。,P:225Q：雪是黑色的。PQ：225当且仅当雪是黑色。显然，PQ是真的，这符合直观。,注4.充要条件,pq为真命题的逻辑关系是：p是q的充分条件，q是p的必要条件。,命题公式（合式公式，WFF），是如下定义的一个符号串：命题变元和命题常量(1和0)是命题公式；若G是命题公式，则（G）是命题公式。若G和H是命题公式，则（G）、（GH）、（GH）、（GH）、（GH）是命题公式。有限次应用、所得到的符号串是仅有的命题公式。,命题公式及其真值表,设P为命题公式，Q为P中的一个连续的符号串，且Q为命题公式，则称Q为P的子公式。（GH

16、）为（GH）的子公式。,子公式,严格按照命题公式的定义，就会出现很多的括号。因此作如下一些可以省略括号的约定：最外层的括号可以省略；联结词运算的优先顺序依次为:、；同级运算从左至右依次进行。,关于命题公式,命题的符号化,所谓命题的符号化就是使用符号命题变元、逻辑联结词和括号将所给出的命题表示出来。,将命题符号化的步骤：找出所给命题的所有原子命题,并用小写英文字母或带下标表示；确定应使用的联结词,进而将原命题用符号表示出来.,命题符号化实例,如果你走路时看书，那么你一定会成为近视眼。解：令P：你走路；Q：你看书；R：你是近视眼。于是，上述命题符号化为：（PQ）R。,除非他以书面或口头的方式正式通

17、知我，否则我不参加明天的会议。解：令P：他书面通知我；Q：他口头通知我；R：我参加明天的会议。于是，上述命题符号化为：（PQ）R。,命题符号化实例,将下列语句形式化狗急跳墙。可表示为pq，其中p：狗急了，q：狗跳墙。如果他不来,那么他或者是生病了,或者是不在本地。可表示为p(qr)，其中p：他来，q：他生病，r：他在本地。,命题符号化实例,只有努力学习、认真复习，才能取得好成绩。解：令P表示“努力学习”；Q表示“认真复习”；R表示“取得好成绩”。则原句译为R（PQ）。,该语句能不能译为（PQ）R？,翻译是一定要考虑条件的必要性和充分性！,对一个公式A，将A在其所有解释下取得的真值列成一个表，称

18、为A的真值表。,构造命题公式A的真值表的具体步骤为：找出A中所有命题变元A1，An（一般按字典顺序给出），列出所有可能的解释；按从低到高的顺序写出各层次的子公式；对应每个解释，计算命题公式的各层次的子公式的真值，直到最后计算出命题公式A的真值。,命题公式的真值表真值表,例：命题公式G=(PQ)R的真值表,一般来说,含n个命题变元的命题公式的不同的真值指派有2n种.,练习：命题公式的真值表,2020/6/18,练习：P58，综合题1,2题。,命题公式等价：如果两个不同的命题公式P和Q，无论其命题变元取什么值它们的真值都相同，则称该两个命题公式等价，记为PQ。例2-25证明（AB）与AB是等价的。,命题公式的等价律,其中A、B、C等为命题变元，T表示“真”，F表示“假”零律：AFAAFF幺律：ATTATA幂等律：AAAAAA求补律：AATAAF交换律：ABBAABBA,结合律：A（BC）（AB）CA（BC）（AB）C分配律：A（BC）ABACABC（AB）（AC）吸收律：ABABA（AB）（AB）A狄摩根定律：（AB）AB（AB）AB双重否定律：AA,证明狄摩根定律,例2-26证明狄摩根定律之一：（AB）AB。,逻辑代数的等价律,在逻辑代数中通常用符号“.”表示“与”运算。通常情况下可以省略。用