《四川大学离散数学第二章》由会员分享，可在线阅读，更多相关《四川大学离散数学第二章（29页珍藏版）》请在金锄头文库上搜索。
1、习题课1习题课1- 命题逻辑- 命题逻辑2014 秋季2014 秋季第一章 命题逻辑 总 结第一章 命题逻辑 总 结一、基本概念一、基本概念命题命题命题的真值原子命题、复合命题逻辑联结词（、）命题的真值原子命题、复合命题逻辑联结词（、）命题公式命题公式公式的解释永真式(重言式)永假式(矛盾式，不可满足公式)可满足式公式的解释永真式(重言式)永假式(矛盾式，不可满足公式)可满足式命题公式的等价命题公式的等价基本等价式基本等价式命题定律替换规则（定理）对偶式对偶原理命题定律替换规则（定理）对偶式对偶原理范式范式句节、子句、短语、析取范式、合取范式句节、子句、短语、析取范式、合取范式极小项-主析取范
2、式极小项-主析取范式极大项-主合取范式极大项-主合取范式命题公式的蕴涵命题公式的蕴涵基本蕴含（关系）式基本蕴含（关系）式推理规则推理规则 P规则（称为前提引用规则） 规则（逻辑结果引用规则） 规则（附加前提规则） P规则（称为前提引用规则） 规则（逻辑结果引用规则） 规则（附加前提规则）二、基本方法二、基本方法1、应用基本等价式及置换规则进行等价演算2、求主析取（主合取）范式的方法、应用基本等价式及置换规则进行等价演算2、求主析取（主合取）范式的方法1）公式转换法2）真值表技术法1）公式转换法2）真值表技术法主合取范式-主合取范式-在命题公式的真值表中，使公式取值0时的解释所对应的在命题公式的
3、真值表中，使公式取值0时的解释所对应的全部极大项的合取式全部极大项的合取式。主析取范式-主析取范式-在命题公式的真值表中，使公式取值1时的解释所对应的在命题公式的真值表中，使公式取值1时的解释所对应的全部极小项的析取式全部极小项的析取式。3、推理的各种方法3、推理的各种方法（1）直接法（1）直接法（2）利用CP规则（2）利用CP规则（3）反证法（3）反证法4、消解法4、消解法1.命题逻辑表达式的翻译：1.命题逻辑表达式的翻译：除非你已满16周岁，否则只要你的身高不足1.2米就不能乘公园滑行铁道游乐车。除非你已满16周岁，否则只要你的身高不足1.2米就不能乘公园滑行铁道游乐车。解：令P：你能乘坐
4、公园滑行铁道游乐车。Q：你身高不足1.2米。R：你已满16周岁。解：令P：你能乘坐公园滑行铁道游乐车。Q：你身高不足1.2米。R：你已满16周岁。翻译成：(R Q) P翻译成：(R Q) P三、典型例题三、典型例题2、试证明 (P(QR)(P Q R) P2、试证明 (P(QR)(P Q R) P证明：证明： (P(QR)(P Q R) P(QR)(Q R)(P(QR)(P Q R) P(QR)(Q R)（分配律）（分配律） P(QR)P(QR)(QR)(QR) ) (De Morgan定律)(De Morgan定律) PTPT（矛盾律）（矛盾律） P P (同一律)(同一律)3、证明(PQ)
5、 (PQ) (PQ)3、证明(PQ) (PQ) (PQ) 证：证： (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (De Morgan定律)(De Morgan定律) (PQ)P) (PQ)Q) (PQ)P) (PQ)Q) （分配律）（分配律） (PP)(QP)(PQ)(QQ) (QP)(PQ) (PP)(QP)(PQ)(QQ) (QP)(PQ) （矛盾律）（矛盾律） (QP)(PQ) (QP)(PQ) (De Morgan定律)(De Morgan定律) (QP)(PQ) (QP)(PQ) （蕴涵式）（蕴涵式） (PQ) (PQ) （等价式）（等价式）4、 G=()
6、，求公式G的主析取范式和主合取范式。4、 G=()，求公式G的主析取范式和主合取范式。解：首先列出其真值表如下：P Q R P Q R PQPQ（PQ）（PQ）( (PQ)RPQ)R0 0 00 0 01 10 00 00 0 10 0 11 10 01 10 1 00 1 01 10 00 00 1 10 1 11 10 01 11 0 01 0 00 01 11 11 0 11 0 10 01 11 11 1 01 1 01 10 00 01 1 11 1 11 10 01 1极大项极大项极小项极小项PQRPQRPQRPQRPQRPQRPQRPQR PQR PQRPQRPQRPQR PQR
7、 PQRPQR主析取范式 =（主析取范式 =（PQRPQR）（）（PQRPQR） （） （PQRPQR）（）（PQRPQR）（）（PQRPQR） =m） =m1 1 m m3 3 m m4 4 m m5 5 m m7 7主合取范式 =（主合取范式 =（ PQRPQR ）（）（ PQRPQR ）（）（PQRPQR） =M） =M0 0 M M2 2 M M6 6 5、用公式转换法求上题中的主析取和主合取范式 () （PQ）R （PQ）R (PQ5、用公式转换法求上题中的主析取和主合取范式 () （PQ）R （PQ）R (PQ(RR)(RR)( )( (PP)(QQ)(PP)(QQ)R) (P Q
8、R) (P Q R ) （ (P P) R) (P QR) (P Q R ) （ (P P) (QR)(QR)） (PQR)(PQR) (PP) (QR) (PP) (QR) （PQR）（PQR）（PQR） （PQR）(QR)(QR)） (PQR)(PQR) (PP) (QR) (PP) (QR) （PQR）（PQR）（PQR） （PQR）（PQR）（PQR）（PQR ）（PQR ）（主析取范式）（主析取范式）() （PQ）R （PQ）R （PR）（QR） （P() （PQ）R （PQ）R （PR）（QR） （P（QQ）（QQ）R ）（PP）QR） （PQR）（PQR ）（ PQR）R ）（P
9、P）QR） （PQR）（PQR ）（ PQR） （PQR）（PQR） （PQR）（PQR ）（ PQR）（PQR）（PQR ）（ PQR） （主合取范式）（主合取范式）6、将下面一段程序简化If AB then If BC then将下面一段程序简化If AB then If BC then X X ElseElse Y Y End Else If AC thenEnd Else If AC then Y Y ElseElse X X End EndEnd End执行程序段X 的条件为(AB)(BC)(执行程序段X 的条件为(AB)(BC)( (AB)AB) (AC)(AC) (AABC)BC
10、)If AIf ABC then Y Else X EndBC then Y Else X End执行程序段Y的条件为 (AB)执行程序段Y的条件为 (AB)(BC)(BC)( (AB) (AC) AAB) (AC) ABCBC7、习题一 14题7、习题一 14题解：解：由题设 A：A去，B：B去，C：C去，D：D去则满足条件的选派应满足如下范式：由题设 A：A去，B：B去，C：C去，D：D去则满足条件的选派应满足如下范式：（A（CD）（BC）（CD）（A（CD）（BC）（CD）构造和以上范式等价的主析取范式（为什么？）构造和以上范式等价的主析取范式（为什么？）（A（CD）（BC）（CD）（A
11、（CD）（BC）（CD）（AB C D ）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（AB C D ）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）共有四个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：共有四个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：（ABCD），（ABCD），（ABCD）（ABCD），（ABCD），（ABCD）即有三种方案：A和C去，或者A和D去，或者B和D去。即有三种方案：A和C去，或者A和D去，或者B和D去。8、如果今天是星期一，则要进行离散数学或数据结构
12、两门课 程中的一门课的考试；如果数据结构课的老师生病，则不 考数据结构；今天是星期一，并且数据结构的老师生病。 所以今天进行离散数学的考试。8、如果今天是星期一，则要进行离散数学或数据结构两门课 程中的一门课的考试；如果数据结构课的老师生病，则不 考数据结构；今天是星期一，并且数据结构的老师生病。 所以今天进行离散数学的考试。解：解：设 P：今天是星期一；Q：要进行离散数学考试；R：要进行数据结构考试；S：数据结构课的老师生病； 则PQR，SR，PS Q。设 P：今天是星期一；Q：要进行离散数学考试；R：要进行数据结构考试；S：数据结构课的老师生病； 则PQR，SR，PS Q。证:证: PS S ,IPS S ,I1 1 SR R ,ISR R ,I5 5 P ,IP ,I1 1 PQR QR ,IPQR QR ,I5 5 Q ,IQ
