离散数学课件资料

在命题“如果2是素数，3也是素数”中，设 p 表 示“2是素数”，q 表示“3是素数”，则 p q 表示 “如果2是素数，则3也是素数”。
联结词“只要 p 就 q ”，“ p 仅当 q ”，“只有q才p ” 等，都表示q是p的必要条件,因此都可符号化为 p q 。
2020/11/15
离散数学
14
设p：王一乐是计算机系的学生，q：他生于1968年，r：他生于 1969年，s：他是三好学生，则符号化为：p (q r) s220/11/15离散数学
19
§1.2 命题公式及其赋值
一、命题公式的概念
合式公式： (1) 单个命题常项或变项p, q, …, 0, 1是合式公式； (2) 若A是合式公式，则 A也是合式公式； (3) 若A, B是合式公式，则(A B), (A B), (A B), (A B)是合式公式;
离散数学
3
第一章 命题逻辑
§1.1 命题符号化与联结词 §1.2 命题公式及其赋值 §1.3 等值演算 §1.4 联结词的完备集 §1.5 对偶与范式 §1.6 推理理论
2020/11/15
离散数学
4
§1.1 命题符号化及联结词
一、命题的概念
命题：能判断真假的陈述句。这种判断只有两种 可能，一种是正确的判断，一种是错误的 判断。
11 1
0
表1.4
(pq) q 0 0 0 0
2020/11/15
离散数学
26
三、命题公式的类型
1、重言式(或永命真题式公)：式A在各种赋值下取 值恒为真，则A为重言式。
2、矛盾式(或永命假题式公)：式A在各种赋值下取 值恒为假，则A为矛盾式。
3、可满足命式题：公式A至少存在一组赋值是成真 赋值，则A为可满足式。
2020/11/15
离散数学
9
三、联结词
先看一个例子：
例2：判断下列命题是否为复合命题，说出其联结词。
(1) 3不是偶数。
(非)
(2) 2是偶素数。
(且)
(3) 2或4是素数。
(或)
(4) 如果2是素数，3也是素数。 (如果…,则…)
(5) 2是素数当且仅当4也是素数。 (当且仅当)
2020/11/15
若指定的一组真值使命题公式A的真值为1，则 称这组赋值为A的成真赋值；若使A的真值为0，则 称这组赋值为A的成假赋值。
将命题公式A在所有赋值下的取值情况列成表，
称为A的真值表。
2020/11/15
离散数学
21
二、命题公式的解释或赋值（真值表）
构造真值表的步骤：
(1)找出命题公式中所有命题变项：p1 , p2 , …, pn , 列出所有可能的赋值(2n个)。
2020/11/15
离散数学
23
二、命题公式的解释或赋值（真值表）
(1) ( p) q
真值分析如下：
p q ( p) q ( p) q
00 0
1
0
01 0
0
0
10 1
1
1
11 1
0
0
表1.2
2020/11/15
离散数学
24
二、命题公式的解释或赋值（真值表）
(2) (p ( p q )) q
(5) 2050年元旦是晴天。
(是)
(6) 5x + 1 > 11。
(否)
(7) 这朵花真美丽呀！
(否)
(8) 明天下午开会吗？
(否)
(9) 我正在说假话。
(否)
2020/11/15
离散数学
6
解题思想：判断一个句子是否为命题，首先看它 是否为陈述句，其次看它的真值是否唯一。
2020/11/15
离散数学
真值分析如下：
p q pq p(pq)
00 1
0
01 1
0
10 0
0
11 1
1
(p ( p q )) q 1 1 1 1
表1.3
2020/11/15
离散数学
25
二、命题公式的解释或赋值（真值表）
(3) ( p q ) q
真值分析如下：
p q pq (pq)
00 1
0
01 1
0
10 0
1
2020/11/15
离散数学
2
数理逻辑
逻辑学:研究思维(或推理)的形式结构和规 律的学科。利用数学方法研究思维(或推理)的形式 结构和规律的学科，称作数理逻辑。
数理逻辑的基本内容：命题逻辑(演算)、 谓词逻辑。它们对电子元件设计和性质分析， 对逻辑程序设计语言的研制具有十分重要的意 义。
2020/11/15
设p:天下雨,q:我骑自行车上班, 逐 个p是联q结的起必来要，条组件则 成一复合命题的符
(4) 如符果号化下为雨q，我就p不骑自行车号上化班形。式。
设p:天下雨,q:我骑自行车上班,则符号化为p q
(5) 我去书店看看，除非我很累。
设p:我很累,q:我去书店看看,则符号化为 p q
2020/11/15
(4) 只有有限次地应用(1) ～ (3)组成的符号串才是 合式公式。 合式公式即称为命题公式。
2020/11/15
离散数学
20
二、命题公式的解释或赋值
一个含有命题变项的命题公式的真值是不确定的， 只有用指定的命题常项代替后真值才唯一确定。
设A为一命题公式，p1, p2, … , pn为出现在A中的 所有的命题变项。给p1, p2, … , pn指定一组真值，称 为对A的一个赋值或解释。
联结词“既…又…”，“不但…而且…”，“虽然…但 是…”等，都可符号化为 。
2020/11/15
离散数学
12
三、联结词（续）
3、析取联结词“ ”，读作“析取”。 复合命题“ p或q ”称作 p与q 的析取式，记作“p q ”。 p q 为真当且仅当 p 与 q 中至少一个为真。
在命题“2或4是素数”中，设 p 表示“2是素数”， q 表示“4是素数”，则 p q 表示“2或4是素数”。
命题真值：判断为正确的命题称其命题真值为真(1) ； 判断为错误的命题称其命题真值为假(0) ； 命题是具有唯一真值的陈述句。
2020/11/15
离散数学
5
例1 判断下列句子中哪些是命题。
(1) 4是素数。
(是)
(2) 2 + 3 = 5。
(是)
(3) 雪是黑色的。
(是)
(4) 3能被2整除。
(是)
可满足式。
2020/11/15
离散数学
28
§1.3 等值演算
一、等值演算的概念
等值公式：设A, B为两命题公式，若等价式A B 是重言式，称A与B等值。记作:A B
等值关系是自反的、对称的和传递的，因而为 等价关系。用真值表可以验证公式等值。
三、联结词（续）
5、等价联结词“ ”，读作“等价”。 复合命题“ p 当且仅当 q ”称作 p 与 q 的等价式，记 作“ p q ”。 p q 为真当且仅当 p 与 q 真值相同。
在命题“2是素数当且仅当4也是素数”中，设 p 表示“2是素数”，q 表示“4是素数”，则 p q
表示“2是素数当且仅当4是素数”,由于p、q的真值
7
二、与命题相关的几个概念
1、简单命题(或原子命题)： 命题为简单的陈述句，不能分解成更简单的句子。
一般用小写的英文字母p, q, r, …表示。
2、命题常项(或命题常元)： 由于简单命题的真值确定，故又称之为命题常项 或命题常元。 如例1中的陈述句(1) (2) (3) (4) (5)。
2020/11/15
2020/11/15
离散数学
1
离散数学，是现代数学的一个重要分支， 是计算机科学中基础理论的核心课程。离散数 学是以研究离散量的结构和相互间的关系为主 要目标，其研究对象一般地是有限个或可数个 元素，因此充分描述了计算机科学离散性的特 点。
离散数学是随着计算机科学的发展而逐步 建立的， 它形成于七十年代初，是一门新兴的 工具性学科。
参考教材：
1、《离散数学》、《离散数学 理论.分析.题解》
左孝凌、李为鑑、刘永才，上海科学技术文献出版社
2、《离散数学》（修订版）
耿素云、屈婉玲，高等教育出版社
3、《离散数学》（第三版）
耿素云、屈婉玲、张立昂，清华大学出版社
4、《离散数学及其应用》（原书第5版）
（美）Kenneth H.Rosen著，袁崇义、屈婉玲、王悍贫、 刘田 译， 机械工业署版社
2020/11/15
离散数学
27
三、命题公式的类型
从以上定义可以看出以下几点：
1、可满足式至少存在一组成真赋值。 2、重言式一定是可满足式，反之不真。 3、真值表可以用来判断公式的类型： （1）若真值表最后一列全为1，则公式为重言式； （2）若真值表最后一列全为0，则公式为矛盾式； （3）若真值表最后一列至少有一个1，则公式为
(2)按从低到高的顺序列出命题公式的各个运算层次。 (3)对应每个赋值，计算命题公式各层次的值，直到
最后计算出命题公式的值。 命题运算的优先级顺序：(1)先括号 (2) (3) , (4) (5) (6) 从左至右
2020/11/15
离散数学
22
二、命题公式的解释或赋值（真值表）
例4：求下列命题的真值表 (1) ( p) q (2) ( p ( p q )) q (3) ( p q ) q
注意：“或”的二义性。如命题：派小王或小李中 的一人去开会，应符号化为( p q ) ( p q ), 这类“或”表达的是排斥或。
2020/11/15
离散数学
13
三、联结词（续）