《命题逻辑及命题演算优秀课件.ppt》由会员分享，可在线阅读，更多相关《命题逻辑及命题演算优秀课件.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、命命题逻辑及命及命题演算演算第1页，本讲稿共52页概述和计算机科学联系概述和计算机科学联系 n和计算机科学联系紧密是计算机科学的支撑学科之一，也是信息科学的数学基础。在计算机理论研究及软硬件开发的各个领域都有广泛的应用。在计算机科学发展的过程中，各种理论问题的研究交错地使用着近代数学中的不同论题，这些论题构成了离散数学。第2页，本讲稿共52页学习离散数学的重要性学习离散数学的重要性第3页，本讲稿共52页一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现
2、在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来的呢？第4页，本讲稿共52页要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程：(1)什么是前提？有哪些前提？(2)结论是什么？(3)根据什
3、么进行推理？(4)怎么进行推理？第5页，本讲稿共52页二、命题与联结词二、命题与联结词1 引例：4是素数；是无理数；大于；大于吗？；请不要吸烟！第6页，本讲稿共52页定义：命题定义：命题-具有唯一真值的陈述句。具有唯一真值的陈述句。n例 我正在说假话；2009年的元旦是晴天。真命题-命题的判断结果为真。假命题-命题的判断结果为假。第7页，本讲稿共52页表示方法：命题（），真（1）假（0）。4是素数；是无理数等不能分解成更简单例的陈述句了，称此种命题为简单命题（原子命题）。否则，某命题是由简单命题通过联结词连接在否则，某命题是由简单命题通过联结词连接在一起的命题，称之为一起的命题，称之为复合命题
4、复合命题。第8页，本讲稿共52页例：2是偶数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。解：2是偶数；2是素数；4是素数；3是素数。非；且；或；如果则；当且仅当。第9页，本讲稿共52页ppF（0）T（1）T（1）F（0）“见假为真，见真为假见假为真，见真为假”p读作读作“并非并非p”或或“非非p”。(1)(1)(1)(1)否定式否定式否定式否定式：（negationnegation ）设设设设P P P P为一命题，为一命题，为一命题，为一命题，P P P P的否定的否定的否定的否定是一个新命题，记作是一个新命题，记作是一个新命题，记作是一个新命
5、题，记作“P”P”P”P”。若。若。若。若P P P P为为为为T T T T，P P P P为为为为F F F F；若若若若P P P P为为为为F F F F，P P P P为为为为T T T T。联结词。联结词。联结词。联结词“”表示自然语表示自然语言中的言中的“并非并非”（not not ）。）。三、联结词第10页，本讲稿共52页（2 2 2 2）合取式合取式：（conjunction conjunction）两个命题两个命题两个命题两个命题P P P P和和和和Q Q Q Q的的的的 合取是一个复合命题，记作合取是一个复合命题，记作合取是一个复合命题，记作合取是一个复合命题，记作P
6、P P PQ Q Q Q。当且仅当。当且仅当。当且仅当。当且仅当P P P P、Q Q Q Q同时为同时为同时为同时为T T T T时，时，时，时，P P P PQ Q Q Q 为为为为T T T T，其他情况下，其他情况下，其他情况下，其他情况下，P P P PQ Q Q Q 的真值都是的真值都是的真值都是的真值都是F F F F。合取联结词合取联结词“”“”表示自然语言表示自然语言 中的中的“并且并且”。pqp qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）F（0）F（0）F（0）T（1）p q读作读作“p并且并且q”或或“p且且q”见假为假，见假为假，全真为真。全真为
7、真。第11页，本讲稿共52页（3 3 3 3）析取析取析取析取式式：两个命题两个命题两个命题两个命题P P P P和和和和Q Q Q Q的析取是一个复合的析取是一个复合的析取是一个复合的析取是一个复合 命题，记作命题，记作命题，记作命题，记作P P P P Q Q Q Q。当且仅当。当且仅当。当且仅当。当且仅当P P P P、Q Q Q Q同时为同时为同时为同时为F F F F时，时，时，时，P P P P Q Q Q Q 为为为为F F F F，其他情况下，其他情况下，其他情况下，其他情况下，P P P P Q Q Q Q的真值都的真值都的真值都的真值都 是是是是T T T T。析。析。析。
8、析取联结词取联结词“”表示自然语言中的表示自然语言中的 “或或”（or or）。）。pqp qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）F（0）T（1）T（1）T（1）见真为真，见真为真，全假为假。全假为假。p q读作读作“p或者或者q”、“p或或q”。第12页，本讲稿共52页（4 4 4 4）蕴涵式蕴涵式蕴涵式蕴涵式：给定两个命题：给定两个命题：给定两个命题：给定两个命题P P P P和和和和Q Q Q Q，其条件命题，其条件命题，其条件命题，其条件命题是一个复合命题，记作是一个复合命题，记作是一个复合命题，记作是一个复合命题，记作P P P P Q Q Q Q。当且仅
9、当。当且仅当。当且仅当。当且仅当P P P P的真的真的真的真值为值为值为值为T T T T，Q Q Q Q的真值为的真值为的真值为的真值为F F F F时，时，时，时，P P P P Q Q Q Q 的真值为的真值为的真值为的真值为F F F F，其，其，其，其他情况下，他情况下，他情况下，他情况下，P P P P Q Q Q Q的真值都是的真值都是的真值都是的真值都是T T T T。条件。条件。条件。条件联结词联结词 “”表示自然语言中的表示自然语言中的“如果如果，那么，那么”。pqp qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）T（1）T（1）F（0）T（1）pq中
10、的中的p称为称为条件前件条件前件条件前件条件前件，q称为称为条件后件条件后件条件后件条件后件 前真后假为假，前真后假为假，其他为真。其他为真。第13页，本讲稿共52页（5）等价式等价式：给定两个命题给定两个命题给定两个命题给定两个命题P P和和和和QQ，其复合命，其复合命，其复合命，其复合命题题题题P P QQ称作双条件命题。当称作双条件命题。当称作双条件命题。当称作双条件命题。当P P和和和和QQ的真值相同时，的真值相同时，的真值相同时，的真值相同时，P P Q Q 的真值为的真值为的真值为的真值为T T，否则，否则，否则，否则，P P QQ的真值都是的真值都是的真值都是的真值都是F F。双
11、条件双条件双条件双条件联结词联结词“”表示自然语言中的表示自然语言中的“当且仅当当且仅当”。pqp qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）T（1）F（0）F（0）T（1）pq读读作作“p与与q互为条件互为条件”，“p当且仅当当且仅当q”。相同为真，相同为真，相异为假。相异为假。第14页，本讲稿共52页1-1.2 复合命题的符号化n复合命题的符号化的基本步骤1)找出各个原子命题，并逐个符号化；2)找出各个连接词，符号成相应联结词；3)用联结词将原子命题逐个联结起来；第15页，本讲稿共52页1-1.2 复合命题的符号化n例 将下列命题符号化(1)北京不是村庄P:表示“北
12、京是村庄”P:北京不是村庄(2)小王是游泳冠军和百米赛跑冠军P：小王是游泳冠军;Q：小王百米赛跑冠军PQ:小王是游泳冠军和百米赛跑冠军第16页，本讲稿共52页1-1.2 复合命题的符号化n例 将下列命题符号化(3)小明或者小华能解够出这道题P：小明能够解出这道题;Q：小华能够解出这道题PQ(4)小王或者小李中的一个能够当上班长P：小王能够当上班长;Q：小李能够当上班长(P)Q)(P(Q)第17页，本讲稿共52页1-1.2 复合命题的符号化n例 将下列命题符号化(5)今夜你若敢去公墓，那么我就咬掉我的鼻子或咬掉我的耳朵P：今夜你敢去公墓。Q：咬掉我的鼻子。R:咬掉我的耳朵 P(QR)第18页，本
13、讲稿共52页1-1.2 复合命题的符号化n例 将下列命题符号化(6)王乐是计算机系的学生，生于1980年或1981年,是三好学生。P：王乐是计算机系的学生。Q：生于1980年。R:生于1981年.S:是三好学生.P(QR)S第19页，本讲稿共52页四、命题公式及其赋值1.命题常项（命题常元）：简单命题2.命题变项（命题变元）3.合式公式（命题公式）：将命题变元用联合式公式（命题公式）：将命题变元用联结词或圆括号按一定的逻辑关系联结起来的符结词或圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式。（号串称为合式公式或命题公式。（A，B）第20页，本讲稿共52页定义：（1）单个命题变项可
14、被称为合式公式；（2）若是合式公式，则也是合式公式；（3）若是合式公式，则也是合式公式；（4）将1-3有限次的联结起来也是合式公式。注：合式公式的运算规则:例第21页，本讲稿共52页五、合式公式的真值引例：定义：设是出现在公式中的全部的命题变项，给各指定一个真值，称为对的一个赋值或解释。若指定的一组值使的真值为1，则称这组值为的成真赋值，若使的真值为0，则称这组值为的成假赋值。第22页，本讲稿共52页例：利用真值表求的成真赋值和成假赋值练习：（1）（2）（3）（2）若在它的各种赋值下取值为假，则称为矛盾式或永假式；定义：设为任一命题公式.(1)若在它的各种赋值下取值为真，则称为重言式或永真式；
15、（3）若不是矛盾式，则称为可满足式。第23页，本讲稿共52页第二章命题逻辑等值演算一、等值式引例：与定义：设是两个命题公式，若构成的等价式为重言式，则称是等值的，记作。第24页，本讲稿共52页练习：1）与2）与等值演算公式：双重否定律双重否定律:AA等幂律：等幂律：A AA,A AA交换律交换律:A BB A,A BB A结合律结合律:(A B)CA(B C)(A B)CA(B C)分配律分配律:A(B C)(A B)(A C)A(B C)(A B)(A C)第25页，本讲稿共52页德德摩根律摩根律 :(A B)AB (A B)AB吸收律吸收律:A(A B)A,A(A B)A零律零律:A 11
16、,A 00 同一律同一律:A 0A,A 1A排中律排中律:AA1矛盾律矛盾律:AA0第26页，本讲稿共52页蕴涵等值式蕴涵等值式:ABA B等价等值式等价等值式:AB(AB)(BA)假言易位假言易位:ABBA等价否定等值式等价否定等值式:ABAB归谬论归谬论:(AB)(AB)A注意注意:A,B,C代表任意的命题公式代表任意的命题公式第27页，本讲稿共52页等值演算的用途一：证明等值式。等值演算的用途一：证明等值式。例例1.10 验证验证 p(q r)(p q)r 右右 (p q)r 蕴涵等值式蕴涵等值式 p q r 德摩根律德摩根律 p (q r)结合律结合律 p (q r)蕴涵等值式蕴涵等值
17、式 p (q r)蕴涵等值式蕴涵等值式 注注:A B A B 练习：第28页，本讲稿共52页例 证明:p(q r)(p q)r 用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一 真值表法（自己证）方法二 观察赋值法.容易看出000,010等是左 边的成真赋值，是右边的成假赋值.方法三 用等值演算先化简两个公式，再观 察第29页，本讲稿共52页例例 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1)q(pq)解解 q(pq)q(p q)（蕴涵等值式）（蕴涵等值式）q(pq)（德摩根律）（德摩根律）p(qq)（交换律，结
18、合律）（交换律，结合律）p 0 （矛盾律）（矛盾律）0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知，该式为矛盾式.第30页，本讲稿共52页(2)(p q)(q p)解解 (p q)(q p)(p q)(q p)（蕴涵等值式）（蕴涵等值式）(p q)(p q)（交换律）（交换律）1由最后一步可知，该式为重言式由最后一步可知，该式为重言式.第31页，本讲稿共52页(3)(p q)(p q)r)解解 (p q)(p q)r)(p (q q)r （分配律）（分配律）p 1 r （排中律）（排中律）p r （同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式这不是矛盾式，也不是重
19、言式，而是非重言式的可满足式的可满足式.如如101是它的成真赋值是它的成真赋值,000是它是它的成假赋值的成假赋值.总结：总结：A A为矛盾式当且仅当为矛盾式当且仅当A A0 0 A A为重言式当且仅当为重言式当且仅当A A1 1说明：演算步骤不惟一说明：演算步骤不惟一,应尽量使演算短些应尽量使演算短些第32页，本讲稿共52页定义定义文字：命题变项及其否定统称为文字。文字：命题变项及其否定统称为文字。如：如：p ,q简单析取式：仅有有限个文字组成的析取式。简单析取式：仅有有限个文字组成的析取式。如：如：p ,q,p q,p q r简单合取式：仅有有限个文字组成的合取式。简单合取式：仅有有限个文
20、字组成的合取式。如：如：p ,q,p q,p q r二、析取范式与合取范式第33页，本讲稿共52页 命题公式是千变万化的，这给研究命题演算带来困难，这里我们命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这样命题演算研究如何由一个命题公式化归为一个标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问题，这种标准形式就叫的研究问题就归结为对标准形式的研究问题，这种标准形式就叫范式范式。析取范式析取范式 它是这样一种标准形式，在此式内不出现联结词它是这样一种标准形式，在此式内不出现联结词及及，否否定定符符号号只只出出现现在在命命题
21、题变变元元前前。它它是是一一个个析析取取式式，式式中中的的每每个个析析取取项是个合取式，每个合取式中只包含命题变元或命题变元的否定。项是个合取式，每个合取式中只包含命题变元或命题变元的否定。例如例如 p(p q)(q r)此式即具有析取范式之形式此式即具有析取范式之形式注意注意:一个公式的析取范式并不唯一，如一个公式的析取范式并不唯一，如p(r q),可以写成可以写成(p p)(r q)第34页，本讲稿共52页合取范式合取范式 它它是是这这样样一一种种标标准准形形式式，在在此此式式内内不不出出现现联联结结词词及及，否否定定符符号号只只出出现现在在命命题题变变元元前前。它它是是一一个个合合取取式
22、式，式式中中的的每每个个合合取取项项是是个个析析取取式式，每每个个析析取取式式中中只包含命题变元或命题变元的否定。只包含命题变元或命题变元的否定。例如例如 p(pq)(q r)此式即具有合取范式之形式此式即具有合取范式之形式注意注意:一个公式的合取范式并不唯一，一个公式的合取范式并不唯一，如如 p (r q)可以写成可以写成(p p)(r q)第35页，本讲稿共52页定义：定义：析取范式：析取范式：由有限个简单合取式构成的析取式。由有限个简单合取式构成的析取式。如：如：p q,(p q)(p q r)合取范式合取范式：由有限个简单析取式构成的合取式。：由有限个简单析取式构成的合取式。如：如：p
23、 q,（p q）（p qr）范式范式：析取范式与合取范式统称为范式。：析取范式与合取范式统称为范式。第36页，本讲稿共52页设设Ai(i=1,2,3,n)为简单合取式，则为简单合取式，则A=A1 A2 An 就是析取范式，就是析取范式，而而B=A1 A2 An 就是合取范式。就是合取范式。析取范式和合取范式有下列性质：析取范式和合取范式有下列性质：（1）一个析取范式是矛盾式）一个析取范式是矛盾式它的每个简单合它的每个简单合取式都是矛盾式。取式都是矛盾式。（2）一个合取范式是重言式）一个合取范式是重言式它的每个简单析它的每个简单析取式都是重言式。取式都是重言式。第37页，本讲稿共52页例例 求下
24、列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1)A=(pq)r解解 (pq)r (pq)r （消去（消去）pqr （结合律）（结合律）这这既既是是A的的析析取取范范式式（由由3个个简简单单合合取取式式组组成成的的析析取取式式），又是又是A的合取范式（由一个简单析取式组成的合取式）的合取范式（由一个简单析取式组成的合取式）第38页，本讲稿共52页(2)B=(pq)r解解 (pq)r (pq)r （消去第一个（消去第一个）(pq)r （消去第二个（消去第二个）(p q)r （否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单
25、合取式构成）继续：继续：(p q)r (p r)(q r)（对对 分配律）分配律）这一步得到合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成）第39页，本讲稿共52页求范式的具体步骤：求范式的具体步骤：（1）消去对）消去对 ,来说冗余的联结词来说冗余的联结词 ，即，即，。利用下列等值式：。利用下列等值式：A B(A B)A B(A B)(A B)第40页，本讲稿共52页（2）否定词的消去或内移。）否定词的消去或内移。利用下列等值式：利用下列等值式：A B(A B)(A B)A B (A B)A B（3）利用分配律：利用分配律：C(AB)（CA）（C B）C(AB)（CA
26、）（C B）第41页，本讲稿共52页(3)求求(p q)(p r)的析取范式。的析取范式。解：解：(p q)(p r)(p q)(p r)(p q)p)(p q)r)(p p)(q p)(p r)(qr)(q p)(p r)(q r)第42页，本讲稿共52页(4)求求(p q)(p r)的析取的析取/合取范式。合取范式。解解:(1)求求析取范式析取范式 (p q)(p r)(p q)(p r)p q(p r)第43页，本讲稿共52页(4)求求(p q)(p r)的析取的析取/合取范式。合取范式。解：解：(2)求求合取取范式合取取范式 (p q)(p r)(p q)(p r)(p r)(p q)
27、(p r)p)q (p p)(p r)q (p pq)(pr q)(合取范式合取范式)第44页，本讲稿共52页定义定义 在在含含有有n个个命命题题变变项项的的简简单单合合取取式式(简简单单析析取取式式)中中，若若每每个个命命题题变变项项均均以以文文字字的的形形式式在在其其中中出出现现且且仅仅出出现现一一次次，而而且且第第i（1 i n）个个文文字字出出现现在在左左起起第第i位位上上，称称这这样样的简单合取式（简单析取式）为的简单合取式（简单析取式）为 极小项（极大项）极小项（极大项）.第45页，本讲稿共52页由由p,q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 公式成真赋
28、值名称公式成假赋值名称p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M2M3 极小项极大项第46页，本讲稿共52页由由p,q,r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项 极小项极大项公式成真赋值名称公式成假赋值名称p q rp q rp q rp q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p
29、q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 第47页，本讲稿共52页 极小项与极大项关系极小项与极大项关系 设设mi和和Mi是命题变项是命题变项p1，p2，pn形成的形成的极小项和极大项，则极小项和极大项，则 mi Mi ，Mi mi定义定义设由设由n个命题变项构成的析（合）取范式中所个命题变项构成的析（合）取范式中所有的简单合（析）取式都是极小（大）项，有的简单合（析）取式都是极小（大）项，则称该析（合）取范式为主析（合）取范式。则称该析（合）取范式为主析（合）取范式。由不同最小项所组成的析
30、取式称为主析取范式由不同最小项所组成的析取式称为主析取范式由不同最大项所组成的合取式称为主合取范式由不同最大项所组成的合取式称为主合取范式第48页，本讲稿共52页 求求(p q)(p r)的主析取范式。的主析取范式。(p q)(p r)(q p)(p r)(q r)(析取范式析取范式)(pr)(q q)()(pq)(r r)(qr)(p p)(p qr)(p q r)(pq r)(pq r)(主析取范式主析取范式)m2 m3 m5 m7 第49页，本讲稿共52页用等值演算法求公式的主范式的步骤：用等值演算法求公式的主范式的步骤：(1)先求析取范式（合取范式）先求析取范式（合取范式）(2)将不是
31、极小项（极大项）的简单合取式将不是极小项（极大项）的简单合取式 （简单析取式）化成与之等值的若干个极小（简单析取式）化成与之等值的若干个极小 项的析取（极大项的合取），需要利用同一项的析取（极大项的合取），需要利用同一 律（零律）、排中律（矛盾律）、分配律、律（零律）、排中律（矛盾律）、分配律、幂等律等幂等律等.(3)极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，）表示，并按角标从小到大顺序排序并按角标从小到大顺序排序.第50页，本讲稿共52页例例 求求(p q)(p r)的主合取范式。的主合取范式。解法解法1：P q r p p q p r (p q)(p r)0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1第51页，本讲稿共52页解法解法2：(p q)(p r)(pq)(p r)(合取范式合取范式)(p q)(r r)(p r)(q q)(p q r)(p q r)(pq r)(p q r)(p q r)(p q r)(pq r)(p q r)(主合取范式主合取范式)M0 M1 M4 M6第52页，本讲稿共52页