北京大学离散数学教材 2
- 格式：pdf
- 大小：61.32 KB
- 文档页数：16
文档推荐
-
离散数学课程.页数:31
-
北大离散数学07页数:54
-
离散数学课后习题答案 (邱学绍)页数:76
-
北大离散数学ppt课件页数:61
下载文档原格式
合集下载
离散数学(第四版)讲义1
引言Discrete Math.离散数学研究离散对象及其相互间关系的一门数学学科。
研究离散结构的数学分支。
（辞海）计算机科学、信息科学、数字化科学的数学基础离散数学的内容：数理逻辑(Mathematics Logic)集合论(Sets)代数结构(Algebra Structure)图论(Graph Theory)组合论(Combination)线性代数(Linear Algebra)概率论(Probability Theory)……与高等数学的区别教学内容：数理逻辑(Mathematics Logic)集合论(Sets)代数结构(Algebra Structure)图论(Graph Theory)离散数学的由来与发展：一、古老历史：计数：自然数发展：图论：Konigsberg七桥问题二、年青新生：计算机：二进制运算离散数学课程设置：计算机系核心课程信息类专业必修课程其它类专业的重要选修课程离散数学的后继课程：数据结构、编译技术、算法分析与设计、人工智能、数据库、……离散数学课程的学习方法：强调：逻辑性、抽象性；注重：概念、方法与应用参考教材：1、离散数学（耿素云，屈婉玲，北大版）2、离散数学（方世昌，西安电子科大版）3、离散数学结构（第三版、影印版）（Bernard Kolman、Robert C.Busby、Sharon Ross，清华版）4、离散数学提要与范例（阮传概、卢友清，北京广播学院版）第一章命题逻辑（Proposition Logic）1、命题符号化及联结词2、命题公式及分类3、等值演算4、联结词全功能集5、对偶与范式6、推理理论逻辑学：研究推理的一门学科数理逻辑：用数学方法研究推理的一门数学学科——一套符号体系+ 一组规则数理逻辑的内容：古典数理逻辑：命题逻辑、谓词逻辑现代数理逻辑：逻辑演算、公理化集合论、递归论、模型论、证明论1、命题符号化及联结词命题(Proposition)：一个有确定真或假意义的语句。
Ramsey定理 北京大学计算机系离散数学讲义(ppt版)
2020/10/7
W1 W2 W3 W4 W5 W11 W12 W13 W14 W15 W6 W7 W8 W9 W10
20
S10
方案的最优性
满足目标要求： 任取 10 个工作站. 如果恰好为 W1,W2,…,W10，Wi 访问 Si，i=1,…10, 满足要求; 如果 W1-W10 中只选中 k 个工作 站，不妨设为 W1--Wk, 剩下的 10-k 个选自 W11-W15. 那 么 Wi 访问 Si，i=1,…,k. 还剩下 10-k 个服务器空闲，恰好 分配给 10-k 个工作站.
保证这组工作站可以同时访问不同的服务器.
问题：达到这个目标需要的最少缆线数目 N 是多少？
方案 1：每个工作站都连到每个服务器，需要
1015=150
2020/10/7
根缆线，N 150.
例11的解决方案
方案 2 将工作站标记为 W1,W2, …, W15, 服务器标记为 S1,S2, …, S10. 对于 k=1,2,…,10，我们连接 Wk 到 Sk, 剩下 5 个工作站的每一个都连接到 10 个服务器 总共 60 条直接连线.
2020/10/7
简单Ramsey定理的推广
(1) R(p,q)的集合表述：
Kn 的顶点集 V
集合 S
Kn 的边集 E
S 的 2 元子集的集合 T
用 2 色涂色 Kn 的边 将 T 划分成 E1,E2
存在蓝色完全 p 边形 存在 S 的 p 子集，其所有 2 元子集E1
存在红色完全 q 边形 存在 S 的 q 子集，其所有 2 元子集E2
对于 K8，存在一种涂色方案， 既没有蓝色三角形，也没有红 色完全四边形.
R(3,4)=9.
2020/10/7
W1 W2 W3 W4 W5 W11 W12 W13 W14 W15 W6 W7 W8 W9 W10
20
S10
方案的最优性
满足目标要求： 任取 10 个工作站. 如果恰好为 W1,W2,…,W10，Wi 访问 Si，i=1,…10, 满足要求; 如果 W1-W10 中只选中 k 个工作 站，不妨设为 W1--Wk, 剩下的 10-k 个选自 W11-W15. 那 么 Wi 访问 Si，i=1,…,k. 还剩下 10-k 个服务器空闲，恰好 分配给 10-k 个工作站.
保证这组工作站可以同时访问不同的服务器.
问题：达到这个目标需要的最少缆线数目 N 是多少？
方案 1：每个工作站都连到每个服务器，需要
1015=150
2020/10/7
根缆线，N 150.
例11的解决方案
方案 2 将工作站标记为 W1,W2, …, W15, 服务器标记为 S1,S2, …, S10. 对于 k=1,2,…,10，我们连接 Wk 到 Sk, 剩下 5 个工作站的每一个都连接到 10 个服务器 总共 60 条直接连线.
2020/10/7
简单Ramsey定理的推广
(1) R(p,q)的集合表述：
Kn 的顶点集 V
集合 S
Kn 的边集 E
S 的 2 元子集的集合 T
用 2 色涂色 Kn 的边 将 T 划分成 E1,E2
存在蓝色完全 p 边形 存在 S 的 p 子集，其所有 2 元子集E1
存在红色完全 q 边形 存在 S 的 q 子集，其所有 2 元子集E2
对于 K8，存在一种涂色方案， 既没有蓝色三角形，也没有红 色完全四边形.
R(3,4)=9.
2020/10/7
精品文档-离散数学(第二版)(武波)-第2章
第2章 谓词逻辑
例如， “x是偶数”可以用谓词P(x)表示， P(2)、 P(3) 分别表示“2是偶数”、 “3是偶数”。 “x小于y”可以用 谓词Q(x， y)表示， Q(5， 7)、 Q(6， 5)分别表示“5小于 7”、 “6小于5”。 “x在y和z之间”可以用谓词R(x, y, z)表示， R(a, b, c)表示“a在b和c之间”。
第2章 谓词逻辑
定义2.3.3 设A是谓词公式， 如果对于任何赋值， A的 真值都为真， 则称谓词公式A是永真式； 如果对于任何赋值， A的真值都为假， 则称谓词公式A是永假式； 若存在一种赋 值， 使得A的真值为真， 则称谓词公式A是可满足式。
由定义可知， 对于任意谓词公式A， 若A是永真式， 则 A在特定论域E上永真； 若A是永假式， 则A在特定论域E上永 假； 若A在特定论域E上可满足， 则A是可满足式。
…… n元谓词用于刻画n个个体之间的关系， 由一个表示n个 个体关系的大写字母(称为n元谓词符、 n元关系符)和n个个 体常元或变元组成的表达式表示， 如R(a1, a2, …, an)、 R(x1, x2, …, xn )等。 根据以上约定， 谓词就可以简单地描述为是由一个谓词 符和若干具有有固定次序的个体常元或变元组成的表达式。 带有 n(n≥0)个个体的谓词称为n 元谓词。
所有命题， 如“所有的人都要呼吸”、 “有些有理数是自然
数”等。 为了刻画这类表示全称判断或特称判断的命题， 需
要引入量词( quantifier )。
1.
x表示“对于所有的x”、 “对于任一x”或“对于每
一个x”，
(universal
quantifier)，x是量词 的作用变元(指导变元)。
第2章 谓词逻辑
北京大学计算机成教离散数学 逻辑学部分(板书)
第三部分逻辑学第六章命题逻辑第一节命题演算6-1-1 命题1.什麽叫命题其结果能判断真假，但不能既真又假的陈述句，称为命题。
作为判断使用的句子都是陈述句。
2.作为命题的陈述句，不能分成更简单的陈述句，这样的命题叫原子命题。
即简单命题。
3.什麽叫命题的真值作为命题的陈述句的判断结果，即正确（对应着真命题）或错误（对应着假命题）的两个值。
4.为了研究方便，我们把简单命题符号化。
每一个简单命题用一个小写英文字母表示。
而命题真值也要符号化。
用 1 表示命题的结果是真，即真命题；用 0 表示命题的结果是假，即假命题。
联结词与复合命题及其真值1.我们称用联结词联结在一起的简单命题为复合命题。
（1）否定联结词与命题否定式：“﹁”是否定联结词。
通过他可以构成命题否定式。
例如：用 p 表示“4是素数”。
p 的真值显然是假，即真值为 0；¬ p 表示假命题 p 的否定式，¬ p 的真值自然为真，即为 1。
（2）合取联结词与命题的合取式：“∧”是合取联结词。
通过他可以构成命题的合取式。
例如：p∧q，即 p 与 q 同时为真，复合命题的值才为真，即0 ∧ 0 = 0；0 ∧ 1 = 0；1 ∧ 0 = 0；1 ∧ 1 = 1。
所以，在p，q取不同真值的4种情况下，命题的合取式只有一个真值。
（3）析取联结词与命题析取式：“∨”是析取联结词。
通过他可以构成命题的析取式。
例如：p∨q，只要 p 、q 中至少一个真值为真，其值便为真，即0 ∨ 0 = 0；0 ∨ 1 = 1；1 ∨ 0 = 1；1 ∨ 1 = 1。
所以，在 4 种情况下，只有一个情况是假命题，即简单命题同时为假时命题析取式真值为 0。
（4）蕴涵联结词与命题蕴涵式：“如果... 则...”被称为蕴涵联结词，采用蕴涵符号“→”。
在这类句型中，q 是 p 的必要条件；p 是 q 的充分条件；蕴涵式 p→q 只有一个假值，即p为真，q 为假时蕴涵式命题的真值为 0。
清华离散数学(第2版)：13.1-2
7
解密算法正确性证明(续)
从而存在h使得 mk(n)=hq+1, 两边同乘以m, 并注意到m=cp, mk(n)+1=hcpq+m=hcn+m, 得证 mk(n)+1≡m(mod n), 即 mdw≡m(mod n).
8
模幂乘运算
模幂乘运算ab(mod n) 设b=b0+b1×2+…+br1×2r1, 其中bi=0或1, 于是
a a (a ) (a
b b0 2 b1
2r 1 br 1
)
(modn)
令 A0=a, Ai≡(Ai1)2(mod n), i=1, 2,…,r1, 则有
a A A A
b b0 0 b1 1
br 1 r 1
(modn)
9
实例
例1 p=43,q=59, n=43×59=2537,(n)=42×58=2436, w=13. A, B,…, Z依次用00, 01,…,25表示, 各占2位. 设明文段m=2106, 即VG, 密文c=210613mod 2537. 计算如下: 13=(1101)2, 即13=1+22+23. A0=2106≡431(mod 2537), A1≡(431)2≡560(mod 2537), A2≡5602≡988(mod 2537), A3≡(988)2≡601(mod 2537), 210613≡(431)×(988)×(601)≡2321(mod 2537), 得密文c=2321.
4
加密算法
线性同余加密算法 E(i)=(ai+b)mod 26, 其中a与26互素. i=0, 1,…,25,
维吉利亚(Vigenere)密码 把明文分成若干段, 每一段有n个数字, 密钥k=k1k2…kn, 加密算法 E(i1i2…in)=c1c2…cn, 其中cj=(ij+kj)mod 26, ij=0,1,…,25, j=1, 2,…, n.
解密算法正确性证明(续)
从而存在h使得 mk(n)=hq+1, 两边同乘以m, 并注意到m=cp, mk(n)+1=hcpq+m=hcn+m, 得证 mk(n)+1≡m(mod n), 即 mdw≡m(mod n).
8
模幂乘运算
模幂乘运算ab(mod n) 设b=b0+b1×2+…+br1×2r1, 其中bi=0或1, 于是
a a (a ) (a
b b0 2 b1
2r 1 br 1
)
(modn)
令 A0=a, Ai≡(Ai1)2(mod n), i=1, 2,…,r1, 则有
a A A A
b b0 0 b1 1
br 1 r 1
(modn)
9
实例
例1 p=43,q=59, n=43×59=2537,(n)=42×58=2436, w=13. A, B,…, Z依次用00, 01,…,25表示, 各占2位. 设明文段m=2106, 即VG, 密文c=210613mod 2537. 计算如下: 13=(1101)2, 即13=1+22+23. A0=2106≡431(mod 2537), A1≡(431)2≡560(mod 2537), A2≡5602≡988(mod 2537), A3≡(988)2≡601(mod 2537), 210613≡(431)×(988)×(601)≡2321(mod 2537), 得密文c=2321.
4
加密算法
线性同余加密算法 E(i)=(ai+b)mod 26, 其中a与26互素. i=0, 1,…,25,
维吉利亚(Vigenere)密码 把明文分成若干段, 每一段有n个数字, 密钥k=k1k2…kn, 加密算法 E(i1i2…in)=c1c2…cn, 其中cj=(ij+kj)mod 26, ij=0,1,…,25, j=1, 2,…, n.
清华离散数学(第2版)：14.3.1-2
13
群中的术语(续 群中的术语 续)
定义14.16 设G是群,x∈G,n∈Z,则 x 的 n 次幂 xn 定 是群, ∈ , ∈ , 定义 是群 义为
n=0 e xn = xn1 x n > 0 ( x1 )m m = n, n < 0
n∈Z
实例 在<Z3,⊕ >中有 23=(21)3=13=1⊕1⊕1=0 ⊕ 中有 ⊕ ⊕ 在 <Z,+> 中有 (2)3=23=2+2+2=6
8
实例
其中为矩阵乘法 为矩阵乘法, 设半群 V1=<S,>,独异点 V2=<S,,e>. 其中 为矩阵乘法, , e 为2阶单位矩阵 且 阶单位矩阵, 阶单位矩阵
a 0 | a, d ∈ R S = 0 d
a 0 a 0 f 0 d = 0 0
( x1 x 2 ... x n ) 1 = x n x n1 ... x 2 x1
1
1
1
1
等式(5)只对交换群成立 如果G是非交换群 是非交换群, 等式 只对交换群成立. 如果 是非交换群,那么 只对交换群成立
( xy ) = ( xy )( xy )...( xy )
n n个
17
群的性质---群方程存在唯一解 群的性质 群方程存在唯一解
3
实例
是半群, 是普通 例1 (1) <Z+,+>,<N,+>,<Z,+>,<Q,+>,<R,+>是半群,+是普通 是半群 加法, 其中除<Z 外都是独异点. 加法 其中除 +,+>外都是独异点 外都是独异点 (2) 设n是大于 的正整数 是大于1的正整数 是大于 的正整数,<Mn(R),+>和<Mn(R),>都是半群 和 都是半群 和独异点,其中+和 分别表示矩阵加法和矩阵乘法 分别表示矩阵加法和矩阵乘法. 和独异点,其中 和分别表示矩阵加法和矩阵乘法 (3) <P(B),⊕>为半群,也是独异点,其中⊕为集合的对称 为半群, ⊕ 为半群 也是独异点,其中⊕ 差运算. 差运算 (4) <Zn, ⊕>为半群,也是独异点,其中 n={0,1, … , n1}, 为半群, 为半群 也是独异点,其中Z , 为模n加法 加法. ⊕为模 加法 (5) <AA,>为半群,也是独异点,其中为函数的复合运算 为半群, 为半群 也是独异点,其中为函数的复合运算. (6) <R*,>为半群,其中 为非零实数集合,运算定义 为半群, 为非零实数集合, 为半群 其中R*为非零实数集合 如 下:x, y∈R*, xy = y. ∈ 4
《离散数学》命题逻辑
由原子命题组合而成的命题称为复合 命题（compound proposition）。
例如：
和 e 都是无理数。 6和8至少有一个是合数。 说刘老师讲课不好是不正确的。 不下雨我就去买书。
7
命题与命题联结词
将命题连接起来的方式叫做命题联结词
（ proposition connective ） 或 命 题 运 算 符
3
命题与命题联结词
逻辑
如何表示？ 如何“操作”？
非真即假的陈述句称为命题（proposition）。 一个命题如果是对的或正确的，则称为真命
题，其真值为“真”（true），常用T或1表示； 一个命题如果是错的或不正确的，则称为假
命题，其真值为“假”（false），常用F或0表示。
4
命题与命题联结词
32
命题公式及其分类
为简化公式的形式，作如下规定：
(1) 优先级 , (∧, ∨), (, ) (2) 公式 (~p) 的括号可以省略，写成 ~p (3) 整个公式最外层的括号可以省略
例1
(((p)∧q)(q∨p)) p∧q q∨p
例2
p∧q∨r 不是 命题公式 应写作 (p∧q)∨r 或 p∧(q∨r)
例 判断下列句子哪些是命题，哪些不是
这门课程题为“离散数学”。 这门“离散数学”讲得好吗？ X 这门“离散数学”讲得真好！ X 请学习“离散数学” 。 X 5是素数。 太阳从西方升起。 如果明天晴，而且我有空，我就去踢球。 天王星上没有生命。 x + 3 > 5。 X 5 本命题是假的。X
俞伯牙和钟子期是好朋友。 俞伯牙是好朋友 ∧ 钟子期是好朋友 俞伯牙 ∧ 钟子期是好朋友 Friend (俞伯牙,钟子期)
23
例如：
和 e 都是无理数。 6和8至少有一个是合数。 说刘老师讲课不好是不正确的。 不下雨我就去买书。
7
命题与命题联结词
将命题连接起来的方式叫做命题联结词
（ proposition connective ） 或 命 题 运 算 符
3
命题与命题联结词
逻辑
如何表示？ 如何“操作”？
非真即假的陈述句称为命题（proposition）。 一个命题如果是对的或正确的，则称为真命
题，其真值为“真”（true），常用T或1表示； 一个命题如果是错的或不正确的，则称为假
命题，其真值为“假”（false），常用F或0表示。
4
命题与命题联结词
32
命题公式及其分类
为简化公式的形式，作如下规定：
(1) 优先级 , (∧, ∨), (, ) (2) 公式 (~p) 的括号可以省略，写成 ~p (3) 整个公式最外层的括号可以省略
例1
(((p)∧q)(q∨p)) p∧q q∨p
例2
p∧q∨r 不是 命题公式 应写作 (p∧q)∨r 或 p∧(q∨r)
例 判断下列句子哪些是命题，哪些不是
这门课程题为“离散数学”。 这门“离散数学”讲得好吗？ X 这门“离散数学”讲得真好！ X 请学习“离散数学” 。 X 5是素数。 太阳从西方升起。 如果明天晴，而且我有空，我就去踢球。 天王星上没有生命。 x + 3 > 5。 X 5 本命题是假的。X
俞伯牙和钟子期是好朋友。 俞伯牙是好朋友 ∧ 钟子期是好朋友 俞伯牙 ∧ 钟子期是好朋友 Friend (俞伯牙,钟子期)
23
北大离散数学02
2013-1-2
《集合论与图论》第2讲
15
命题符号化(举例、续)
例:
“有些病人相信所有的医生”。 解: 设: F(x): x是病人; G(x): x是医生; H(x,y): x相信y 原命题符号化成: x(F(x)y(G(y)H(x,y)))
2013-1-2
《集合论与图论》第2讲
16
命题符号化(举例、续)
2013-1-2 《集合论与图论》第2讲 10
命题符号化(举例、续)
例:
“凡人都是要死的”. 解1: 采用全总个体域. 设: F(x): x是人; G(x):x是要死的. 原命题符号化成: x(F(x)G(x)) 解2: 采用全体人作为个体域. 设: G(x): x是要死的. 原命题符号化成: xG(x)
2013-1-2
《集合论与图论》第2讲
14
命题符号化(举例、续)
例:
“有的汽车比火车快”。 解: 设: F(x): x是汽车; G(x): x是火车; H(x,y): x比y快 原命题符号化成: x(F(x)y(G(y)H(x,y))) 或: xy(F(x)G(y)H(x,y))
例:
“存在唯一的对象满足性质P”。 解: 设: P(x): x满足性质P 原命题符号化成: !xP(x) 或: x( P(x) y( P(y)x=y ) )
2013-1-2
《集合论与图论》第2讲
17
合式公式中的变项
在xA, xA中, A是量词的辖 域. 例如: x(F(x)y(G(y)H(x,y))) 指导变项: 紧跟在量词后面的个体变项. 例如: x(F(x)y(G(y)H(x,y))) 约束出现: 在辖域中与指导变项同名的变 项. 例如: x(F(x)y(G(y)H(x,y))) 自由出现: 既非指导变项又非约束出现. 例如: y(G(y)H(x,y))
离散数学(第2版)电子教案
第二类是复合命题，它由原子命题、命题联结词和圆括号组成。什么是命题联结词？下面就来定义五个常用命题联结词。
3.命题联结词
定义1.1.1设P表示一个命题，由命题联结词和命题P连接成P，称P为P的否定式复合命题，P读“非P”。称为否定联结词。P是真当且仅当P为假；否定联结词“”的定义可由表1.1.1表示之。
1.1
1.命题的概念
所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值：真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。
例1.1.1判断下列语句哪些是命题
第
命题逻辑，也称命题演算，记为LS。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑，又名为符号逻辑，它是选用数学方法即通过引入没有二义性的表意符号，使用公认的与任一特定的论证无关的规则研究推理的学问。
命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。那么，什么是命题？如何表示和构成？如何进行推理的？下面逐一地进行讨论。
3.一方面每章各有独立性，教师根据需要可以单独选讲几章；另一方面，尽可能注意各章之间的联系，规范并统一了符号和术语。
本书在编写过程中，得到了有关领导、老师和同学的热情关心、支持和帮助，在此一并表示感谢。
限于作者水平，书中难免有不当和疏漏之处，恳请读者批评指正。
编者
于大连理工大学
2008年9月
由于离散数学上课学时普遍减少，电子教案只包含了数理逻辑、集合论、代数结构和图论的基本理论部分。使用它的各位老师，可以根据教学计划的需求，适当做删减或增补。
3.命题联结词
定义1.1.1设P表示一个命题，由命题联结词和命题P连接成P，称P为P的否定式复合命题，P读“非P”。称为否定联结词。P是真当且仅当P为假；否定联结词“”的定义可由表1.1.1表示之。
1.1
1.命题的概念
所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值：真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。
例1.1.1判断下列语句哪些是命题
第
命题逻辑，也称命题演算，记为LS。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑，又名为符号逻辑，它是选用数学方法即通过引入没有二义性的表意符号，使用公认的与任一特定的论证无关的规则研究推理的学问。
命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。那么，什么是命题？如何表示和构成？如何进行推理的？下面逐一地进行讨论。
3.一方面每章各有独立性，教师根据需要可以单独选讲几章；另一方面，尽可能注意各章之间的联系，规范并统一了符号和术语。
本书在编写过程中，得到了有关领导、老师和同学的热情关心、支持和帮助，在此一并表示感谢。
限于作者水平，书中难免有不当和疏漏之处，恳请读者批评指正。
编者
于大连理工大学
2008年9月
由于离散数学上课学时普遍减少，电子教案只包含了数理逻辑、集合论、代数结构和图论的基本理论部分。使用它的各位老师，可以根据教学计划的需求，适当做删减或增补。
最新离散数学 第2版 教学课件 尤枫 第07章 半群与群ppt课件
与
到W的半群同态。
群
证明 对于任意的a,b∈R，有
(g·f)(a*b) = g(f(a*b))
= g(f(a)f(b))
= g(f(a))g(f(b))
= (g·f)(a)(g·f)(b)
所以，g·f是从U到W的半群同态。
7.1半群与独异点
第 定理7-7 设U=<R,*>和V=<S,+>都是半群，则U和
因此，U是一个群。
7.2 群与子群
第 定义7-11 设U=<S,*>是一个群。若
7 章
(1) S为有限集合，则称U为有限群，
半
若|S|=n，则称U为n阶群；
群 与
(2) S为无限集合，则称U为无限群。
群
7.2 群与子群
第 定理7-9 群中不存在零元。
7 章
证明 设U=<S,*>是任意一个群，当群的阶为1时，
半
集合S中唯一的一个元素看作是群的幺元。
群 与
设|S|>1，且存在零元。因零元不存在逆元，
群 而群中每个元素都必须是可逆的，于是产生矛盾，
所以，群中不存在零元。
7.2 群与子群
第 定理7-10 幺元是群中唯一的一个幂等元。
7 章
证明 对于幺元e，因e2=e，故e是幂等元。
半
若a也是幂等元，即若a*a=a，则
群 与
e = a-1*a
群
= a-1*(a*a)
= (a-1*a)*a
= e*a
=a
这说明e是唯一的幂等元，证毕。
7.2 群与子群
第 定理7-11 设U=<S,*>是一个群，则对于任意的
7 章
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
命题逻辑等值演算2学习目的本章主要涉及命题演算中两个重要内容之一：等值演算。
首先理解命题公式等值的含义，掌握构造真值表和不构造真值表两种方法证明等值式，熟练应用于命题公式的化简和范式表示基本内容z命题公式等值关系及其证明z联结词的全功能集z命题公式的范式表示等值关系基本概念等值的两种定义：z如果两个逻辑形式对其中的命题变项的任何取值，都具有相同的值，则称它们是相等的。
z A、B等值是指等价式A↔B为重言式，记为A⇔B。
可直接构造真值表证明两个命题形式的等值。
等值演算根据已知的等值式，可以推演出另外许多的等值式，这种推演过程称为等值演算。
这些已知等值式通常是经过证明了的常用等值式，其中许多是布尔代数或逻辑代数的主要组成部分，称为等值关系模式：(1) 双重否定律： A ⇔¬¬A(2) 等幂律：(2a) A ⇔ A∧A(2b) A ⇔ A∨A(3) 交换律：(3a) A∧B ⇔ B∧A(3b) A∨B ⇔ B∨A(3c) A∨B ⇔ B∨A(3d) A↔B ⇔ B↔A(4) 结合律：(4a) (A∧B)∧C ⇔ A∧(B∧C)(4b) (A∨B)∨C ⇔ A∨(B∨C)(4c) (A∨B) ∨C ⇔ A∨ (B∨C)(4d) (A↔B) ↔C ⇔ A↔ (B↔C)(5) 分配律：(5a) A∨(B∧C) ⇔ (A∨B)∧(A∨C)(5b) A∧(B∨C) ⇔ (A∧B)∨(A∧C)(5c) A∧(B∨C) ⇔ (A∧B) ∨ (A∧C)(6) 德•摩根律：(6a) ¬(A∧B) ⇔¬B∨¬A(6b) ¬(A∨B)⇔¬B∧¬A(7) 吸收律：(7a) A∨(A∧B)⇔A(7b) A∧(A∨B)⇔A(7c) A∨(¬A∧B)⇔A∨B(7d) A∧(¬A∨B)⇔A∧B(7e) (A∧B) ∨ (¬A∧C) ∨ (B∧C) ⇔ (A∧B) ∨ (¬A∧C) (8) 零律：(8a) A∨1 ⇔ 1(8b) A∧0 ⇔ 0(9) 同一律：(9a) A∨0 ⇔ A(9b) A∨0 ⇔ A(10)排中律：A∨¬A ⇔ 1(11)矛盾式：A∧¬A ⇔ 0(12)蕴涵等值式：A→B ⇔¬A∨B(13)等价等值式：(13a) A↔B ⇔ (A→B) ∧ (B→A)(13b) A↔B ⇔¬ (A∨B)(14)假言易位：A→B ⇔¬B→¬A(15)等价否定等值式：A↔B ⇔¬A↔¬B(16)否定等价等值式：¬ (A↔B) ⇔¬A↔B ⇔ A↔¬B(17)归谬律：(A→B) ∧ (A→¬B) ⇔¬A(18)输出律：(A∧B) → C ⇔ A → (B → C)(19) A ∨¬A ⇔ 0(20) A ∨ B ⇔ (A ∧¬B) ∨ (¬A ∧ B)通常在等值演算的过程中，还可以用到一些规则或定理：z置换规则设Φ是含有公式A的命题形式，Ψ是用公式B置换Φ中的公式A(不一定是每一处)而得到的命题形式，如果A ⇔ B，则Φ⇔Ψ。
z香农(Shannon)定理：, p2,…, p n和命题常项命题形式A仅含有命题变项p10,1及联结词¬，∧，∨，表示成A(p1, p2,…, p n,0,1,∧,∨)，则A的非可以通过对所有命题变项取非，并将常量1换成0，0换成1，联结词∧换成∨，∨换成∧而得到：¬A(p1, p2,…, p n,0,1,∧,∨)⇔A(¬p1, ¬p2,…,¬p n,1,0,∨, ∧)z对偶定理：对偶式：公式A仅含有联结词¬，∧，∨，则将A中的∧，∨，0，1分别换以∨，∧，1，0后得到的公式为A的对偶式A*。
即：A*(p1, p2,…, p n,0,1,∧,∨) = A(p1, p2,…, p n,0,1, ∧,∨)香农定理的对偶式表示：¬A(p1, p2,…, p n) ⇔ A*(¬p1, ¬p2,…, ¬p n)对偶定理：如果A ⇔ B，且A,B仅含有联结词¬，∧，∨，则A*⇔ B*。
注意两个定理的A、B、F仅含有联结词¬，∧，∨。
z展开定理, p2, …, p n，则设命题形式A含有命题变项p1A(p1,p2,…,p i,…,p n) ⇔(p i∧B(p1,p2,…,1,…,p n))∨(¬p i∧B(p1,p2,…,0,…,p n))；(1)A(p1,p2,…,p i,…,p n)⇔(p i∨B(p1,p2,…,0,…,p n))∧(¬p i∨B(p1,p2,…,1,…,p n))。
(2)逻辑等值演算不仅仅停留在符号级，总要用来解决实际问题，如简化语句，确定一些命题的真值等等，可以首先符号化命题，然后由已知条件列出这些命题应该满足的方程组，从而达到要求。
化简语句：“情况并非如此：如果他不来，那么我也不去”设p:他来，q：我去；上述语句符号化为¬ (¬p→¬q) 等值化简为¬p∧q化简后语句为：“我去了，而他每来”。
小李或小张是先进工作者；如果小李是先进工作者，你是会知道的；如果小张是先进工作者，小赵也是；你不知道小李是先进工作者。
问：谁是先进工作者？设p：小李是先进工作者；。
q：小张是先进工作者；r：你知道小李是先进工作者；s：小赵是先进工作者。
则上述语句符号化为(p∨q) ∧ (p→r) ∧ (q→s) ∧¬r⇔ 1等值化简为¬p∧q∧s∧¬r ⇔ 1显然p=0, q=1, s=1, r=0满足此等值式，即小张和小赵是先进工作者。
联结词的全功能集从等值式模式可以发现，常用的六种联结词不是相互独立的，其中有些联结词的逻辑功能可以用其它联结词代替，如:A→B⇔¬A∨B，A↔B⇔ (A→B) ∧ (B→A) ⇔ (¬A∨B) ∧ (¬B∨A)，A∨B⇔ (A∧¬B) ∨ (¬A∧B)。
将联结词组成一个集合，如果一个联结词可由集合中的其它联结词定义，则称此联结词为冗余联结词，否则称为独立连接词。
一个联结词集合称作是全功能集是指任意真值函数都可以用仅含有此集合中联结词的命题形式表示。
如果一个全功能联结词集合中不含有冗余联结词，则称其为极小全功能集。
z{¬, ∧, ∨}是全功能集。
z如果一个全功能集S1中的所有联结词都可由一个联结词集合S2定义，则S2也是全功能集。
要证明一个联结词集合是全功能集比较简单，只要写出各联结词的适当等值式即可。
要证明一个联结词集合是极小全功能集，要证明它是全功能集，还要证明其中的每个联结词都不能由其它联结词定义。
证明一个联结词集合是极小全功能集比证明其不是极小全功能集困难得多。
可以证明{¬, ∧}、{¬, →}是极小全功能集。
“命题p与q的否定”称作p, q的与非式，记作p↑q，符号↑称为与非联结词。
p↑q ⇔¬(p∧q)，从而p↑q 为真当且仅当p, q不同时为真。
“命题p或q的否定”称作p, q的或非式，记作p↓q，符号↓称作或非联结词。
p↓q ⇔¬(p∨q)，从而p↓q 为真当且仅当p, q同时为假。
z{↑}, {↓}都是极小全功能集。
{↑}, {↓}都是极小全功能集，这不仅在理论上而且在实践上都有着重要的意义。
例如，在数字逻辑电路设计中，只要选择一个基本的单元电路——与非门或或非门就可以设计出满足任何要求的逻辑电路。
逻辑电路中用得较多的就是与非门。
范式我们知道，任何一个n元真值函数，其具体的逻辑命题形式是无穷多的，而这些命题形式实质上却是等值的。
这里介绍一种方法，将公式都等值演算成某种标准形式，从而可以通过这些标准形式进行比较。
简单合取式和简单析取式命题变项及其否定统称为文字(literal)。
p, ¬p, q等都是文字，但¬¬p不是文字仅由有限个文字构成的合取式，称为简单合取式；仅由有限个文字构成的析取式，称为简单析取式。
p∧q, p∧q∧¬p, p∧q∧r∧s等都是简单合取式，p∨q, p∨¬q∨r, p∨p∨r等都是简单析取式。
单个文字既可看作是简单合取式，也可看作是简单合取式。
z一个简单合取式是矛盾式，当且仅当其含有一个文字及其否定。
z一个简单合取式是重言式，当且仅当其含有一个文字及其否定。
析取范式和合取范式仅由有限个简单析取式的合取构成的命题形式，称为合取范式；仅由有限个简单合取式的析取构成的命题形式，称为析取范式。
z一个析取范式是矛盾式，当且仅当它的每个简单合取式都是矛盾式。
z一个合取范式是重言式，当且仅当它的每个简单析取式都是重言式。
任何一个命题形式都可以等值演算成合取范式和析取范式，具体步骤如下：z任何命题形式化为由¬, ∧, ∨定义的形式。
z简化双重否定号，并利用香农定理将所有¬写到文字里；z利用分配律，将A最终变成合取范式和析取范式。
通过等值演算将 ((p∨q)→r)→p化成合取范式和析取范式。
((p∨q)→r) →p⇔¬(¬(p∨q)∨r) ∨p⇔ (p∧¬r) ∨ (q∧¬r ) ∨p(析取范式)⇔p ∨ (q∧¬r)(析取范式)⇔ (p∨q) ∧ (p∨¬r)。
(合取范式)一个命题形式的析取范式不是唯一的，同样，合取范式也不是唯一的。
不能将析取范式和合取范式作为标准形式。
主析取范式和主合取范式在含有n个命题变项的简单合取式中，每个命题变项作为文字出现且仅出现一次，则称此简单合取式为n个命题变项的极小项(minterm)。
在极小项中，不允许一个文字及其否定式同时出现，也不允许一个文字出现多次。
n个命题变项共可构成2n个不同的极小项。
极小项的主要性质：z每个极小项的成真赋值有且仅有一个；z两个不同的极小项的合取构成的命题形式为矛盾式；z所有极小项的析取构成的命题形式为重言式。
表示第i个极小项，其中为了书写方便，通常用mi下标i的规定如下：将极小项的命题变项按照一定次序排列，下标i化为二进制后恰好等于该极小项的成真赋值。
这样，每个m与其成真赋值之间就建i立了一一对应的关系。
极小项可以用卡诺图表示：卡诺图的构成遵循以下规律：(1) 含有n 个命题变项，若n 是偶数，则斜线左右命题变项数目相同；若n 是奇数，斜线左边命题变项的数目多一个；按照排列顺序，依次从外到里，从斜线左边到右边；(2) 命题变项的赋值，位于最外层的总是从上往下、从左到右依次为0, 1；位于里层的，则按照其相邻外层的相邻两个赋值0, 1，从上往下、从左到右依次扩展为0, 1, 1, 0。