离 散 数 学,2020年10月9日星期五,,数理逻辑（Mathematical Logic） 是研究演绎推理的一门学科，用数学的方法来研究推理的规律统称为数理逻辑。 公元前四世纪由希腊的亚里斯多德首创 他力图把思维形式和存在联系起来， 并按照客观实际来阐明逻辑的范畴。,第二篇 数理逻辑,,主要研究内容：推理 着重于推理过程是否正确 着重于语句之间的关系 主要研究方法：数学的方法 就是引进一套符号体系的方法，所以数理逻辑又叫符号逻辑（Symbolic Logic）。,第二篇 数理逻辑,,什么是数理逻辑 ？ 用数学的方法来研究推理的规律统称为数理逻辑。 为什么要研究数理逻辑？ 程序算法数据 算法逻辑控制,总结,日常语言叫做自然语言。 自然语言丰富，但是也有模棱两可的特性。,小朱和小张在寝室聊天，小李破门而入，小朱感叹：“说曹操曹操到。”（经典问题） 1、请问是谁来了? A、小朱 B、小张 C、小李D、曹操 2、门破了没有？ A、破了 B、没破,一个风和日丽的早晨，Summer跑过来对小王说：“好激动啊，刚刚捡到了100块钱啊！”小王说：“天上掉馅饼的事，你都遇到了！”请问：天上在下着什么？ A、小雨 B、钱 C、没下 D、馅饼,需要引入一种形式化语言单一、明确 这种形式化语言在数理逻辑中叫做目标语言 目标语言和一些规定的公式与符号构成了数理逻辑的形式符号体系。,,第二篇 数理逻辑,,第三章 命题逻辑,命题逻辑也称命题演算，或语句逻辑。 研究内容： （1）研究以命题为基本单位构成的前提和结论之间的可推导关系 （2）研究什么是命题？ （3）研究如何表示命题？ （4）研究如何由一组前提推导一些结论？,,第三章 命题逻辑,命题逻辑的特征： 在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析为非命题的集合，不把谓词和量词等非命题成份分析出来。,,第三章 命题逻辑,,3.1 本章学习要求,,3.2.1 命题 定义3.2.1具有确切真值的陈述句称为命题, 该命题可以取一个“值”，称为真值。 真值只有“真”和“假”两种， 分别用“”(或“”)和“”(或“”)表示。,3.2 命题与命题联结词,,（1）太阳是圆的； （2）成都是一个旅游城市； （3）北京是中国的首都； （4）这个语句是假的； （5）1110； （6）+y； （7）我喜欢踢足球； （8）3能被2整除； （9）地球外的星球上也有人； （10）中国是世界上人口最多的国家； （11）今天是晴天；,例3.2.1,T,T,T/F,非命题,T/F,F,T/F,T,T/F,T,非命题,,例3.2.1（续）,（12）把门关上； （13）滚出去！ （14）你要出去吗？ （15）今天天气真好啊！,非命题,非命题,非命题,非命题,注意： 一切没有判断内容的句子都不能作为命题，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。,,命题一定是陈述句，但并非一切陈述句都是命题。 命题的真值有时可明确给出，有时还需要依靠环境、条件、实际情况时间才能确定其真值。,结论：,在数理逻辑中像字母“x”、“y”、“z”等字母总是表示变量。,约定：,,下列语句是否是命题？并判断其真值结果？ （1）四川不是一个国家； （2）3既是素数又是奇数； （3）张谦是大学生或是运动员； （4）如果周末天气晴朗，则我们将到郊外旅游； （5）2+2=4当且仅当雪是白的。,例3.2.2,T/F,T/F,T,T,T,,一般来说，命题可分两种类型： 原子命题(简单命题)：不能再分解为更为简单命题的命题。 复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。,命题的分类,,今天天气很冷。 今天天气很冷并且刮风。 今天天气很冷并且刮风，但室内暖和。,例3.2.3,通常用大写的带或不带下标的英文字母、.P、Q、R、. Ai、Bi P=1,Q=0,5.等价,P当且仅当Q,P等价于Q,PQ,PQ=1P=1,Q=1 或P=0,Q=0,例如：命题P：2是素数；Q：北京是中国的首都,1.否定联结词,设p为命题，则p的否定是一个复合命题，记作： p ，读作“非p”或“p的否定”。定义为：若p真值为1，则 p为0；若p为0，则 p的真值为1。 联结词“”也可以看作逻辑运算，它是一元运算。 【例】否定下列命题。 p ：王强是一名大学生。 p ：王强不是一名大学生。,P:苏州处处清洁 P: 苏州不处处清洁 (注意,不是处处不清洁) S：苏州处处不清洁 (假设苏州有两个地方寒山寺 、沙家浜）,所以P一定不是S,Q:这些都是男同学,Q:这些不都是男同学,S：这些都不是男同学,S和Q、Q的关系？,2. 合取联结词,定义1.1.2设p和q均为命题，则p和q的合取是一个复合命题，记作pq ，读作“p与q”或“p合取q”。 定义为：当且仅当p和q均为1时，pq的真值才为1，其他情况pq 的真值都为0。,p：2是素数。（真值？） q：2是偶数。（真值？） 则pq表示： 2是素数和偶数 由于p，q的真值均为1，所以pq的真值也为1。,合取的概念与自然语言中的“与”“和”“并且”的意义很相似，但是不完全相同 小王是大学生，小张是大学生。 两个命题的合取为小王和小张都是大学生 但是对于命题“小王与小张是好朋友”。这个就不是命题的合取，而是一个普通命题。,p：我去旅游 q：教室里面有电视 pq：我去旅游并且教室里面有电视 自然语言中，上述命题合取没有任何意义。 但是在数理逻辑中， pq仍然是一个命题。满足合取的真值定义,练习:将下列命题符号化,张三既用功又聪明 p：张三用功 q：张三聪明 p q,张三不仅用功又聪明 p：张三用功 q：张三聪明 p q,张三虽然聪明，但不用功 p：张三用功 q：张三聪明 q p,张三与李四是同班同学 t：张三与李四是同班同学 简单陈述句，t是原子命题,3. 析取联结词,定义设p和q均为命题，则p和q的析取是一个复合命题，记作pq，读作“p或q”或者“p析取q”。定义为：当且仅当p和q真值均为0时， pq真值才为0。其他情况pq真值都为1 联结词“”也可以看成逻辑运算，它是二元逻辑运算,p：张山是大学生 q：张山是篮球运动员 pq的语义： 张山是大学生 或者张山是篮球运动员,“”与汉语中的“或”相似，但又不相同。 分析下列两个命题中的“或”，有什么区别？ 今晚9点，中央一台播放“雍正王朝”或者转播足球比赛 (不可兼) 灯泡有故障或开关有故障。 (可兼, “”是可兼或) 汉语中的或有可兼或与不可兼或(排斥或)的区分。,今晚9点，中央一台播放“雍正王朝”或者转播足球比赛,p：今晚9点，中央一台播放“雍正王朝” q：今晚9点，中央一台转播足球比赛 (p q) ( p q) 此复合命题为真当且仅当p，q中一个为真一个为假,4. 排斥析取词,定义: 设定p，q，则“p排斥析取q”也是一种命题，记作p q。,5. 条件联结词,定义:设p和q均为命题，复合命题”如果p，则q”，称为p与q的蕴含式，记为：pq。读作“如果p，那么q”或“若p，则q”。 p是蕴含式的前件，q为蕴含式的后件 真值定义为：当且仅当p为1，q为0时， pq才为0。 pq的逻辑关系为q是p的必要条件,使用，注意几点：,(1)q是p的必要条件有许多不同叙述方式： ”只要p就q”, ”因为p，所以q”, ”p仅当q”, ”只有q才p”, ”除非q才p”, ”除非q，否则非p”等等,(2)在自然语言中，如果p则q，前件p与后件q往往具有某种内在联系。但是在数理逻辑中，p与q可以无任何内在联系,(3)在数学或其他自然科学中，如果p则q，往往表达前件p为真，后见q也为真的推理关系。但是在数理逻辑中，作为一种规定，当p为假时，无论q是真是假， pq均为真。 自然语言中，前件为假，结论不管真假，整个语句的意义往往无法确定。,例 p： 月亮下山 q： 3+3=6,则pq： 若月亮下山,则3+3=6 （并没有实质蕴含关系，仍承认）,qp： 叫做pq的逆命题,qp： 叫做pq的逆否命题,【例】 p：小王努力学习。q：小王学习成绩优秀。 pq表示？ 如果小王努力学习，那么他的学习成绩就优秀。,如果小明学日语，小华学英语，则小芳学德语。 p：小明学日语 q：小华学英语 x：小芳学德语. 则原式可表示为：(pq)x,5. 等价(双条件)联结词,定义：设p和q均为命题，其复合命题pq称为双条件命题，读作：“p双条件q”或者“p等价q”。定义为：当且仅当p和q的真值相同时， pq真值为1。 联结词“”也可以理解成逻辑运算，它是二元逻辑运算 双条件联结词表示的是一个充分必要关系,【例】 设p：张华是三好学生。 q：张华德、智、体全优秀。 pq表示： 张华是三好学生当且仅当德、智、体全优秀,p：2+2=4 ：1,,总结,,说明,1、联结词是句子与句子之间的联结，而非单纯的名词、形容词、数词等地联结； 2、联结词是两个句子真值之间的联结，而非句子的具体含义的联结，两个句子之间可以无任何地内在联系；,,说明,3、联结词与自然语言之间的对应并非一一对应；,,符号化下列命题 （1）四川不是人口最多的省份； （2）王超是一个德智体全面发展的好学生； （3）教室的灯不亮可能是灯管坏了或者是停电了； （4）如果周末天气晴朗，那么学院将组织我们到石像湖春游； （5）两个三角形全等当且仅当三角形的三条边全部相等。,例3.2.4,,例3.2.4 解,（1）设：四川是人口最多的省份。 则命题（1）可表示为。 （2）设：王超是一个思想品德好的学生； ：王超是一个学习成绩好的学生； R：王超是一个体育成绩好的学生。 则命题（2）可表示为R。 （3）设：教室的灯不亮可能是灯管坏了 ：教室的灯不亮可能是停电了 则命题（3）可表示为。,,（4）设：周末天气晴朗； ：学院将组织我们到石像湖春游。 则命题（4）可表示为。 （5）设：两个三角形全等； ：三角形的三条边全部相等。 则命题（5）可表示为。,例3.2.4 解(续),,为了不使句子产生混淆，作如下约定，命题联结词之优先级如下：,否定合取析取蕴涵等价 同级的联结词，按其出现的先后次序(从左到右) 若运算要求与优先次序不一致时，可使用括号；同级符号相邻时，也可使用括号。括号中的运算为最优先级。,约 定,,设命题P：明天上午七点下雨；Q：明天上午七点下雪； R：我将去学校。 符号化下述语句： 如果明天上午七点不是雨夹雪，则我将去学校 如果明天上午七点不下雨并且不下雪，则我将去学校 如果明天上午七点下雨或下雪，则我将不去学校 明天上午我将雨雪无阻一定去学校,可符号化为： (PQR)(PQR) (PQR)(PQR)。 或 (PQ)(PQ)(PQ) (PQ)R。,例3.2.5,可符号化为：(PQ)R。,可符号化为:(PQ)R。,可符号化为:(PQ)R。,,例3.2.6,设命题P：你陪伴我； Q：你代我叫车子； R：我将出去。 符号化下述语句： 除非你陪伴我或代我叫车子，否则我将不出去 如果你陪伴我并且代我叫辆车子，则我将出去 如果你不陪伴我或不代我叫辆车子，我将不出去,R(PQ) 或 (PQ)R,(PQ)R,(PQ)R,,设P:雪是白色的;Q:2+2=4。将下列命题符号化： （1）因为雪是白色的，所以2+2=4； PQ （2）如果2+2=4，则雪是白色的； QP （3）只有雪是白色的，才有2+2=4； QP （4）只有2+2=4，雪才是白色的； PQ （5）只要雪不是白色的，就有2+2=4； PQ （6）除非雪是白色的，否则2+24； P Q或QP （7）雪是白色的当且仅当2+2=4； P Q,,3.2.4 命题联结词的应用,例 3.2.7 用复合命题表示如下图所示的开关电路：,图3.2.1 图3.2.2 图3.2.3,AB,AB,A,设：开关闭合；：开关闭合。,,3.3 命题公式、解释与真值表,定义3.3.1 一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。 而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的变域是集合T，F(或0，1) 注意 (1)复合命题为命题变元的“函数”,其函数值仍为真或“假”值。 (2)真值函数或命题公式，没有确切真值。,真值函数,,3.3.1命题公式,定义3.3.2 (命题公式) 命题变元本身是一个公式； 如G是公式，则(G)也是公式； 如G，H是公式，则(GH)、(GH)、(GH)、(GH)也是公式； 仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、等表示。,,符号串： (PQ)； (P(PQ) ) )； ( ( (PQ)(RQ) ) (PR) )。 都是命题公式。,例3.3.1,例3.3.2符号串： (PQ)Q)；(PQ； (PQ(R； PQ。 等都不是合法的命题公式。,,例3.3.3,试用符号形式写出下列命题： （1）虽然今天天气晴朗，老陈还是不来； （2）除非你陪伴我或代我叫车子，否则我将不出去； （3）停机的原因在于语法错误或者程序错误； （4）若a和b是偶数，则a+b是偶数； （5）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。,,例3.3.3试用符号形式写出下列命题,（1）虽然今天天气晴朗，老陈还是不来。P：今天天气晴朗,Q：老陈还是不来,则有： PQ； （2）除非你陪伴我或代我叫车子，否则我将不出去 P：你陪伴我； Q：你代我叫车子；R：我出去。则： RPQ或PQR； （3）停机的原因在于语法错误或者程序错误。P：停机的原因在于语法错误，Q：停机的原因在于程序错误，则有： P Q；,（4）若a和b是偶数，则a+b是偶数。P：a是偶数；Q：b是偶数，R：a+b是偶数，则有： PQR； （5）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。P：我们要做到身体好,Q：我们要做到学习好, R：我们要做到工作好，S：我们要为祖国四化建设而奋斗，则有： 一般来说，若有个命题变元，则应有2n个不同的解释。 如果公式G在解释下是真的，则称满足G；如果G在解释下是假的，则称弄假G。 定义3.3.4 将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。,,例3.3.5,求下面公式的真值表： (P(PQ)R)Q 其中，、是的所有命题变元。,,例3.3.5（续）,进一步化简为：,成真赋值， (Q)。,,从这三个真值表可以看到一个非常有趣的事实：,公式G1对所有可能的解释具有“真”值 公式G3对所有可能的解释均具有“假”值 公式G2则具有“真”和“假”值,结论,,定义3.3.5,公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。 公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。 公式G称为可满足的，如果它不是永假的。,,从上述定义可知三种特殊公式之间的关系：,永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。 永真式一定是可满足式,可满足式不一定是永真式 可满足式的否定不一定为不可满足式(即为矛盾式),结论,,例3.3.7,写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。 （1）G1=()()； （2）G2=(Q)(Q)(Q)； （3）G3=(PQ)Q。,,例3.3.7 解,三个公式的真值表如下：,,若将其看成两个公式，分别令： ， 。 则是一个永真公式，即这两个公式对任何解释都必同为真假，此时，说和相等，记为。为此可定义：,分析公式（1）,定义3.3.6 设G、H是公式，如果在任意解释下，G与H的真值相同，则称公式G、H是等价的，记作GH。,() (),,公式G、H等价的充分必要条件是公式GH是永真公式 证明:“”假定G，H等价，则G，H在其任意解释下或同为真或同为假，于是由“”的意义知，GH在其任何的解释下，其真值为“真”，即GH为永真公式。 “”假定公式GH是永真公式，是它的任意解释，在下，GH为真，因此，G、H或同为真，或同为假，由于的任意性，故有GH。,定理3.3.1,,首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH 的结果不是命题公式。 其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。,“” 与“”的区别,,“=”的性质,由于“=”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质： （1）自反性 G=G； （2）对称性 若G=H，则H=G； （3）传递性 若G=H，H=S，则G=S。 这三条性质体现了“=”的实质含义。,,3.3.4 A(AB)AB,,这种图是将G，H理解为某总体论域上的子集合，而规定GH为两集合的公共部分（交集合），GH为两集合的全部（并集合），G为总体论域（如矩形域）中G的补集，将命题中的真值“1”理解为集合中的总体论域（全集），将命题中的真值“0”理解为集合中的空集，则有：,命题与集合之间的关系,“” 若G是永真公式（或永假公式），则G也是一个永真公式（或永假公式）。,定理3.3.2(代入定理),,例3.3.9,设(, )()，证明公式G是一个永真公式。另有两个任意公式： (, )()； (, )()。 进一步验证代入定理的正确性。,解 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1H1，则GH。,利用24个基本等价公式及代入定理和替换定理，可完成公式的转化和等价判定。 有些教材叫等值演算,利用等值演算证明p(qr) = (pq)r 证p(qr) = p(qr) （蕴涵等值式，置换规则） = (pq)r （结合律，置换规则） = (pq)r （德摩根律，置换规则） = (pq)r （蕴涵等值式，置换规则） 今后在注明中省去置换规则 注意：用等值演算不能直接证明两个公式不等值,,例3.3.10,利用基本的等价关系，完成如下工作： （1）判断公式的类型： 证明 () ()()()是一个永真公式。 （2）证明公式之间的等价关系： 证明() = () （3）化简公式： 证明(P(R)(R)(PR) = Y,,例3.3.14,一家航空公司，为了保证安全，用计算机复核飞行计划。每台计算机能给出飞行计划正确或有误的回答。由于计算机也有可能发生故障，因此采用三台计算机同时复核。由所给答案，再根据“少数服从多数”的原则作出判断，试将结果用命题公式表示，并加以简化，画出电路图。,,例3.3.14 解,设C1，C2，C3分别表示三台计算机的答案。 =(C2C3)(C1C3)(C1C2),,3.5 公式的标准型范式,3.5.1 析取范式和合取范式 定义3.5.1 （1）命题变元或命题变元的否定称为文字 （2）有限个文字的析取称为析取式(也称为子句） （3）有限个文字的合取称为合取式(也称为短语） （4）P与 P称为互补对。,,例子,（1）、是文字； （2）是子句； （3）是短语。,P是一个子句，这种说法正确么？,一个命题变元或者其否定既可以是简单的子句，也可以是简单的短语。,因此，不但是文字，也是子句、短语,,定义3.5.2,（1）有限个短语的析取式称为析取范式 （2）有限个子句的合取式称为合取范式,一个不含最外层括号的短语（子句）也可以是析取范式（合取范式）。,,例子,（1）、是析取范式、合取范式； （2）是子句、析取范式、合取范式， ( )仅是子句、合取范式； （3） 是短语、析取范式、合取范式， ()仅是短语、析取范式； （4）()()是析取范式； （5）()()是合取范式； （6）句子()、()既不是析取范式也不是合取范式,,总结,（1）单个的文字是子句、短语、析取范式，合取范式 （2）单个的子句是析取范式； （3）单个的短语是合取范式； （4）若单个的子句（短语）无最外层括号，则是合取范式（析取范式）； （5）析取范式、合取范式仅含联结词集， （6） “”联结词仅出现在命题变元前。,,范式的求解方法,定理3.5.1 对于任意命题公式，都存在与其等价的析取范式和合取范式。,转换方法：,（1）利用等价公式中的等价式和蕴涵式将公式中的、用联结词 、来取代，这可利用如下等价关系：,() = ()； () = ()() = ()()。,,范式的求解方法(续),（2）重复使用德摩根定律将否定号移到各个命题变元的前端，并消去多余的否定号，这可利用如下等价关系：() =； () = ； () = 。,（3）重复利用分配律，可将公式化成一些合取式的析取，或化成一些析取式的合取，这可利用如下等价关系：() = ()()； () = 这种不惟一的表达形式给研究问题带来了不便。,,3.5.2 主析取范式和主合取范式,1 极小项和极大项,定义 3.5.3 在含有n个命题变元P1、P2、P3、Pn的短语或子句中，若每个命题变元与其否定不同时存在，但二者之一恰好出现一次且仅一次，则称此短语或子句为关于P1、P2、P3、Pn的一个极小项或极大项。,对于n个命题变元，可构成2n个极小项和2n个极大项,,例子,（1）一个命题变元P， 对应的极小项有两项：P、 P； 对应的极大项有两项：P、 P。 （2）两个命题变元P、Q， 对应的极小项有四项： PQ、 PQ、P Q、 P Q； 对应的极大项有四项： PQ、 PQ、P Q、 P Q。,,例子（续）,（3）三个命题变元P、Q、R， 对应的极小项有八项： 、 、 、； 对应的极大项有八项： 、 、 、。,,两个命题变元的所对应极小项真值表,注意：（1）没有等价的两个极小项； （2）使该极小项的真值为真的指派是唯一的,并且 使得其它极小项为假； （3）使极小项为真的那组指派为对应极小项的编码； （4）命题变元与1对应，命题变元的否定与0对应。,0、0为真 0 0 m00(m0) 0 1为真0 1 m01(m1) 1 0为真1 0 m10(m2) 1 1为真1 1 m11(m3),,两个命题变元的所对应极大项真值表,注意：（1）没有等价的两个极大项； （2）使该极大项的真值为假的指派是唯一的并且 使得其它极大项为真； （3）使极大项为假的那组指派为对应极大项的编码； （4）命题变元与0对应，命题变元的否定与1对应。,0、0为假 0 0 M00(M0) 0 1为假0 1 M01(M1) 1 0为假1 0 M10(M2) 1 1为假1 1 M11(M3),,三个命题变元的极小项和极大项,mimj=F,,极小项和极大项的性质,任意两个极小项的合取必为假； 任意两个极大项的析取必为真； 极大项的否定是极小项； 极小项的否定是极大项； 所有极小项的析取为永真公式； 所有极大项的合取是永假公式。,Mi=mi,MiMj=T,Mi= mi,,2 主析取范式和主合取范式,定义3.5.4 （1）在给定的析取范式中，每一个短语都是极小项，则称该范式为主析取范式 （2）在给定的合取范式中，每一个子句都是极大项，则称该范式为主合取范式 （3）如果一个主析取范式不包含任何极小项，则称该主析取范式为“空”；如果一个主合取范式不包含任何极大项，则称主合取范式为“空”。,,定理3.5.2,任何一个公式都有与之等价的主析取范式和主合取范式。,证明（1）利用定理3.5.1先求出该公式所对应的析取范式和合取范式；,（2）在析取范式的短语和合取范式的子句中重复出现的命题变元，将其化成只出现一次；,（3）去掉析取范式中的所有永假式（ PP ）， 去掉合取范式中所有永真式（ PP ）,,定理3.5.2 证明（续）,（4）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，则可用公式：()Q = Q将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项 若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，则可用公式：()Q = Q 将命题变元P补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是标准的极大项；,,证明（续）,（5）利用等幂律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。,,3 主合取范式,,需要说明,求任何一个公式的主析取范式和主合取范式不仅要取决于该公式，而且取决于该公式所包含的命题变元。,如公式： G1 = (PQ)Q， G2(P, Q, R) = (PQ)Q。 前者是依赖于两个命题变元的，后者应依赖于三个命题变元。,,如何用极小项来构成主析取范式？,m1必须包含在 主析取范式中,m0必须包含在 主析取范式中,m3必须包含在 主析取范式中,m2一定不能包含 在主析取范式中,主析取范式中必须且只能包含使得公式 真值为真的那些解释对应的极小项。,P-Q 与m0m1m3 一定等价,,如何用极大项来构成主合取范式？,M1必须包含在 主合取范式中,M2必须包含在 主合取范式中,M0一定不能包含 在主合取范式中,M3一定不能包含 在主合取范式中,主合取范式中必须且只能包含使得公式 真值为假的那些解释对应的极大项。,,真值表技术,（1）列出公式对应的真值表，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项进行析取即可得到相应的主析取范式。,（2）列出公式对应的真值表，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个解释所对应的极大项，将这些极大项进行合取即可得到相应的主合取范式。,,例3.5.4,利用真值表技术求公式G = ()的主析取范式和主合取范式。,,例3.5.4（续）,（1）求主析取范式 找出真值表中其真值为真的行： 2. 0 0 1； 4. 0 1 1； 5. 1 0 0； 6. 1 0 1； 8. 1 1 1。 这些行所对应的极小项分别为： P， P，P， P，P。,,例3.5.4（续）,将这些极小项进行析取即为该公式G的主析取范式。 G = () = 主析取范式和主合取范式之间的转换,（1）已知公式G的主析取范式，求公式G的主合取范式,（a）求G的主析取范式，即G的主析取范式中没有出现过的极小项的析取，若,为的主析取范式。其中，mji(i=1,2,2n-k)是mi(i=0,2n-1)中去掉mli(i=,k)后剩下的极小项。,为的主析取范式，则,,主析取范式主合取范式,（b）G=(G)即是G的主合取范式。即，,为G 的主合取范式。,,主合取范式主析取范式,（1）已知公式G的主合取范式，求公式G的主析取范式,（a）求G的主合取范式，即G的主合取范式中没有出现过的极大项的合取，若,为的主合取范式。其中，Mji(i=1,2,2n-k)是Mi(i=0,2n-1)中去掉Mli(i=,k)后剩下的极大项。,为的主合取范式，则,,主合取范式主析取范式,（2）已知公式G的主合取范式，求公式G的主析取范式 （a）求G的主合取范式，即G的主合取范式中没有出现过的极大项的合取，若 为的主合取范式，则 为的主合取范式。 其中，mji (i=1,2,2n-k)是Mi(i=0,2n-1)中去掉mli (i=,k)后剩下的极大项。,,主合取范式主析取范式,（b）G=(G)即是G的主析取范式。即，,为G m1m3m5 m6m7 （主析取范式） (pq)r M0M2M4 （主合取范式）,,3.5.3 范式中的难点,1、如何正确的理解范式定义中的“有限个文字”、“有限个短语”、“有限个子句”的概念是很关键的，“有限个”N=0, 1, 2, , n, ； 2、使用真值表技术求主范式时注意正确地建立真值表，正确地掌握真值解释还原成子句和短语的方法；,,3.5.3 范式中的难点,3、使用公式转换法求主范式时，需要增加某一个命题变元，此时注意关于该变元的永真公式和永假公式的正确加入，同时注意公式的正确化简； 4、利用主析取求主合取或者利用主合取求主析取时，注意是“”的主析取范式的否定或“”的主合取范式的否定，而非直接是G的否定。,,3.5.4 范式的应用,定理3.5.3 （1）公式G为永真式G的合取范式中每个简单的析取式至少包含一个命题变元及其否定； （2）公式G为永假式G的析取范式中每个简单的合取式至少包含一个命题变元及其否定；,,3.5.4 (PPQ)(QPQ)析取范式,由于该公式所对应的析取范式中的每一个简单的合取式至少包含一个命题变元及其否定，根据定理3.5.3知，该公式是一个永假公式。,,定理3.5.4,（1）如果命题公式是永真公式它的主析取范式包含所有的极小项，此时无主合取范式或者说主合取范式为“空”。 （2）如果命题公式是永假公式它的主合取范式包含所有的极大项，此时无主析取范式或者说主析取范式为“空”。 （3）两个命题公式是相等的它们对应的主析取范式之间相等，或者(可兼或)它们对应的主合取范式之间相等。,,例3.5.7,求证(PQ)(PR)P(QR),证明 左式=(PQ)(PR)(PQ)(PR),=(PQ(RR)(P(QQ)R),=(PQR)(PQR)(PQR),=

[版权声明] 本站所有资料由用户提供并上传，若内容存在侵权，请联系邮箱。资料中的图片、字体、音乐等需版权方额外授权，请谨慎使用。网站中党政主题相关内容(国旗、国徽、党徽)仅限个人学习分享使用，禁止广告使用和商用。

电路中的基本元件是“门”，每种类型的门实现 一种逻辑运算，一种联结词可视为一种运算。 P ￢P 非门(反相器) P Q P∨Q 或门 P Q P∧Q 与门 或非门 P Q P↓Q 与非门 P Q P↑Q P Q P▽Q 不可兼或(异或门) 恰当选取各种门就能表示任一个逻辑表达式。 经过联结后的“门”图称为逻辑网络（组合网络）。 一个命题公式有多种等价表现形式，所以形成它的 逻辑网络也不同。设计时，考虑到简单和经济因素， 应尽可能选用较少的门，类型较单一的门来实现。 例6.3 某仓库的警报系统，只在保卫部门的一个 人工控制开关关闭时进行工作。当此人工控制开关 关闭时，如果通向设施范围内禁区的门有盗贼进入， 或者保卫人员还没有关闭专门开关时，设施的主要 入口就已打开，则报警器鸣响。设计此控制线路。 解：依据题意，报警器鸣响的条件： ①人工控制开关关闭 ② 通向设施范围内禁区的门有盗贼进入 保卫人员还没有关闭专门开关时，设施的主要 入口就已打开。 或者 对问题符号化 B：人工控制开关关闭。 C：设施的主要入口打开。 D：禁区的门有盗贼进入。 E: 关闭专门开关。 B∧(D∨(￢E∧C)) 设计此控制线路 令 A=B∧(D∨(￢E∧C))， B，C，D，E皆为输入信号，A为输出信号。 E C D B A 例6.4 某航空公司，为了保证安全，用三台计算机 同时复核飞行计划是否正确，根据计算机所给的答 案，按照少数服从多数的原则作出计划是否正确的 判断，试画出逻辑网络。 解：设P，Q，R分别表示三台计算机给出的判断结果（假设1为正确，0为不正确），C表示最终的判断结果，由题意可得真值表 P Q R C 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 定义7.1 E是若干个逻辑联结词的集合，如果任一 命题公式都可以由且仅由E中联结词构造的公式等价 表示，则称E是联结词功能完备集。 若E是联结词功能完备集，且删去E中任一个联结 词X后，至少有一个命题公式不能由E-{X}中联结词 构造的公式等价表示，则称E是一个最小联结词组 或功能完备集。 {￢ ，∧，∨} {￢ ，∧} {￢ ，∨} {↑}，{↓} 1.设p：星期六天气好，q：我去公园玩。将下列命题符号化。 （1）只要星期六天气好，我就去公园玩。? （2）只有星期六天气好，我才去公园玩。 （3）除非星期六天气好，否则我不去公园玩。 （1）p→q （2）q→p （3）q→p 设p： ???是无理数，q：北京比天津人口多，r：美国的首都是旧金山。求下列各公式的真值： ?（1）(p∨q)→r??????? ?