第四篇_数理逻辑部分.pdf

第四部分数理逻辑 一、主要内容 命题逻辑基本概念 命题公式及范式 命题逻辑推理理论 谓词逻辑基本概念 谓词逻辑等值演算与推理理论 二、学习要求 深刻理解命题、联结词、复合命题、命题公式、等值式、 等值演算、范式、推理及证明等概念 熟练进行等值演算与构造证明 第一章 命题逻辑 本章的主要内容： 命题、联结词、复合命题 命题公式、赋值、命题公式的分类 析取范式、合取范式 命题演算的推理理论 第一节命题及其符号化 一、命题与命题变元 1. 命题与真值 (1) 命题—判断结果惟一的陈述句 (2) 命题的真值—判断的结果 (3) 真值的取值：真与假 (4) 真命题与假命题 注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不惟一确定的不是命题 例：下列句子中那些是命题？ (1） 是有理数. 2 （2 ）2 + 5 ＝ 7. （3）x + 5 ＞ 3. （4 ）你去教室吗？ （5）这个苹果真大呀！ （6）请不要讲话！ （7）2005 年元旦下大雪. 不难看出：（1）是假命题，（2 ）是真命题. （7）是真命题，它 的真值现在不知道，到2005 年元旦就知道了. 可见命题的真值 是客观存在的，不以我们是否知道而改变 2. 命题的分类 （1）简单命题（原子命题） 只由一个主语和一个谓语构成的最简单的陈述句. （2）复合命题 若干个简单命题通过联结词联结而成的更为复杂的命题. 3. 命题的常量、变量 （1）命题常元（命题常量）： 简单命题和复合命题（真值固定不变） （2）命题变元（命题变量）： 真值可以变化的陈述句 4. 简单命题符号化 （1）用小写英文字母p ，q ，r ，…，p ，q ，r （i≥1 ）表示 i i i 命题常元或命题变元 （2）用“1”表示真，用“0”表示假 例如，令 p ： 是有理数，则p 的真值为0 ， 2 q ：2 + 5 = 7 ，则q 的真值为1 二、联结词与复合命题 1．否定式与否定联结词“” 定义8.1 ：设p 为命题，符合命题“非p ”（或“p 的否定”）称 为p 的否定式，记作p ，符号称作否定联结词，并规定p 为真当且仅当p 为假. p 的真值表 p p 0 1 1 0 2. 合取式与合取联结词“∧” 定义8.2 ：设p ，q 为二命题，复合命题“p 并且q”（或“p 与q”） 称为p 与q 的合取式，记作p ∧q ，∧称作合取联结词，并规定 p ∧q 为真当且仅当p 与q 同时为真. 使用合取联结词时要注意两点： p q p ∧q (1) 描述合取式的灵活性与多样性 0 0 0 0 1 0 (2) 分清简单命题与复合命题 1