命题逻辑及命题演算课件

《命题逻辑及命题演算课件》由会员分享，可在线阅读，更多相关《命题逻辑及命题演算课件（51页珍藏版）》请在金锄头文库上搜索。

1、概述和计算机科学联系,和计算机科学联系紧密 是计算机科学的支撑学科之一，也是信息科学的数学基础。 在计算机理论研究及软硬件开发的各个领域都有广泛的应用。 在计算机科学发展的过程中，各种理论问题的研究交错地使用着近代数学中的不同论题，这些论题构成了离散数学。,学习离散数学的重要性,一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是

2、什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来的呢？,要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程： (1) 什么是前提？有哪些前提？ (2) 结论是什么？ (3) 根据什么进行推理？ (4) 怎么进行推理？,二、命题与联结词,1 引例：,4是素数；,是无理数；,大于 ；,大于 吗？；,请不要吸烟！,定义

3、：命题-具有唯一真值的陈述句。,例 我正在说假话； 2009年的元旦是晴天。,表示方法：命题（ ），真（1） 假（0）。,否则，某命题是由简单命题通过联结词连接在 一起的命题，称之为复合命题。,非 ； 且 ； 或 ；如果 则 ； 当且仅当 。,“见假为真，见真为假” p读作“并非p”或“非p”。,（2）合取式：（ conjunction ）两个命题P和Q的 合取是一个复合命题，记作PQ。当且仅当P、 Q同时为T时， PQ 为T，其他情况下， PQ 的真值都是F。合取联结词“”表示自然语言 中的 “并且” 。,pq读作“p并且q”或“p且q”,见假为假，全真为真。,（3）析取式：两个命题P和Q的

4、析取是一个复合 命题，记作P Q。当且仅当P、Q同时为F时， P Q 为F，其他情况下， P Q的真值都 是T。析取联结词 “ ”表示自然语言中的 “ 或”（or ）。,见真为真，全假为假。,pq读作“p或者q”、“p或q”。,（4）蕴涵式：给定两个命题P和Q，其条件命题 是一个复合命题，记作P Q。当且仅当P的真 值为T，Q的真值为F时， P Q 的真值为F，其 他情况下， P Q的真值都是T。条件联结词 “ ”表示自然语言中的“如果，那么”。,pq中的p称为条件前件，q称为条件后件,前真后假为假，其他为真。,（5）等价式：给定两个命题P和Q，其复合命 题P Q称作双条件命题。当P和Q的真值

5、相同时， P Q 的真值为T，否则， P Q的真值都是F。 双条件联结词 “ ”表示自然语言中的“当且仅当”。,pq读作“p与q互为条件”，“p当且仅当q”。,相同为真，相异为假。,1-1.2 复合命题的符号化,复合命题的符号化的基本步骤 1) 找出各个原子命题，并逐个符号化； 2) 找出各个连接词，符号成相应联结词； 3) 用联结词将原子命题逐个联结起来；,1-1.2 复合命题的符号化,例 将下列命题符号化 (1)北京不是村庄 P: 表示“北京是村庄” P:北京不是村庄 (2)小王是游泳冠军和百米赛跑冠军 P：小王是游泳冠军; Q：小王百米赛跑冠军 PQ: 小王是游泳冠军和百米赛跑冠军,1-

6、1.2 复合命题的符号化,例 将下列命题符号化 (3)小明或者小华能解够出这道题 P：小明能够解出这道题; Q：小华能够解出这道题 PQ (4)小王或者小李中的一个能够当上班长 P：小王能够当上班长; Q：小李能够当上班长,1-1.2 复合命题的符号化,例 将下列命题符号化 (5) 今夜你若敢去公墓，那么我就咬掉我的鼻子或咬掉我的耳朵 P：今夜你敢去公墓。 Q：咬掉我的鼻子。 R: 咬掉我的耳朵,P (QR),1-1.2 复合命题的符号化,例 将下列命题符号化 (6) 王乐是计算机系的学生，生于1980年或1981年,是三好学生。 P：王乐是计算机系的学生。 Q：生于1980年。 R: 生于1

7、981年. S: 是三好学生.,P(QR)S,四、命题公式及其赋值,2.命题变项（命题变元）,3.合式公式（命题公式）：将命题变元用联 结词或圆括号按一定的逻辑关系联结起来的符 号串称为合式公式或命题公式。（A，B）,定义： （1）单个命题变项可被称为合式公式； （2）若 是合式公式，则 也是合式公式； （3）若 是合式公式，则 也是合式公式； （4）将1-3有限次的联结起来也是合式公式。,定义：设 是出现在公式 中的全 部的命题变项，给 各指定一个真值 ，称为对 的一个赋值或解释。若指定的一组 值使 的真值为1，则称这组值为 的成真赋 值，若使 的真值为0，则称这组值为 的成 假赋值。,例：

