离散数学第13讲

注意：可能有多个同构映射，如f(x)=lg x也是。
同构关系是等价关系
自反：对任意群(G,), G≅G ≅ – 恒等映射 f(x)=x 是同构映射 对称：对任意群G1, G2, 若G1≅ 2, 则G2≅ 1 ≅G ≅G – 设从G1到G2的同构映射为f, 则从G2到G1的同构映 射是f -1 传递：对任意群G1, G2, G3, 若G1≅G2, 且G2≅G3，则 G1≅G3, – 设从G1到G2的同构映射为f, 从G2到G3的同构映射 为g, 则设从G1到G3的同构映射fg,
有单位元e即对任意xg的每个元素均有逆元素即对任意xg存在x1的单位元素由逆元素的唯一性可知
群的同构与同态
离散数学 第13讲
上一讲内容的回顾
子群的定义及其判定 有限群的子群的判定 陪集与集合的划分 陪集关系
–
陪集关系是等价关系
拉格朗日定理 拉格朗日定理的重要推论
群的同构与同态
同构与同构映射 同态与同态映射 满同态 同构、同态与系统性质的保持
满同态与运算性质的保持（ ） 满同态与运算性质的保持（1）
结合律
–
假设f: G1→G2是满同态映射，若G1满足结合律，即对任意 x,y,z∈G1,(xy)z=x(yz) 则：对任意x’,y’,z’∈G2, 因为f 是满射，必有x,y,z∈G1,使得f(x)=x’, f(y)=y’, f(z)=z’, 因此：(x’*y’)*z’ = (f(x)* f(y))* f(z) = f(xy) * f(z) = f((xy)z) = f(x(y z)) = f(x)* (f(y)* f(z)) = x’*(y’*z’)
若群G1与G2满同态，证明：
–
–
群(G1,)与(G2,*)同构 (G1≅G2) 当且仅当： ≅

其中P(x)为任何谓词公式。 如：A={x|x∈R ∧ x2+1=0}。 该方程无实数解。 注意： φ ≠{φ } 由定义可知，对任何集合A，有A。这是因为任意元素x，公式xxA总是 为真。
第23页/共193页
注意： 与{}是不同的。 {}是以为元素的集合， 而没有任何元素，能 用构成集合的无限序列： ，{}，{{}}，···
例 设A={{1,2,3}, 1,2,3}， 则 {1,2,3} A 且 {1,2,3} A 。
第27页/共193页
重要结论
➢对任意集合A, 有A A。 ➢空集是任意集合的子集，且空集是唯一的。 ➢对于任意两个集合A、B，A=B的充 要条件是AB且BA。（这个结论非常简单， 但它非常重要，很多证明都是用这个Fra bibliotek法或思路来证明。）
第2页/共193页
集合的基本概念
例:
1. 二十六个英文字母可以看成是一个集合；
2. 所有的自然数看成是一个集合； 3. 重庆邮电大学计算机学院2010级的本科学生可以看成是一个集合； 4. 这间教室中的所有座位可以看成是一个集合。
第3页/共193页
集合的元素
组成一个集合的那些对象或单元称为这 个集合的元素。通常，用小写的英文字母a, b, c,…表示集合中的元素。元素可以是单 个的数字也可以是字母，还可以是集合。
下列选项正确的是（ 3 ）；
（1） 1A
（2）{1,2,3} A
（3）{{4,5}} A （4） ØA
例3.4 下列各选项错误的是（2）；
（1） Ø Ø
（2） Ø Ø
（3） Ø { Ø }
（4） Ø { Ø }
例3.5 在0 ___ Ø 之间填上正确的符号：（4）

