《离散数学PowerPoint 演示文稿12》由会员分享，可在线阅读，更多相关《离散数学PowerPoint 演示文稿12（54页珍藏版）》请在金锄头文库上搜索。
1、 克拉玛依职业技术学院制作人:卢自娟2007年9月10日第一部分 数理逻辑l引言数理逻辑主要包括两部分的 内容,命题逻辑和一阶逻辑.命题逻 辑是研究由命题为基本单位构成的 前提和结论之间的可推导关系. 一 阶逻辑又称谓词逻辑.案例 :l 一个公安人员审查一件盗窃案,已 知下列事实: (1) 甲或乙盗窃了 DVD(2) 若甲盗窃了DVD,则作案时间不能发 生在午夜前;(3)若乙的证词正确,则午夜时灯光未灭;(4)若乙的证词不正确,则作案时间发生 在午夜前;(5)午夜时屋里灯灭了. 试问:盗窃DVD的是甲还是乙主要内容.1 命题与联结词.2 命题公式与赋值.3 等值演算.4 析取范式与合取范式.5
2、命题逻辑的推理理论1.1 命题与联结词l . 命题的概念l所谓命题，是指具有非真必假的陈述句。而 疑问句、祈使句和感叹句等因都不能判断其 真假，故都不是命题。命题仅有两种可能的 真值真和假，且二者只能居其一真用1或T 表示，假用0或F表示。由于命题只有两种真 值，所以称这种逻辑为二值逻辑。命题的真 值是具有客观性质的，而不是由人的主观决 定的。例1.1 判断下列句子中哪些是 命题.(1) 2是素数. (2) x+y9. (3) 太阳从西方升起.(4) 乌鸦是黑色的.(5) 这个男孩多勇敢啊!(6) 明年中秋节的晚上是晴天.(7) 您贵姓?(8) 请把门开开!(9) 地球外的星球上也有生物 l如
3、果一陈述句再也不能分解成更为简单 的语句，由它构成的命题称为原子命题.原子命题是命题逻辑的基本单位。l命题分为两类，第一类是原子命题，原 子命题用大写英文字母P，Q，R及其带下标的Pi，Qi，Ri，表示。例: p: 2是素数 ; q :乌鸦是黑色的.l第二类是复合命题，它由原子命题、命题联结词和圆括号组成。. 命题联结词l定义1.1 设P表示一个命题，由命题联 结词l和命题P连接成lP，称lP为P的 否定式复合命题， lP读“非P”。称l为 否定联结词 (否定联结词“l”的定义可由表 1.1.1表示之).l例: P: 10是素数 真值为F lp: 10不是素数 真值为T Q: 5是素数 真值为
4、T lQ 5不是素数 真值为F由于“否定”修改了命题，它是对单个命题进行操作，称它为一元联结词.l定义1.2 设P和Q为两个命题,由命题联结词将P和Q连接成PQ,称PQ为命题P和Q的合取式复合命题，PQ读做“P与Q” , 或“P且Q”。 称为合取联结词.自然语言中,既又,不但而 且 虽然但是 等都可以 符号化为 l例1.3 将下列命题符号化.(1)张路即聪明又用功.(2)张路不仅聪明,而且用功.(3)张路虽然不太聪明,但他很用功.(4)张路不是不聪明,而是不用功,解 设 P:张路聪明,Q:张路用功.则(1)到(4)分别符号化PQ， PQlPQ ， l（lP）lQl定义.1.3 设P和Q为两个命
5、题，由命题 联结词把 P 和Q连接成PQ，称PQ为命题P和 Q 的析取式复合命题，PQ读做“P或Q”。称为析取联结词。自然语言中的“或”有二义性，有时 具有相容性，有时具有排斥性，注 意区分l例1.3 将下列命题符号化(1)谢丹生于1972年或1973年.(2)吕小洲学过德语或法语(3)派老王或老李中的一人到上海开会.分析: 上述例题(1) (3)的或为排斥 或,而(2)中的或为可兼或.解 设：谢丹生于1972年S: 谢丹生于1973年 Q: 吕小洲学过德语 ：吕小洲学过法语 ：派老王到上海开会 ：派老李到上海开会 l 则: (1) 可符号化为RS ;(2)可符号化为QM ;(3)可符号化为(
6、NlH)(lNH)l定义1.1.4设P和 Q为两个命题 ，由 命题联结词把P 和Q 连接成 PQ， 称PQ为命题P和 Q的条件式复 合命 题 , 简称条件命题 PQ 读做 “P条件 Q”或者 “若P则Q”。 称为条件联结词或蕴涵联结词l自然语言中, “只要就”，“仅当 ”，“只有才” 等都可以符号化为PQ的形式l自然语言中, “如果则”中的与往往有某种内在的联系，而在数理逻辑中，与不一定有联系l在数学和其他自然科学中，“如果则”表示的前件为真，后件为真的推理关系，但数理逻辑中不同l例1. 将下列命题符号化(1)若3+3=6，则地球是运动的.(2)只要a是4的倍数,a就是2的倍数.(3) a是4
7、的倍数,仅当a是2的倍数(4)只有a是2的倍数, a才是4的倍数解 设：3+3=6 ：地球是运动的：a是4的倍数 ： a是2的倍数则 (1)可符号化为PQ(2)_ (4)可符号化为RSl定义.1.5 令P与Q是两个命题，由命题联结词把P和Q连接成P Q，称P Q为命题P和Q的双条件式复合命题， 简称双 条件命题， P Q读做“P当且仅当Q”，称为双条件联结词。l例1. 将下列命题符号化(1)2+3=5当且仅当是有理数；解 设：2+3=5：是有理数则(1)可符号化为P Q(2)A,B两角相等当且仅当他们是 同位角解 设：A,B两角相等：A,B是同位角则(2)可符号化为P Ql例1.6 将下列命题
8、符号化,并 求其真值(1) 如果是合数则是素数， 并且如果是素数，则它不能 被整除解 设:是合数 : 4是素 数， R: 4能被2正整除则(1) 符号化为 (PQ)(QR)因为(00)(01),其真值为1(2) 如果2+35当且仅当5是合数,则4和 7都是无理数解 设:2+35 : 5是合数， R: 4是无理数, S: 7是无理数 (2) 符号化为(P Q) (RS)因为把个自的真值代入上式得(0 0)(00)计算其真值为0l强调： 复合命题的真值只取决于各 原子命题的真值，而与它们 的内容、含义无关，与原子 命题之间是否有关系无关， 理解和掌握这一点是至关重 要的1. 命题公式与赋值. 命题
9、变元l在命题逻辑中，命题又有命题常 元和命题变元之分。一个确定的 具体的命题，称为命题常元；一 个不确定的泛指的任意命题，称 为命题变元。l命题变元不是命题，只有用一 个特定的命题取代才能确定它 的真值：真或假。这时也说对 该命题变元指派真值。l命题常元和命题变元均可用字 母P等表示。由于在命题逻辑中并不关心具体命题的涵义， 只关心其真值，因此，可以形 式地定义它们如下：l定义.以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。2.合式公式l通常把含有命题变元的断言称为命题公 式.但这没能指出命题公式的结构, 因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命
10、题公式。常使用归纳定义命题公式，以便构成的公式有规则可循。由这种规定产生的公式称为合式公式。l定义. 合式公式是由下列规则 生成的公式：单个命题变项(或常项)是合式公式。 若A是一个合式公式，则(lA)也是一 个合式公式。若A、B是合式公式,(AB)、(AB)、 (AB)和(A B)都是合式公式。只有有限次使用、和生成的公 式才是合式公式(也称公式)。l 符号集 运算优级：运算优级：高低l当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量可作以下约定：规定联结词的优先级由高到低的次序为： l、 相同的联结词按从左至右次序计算时，圆括号可省略。最外层的圆括号可以省略。3. 命题赋值
11、l定义.7 设 是出现在公式A中的全部命题变项,给 各指定一个真值, 称为对A的一个赋值或解释. 若指定的一组值使A的值为1,则称这组值为A的成真赋值.若使A的值为0,则称这组值为A的成假赋值.l定义1.8 对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。含n(n 1)个命题变项的公式 A共 有 个赋值.例1.7 求下列命题公式的真值表 (1) (plq)rpqr 1 0 1 0 1 0 1 00 0 0 0 1 1 1 1lqplq(plq)r0 0 1 1 0 0 1 11 10 0 1 1 0 01 10 0 0 00 001 1 1
12、1 11 1(2) (2) (p p(q(qp p) ) r rp q rqpp(qp)(p(qp) r0 0 1 0 0 00 1 10 1 01 0 11 0 0 1 1 11 1 0 0 0 1 1 1 1 1 11 1 1 1 1 1 1 11 1 1 1 1 1 1 1(3) l (pq) qr(记为A)p q r pq l (pq) l (pq) q A0 0 0 1 0 0 00 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 0 01 0 0 0 1 0 01 0 1 1 0 0 01 1 0 0 1 1 0 1 1 1 1 0 0 0定义1.9 设为一命题公式 l() 若在它的各种赋值下取值均为 真，则称为永真式（或重言式）；l() 若在它的各种赋值下取值均为 假，则称为永假式（或矛盾式）；l() 若不是永假式，则称是可满 足的；练习与作业l.求下列命题公式的真值表(1) l (qp) (2) lpq (3) l qlp思考：比较上述三题与 pq 真值表 l.将下列命题符号化(1)王威是100米冠军,又是200米冠军.(2)虽然天气很冷，老王还是来了(3)他一边吃
