命题公式的析取范式和合取范式是不唯一的
时间： 10:59:43
&&&&&&&&离散数学&&&&哈尔滨工业大学数学系计算教研室陈延梅&&&&&&&&&&&&离散数学的研究对象&&&&离散数学是现代数学的重要分支，它所研究的对象是离散的数量关系和离散量的结构模型.是与信息科学及其相关的现代科学领域密切相关的数学学科.&&&&&&&&&&&&离散数学的应用背景&&&&离散数学具有广泛的应用背景，信息科学及其相关领域需要对离散结构建立相应的数学模型，或对连续关系的数学模型离散化，离散数学就是适应这种需要建立的，同时离散数学为这些学科的发展提供了数学基础.&&&&&&&&&&&&离散数学的主要内容&&&&数理逻辑集合论代数系统图论&&&&&&&&&&&&第一部分&&&&&&&&数理逻辑&&&&&&&&&&&&通过概念对事物是否具有某种属性进行肯定或否定的回答，就是判断.由一个或几个判断推出另一判断的思维形式，就是推理.研究推理有很多方法.逻辑是研究推理形式有效性的学科.&&&&&&&&&&&&用数学方法来研究推理的规律称为数理逻辑.所指的数学方法就是引进一套符号体系的方法（形式化方法）,故数理逻辑也称为符号逻辑.数理逻辑是用形式系统的方法来研究推理形式的有效性的学科.&&&&&&&&&&&&数理逻辑&&&&命题逻辑一阶逻辑（谓词逻辑）&&&&&&&&&&&&第一章&&&&&&&&命题逻辑&&&&&&&&&&&&简单（原子）命题和一些逻辑符号构成了命题逻辑的形式符号体系.简单（原子）命题是命题逻辑中的最基本单位.&&&&&&&&&&&&命题逻辑的主要内容&&&&命题与联结词命题公式与赋值等值演算析取范式和合取范式命题逻辑的推理理论&&&&&&&&&&&&命题&&&&具有唯一真值的表达判断意义的陈述句称作命题.命题的判断结果称为命题的真值.真值只能取两个值：真或假真→判断正确假→判断错误&&&&&&&&&&&&任何命题的真值都是唯一的.真值为真的命题为真命题.真值为假的命题为假命题.&&&&&&&&&&&&只有具有确定真值的陈述句才是命题,一切没有判断内容的句子,无所谓是非的句子,如感叹句,疑问句,祈使句等都不能作为命题.真值是否唯一与我们是否知道它的真值是两回事.命题一定是陈述句,但陈述句不一定是命题.&&&&&&&&&&&&例&&&&7是无理数.&&&&&&&&太阳从西方升起.火星上存在生命.陈芳和王利是好朋友.这天真冷呀！你出去吗？全体立正!x+80.我正在说谎话.&&&&&&&&真命题假命题命题命题&&&&&&&&悖论&&&&&&&&&&&&例&&&&3不是素数.假命题王丽和李刚都是学生.命题5或6是素数.真命题如果行列式的两行元素对应成比例，则行列式的值为0.真命题角A与角B相等当且仅当A与角B是对顶角.假命题&&&&&&&&&&&&?简单命题命题复合命题&&&&简单命题：由简单的陈述句构成的命题.复合命题：由简单命题用联结词联结而成的命题.&&&&&&&&&&&&命题的符号化&&&&简单命题用p,q,r…等表示.命题的真值符号化为用“1”表示“真”；用“0”表示“假”.&&&&&&&&&&&&复合命题的符号化&&&&用p,q,r…等表示简单命题（通常称p,q,r…为命题常项或命题常元），将p,q,r…用某些联结词符按一定的逻辑关系联结起来就是复合命题的符号化形式.&&&&&&&&&&&&联结词&&&&否定联结词合取联结词析取联结词蕴涵联结词等价联结词&&&&&&&&&&&&否定联结词&&&&设p为一命题，复合命题“非p”定义（或“p的否定”）称为p的否定式，记作?p，称?为否定联结词.?p为真当且仅当p为假.p的真值表为p01?p10&&&&&&&&&&&&否定联结词是一个一元运算.例如p：上海是一个大城市.?p：上海不是一个大城市.q：5能被2整除.?q：5不能被2整除.&&&&&&&&&&&&合取联结词&&&&定义设p,q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作p∧q，称∧为合取联结词.p∧q为真当且仅当p与q同时为真.合取联结词是一个二元运算.&&&&&&&&&&&&p∧q的真值表为&&&&pp∧q0001&&&&&&&&&&&&例如r：2是偶数，s：6是偶数.r∧s：2和6都是偶数.p：2×2=5，q：雪是黑的.p∧q：2×2=5并且雪是黑的.&&&&&&&&&&&&自然语句中的“既…又…”，“不但…而且…”，“不仅…而且…”，“一边…一边…”，“虽然…但…”，等都可符号化为p∧q的形式.&&&&&&&&&&&&例将下列命题符号化&&&&（1）小李既是100米冠军，又是400米冠军.（2）他一边吃饭，一边看电视.（3）他不仅聪明，而且用功.（4）他虽然不太聪明，但他很用功.（5）他不是不聪明，而是不用功.解设u：小李是100米冠军,v：小李是400米冠军.（1）u∧vs：他吃饭，t：他看电视.（2）s∧t设p：他聪明，q：他用功.（3）p∧q（4）?p∧q（5）?(?p)∧?q&&&&&&&&&&&&析取联结词&&&&定义设p,q为二命题，复合命题“p或q”称为p与q的析取式，记作p∨q，称∨为析取联结词.p∨q为假当且仅当p与q同时为假.析取联结词是一个二元运算.&&&&&&&&&&&&p∨q的真值表为pp∨q0111&&&&&&&&&&&&联结词∨与自然语言中的“或”不完全相同，自然语言中的“或”可表示“排斥或”，也可表示“可兼或”.&&&&&&&&&&&&例&&&&&&&&p：小张学过英语，q：小张学过法语.p∨q：小张学过英语或法语.r：今天下雨s：今天刮风.r∨s：今天下雨或者刮风.&&&&&&&&&&&&例&&&&&&&&p:谢单生于1986年，q:谢单生于1999年.谢单生于1986年或1999年：(p∧?q)∨(?p∧q)s：派小王去开会，r：派小张去开会.派小王和小张中的一人去开会：(s∧?r)∨(?s∧r)&&&&&&&&&&&&蕴涵联结词&&&&定义设p,q是二命题，复合命题“如果p，则q”称为p与q的蕴涵式，记作p→q。称p为蕴涵式的前件，q为蕴涵式的后件，称→为蕴涵联结词.p→q为假当且仅当p为真q为假.蕴涵联结词是一个二元运算.&&&&&&&&&&&&p→q的真值表为pp→q1101&&&&&&&&&&&&例&&&&p：f(x)是可微的，q：f(x)是连续的.p→q：若f(x)是可微的，则f(x)是连续的.p：经一事，q：长一智.?p→?q：不经一事，不长一智．&&&&&&&&&&&&例&&&&&&&&将下列命题符号化并判断其真值&&&&&&&&（1）若2+2=4，则地球是运动的.（2）若2+2≠4，则地球是运动的.（3）若2+2=4，则地球是静止的.（4）若2+2≠4，则地球是静止的.42+2≠4.解p：2+2=4，q：地球是运动的,（1）符号化为p→q,真值为1.（2）符号化为?p→q,真值为1.（3）符号化为p→?q,真值为0.（4）符号化为?p→?q,真值为1.&&&&&&&&&&&&使用蕴涵联结词时应注意的问题&&&&在自然语句中“如果p，则q”中的p与q往往有某种内在的联系，否则无意义.而在数理逻辑中p与q不一定有什么内在联系.只要p，q能够分别确定真值，p→q即成为命题．在自然科学中，“如果p，则q”往往表示前件p为真，后件q也为真的推理关系.而在数理逻辑中，当p为真，q也为真时，命题p→q为真，这与自然语言是一致的；但当p为假时，则不管q是什么命题，命题p→q都是真命题，这与自然语言是不一致的.&&&&&&&&&&&&自然语句中的“只要p就q”，“p仅当q”，“只有q才p”,“除非q才p”，“除非q，否则非p”等都可符号化为p→q的形式.&&&&只要明天晴天,我们就去郊游.&&&&&&&&p：明天晴天，q：我们去郊游,p→q：只要明天晴天,我们就去郊游.&&&&&&&&&&&&例&&&&&&&&将下列命题符号化&&&&&&&&(1)只有2是偶数，3才能被2整除(2)除非6能被4整除，6才能被2整除(3)只有天下雨，他才乘公共汽车上班(4)(4)除非天下雨，否则他不乘公共汽车上班解p：2是偶数，q：3能被2整除,(1)符号化为q→pr：6能被4整除，s：6能被2整除(2)符号化为s→r解u：天下雨,v：他乘公共汽车上班(3)符号化为v→u,(4)符号化为v→u(?u→?v)&&&&&&&&&&&&等价联结词&&&&定义设p,q为二命题，复合命题“p当且仅当q”称为p与q的等价式，记作p?q，称?为等价联结词.p?q为真当且仅当p与q的真值相同.等价联结词是一个二元运算.&&&&&&&&&&&&p?q的真值表为pp?q1001&&&&&&&&&&&&例如p：a2+b2=a2，q：b=0.p?q：a2+b2=a2当且仅当b=0.s：1+2=3，r：雪是黑的.s?r：1+2=3当且仅当雪是黑的.u：燕子飞回北方，v：春天来了.u?v：燕子飞回北方，春天来了.&&&&&&&&&&&&例&&&&&&&&将下列命题符号化并判断其真值&&&&&&&&（1）若2+2=4当且仅当3+3=6.（2）若2+2≠4当且仅当3+3=6.（3）若2+2=4当且仅当3+3≠6.（4）若2+2≠4当且仅当3+3≠6.解p：2+2=4，q：3+3=6.（1）符号化为p?q,真值为1.（2）符号化为?p?q,真值为0.（3）符号化为pq,真值为0.（4）符号化为?pq,真值为1.&&&&&&&&&&&&联结词的优先级顺序&&&&以上五种联结词，构成一个联结词集{?，∧，∨，→，?}.其中?是一元联结词符；∧，∨，→，?是二元联结词符.这些联结词符的优先级顺序为?，∧，∨，∧∨→，?.如果联结词符同级，又无括号，则按从左到右的顺序计算。如果有括号，先进行括号中运算.&&&&&&&&&&&&异或联结词&&&&定义设p,q为二命题，复合命题“p、q之中仅一个成立”称为p与q的异或式（或排斥式），记作p?q，称?为异或联结词.p?q为真当且仅当p与p中仅一个为真.p?q?(p∧?q)∨(?p∧q)&&&&&&&&&&&&p?q的真值表为pp?q0110&&&&&&&&&&&&例&&&&&&&&p:谢单生于1986年，q:谢单生于1999年.p?q：谢单生于1986年或1999年.s：派小王去开会，r：派小张去开会.s?r：派小王和小张中的一人去开会.&&&&&&&&&&&&复合命题的符号化&&&&用p,q,r…等表示简单命题（通常称p,q,r…为命题常项或命题常元），将p,q,r…用{?，∧，∨，→，?}中的某些联结词符按一定的逻辑关系联结起来就是复合命题的符号化形式.&&&&&&&&&&&&例将复合命题符号化，并讨论其真值&&&&（1）如果3是合数，则4是素数，并且如果4是素数，则它不能被2整除.（2）如果2+35当且仅当5是合数，则3和5都22+35535是偶数.解（1）p：3是合数，q：4是素数，r：4能被2整除，命题符号化为(p→q)∧(q→?r).真值1.（2）p：2+35，q：5是合数，r：3是偶数,s：5是偶数.命题符号化为(p?q)→(r∧s).真值0.&&&&&&&&&&&&命题公式与赋值&&&&&&&&&&&&在数理逻辑中不仅要研究具体的逻辑关系,而更主要的是研究抽象的逻辑关系,为此首先对简单命题进行抽象,引入命题变项.命题变项是取值0或1的变量.命题变项也用p,q,r…表示.命题变项不是命题.&&&&&&&&&&&&命题公式（合式公式）&&&&定义（1）单个的命题变项或常项是合式公式；（2）若A是合式公式，则（?A)也是合式公式；（3）若A,B是合式公式，则（A∧B）,（A∨B）,（A→B）,（A?B）也是合式公式.（4）当且仅当能够有限次地应用(1),(2),(3)的符号串是合式公式.注:(1)（A∧B）,（A∨B）,（A→B）,（A?B）外面的括号可省去.(2)合式公式亦简称为公式.&&&&&&&&&&&&例&&&&?(p∧q),?(p→q),(p→(p∨?q)),(((p→q)∧(q→r))?(s?t))都是合式公式(p→q)→(∧q),(p→q,(pq)→q都不是合式公式.&&&&&&&&&&&&命题公式是没有真假值的,仅当一个公式中的命题变项用确定的命题代入时,才成为命题,且这个命题的真值依赖于代换命题变项的那些命题的真值.例１．给出解释p：6是素数,q：7是偶数,r：π是无理数.p,q,r的真值分别为０,0,1,故(p→q)∧r的真值为１．２．给出解释p：３是奇数,q：２是合数,r：８是整数.p,q,r的真值分别为１,0,1,故(p→q)∧r的真值为０．&&&&&&&&&&&&命题公式的赋值&&&&定义设p1,p2,…,pn是命题公式A中出现的所有命题变项。给p1,p2,…,pn各指定一个真值，则这组真值称为A的一个解释或赋值.若指定的一组值使A的真值为1，则称这组值为A的成真赋值.若指定的一组值使A的真值为0，则称这组值为的A成假赋值.&&&&&&&&&&&&命题公式的赋值形式&&&&含n个命题变项的命题公式A的赋值形式做如下规定:（1）设A中的命题变项为p1,p2,…,pn，赋值a1a2…an（ai为0或1）是指p1=1,=ap2=a2,…,pn=an.（2）设A中的命题变项为p,q,r…，赋值a1a2…an（ai为0或1）是指p=a1,q=a2,r=a3,…，即按字典顺序.&&&&&&&&&&&&例&&&&公式(p→q)∧r中，111（p=1,q=1,r=1）为成真赋值．101（p=1,q=0,r=1）为成假赋值．&&&&&&&&&&&&含n个命题变项的命题公式A的共有2n个赋值.&&&&&&&&&&&&公式的层次&&&&定义（1）若A是单个的命题变项（或常项），则称A是０层公式；（2）称A是n+1层公式是指下列诸情况之一：①A=?B,其中B是n层公式；②A=B∧C,其中B,C分别为i层和j层公式,且n=max(i,j)；③A=B∨C,其中B,C的层次同②;④A=B→C,其中B,C的层次同②;⑤A=B?C,其中B,C的层次同②.&&&&&&&&&&&&真值表及其构造&&&&将公式A在所有赋值情况下列成表，称为A的真值表.构造真值表的具体步骤为（1）找出公式中所有的命题变项p1,p2,…,pn（如无脚标按字典顺序），列出所有可能的赋值；（2）按从低到高的顺序写出各层次；（3）对应各赋值，计算公式各层次的值，直到最后计算出公式的值.&&&&&&&&&&&&例构造公式?(p∧q)?(?p∨?q)的真值表&&&&pq?p?qp∧q?(p∧q)?p∨?q?(p∧q)?(?p∨?q)&&&&&&&&&&&&例构造公式(p∧?q)→r的真值表&&&&p01?qp∧?q(p∧?q)→r&&&&&&&&&&&&例构造公式?(p→q)∧q∧r的真值表&&&&p10011rp→q?(p→q)?(p→q)∧q?(p→q)∧q∧r1000&&&&&&&&&&&&公式的类型&&&&定义设A为一命题公式.若A在它的所有赋值下取值均为1，则称A为重言式（或永真式）；若A在它的所有赋值下取值均为0，则称A为矛盾式（或永假式）；如A不是矛盾式，则称A为可满足式.&&&&&&&&&&&&公式的分类&&&&重言式?可满足式?命题公式非重言式的可满足式?矛盾式?&&&&&&&&&&&&等值演算&&&&&&&&&&&&n个命题变项共能生成公式.&&&&&&&&2个真值不同的命题&&&&&&&&2n&&&&&&&&&&&&等值式&&&&定义设A,B为二命题公式，若等价式A?B为重言式，则称A与B是等值的，记作A?B.注意:“?”与“?”的区别“?”是逻辑联结词符,起逻辑运算的作用.“?”表示两公式关系的符号.&&&&&&&&&&&&判断公式等值的方法&&&&真值表法等值演算法&&&&&&&&&&&&基本等值式&&&&双重否定律等幂律交换律结合律A?AA∧A?A，A∨A?AA∧B?B∧A，A∨B?B∨A，(A∧B)∧C?A∧(B∧C)(A∨B)∨C?A∨(B∨C)分配律A∧(B∨C)?(A∧B)∨(A∧C)A∨(B∧C)?(A∨B)∧(A∨C)德·摩根律?(A∧B)A∨?B?(A∨B)A∧?B&&&&&&&&&&&&基本等值式&&&&吸收律A∧(A∨B)?A，A∨(A∧B)=A零律A∧0?0，A∨1?1同一律A∨0?A，A∧1?A排中律A∨?A?1矛盾律A∧?A?0蕴涵等值式A→BA∨B等价等值式A?B?(A→B)∧(B→A)；假言易位A→BB→?A等价否定等值式A?BAB归谬论(A→B)∧(A→?B)A&&&&&&&&&&&&代入定理&&&&定理1.1（代入定理）设A为含n个命题变项p1,p2,…,pn的命题公式，A1,A2,…,An是任意命题公式，A中pi用Ai(i=1,2,…,n)代入后得到的公式记为B，若A是重言式，则B也是重言式.&&&&&&&&&&&&置换规则&&&&定理1.2（置换规则）设Ф(A)是含公式A的命题公式，B?A则可用B置换Ф(A)中的A，得Ф(B)，保证Ф(A)?Ф(B).&&&&&&&&&&&&等值演算&&&&由已知等值式推演出另外一些等值式的过程称为等值演算.通过等值演算可化简公式，判断公式的类型等等.等值演算过程中，需不断使用置换规则.&&&&&&&&&&&&例把下列语句的确切含义表达出来&&&&1.你去不去都没关系.p：你去.p∨?p?12.玫瑰香,牡丹香,玫瑰与牡丹都香,没有不香的玫瑰,也没有不香的牡丹.p：玫瑰香&&&&,q：牡丹香,p∧q∧(p∧q)∧?(?p)∧?(?q)?p∧q:玫瑰香，牡丹也香．&&&&&&&&&&&&例证明p→(q→r)?(p∧q)→r&&&&证明:p→(q→r)p∨(q→r)p∨(?q∨r)?(?p∨?q)∨r(p∧q)∨r?(p∧q)→r(蕴涵等值式)(蕴涵等值式)(结合律)(德·摩根律)(蕴涵等值式)&&&&&&&&&&&&例用等值演算法判断公式的类型&&&&(1)．p→(p∨q∨r)(2)．(?p→q)→(q→?p)(1)．p→(p∨q∨r)p∨(p∨q∨r)?(?p∨p)∨q∨r?1∨q∨r?1(1)为重言式．&&&&&&&&(蕴涵等值式)(结合律)(排中律)(零律)&&&&&&&&&&&&(2)．(?p→q)→(q→?p)?(p∨q)→(?q∨?p)(蕴涵等值式)(p∨q)∨(?q∨?p)(蕴涵等值式)?(?p∧?q)∨(?q∨?p)(德·摩根律)?((?p∧?q)∨?q)∨?p(结合律)?(?q∨(?q∧?p))∨?p(交换律)q∨?p(吸收律)p∨?q(交换律)11为该公式的成假赋值，01为该公式的成真赋值，故是非重言式的可满足式．&&&&&&&&&&&&析取范式和合取范式&&&&&&&&&&&&文字、简单析取式、简单合取式&&&&定义命题变项及其否定统称为文字。例如p，?p是文字.仅由有限个文字构成的析取式称为简单析取式仅由有限个文字构成的合取式称为简单合取式例如p，p∨q，?p∨q是简单析取式；p，p∧q，?p∧?q是简单合取式.特别，一个文字既是简单析取式，又是简单合取式.&&&&&&&&&&&&一个简单析取式是重言式当且仅当它同时含有一个命题变项及其否定式.一个简单合取式是矛盾式当且仅当它同时含有一个命题变项及其否定式.例如?p∨q∨?q是重言式；?p∧p∧r是矛盾式.&&&&&&&&&&&&析取范式、合取范式、范式&&&&定义由有限个简单合取式构成的析取式称为析取范式.由有限个简单析取式构成的合取式称为合取范式.析取范式和合取范式统称为范式.例?p,q∧r,(p∧q)∨(?q∧r)都是析取范式；?p,q∧r,?p∨q,(p∨q)∧(q∨?r)都是合取范式.&&&&&&&&&&&&一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式.一个合取范式是重言式当且仅当它的每个简单析取式都是重言式.&&&&&&&&&&&&范式存在定理&&&&定理1.3任一命题公式都存在与之等值的析取范式和合取范式.证第1步使用基本等值式A→BA∨B，A?B?(?A∨B)∧(?B∨A)将联结词→，?消去；第2步使用双重否定律和德·摩根律A?A，?(A∧B)A∨?B?(A∨B)A∧?B消去或内移否定联结词到命题变项之前；&&&&&&&&&&&&第2步利用分配律，求析取范式用“∧”对“∨”的分配律；求合取范式用“∨”对“∧”的分配律．证毕一个命题公式的析取范式和合取范式是不唯一的.&&&&&&&&&&&&求公式的析取范式和合取范式的步骤&&&&（1）消去{?，∧，∨}以外的联结词；（2）内移或削去否定联结词；（3）利用分配律.求公式的析取范式利用“∧”对“∨”的分配律；求公式的合取范式利用“∨”对“∧”的分配律.&&&&&&&&&&&&例求公式(p∨q)→(q?r)的析取范式和合取范式&&&&(p∨q)→(q?r)?(p∨q)→((q→r)∧(r→q))(消去?)(p∨q)∨((?q∨r)∧(?r∨q))(消去→)?(?p∧?q)∨((?q∨r)∧(?r∨q))(德·摩根律)?(?p∧?q)∨(?q∧?r)∨(?q∧q)∨(r∧?r)∨(r∧q)(“∧”对“∨”的分配律)，(析取范式)?(?p∧?q)∨(?q∧?r)∨0∨0∨(r∧q)?(?p∧?q)∨(?q∧?r)∨(r∧q)(析取范式)&&&&&&&&&&&&(p∨q)→(q?r)?(?p∧?q)∨((?q∨r)∧(?r∨q))?((?p∧?q)∨(?q∨r))∧((?p∧?q)∨(?r∨q))(“∨”对“∧”分配)?(?p∨?q∨r)∧(?q∨?q∨r)∧(?p∨q∨?r)∧(?q∨q∨?r)(“∨”对“∧”分配)，(合取范式)?(?p∨?q∨r)∧(?q∨r)∧(?p∨q∨?r)(合取范式)&&&&&&&&&&&&命题公式的析取范式和合取范式是不唯一的.为寻找相互等值公式的标准形式，引进主析取范式和主合取范式．给出一个公式的主析取范式和主合取范式，首先需要对简单合取式和简单析取式标准化，即引进极小项和极大项．&&&&&&&&&&&&极小项&&&&定义在含有n个文字的简单合取式中，若每个命题变项与其否定式不同时存在，而二者之一必出现且仅出现一次，且第i个命题变项或者其否定式出现在从左起的第i个位置上（若命题变项无脚标按字典顺序），这样的简单合取式称为极小项.n个命题变项共可产生2n个不同的极小项.&&&&&&&&&&&&例对命题变项p,q,r而言，p∧?q∧r，?p∧?q∧r，p∧q∧r都是极小；但是，p，?p∧q不是极小项.而?p∧q对命题变项p，q而言是极小项.&&&&&&&&&&&&显然，对于n个命题变项p1,p2,…,pn而言，其不同的赋值共有2n个，对于p1,p2,…,pn的任一个极小项m，2n个赋值中，有且只有一个赋值为m的成真赋值。例如，对p,q,r而言，?p∧q∧?r是极小项，只有赋值010为该极小项的成真赋值，其它赋值都是该极小项的成假赋值．&&&&&&&&&&&&如果将命题变项的原形对应1，否定式对应0，则每一个极小项对应一个n位二进制数。当然也对应一个十进制数。二进制数正是该极小项的唯一成真赋值，十进制数可作为该极小项的抽象表示法的角标．假设极小项m的成真赋值对应的二进制数为a1a2…an（ai为0或1），十进制数为j，今后将m记为mj。&&&&&&&&&&&&3个命题变项生成8个极小项&&&&极小项?p∧?q∧?r?p∧?q∧r?p∧q∧?r?p∧q∧rp∧?q∧?rp∧?q∧rp∧q∧?rp∧q∧r解释记法m0m1m2m3m4m5m6m7&&&&&&&&&&&&一般地，对n个命题变项p1,p2,…,pn共产生2n个极小项，分别记作m0,m1,…,m2n?1.mi(0≤i≤2n?1)的角标i的二进制表示为mi的唯一成真赋值，于是有n个命题变项的2n个赋值与2n个极小项之间有一一对应关系.&&&&&&&&&&&&主析取范式&&&&定义设命题公式A中含有n个命题变项，如果A的析取范式中的每一个简单合取式都是极小项，则称该析取范式为A的主析取范式．矛盾式的主析取范式没有极小项，用0表示．重言式主析取范式含有2n个极小项．&&&&&&&&&&&&主析取范式唯一存在定理&&&&定理1.4任一命题公式都存在与之等值的主析取范式，并且是唯一的。证（1）由定理1.3知，命题公式A存在析取范式A’，使得A?A’．（2）设A中含有n个命题变项p1,p2,…,pn，如果A’中的某个简单合取式Ai不含命题变项pj，也不含?pj，则将Ai展成如下形式Ai?Ai∧1?Ai∧(pj∨?pj)?(Ai∧pj)∨(Ai∧?pj)添补上缺少的命题变项．&&&&&&&&&&&&（3）将重复出现的命题变项，极小项，矛盾式消去．如p∧p用p代替，p∧?p用０代替，mi∨mi用mi代替.经(2),(3)A化成了与其等值的主析取范式A’’.（4）假设A存在两个不同的与其等值的主析取范式B与C,则A?B,A?C,从而B?C．由于B与C不同，必存在一个极小项mi只出现于B中或C中，不妨设出现在B中，而不出现在C中，于是i的二进制数表示B的成真赋值,C的成假赋值,与B?C矛盾,故B与C相同.&&&&&&&&&&&&求公式A的主析取范式的方法&&&&等值演算法利用公式的主合取范式求主析取范式真值表法&&&&&&&&&&&&等值演算法求公式A的主析取范式的步骤&&&&(1)求公式A的析取范式；(2)若公式A的析取范式A’中的某个简单合取式Ai不含命题变项pj，也不含?pj，则将Ai展成如下形式：Ai?Ai∧1?Ai∧(pj∨?pj)?(Ai∧pj)∨(Ai∧?pj)(3)将重复出现的命题变项，矛盾式，重复出现的极小项消取.&&&&&&&&&&&&例&&&&求A=?(r→p)∨(q∧(p∨r))主析取范式.?→∨∧∨解A=?(r→p)∨(q∧(p∨r))(?r∨p)∨(q∧p)∨(q∧r)?(?p∧r)∨(p∧q)∨(q∧r)?((?p∧r)∧(?q∨q))∨((p∧q)∧(?r∨r))∨((q∧r)∧(?p∨p))?(?p∧?q∧r)∨(?p∧q∧r)∨(p∧q∧?r)∨(p∧q∧r)?m1∨m3∨m6∨m7?∑(1,3,6,7)&&&&&&&&&&&&用真值表法求A=(p∧q)∨(?p∧r)∨(q∧r)主析取∧∨?∧∨∧范式&&&&p&&&&&&&&&&&&q&&&&&&&&&&&&r&&&&&&&&&&&&A&&&&&&&&&&&&&&&&A的主析取范式为(?p∧?q∧r)∨(?p∧q∧r)∨(p∧q∧?r)∨(p∧q∧r)?m1∨m3∨m6∨m7?∑(1,3,6,7)&&&&&&&&&&&&主析取范式的应用&&&&求公式的成真赋值和成假赋值若公式A中含有n（n≥1）个命题变项，A的主析取范式含s（0≤s≤2n）个极小项，则A有s个成真赋值,它们是所含极小项的脚标的二进制表示，其余2n-s个赋值都是A的成假赋值.例A是含2个命题变项的命题公式,其主析取范式为m0∨m2,则00,10是A的成真赋值,01,11为A的成假赋值.B是含3个命题变项的命题公式,其主析取范式为m0∨m2∨m5,则000,010,101是B的成真赋值,001,011,100,110,111为B的成假赋值.&&&&&&&&&&&&主析取范式的应用&&&&判断两个公式是否等值设若A,B是二命题公式，则A?B当且仅当A与B有相同的主析取范式.&&&&&&&&&&&&主析取范式的应用&&&&判断公式的类型设A是含n个命题变项的命题公式，A为重言式当且仅当A的主析取范式含全部2n个极小项；A为矛盾式当且仅当A的主析取范式不含任何极小项.&&&&&&&&&&&&极大项&&&&定义在含有n个文字的简单析取式中，若每个命题变项与其否定式不同时存在，而二者之一必出现且仅出现一次，且第i个命题变项或者其否定式出现在从左起的第i个位置上（若命题变项无脚标按字典顺序），这样的简单析取式称为极大项.n个命题变项共可产生2n个不同的极大项.&&&&&&&&&&&&显然，对于n个命题变项p1,p2,…,pn而言，其不同的赋值共有2n个，对于p1,p2,…,pn的任一个极大项M，2n个赋值中，有且只有一个赋值为M的成假赋值。例如，对p,q,r而言，?p∨q∨?r是极大项，只有赋值101为该极大项的成假赋值，其它赋值都是该极大项的成真赋值．&&&&&&&&&&&&如果将命题变项的原形对应0，否定式对应1，则每一个极大项对应一个n位二进制数。当然也对应一个十进制数。二进制数正是该极大项的唯一成假赋值，十进制数可作为该极大项的抽象表示法的角标．假设极大项M的成假赋值对应的二进制数为a1a2…an（ai为0或1），十进制数为j，今后将M记为Mj。&&&&&&&&&&&&3个命题变项生成8个极大项&&&&极大项p∨q∨rp∨q∨?rp∨?q∨rp∨?q∨?r?p∨q∨r?p∨q∨?r?p∨?q∨r?p∧?q∧?r解释记法M0M1M2M3M4M5M6M7&&&&&&&&&&&&一般地，对n个命题变项p1,p2,…,pn共产生2n个极大项，分别记作M0,M1,…,nM2n?1.Mi(0≤i≤2?1)的角标i的二进制表示为Mi的成假赋值，于是有n个命题变项的2n个赋值与2n个极大项之间有一一对应关系.&&&&&&&&&&&&主合取范式&&&&定义设命题公式A中含有n个命题变项，如果A的合取范式中的每一个简单析取式都是极大项，则称该合取范式为A的主合取范式。重言式的主合析取范式用1表示.矛盾式的主合取范式含有2n个极大项．&&&&&&&&&&&&主合取范式唯一存在定理&&&&定理任一命题公式都存在与之等值的主合取范式，并且是唯一的．&&&&&&&&&&&&求公式A的主合取范式的方法&&&&等值演算法利用公式的主析取范式求主合取范式真值表法&&&&&&&&&&&&等值演算法求公式A的主合取范式的步骤&&&&（1）求公式A的合取范式；（2）若公式A的合取范式A’中的某个简单析取式Ai不含命题变项pj，也不含?pj，则将Ai展成如下形式：Ai?Ai∨0?Ai∨(pj∧?pj)?(Ai∨pj)∧(Ai∨?pj)(3)将重复出现的命题变项，重言式，重复出现的极大项消去．&&&&&&&&&&&&利用公式的主析取范式求主合取范式&&&&若公式A中含有n（n≥1）个命题变项项，A的主析取范式含s（0≤s≤2n）个极小项，则A有s个成真赋值，2n-s个成假赋值，写出各成假赋值对应的个极大项，将它们合取起来就是A的主合取范式．&&&&&&&&&&&&命题逻辑的推理理论&&&&&&&&&&&&数理逻辑是用形式系统的方法来研究推理形式的有效性的学科..推理是从前提出发推出结论的思维过程,前提是已知的命题公式集合,结论是从前提出发利用公认推理规则推出的命题公式.研究推理理论,首先要建立推理的形式结构,给出判断推理正确的方法,提供正确的推理规则.&&&&&&&&&&&&推理的形式结构&&&&定义称蕴涵式(A1∧A2∧…∧Ak)→B为推理的形式结构.A1,A2,…,Ak为推理的前提，B为推理的结论.若(A1∧A2∧…∧Ak)→B为重言式，则称从前提A1,A2,…,Ak推出结论B的推理正确9（有效），B是A1,A2,…,Ak的逻辑结论或有效结论.否则称推理不正确（无效）.&&&&&&&&&&&&推理正确的表示方法&&&&用“A?B”表示“A→B”是重言式.若从前提A1,A2,…,Ak推出结论B的推理正确，则记(A1∧A2∧…∧Ak)?B注意：“?”不是逻辑联结词符，只是表示重言式的一种方式.&&&&&&&&&&&&判断推理是否正确的方法&&&&真值表法等值演算法主析取范式法形式证明法(形式演绎法)&&&&&&&&&&&&证明(演绎)&&&&在数理逻辑逻中,证明是一个描述推理过程的命题公式序列,其中的每个命题公式或者是已知的前提,或者是某些前提应用推理规则的基础上得到的结论.应用推理规则要明确列出.&&&&&&&&&&&&推理定律(重言蕴涵式)&&&&(1)A?A∨B（B?A∨B）(2)A∧B?A（A∧B?B）(3)(A→B)∧A?B(4)(A→B)∧?BA(5)(A∨B)∧?B?A(6)(A→B)∧(B→C)?(A→C)(7)(A?B)∧(B?C)?(A?C)(8)(A→B)∧(C→D)∧(A∨C)?(B∨D)附加化简假言推理拒取式析取三段论假言三段论等价三段论构造性二难&&&&&&&&&&&&推理定律&&&&每个等值式均产生两个推理定律例?A∨B?A→B?A∨B?A→BA→BA∨B&&&&&&&&&&&&定理&&&&定理1.5定理(1)(A1∧A2∧…∧Ak)?Ai,i=1,2,…,k(2)若(A1∧A2∧…∧Ak)?Bj,j=1,2,…,s且(B1∧B2∧…∧Bs)?B，则(A1∧A2∧…∧Ak)?B&&&&&&&&&&&&推理规则&&&&规则P(前提引入规则)在证明的任何一步骤，都可以引用前提．规则T(结论引入规则)在证明的任何一步骤上，所得到的结论都可作为后续证明的前提．[(置换规则)在证明的任何一步骤上，命题公式中的任何公式都可以用与之等值的公式置换，得到证明公式序列中又一公式.&&&&附加，化简,合取，假言推理,拒取式,析取三段论,假言三段论,等价三段论,构造性二难等.]&&&&&&&&&&&&如果结论是A→B的形式,即推理形式结构为(A1∧A2∧…∧Ak)→(A→B)(1)(1)(A1∧A2∧…∧Ak)∨(?A∨B)(A1∧A2∧…∧Ak∧A)∨B?(A1∧A2∧…∧Ak∧A)→B(2)(1)为重言式当且仅当(2)为重言式.&&&&&&&&&&&&附加前提证明法&&&&CP规则&&&&若(A1∧A2∧…∧Ak∧A)?B,则(A1∧A2∧…∧Ak)?(A→B)&&&&&&&&此规则把结论A→B中的A做为附加前提,也称为附加前提引入规则.&&&&&&&&&&&&归谬法&&&&若A1∧A2∧…∧Ak是可满足式,则称A1,A2,…,Ak是相容的.若A1∧A2∧…∧Ak是矛盾式,则称A1,A2,…,Ak是不相容的.A1,A2,…,Ak是不相容当且仅当(A1∧A2∧…∧Ak)?0.&&&&&&&&&&&&(A1∧A2∧…∧Ak)→B(A1∧A2∧…∧Ak∧?B)从而(A1∧A2∧…∧Ak)→B为重言式当且仅当A1,A2,…,Ak,?B不相容.(A1∧A2∧…∧Ak)?B当且仅当(A1∧A2∧…∧Ak∧?B)?0这种在推理过程中,将结论的否定式作为附加前提引出矛盾式的证明方法称为归谬法.&&&&&&&&&&&&命题逻辑自然推理系统的构成&&&&命题逻辑字母表命题逻辑合式公式命题逻辑推理规则&&&&&&&&&&&&例在命题逻辑中构造下面推理的证明&&&&(1)前提:p∨q,p→r,q→s,结论:s∨r(2)前提:p→(q→s),?r∨p,q,结论:r→s证明①p∨q前提引入②?p→q①置换③q→s前提引入④?p→s②③假言三段论⑤?s→p④置换⑥p→r前提引入⑦?s→r⑤⑥假言三段论⑧s∨r⑦置换&&&&&&&&&&&&前提:p→(q→s),?r∨p,q,结论:r→s&&&&证明①?r∨p②r③p④p→(q→s)⑤q→s⑥q⑦sr→s前提引入附加前提引入①②析取三段论前提引入③④假言推理前提引入⑤⑥假言推理&&&&&&&&CP规则&&&&&&&&&&&&例在命题逻辑中构造下面推理的证明&&&&如果A工作努力,则B或C将生活愉快.如果B生活愉快,那么A将不努力工作.如果D生活愉快,则C将生活不愉快.所以如果A努力工作,D则不愉快.解设p：A工作努力；q：B生活愉快；r：C生活愉快；s：D生活愉快．&&&&&&&&&&&&前提：p→(q∨r),q→?p,s→?r结论：p→?s&&&&证明①s→?r②r→?s③q→?p④p→?q⑤p→(q∨r),⑥p→(?q→r)⑦p⑧?q→r⑨?q⑩r&&&&⑾?s&&&&&&&&p→?s&&&&&&&&前提引入①置换前提引入③置换前提引入⑤置换附加前提引入⑥⑦假言推理④⑦假言推理⑧⑨假言推理②⑩假言推理CP规则&&&&&&&&&&&&例在命题逻辑中构造下面推理的证明&&&&若厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂经理辞职．厂方拒绝增加工资.罢工又刚刚开始.罢工是否能停止?令p：厂方拒绝增加工资；q：罢工停止；r：工厂经理辞职；s：罢工超过一年．&&&&&&&&&&&&前提：p→(q→(s∧r)),p,?s结论：设想为?q&&&&证明①p→(q→(s∧r))②p③q→(s∧r)④?(s∧r)→?q⑤?s⑥?s∨?r⑦?(s∧r)⑧?q猜想正确，即罢工不会停止．前提引入前提引入①②假言推理③置换前提引入⑤附加⑥置换④⑦假言推理&&&&&&&&&&&&用归谬法证明(p→q)∧p?q&&&&证明①p→q前提引入②?q否定结论引入③?p①②拒取式④p前提引入⑤?p∧p③④合取⑤为矛盾式,故推理正确.&&&&&&&&&&&&作业&&&&习题一14，16，19，26习题二3，5，6，7，8，9，10，15，27，30习题三9，14，15，16，17，18红色题号每题中只选一道题&&&&&&&&&&&&&&&&