命题逻辑典型问题解析.doc

湖南电大教学指导中心袈袅膁薈薇肁肇薇蚀袄莆薆螂聿节蚅袄袂膈蚅薄肈肄蚄蚆袀蒂蚃衿肆莈蚂羁罿芄蚁蚁膄膀芈螃羇肆芇袅膂莅芆薅羅芁莅蚇膁膇莄蝿羄肃莃羂螆蒁莂蚁肂莇莂螄袅芃莁袆肀腿莀薆袃肅荿蚈肈莄蒈螀袁芀蒇袃肇膆蒆蚂衿膂蒆螅膅肈蒅袇羈莆蒄薇膃节蒃虿羆膈薂螁膂肄薁袃羄莃薁薃螇艿薀螅羃芅蕿袈袅膁薈薇肁肇薇蚀袄莆薆螂聿节蚅袄袂膈蚅薄肈肄蚄蚆袀蒂蚃衿肆莈蚂羁罿芄蚁蚁膄膀芈螃羇肆芇袅膂莅芆薅羅芁莅蚇膁膇莄蝿羄肃莃羂螆蒁莂蚁肂莇莂螄袅芃莁袆肀腿莀薆袃肅荿蚈肈莄蒈螀袁芀蒇袃肇膆蒆蚂衿膂蒆螅膅肈蒅袇羈莆蒄薇膃节蒃虿羆膈薂螁膂肄薁袃羄莃薁薃螇艿薀螅羃芅蕿袈袅膁薈薇肁肇薇蚀袄莆薆螂聿节蚅袄袂膈蚅薄肈肄蚄蚆袀蒂蚃衿肆莈蚂羁罿芄蚁蚁膄膀芈螃羇肆芇袅膂莅芆薅羅芁莅蚇膁膇莄蝿羄肃莃羂螆蒁莂蚁肂莇莂螄袅芃莁袆肀腿莀薆袃肅荿蚈肈莄蒈螀袁芀蒇袃肇膆蒆蚂衿膂蒆螅膅肈蒅袇羈莆蒄薇膃节蒃虿羆膈薂螁膂肄薁袃羄莃薁薃螇艿薀螅羃芅蕿袈袅膁薈薇肁肇薇蚀袄莆薆螂聿节蚅袄袂膈蚅薄肈肄蚄蚆袀蒂蚃衿肆莈蚂羁罿芄 第一章 命题逻辑 典型问题解析考试知识点：命题符号化，命题公式的类型，求命题公式的真值表，主合取（析取）范式，命题逻辑的形式证明. (15%)学习要点：1. 理解六个联结词概念：P(否定式)； PQ(合取式)； PQ(析取式)；PQ(蕴含式)； PQ(等价式)； PV Q异或式。熟练掌握求给定公式真值表的方法。2. 理解永真式(重言式)、永假式(矛盾式)和可满足式等概念。 记住基本等值式，掌握用真值表法和等值演算法判别公式类型和公式等值变换的方法。3. 理解析取(合取)范式概念，熟练掌握利用基本等值式将公式化为析取(合取)范式的方法。4. 熟练掌握求主析取(合取)范式的方法。5. 掌握判断重言蕴含式(推理是否有效)的五种方法(1) 真值表法；(2) 等值演算法(记住基本等值式)；(3) 主析取(合取)范式法；(4) 直接证法：掌握P规则和T规则，及常用重言蕴含式、等值式。(5) 间接证法(反证法)：掌握CP规则。 本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论。典型问题解析：1.命题等值式的证明（化简）方法：h真值表法：列出真值表，比较两个公式的真值是否完全相同。完全相同，则两个公式等值。（可以化简后列真值表）h等值演算法：利用基本等值式(16个)，对给定公式进行等值推导。h主范式法：两个公式的主范式相同，则两个公式等值。例1.求命题公式（）的真值表。解：列真值表为 （）例2. 证明：P(QR)PQR.证明:方法1真值表法. 列公式P(QR)与PQR的真值表PQRQRP(QR)PQPQR000110 1001110 1010010 1011110 1100110 1101110 1110001 0111111 1由表可知，公式P(QR)与PQR的真值完全相同，故P(QR)PQR.证明:方法2 等值演算法.P（QR）P(QR) (等值蕴含式)P(QR) (等值蕴含式)（PQ）R (结合律)(PQ)R (摩根律)PQR (等值蕴含式)所以，P（QR）(PQ)R证明:方法3 主范式法.P(QR)P(QR)PQR(主合取范式)PQR(PQ)RPQR(主合取范式)P(QR)与PQR的主合取范式相同，故P(QR)PQR。例3. 化简下式：(ABC)(ABC)解：(ABC)(ABC) 2.命题公式类型的判别 方法：h真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.h等值演算法,利用基本等值式，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式。既非永真，也非永假，成为非永真的可满足式.h主范式法，该公式的主析取范式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式。例4. 判断命题公式(QP)P的类型。解：(QP)P (QP)P (QP)PQPPQ(PP)Q00所以(QP)P是矛盾式。3. 范式h 析取(合取)范式，仅有有限个简单合取式(析取式)构成的析取式(合取式)，就是析取(合取)范式. h 极小项(极大项)，n个命题变项P1,P2,Pn，每个变项或它的否定两者只有其一出现且仅出现一次，第i个命题变项或者其否定出现在从左起第i个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项). h 主析取范式(主合取范式)， 含有n个命题变项的命题公式，如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值，则该等值式称为原命题公式的主析取(合取)范式。每项含有n个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式.h求析取(合取)范式的步骤： 将公式中的联结词都化成，(即消去联结词，)； 将否定联结词消去或移到各命题变项之前； 利用分配律、结合律等，将公式化为析取(合取)范式。h求主析取范式(主合取范式)的方法：h真值表法 在命题公式的真值表中，真值为1的指派所对应的极小项的析取，为此命题公式的主析取范式；在命题公式的真值表中，真值为0的指派所对应的极大项的合取，为此命题公式的主合取范式；h等值演算法 利用等值演算法，求命题公式A的主析取(合取)范式的步骤： 求公式A的析取(合取)范式； 若析取(合取)范式的某个合取项(析取项)B不含有命题变项Pi或Pi，则添加PiPi(PiPi)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全； “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如PP(PP)用0(1)替代. 用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如PP(PP)用P替代，mimi(MiMi)用mi(Mi)替代。 将极小(极大)项按由小到大的顺序排列，用S(P)表示。例5. 求公式（PQ）R的主合取范式.（P26-3）解：真值表法 PQR（PQ）R极小项极大项0000PQR0011PQR0100PQR0111PQR1000PQR1011PQR1101 PQR1111PQR（PQ）R=（PQR）（PQR）（PQR）（PQR）（PQR） 为主析取范式； （PQ）R=（PQR）（PQR）（PQR） 为主合取范式。 等值演算法：（PQ）R（析取范式）=（PQ（RR）（PP）（QQ）R）=（PQR）（PQR）（PQR）（PQR）（PQR） =（PQR）（PQR）（PQR）（PQR）（PQR）（主析取范式）。简记为（1，3，5，6，7） （PQ）R=（PR）（QR） （合取范式）=（P（QQ）R）（PP）QR） =（PQR）（PQR）（PQR）（PQR）=（PQR）（PQR）（PQR） （主合取范式）简记为（0，2，4） 例6.求公式的主合取范式和主析取范式. 解：先将公式 化为合取范式. (去掉) (去掉) (合取范式)(添齐命题变项) 所求主析取范式为主合取范式的缺项所对应的三个极小项，即为m1m6m7或通过求析取范式求主析取范式. (去掉) (去掉) (合取范式) 注：也可以用列真值表的方法，求主析取或主合取范式，4. 命题演算的推理理论设A1,A2,An,C是命题公式，如果是重言式，称C是前提集合 A1,A2,An的有效结论或A1,A2,An逻辑地推出C。记作掌握演绎或形式证明，要理解并掌握14个重言蕴含式(即I1I14)，17个等值式(E1E17)；二是会使用三个规则(P规则、T规则和CP规则)。推理方法有：真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前提证明法和间接证明法)h真值表法：，A1,A2,An的真值都为1时，C也要为1；C为0时，A1,A2,An的真值至少有一个为0.h等值演算法: ,是重言式。h主析取范式法：,是重言式。即公式的主析取范式的极小项齐全。（全体极小项的析取式为重言式）h直接证明法：从前提出发，利用P规则和T规则，及常用14个重言蕴含式、和17个等值式，推演出结论。h间接证明法：(1) 附加前提证明法:条件：结论以蕴含的形式出现。则把B作为附加前提使用，只要推出结论C即可。即证明即可。(2)反证法：把作为附加前提使用，推出矛盾的结论。例7. 试证明：(等值演算法)证明： 欲证明，只需证明是重言式，即其真值是1. 例8. 试证明： (附加前提证明法)证明： (1) S CP规则(2) SP P(3) P (1),(2)析取三段论(4) P(QR) P(5)QR (3),(4)假言推理(6)Q P(7)R (5),(6)假言推理例9. 构造下面推理的证明 前提 R Q，RS，S Q，P Q 结论P证明：用反证法： （1） P CP ，结论之否定作为附加前提 （2） P Q P （3） Q T （1）（2），假言推理 （4） S Q P （5） S T （3）（4），拒取式 （6） R Q P （7） R T （3）（6），拒取式 （8） RS T（5）（7），合取引入 （9） （RS） T （8）德 摩根律 （10） RS P （11） （RS）（RS） T （9）（10），合取引入 （12） P 例10. 用推理规则证明(直接证明法)PQR，SU，RS，UW，WPQ 证明： （1） W P （2） U W P （3） W U T （2），假言易位 （4）U T （1）（3），假言推理 （5）SU P （6）S T （4）（5），析取三段论 （7）RS P （8）R T （6）（7），析取三段论 （9）PQ R P （10）R （PQ） T（9），假言易拉 （11）（PQ） T （8）（10），析取三段论 （12）PQ T（11），德 摩根律 莅芄螈螄羂莇薁螀羁蕿袆聿羀艿虿羅罿莁袅袁羈蒃蚇螇羇薆蒀肅肆芅蚆羁肆莈葿袇肅薀蚄袃肄芀蒇蝿肃莂螂肈肂蒄薅羄肁薇螁袀肀芆薃螆膀莈蝿蚂腿蒁薂羀膈膀螇羆膇莃蚀袂膆蒅袅螈膅薇蚈肇膄芇蒁羃膄荿蚇衿芃蒂葿螅节膁蚅蚁芁芄蒈肀芀蒆螃羅艿薈薆袁芈芈螁螇芈莀薄肆芇蒂螀羂莆薅薃袈莅芄螈螄羂莇薁螀羁蕿袆聿羀艿虿羅罿莁袅袁羈蒃蚇螇羇薆蒀肅肆芅蚆羁肆莈葿袇肅薀蚄袃肄芀蒇蝿肃莂螂肈肂蒄薅羄肁薇螁袀肀芆薃螆膀莈蝿蚂