1命题逻辑.pptVIP

第一篇　数理逻辑 第一章　命题逻辑1.1　命题及其表示法 命题：能判断真假的陈述句。 命题是一个陈述句，不能是祈使句、疑问句和感叹句。 该陈述句所表达的内容可判断真假，非真即假，非假即真，不能无所谓真假。 真值：作为命题的陈述句所表达的判断结果，称为 命题的真值。真值只有两种取值：真或假，分别用符号1(或T)和0(或F)表示。 命题表示法：可用 字母P，Q，R… 或带下标的字母，如P1，Q4…表示命题。 例：P：今天下雨。 　　Q：今天是晴天。 R ：雪是黑的。 命题标识符：表示命题的符号。 如上例中的P，Q和R就是标识符。 1.2　联结词 15. 双条件否定等价式 A?B??A??B 16. 归谬论 (A→B)∧(A→?B)??A Th2(代入规则)　一个重言式，对同一分量都用同一合式公式代入，其结果仍为一个重言式。 证：由于重言式的真值与分量的指派无关，故对同一分量以任何公式代入后，重言式的真值仍永为Ｔ。 1.7 析取范式与合取范式 ——含n个命题变元的公式两种规范表示方法 简单合取式/基本积：由命题变元或命题变元的否定组成的合取式 P1 ∧P2∧...∧Pn，其中Pi指Pi或者? Pi。 如：P，?Q，P∧Q，P∧?Q∧R 简单析取式/基本和：由命题变元或命题变元的否定组成的析取式P1∨P2∨...∨Pn，其中Pi指Pi或者? Pi。 如：P，?Q，P∨Q，P∨?Q∨R Th2 (范式存在定理)　任一个命题公式都存在着与之等价的析取范式与合取范式。 化归过程： 将公式中的联结词都化归成?，∧，∨。 利用德·摩根律将?直接移到各个命题变元以前。 利用分配律、结合律将公式归约为合取范式或析取范式。 命题公式向主合取范式的化归过程： 化归为合取范式。 除去合取范式中所有永真的简单析取式。 将合取式中重复出现的析取项和相同的变元合并。 对简单析取式补入没有出现的命题变元，即添加(P∧?P)式，然后应用分配律展开公式，再除去相同的极大项。 关键之处： 　 Ai ? Ai∨0 ? Ai∨(Pj∧?Pj ) 　 ? (Ai∨Pj )∧(Ai∨?Pj ) 　　　　　　　　　　　　 　　　　　　 c Def3　条件非，条件否定（?）： 0 1 1 1 0 1 0 1 0 0 0 0 c P?Q Q P 　　　　　　　　　　　c 由定义可知 P?Q ? ?(P?Q) 1 0 1 0 1 1 1 1 0 0 0 0 ____ PVQ Q P 　　　　　　　　　　　　　 　　　　　　　　 c _____ Def4 双条件非?，异或⊕，不可兼析取Ｖ： —------ P∨Q ? ?(P?Q) —------ P∨Q ? (P∧? Q)∨(? P∧Q) 性质：第20,21页 Th1　设P、Q、R为命题公式。如果 　　　 　　　——————　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　———————　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　　　　　—————— P∨Q?R，则P∨R?Q，Q∨R?P，且 　 　　　　　——————　　　　　　　　 ——————— P∨Q∨R为一矛盾式。 证明（板书） 　我们一共学了九个联结词{?，∧，∨， — c ?，?，∨，?，?，? }。 　两个命题变元可构成２４个不等价的命题公式。 　　它们可用命题常量T或F、命题变元本身及命题联结词表示如下。 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0