离散谓词.ppt

离散数学课幻灯片 数理逻辑 前言 研究人的思维形式和规律的科学称为逻辑学，由于研究的对象和方法各有侧重而又分为形式逻辑、辨证逻辑和数理逻辑。 数理逻辑是应用数学方法研究推理的科学。数理逻辑又叫符号逻辑，因为它的主要工具是符号体系。数理逻辑的核心是把逻辑推理符号化，即变成象数学演算一样完全形式化了的逻辑演算。 本章主要介绍命题演算(1.1---1.5) 第一章 数理逻辑 1 命题 2 重言式 3 范式 4 联结词扩充与归约 5 推理规则证明方法 命题的概念 所谓命题，是具有真假意义的陈述句，也就是能够确定或分辨其真假的陈述句，且真与假必居其一。简言之，命题是非真即假的陈述句。 命题是真就说其真值为真，命题是假就说其真值为假。 感叹句、疑问句、祈使句都不能称为命题。 判断结果不唯一确定的陈述句不是命题。 陈述句中的悖论不是命题。 原子命题,复合命题与命题联结词 1 否定词 ? 设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式,记作┐p，符号┐称作否定联结词，并规定┐p为真当且仅当p为假。 2 合取词 ∧ 若 P,Q 表示命题，则 ‘P并且Q’ 也是命题，记为 P∧Q ,读为 ‘P合取Q’. P∧Q 的真值表如右表所示。由真值表可知 P∧Q 真,当且仅当 P,Q 俱真. 使用合取联结词时要注意的两点： 描述合取式的灵活性与多样性。自然语言中的“既……又……”、“不但……而且……”、“虽然……但是……”、“一面……一面……”等联结词都可以符号化为∧。 分清简单命题与复合命题。不要见到“与”或“和”就使用联结词∧。 3 析取词 ∨ 若 P,Q 表示命题，则 ‘P或者Q’ 也是命题，记为 P∨Q,读为 ‘P析取Q’. P∨Q 的真值表如右表所示。由真值表可知 P∨Q 真,当且仅当P,Q 至少有一个真 张晓静爱唱歌或爱听音乐。 张晓静只能挑选202或203房间。 张晓静是江西人或安徽人。 他昨天做了二十或三十道习题。 4 蕴涵词 → 若 P,Q 表示命题，则 ‘P蕴涵Q’ 也是命题，记为 P→Q,读为 ‘P蕴涵Q’. P→Q 的真值表如右表所示。由真值表可知P→Q为假,当且仅当P为真而Q为假. 关于 P→Q 真值表的说明 p→q的逻辑关系表示q是p的必要条件。 q是p的必要条件有许多不同的叙述方式 只要p，就q 因为p，所以q p仅当q 只有q才p 除非q才p 除非q，否则非p 5 等值词 ? 若 P,Q 表示命题，则 ‘P等值于Q’ 也是命题,记为 P?Q, 读为 ‘P等值于Q’. P?Q 的真值表如右表所示. 由真值表可知 P?Q 为真,当且仅当P与Q有相同的真值. 例： 设 P:天不下雨, Q:草木枯黄, 则 ?P:天下雨; P∧Q:天不下雨并且草木枯黄; P∨Q:天不下雨或草木枯黄; P→Q:如果天不下雨,那麽草木枯黄; P?Q:天不下雨当且仅当天草木枯黄. 五个逻辑运算符强弱顺序 运算符结合力的强弱顺序约定为： ?,∧,∨,→,? 没有括号时按上述先后顺序执行. 相同运算符按从左至右顺序执行括号可省去. 最外层的括号总可以省去. 例如 ?P∨?P∨Q∧?S∨?Q∧R 与 (((?(P)∨?(P))∨(Q∧?(S))∨(?(Q)∧R)) 运算顺序完全一样,前者不加一个括号. 请大家特别注意先∧后∨的习惯. 命题符号化—自然语言翻译为逻辑式 符号化应注意以下几点： ① 确定句子是否为命题.不是就不必翻译. ② 确定句中连接词是否能对应于并且对应于哪一个命题连接词. ③ 正确表示原子命题和选择命题连接词. ④ 要按逻辑关系翻译而不能凭字面翻译.例如令：P:林芬做作业 Q:林芳做作业.则‘林芬和林芳同在做作业’可译为P∧Q;但‘林芬和林芳是姐妹’不能译为P∧Q，因为这是一个原子命题. 命题变元和命题公式 以‘真’、‘假’为变域的变元称为命题变元；T 和 F 称为命题常元. 单个命题变元和命题常元称为原子公式；由下列递归规则生成的公式称为命题公式: (1)单个原子公式是命题公式. (2)若A和B是命题公式，则 ?A,A∧B,A∨B,A→B,A?B 是命题公式. (3)只有有限步应用(1)和(2)生成的公式(称为合式公式)才是命题公式. 关于合式公式的说明 (┐A)、(A∧B)等公式单独出现时，外层括号可以省去，写成┐A、A∧B等。 公式中不影响运算次序的括号可以省去，如公式(p∨q)∨(┐r)可以写成p∨q∨┐r。 合式公式的例子：(p→q)∧(q ? r)(p∧q)∧┐rp∧(q∧┐r) 不是合式公式的例子p