离散数学导论(第5版)-第一篇

⇔0↔q
（矛盾律）
⇔ ( p → q) ∧ (q → 0)
（等价等值式）
⇔ (¬0 ∨ q) ∧ (¬q ∨ 0)
（蕴含等值式）
⇔ (1∨ q) ∧ ¬q
（同一律）
⇔ 1∧ ¬q
（零律）
⇔ ¬q
（同一律）
到最后一步已将公式化得很简单。由此可知，无论 p 取 0 或 1 值，只要 q 取 0 值，原公式取值为 1，即 00 或 10 都为原公式的成真赋值，而 01，11 为成假赋 值，于是公式为非重言式的可满足式。
（蕴含等值式）
⇔ p ∨ ¬q ∧ q
（德·摩根律）
⇔ p ∨ (¬q ∧ q)
（结合律）
⇔ p∧0
（矛盾律）
⇔0
（零律）
由最后一步可知，（3）为矛盾式。
（5）用两种方法判（5）为非重言式的可满足式。
真值表法
p
q
¬p
¬p → q q → ¬p (¬p → q) → (q → ¬p)
0
0
1
0
1
1
0
1
1
（10）p：小李在宿舍里. p 的真值则具体情况而定，是确定的。 （12） p ∨ q ，其中， p : 4 是偶数，q : 4 是奇数。由于 q 是假命题，所以，q 为假命题， p ∨ q 为真命题。 （13）p ∨ q ，其中，p : 4 是偶数，q : 4 是奇数，由于 q 是假命题，所以，p ∨ q 为假命题。 （14） p：李明与王华是同学，真值由具体情况而定（是确定的）。 （15） p：蓝色和黄色可以调配成绿色。这是真命题。 分析 命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不 能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令 p : 2 + 2 = 4, q : 3 + 3 = 6, 则以下命题分别符号化为 （1） p → q （2） p → ¬q （3） ¬p → q （4） ¬p → ¬q （5） p ↔ q （6） p ↔ ¬q （7） ¬p → q （8） ¬p ↔ ¬q 以上命题中，（1），（3），（4），（5），（8）为真命题，其余均为假命题。 分析 本题要求读者记住 p → q 及 p ↔ q 的真值情况。p → q 为假当且仅当 p 为真,q 为假,而 p ↔ q 为真当且仅当 p 与 q 真值相同.由于 p 与 q 都是真命题， 在 4 个蕴含式中，只有（2） p → r ，其中，p 同（1），r：明天为 3 号。 在这里，当 p 为真时，r 一定为假， p → r 为假，当 p 为假时，无论 r 为真 还是为假， p → r 为真。

何情况下真值相同。
12
命题与联结词
2. 合取 符号：
定义1.2：设p，q为二命题，复合命题“p并且q”（或“p与q”）称为p 与q的合取式，记作pq ，符号称为合取联结词。并规定pq 为真当且仅当p与q同时为真时为真。 真值表：
P Q 0 0 0 1 1 0 1 1 P 0 0 0 1
Q
p:天下雨。 q:我骑自行车上班。 s:2+2=4。 t:太阳从东方升起
r:太阳从西方升起。
19
命题与联结词
5. 等价 符号：
定义1.5：设p ，q为二命题，复合命题“p 当且仅当 q” 称为p与q的等 价式，记作p q ，符号 称为等价联结词。并规定p q为真当且仅当p与q同时为真或同时为假。 真值表：
25
等值式
一、等值 1. 定义2.1
设A、B是两个命题公式，若A，B构成的等价式AB为重 言式，则称A与B是等值的，记作AB。
2.
注意
不是联结符，它是用来说明A与B的等值，要与区分清楚。
3.
如何判断两个命题公式是否等值？
方法一：通过真值表比较在各相同赋值情况下，真值是否相同。 方法二：将A，B构成 AB等价式，判断其是否为重言式。
② 设P: 明天下雨, Q: 明天下雪, R: 我去学校。 则 (i) “如果明天不是雨夹雪则我去学校”可写成 (ii) “如果明天不下雨并且不下雪则我去学校”可写成 (iii) “如果明天下雨或下雪则我不去学校”可写成 (iv) “ 当 且 仅 当 明 天 不 下 雪 并 且 不 下 雨 时 我 才 去 学 23 校 ; ; ; ;
p:张明正在睡觉。 q:张明正在游泳
p q
排斥或
p:李强是位排球队员。 q:李强是位足球队员 pq 相容或 p:张静挑选202房间。 q:张静挑选203房间 （ p q）（p q）

