第一章_命题逻辑1-4节.ppt

第一部分数理逻辑,第一章命题逻辑,第一节命题符号化与联结词,解：1.设p：吴颖用功；q：吴颖聪明则(1)、(2)pq；(3)p(q)2.p:张辉是三好生；q:王丽是三好生(1)pq(2)p：张辉与王丽是同学,解：（1），（2），（3），（6）符号化为pq（4）,（5）符号化为qp注意：pq与qp等值（真值相同）,解：（1）符号化为为pq（2）符号化为pq（3）符号化为pr（4）符号化为pr,解：（1）1；（2）0；（3）1；（4）0；（5）1。,例1:将命题符号化:王小红是计算机系学生,她是三好学生,她不喜欢数学。解:p:王小红是计算机系学生;q:王小红是三好学生r:王小红喜欢数学命题符号化:pq(r)例2:设p:是无理数，q:3是奇数，r:苹果是方的，s:太阳绕地球转则复合命题(pq)(rs)p)是假命题.,第二节命题公式及分类,例：求下列命题公式的层次：其中p，q为单个命题(1)A=p,(2)B=p,(3)C=pq,(4)D=(pq)r,(5)E=(pq)r)(rs),解：分别为0层，1层，2层，3层，4层公式,几点说明：对命题变项p1,p2,pn,给定赋值12n(i=0或1)赋值12n之间不加标点符号，分别指p1=1,pn=n，否则按字典顺序。含n个变项的公式有2n个赋值.注意区分复合命题与命题公式：复合命题有确定的真假值，命题公式必须赋值,易知000,010,101,110是(pq)r的成真赋值，而001,011,100,111是成假赋值.,第三节等值演算,几点说明：这里的A、B、C代表任意的命题公式：这里的1，0代表任意的重言式和矛盾式命题公式之间的等值关系是等价关系：自反，对称，传递。使用上述等值式，不用真值表法可推演出更多等值式来,练习1-31判断下列等值式是否成立（1）（PQ）（RQ）（PR）Q（2）（PQ）（PQ）（PQ）,2.证明下列命题公式的等值关系(PQ)(P(PQ)PQ,1.4析取范式与合取范式每种数字标准形都能提供很多信息，如代数式的因式分解可判断代数式根的情况。逻辑公式在等值演算下也有标准形-范式，范式有两种：析取范式和合取范式。,定义1.11将命题变项及其否定统称为文字。仅由有限个文字构成的析取式称作简单析取式。仅由有限个文字构成的合取式称作简单合取式。（举例）,一、析取范式和合取范式,定理1：（1）简单合取式为永假式的充分必要条件是，它同时包含某个命题变元P及其否定P。（2）简单析取式为永真式的充分必要条件是，它同时包含某个命题变元P及其否定P。,证明（2）必要性：假设A=A1*A2*An*为一简单析取式，且A为一永真式。,(反证法)假设A式中不同时包含任一命题变元及其否定，,则在A中，当Ai*为Ai时指派Ai取0，当Ai*为Ai时，指派Ai取1。(i=1,2,n).这样的一组真值指派使A的真值取0，这与A为永真式矛盾。,例如A=P1P2P3.则(P1,P2,P3)=(0,1,0)的指派，使A的真值为0.,充分性：设A含命题变元Pi和Pi，而PiPi是永真式，由结合律和零一律，A的真值必为1，故A也是永真式。,定义1.12（1）由有限个简单合取式构成的析取式称为析取范式。即具有A1A2An(n1)的形式的公式，其中Ai是简单合取式。,例如，F1=P(PQ)R(PQR)是一析取范式。,（2）由有限个简单析取式构成的合取式称为合取范式。即具有A1A2An(n1)的形式的公式，其中Ai是简单析取式。,例如，F2=P(PQ)R(PQR)是一合取范式。F3=(PRQ)(PQ)R(PR)也是一合取范式。,二、求公式的析取范式和合取范式,任何一个命题公式都可以变换为与它等值的析取范式和合取范式(范式存在性定理)。按下列步骤进行：,（1）利用命题定律消去公式中的运算符“”和“”；,(2)利用德摩根定律将否定符号“”向内深入，使之只作用于命题变元；,（3）利用双重否定律将(P)置换成P；,（4）利用分配律、结合律将公式归约为合取范式或析取范式。,例1求F1=(P(QR)S的合取范式和析取范式,解F1(P(QR)S,P(QR)S,P(QR)S(析取范式),又F1P(QR)S,(PS)(QR),(PSQ)(PSR)（合取范式）,另外由F1(PSQ)(PSR),(P(PSR)(S(PSR)(Q(PSR),PS(QP)(QS)(QR)（析取范式）,例2求F2=(PQ)(PQ)的析取范式、合取范式。,解F2(PQ)(PQ)(PQ)(PQ),(PQ)(PQ)(PQ)(PQ),(P(Q(PQ)(PQ(PQ),(PQ)(PQ)（合取范式）,(P(PQ)(Q(PQ),(PP)(PQ)(PQ)(QQ)（析取范式）,（1）公式A为永真式的充分必要条件是，A的合取范式中每一简单析取式至少包含一对互为否定的析取项。,三、利用范式判定公式类型,证明：（2）必要性（用反证法）：假设AA1A2An中某个Ai不包含一对互为否定的合取项，由前面的定理知，,（2）公式A为永假式的充分必要条件是，A的析取范式中每一质合取式至少包含一对互为否定的合取项。,则Ai不是矛盾式。于是存在一组真值指派使Ai取值为真。,对同一组真值指派，A的取值也必为真，这与A是矛盾式不符，假设不成立。因此A的析取范式中每一质合取式至少包含一对互为否定的合取项。,充分性：假设任一Ai(1in)中含有形如合取式，其中P为命题变元。那么每一Ai(1in)都为矛盾式，因此A1A2An必为矛盾式，即A为矛盾式。,例3判别公式A=P(P(QP)是否为重言式或矛盾式。,解AP(P(QP),P(PQ)(PP)(析取范式),根据定理，A不是矛盾式。,又AP(P(QP),（PP）（PQP)（合取范式）,由定理知，A是重言式。,例4利用范式判断公式P(PQ)的类型。,解P(PQ)(P(PQ)(P(PQ),(PQ)(P(PQ),(PQ)P(析取范式),由定理，该公式不是永假公式。,(PP)(PQ)（合取范式）,由定理，该公式也不是永真公式。,由上可知，该公式是一可满足公式。,又P(PQ)(PQ)P,例如,P1P2P3，P1P2P3均是由P1，P2，P3所产生的极小项。P1P2P3是由P1，P2，P3产生的一个极大项。,五、求公式的主析取范式和主合取范式,例4求公式F1=P(P(QP)和公式F2=(PQ)(PQ)的主析取范式.,解F1P(P(QP),P(PQ)(PP),(P(QQ)(PQ)(P(QQ),(PQ)(PQ)(PQ)(PQ)(PQ),(PQ)(PQ)(PQ)(PQ),F2(PQ)(PQ),(PQ)(PQ)E11,(PPQ)(QPQ)E3,永真公式的主析取范式包含所有2n个最小项。,永假公式的主析取范式是一个空公式。用0表示。,每一个不为永假的命题公式F（P1,P2,Pn）必与一个由P1，P2，Pn所产生的主析取范式等值。,例5求公式F1=(PQ)(PQ)和公式F2=P(P(QP)的主合取范式,F1(PQ)(PQ),(PQ)(P(QQ)(Q(PP),(PQ)(PQ)(PQ)(PQ)(PQ),(PQ)(PQ)(PQ)(PQ),解F2P(P(QP)E11,(PP)(PQP)E3,11E5,E1,1,每一个不为永真的公式F(P1,P2,Pn）必与一个由P1,P2,Pn所产生的主合取范式等值。,永假公式的主合取范式包含所有2n个极大项。,永真公式的主合取范式是一空公式，用1表示。,例6求公式F=(Q(PQ)P的主范式并判定公式的类型.,解(1)求F的主析取范式,F(Q(PQ)P,Q(PQ)P,(Q(PP)(PQ)(P(QQ),（PQ)(PQ)(PQ)(PQ)(PQ),(PQ)(PQ)(PQ),由此可知F是可满足公式。,(2)求F的主合取范式,F（Q(PQ)P,PQ,由前分析和举例可知：仅需求出公式F的任一种主范式即可判定F的类型。,练习1-41判