05a数理逻辑总复习.ppt

1数理逻辑单元总复****第五周第二讲 2原子命题、复合命题命题的分类: 原子命题: 不能分解为更简单的陈述句。复合命题: 由联结词、标点符号和原子命题复合构成的命题。命题的定义:客观上能够确定真假的陈述句。 3命题变元、命题常量命题常量: 用来表示确定命题的标识符。例如: P表示“今天下雨。”命题变元: 表示任意命题位置标志的命题标识符。例如: P∨┑ P,P∧Q 命题变元可以表示任何命题; 当用一个特定命题取代命题变元 P时,称为对 P指派。 4命题联结词联结词: 用于把原子命题联结成复合命题,是复合命题的重要组成部分。例如:或、与、但是、如果、……符号化的联结词(命题的五个基本联结词) ┑:否定∧:合取∨:析取?:条件?:双条件在表达式中的优先级顺序 5 合式公式( wff : Well-Formed Formula) 的定义: 1、单个命题变元本身是一个合式公式; 2、如果 A是合适公式,则┑A是合式公式; 3、如果 A和B是合适公式,则(A ∧ B)、(A ∨ B)、(A ? B)、(A ? B)都是合式公式。 4、当仅当能够有限次地应用 1、2、3所得到的包含命题变元、联结词和括号的符号串是合式公式。这是一个递归定义, 1、为基础, 2、3为归纳, 4、为界限(停机条件)。定义合式公式定义谓词公式 6定义真值表在命题公式中,对于分量指派真值的各种可能组合,就确定了这个命题公式的各种真值情况,把它汇列成表,就是命题公式的真值表。 7真值表的讨论变元取值的顺序:按二进制递增或递减 n个命题变元组成的命题公式共有种真值情况。特殊的命题公式: T(F) 不论命题变元作何种指派,其真值永为真(假) P14 表 1- 和表 1- 的结论今后可作定理使用。 2 n8命题的定律用真值表证明以下定律: 对合律结合律交换律分配律吸收律摩根律同一律零律否定律 9置换规则定义子公式: 如果 X是合式公式 A的一部分,且 X本身也是一个合式公式,则称 X为公式 A的子公式。置换规则: 设X是合式公式 A的子公式,若 X ? Y, 如果将 A中的 X用Y来置换,所得到公式 B与公式 A等价,即 A ? B 10证明命题公式等价方法一:利用 定律进行转换(注意用等价号“?”,不能用等号“=”) 方法二:构造真值表这是万无一失的方法但不适合于多于 3个变元的命题公式方法三:要证明 A?B,往证 A?B是重言式方法四:要证明 A?B,往证 A?B且B?A 方法五:利用对偶原理:若 A?B,则 A*?B* 方法六:统一化为范式