7
9.1二元运算及其性质
例6：设S={1,2},给出P(S)上的运算～和的运算表， 其中全集为S。
P(S)={,{1},{2},{1,2}}
ai
~ai
{1} {2} {1,2}
{1} {2} {1,2}
{1,2} {1} {2}
{1} {2} {1,2} {1} {1} {1,2} {2} {2} {2} {1,2} {1}
设V1=<S1,>,V2=<S2,*>是代数系统， 和*是二元运算。 如果存在映射：S1S2，若x，yS1都有
(xb)=(x)*(y)
则称是V1到V2的同态映射，简称同态。
35
9.2 代数系统
例14： (1)G1=<Z,+>，G2=<Zn,>,令
：ZZn，(x)=(x)modn
则是否为G1到G2的同态？
六、消去律（定义9.7）
设为S上的二元运算,如果对于任意的x,y,zS满足以下 条件：
(1)若xy=xz且x，则y=z。 (2)若yx=zx且x，则y=z。 那么称运算满足消去律，其中(1)称作左消去律，(2)称作 右消去律。
24
9.1二元运算及其性质
例10：设是字母的有穷集，称为字母表，中的有限 个字母组成的序列称为上的串，对任何串，串中字 母的个数叫做串的长度，记作||，长度是0的串叫空 串，记作，对任给的自然数k，令
f:ZZZ
1 )f(x ,y )x y
2 )f( x ,y ) x y
3 )f(x ,y )xy
4 )f( x ,y ) x y
4
9.1二元运算及其性质
例2： f:R*R*R*(其R 中 *是非零 ) 实数

3
复合联结词
与非式: pq(pq) 或非式: pq(pq)
和与, ∧,∨有下述关系: p(p∧p)pp p∧q( p∧q)(pq)(pq)(pq) p∨q(p∧q)(p)(q)(pp)(qq)
4
复合联结词(续)
ppp p∧q(pp)(qq) p∨q(pq)(pq)
13
例ቤተ መጻሕፍቲ ባይዱ续)
解 编号
极小项
角码 标记
1 x1∧x2∧x3∧x4 2 x1∧x2∧x3∧x4 3 x1∧x2∧x3∧x4
1110 * 1011 * 0111 *
4 x1∧x2∧x3∧x4 1010 * 5 x1∧x2∧x3∧x4 0101 * 6 x1∧x2∧x3∧x4 0011 *
1.5 联结词全功能集
联结词全功能集 与非联结词,或非联结词
1
联结词的全功能集
定义 设S是一个联结词集合，如果任何n(n1) 元 真值函数都可以由仅含S中的联结词构成的公式表 示，则称S是联结词全功能集.
说明：若S是联结词全功能集，则任何命题公式都 可用S中的联结词表示.
设S1, S2是两个联结词集合，且S1 S2. 若S1是全
x y
x∧y x y
x∨y x
x
与门
或门
非门
8
组合电路的例子
(x∨y)∧x的组合电路
x y
x y
第一种画法
x 第二种画法
9
例
例 楼梯的灯由上下2个开关控制, 要求按动任何一个 开关都能打开或关闭灯. 试设计一个这样的线路. 解 x,y:开关的状态, F:灯的状态, 打开为1, 关闭为0. 不妨设当2个开关都为0时灯是打开的.
(5,7) x1∧x3∧x4 001 *

R 0 1 0 1 0 1 0 1
Assignments（作业）
第30页: 4
1.3 公式分类与等价式
1.3.1 公式分类 1.3.2 等价公式（等值演算） 1.3.3 基本等价式----命题定律 1.3.4 代入规则和替换规则 1.3.5 证明命题公式等价的方法
1.3.1 公式分类
定义1.13 设A是一个命题公式，对A所有可能的解释： (1)若A都为真，称A为永真式或重言式。
(2)若A都为假，称A为永假式或矛盾式。
(3)若至少存在一个解释使得A为真，称A为可满足式。
例1 从上一节真值表可知，命题公式(PQ)(P∨Q)为 重言式，(PQ)∧Q为矛盾式，PQ)∧R为可满足式。
注： 1、 永真式必为可满足式，反之则不然；永真式的否定是永 假式，反之亦然； 2、 决定一个公式是否是一个永真式、永假式或可满足式有 三种方法：真值表法（适用于变元少而简单的公式）、求主范
1.否定词(negation connective )﹁
定义1.4 复合命题“非P”称为命题P的否定，记作
P，读作非P。 P为真当且仅当P为假。
例3 设 P：离散数学是计算机专业的核心课程， 则 P:离散数学不是计算机专业的核心课 程。
2.合取词(conjunction connective )∧
命题符号化的目的在于用五个联结词将日 常语言中的命题转化为数理逻辑中的形式命题， 其关键在于对自然语言中语句之间的逻辑关系 以及命题联结词的含义要有正确的理解，使用 适当的联结词： （1）确定语句是否是一个命题；
（2）找出句中连词，用适当的命题联结词表
示。
Assignments（作业）
第30页: 3（偶数小题）
定义1.12 设A是含有n个命题变元的命题 公式，将命题公式A在所有赋值之下取值的情 况汇列成表，称为A的真值表( truth table )。 为列出一个公式的真值表，我们约定： ①命题变元按字典序排列；②对公式的每个 解释，以二进制从小到大列出；③当公式较 复杂时，可先列出子公式的真值，最后列出 所给公式的真值。