8、利用真值表求 的成真赋值和成假赋值,练习：（1） （2） （3）,（2）若 在它的各种赋值下取值为假，则称 为矛盾式或永假式；,定义：设 为任一命题公式. (1)若 在它的各种赋值下取值为真，则称 为重言式或永真式；,（3）若 不是矛盾式，则称 为可满足式。,第二章 命题逻辑等值演算,一、等值式,引例：,与,定义：设 是两个命题公式，若 构成 的等价式 为重言式，则称 是等值的，记 作 。,练习：1） 与,2） 与,等值演算公式：,双重否定律 : AA 等幂律： AAA, AAA 交换律: ABBA, ABBA 结合律: (AB)CA(BC) (AB)CA(BC) 分配律: A(BC)(AB)

9、(AC) A(BC) (AB)(AC),德摩根律 : (AB)AB (AB)AB 吸收律: A(AB)A, A(AB)A 零律: A11, A00 同一律: A0A, A1A 排中律: AA1 矛盾律: AA0,蕴涵等值式: ABAB 等价等值式: AB(AB)(BA) 假言易位: ABBA 等价否定等值式: ABAB 归谬论: (AB)(AB) A 注意: A,B,C代表任意的命题公式,等值演算的用途一：证明等值式。 例1.10 验证 p( q r) (p q) r 右 (p q) r 蕴涵等值式 p q r 德摩根律 p ( q r) 结合律 p ( q r) 蕴涵等值式 p ( q r)

10、 蕴涵等值式 注:A B AB,练习：,例 证明: p (q r) (p q) r 用等值演算不能直接证明两个公式不等值,证 明两个公式不等值的基本思想是找到一个赋值 使一个成真,另一个成假. 方法一 真值表法（自己证） 方法二 观察赋值法. 容易看出000, 010等是左 边的成真赋值，是右边的成假赋值. 方法三 用等值演算先化简两个公式，再观 察,例 用等值演算法判断下列公式的类型 (1) q(pq) 解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 由最后一步可知，该式为矛盾式.,(2) (p q )(q

11、 p) 解 (p q) (q p) (p q) ( q p) （蕴涵等值式） (p q )(p q) （交换律） 1 由最后一步可知，该式为重言式.,(3) (p q) (p q )r) 解 (p q) (p q )r) (p (q q )r （分配律） p1r （排中律） p r （同一律） 这不是矛盾式，也不是重言式，而是非重言式 的可满足式.如101是它的成真赋值,000是它 的成假赋值.,总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1 说明：演算步骤不惟一,应尽量使演算短些,定义 文字：命题变项及其否定统称为文字。 如：p , q 简单析取式：仅有有限个文字组成的析取式。 如：p

12、 , q , p q , p q r 简单合取式：仅有有限个文字组成的合取式。 如：p , q , p q , p q r,二、析取范式与合取范式,命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问题，这种标准形式就叫范式。 析取范式 它是这样一种标准形式，在此式内不出现联结词 及，否定符号只出现在命题变元前。它是一个析取式，式中的每个析取项是个合取式，每个合取式中只包含命题变元或命题变元的否定。 例如 p (p q) (q r) 此式即具有析取范式之形式 注意:一个公式的析取范式并不唯一，如

13、p (rq) ,可以写成(p p )(rq),合取范式 它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个合取式，式中的每个合取项是个析取式，每个析取式中只包含命题变元或命题变元的否定。 例如 p (pq) (q r) 此式即具有合取范式之形式 注意:一个公式的合取范式并不唯一， 如 p (r q) 可以写成(p p) (r q),定义： 析取范式：由有限个简单合取式构成的析取式。 如：p q , (p q) (p q r) 合取范式：由有限个简单析取式构成的合取式。 如：p q ,（p q）（ p qr） 范式：析取范式与合取范式统称为范式。,设Ai(i=1,

14、2,3,n)为简单合取式，则 A=A1 A2 An 就是析取范式， 而B=A1 A2 An 就是合取范式。 析取范式和合取范式有下列性质： （1）一个析取范式是矛盾式它的每个简单合 取式都是矛盾式。 （2）一个合取范式是重言式它的每个简单析 取式都是重言式。,例 求下列公式的析取范式与合取范式 (1) A=(pq)r 解 (pq)r (pq)r （消去） pqr （结合律） 这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）,(2) B=(pq)r 解 (pq)r (pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定号内移

15、德摩根律） 这一步已为析取范式（两个简单合取式构成） 继续： (pq)r (pr)(qr) （对分配律） 这一步得到合取范式（由两个简单析取式构成）,求范式的具体步骤： （1）消去对 ,来说冗余的联结词 ，即， 。利用下列等值式： A B ( A B) A B ( A B) (A B),（2）否定词的消去或内移。 利用下列等值式： A B ( A B) ( A B) A B ( A B) A B （3）利用分配律： C ( AB) （CA）（C B） C ( AB ) （CA）（C B）,(3) 求(p q)(p r)的析取范式。 解：(p q) (p r) (p q) ( p r) (p q) p) (p q) r) (pp)(q p)(p r)(qr) (q p)(p r)(q r),(4) 求(p q)(pr)的析取/合取范式。 解: (1) 求析取范式 (p q) (p r) (p q) ( p r ) p q ( p r ),(4) 求(p q)(pr)的析取/合取范式。 解：(2) 求合取取范式 (p q) (p r) (p q) ( p r ) (