离散数学第一章数理逻辑

故命题可形式化为:(A∧B∧C) ↔ P
34
中北大学离散数学课程组
例3.他既聪明又用功。 例4.他虽聪明但不用功。 例5.除非你努力，否则你将失败。 例6.张三或李四都可以做这件事。
35
中北大学离散数学课程组
作业：
（1）判断下列公式哪些是合式公式，哪些不是合 式公式。
a.(Q→R∧S） b.(P ↔(R →S)) c.((┐P→Q)→(Q→P)) d.(RS→T) e.((P→(Q→R))→((P→Q)→(P→R)) （2）用符号形式写出下列命题。 a.假如上午不下雨，我去看电影，否则就在家里读
书或看报。
36
中北大学离散数学课程组
b.我今天进城，除非下雨。 c.仅当你走我将留下。
37
中北大学离散数学课程组
练习：将下列命题符号化。 1）说逻辑学枯燥无味（P）或毫无意义（Q）是不对的。 2）如果明天有雾（P），则我乘车（Q），不坐飞机（R）。 3）有雨（P）就刮风（Q）。 4）如果小王没来上课（P），一定是他生病了（Q）。 5）如果我上街（P），我就去图书馆看看（Q），除非我很累
2020/6/30
10
中北大学离散数学课程组
结论： 命题一定是陈述句，但并非一切陈述句都是命题。 命题的真值有时可明确给出，有时还需要依靠环境、 条件、实际情况时间才能确定其真值。
2020/6/30
11
中北大学离散数学课程组
二、命题的分类
1.原子命题(简单命题)：不能再分解为更为简单命 题的命题。
游； （5）两个三角形全等当且仅当三角形的三条边全部
相等。 (6) 张辉与王丽是同学。
2020/6/30
24
中北大学离散数学课程组
例 （解）
（1）设Ｐ：四川是人口最多的省份。
则命题（1）可表示为┐Ｐ。
（2）设Ｐ：王超是一个思想品德好的学生；
Ｑ：王超是一个学习成绩好的学生；
R：王超是一个体育成绩好的学生。
PQ：今天下雨并且明天下雨。
（2）小明与小华是兄弟。
0
（3）他打开箱子并拿出一件衣服。 1
1
Q P ∧Q
0
0
1
0
0
0
1
1
15
中北大学离散数学课程组
1.2 命题联结词
三、析取联结词“∨”
读“或”
PQ
P∨Q
例：
0
0
0
灯泡有故障或开关有故障。
01
1
他可能是100米或400米赛跑的冠军。1 0
1
11
1
16
电子科技大学离散数学课程组——国家精品课程
离散数学
中北大学
2020年6月30日星期二
1
中北大学离散数学课程组
学习离散数学的目的
学习离散数学的目的 《离散数学》是计算机专业的一门十分重要的专
业基础课。离散数学作为有力的数学工具，对计 算机的发展、计算机研究起着重大的作用。目前 ，计算机科学中普通采用离散数学中的一些基本 概念、基本思想和基本方法。 通过本课程的学习，掌握集合论、数理逻辑、代 数和图论等近代数学分支的最基本知识；培养抽 象思维能力及逻辑思维能力。
30
中北大学离散数学课程组
b.小李一边看书，一边听音乐。 c.气候很好或很热。 d.如果a和b是偶数，则a+b是偶数。 e.四边形abcd是平行四边形，当且仅当它的对边平
行。 f.停机的原因在于语法错误或程序错误。
31
中北大学离散数学课程组
1.3命题公式与翻译
命题公式： （1）命题变元(常元)本身是一个合式公式； （2）如A是合式公式，则(┐G)也是合式公式； （3）如G，H是合式公式，则(G∧H)、(G∨H)、(G→H)、
1.2 命题联结词
五、等价词“ ”
PQ
PQ
读“当且仅当”
00
1
例(a)两个三角形全等当且仅当
三角形的三条边全部相等。
01
0
(b)2+2=4,当且仅当雪是白的。 1 0
0
11
1
20
中北大学离散数学课程组
1.2 命题联结词
设命题P,Q表示任意两个命题,则最常见的命题联结词有：
联接词 记号 复合命题 读法
2020/6/30
27
中北大学离散数学课程组
例
设命题
P：明天上午七点下雨； Q：明天上午七点下雪；
R：我将去学校。
符号化下述语句：
1) 如果明天上午七点不是雨夹雪，则我将去学校
2) 如果明天上午七点不下雨并且不下雪，则我将去
学校 可可符符号号化化为为：:(┐P∨(PQ∧)→Q┐)→R。R。
3) 如果明天上午七点下雨或下雪，则我将不去学校 可符号化为:(┐P∧┐Q)→R。
联结词
自然语言
∧
既…又…、不仅…而且…、虽然…但
是…、并且、和、与，等等；
→
如P则Q、只要P就Q、P仅当Q、只有Q才P、
除非Q否则P，等等
↔
等价、当且仅当、充分必要、等等；
相容（可兼）的或
2020/6/30
23
中北大学离散数学课程组
例
符号化下列命题 （1）四川不是人口最多的省份； （2）王超是一个德智体全面发展的好学生； （3）教室的灯不亮可能是灯管坏了或者是停电了； （4）如果周末天气晴朗，那么学院将组织我们到春
2020/6/30
26
中北大学离散数学课程组
七、约 定
为了不使句子产生混淆，作如下约定，命题联结 词之优先级如下：
(1)否定→合取→析取→条件→等价 (2)同级的联结词，按其出现的先后次序(从左到右) (3)若运算要求与优先次序不一致时，可使用括号；
同级符号相邻时，也可使用括号。括号中的运算 为最优先级。
2020/6/30
7
中北大学离散数学课程组
1.1 命题及其表示
一、命题 命题：能判断真假的陈述句。
2020/6/30
8
中北大学离散数学课程组
例.
（1）雪是黑色的； （2）中国位于亚洲； （3）北京是中国的首都； （4）ｘ+y>0； （5）我喜欢踢足球； （6）3能被2整除； （7）明年的十月一日是晴天； （8）地球外的星球上也有人； （9）我正在说谎；
(GH)也是合式公式； （4）当且仅当能够有限次地应用（1）,（2）,（3）
所得到的包含命题变元，联结词和括号的符号串是 合式公式。
2020/6/30
32
中北大学离散数学课程组
例
符号串：P∧(Q∨R)→(Q∧(┐S∨R))；
┐P∧Q； P→(┐(P∧Q))； ((P→Q)∧(R→Q))(P→R)。 等都是命题公式。
则命题（2）可表示为Ｐ∧Ｑ∧R。
（3）设Ｐ：教室的灯不亮可能是灯管坏了
Ｑ：教室的灯不亮可能是停电了
则命题（3）可表示为Ｐ∨Ｑ。
2020/6/30
25
中北大学离散数学课程组
例 解(续)
（4）设Ｐ：周末天气晴朗； Ｑ：学院将组织我们春游。
则命题（4）可表示为Ｐ→Ｑ。 （5）设Ｐ：两个三角形全等；
Ｑ：三角形的三条边全部相等。 则命题（5）可表示为ＰＱ。 (6) P:张辉与王丽是同学
数理逻辑在问路问题中、排队论问题中的应用有 很多。
例如：有A,B两个相邻的小岛，A岛居民是诚实人 ，B岛居民都是骗子。一个旅游者独自登上了两 岛中的某个岛，他分辨不清这个岛是A岛还是B岛 ，只知道这个岛上的人既有本岛的，也有另一个 岛的，此旅游者用什么办法判定这是哪个岛。 通过提问的方式解决。
5
中北大学离散数学课程组
或P=0,Q=0
2020/6/30
21
中北大学离散数学课程组
六、说明
（1）联结词是句子与句子之间的联结
（2） 联结词是两个句子真值之间的联结，而非 句子的具体含义的联结，两个句子之间可以无 任何地内在联系
2020/6/30
22
中北大学离散数学课程组
六、说明
（3）联结词与自然语言之间的对应并非一一对应；
中北大学离散数学课程组
1.2 命题联结词
注意：
运算∨：表示“可兼或”，不能表示“排斥 或”（举例说明）
例：选小王或小李中一人去开会。
注：“排斥或”用∨表示；
17
中北大学离散数学课程组
1.2 命题联结词
四、蕴含联结词“”（条件联结词） 相当于自然语言中的“若…则…”、
“如果…就…”、“只有…才…”，
13
中北大学离散数学课程组
1.2 命题联结词
一、否定联结词“¬” 是一元联结词。读做“非”
例如： P： 上海是一个城市。
P：上海不是一个城市。
P ¬P
0
1
1
0
14
中北大学离散数学课程组
1.2 命题联结词
二、合取联结词“∧”
二元联结词。读做“与”、“且”
例如：
P
（1）P：今天下雨，Q：明天下雨， 0
2020/6/30
28
中北大学离散数学课程组
作业： （1）指出下列语句哪些是命题，哪些不是命题，
如果是命题，指出它的真值。 a.离散数学是计算机科学系的一门必修课。 b.计算机有空吗？ c.明天我去看电影。 d.请勿随地吐痰！ e.不存在最大质数。 f.如果我掌握了英语、法语，那么学习其他欧洲语
言就容易得多。 g.9+5≤12。
例 符号串： (P→Q)∧┐Q)；(┐P∨Q∨(R； P∨Q∨。
等都不是合法的命题公式。
2020/6/30
33
中北大学离散数学课程组
例1：以符号形式写出命题：我们要做到身体好、 、工作好，为祖国四化建设而奋斗。
解：找出各原子命题，并用命题符号表示： A:我们要做到身体好。 B:我们要做到学习好。 C:我们要做到工作好。 P:我们为祖国四化建设而奋斗。