例2： “派小王或小李中的一人去开会” 不能符号化为形式P∨Q ，因为这里的“或”表示 的是排斥或。它表示非此即彼，不可兼得。 运算符 ∨表示可兼或，排斥或以后用另一符号表达。也可
以借助于联结词
或。
┒、∧ 、∨共同来表达这种排斥
课堂练习： 将下列命题符号化: (1) 王东梅学过日语或俄语。 (2) 张小燕生于1977年或1978年。 (3) 小元元只能拿一个苹果或一个梨。
常称为“非”运算，所有可能的运算结果可用下表
（真值表）表示。
P
┒P
T F
F T
例: (a) P: 3是偶数。
则┑P： 3不是偶数。
(b)
的”。 (c) (d)
Q: 4 是质数。
则┑Q： 4 不是质数。或 “说4 是质数是不对 R: 我们都是汉族人。 则┒R: 我们不都是汉族人。 S: 今天下雨并且今天下雪。 则 ┒S:今天不下雨或者今天不下雪。
Q：明天下雨
是两个命题，利用联结词“不”、“并且”、 “或” 等可分别构成新命题： “明天不下雪”； “明天下雪并且明天下雨”； “明天下雪或者明天下雨”等。
即 ： “非P”；
“P并且Q”；
“P或Q”等。 在代数式x+3 中， x 、 3 叫运算对象， +叫运 算符，x+3 表示运算结果。在命题演算中， 也用同样术语。 联结词就是命题演算中的运算符，叫逻辑运算符或叫命题联 结词。常用的命题联结主要有 5 个。
2.常用命题联结词 1）. 否定词┑ 定义：设P为任一命题。复合命题“非P”(或“P的 否定”)称为P的否定，记作 ┑P，读作“非P”。┒ 为否定联结词。┑P为真当且仅当P为假。 由定义可知， ┑P 的逻辑关系为P不成立，因而P

(3).由真值表可知，公式A为可满足式.
5、谓词公式的符号化. 准确地从语句中提取谓词，表示性质的谓语用一
元谓词表示，表示关系的谓语用二元或更多元数的 谓词来表示，准确地使用量词和适当的逻辑联结词 把原语句表示为谓词公式. 例：设N(x)：x是自然数. I(x)：x是整数. 则语句： “所有的自然数都是整数”可表示为谓词公式：
x(N ( x) I( x)) 设N(x)：x是自然数. E(x)：x是奇数. 则语句： “有些自然数是奇数”可表示为谓词公式：
x(N( x) E( x))
当个体域D是有限集合时, D a1 , a2 ,, an
利用下列等价式可以消去谓词公式中的量词
xp( x) p(a1 ) p(an ) xp( x) p(a1 ) p(an )
命题公式的类型可用以下方法判定： （1）真值表的方法 （2）利用已知永真式及代入、替换原理进行等价推 演的方法. （3）利用主析取范式和主合取范式的方法.
5、命题公式的范式（主析取范式、主合取范式）, 求命题公式的范式的方法: （1）利用真值表的方法. （2）等价推演的方法.
例. 命题公式的范式. 设命题公式为
整数集合上的等价关系：模n的相等关系（模n的 同余关系）,确定由模n的相等关系确定的等价类的 元素.
例：设R是集合A={1，2，….10}上的模3同余关系，
则
2 2，5，8，3 3，6，9，1 1,4,7,10
第六章
1、函数的概念及运算 2、特殊函数：单射、满射、双射的判定.
i 1
假如n为奇数，则所有结点度数之和也为奇数， 这与握手定理相违，故n必为偶数。
第九章 树 1、树的定义及等价定义 问题：设是具有个顶点的树，问其顶点度数之和等 于多少？ 2、生成树的概念

