离散数学
1 离散数学
主要内容 ■数理逻辑 ■集合论 ■代数结构 ■图论 组合分析初步 ■形式语言和自动机初步
2 主要内容 ◼ 数理逻辑 ◼ 集合论 ◼ 代数结构 ◼ 图论 ◼ 组合分析初步 ◼ 形式语言和自动机初步
教材与教学参考书 ■教材: □耿素云、屈婉玲、张立昂,离散数学(第三 版),清华大学出版社,2004 教学参考书: □屈婉玲、耿素云、张立昂,离散数学题解(修 订版),清华大学出版社,2004
3 教材与教学参考书 ◼ 教材： 耿素云、屈婉玲、张立昂，离散数学（第三 版），清华大学出版社, 2004. ◼ 教学参考书： 屈婉玲、耿素云、张立昂，离散数学题解（修 订版），清华大学出版社，2004
数理逻辑部分 ■第1章命题逻辑 第2章一阶逻辑
4 数理逻辑部分 ◼ 第1章 命题逻辑 ◼ 第2章 一阶逻辑
第1章命题逻辑 11命题符号化及联结词 12命题公式及分类 1.3等值演算 1.4对偶与范试 1.5推理理论
5 第1章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 对偶与范试 1.5 推理理论
11命题符号化及联结词 ■命题与真值 ■原子命题 ■复合命题 ■命题常项 命题变项 ■联结词
6 1.1 命题符号化及联结词 ◼ 命题与真值 ◼ 原子命题 ◼ 复合命题 ◼ 命题常项 ◼ 命题变项 ◼ 联结词
命题与真值 命题:判断结果惟一的陈述句 命题的真值:判断的结果 真值的取值:真与假 真命题:真值为真的命题 假命题:真值为假的命题 注意:感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题
7 命题与真值 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题
例下列句子中那些是命题? (1)√2是无理数 真命题 (2)2+5=8 假命题 3)x+5>3. 真值不确定 (4)你有铅笔吗? 疑问句 (5)这只兔子跑得真快呀! 感叹句 (6)请不要讲话! 祈使句 (7)我正在说谎话 悖论 (3)-(7)都不是命题
8 例 下列句子中那些是命题？ (1) 是无理数. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话. 真命题 假命题 真值不确定 疑问句 感叹句 祈使句 悖论 (3)~(7)都不是命题 2
命题的分类 简单命题(原子命题): 简单陈述句构成的命题 复合命题: 由简单命题与联结词按一定规则复合 而成的命题
9 命题的分类 简单命题(原子命题)： 简单陈述句构成的命题 复合命题： 由简单命题与联结词按一定规则复合 而成的命题
简单命题符号化 用小写英文字母p,q,F,…,P,qr(≥1)表示 简单命题 用“1”表示真,用“0”表示假 例如,令 p:√2是有理数,则p的真值为0 q:2+5=7,则q的真值为1 10
10 简单命题符号化 2 用小写英文字母 p, q, r, … ,pi ,qi ,ri (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1