离散数学集合论部分常考××题.docVIP

PAGE PAGE 2 离散数学常考题型梳理 第6章 命题逻辑 一、题型分析 本章主要介绍命题、联结词的概念，命题公式与翻译，真值表与等价公式，重言式与蕴含式，范式和命题逻辑的推理理论等内容。经常涉及到的题型有： 6-1 HYPERLINK /mod/resource/view.php?inpopup=trueid=427 \t _blank 将陈述句翻译成命题公式 6-2 HYPERLINK /mod/resource/view.php?inpopup=trueid=428 \t _blank 求命题公式的真值 6-3 命题公式类型的判断 6-4 等价公式的证明 6-5 求范式和主范式 6-6判断有效结论的直接证法和间接证法 因此，在本章学习过程中希望大家要清楚地知道： 1． HYPERLINK /mod/resource/view.php?inpopup=trueid=427 \t _blank 将陈述句翻译成命题公式 命题表述为具有确定真假意义的陈述句。命题必须具备二个条件：语句是陈述句；语句有唯一确定的真假意义。因此判断一个句子是否为命题，应首先判断它是否为陈述句，再判断它是否有唯一的真值。 例如，“北京是中国的首都”是陈述句，有确定的真假意义，是命题，为真命题。 将陈述句翻译成命题公式关键在于陈述句的逻辑含义要与命题公式的逻辑含义保持一致。因此首先要注意陈述句中表示特殊逻辑关系的词语的含义，其次要掌握五个联结词“?， ?， ?，?，?”所表示的命题间的逻辑关系：“?” 是唯一一元联结词，表示否定；合取联结词“?”在语句中相当于“不但…而且…”，“既…又…”；析取联结词“?”在语句中表示“或”的含义；条件联结词“?”在语句中表示“如果P则Q”或“只有Q，才P”；双条件联结词“?”在语句中相当于“…当且仅当…”。 例如，“我们不能划船，又跑步”。设P：我们划船，G：我们跑步，那么该命题符号化为：或。 2． HYPERLINK /mod/resource/view.php?inpopup=trueid=428 \t _blank 求命题公式的真值 一般将命题的合式公式简称为命题公式。要理解合式公式的递归定义： （1）单个命题变元本身是一个合式公式． （2）若A是合式公式，则┐A是合式公式． （3）若A与B是合式公式，则（A∧B），（A∨B），（A→B）与（A?B）是合式公式． （4）当且仅当能够有限次应用（1）、（2）、（3）所得到的包含命题变元，联结词和括号的符号串是合式公式． 显然，如果对一个命题公式中的命题变元不给以真值指派，则命题公式无真值可言。如果对命题公式中的每个命题变元都赋以真值（1或0），则命题公式就变成了一个有真值的命题，并可求出其真值。 对于特殊的命题公式（永真式和永假式），对命题公式中的命题变元不给以真值指派，利用常用的等价公式也可以求出其真值（永真式为1，永假式为0）。 对命题公式中的所有命题变元指派各种可能的真值组合，就可确定这个命题公式对应的取值，将命题变元的所有真值组合及命题公式对应的取值汇列成表，就得到命题公式的真值表． 如果一个命题公式有n个命题变元，那么命题变元的真值指派就可能出现种不同的组合。在真值表中是包含了命题变元的所有真值指派。例如，如果一个命题公式有3个命题变元，那么命题变元的真值指派就有8种不同的组合，作其真值表就是将这8种真值组合及命题公式对应的真值汇列成表。 要非常熟练地掌握命题公式的真值表作法，因为利用真值表可以判定命题公式类型，验证等价公式和蕴含式，求命题公式的主析取(合取)范式，在推理理论中判别有效结论。 3. 命题公式类型的判断 在各种真值指派下均为真的命题公式，称为重言式或永真式；在各种真值指派下均为假的命题公式，称为矛盾式或永假式；不是矛盾式的命题公式，称为可满足式。 判定命题公式类型的方法： (1) 真值表法：任给命题公式，列出其真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式。 (2) 等值演算法：利用常用的等价公式，对给定公式进行等值推导，若该公式的真值为1，则该公式为永真式；若该公式的真值为0，则该公式为永假式。既非永真，也非永假，则为非永真的可满足式。 4. 等价公式的证明 等价公式：给定两个命题公式A与B，设P1，P2，…，Pn为所有出现于A与B中的原子变元，若给P1，P2，…，Pn任一组真值指派，A与B的真值均相同，则称公式A与B是等价的或逻辑相等，记作A?B，此公式可称为等价公式。 真值表法（验证公式等价）：将两个命题公式的真值表列出，在所有的真值指派下，两个公式的真值都对应相同，则说明两个公式等价，否则，就不等价。 等