第一篇----数理逻辑.ppt

离 散 数 学Discrete Mathematics 福建师范大学福清分校 数学与计算机科学系 黄晓秋 第一章 命题逻辑 1. 命题及其表示 命题：是指具有确定真值的陈述句或者能够判断真假的陈述句。 命题的真值：命题的判断结果。真值只取两个值：真（1或T）、假（0或F）。 真命题：真值为真的命题。 假命题：真值为假的命题。 判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。 感叹句、祈使句、疑问句都不是命题. 陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单陈述句表达的命题称为简单命题或原子命题。命题逻辑不再进一步分析简单命题的内部结构。 命题的分类 简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。 复合命题：由简单命题通过联结词联结而成的陈述句。 如： 命题“如果2是素数，则3也是素数”通过“如果……，则……” 组合而成，是复合命题，而“2是素数”和“3是素数”是简单命题。 命题表示 用英文字母表示命题,用“1(或者T）”、“0（或者F）”分别表示真值的真、假。 如 P：太阳从东边升起。 Q：5是负数。 R：2008北京举办奥运会 。 其真值依次为1、0、1。 2. 命题联结词 在日常语言中，一些简单的陈述句，可以通过某些联结词联结起来，组成较为复杂的语句。 例如可以说：“如果下星期日是晴天，那么我就去春游”。 这里就是用：“如果……，那么……”把两个命题“下星期日是晴天”和“我去春游”联结起来组成的一个新复合命题。 在日常语言中还有许多联结词，如“不”、“并且”、“或者”、“当且仅当”，“只要……就……”， “除非……否则……”等都是联结词。 使用它们可以将一个命题加以否定或将两个命题连接起来得到新的复合命题。 下面介绍6种常用的联结词。 （1）否定联结词 设p为命题，复合命题“非P”（或“P的 否定”）称为P的否定式，记作﹁ P， 符号﹁称为否定联结词。 ﹁ 运算规则：属于一元运算符 合取运算特点： 只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是”等都可以用∧符号化。 例如：将下列命题符号化 (1) 北京不仅是中国的首都而且是一个故都。 解：设P：北京是中国的首都； Q：北京是一个故都； 则原命题符号化为： P∧Q。 （2）小丽既聪明，又能干。 解：设P：小丽聪明；Q：小丽能干； 则原命题符号化为： P∧Q。 （3）小刚聪明但不努力。 解：设P：小刚聪明；Q：小刚努力； 则原命题符号化为： P∧ ﹁ Q。 （4）小刚和小明是同学。 解： P：小刚和小明是同学 说明： 联结词析取∨的意义与日常所使用的“或”意思并不完全相同。在日常生活中，“或”实际上分为 “可兼或”和“排斥或”（异或），还有一种是描述模糊数据。 “排斥或”用异或联结词 表示，也可用等价的联结词代替。 （4）异或（排斥或）联结词(不做要求） 运算规则：属于二元运算符。 例如: (1)老王学过俄语或英语。 解：设P：老王学过俄语； Q：老王学过英语； 则原命题符号化为： P ∨ Q 。（可兼或） （2）张三生于1972年或1973年。 解：设P：张三生于1972年； Q：张三生于1973年； 则原命题符号化为：P Q （不可兼或） 该命题中的“或”不是“可兼或”，不能用析取联结词也可以用一种等价形式来代替。 (P∧?Q) ∨(?P∧Q). （3）小刚有20或30岁。 解：这是原子命题，这里的“或”表示一个模糊数据。原命题符号化为 P：小刚有20或30岁 （5）单条件联结词 设P,Q为二命题变元,复合命题“如果P,则Q” 称为P与Q的单条件（蕴涵式），记作P?Q，并称P为单条件的前件，Q为单条件的后件，符号? 称为单条件联结词。 说明：P?Q 的逻辑关系： Q 为 P 的必要条件， P为Q的充分条件。 但P，Q 间可以没有任何内在联系。 例：如果小明去公园，那么意大利取得本届欧洲杯足球赛冠军。 当P为假时，无论Q取何值，P?Q 均为真。 前提不真，结论总是成立的。 例：如果太阳是三角形的，那么月亮就是四边形的。 是真命题。 “如果 P，则 Q ” 的不同表述法很多： “若P，就Q” “只要P，就Q” “因为P，所以Q”