离散课件-1.pptVIP

离散数学 周文俊 离散数学的内容 数理逻辑 集合论 图论 代数结构 离散数学的地位 专业基础课 与其它专业课的关系 与微积分的区别 课程特点 学习要求 第1章 命题逻辑 §1 基本概念 §2 公式的等价关系 §3 范式 §4 公式的蕴涵关系 §5 连接词的完备集合 §6 半形式化推导方法 §1基本概念 1.命题 逻辑：研究人类思维和推理规律的一门学科。 数理逻辑：用数学的方法（即建立一套符号系统）研究思维和推理规律的一个逻辑分支。包括命题逻辑与谓词逻辑 命题：能判明真假的陈述句。 真命题的真值用1表示，假命题的真值用0表示 简单命题：只含有一个内容的命题。用单个字母表示。 复合命题：含有多个内容的命题。它是用一些连接词将多个简单命题连接起来的复合句。需要引进一些符号表示这些连接词。 举例 （1）3+2=5 （2）郑州是河北的省会。 （3）中国承办二零零八奥运会。 （4）5－3=1 （5）X+2=5 （6)2+3=5并且2×3=5 （7）如果2+3=4，那么雪是黑的。 （8）今天下雨吗？ （9）请把门关上！ （1）——（4）是简单命题。 （6）——（7）是复合命题。 （1）（3）（7）真值为1。 （2）（6）真值为0。 （5）（8）（9）不是命题。 2. 逻辑连接词 否定连接词? p ?p 0 1 1 0 “非” “不” “没有” “是不对的” 合取连接词∧ p q p∧q 0 0 0 0 1 0 1 0 0 1 1 1 “与” “并且” “不但， 而且” 析取连接词∨ p q p∨q 0 0 0 0 1 1 1 0 1 1 1 1 “或者” “要么 要么” 条件连接词→ p q p→q 0 0 1 0 1 1 1 0 0 1 1 1 “若，则” “如果，那么” 双条件连接词? p q p?q 0 0 1 0 1 0 1 0 0 “当且仅当” 1 1 1 “充要条件” 举例 符号化下面命题 （1）郑州不是河北省的省会。 （2）2+3=5并且2×3≠5。 （3）今天刮风或者下雨。 （4）如果2+3=4，那么雪是黑的。 （5）3-2﹥0当且仅当3﹥2。 解:（1）令p表示“郑州是河北的省会”，则该命题可表示为? p 。 （2）令p表示“2+3=5”，q表示“2×3=5” ，则该命题可表示为p∧ ? q 。 （3）p令表示“今天刮风”，q表示“今天下雨”，则该命题可表示为p ∨ q 。 （4）令p表示“2+3=4”，q表示“雪是黑的”，则该命题可表示为p → q 。 （5）令p表示“3-2﹥0”，q表示“3﹥2” ，则该命题可表示为p ? q 。 3. 命题公式 命题公式（递归定义） （1）一个字母（命题变元）是命题公式。 （即原子公式）。 （2）若A，B是命题公式，则?A，A∧B， A∨B，A→B，A?B也都是命题公式。 （3）每个命题公式都是有限次使用（1）,（2）产生的。 注：命题公式中的逻辑连接词的优先级依次为? ，∧，∨，→ ， ? 4. 真值指派与真值表 真值指派：给每个命题变元都指定一个真值。 n个命题变元共有2n种真值指派。 真值表：用表列出命题公式在每种真值指派