资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,第一章 命题逻辑,11 命题及其表示法,1.什么是命题,命题：能判断真假陈说句。,命题值叫它真值。,真值：“真”：表示判断正确。记作True，用T表示。,“假”：表示判断错误。记作False，用F表示。,第1页,例1 判断以下句子中哪些是命题？,（1）2是素数。,（2）雪是黑色。,（3）2+3=5,（4）明年10月1日是晴天。,（5）3能被2整除。,（6）这朵花真好看呀！,（7）明天下午有会吗？,（8）请关上门！,（9）X+Y5,（10）地球外星球上也有些人。,（11）我正在说谎。,第2页,2命题符号化表示,命题符号化就是用符号表示命题。,简单命题（或原子命题）：简单陈说句表示命题。用P，Q，R,P,i,Q,i,R,i,表示。,例 P:2是偶数。,Q:雪是黑色。,命题常量（或命题常元）：简单命题。,命题变项（或命题变元）：真值能够改变简单陈说句。不是命题。,例：x+y5,第3页,命题变项也用P，Q，R,P,i,Q,i,R,i,表示。,复合命题：由简单命题用联结词联结而成命题。,第4页,例2 将以下命题符号化。,（1）3 不是偶数。,（2）2 是素数和偶数。,（3）林芳学过英语或日语。,（4）假如角A和角B是对顶角，则角A 等于角B。,解：（1）设P：3是偶数。,P（：表示并非）,（2）设P：2 是素数；Q：2是偶数。,PQ(:表示和),（3）设P：林芳学过英语；Q：林芳学过日语。,PQ(:表示或),（4）设P：角A和角B是对顶角；Q：角A 等于角B。,PQ（个表示假如则）,第5页,12.联结词,定义12.1,设P为任一命题，P否定是一个新命题，称为P,否定式，,记作P。为,否定联结词。,P,P,T,F,F,T,例 p：3是偶数。,p：3不是偶数。,第6页,定义12.2,设P、Q为两命题，复合命题“P而且Q”（或“P和Q”）称为 P与Q,合取式，,记作PQ，为,合取联结词。,表示自然语言中“既又”，,“不但而且”，,“即使不过”,P,Q,P Q,T,T,T,T,F,F,F,T,F,F,F,F,第7页,例3将以下命题符号化。,（1）李平既聪明又用功。,（2）李平即使聪明，但不用功。,（3）李平不但聪明，而且用功。,（3）李平不是不聪明，而是不用功。,解：设P：李平聪明；Q：李平用功。,（1）PQ,（2）PQ,（3）PQ,（4）（P）Q,注意：不是见到“和”、“与”就用。,例：“李文和李武是弟兄”，“王芳和陈兰是好朋友”是简单命题。,第8页,定义12.3,设P、Q为两命题，复合命题“P或Q”称为 P与Q,析取式，,记作PQ，为,析取联结词。,P,Q,P Q,T,T,T,T,F,T,F,T,T,F,F,F,第9页,析取式PQ表示是一个相容性或，即允许P和Q同时为真。,例：“王燕学过英语或日语”PQ,自然语言中“或”含有二义性，有时表示不相容或。,例：“派小王或小李中一人去开会”。为排斥性或。,P：派小王去开会；Q：派小李去开会。,（PQ）（PQ），,（PQ）（PQ）,第10页,定义12.4,设P、Q为两命题，复合命题“假如P，则Q”称作 P与Q,蕴涵式，,记作PQ，为,蕴涵联结词。,P,Q,P Q,T,T,T,T,F,F,F,T,T,F,F,T,第11页,在PQ中，Q是P必要条件，P是Q充分条件。表示自然语言,“只要P就Q”，,“P仅当Q”，,“只有Q，才P”,注意：1.在自然语言中，“假如P，则Q”中P与Q往往有某 种内在联络，但在数理逻辑中，PQ中P与Q不一定有内在联络。,2.在数学中，“假如P，则Q”表示P为真，Q为真逻辑关系，但在数理逻辑中，当P为假时PQ为真。,第12页,例4将以下命题符号化。,(1)只要不下雨，我就骑自行车上班。,(2)只有不下雨，我才骑自行车上班。,(3)若 2+24，则太阳从东方升起。,(3)若 2+24，则太阳从东方升起。,(4)若 2+24，则太阳从西方升起。,(5)若 2+24，则太阳从西方升起。,解：在（1）、（2）中，设P：天下雨；Q：我骑自行车上班。,（1）PQ（2）Q P,在（3）（6）中，设P：2+24；Q：太阳从东方升起；R:太阳从西方升起。,（1）PQ，真值为T （2）PQ，真值为T,（3）PR，真值为F （4）PR 真值为T,第13页,定义1-2.5,设P、Q为两命题，复合命题“P当且仅当 Q”称作 P与Q,等价式，,记作P,Q，,为,等价联结词。,PQ表示P与Q互为充分必要条件,。,P,Q,P Q,T,T,T,T,F,F,F,T,F,F,F,T,第14页,例5将以下命题符号化。,（1）2+24，当且仅当3是奇数。,（2）2+24，当且仅当3不是奇数。,（3）2+24，当且仅当3是奇数。,（4）2+24，当且仅当3不是奇数。,（5）两圆面积相等，当且仅当它们半径相同。,（6）两角相等当且仅当它们是对顶角。,解：（1）（4）设P：2+24；Q：3是奇数。,（1）PQ 真命题,（2）PQ 假命题,（3）PQ假命题,（4）PQ真命题,（5）设P：两圆面积相等；Q：两圆面积相同。,PQ真命题,（6）设P：两角相等；Q：它们是对顶角。,PQ假命题,第15页,4.5种联结词优先级次序：，,第16页,1-3命题公式与翻译,1.命题公式,命题公式：由命题常量、,命题变元,、联结词、括号 等组成符号串。,命题公式中命题变元称作命题公式分量。,第17页,定义13.1,（1）单个命题常量或命题变 元,Q,R,Pi,Qi,Ri,，F，T是合式公式。,（2）假如A是合式公式，则（A）也是合式公式。,（3）假如A、B是合式公式，则（AB）、（A B）、（AB）、（AB）也是合式公式。,（4）只有有限次地应用（1）（3）组成符号串才是合式公式。,例：P,P,(P),(0P),P(PQ),(PQ)R)(R)是公式；,PQR,(P),PQ)不是公式。,第18页,2.翻译,翻译就是把自然语言中有些句子符号化。,复合命题符号化基本步骤：,（1）分析出各简单命题，将它们符号化。,（2）使用适当联结词，把简单命题逐一联结起来，组成复合命题符号化表示。,第19页,例 将以下命题符号化。,（1）小王是游泳冠军或是百米冠军。PQ,（2）小王现在在宿舍或在图书馆。PQ,（排斥性或，不可能同时为真）,(3)选小王或小李中一人当班长。,（P Q）（PQ）或 （PQ）,（排斥性或，可能同时为真）,P,Q,原命题,PQ,（PQ）,T,T,F,T,F,T,F,T,F,T,F,T,T,F,T,F,F,F,T,F,第20页,(4)假如我上街，我就去书店看看，除非我很累。,R(PQ)或（RP）Q （除非：假如不）,(5)王一乐是计算机系学生，他生于1968年或1969年，他是三好学生。P（Q R）S,（6）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。,A：我们要做到身体好,B：我们要做到学习好,C：我们要做到工作好,P：我们要为祖国四化建设面奋斗。,命题符号化形式为：（ABC）P,第21页,14真值表与等价公式,1.真值表,定义14.1,含n个（n1）个命题变元（分量）命题公式，共有2,n,组真值指派。将命题公式A在全部真值指派之下取值情况列成表，称为A真值表。,结构真值表步骤：,(1)找出命题公式中所含全部命题变元P1,P2,Pn。列出全部可能真值指派。,(2)对应每种真值指派，计算命题公式各层次值，直到最终计算出命题公式值。,第22页,例1 结构求PQ真值表。,P,Q,P,PQ,T,T,F,T,T,F,F,F,F,T,T,T,F,F,T,T,第23页,例2 给出（PQ）P真值表。,P,Q,PQ,P,（PQ）P,T,T,T,F,F,T,F,F,F,F,F,T,F,T,F,F,F,F,T,F,第24页,例3 给出（PQ）（PQ）真值表。,P,Q,P,Q,PQ,PQ,（PQ）（PQ）,T,T,F,F,T,F,T,T,F,F,T,F,F,F,F,T,T,F,F,F,F,F,F,T,T,F,T,T,第25页,例4 给出（PQ）（PQ）真值表。,P,Q,PQ,（PQ）,P,Q,PQ,（PQ）（PQ）,T,T,T,F,F,F,F,T,T,F,F,T,F,T,T,T,F,T,F,T,T,F,T,T,F,F,F,T,T,T,T,T,由以上例子能够看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为T（F）。如例4和例2,第26页,2等价公式,从真值表中能够看到，有些命题公式在分量各种指派下，其对应真值都完全相同，如PQ与PQ对应真值相同。,P,Q,P,PQ,PQ,T,T,F,T,T,T,F,F,F,F,F,T,T,T,T,F,F,T,T,T,（PQ）（PQ）与PQ对应真值相同。,第27页,定义14.2,给定两个命题公式A和B，设P,1,，P,2,，P,n,为全部出现于A和B中原子变元,若给P,1,，P,2,，P,n,任一组真值指派,A和B真值都相同,则称A和B是,等价,或,逻辑相等,。记作AB。,例5 证实PQ（PQ）（QP）,证实 列出真值表,P,Q,PQ,QP,(PQ）(QP）,PQ,T,T,T,T,T,T,T,F,F,T,F,F,F,T,T,F,F,F,F,F,T,T,T,T,第28页,24个主要等价式,PP 双重否定律,PPP等幂律,PPP,PQQP交换律,PQQP,（PQ）RP（QR）结合律,（PQ）RP（QR）,P（QR）（PQ）（PR）分配律,P（QR）（PQ）（PR）,（PQ）PQ 德摩根律,（PQ）PQ,第29页,P（PQ）P吸收律,P（PQ）P,PT T零律,PF F,PFP同一律,PT P,PP T排中律,PP F矛盾律,PQ PQ蕴涵等价式,P,Q（PQ）（QP）等价等价式,PQ QP假言易位,P,Q P,Q等价否定等价式,（PQ）（PQ）P归谬论,其中P、Q和R代表任意命题公式,。,第30页,例6 验证吸收律P（PQ）P和,P（PQ）P,P,Q,P,Q,P（PQ）,PQ,P（PQ）,T,T,T,T,T,T,T,F,F,T,T,T,F,T,F,F,T,F,F,F,F,F,F,F,第31页,定义1-4.3,假如X是合式公式A一部分,且X本身也是一个合式 公式,则称X为公式 A子公式。,定理14.1,假如X是合式公式A子公式，若XY，假如将A中X用Y来置换，所得到公式B与公式A等价，即AB。,证实,因为在对应变元任一个指派下，X与Y真值相同，故以Y取代X后，公式B与公式 A在对应指派下，其真值必相同，故AB。,满足定理14.1置换称为等价置换（等价代换）,第32页,例7 证实PQ（PQ）,证实 PQ PQ，（依据蕴涵等价式）,PQ（Pq），（德摩根律）,即Pq（Pq）,第33页,例8 证实P(QR)(PQ)R,证实 P,(QR),P(,QR,)（蕴涵等价式）,P(QR)（蕴涵等价式）,(PQ)R（结合律）,(PQ)R（德摩根律）,(PQ)R（蕴涵等价式）,第34页,例9 证实 P(PQ)(PQ),证实 P,P,1,(同一律),P(QQ)（排中律）,(PQ)(PQ)（分配律）,第35页,练习 1.证实 Q(PQ)P)T;,2.证实 (PP)(QQ)R)F,3.证实 (PQ)PP,第36页,1,证实Q(PQ)P),Q(PP)(PQ)（分配律）,Q(F(PQ)（矛盾律）,Q(PQ)（同一律）,Q(PQ)（德摩根律）,(QQ)P（结合律）,TP（排中律）,T（零律）,第37页,2.证实(PP)(QQ)R),T(QQ)R)（排中律）,T(FR)（矛盾律）,TF（零律）,TF（蕴涵等值式）,FFF（等幂律）,第38页,3.证实 (PQ)P,(PQ)P（蕴涵等价值式）,P（吸收律）,第39页,1-5 重言式与蕴涵式,定义15.1,给定一命题公式，若不论对分量作什么样指,派，其对应真值永为T，则称该命题公式 为,重言式,或,永真式,。,定义15.2,给定一命题公式，若不论对分量作什么样指,派，其对应真值永为F，则称该命题公式 为,矛盾式,或,永假式,。,第40页,定理15.1,任何两个重言式合取或析取，依然是一个重言式。,定理15.2,一个 重言式，对同一分量，都 用任何合式公式 置换，其结果仍为一重言式。,证实,因为重言式真值与分量指派无关，帮对同一分量以任何合式公式置换后，重言式真值仍永为真。,对于矛盾式也有类似于定理15.1和定理51.2结果。,第41页,例1 证实（PS）R）,（P,S）R）为重言式。,证实 因为 PP,T，用,（PS）R）置换P得,（PS）R）（PS）R）T,第42页,定理15.,3 设A、B为两命题公式,A,B，当且仅当,AB 为一个重言式。,证实 若,AB，则A、B有相同真值，即有AB 永为T。,若 AB 为重言式，则AB 永为T，故A、B真值相同，即AB。,第43页,例2 证实（PQ）（PQ）,证实 做（PQ）（PQ）真值表。,P,Q,PQ,P,Q,（PQ）,PQ,（PQ）PQ,T,T,T,F,F,F,F,T,T,F,F,F,T,T,T,T,F,T,F,T,F,T,T,T,F,F,F,T,T,T,T,T,由以上真值表可知，（PQ）PQ 为重言式，依据定理15.3得 （PQ）（PQ）,第44页,定义15.3,当且仅当 P,Q 是重言式时，我们称“P蕴涵Q”，并记作PQ,。,做PQ QP，PQ，Qp 真值表,P,Q,P,Q,PQ,Q,P,QP,P,Q,T,T,F,F,T,T,T,T,T,F,F,T,F,F,T,T,F,T,T,F,T,T,F,F,F,F,T,T,T,T,T,T,由此得 PQ QP，QP PQ，所以要PQ，只要证实QP，反之亦然。,第45页,要证实PQ，即证PQ 是重言式，对于PQ 来说，除P真值取T，Q真值取F这么一个指派时，PQ 真值为F外，其余情况PQ 真值为T，故要征PQ，只要对条件PQ 前件P，指定真值为T，若由此指出Q真值为T，则PQ 为重言式，即PQ 成立；同理，如对条件命题PQ 中，假定后件Q真值为F，若由此推出P真值为F，即推证了QP。故PQ成立。即,若P为T时，推出Q为T,或若Q为F时，推出P为F,则PQ,。,第46页,例1 推证Q（PQ）P,证法1 假定Q（PQ）为T，则Q为T，且PQ 为T。,所以Q为F，PQ 为T，,所以P为F，故P为T。,证法2 假定P为F，则P为T，,若Q为F，则PQ 为F，Q（PQ）为F，,若Q为T，则Q为F，Q（PQ）为F，,所以 Q（PQ）P,第47页,惯用蕴涵式以下：,PQ P,PQ Q,PPQ,PPQ,QPQ,（PQ）P,（PQ）Q,P（PQ）Q,Q（PQ）p,P（PQ）Q,（PQ）（QR）PR,（PQ）（PR）（QR）R,（PQ）（RS）（PR）（QS）,（P,Q）（Q,R）（P,R）,第48页,定理15.,4 设P、Q为任意两个 命题公式，,P,Q 充分,必要条件是,P,Q 且,Q,P,证实,若PQ，则,P,Q为重言式。,因为PQ （,P,Q）（QP），,故 PQ为T，且QP 为T，,因为PQ 且QP成立。,反之，若PQ 且QP，,则PQ为T，且QP 为T，,所以PQ （PQ）（QP）为T，,即P,Q,这个定理也能够作为两个公式等价定义。,第49页,蕴涵几个惯用性质：,（1）设A、B、C为合式公式，若AB且A为重言式，则B也是重 言式。,证实 因为 AB 永为T，所以当A为T时，B必T。,（2）若AB，BC，则 AC,证实 由AB，BC 得AB，BC 为重言式,所以（AB）（BC）为重言式，,依据（PQ）（QR）PR,所以（AB）（BC）AC，,由性质（1）得：AC为重言式，即 AC,第50页,（3）AB，且AC，那么A（BC）,证实 由假设知AB，AC为重言式。,设A这T，则B、C为T，,故BC为T，,所以A（BC）为T，,若A为F，则A（BC）为T，,所以A（B,C）,第51页,（4）若AB 且 CB，则AC,B,证实 因为AB 为T，CB为T，,故（,A,B）（C B）为T，,则（AC）B 为T，,即（AC）B为T，,即 （AC）B为T，,所以（AC）,B,第52页,16 其它联结词,定义16.3,设P、Q是两个命题公式，复合命题P Q称作P和Q“与非”。,PQ（PQ）,P,Q,P Q,T,T,F,T,F,T,F,T,T,F,F,T,第53页,联结词“”几个性质：,（1）PP （PP）p,（2）（PQ）（PQ）（PQ）PQ,（3）（PP）（QQ）PQ,（Pq）PQ,第54页,定义16.3,设P、Q是两个命题公式，复合命题P,Q称作P和Q“或非”。,P,Q（P,Q）,P,Q,P Q,T,T,F,T,F,F,F,T,F,F,F,T,第55页,联结词“,”几个性质：,（1）P,P （PP）p,（2）（P Q）,（PQ）（PQ）PQ,（3）（PP）（QQ）PQ PQ,当有n个命题变元时，可组成2,2,n,种不等价命题公式，如n2时，有16种不等价命题公式。，见27页表16.5。,第56页,最小联结词组：对于任何一个命题公式，都能由仅含这些联结词命题公式等价代换。,因为（1）（P,Q）,（PQ）（QP）,（2）（PQ）PQ,（3）PQ（P Q）,（4）PQ（Pq）,故由“”、“”、“”，“”、“”这五个联结词组成命题公式，必能够由，或，组成命题公式所替换。,第57页,17 对偶与范式,定义17.1,在给定命题公式A中，将换成，换成，若有特殊变元F和T亦相互取代，所得命题公式A*称为A对偶式。,A和A*互为对偶式。,例1:PQ与 PQ,(PQ)与(PQ),(PQ)R与 (PQ)R,(PT)Q 与(P F)Q 均为对偶式.,例2：PQ,、,P Q对偶式。,解：PQ(PQ)，PQ对偶式为(PQ),P Q（PQ）,，,P Q对偶式为(PQ),第58页,定理17.1,设A和A*互为对偶式,P,1,P,2,P,n,，是出现在A和A*中全部命题变元,则,A(P,1,P,2,P,n,)A*(P,1,P,2,P,n,),A(P,1,P,2,P,n,)A*(P,1,P,2,P,n,),例:设 A(P,Q,R)P(QR),得:A*(P,Q,R)P(QR),(1)由知:A(P,Q,R)P(QR),由知:A*(P,Q,R)P(QR),所以:A(P,Q,R)A*(P,Q,R),类似地,有A(P,Q,R)A*(P,Q,R),第59页,定理17.2,设P,1,P,2,P,n,是出现有命题公式A和B中全部命题变元，若A B，则A*B*。,证实：因为A B，,即A(P1,P2,Pn)B(P1,P2,Pn)是重言式，,A(P1,P2,Pn)B(P1,P2,Pn)是重言式，,故A(P1,P2,Pn)B(P1,P2,Pn),由定理17.1得,A*(P1,P2,Pn)B*(P1,P2,Pn),所以A*B*,第60页,例4 假如A(P,Q,R)是P（Q（RP），求它对偶式A*(P,Q,R)。并求与A及 A*等价，但仅包含联结词“”、“”、“”公式。,解：因 A(P,Q,R)是 P（Q（RP）,故 A*(P,Q,R)是P（Q（RP）,但P（Q（RP）,P（Q（R,P）,（P（Q（RP）,所以P（Q（RP）(P（Q（RP）),第61页,定义17.2,一个命题公式 称为,合取范式,，当且仅当它含有形式A,1,A,2,A,n,（n1）。其中,A,1,，A,2,，A,n,都是命题变元或其否定所组成析取式。,例,P(PQ)(PP)(PR),定义17.3,一个命题公式 称为,析取范式,，当且仅当它含有形式A,1,A,2,A,n,（n1）。其中A,1,，A,2,，A,n,都是命题变元或其否定所组成合取式。,例(PQR),(PQ),(,PQR,),第62页,求合取范式或 析取范式步骤：,（1）将公式中联结词化归成、。,（2）将消去或内移。,（3）利用分配律、交换律求合取范式或析取范式。,（求合取范式：对；,求析取范式：对 ）,注意任何命题析取范式和合取范式都不是唯一。,第63页,例求下面命题公式合取范式和析取范式。,（PQ）R）P,解（1）求合取范式,（PQ）R）P,（PQ）R）P,(PQ)R)P,(PQ)R)P,(PQ)R)P,(PQ)R)P,(PQ)R)P,(PQP)(RP),（PQ）(RP),(2)求析取范式,(PQ)R)P,(PR)(QR)P,P（P,R）,(QR),P(QR),第64页,练习：求下面命题公式合取范式和析取范式。,（1）求合取范式,(PQ),R,(PQ),R,(PQ)R)(R(PQ),(PQ)R)(R(PQ),(PQ)R)(RPQ),(PR)(QR)(RPQ),（2）求析取范式,(PQ,),R)(RPQ),（(PQ)(RPQ)）(R(RPQ),(PQ)R)(PQ)P)(PQ)Q),(RR)(RP)(RQ),(PQR),(PPQ),(,PQQ,),(RR),(PR)(QR),(PQR)(PR)(QR),第65页,定义17.4,n个命题变元合取式，称作布尔合取或小项，其中变元与它否定不能同时存在，但二者必须出现且仅出现一次。,n个命题变元 共有2,n,个小项。,例两个命题变元 P和Q，其小项为：PQ，PQ，PQ，PQ,第66页,3个命题变项P、Q、R可形成8个小项：,m,000,PQR,m,001,PQR,m,010,PQR,m,011,PQR,m,100,PQR,M,101,PQR,m,110,PQR,m,111,PQR,第67页,小项性质：,（1）每一个小项当其真值指派与编码相同时，其真值为T，其余均为F。,（2）任意两个不一样小项合取永为F。,（3）m,0,m,1,m,2,m,3,m,4,m,5,m,6,m,7,T,第68页,定义17.3,对于给定命题公式，假如有一个等价公式，它仅由小项析取所组成，则该等价式称作原式主析取范式。,定理17.3,在真值表中，一个 公式真值为T指派所对小项析取，即为此公式主析取范式。,第69页,例6给定P Q，PQ和（PQ），求这些公式主析取范式。,解：真值表以下：,P,Q,P,Q,PQ,（PQ）,T,T,T,T,F,T,F,F,T,T,F,T,T,T,T,F,F,T,F,T,故P Q（PQ）（PQ）（PQ）,PQ（PQ）（PQ）（PQ）,（PQ）（PQ）（PQ）（PQ）,第70页,例7 设一公式A真值表以下，求公式 A主析取范式。,P,Q,R,A,T,T,T,T,T,T,F,F,T,F,T,F,T,F,F,T,F,T,T,F,F,T,F,F,F,F,T,F,F,F,F,T,解 公式A主析取范式 为：,A（PQ,R）（PRR）（PQR）,第71页,例8 求（PQ）（PR）（QR）主析取范式。,解：原式（PQ（RR）,（PR（QQ）,（QR（Pp）,（PQR）（PQR）,（PQR）（PQR）,（PQR）（PQR）,（PQR）（PQR）,（PQR）（PQR）,第72页,例9求P,（P,Q）（QP）主析取范式。,解：原式P（P,Q）,（QP）,P（PQP）（QQP）,P（QP）,P（QQ）（PQ）,（PQ）（PQ）（PQ）,第73页,求主析取范式步骤：,（1）求析取范式。,（2）去掉永假析取项。,（3）去掉重复合取项、合并相同变元。,（4）对合取项补入没出现命题变元。（PP）,第74页,定义17.6,n个命题变元析取式，称作布尔析取或大项，其中变元与它否定不能同时存在，但二者必须出现且仅出现一次。,n个命题变元 共有2n个小项。,例 两个命题变元 P和Q，其小项为：PQ，,PQ，PQ，PQ,第75页,3个命题变项P、Q、R可形成8个大项：,M,000,PQR,M,001,PQ,R,M,010,P,QR,M,011,P,Q,R,M,100,PQR,M,101,PQ,R,M,110,P,QR,M,111,P,Q,R,第76页,大项性质：,（1）每一个大项当其真值指派与编码相同时，其真值为F，其余均为T。,（2）任意两个不一样大项析取永为T。,（3）M,0,M,1,M,2,M,3,M,4,M,5,M,6,M,7,F,第77页,定义17.7,对于给定命题公式，假如有一个等价公式，它仅由大项合取所组成，则该等价式称作原式主合取范式。,定理17.4,在真值表中，一个公式真值为F指派所对大项合取，即为此公式主合取范式。,第78页,例10 利用真值表求（PQ）（PR）主合取范式与主析取范式。,P,Q,R,P,Q,P,R,（PQ）（PR）,T,T,T,T,F,T,T,T,F,T,F,T,T,F,T,F,F,F,T,F,F,F,F,F,F,T,T,F,T,T,F,T,F,F,F,F,F,F,T,F,T,T,F,F,F,F,F,F,第79页,主合取范式：（,PQ,R）（,PQR）（P,QR）（PQR）,主析取范式：（PQR）（PQR）（PQR）（PQR）,第80页,求主合取范式步骤：,（1）求合取范式。,（2）去掉全部为T合取项。,（3）合并相同析取项和变元。,（4）补入没出现命题变元。（即添加PP）,第81页,例11 求,（PQ）（PR）主合取范式。,解：原式（PQ）P）（PQ）R）,（,Pp,）（Qp）（PR）（QR）,（Qp）（PR）（QR）,（QP（RR）,（PR（QQ）,（QR（PP）,（QPR）（QPR）,（PRQ）（PRQ）,（QRP）（QRP）,（PQ,R）（P,Q,R）,（P,Q,R）（PQR）,第82页,用,表示小项析取,用表示大项合取,比如,（PQ）（PR）,（PQR）（PQR）,（PQR）（PQR）,M,000,M,010,M,100,M,101,0,2,4,5,m,001,m,011,m,110,m,111,1,3,6,7,第83页,1-8推理理论,推理是从前提推出结论思维过程,前提是指已知命题公式,结论是从前提出发应用推理规则推出来命题公式。前提能够是多个。,定义18.1,设H,1,，H,2,，,，H,n,，C是命题公式，若（H,1,H,2,H,n,）C为重言式,则称C是一组前提H,1,H,2,H,n,有效结论。记作：,H,1,H,2,H,n,C,真值表法,推理方法 直接证法,间接证法,第84页,（1）真值表法,若H,1,，H,2,，,，H,n,都为T行，C也为真；,或若C为假行，H,1,，H,2,，,，H,n,中最少有一个为假,则,H,1,H,2,H,n,C 成立。,第85页,例1 一份统计表格错误或者是因为材料不可靠，或者是因为计算有错误；这份统计表格错误不是因为材料不可靠，所以这份统计表格是因为计算有错误。,解：设 P：统计表格错误是因为材料不可靠。,Q：统计表格错误是因为计算不可靠。,前提是：PQ,，,P ，结论是：Q，即证实,（,PQ）,P Q,P,Q,PQ,P,T,T,T,F,T,F,T,F,F,T,T,T,F,F,F,T,故（PQ）,P Q,第86页,例2 假如张老师来了，这个问题能够得到解答，假如李老师来了，这个问题也能够得到解答，总之张老师或李老师来了，这个问题就能够得到解答。,解：设P：张老师来了。,Q：李老师来了。,R：这个问题能够得到解答。,本题可译为：,（P R）（QR）（PQ）R,第87页,P,Q,R,P,R,Q,R,PQ,T,T,T,T,T,T,T,T,F,F,F,T,T,F,T,T,T,T,T,F,F,F,T,T,F,T,T,T,T,T,F,T,F,T,F,T,F,F,T,T,T,F,F,F,F,T,T,F,第88页,（2）直接证法,就是由一组前提，利用一些公认推理规则，依据已知等价公式或蕴涵公式，推出有效结论。,P规则：前提在推导过程中随时能够引用。,T规则：已经推出公式在以后推导过程中可随时引用。,惯用蕴涵式见43页表18.3,第89页,例1 证实（PQ）,（P,R）,（QS）,S,R,证法1（1）PQ P,（2）,P,Q T（1）E,（3）QS P,（4）PS T（2），（3）I,（5）SP T（4）E,（6）PR P,（7）SR T（5），（6）I,（8）SR T（7）E,第90页,证法2（1）PR P,（2）PQRQ T（1）I,（3）QS P,（4）QRSR T（3）I,（5）PQSR T（2），（4）I,（6）PQ P,（7）SR T（5），（6）I,第91页,例2 证实（WR）V，VCS，SU，C U W,证实,（1）,C U P,（2）U T（1）I,（3）SU P,（4）S T（2）,（3）I,(5)C T（1）I,(6)C S T(4),(5)I,(7)(C S)T(6)E,(8)（WR）V P,(9)V(CS)P,(10)（WR）(CS)T(8),(9)I,(11)(（WR）T(7),(10)I,(12)W R T(11)E,(13)W T(12)E,第92页,(3)间接证法1(归谬法),要证 H,1,H,2,H,n,C,即要证 H,1,H,2,H,n,C 为重言式,H,1,H,2,H,n,C,(H,1,H,2,H,n,)C,(H,1,H,2,H,n,C),所以只要证 H,1,H,2,H,n,C 为矛盾式.,第93页,例3 证实 AB,(BC)可逻辑推出A,证实(1)AB P,(2)A P(附加前提),(3)(BC)P,(4)BC T(3)E,(5)B T(1),(2)I,(6)B T(4)I,(7)BB(矛盾)T(5),(6)I,第94页,例4 证实(PQ)(PR)(QS)SR,证实(1)(SR)P,(2)SR T(1)E,(3)PQ P,(4)PQ T(3)E,(5)QS P,(6)PS T(4),(5)I,(7)SP T(6),(8)(S,R,)(P,R,)T(7)I,(9)PR T(2),(8)I,(10)PR P,(11)P R T(10)E,(12)(P R,)T(11)E,(13),(P R,),(P R,)(矛盾)T(9),(12)I,第95页,(4)间接证法2(附加前提法),要证 H1H2Hn RC,只要证 (H1H2Hn)(R C)为重言式,(H1H2Hn)(R C),(H1H2Hn)(R C),(H1H2HnR)C,(H1H2Hn R)C,只要证 (H1H2Hn,R,)C,由(SR)C 证得S(R C)称为,CP规则,。,第96页,例5 证实 A(BC),DA,B 重言蕴涵 DC,证实(1)D P(附加前提),(2)DA P,(3)A T(1),(2)I,(4)A(BC)P,(5)BC T(3),(4)I,(6)B P,(7)C T(5),(6)I,(8)DC CP,第97页,例6 设有以下情况,结论是否有效?,(a)或者是天晴,或者是下雨。,(b)假如是天晴，我去看电影。,(c)假如我去看电影，我就不看书。,结论：假如我在看书则天在下雨。,解 若设 M：天晴。Q：下雨。,S：我看电影。R：我看书。,即证：M,Q，M,S，SR，推出RQ,其中 MQ(M,Q）,第98页,(1)R P（附加前提）,(2)SR P,(3)R S T(2)E,(4)S T(1),(3)I,(5)MS P,(6)M T(4),(5)I,(7)(M Q）P,(8)M Q T(7)E,(9)(MQ)(QM)T(8)E,(10)QM T(9)I,(11)MQ T(10)E,(12)Q T(6),(11)I,(13)RQ CP,第99页,第二章 谓词逻辑,原子命题是命题逻辑研究基本单位,没有对原子内部结构及其相互之间逻辑关系进行分析,这么就无法处理一些简单而又常见推理问题。,比如:全部人都是要死，苏格拉底是人，所以,苏格拉底是要死。,P:全部人是要死.,Q:苏格拉底是人.,R:所以,苏格拉底是要死,PQ,R,不是重言式。,第100页,21 谓词概念与表示,原子命题由主语和谓语两部分组成。,主语普通是客体。,客体：能够是一个详细事物，也能够是一个抽象事物。是命题所研究对象。,谓词：用以刻划客体性质或客体之间性质。,例 李明是一个学生。,李明比王杰高。,哥白尼指出地球绕着太阳转。,第101页,谓词用大写字母表示。,客体名称用小写字母表示。,客体常元：,表示详细或特定客体词。,普通用小写字母a,b,c,表示。,客体变元：,表示抽象或泛指客体词。,普通用小写字母x,y,z,表示。,比如：A表示“是个大学生”，,c表示张三，,e表示李四，,则 A（c）表示“张三是个大学生”，,A（e）表示“李四是个大学生”，,第102页,“,b是A”类型命题可用A（b）表示。,两个客体之间关系命题可表示为B（a,b）。,A（b）为一元谓词。,B（a,b）为二元谓词。依这类推。,单独一个谓词不是命题，只有将变元x,y,z等取特定客体时，才确定了一个命题。,第103页,22 命题函数与量词,定义22.1,由一个谓词，一些客体变元组成表示式称为,简单命题函数,。,例 B（x,y）。,n元谓词就是有n个客体变元命题函数。,当n0时，它本身就是一个命题。,第104页,由一个或几个简单命题函数以及联结词组合而成表示式称为,复合命题函数,。,例1（1）2是素数且是偶数。,解：设A（x）：x是素数；,B（x）：x是偶数；,a：2,则命题表示为：A（a）,B（a）,（2）假如2大于3，则2大于4。,解：设L（x,y）：x大于y；,a：2；b：3；c：4,则命题表示为：L（a,b）,L（,a,c）。,第105页,（,3）假如张明比李民高，李民比赵亮高，则张明比赵亮高。,解：设 H（x,y）：x比y高；,a：张明；b：李民；c：赵亮。,则命题符号化为：,H（a,b）H（b，c）,H（,a,c）。,命题函数不是命题，只有客体变元取特定客体名称时，才能成为命题。,第106页,个体域,：客体变元取值范围。,个体域能够是有限，也能够是无限。,例 学生、工人，实数，a,b，c。,全总个体域：,宇宙间一切事物。,第107页,量词：表示数量词。,全称量词“,”,用来表示“对全部”、“每一个”，“对任何一个”。,例2（1）全部人都是要呼吸。,解：设M（x）：X是人；H（x）：x要呼吸。,则符号化为：（,x,）（M（x）,H（x）,域为全总域。,第108页,（2）每个学生都要参加考试。,解：设P（x）：x是学生；Q（x）：x要参加考试。,符号化为:,（,x,）（P（x）Q（x）,(3)任何整数或是正或是负。,解：设 I（x）：x是整数；,R（x）：X是正数；,M（x）：x是负数。,符号化为：（,x,）（I（x）R（x）,M（x）,第109页,存在量词“”：,表示“存在一些”。,例3（1）存在一个数是质数。,解：设 P（x）：x是质数。,符号化为：（x,）（,P（x）,（2）一些人是聪明。,解：设 M（x）：x是；R（x）：x是聪明。,符号化为：（x,）（M,（x）R（x）,第110页,注意：,（1）在不一样个体域中，命题符号化形式可能不一样。,（2）假如事先没有给出个体域，都应以全总个体域为个体域。,（3）在引入特征谓词后，使用全称量词与存在量词符号化形式是不一样。,对全称量词，特征谓词常作蕴涵前件；,对存在量词，特征谓词常作合取 项。,第111页,例：（1）全部人都是要死。,（2）有人活百岁以上。,解：,第一个情况：考虑个体域D为人类集合。,（1）符号化为：x F(x)。,其中F(x)：x是要死。,（2）xF(x)。其中F(x)：x活百岁以上。,第二种情况：考虑个体域为全总个体域，,对全部个体而言，假如它是人，则它是要死。,存在着个体，它是人而且活百岁以上/,引进特征谓词：M（x）：X是人。,（1）符号化为：x（M（x）F(x)）,（2）符号化为：x（M（x）F(x)）,第112页,23 谓词公式与解释,原子谓词公式：若P（x1,x2,xn）是n元谓词，则称P（x1,x2,xn）是,原子谓词公式,。,其中x1,x2,xn是客体变元。,例 Q，R（x），A（x,y),A(f(x),y),A(a,y,z),第113页,合式公式,定义以下：,（1）原子公式是合式公式；,（2）若A是合式公式，则（A）也是合式公式；,（3）若A、B是合式公式，则（AB）、（AB）、（A B）、（A,B）
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
