1.1 命题和命题联结词
6.异或联结词 指的是排斥或，当且仅当p、q的真值相异时，p q为真。
由定义知 有如下性质： （1 p q等价于q p ）
p F T
q F T F
p F T T
q
( 2) p q等价于( p q ) (p q ) F
T
例：今天第一节课上离散数学或数据结构。
p：王化的成绩很好。 q：王化的1 命题和命题联结词
3).析取词 命题p、q和 组成的复合命题记作p q, 读作“p或q”。
是自然语言中的“或” 、“或者”中的可兼或 的逻辑抽象。
p q
F T
p：开关坏了。 q：灯泡坏了。
开关坏了或灯泡坏了。 p∨q：
假 — 假命题
注意：此处不纠缠具体命题的真假问题，只是将其作为数学概念来处理。
3.命题和真值的符号化
命题 : 一般用p, q, r ,或pi , qi ,表示。
真值：真用T或1表示，假用F或0表示。
1.1 命题和命题联结词
原子命题：不能被分解为更简单的陈述句 复合命题：原子命题通过联结词联结而成
离散数学
离散数学
• • • • • 离散数学概述 第一部分 数理逻辑 第二部分 集合论 第三部分 图论 第四部分 抽象代数
第一部分 数理逻辑
• 寻找真理的人存在吗？ • 上帝是万能的吗？ • 你能获得会员资格吗？
桌子上摆着两个盒子：一个圆盒子，一个方盒子。 圆盒子上写着一句话：“申请不在盒中”。 方盒子上写着一句话：“这两句话中只有一句是真话”。 那么申请表在哪个盒子里呢？
1.1 命题和命题联结词
4、命题联结词
1).否定词 用命题p和“非”、“不”、“没有”等否定词组成的复合命题， 称作p的否命题，记作p, 读作“非p”。
是自然语言中的“非”、“不”和“没有”等的逻辑抽象。 如：p : 4是质数。 p： 4不是质数。
p
p
F
T
T
F
1.1 命题和命题联结词
1.1 命题和命题联结词
5).等价词 由命题p、q和 组成的复合命题记作p q, 读作“p当且仅当q”。 是自然语言中的“充要条件”，“当且仅当”的逻辑抽象。
p q的逻辑关系为p与q互为充要条件 p 例：1.3是有理数当且仅当加拿大位于亚洲。 2.两圆的面积相等，则他们的半径相等， 反之亦然。 F F T T q F T F T p q T F F T
p
F F
q
F T
T
T
F
T
T
T
1.1 命题和命题联结词
例：1.张晓婧爱唱歌或爱听音乐。 2.张晓婧是内蒙人或是陕西人。 3.张晓婧只能挑选202或203房间。
注意：当排斥或两边的情况实际根本不可能同时发生的时候，排斥或也 可抽象为∨。但为了方便起见一般不这样抽象。
1.1 命题和命题联结词
4).蕴涵词 由命题p、q和 组成的复合命题记作p q, 读作“如果p, 则q” 或“p条件q”。称为前件（前提），q称作后件（结论）。
第一部分 数理逻辑
一人在寻找真理，别人问他：“你真的不知道 真理是什么 吗？” 那个人说：“当然！” 别人又问：“你既然不知道真理是什么，当 你找到真理的时 候，你又如何辨别出来呢？ 如果你辨别得出真理与否，那说明你已经知 道了真理是什 么，又何来寻找呢？”
第一部分 数理逻辑
上帝真的是万能的吗？ 让我们来问提出一个问题：上帝是否能创造出一块连自 己都举不起来的石头？ 如果上帝创造出了一块连他自己都举不起来的石头，那么上 帝就不是万能的，因为有一块石头他举不起来。 如果上帝不能创造出一块连他自己都举不起来的石头，那么 上帝也不是万能的，因为有一块石头他创造不出来。 所以无论上帝是否能创造出这么一块石头，他都不是万能的。
第一部分 数理逻辑
逻辑推理俱乐部门口贴着一张布告：“欢迎你加入推理俱乐部！只要你 通过推理取得一张申请表，就可以获得会员资格了！” 只见桌子上摆着两个盒子：一个圆盒子，一个方盒子。 圆盒子上写着一句话：“申请不在盒中”。 方盒子上写着一句话：“这两句话中只有一句是真话”。 那么申请表在哪个盒子里呢？
1.1 命题和命题联结词
1. 命题：能判断真假的陈述句。 包含两层意思：
自然语言中的陈述句 1）必须是陈述句 等式 不等式
2）能够确定（分辨）其真值。
注意：能否分辨真假与是否知道真假是不同的。 如：张校长的头发有一万根。
1.1 命题和命题联结词
2. 命题的真值：判断结果 真 — 真命题
是自然语言中的“如果 ，则 ”，“若 ，则 ” 的逻辑抽象。
有位父亲对儿子说：“如果我 去书店，就一定给你买电脑 报“。问：在什么情况下，
p F F T T
q F T F T
p T T F T
父亲算失信呢？

q
1.1 命题和命题联结词
注意：①“只要p，就q‘，’因为p，所以q”，“p仅 当q”， ‘只有q，才p“，”除非q才p“，”除非q，否则非 p“都可 抽象为p→q。 ②p，q可以没有任何内在联系。 例：1.如果3＋3＝6，那么雪是白的。 2.除非我能工作完成了，我才去看电影。 3.只要天下雨，我就回家。 4.我回家仅当天下雨。 p→q的逻辑关系为q是p的必要条件或p是q的充分条件。
1、设方盒子上写的话是真的，推出圆盒子上的话是假的，推出 申请表在圆盒子中。 2、设方盒子上的话是假的，推出圆盒子上的话也是假的，推出 申请表在圆盒子里。 3、或者方盒子上的话是真的，或者方盒子上的话是假的。总 之，申请表在圆盒子中。
第一部分 数理逻辑
数理逻辑: 是用数学方法研究逻辑或形式逻辑的学科。
1.1 命题和命题联结词
注意： （ ）给定句子是否是命题 ，如：我和他是同学。 1 （2）要善于识别自然语言 中的联结词，如：狗急 跳墙。
例1.如果你和他不都是傻子 ，那么你们俩都不会去 自讨没趣。 2.如果你走路时看书，那 么你一定会成为近视眼 。 3.他虽有理论知识但无实 践经验。 4.选小陈或小周一人为代 表。 5.如果明天天气好，我们 去郊游，否则就不去。
推理:
是由一个或几个判断推出一个新判断的思维形式。 数学方法: 是指建立一套表意符号体系，对具体事物进行抽象的形 式研究的方法。
第一部分 数理逻辑
• 第一章 命题逻辑 • 第二章 一阶谓词逻辑
第一章 命题逻辑
• • • • • • 1.1 命题和命题联结词 1.2 命题公式及其赋值 1.3 等值演算与联结词完备集 1.4 析取范式与合取范式 1.5 推理的形式结构 1.6 自然推理系统P
T
F
1.1 命题和命题联结词
联结词的优先次序： （1 ）由强到弱依次是：， ， ， ， ,。 （2）按优先级书写，可以省略不必要的括号。 （3）同级的联结词，按从左往右的次序运算。
例：p：北京比天津人口多 q：2＋2＝4 r：乌鸦是黑色的
求以下命题的真值 （ ）p q q r 1 (2)r q p q p
2).合取词 p、q是命题，由p、q和 组成的复合命题，记作p q, 读作“p与q”或“p合取q”。
是自然语言中的“并且”、 “既 又 ”、“不但 而且”、“虽然但是” 、“一面一面”等的逻辑抽象。
p F F T T q F T F T p q F F F T