(3)至于p为0即“我期终考了年级不是前 10”时,无论q为1或为0，即无论"我老妈 奖励1000元"或不奖励，都不能说老妈的 话是假的，故善意的认为pq为1均为1
1.1 命题及联结词
定义1.5双条件:当p与q值相同时,pq为1,不同 为0。 称p当且仅当q
“普通老师赚了100万当且仅当他 中了100万的彩票”， 普通老师赚了100万 普通老师买彩票中了100万大奖
故pq为0
1.1 命题及联结词
定义1.4条件式当p是1 ,q是0时,pq为0,即 10为0,其他情况为1。 p称为前件,q称为后件
(1)当p为1即“我期终考了年级前10”
q为0即“我老妈没有奖励1000元” 这时老妈的话为假，即pq为0 (2)当p为1即“我期终考了年级前10” q为1即“我老妈奖励1000元” 这时妈妈的话就对了，即pq为1
由于所有内容(整数，实数，字符，汉字，图片，声 音，视频，网页，……)进入电脑后，全是01组成的字 符串，从而都可以用布尔运算即逻辑运算实现，命题逻 辑成为计算机的基础。
命题逻辑将数学由连续变到离散，由高数进入离散。
Google采用逻辑运算进行搜索：数字之美 吴军 杨圣洪 000100010001110000 两者对应位置与运算。 离散数学 100100000000100001
陈述句(6)的正确性，到2018年12月时能确定的，若届 时建成了则它是对的、为真命题，否为假命题。
1.1 命题及联结词
对错确定的陈述语句称为命题。如：
(7) x与y之和为100，其中x为整数，y为整数 (8)1加1等于10 (7)的对错不确定。当x为50、y为50时是对的，当x为 51、y为52时是错的。 (8)的对错是不确定的，为二进制时正确，当为八进制、 十进制时是错的，因此这两个陈述句不是命题。 (9)青枫峡的红叶真美呀！ (10)动作快点！ (11)你是杨老师吗？ 这三个语句不是陈述语句，因此不是命题。

A＝B C或A＝B C或A＝B C，则公式A是n＋1层公式， n max( i, j)。
例（1）p q r (2)r q p q p
第23页/共292页
1.2 命题公式及其赋值
( p q) r
p：2是素数，q：3是偶数，r：2是有理数 p：2是素数，q：3是偶数，r：2是无理数
例2.等值等价式p q p q q p
等值演算的应用： 1.验证等值式 ( p q) ( p r) p (q r) 2.判定公式的类型 ( p q) p q,( p ( p q)) r, p ((( p q) p) q) 3.解决工作生活中的判断问题
甲、已、丙3人根据口音对王教授是哪人进行了判断： 甲说：王教授不是苏州人，是上海人 已说：王教授不是上海人，是苏州人 丙说：王教授既不是上海人，也不是杭州人
例：1.如果3＋3＝6，那么雪是白的。 2.除非我能工作完成了，我才去看电影。 3.只要天下雨，我就回家。 4.我回家仅当天下雨。 p→q的逻辑关系为q是p的必要条件或p是q的充分条件。
第15页/共292页
1.1 命题和命题联结词
5).等价词 由命题p、q和 组成的复合命题记作p q,读作“p当且仅当q”。 是自然语言中的“充要条件”，“当且仅当”的逻辑抽象。
1.3 命题公式的等值式
定义1.设A和B是两个命题公式，若A B为重言式， 则称公式A, B是等值的公式，记作A B。
例1.证明（p q) (q p); p p p.
注意： 和 的区别 是公式间的关系符号，如：p q 是命题联结词.p q
第28页/共292页
1.3 命题公式的等值式
1.1 命题和命题联结词
例：1）海洋的面积比陆地的面积大。 例 q2:）： 22p6:6海 9洋 9。 。的面积比陆地的面积大。 r3:）火火星星上上有有生生命命。。 s4:）三三角角形形的的内内角角和和等等于 于118800。 。 55））你你喜 喜欢 欢数学吗吗？？ 66））我我们 们要 要努 努力力学学习习。。 77））啊啊， ，我 我的 的天天哪哪！！ 88））我我正 正在 在说 说谎 谎。。