离散数学与第一部分 .ppt

离 散 数 学Discrete Mathematics 张清华 蒲兴成 尹邦勇 刘勇 第一章 命题逻辑 1. 命题及其表示 命题：是指具有确定真值的陈述句或者能够判断真假的陈述句。 命题的真值：命题的判断结果。真值只取两个值： 真（1或T）、假（0或F）。 真命题：真值为真的命题。 假命题：真值为假的命题。 判断命题的两个步骤： 1、是否为陈述句； 2、是否有确定的、唯一的真值。 注意: 感叹句、祈使句、疑问句都不是命题. 陈述句中的悖论以及判断结果不惟一确 定的也不是命题。 命题表示 在本书中，用大写的英文字母P,Q,R,…，P1,P2,P3…，等表示命题,用“1(或者T）”、“0（或者F）”分别表示真值的真、假。 如 P：太阳从东边升起。 Q：5是负数。 R：2008北京举办奥运会 。 其真值依次为1、0、1。 命题的分类 简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。 复合命题：由简单命题通过联结词联结而成的陈述句。 如： 命题“如果2是素数，则3也是素数”通过“如果……，则……” 组合而成，是复合命题，而“2是素数”和“3是素数”是简单命题。 2. 命题联结词 在日常语言中，一些简单的陈述句，可以通过某些联结词联结起来，组成较为复杂的语句。 例如可以说：“如果下星期日是晴天，那么我就去春游”。 这里就是用：“如果……，那么……”把两个命题“下星期日是晴天”和“我去春游”联结起来组成的一个新复合命题。 在日常语言中还有许多联结词，如“不”、“并且”、“或者”、“当且仅当”，“只要……就……”，“除非……否则……”等都是联结词。 使用它们可以将一个命题加以否定或将两个命题连接起来得到新的复合命题。 下面介绍常用的5种常用的联结词。 （1）否定联结词 设p为命题，复合命题“非P”（或“P的 否定”）称为P的否定式，记作﹁ P， 符号﹁称为否定联结词。 运算规则：属于一元运算符 合取运算特点： 只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是”等都可以符号化为∧ 例如：将下列命题符号化 (1) 北京不仅是中国的首都而且是一个故都。 解：设P：北京是中国的首都； Q：北京是一个故都； 则原命题符号化为： P∧Q。 （2）小丽既聪明，又能干。 解：设P：小丽聪明；Q：小丽能干； 则原命题符号化为： P∧Q。 （3）小刚聪明但不努力。 解：设P：小刚聪明；Q：小刚努力； 则原命题符号化为： P∧ ﹁ Q。 （4）小刚和小明是同学。 解： P：小刚和小明是同学 说明： 联结词析取∨的意义与日常所使用的“或”意思并不完全相同。在日常生活中，“或”实际上分为 “排斥或”和“可兼或”，还有一种是描述模糊数据。本书将析取表示“可兼或”。“排斥或”用等价的联结词代替。 例如: (1)今天晚上我在家看电视或听音乐。 解：设P：今天晚上我在家看电视； Q：今天晚上我在家听音乐； 则原命题符号化为： P ∨ Q 。（可兼或） （2）从重庆到北京的T10次列车是中午1点或1点半开。 解：设P：重庆到北京的T10次列车是中午1点开； Q：重庆到北京的T10次列车是中午1点半开； 则原命题符号化为： (P∧?Q) ∨(?P∧Q). 该命题中的“或”不是“可兼或”，不能用联结词析取。我们用一种等价形式来代替。 例如: （3）小刚是山东或山西人。 解：设P：小刚是山东人；Q：小刚是山西人； 则原命题符号化为： (P∧?Q) ∨(?P∧Q).（排斥或） （4）小刚是有20或30岁。 解：这是原子命题，这里的“或”表示一个模糊数据。原命题符号化为P：小刚是有20或30岁 在遇到含有“或”的命题符号化时，要分清它是“可兼或”、“排斥或”、还是表示模糊数的“或”，析取联结词表示“可兼或”。 （4）单条件联结词 设P,Q为二命题变元,复合命题“如果P,则Q” 称为P与Q的单条件（蕴涵式），记作P?Q，并称P为单条件的前件，Q为单条件的后件，符号?称为单条件结词。 运算规则：属于二元运算符 与自然语言的不同：前件与后件可以没有任何内在联系！ 说明：P?Q 的逻辑关系：Q 为 P 的必要条件 “如果 P，则 Q ” 的不同表述法很多： “若P，就Q” “只