三章.命题逻辑.docVIP

离散数学讲义 武汉科技大学计算机学院 －3. PAGE 17－ 第三章 命题逻辑 重点：掌握数理逻辑中命题的翻译及命题公式的定义；利用真值表技术和公式转换方式求公式的主析取范式和主合取范式；利用规则、基本等价和蕴涵公式、三种不同的推理方法完成命题逻辑推理； 难点：如何正确地掌握对语言的翻译，如何利用推理方法正确的完成命题推理。 数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支、计算机学科、人工智能、语言学等学科均有十分密切的联系，并且益显示出它的重要作用和更加广泛的应用前景。要很好地使用计算机，就必须学习逻辑。数理逻辑分五大部分。在离散数学中仅介绍命题逻辑和谓词逻辑。命题逻辑是谓词逻辑的基础，只有掌握了命题逻辑，才能学好谓词逻辑。对于命题逻辑，下面从六个知识点来加以阐述。 3.1 命题符号化及联系结词 1 命题 有确切真值的陈述句称为命题。 所谓确切真值是指在具体的环境，具体的时间，具体的对象，具体的位置等情况下能唯一确定真值的。命题分为两种： (1) 简单命题：不能分解为更为简单的句子的命题。 复合命题：能够分解为更为简单的命题。 2 命题联结词 联结词记号复合命题读法记法真值结果否定乛P是不对的P的否定乛P乛P为真当且仅当P为假合取∧P并且QP与Q的合取P∧QP∧Q为真当且仅当P，Q同为真析取∨P或者QP与Q的析取P∨QP∨Q为真当且仅当P，Q至少一个为真蕴涵→若P，则QP蕴涵QP→QP→Q为假当且仅当P为真，Q为假等价←→P当且仅当QP等价于QP←→ QP←→ Q为真当县仅当P，Q同为真假 关于联结词，有如下几点要注意： （1）此联结词是联结的句子与句子之间的联结，而非单纯的名记号、形容词、数词等的联结； （2）此联结词是两个句子真值之间的联结词，而非句子的具体含义的联结，两句子之间可以无任何的内在联系； （3）联结词与自然语言之间的对应并非一一对应，如合取联结词“∧”对应了自然语言中的“既……又……”、“不仅……而且……”、“虽然……但是……”、“并且”、“和”、“与”等。如蕴涵联结词“→”，P→Q对应了自然语言中的“加P则Q”，“只要P就Q”，“P仅当Q”，“只有Q才P”，“除非Q否则乛P”等。如等价联结词“←→ ”对应了自然语言中的“等价”、“并且仅当”、“充分必 ”等。如析取联结词∨是对应相容的或(中兼的或)。 3.2 命题公式及分类 一般称具有确切真值的简单命题叫命题常量，用P，Q，R，…等表示。而没有赋予具体内容的简单命题称为命题变量（变元），此时的P，Q，R没有具体的真值。 1．合式公式 （1）单个的命题变量或常量（含1或0）是合式公式； （2）若P是合式公式，则（乛P）也是合式公式； （3）若P，Q是合式公式，则（P∨Q）、（P∧Q）、（P→Q）、（P←→ Q）也是合式公式。 只有有限次使用上述三步形式的符号串才是合式公式（命题公式），简称公式。 为了简化公式，可按如下优先级别进行：“（）”“乛”“→”“←→ ” 其中，为避免错误，合取与析取看成是同等优先级别，要改变或强调其优先级别，采用括号。另外，最外层的括号可以省掉，同级的按从左到右的顺序进行运算。 2．赋值或解释与真值表 设G是命题公式，P1，P2，…，Pn (n/1)是出现在公式G中的所有命题变元，指定P1，P2，…，Pn一组真值，则这组真值称为G的一个解释或赋值。此时不同的赋值就有2n种。将此2n种不同的赋值下的取值情况列成的表称为G的真值表。 3．公式的分类 设G为一公式， （1）如G在它所有的解释之下都为真，则称G为永真或重言式； （2）如G在它所有的解释之下都为假，则称G为永假或矛盾式； （3）如G在它所有的解释之下至少有一个为真，则称G为可满足式。 3.3 等价公式与演算 1．等价关系 称公式G，H是等价的，如果在其任意的解释下，其真值相同，记为G=H。 说明：G=H仅描述了两公式G，H之间的一种等价的关系，G=H本身并非是一个公式，它不能作直接计算。 要判断G=H，可采用：G=H当且仅当公式G←→ H 是一个永真式。 2．代入定理 设G(P1，P2，…，Pn)是一个公式，G1(P1，P2，…，Pn)，…，Gn(P1，P2，…，Pn)为任意公式，若G是永真式或永假式，则用G1，G2，…，Gn取代公式G中的P1，P2，…Pn后而得的新公式G(G1，…，Gn)＝G’(P1，P2，…