图的连通性
04
CHAPTER
逻辑基础
命题逻辑中的基本概念包括命题、真值和逻辑运算，通过这些基本概念可以表达和推理复杂的命题关系。
命题逻辑在计算机科学、人工智能、自动化等领域有广泛应用，是形式化方法的重要基础。
命题逻辑是研究命题之间关系的逻辑分支，主要涉及命题的否定、合取、析取、蕴含等基本运算。
命题逻辑
详细描述
集合的运算包括并集、交集、差集等。并集是指两个或多个集合合并为一个新的集合，包含所有元素；交集是指两个或多个集合中共有的元素组成的集合；差集是指从一个集合中去掉另一个集合中的元素后剩余的元素组成的集合。这些运算在离散数学中有着广泛的应用。
总结词
集合的运算
集合的基数是指集合中元素的个数，通常用大写字母表示。
鸽巢原理
THANKS
感谢您的观看。
集合论
图论是研究图（由节点和边构成的结构）的数学分支，它广泛应用于计算机科学和工程学科。
图论
逻辑是离散数学的另一个重要分支，它研究推理的形式和规则，是计算机科学和人工智能的基础。
逻辑
组合数学是研究计数、排列和组合问题的数学分支，它在计算机科学和统计学中有重要的应用。
组合数学
离散数学的研究内容
02
CHAPTER
离散数学课件第一章
目录
绪论 集合论基础 图论基础 逻辑基础 组合数学基础
01
CHAPTER
绪论
离散数学是研究离散对象（如集合、图、树等）的数学分支，它不涉及连续的量或函数。
离散数学的定义
离散数学的起源
离散数学的特点
离散数学的起源可以追溯到古代数学，如欧几里得几何和数论。
离散数学强调结构、关系和组合，而不是连续性和微积分。

•
从图中可以看出，函数g使得
不但X中的每一个元素xi唯一对应一 个Y中的一个元素yj，而且也只有一 个xi对应yj，也就是说一个像只有
28
§3.2 复合函数、反函数、多
元• 函数
•
（3）两种运算：
•
• 复合运算（复合函数）设函
数f：XY，g：YZ则复合函数h＝gf：
XZ 是一个新的函数。
•
定 义 ： 设 函 数 f ： XY ， g ：
• • 自反闭包 r (R)
• • 对称闭包 s (R）
•
•
传递闭包
t
(R）
• （2）闭i=1 包的公式：
19
§2.6 次序关系
• （7）次序关系
• • 四个定义：
•
偏序关系：X上自反、反对称与
传递的关系称偏序关系
• 并用‘≤ ’表示。
• 拟序关系：反自反、传递的关系 称拟序关系并用‘< ’表示。
• 2）交换律：a ＋ b＝b ＋ a
• 3）分配律：a ＋ （b×c）＝（a ＋ b） ×（a＋ c）
• 4）单位元：a ＋ e＝a
• 5）逆元：a ＋ a－1＝ e
• 6）零元：a ＋ Θ＝Θ
39
§5.3 同构与同态
• （4）同构：（X， ）与（Y，）
存在一一对应函数g : XY使 得如
x1 , x2X，则有 ：g（x1 x2）＝g （x1）g（x2）此时则 称（X, ）与
• • 关系的自反性 • • 关系的反自反性 • • 关系的对称性 • • 关系的反对称性 • • 关系的传递性
17
• （6）六种常用关系
• • 次序关系之一：偏 序关系
• • 次序关系之二：拟 序关系

5,
1 1
10
2,
2 0
11
3,
2 2
01
第8页8
积代数性质
设 V1 = <S1,o>和 V2 = <S2,>是代数系统，其中 o 和 是二元运算. V1 与 V2 积代数是 V=<S1S2,∙> (1) 若 o 和 运算是可交换，那么∙ 运算也是可交换 (2) 若 o 和 运算是可结合，那么∙ 运算也是可结合 (3) 若 o 和 运算是幂等，那么∙ 运算也是幂等 (4) 若 o 和 运算分别含有单位元 e1 和 e2，那么∙ 运算
实例 N是<Z,+> 和<Z,+,0>子代数. N{0}是<Z,+> 子代数，但不是<Z,＋,0>子代数
说明： 子代数和原代数是同种代数系统 对于任何代数系统 V ，其子代数一定存在.
第6页6
关于子代数术语
最大子代数 就是V 本身. 假如V 中全部代数常数组 成集合 B，且 B 对V 中全部运算封闭，则 B 就组 成了V 最小子代数. 最大和最小子代数称为V 平凡 子代数. 若 B 是 S 真子集，则 B 组成子代数称为V 真子代数 . 例2 设V=<Z,+,0>，令 nZ = { nz | z∈Z}，n 为自然 数，则 nZ 是 V 子代数, 当 n = 1 和 0 时，nZ 是 V 平凡子代数，其它都是 V 非平凡真子代数.
第111页1
例题
例1 V=<R*,>, 判断下面哪些函数是V 自同态？ (1) f(x)=|x| (2) f(x)=2x (3) f(x)=x2 (4) f(x)=1/x (5) f(x)= x (6) f(x)=x+1