离散数学-命题逻辑.ppt

1,离散数学课程学时：48讲 授：杨绍禹,2,课程性质,离散数学（又称计算机数学）是现代数学的重要分支，是计算机专业核心基础课程之一。,3,课程目标,离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。,4,与其他课程的关系,离散数学与计算机科学的其他课程,如：数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、容错技术、人工智能等有密切的联系。它是这些课程的先导和基础课程。,5,离散数学高等教育出版社,2008屈婉玲著Discrete Mathematics and Its Applications 6th Edition Kenneth H Rosen,教材与参考书,6,课程内容,本课程根据大纲的内容和相关独立性，可分为四大部分 第一部分 数理逻辑 包括命题逻辑;谓词逻辑 第二部分 集合论 包括集合与关系;函数,7,课程内容,第三部分 代数系统 包括代数结构;格与布尔代数第四部分 图论,8,学习方法,课程特点：定义、定理多 本课内容定义定理习题为了学好这门课，要求：（）弄懂定义、定理，弄懂例题，加深对定义、定理的理解；（）在复习基础上，做好课外作业。同学之间可以讨论，弄懂弄通。（3）做好课堂笔记。（4）结合专业实践，做到融会贯通。,9,学习建议,平时考勤 20%平时作业 20%期末考试 60%,考核方式,课前预习+课上笔记+课下习题+经典文献阅读,10,第一篇 数理逻辑,数理逻辑是用数学语言表述的推理形式有效性的学问。命题逻辑、谓词逻辑数理逻辑使用特制的表意符号，亦称为符号逻辑。逻辑研究对象逻辑真值真，表示为T或1假，表示为F或0正确的推理形式正确前提正确的推理形式必然得出正确的结论,第一章 命题逻辑 1.1 命题与联接词,什么是命题？命题的运算符是什么？如何表示命题？有多少种命题的运算符？,语句表达,陈述句疑问句祈使句感叹句,雪是白的。2是奇数。X+Y5。你是谁？我正在说谎。北京是中国的首都。前进！天空多漂亮!,特点：有的语句可以判断真假。,自然语言、命题,语言是人们思维和交际的工具，也是一种表达观念的符号系统。自然语言由各种句式组成，如陈述句、疑问句、感叹句、祈使句等等。陈述句是陈述一个事实或者说话人的看法，它包括肯定句和否定句两种。一般来说，仅有陈述句能够确定句子的意义是真还是假。命题表达为具有确定真假意义的陈述句。,命题示例,雪是白的。2是奇数。X+Y5。你是谁？我正在说谎。北京是中国的首都。每个不小于6的偶数都是两个奇素数之和（歌德巴赫猜想）21世纪有人住在月球上。他很高。一个自然数不是合数就是素数,命题，真 命题，假不确定，非命题疑问句，非命题悖论，非命题命题，真命题，真，有唯一真假值。命题，假，有唯一真假值。无法确定，非命题命题，假，1不是合数和素数,命题的抽象表示,自然语言具有二义性 比如：郑州市长远规划出来了命题逻辑不关注语句的内容，也不关注语句为何是真或为假，而是仅仅关注语句能够为真或假。命题的抽象用小写字母表示命题，取值为0,1。命题真值陈述句的意义为真，称为真命题，真值为1或T。陈述句的意义为假，称为假命题，真值为0或F。命题逻辑的研究对象命题。数理逻辑从形式结构方面研究命题。,自然语言复杂语句构造,简单语句+联接词（连词、介词）=复杂语句,语句联接词并且或否定如果,则。当且仅当既不，也不。,运算思维,简单命题与复合命题,简单命题由简单陈述句表述的命题称为简单命题。命题逻辑不再进一步分析简单命题的内部结构p:孔子是圣人,语句联接词并且或否定如果,则。当且仅当既不，也不。,复合命题用联接词可以将若干个简单句组合成复合句。子命题,命题逻辑如何运算？,数计算启示自然数运算：+、*整数运算：+、-、*有理数运算：+、-、*、/,命题逻辑真1，假0运算：？,逻辑联结词,定义0和1称为0元函数。设n0,称为0,1n到0,1的函数为n元函数，真值函数也称为联结词。命题的操作符（联结词）非 与 或 如果,则。当且仅当 异或,真值表真值形式可以用图表来说明。这种表称为真值图表。,0元函数0，11元函数2元函数、,逻辑联结词,命题p的否定记为p,读作非p,真值表,逻辑联接词的含义自然语言中，并非的含义举例：每一种生物均是动物。F：有一些生物不是动物。T 这里不能讲成“每一种生物都不是动物”。,逻辑联结词,真值表,pq称为p和q的合取读作p且q,逻辑联接词的含义自然语言中，并且的含义都真(p:1)才真(q:1),22,举例：(1)p：王华的成绩很好 q：王华的品德很好。则pq：王华的成绩很好并且品德很好。(2)p：我们去种树 q：房间里有一台电视机 则pq：我们去种树与房间里有一台电视机。(3)p：今天下大雨 q：3+3=6 则pq：今天下大雨和3+3=6由例(2)(3)可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。,逻辑联结词,逻辑联结词,真值表,pq称为p和q的析取，读作p或q,逻辑联接词的含义自然语言中，或的含义都假(p:0)才假(q:0)举例：今天晴天或者下雨,逻辑联结词,真值表,逻辑联接词的含义自然语言中，如果,则.的含义真(1)假(0)才假(0),pq称为p蕴涵q读作p则qp称为前件q称为后件,25,举例：(1)p：我拿起一本书 q：我一口气读完了这本书 pq：如果我拿起一本书，则我一口气 读完了这本书。(2)p：Alice当选总统 q：Alice减税 pq：如果Alice当选总统，那么Alice将减税(3)p：今天打雷了 q：1+1=2 pq：如果今天打雷，那么1+1=2,逻辑联结词,逻辑联结词,真值表,p q称为p与q等值，读作p当且仅当q,p与q互蕴含。pq=(pq)(qp),逻辑联接词的含义自然语言中，当且仅当的含义相同才1，不同则0,逻辑联结词,举例设：ABC是等腰三角形：ABC有两只角相等：ABC是等腰三角形当且仅当 有两只角相等。,逻辑联结词,Alice是男孩或女孩。（不可兼或）比较李明学习英语或学习法语。(可兼或),真值表,p q称为p与q异或（不可兼或），读作p异或q。pq=(pq)(qp)不同才1，相同则0,29,区分“可兼或”与“不可兼或”,“可兼或”即p或q为“T”时（pq）为“T”，是析取。例如：灯泡有故障或开关有故障。今晚写字或看书。今天下雨或打雷。以上例句均为“可兼或”。,30,“不可兼或”即p和q的真值不同时，p q为T。（异或用“”表示）不是析取。,区分“可兼或”与“不可兼或”,例：Alice通过电视看杂技或到剧场看杂技。Alice乘火车去北京或乘飞机去北京。以上两句均为“不可兼或”。,31,命题联结词在使用中的优先级,（）先括号内，后括号外（）运算时联结词的优先次序为：（由高到低）（）联结词按从左到右的次序进行运算（）最外层的括号一律均可省去（pqr）可写成pqr,32,命题联结词注意事项,（1）五个联结词的含义与日常生活中的联结词 的含义大致相同。（2）“或”可分为可兼或（）和异或（）（不可兼或）（3）“”为一元运算，其余四个均为二元运算。（4）“”分为形式条件和实质条件命题，当前件为“”时，不论后件怎样，则单条件命题的真值均为“”。（5）命题联结词是命题或命题之间的联结词，而 不是名词之间、数字之间和动词之间的联结词。,33,命题符号化,以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。步骤如下：找出各简单命题，分别符号化。找出各联结词，把简单命题逐个联结起来。,34,命题符号化,例.将下列命题符号化：（1）李明是计算机系的学生，他住在312室或 313室（2）张三和李四是朋友。（3）虽然交通堵塞，但是老王还是准时到达了车站。（4）只有一个角是直角的三角形才是直角三角形。（5）老王或小李中有一个去上海出差。（6）除非今天下雨，否则我去踢球。（7）只要今天下雨，我就不去踢球。（8）只有今天不下雨，我才去踢球。,35,命题符号化,约定：（）我们只注意命题的真假值，而不再去注意命题的汉语意义。（）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。,36,1.2 命题公式,命题公式命题常元：表示确定的命题T，F。命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母表示。命题公式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。,37,命题公式构造法则,定义命题公式(wff)可按下述法则来生成：）单个的命题变元是一个命题公式。）若是命题公式，也为命题公式。）若、是命题公式，则（）、（）、（）、（）均为命题公式。）当且仅当有限次使用（）（）（）所得到的包含有命题变元和命题常元，联结词，括号的符号串才是命题公式。,38,命题公式的真值表,例如：(PQ)，(P(QR)，(PQ)R)，P都是命题公式。而(P)，(P)都不是命题公式命题公式的真值表:命题变元用特定的命题来取代，这一过程称为对该命题变元进行真值指派。命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。写成(x),39,命题公式的真值表,例如：公式 P(Q R)定义三元函数 Y(P，Q，R)P(Q R)定义命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表。,40,命题公式真值表构造方法,构造真值表的步骤如下：1)找出给定命题公式中所有的命题变元，列 出所有可能的赋值。2)按照从高到低顺序写出命题公式的各层次。3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。,41,命题公式真值表构造方法,例构造命题公式（）R）的真值表,例2构造命题公式P(PQ)的真值表,例3构造命题公式(PQ)Q 的真值表,个命题变元有组真值指派；个命题变元有23 组真值指派，个则有个2n个真值指派。,42,命题公式的永真式、永假式和可满足式,定义设公式中有n个不同的原子变元 p1,pn,(n为正整数)。该变元组的任意一组确定的值（u1,un）称为关于p1,pn的一个完全指派，其中ui或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式的关于该变元组的部分指派。定义使公式取真的指派称为成真指派。,43,命题公式的永真式、永假式和可满足式,定义如果一个命题公式的所有完全指派均为成真指派，则该公式称为永真式。如果一个命题公式的所有完全指派均为成假指派，则该公式称为永假式。不是永假式的公式，则称此命题公式是可满足式。讨论：（）永真式的否定为永假式（）；永假式的否定为永真式（）。（）二个永真式的析取、合取、蕴含、等价 均为永真式。,第二章 命题逻辑等值演算 2.1 等值式,有哪些基本的等值式？如何进行等值演算？析取范式与合取范式，主析取范式与主合取范式的求解什么是联结词完备集？,45,2.1 等值式,定义2.1 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式几点说明：定义中，A,B,均为元语言符号 A或B中可能有哑元出现.例如(pq)(pq)(rr)r为左边公式的哑元.用真值表可检查两个公式是否等值请验证：p(qr)(pq)r p(qr)不与(pq)r 等值,46,等值式例题,例1 判断下列各组公式是否等值:(1)p(qr)与(pq)r,结论:p(qr)(pq)r,47,等值式例题,(2)p(qr)与(pq)r,结论:p(qr)与(pq)r 不等值,48,基本等值式,双重否定律 AA幂等律 AAA,AAA交换律 ABBA,ABBA结合律(AB)CA(BC),(AB)CA(BC)分配律 A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律(AB)AB(AB)AB吸收律 A(AB)A,A(AB)A,49,基本等值式,零律 A11,A00同一律 A0A.A1A排中律 AA1矛盾律 AA0蕴涵等值式 ABAB等价等值式 AB(AB)(BA)假言易位 ABBA等价否定等值式 ABAB归谬论(AB)(AB)A特别提示：必须牢记这16组等值式，这是继续学习的基础,50,等值演算与置换规则,1.等值演算由已知的等值式推演出新的等值式的过程2.等值演算的基础：(1)等值关系的性质：自反性、对称性、传递性(2)基本的等值式(3)置换规则（见3）3.置换规则 设(A)是含公式 A 的命题公式，(B)是用公式 B 置换(A)中所有的 A 后得到的命题公式 若 BA，则(B)(A),51,等值演算的应用举例,证明两个公式等值例2 证明 p(qr)(pq)r,证 p(qr)p(qr)（蕴涵等值式，置换规则）(pq)r（结合律，置换规则）(pq)r（德摩根律，置换规则）(pq)r（蕴涵等值式，置换规则）今后在注明中省去置换规则注意：用等值演算不能直接证明两个公式不等值,52,证明两个公式不等值例3 证明 p(qr)与(pq)r 不等值,等值演算的应用举例,证 方法一:真值表法,见例1(2)方法二:观察法.观察到000,010是左边的成真赋值，是右边的成假赋值 方法三:先用等值演算化简公式，然后再观察 p(qr)pqr(pq)r(pq)r(pq)r 更容易看出前面的两个赋值分别是左边的成真赋 值和右边的成假赋值,53,判断公式类型:A为矛盾式当且仅当A 0 A为重言式当且仅当A 1例4 用等值演算法判断下列公式的类型(1)q(pq)(2)(pq)(qp)(3)(pq)(pq)r),等值演算的应用举例,解(1)q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）矛盾式,54,判断公式类型,(2)(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1重言式,(3)(pq)(pq)r)(p(qq)r（分配律）p1r（排中律）pr（同一律）可满足式，101和111是成真赋值，000和010等是成假赋值.,55,2.2 析取范式与合取范式,基本概念(1)文字命题变项及其否定的总称(2)简单析取式有限个文字构成的析取式 p,q,pq,pqr,(3)简单合取式有限个文字构成的合取式 p,q,pq,pqr,(4)析取范式由有限个简单合取式组成的析取式 p,pq,pq,(pq)(pqr)(qr)(5)合取范式由有限个简单析取式组成的合取式 p,pq,pq,(pqp(pqr)(6)范式析取范式与合取范式的总称,56,范式的性质,定理2.1(1)一个简单析取式是重言式当且仅当它同时含有某个命题变项和它的否定式.(2)一个简单合取式是矛盾式当且仅当它同时含有某个命题变项和它的否定式.定理2.2(1)一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式.(2)一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.,57,命题公式的范式,定理2.3（范式存在定理）任何命题公式都存在与之等值的析取范式与合取范式公式A的析取(合取)范式与A等值的析取(合取)范式求公式A的范式的步骤：(1)消去A中的,（若存在）ABAB AB(AB)(AB)(2)否定联结词的内移或消去 A A(AB)AB(AB)AB,58,命题公式的范式,(3)使用分配律 A(BC)(AB)(AC)求合取范式 A(BC)(AB)(AC)求析取范式公式范式的不足不惟一,59,求公式的范式,例5 求下列公式的析取范式与合取范式(1)(pq)r(2)(pq)r解(1)(pq)r(pq)r（消去）pqr（结合律）(2)(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移德摩根律)析取范式(pr)(qr)（对分配律）合取范式,60,极小项与极大项,61,实例,由两个命题变项 p,q 形成的极小项与极大项,62,实例,由三个命题变项 p,q,r 形成的极小项与极大项.,mi与Mi的关系：mi Mi,Mi mi,63,主析取范式与主合取范式,主析取范式由极小项构成的析取范式主合取范式由极大项构成的合取范式例如，n=3,命题变项为 p,q,r 时，(pqr)(pqr)m1m3 主析取范式(pqr)(pqr)M1M7主合取范式定理2.5(主范式的存在惟一定理)任何命题公式都存在与之等值的主析取范式和主合取范式,并且是惟一的,需要说明,求任何一个公式的主析取范式和主合取范式不仅要取决于该公式，而且取决于该公式所包含的命题变元。,如公式：G1(P,Q)=(PQ)Q，G2(P,Q,R)=(PQ)Q。前者是依赖于两个命题变元的，后者应依赖于三个命题变元。,求主析取范式和主合取范式的方法,主范式,求公式A的主析取范式的方法与步骤,方法一、等值演算法(1)化归为析取范式。(2)除去析取范式中所有永假的析取项。(3)将析取式中重复出现的合取项和相同的变元合并。(4)对合取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。方法二、真值表法(1)写出A的真值表。(2)找出A的成真赋值。(3)求出每个成真赋值对应的极小项（用名称表示），按角标从小到大顺序析取。,(1)等值推演法求主析取范式(pq)r(pqr)(pr)(qr)pqr m4pr p（qq）r(pqr)(pqr)m1m3 qr(pp)qr(pqr)(pqr)m3m7(pq)r m1m3m4m7,实例,68,实例,(2)真值表法求(pq)r的主析取范式。解 首先列出其真值表,69,实例,将公式的真值进行分解，分解成一些子公式，该子公式仅有一组解释使其真值为真，此时的每一个子公式都对应了一个极小项。,将极小项全部进行析取后，可得到相应的主析取范式：(pq)r=(pqr)(pqr)(pqr)(pqr),求公式A的主合取范式的方法与步骤,方法一、等值演算法(1)化归为合取范式。(2)除去合取范式中所有永真的合取项。(3)将合取式中重复出现的析取项和相同的变元合并。(4)对析取项补入没有出现的命题变元，即添加如(pp)式，然后应用分配律展开公式。方法二、真值表法(1)写出A的真值表。(2)找出A的成假赋值。(3)求出每个成假赋值对应的极大项（用名称表示），按角标从小到大顺序合取。,(1)等值推演法求主合取范式(pq)r(pr)(qr)(pqr)pqr M5 pr p(qq)r(pqr)(pqr)M0M2 qr(pp)qr(pqr)(pqr)M2M6(pq)r M0M2M5M6,实例,72,实例,(2)真值表法求(pq)r的主合取范式。解 首先列出其真值表,73,实例,将公式的真值进行分解，分解成一些子公式，该子公式仅有一组解释使其真值为假，此时的每一个子公式都对应了一个极大项,将极大项全部进行析取后，可得到相应的主合取范式：(PQ)R=(PQR)(PQR)(PQR)(PQR),74,真值表技术,利用真值表技术求主析取范式和主合取范式的简要方法：从真值表知，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个成真解释所对应的极小项，将这些极小项的析取即可得到相应的主析取范式。从真值表知，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个成假解释所对应的极大项，将这些极大项的合取即可得到相应的主合取范式。从真值表按所给的算法求出主范式的方法，称为真值表技术（Technique of Truth Table）。,75,Try 1 Try,设G=(pq)r，求出它的主析取范式和主合取范式。（分别用等值推演和真值表法）,76,主范式的应用,1.求公式的成真成假赋值 设公式A含n个命题变项,A的主析取范式有s个极小项,则A 有s个成真赋值,它们是极小项下标的二进制表示,其余2n-s 个赋值都是成假赋值 例如(pq)r m1m3m5 m6m7成真赋值为 001,011,101,110,111，成假赋值为 000,010,100.类似地，由主合取范式也立即求出成假赋值和成真赋值.,77,2.判断公式的类型 设A含n个命题变项.A为重言式 A的主析取范式含全部2n个极小项 A的主合取范式不含任何极大项,记为1.A为矛盾式 A的主合析取范式含全部2n个极大项 A的主析取范式不含任何极小项,记为0.A为非重言式的可满足式 A的主析取范式中至少含一个、但不是全 部极小项 A的主合取范式中至少含一个、但不是全 部极大项.,主范式的应用,78,例7 用主析取范式判断公式的类型:(1)A(pq)q(2)B p(pq)(3)C(pq)r解(1)A(pq)q(pq)q 0 矛盾式(2)B p(pq)1 m0m1m2m3 重言式(3)C(pq)r(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m3 m5m7 非重言式的可满足式,主范式的应用,79,3.判断两个公式是否等值例8 用主析取范式判以下每一组公式是否等值 p(qr)与(pq)r p(qr)与(pq)r解 p(qr)=m0m1m2m3 m4m5 m7(pq)r=m0m1m2m3 m4m5 m7(pq)r=m1m3 m4m5 m7显见，中的两公式等值，而的不等值.,主范式的应用,80,4.解实际问题例9 某单位要从A,B,C三人中选派若干人出国考察,需满足下述条件:(1)若A去,则C必须去;(2)若B去,则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案?解 记 p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真赋值 A=(pr)(qr)(pq)(pq),主范式的应用,81,求A的主析取范式 A=(pr)(qr)(pq)(pq)(pr)(qr)(pq)(pq)(pq)(pr)(rq)(rr)(pq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pq)(pq)(pr)(pq)(rq)(pq)(pqr)(pqr)成真赋值:101,010结论:方案1 派A与C去,方案2 派B去,主范式的应用,82,2.3 联结词的完备集,定义:0,1上的n元函数 f:0,1n 0,1 就称为一个n元真值函数（布尔函数）自变量有2n组不同的取值，真值函数取值只有两种：1 0,共有 种不同的真值函数,83,2.3 联结词的完备集,每个（二元）联结词确定了一个（二元）真值函数。每个（二元）真值函数也确定了一个（二元）联结词。二元联结词总共可以有2416个,84,2.3 联结词的完备集,85,真值函数,2元真值函数,86,二元联结词总共可以有2416个,所有可能的联结词,87,其他联结词,不可兼或,蕴涵否定,与非,或非,c,c,c,88,问题,常用五个联结词，是否有冗余呢？,ABAB,AB(AB)(B A),89,联结词完备集（Functionally Complete）,设S是联结词的一个集合，称C为联结词的一个完备集，如果任一个命题公式都能够逻辑等值于仅包含S中联结词的公式。最（极）小完备联结词集：若一个完备集的任何真子集都不是完备集(最小联结词组)。,90,联结词完备集举例,，是完备集，是完备集 pq(pq)(qp)pqpq，和，是否是完备集?pq(pq)pq(pq),91,联结词完备集举例续1,，是否是完备集？pq pq，是否是完备集？可以证明任何一个仅含“”和“”的二元命题合式公式真值中有1和0 的个数都是偶数的。不是,92,联结词完备集举例续3,是否是完备集？pq(pq)ppp同理：也是完备集 pq(pq)ppp,93,2.4 可满足性问题与消解法,不含任何文字的简单析取式称作空简单析取式,记作。规定是不可满足的.约定:简单析取式不同时含某个命题变项和它的否定S:合取范式,C:简单析取式,l:文字,:赋值,带下角标或 文字l的补lc:若l=p,则lc=p;若l=p,则lc=p.SS:S是可满足的当且仅当S 是可满足的定义2.9 设C1=lC1,C2=lcC2,C1和C2不含l和lc,称C1C2为C1和C2(以l和lc为消解文字)的消解式或消解结果,记作Res(C1,C2)例如,Res(pqr,pqs)=qrs,94,消解规则,定理2.8 C1C2Res(C1,C2)证:记C=Res(C1,C2)=C1C2,其中l和lc为消解文字,C1=lC1,C2=lcC2,且C1和C2不含l和lc.假设C1C2是可满足的,是它的满足赋值,不妨设(l)=1.C2必含有文字l l,lc且(l)=1.C中含有l,故满足C.反之,假设C是可满足的,是它的满足赋值.C必有l 使得(l)=1,不妨设C1含l,于是满足C1.把扩张到l(和lc)上:若l=p,则令(p)=0;若lc=p,则令(p)=1.恒有(lc)=1,从而满足C2.得证C1C2是可满足的.注意:C1C2与Res(C1,C2)有相同的可满足性,但不一定等值.C1=pqr,C2=p r,=011,95,消解序列与合取范式的否证,定义2.10 设S是一个合取范式,C1,C2,Cn是一个简单析取式序列.如果对每一个i(1in),Ci是S的一个简单析取式或者是Res(Cj,Ck)(1jki),则称此序列是由S导出Cn的消解序列.当Cn=时,称此序列是S的一个否证.定理2.9 一个合取范式是不可满足的当且仅当它有否证.例11 用消解规则证明S=(pq)(pqs)(qs)q是不可满足的.证 C1=pq,C2=pqs,C3=Res(C1,C2)=qs,C4=qs,C5=Res(C3,C4)=q,C6=q,C7=Res(C5,C6)=,这是S的否证.,96,消解算法,消解算法输入:合式公式A输出:当A是可满足时,回答“Yes”;否则回答“No”.1.求A的合取范式S2.令S0,S2,S1S的所有简单析取式3.For C1S0和C2S14.If C1,C2可以消解 then5.计算CRes(C1,C2)6.If C=then7.输出“No”,计算结束 8.If CS0且C S1 then9.S2S2C,97,消解算法,10.For C1S1,C2S1且C1C211.If C1,C2可以消解 then12.计算CRes(C1,C2)13.If C=then14.输出“No”,计算结束 15.If CS0且C S1 then16.S2S2C17.If S2=then 18.输出“Yes”,计算结束19.Else S0S0S1,S1S2,S2,goto 3,98,消解算法例题,例12 用消解算法判断下述公式是否是可满足的:1)p(pq)(pq)(qr)(qr)2)(p q)(pq)(q)解 S=p(pq)(pq)(qr)(qr)循环1 S0=,S1=p,pq,pq,qr,qr,S2=Res(pq,pq)=p Res(pq,qr)=pr Res(pq,qr)=pr Res(qr,qr)=q S2=pr,pr,q循环2 S0=p,pq,pq,qr,qr,S1=pr,pr,q,S2=Res(pq,q)=p,99,消解算法例题,Res(qr,pr)=pq Res(qr,pr)=pq Res(pr,pr)=p S2=输出“Yes”,100,主要内容推理的形式结构推理的正确与错误判断推理正确的方法推理定律自然推理系统P形式系统的定义与分类自然推理系统P在P中构造证明:直接证明法、附加前提证明法、归谬法,第三章 命题逻辑的推理理论,101,3.1 推理的形式结构,定义3.1 设A1,A2,Ak,B为命题公式.若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A1,A2,Ak推出结论B的推理是有效的或正确的,并称B是有效结论.,定理3.1 由命题公式A1,A2,Ak 推B的推理正确当且仅当A1A2AkB为重言式注意:推理正确不能保证结论一定正确,102,推理的形式结构,2.A1A2AkB 若推理正确,记为A1 A2 Ak B3.前提：A1,A2,Ak 结论：B判断推理是否正确的方法:真值表法 等值演算法 主析取范式法,推理的形式结构1.A1,A2,Ak B 若推理正确,记为A1,A2,An B,推理实例,例1 判断下面推理是否正确(1)若今天是晴天，则今天踢球.今天是晴天.所以,今天踢球.(2)若今天是晴天，则今天踢球.今天踢球.所以,今天是晴天.,解 设 p：今天是晴天，q：今天踢球.(1)推理的形式结构:,(pq)pq,用等值演算法(pq)pq(pq)p)q pqq 1 由定理3.1可知推理正确,104,推理实例,(2)推理的形式结构:,(pq)qp,用主析取范式法(pq)qp(pq)qp(pq)q)p qp(pq)(pq)(pq)(pq)m0m2m3 结果不含m1,故01是成假赋值，所以推理不正确,105,推理定律重言蕴涵式,1.A(AB)附加律 2.(AB)A 化简律3.(AB)A B 假言推理4.(AB)B A 拒取式 5.(AB)B A 析取三段论6.(AB)(BC)(AC)假言三段论7.(AB)(BC)(AC)等价三段论8.(AB)(CD)(AC)(BD)构造性二难(AB)(AB)B 构造性二难(特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难每个等值式可产生两个推理定律如,由AA可产生 AA 和 AA,106,3.2 自然推理系统P,定义3.2 一个形式系统 I 由下面四个部分组成：(1)非空的字母表，记作 A(I).(2)A(I)中符号构造的合式公式集，记作 E(I).(3)E(I)中一些特殊的公式组成的公理集，记作 AX(I).(4)推理规则集，记作 R(I).记I=自然推理系统:无公理,即AX(I)=公理推理系统 推出的结论是系统中的重言式,称作定理,107,自然推理系统P,定义3.3 自然推理系统 P 定义如下:1.字母表(1)命题变项符号：p,q,r,pi,qi,ri,(2)联结词符号：,(3)括号与逗号：(,),，2.合式公式（同定义1.6）3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则,108,推理规则,(4)假言推理规则(6)化简规则(8)假言三段论规则,(5)附加规则(7)拒取式规则(9)析取三段论规则,109,推理规则,(10)构造性二难推理规则(11)破坏性二难推理规则(12)合取引入规则,110,在自然推理系统P中构造证明,设前提A1,A2,Ak,结论B及公式序列C1,C2,Cl.如果每一个Ci(1il)是某个Aj,或者可由序列中前面的公式应用推理规则得到,并且Cl=B,则称这个公式序列是由A1,A2,Ak推出B的证明直接证明法、附加前提证明法、归谬法例2 构造下面推理的证明：若明天是星期一或星期三，我明天就有课.若我明天有 课，今天必备课.我今天没备课.所以，明天不是星期一、也不是星期三.解(1)设命题并符号化 设 p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课,111,直接证明法,(2)写出证明的形式结构 前提：(pq)r,rs,s 结论：pq(3)证明 rs 前提引入 s 前提引入 r 拒取式(pq)r 前提引入(pq)拒取式 pq 置换,若明天是星期一或星期三，我明天就有课.若我明天有课，今天必备课.我今天没备课.所以，明天不是星期一、也不是星期三.设命题并符号化 p：明天是星期一q：明天是星期三r：我明天有课s：我今天备课,112,附加前提证明法,附加前提证明法 适用于结论为蕴涵式欲证 前提：A1,A2,Ak 结论：CB等价地证明 前提：A1,A2,Ak,C 结论：B理由：(A1A2Ak)(CB)(A1A2Ak)(CB)(A1A2AkC)B(A1A2AkC)B,113,附加前提证明法实例,例3 构造下面推理的证明 2是素数或合数.若2是素数，则 是无理数.若 是无理数，则4不是素数.所以，如果4是素数，则2是合数.解 用附加前提证明法构造证明(1)设 p：2是素数，q：2是合数，r：是无理数，s：4是素数(2)推理的形式结构 前提：pq,pr,rs 结论：sq,114,附加前提证明法实例,(3)证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论,115,归谬法（反证法）,归谬法(反证法)欲证 前提：A1,A2,Ak 结论：B做法 在前提中加入B，推出矛盾.理由 A1A2AkB(A1A2Ak)B(A1A2AkB)(A1A2AkB)0 A1A2AkB0,116,归谬法实例,例4 前提：(pq)r,rs,s,p 结论：q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式(pq)r 前提引入(pq)析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取,117,第一部分 命题逻辑 小结与习题,命题概念、联结词、命题公式、自然语言逻辑真值表构造、命题公式等价形式重言式、矛盾式、可满足式等价推演方法命题公式的范式、主范式、极大（小）项联结词完备集、合式公式消解方法自然语言推理系统,