离散数学4
- 格式：docx
- 大小：113.77 KB
- 文档页数：30
下载文档原格式
合集下载
离散数学4联结词(条件)
联结词----条件复合命题是用“联结词”将原子命题联结起来构成的.归纳自然语言中的联结词，定义了六个逻辑联结词：(1)否定“⌝”(2)合取“∧”(3) 析取“∨”和异或“”∨(4) 条件（蕴涵）“→”(5)双条件（等价）“∆”或记做“↔”四.条件 (蕴涵)“→”表示“如果… 则… ”“只要… 就…”,“若…则…”等.例： P表示：缺少水分.Q表示：植物会死亡.P→Q：如果缺少水分，植物就会死亡.P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”.也说成P是P→Q 的前件，Q是P→Q的后件.还可以说P是Q的充分条件，Q是P的必要条件.P→Q的真值：P→Q的真值为假，当且仅当P为真，Q为假. 注意：当前件P为假时， P→Q为T.关于充分条件和必要条件的说明：•充分条件：就是只要条件成立，结论就成立，则该条件就是充分条件.上例中，“缺少水分”就是“植物会死亡”的充分条件.在自然语言中表示充分条件的词有：如果…则… ，只要… 就…，若…则… .•必要条件：就是如果该条件不成立，那么结论就不成立, 则该条件就是必要条件.上例中，“植物死亡”就是“缺少水分”的必要条件(植物未死亡，一定不缺少水分).在自然语言中表示必要条件的词有 :只有…才… ；仅当…，… ; …, 仅当….例1令：P：天气好. Q：我去公园.1).如果天气好，我就去公园. 2).只要天气好，我就去公园.3).天气好，我就去公园. 4).仅当天气好，我才去公园.5).只有天气好，我才去公园. 6).我去公园，仅当天气好.命题1)、2)、3)写成： P→Q .命题4)、5)、6)写成： Q→P.可见“→”既表示充分条件（即前件是后件的充分条件）；也表示必要条件（即后件是前件的必要条件）.这一点要特别注意!!!它决定了哪个作为前件，哪个作为后件.例2. 将下列命题符号化:（1）如果小明学日语，小华学英语，则小芳学德语.P：小明学日语；Q：小华学英语；R：小芳学德语.则原命题可表示为：(P∧Q)→R.（2）只要不下雨，我就骑自行车上班.P：天下雨.Q：我骑自行车上班.则原命题可表示为：⌝P→Q.（3）只有不下雨，我才骑自行车上班.P：天下雨.Q：我骑自行车上班.则原命题可表示为： Q →⌝P .7。
屈婉玲离散数学第四章
2
谓词
谓词——表示个体词性质或相互之间关系的词 谓词常项 如, F(a)：a是人 谓词变项 如, F(x)：x具有性质F n（n1）元谓词 一元谓词(n=1)——表示性质 多元谓词(n2)——表示事物之间的关系 如, L(x,y)：x与 y 有关系 L，L(x,y)：xy，… 0元谓词——不含个体变项的谓词, 即命题常项 或命题变项
9
实例5
例5 设个体域为实数域, 将下面命题符号化 (1) 对每一个数x都存在一个数y使得x<y (2) 存在一个数x使得对每一个数y都有x<y 解 L(x,y):x<y (1) xyL(x,y) (2) xyL(x,y)
注意: 与不能随意交换 显然(1)是真命题, (2)是假命题
10
4.2 一阶逻辑公式及解释
14
封闭的公式
定义4.6 若公式A中不含自由出现的个体变项，则称A为封闭 的公式，简称闭式. 例如，xy(F(x)G(y)H(x,y)) 为闭式， 而 x(F(x)G(x,y)) 不是闭式
15
公式的解释
定义4.7 设L 是L生成的一阶语言, L 的解释I由4部分组成： (a) 非空个体域 DI . (b) 对每一个个体常项符号aL, 有一个 aDI, 称 a 为a在I 中的解释. (c) 对每一个n元函数符号fL, 有一个DI上的n元函数 f : DIn DI , 称 f 为f在I中的解释. (d) 对每一个n元谓词符号FL, 有一个DI上的n元谓词常项F , 称 F 为F在I中的解释. 设公式A, 取个体域DI , 把A中的个体常项符号a、函数符 号f、谓词符号F分别替换成它们在I中的解释 a、 f 、F , 称 所得到的公式A为A在I下的解释, 或A在I下被解释成A.
20
谓词
谓词——表示个体词性质或相互之间关系的词 谓词常项 如, F(a)：a是人 谓词变项 如, F(x)：x具有性质F n（n1）元谓词 一元谓词(n=1)——表示性质 多元谓词(n2)——表示事物之间的关系 如, L(x,y)：x与 y 有关系 L，L(x,y)：xy，… 0元谓词——不含个体变项的谓词, 即命题常项 或命题变项
9
实例5
例5 设个体域为实数域, 将下面命题符号化 (1) 对每一个数x都存在一个数y使得x<y (2) 存在一个数x使得对每一个数y都有x<y 解 L(x,y):x<y (1) xyL(x,y) (2) xyL(x,y)
注意: 与不能随意交换 显然(1)是真命题, (2)是假命题
10
4.2 一阶逻辑公式及解释
14
封闭的公式
定义4.6 若公式A中不含自由出现的个体变项，则称A为封闭 的公式，简称闭式. 例如，xy(F(x)G(y)H(x,y)) 为闭式， 而 x(F(x)G(x,y)) 不是闭式
15
公式的解释
定义4.7 设L 是L生成的一阶语言, L 的解释I由4部分组成： (a) 非空个体域 DI . (b) 对每一个个体常项符号aL, 有一个 aDI, 称 a 为a在I 中的解释. (c) 对每一个n元函数符号fL, 有一个DI上的n元函数 f : DIn DI , 称 f 为f在I中的解释. (d) 对每一个n元谓词符号FL, 有一个DI上的n元谓词常项F , 称 F 为F在I中的解释. 设公式A, 取个体域DI , 把A中的个体常项符号a、函数符 号f、谓词符号F分别替换成它们在I中的解释 a、 f 、F , 称 所得到的公式A为A在I下的解释, 或A在I下被解释成A.
20
自考离散数学第4章
例：设集合A={a,b,c,d},在A上定义两个运算*和
，如表所示： 解：b,d是A中关于*运算的左幺元，而a是A中关于运算的右幺元。
a d a a a b a b b b c b c c c d c d c d a b c
* a b c d
a a b c
b b a d
c d c a
定义4.3.7 设<G,*>为群，若在G中存在一个元素a，使得G中的任意元素都由a
例：设A={a,b,c,d}，*为A上的二元运算，
* a b c d
a a b c d
b b d a a
c c a b c
d d c b d
可以看出a为单位元。由a*a=a,b*c=a,c*b=a,d*b=a, 故a有逆元a；b有左逆元c，d；c有左逆元b；b有右逆元c；c有右逆元b；d有
定义4.3.2 设<G,*> 为一个群，如果G是有限集合，则称<G,*> 是有限群。G中
元素的个数通常称为有限群的阶数，记为|G|。
定义4.3.3 若群G中，只含有一个元素，即G={e},|G|=1,则称G为平凡群。 例：设G={e,a,b,c},运算*如表所示：
* e a b c
e e a b c
4.2 半群与独异点
4.3 群与子群
定义4.3.1 设<G,*>为一个代数系统，其中G是非空集合，*是G上一个二元运算，
① 如果*是封闭的； ② 运算*是可结合的； ③ 存在幺元e； ④ 对于每一个元素x G，存在它的逆元x-1； 则称<G,*>是一个群。
4.3 群与子群
4.3 群与子群
4.1 代数系统
离散数学第四章(第1讲)
xy??a??bc?xy??xyx??a??y??bc?xy??xyx??a??y??b??y??c?xy??xyx??a??y??b??x??a??y??c?xy??a??ba??c即a??bca??ba??c例
第四章 二元关系
§1 序偶与笛卡尔积 §2 关系及其表示 §3 关系的性质 §4 关系的运算 §5 等价关系与划分 §6 相容关系与覆盖 §7 偏序关系
§1 序偶与笛卡尔乘积
1 序偶 《定义》由二个具有给定次序的客体所组成的序列
称为序偶。记作〈x，y〉 例：X—Y二维平面上的一个点的坐标〈x，y〉就
是一个序偶。
说明： (1)在序偶中二个元素要有确定的排列次序。 若ab时，则〈a，b〉〈b，a〉 若〈x，y〉=〈a，b〉（x=a y=b） (2) 多重序元： 三元组：〈〈x，y〉，z〉 =〈x，y，z〉 n元组： 〈〈〈〈x1，x2〉，x3〉…〉，xn〉= 〈x1,…,xn〉
ran R={a,b,c,d}
FLD R={1,2,3,4,a,b,c,d}
４．关系和笛卡尔乘积 笛卡尔乘积的任何子集都可以定义一种二元关系。 例：X={1,2,3,4}，Y={1,2}
X Y {1,1 ,1,2 , 2,1 , 2,2 , 3,1 , 3,2 , 4,1 , 4,2 }
S1={<x,y>|x X yYx ≤ y}={<1,1><1,2><2,2>}
2 笛卡尔乘积 《定义》设A，B为二个任意集合，若序偶的第 一个成员（左元素）是A的一个元素，序偶的 第二个成员（右元素）是B的一个元素，则所 有这样的序偶构成的集合称为A和B的笛卡尔乘 积。
记作：A B={〈x，y〉|（xA）（yB）}
第四章 二元关系
§1 序偶与笛卡尔积 §2 关系及其表示 §3 关系的性质 §4 关系的运算 §5 等价关系与划分 §6 相容关系与覆盖 §7 偏序关系
§1 序偶与笛卡尔乘积
1 序偶 《定义》由二个具有给定次序的客体所组成的序列
称为序偶。记作〈x，y〉 例：X—Y二维平面上的一个点的坐标〈x，y〉就
是一个序偶。
说明： (1)在序偶中二个元素要有确定的排列次序。 若ab时，则〈a，b〉〈b，a〉 若〈x，y〉=〈a，b〉（x=a y=b） (2) 多重序元： 三元组：〈〈x，y〉，z〉 =〈x，y，z〉 n元组： 〈〈〈〈x1，x2〉，x3〉…〉，xn〉= 〈x1,…,xn〉
ran R={a,b,c,d}
FLD R={1,2,3,4,a,b,c,d}
４．关系和笛卡尔乘积 笛卡尔乘积的任何子集都可以定义一种二元关系。 例：X={1,2,3,4}，Y={1,2}
X Y {1,1 ,1,2 , 2,1 , 2,2 , 3,1 , 3,2 , 4,1 , 4,2 }
S1={<x,y>|x X yYx ≤ y}={<1,1><1,2><2,2>}
2 笛卡尔乘积 《定义》设A，B为二个任意集合，若序偶的第 一个成员（左元素）是A的一个元素，序偶的 第二个成员（右元素）是B的一个元素，则所 有这样的序偶构成的集合称为A和B的笛卡尔乘 积。
记作：A B={〈x，y〉|（xA）（yB）}
离散数学 第四章 关系
若ai Rbj 若ai Rbj
矩阵MR 称为R的关系矩阵。
17
第四章 关系
4.1 二元关系
例：设A={1，2，3，4}，A上的关系R={<x,y>|y是x 的整数倍}，故R={<1,1>,<1,2>,<1,3>,<1,4>,<2,2>,<2, 4>,<3,3>,<4,4>}.
1 2 3 4
1 1 2 0 MR 3 0 4 0
2
第四章 关系
4.1 二元关系
4.1.1 基本概念
4.1.2 关系的表示
3
第四章 关系
4.1 二元关系
4.1.1 基本概念 1)定义： A×B的子集叫做A到B上的一个二元关系。 A1×A2×A3的子集叫做A1×A2×A3上的一个三元 关系。 A1×A2×…xAn的子集叫做A1×A2×… × An上的 一个n元关系。 A×A×A ×… × A的子集叫做A上的n元关系。
1 1 0 0
1 0 1 0
1 1 0 1
18
第四章 关系
4.1 二元关系
3.关系图表示法
关系图由结点和边组成
若A= {x1, x2, …, xm}，R是A上的关系，R的关系图是 GR=<A, R>，其中A为结点集，R为边集。如果<xi,xj> R，在图中就有一条从 xi 到 xj 的有向边；如果<xi,xi> R，在图中就有一条从 xi 到 xi 的有向边。
12
第四章 关系
4.1 二元关系 4)关系的个数： 2，A×A的子集有 2 n 个。 假设|A|=n，|A×A|=n 2n 所以 A上有 个不同的二元关系。
离散数学 第4章 代数系统(2)
12
离散数学
定理1.设(G,*)是群，|G|2 。则 (1)G中每个元素的逆元是唯一的; (2)G中无零元。 [证]. (1)由于群有结合律，所以由书86页定理4.2可知， 逆元唯一；
(2)采用反证法：若零元0G ，则对任何元素gG ， 都有 0 * g=g * 0=0 (1) 由于G是群，每个元都有逆元。设0的逆元为g0，则有 0 * g0=g0 * 0 = 0 (2) 由逆元定义知 0 无逆元，与群中每个元素都有逆元矛盾。 所以G中无零元。
16
离散数学
例8.(G,o)是一有限群 o e a b c e e a b c 这里： G={e,a,b,c}, o运算的 a a e c b 运算表如右： b b c e a (1)封闭性：由表1可得； c c b a e (2)结合律：留待后证； 表1 (3)有幺元：e ； (4)有逆元：e-1=e,a-1=a,b-1=b,c-1=c 。 例如其第三行就与表头元素构成一置换P3。 此群一般称为Klein 4-群，又称为几何群或运动群。
注：Klein 日耳曼民族，几何学家，我国著名几何学家苏步青是他 的晚年弟子；
17
离散数学
e a bc P3 bc ea 。
[证]. 只证关于第i(1i n)行结论成立。我们设 G={a1(=e), a2,, an} 构造自然眏射 fi :GG 使得 对任何的aG， fi(a)=ai * a 为此，只须证明fi是一双射函数即可。 ①后者唯一： aj, akG， aj=ak ai * aj= ai * ak fi(aj)= fi(ak) ；
4
离散数学
例2. (I, +)是一个群 这里： I是整数集合，+是整数加法，由算术知识知： (1)封闭性：两个整数之和仍为整数，且结果唯一。即 a,b, aIbI a+bI ； (2)结合律：整数加法满足结合律。即 a,b,cI, (a+b)+c = a+(b+c) ； (3)有幺元：取 0I, aI,有a+0＝0+a＝a。 由幺元的定义知，0是关于+的幺元； (4)有逆元：aI，取-aI，有a+(-a)＝(-a)+a＝0。 由逆元的定义知I中每个元素都有逆元； 由群的定义知(I, Ʊ 设(G,*)是群，则*运算满足消去律。即x,y,zG, xy=xzy=z； yx=zxy=z 。 [证]. 只证第一式。x,y,zG, y=e*y = (x-1*x)* y = x-1*(x* y) (结合律) = x-1*(x* z) (条件：x y = x z ) = (x-1*x)* z (结合律) = e* z = z
离散数学
定理1.设(G,*)是群，|G|2 。则 (1)G中每个元素的逆元是唯一的; (2)G中无零元。 [证]. (1)由于群有结合律，所以由书86页定理4.2可知， 逆元唯一；
(2)采用反证法：若零元0G ，则对任何元素gG ， 都有 0 * g=g * 0=0 (1) 由于G是群，每个元都有逆元。设0的逆元为g0，则有 0 * g0=g0 * 0 = 0 (2) 由逆元定义知 0 无逆元，与群中每个元素都有逆元矛盾。 所以G中无零元。
16
离散数学
例8.(G,o)是一有限群 o e a b c e e a b c 这里： G={e,a,b,c}, o运算的 a a e c b 运算表如右： b b c e a (1)封闭性：由表1可得； c c b a e (2)结合律：留待后证； 表1 (3)有幺元：e ； (4)有逆元：e-1=e,a-1=a,b-1=b,c-1=c 。 例如其第三行就与表头元素构成一置换P3。 此群一般称为Klein 4-群，又称为几何群或运动群。
注：Klein 日耳曼民族，几何学家，我国著名几何学家苏步青是他 的晚年弟子；
17
离散数学
e a bc P3 bc ea 。
[证]. 只证关于第i(1i n)行结论成立。我们设 G={a1(=e), a2,, an} 构造自然眏射 fi :GG 使得 对任何的aG， fi(a)=ai * a 为此，只须证明fi是一双射函数即可。 ①后者唯一： aj, akG， aj=ak ai * aj= ai * ak fi(aj)= fi(ak) ；
4
离散数学
例2. (I, +)是一个群 这里： I是整数集合，+是整数加法，由算术知识知： (1)封闭性：两个整数之和仍为整数，且结果唯一。即 a,b, aIbI a+bI ； (2)结合律：整数加法满足结合律。即 a,b,cI, (a+b)+c = a+(b+c) ； (3)有幺元：取 0I, aI,有a+0＝0+a＝a。 由幺元的定义知，0是关于+的幺元； (4)有逆元：aI，取-aI，有a+(-a)＝(-a)+a＝0。 由逆元的定义知I中每个元素都有逆元； 由群的定义知(I, Ʊ 设(G,*)是群，则*运算满足消去律。即x,y,zG, xy=xzy=z； yx=zxy=z 。 [证]. 只证第一式。x,y,zG, y=e*y = (x-1*x)* y = x-1*(x* y) (结合律) = x-1*(x* z) (条件：x y = x z ) = (x-1*x)* z (结合律) = e* z = z
离散数学第四章
26
构造一个数b=0.b1b2b3b4…bn……， 其中 ： b1≠a11 b2 ≠ a22 b3≠a33… 于是 b ≠x 1 , b≠ x2, b≠ x3 ... 因此： b(0,1)
bn≠ ann... b ≠ xn …
但是b这样的形式应该是属于集合(0,1)的，因此产生 矛盾，所以(0,1)是不可数的。
1
基本概念
定义4.1 一个集合S与集合Nn={0,1,2，…n-1}，如 存在一一对应函数 f : Nn→S，则称S是有限集合， 并称其有基数n，如果S不是有限集合，则称为无 限集合。 说明：
由集合的元素个数来定义； 由于量变引起的质变； 它们中的一种性质都不能随意扩展到另一个集合中。
有限集和无限集
有限集合
元素的个数称为该集合的基数； 满足包含排斥原理。 元素无限多，如：自然数集合N、整数集I、实数集R等。 对于这样的集合有没有基数呢？ 如果有，基数是多少？ 无限集合之间有无大小的差别?
无限集合
问题：
本章主要借助于函数讨论集合的所谓“大小”问题。这里 用到自然数集合这个重要的概念讨论无限集。
27
说明：
• • • •
这种方法称为：康托对角线法； 对角线法并非康托尔关于实数不可数的第一个证 明，而是发表在他第一个证明的三年后； 他的第一个证明既未用到十进制展开，也未用到 任何其它数字系统； 自从该技巧第一次使用以来，在很大范围内的证 明中都用到了类似的证明构造方法。
28
由前面这些定理可知：
•
如此继续，可取出m3,m4,m5,…无限多个元素，则可得到另一个集合 M1={m1,m2,…}； 令M2=M-M1，即M中除去M1后得到的集合， 则M=M1∪ M2， 做另一集合M’={m2,m3,…} ∪M2，显然M⊃M’且M’~M，因此存在如 下一一对应的关系： 对于M的每个mi对应mi+1，对于M中的每个m∈ M2，对应M’中的 m。
构造一个数b=0.b1b2b3b4…bn……， 其中 ： b1≠a11 b2 ≠ a22 b3≠a33… 于是 b ≠x 1 , b≠ x2, b≠ x3 ... 因此： b(0,1)
bn≠ ann... b ≠ xn …
但是b这样的形式应该是属于集合(0,1)的，因此产生 矛盾，所以(0,1)是不可数的。
1
基本概念
定义4.1 一个集合S与集合Nn={0,1,2，…n-1}，如 存在一一对应函数 f : Nn→S，则称S是有限集合， 并称其有基数n，如果S不是有限集合，则称为无 限集合。 说明：
由集合的元素个数来定义； 由于量变引起的质变； 它们中的一种性质都不能随意扩展到另一个集合中。
有限集和无限集
有限集合
元素的个数称为该集合的基数； 满足包含排斥原理。 元素无限多，如：自然数集合N、整数集I、实数集R等。 对于这样的集合有没有基数呢？ 如果有，基数是多少？ 无限集合之间有无大小的差别?
无限集合
问题：
本章主要借助于函数讨论集合的所谓“大小”问题。这里 用到自然数集合这个重要的概念讨论无限集。
27
说明：
• • • •
这种方法称为：康托对角线法； 对角线法并非康托尔关于实数不可数的第一个证 明，而是发表在他第一个证明的三年后； 他的第一个证明既未用到十进制展开，也未用到 任何其它数字系统； 自从该技巧第一次使用以来，在很大范围内的证 明中都用到了类似的证明构造方法。
28
由前面这些定理可知：
•
如此继续，可取出m3,m4,m5,…无限多个元素，则可得到另一个集合 M1={m1,m2,…}； 令M2=M-M1，即M中除去M1后得到的集合， 则M=M1∪ M2， 做另一集合M’={m2,m3,…} ∪M2，显然M⊃M’且M’~M，因此存在如 下一一对应的关系： 对于M的每个mi对应mi+1，对于M中的每个m∈ M2，对应M’中的 m。
离散数学第四章课件
无对称的偶对。
表示关系矩阵的主对角线两侧各有一个1且 对称，即有一个对称的偶对。
C1
n(n＋1) 2
n(n＋1) C 2 n(n＋1) 2
表示关系矩阵的主对角线两侧全为1，
C1 ＋ n(n＋ ＋…＋ 2
n(n＋1) C 2 n(n＋1) 2
于是
C0 n(n＋1) 2 ＝
2
n(n＋1) 2
四、反对称性 ⒈ 定义： 若xy(x∈A∧y∈A∧xRy∧yRx→x=y)， 称R是反对称的。 例：设A={ a , b , c , d } R={ < a , b > , < a , c > , < b , b > , <b,d>,<c,c>,<c,d>, < d , d >}
⒉自反关系的关系矩阵的特征
R的关系矩阵的主对角线上的元素均为
1 ，则该关系就不具有自反性；
主对角线上有一个元素不为1，则该关
系就不具有自反性。
⒊ 自反关系的图的特征 自反关系的关系图中，每个顶点都有 自回路，则该关系具有自反性。
二、反自反性 ⒈ 定义：若x（x∈A xRx）则该关系是 反自反的。 ⒉ 具有反自反性的关系的关系矩阵的主对角
2 t1× t2 × … ×tn
五、关系的表示法-----通常有三种表示方法
⒈ 集合表示法： 因为关系也是集合，所以也可以用集合 的表示方法
例：A={ 2, 3,4,6 ,9,12 }上的整除关系
用特征描述法表示为
R＝{ < x , y > | x∈A ∧ y∈A ∧ x|y }
用穷举法表示为
R={ < 2 , 2 > , < 2 , 4 > , < 2 , 6 > ,
离散数学第4章-二元关系
4.6 等价关系与划分
• 三 性质 • 定理4.13 设R是A上的等价关系，则 （1）对任一a∈A，有a∈[a]； （2）对a, b∈A，如果aRb，则[a]=[b]; （3）对a, b∈A，如果(a, b)∉R，则[a]∩[b]=∅; （4）∪a∈A[a]=A。
4.6 等价关系与划分
• 定理4.14 集合A上的任一划分可以确定A上 的一个等价关系R。 • 定理4.15 设R1和R2是A上的等价关系， R1=R2⇔ A/R1=A/R2 。 • 定理4.16 设R1和R2是A上的等价关系，则 R1∩R2是A上的等价关系。
4 .3 关系的运算
• 一 逆运算 • 定义4.7（逆关系） 设R是从A到B的二元关系， 则从B到A的二元关系记为R-1，定义为R-1 ={(b,a)|(a,b)∈R}，称为R的逆关系。 • 定理2.1 （1）(R-1)-1=R; （2）(R1∪R2)-1= R1-1∪ R2-1; （3）(R1∩R2)-1= R1-1 ∩R2-1; （4） (A×B)-1= B×A；
4 .5 关系的闭包
•
• (1) (2) (3) • (1) (2) (3)
二 基本性质
定理4.5 设R是A上的二元关系，则 R是自反的 ⇔ r( R )=R； R是对称的 ⇔ s( R )=R； R是传递的 ⇔ t( R )=R； 定理4.6 设R1和R2是A上的二元关系，若R1⊆R2则 r(R1)⊆ r(R2)； s(R1)⊆ s(R2)； t(R1)⊆ t(R2)。
第四章 关系
4.1 二元关系 4.2 关系的性质 4 .3 关系的运算 4 .5 关系的闭包 4.6 等价关系与划分
4.1 二元关系
• 一 定义4.1（二元关系）
设A和B是任意两个集合，A×B的子集R称为从A到 B的二元关系。当A=B时，称R为A上的二元关系。若 (a, b)∈R，则称a与b有关系R，记为aRb。 (a, b)∉R：a与b没有关系R R=∅：空关系 R=A×B：全关系
离散数学 第四章 4
(3)
S={1,2,3,…,n}到自身的双射称为 元置换, 到自身的双射称为n元置换 到自身的双射称为 元置换 记为σ 记为σ，可表示为
2 n 1 σ = σ (1) σ (2) σ ( n )
上的双射即置换的个数共n!个 上置换 注：S上的双射即置换的个数共 个,S上置换 上的双射即置换的个数共 的全体记作S 的全体记作 n
2 设f是含有格中元素以及符号 是含有格中元素以及符号=,≤,≥，∨和∧ 是含有格中元素以及符号 ， 的公式， 是将f中的符号分别替换成 的公式，令f*是将 中的符号分别替换成 ， 是将 中的符号分别替换成=， ≥ ,≤, ∧与∨所得到的公式，则称 为f的对偶 所得到的公式，则称f*为 的对偶 命题。 命题。 3 对偶原理：f* f 对偶原理：
第六章
几个典型的代数系统
半群与群
格与布尔代数
6.1 半群与群
是一个代数系统, 设V=(G, )是一个代数系统 是一个代数系统 上的二元运算, 是G上的二元运算 上的二元运算 1 若 在G上成立结合律 则称 为半群。 上成立结合律 则称V为半群。 上成立结合律,则称 如：〈Z+, +〉, 〈N, +〉, 〈Z,+〉 〉 〉 〉 2 若 在G上成立结合律 且有单位元，则称 为 上成立结合律 上成立结合律, 有单位元，则称V为 独异点（含幺半群） 独异点（含幺半群）。 如： N, +〉, 〈Z,+〉 〈 〉 〉
轮换其乘法
例 设f=(15342), g=(125)(34) 求fg, g f, f-1, g-1
(4) 设M是非空集合 有n个元素 上所有置换 是非空集合,有 个元素 个元素,M上所有置换 是非空集合
的集合关于置换的乘法(函数的复合运算 构成 的集合关于置换的乘法 函数的复合运算)构成 函数的复合运算 一个群,称为 元对称群， 称为n元对称群 一个群 称为 元对称群， 它的任何子群称为n元置换群 元置换群。 它的任何子群称为 元置换群。 例题: 元对称群。 例题 S3是3元对称群。 元对称群
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
一、单项选择题共 8 道试题共 80 分。
得分01. 本课程的教学内容分为三个单元其中第三单元的名称是A. 数理逻辑B. 集合论C. 图论D. 谓词逻辑正确答案 A 满分10 分2. 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合其中第 2 章关系与函数中的第 3 个知识点的名称是A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系正确答案 D 满分10 分3. 本课程所有教学内容的电视视频讲解集中在 VOD 点播版块中VOD 点播版块中共有讲A. 18B. 20C. 19D. 17正确答案 B 满分10 分4. 本课程安排了 7 次形成性考核作业第 3 次形成性考核作业的名称是A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答正确答案 C 满分10 分5. 课程学习平台左侧第 1 个版块名称是A. 课程导学B. 课程公告C. 课程信息D. 使用帮助正确答案 C 满分10 分6. 课程学习平台右侧第 5 个版块名称是A. 典型例题B. 视频课堂C. VOD 点播D. 常见问题正确答案 D 满分10 分7. “教学活动资料”版块是课程学习平台右侧的第个版块A. 6B. 7C. 8D. 9正确答案 A 满分10 分8. 课程学习平台中“课程复习”版块下放有本课程历年考试试卷的栏目名称是A. 复习指导B. 视频C. 课件D. 自测正确答案 D 满分10 分二、作品题共 1 道试题共 20 分。
得分101. 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划学习计划应该包括课程性质和目标参考教学大纲、学习内容、考核方式以及自己的学习安排字数要求在 100—500 字完成后在下列文本框中提交学习离散数学有两项最基本的任务其一是通过学习离散数学使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理掌握计算机中常用的科学论证方法为后续课程的学习奠定一个良好的数学基础其二是在离散数学的学习过程中培训自学能力、抽象思维能力和逻辑推理能力以提高专业理论水平。
因此学习离散数学对于计算机、通信等专业后续课程的学习和今后从事计算机科学等工作是至关重要的。
但是由于离散数学的离散性、知识的分散性和处理问题的特殊性使部分学生在刚刚接触离散数学时对其中的一些概念和处理问题的方法往往感到困惑特别是在做证明题时感到无从下手找不到正确的解题思路。
因此对离散数学的学习方法给予适当的指导和对学习过程中遇到的一些问题分析是十分必要的。
一、认知离散数学离散数学是计算机科学基础理论的核心课程之一是计算机及应用、通信等专业的一门重要的基础课。
它以研究量的结构和相互关系为主要目标其研究对象一般是有限个或可数个元素充分体现了计算机科学离散性的特点。
1定义和定理多离散数学是建立在大量定义、定理之上的逻辑推理学科因此对概念的理解是学习这门课程的核心。
在学习这些概念的基础上要特别注意概念之间的联系而描述这些联系的实体则是大量的定理和性质。
在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用因此要真正理解离散数学中所给出的每个基本概念的真正的含义。
2. 方法性强在离散数学的学习过程中一定要注重和掌握离散数学处理问题的方法在做题时找到一个合适的解题思路和方法是极为重要的。
如果知道了一道题用怎样的方法去做或证明就能很容易地做或证出来。
反之则事倍功半。
在离散数学中虽然各种各样的题种类繁多但每类题的解法均有规律可循。
3. 抽象性强离散数学的特点是知识点集中对抽象思维能力的要求较高。
由于这些定义的抽象性使初学者往往不能在脑海中直接建立起它们与现实世界中客观事物的联系。
不管是哪本离散数学教材都会在每一章中首先列出若干个定义和定理接着就是这些定义和定理的直接应用如果没有较好的抽象思维能力学习离散数学确实具有一定的困难。
在学习离散数学中所遇到的这些困难可以通过多学、多看、认真分析讲课中所给出的典型例题的解题过程再加上多练从而逐步得到解决。
二、认知解题规范一般来说离散数学的考试要求分为了解、理解和掌握。
了解是能正确判别有关概念和方法理解是能正确表达有关概念和方法的含义掌握是在理解的基础上加以灵活应用。
总体评价一、单项选择题共 10 道试题共 100 分。
得分1001. 设集合 A ={1 , 2 , 3 , 4}上的二元关系 R ={<1, 1><2, 2> <2, 3><4, 4>}S ={<1, 1><2, 2><2, 3><3, 2><4, 4>}则 S 是 R 的闭包A. 自反B. 传递C. 对称D. 自反和传递满分10 分2. 设函数 f N N f(n)n+1下列表述正确的是A. f 存在反函数B. f 是双射的C. f 是满射的D. f 是单射函数满分10 分3. 若集合 A {2 a { a }4}则下列表述正确的是( )A. {a{ a }} AB.Ø AC. {2} AD. { a } A满分10 分4.设集合 A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如右图所示若A 的子集 B = {3,4, 5}则元素 3 为 B 的A. 下界B. 最小上界C. 最大下界D. 最小元满分10 分5. 设 A、B 是两个任意集合侧 A-B = Ø⇔ ( )A. A=BB. A BC. A BD. BØ满分10 分6. 若集合 A { a { a }{12}}则下列表述正确的是( )A. { a { a }} AB. {12} AC. { a } AD. A满分10 分7. 设集合 A = {1, a }则 P ( A ) = ( )A. {{1}, { a }}B. { ,{1}, { a }}C. {{1}, { a }, {1, a }}D. { ,{1}, { a }, {1, a }}满分10 分8. 设 A ={ a , b } B ={1, 2} R 1 R 2 R 3 是 A 到 B 的二元关系且 R 1 ={< a 2>,< b 2>} R 2 ={< a 1>, < a 2>, < b 1>} R 3 ={< a1>, < b 2>}则不是从 A 到 B 的函数A.R 1B.R 2C.R 3D. R 1 和 R 3满分10 分9. 设集合 A ={ a }则 A 的幂集为( )A. {{ a }}B. { a { a }}C. { { a }}D. { a }满分10 分10. 设 A ={ a b c } B ={12}作 f A → B 则不同的函数个数为A. 2B. 3C. 6D. 8满分10 分一、单项选择题共 10 道试题共 100 分。
得分1001.设有向图a、b、c与d如图四所示则下列结论成立的是( )图四A. a是强连通的B. b是强连通的C. c是强连通的D. d是强连通的满分10 分2.设无向图 G 的邻接矩阵为则 G 的边数为( )A. 1B. 6C. 7D. 14满分10 分3. 无向树 T 有 8 个结点则 T 的边数为( )A. 6B. 7C. 8D. 9满分10 分4.如图所示以下说法正确的是 ( )A. e 是割点B. { a, e }是点割集C. { b , e }是点割集D. {d}是点割集满分10 分5. 若 G 是一个欧拉图则 G 一定是( )A. 平面图B. 汉密尔顿图C. 连通图D. 对偶图满分10 分6. 设 G 是连通平面图有 v 个结点 e 条边r 个面则 r= ( )A. e v 2B. v e 2C. e v 2D. e v 2满分10 分7. 设无向图 G 的邻接矩阵为则 G 的边数为( )A. 6B. 5C. 4D. 3满分10 分8.如图一所示以下说法正确的是 ( )A. {(a, e)}是割边B. {(a, e)}是边割集C. {(a, e) ,(b, c)}是边割集D. {(d, e)}是边割集满分10 分9.设有向图 a 、 b 、 c 与 d 如图所示则下列结论成立的是( )A. a 只是弱连通的B. b 只是弱连通的C. c 只是弱连通的D. d 只是弱连通的满分10 分10. 无向完全图 K 4 是A. 欧拉图B. 汉密尔顿图C. 非平面图D. 树满分10 分一、单项选择题共 10 道试题共 100 分。
得分1001. 设 C(x)x 是国家级运动员G(x)x 是健壮的则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )A.B.C.D.满分10 分2. 命题公式P Q的合取范式是 ( )A. P QB. P Q P QC. P QD. P Q满分10 分3. 设 P我将去打球Q我有时间命题“我将去打球仅当我有时间时”符号化为( )A.B.C.D.满分10 分4. 设个体域 D={a, b, c}那么谓词公式消去量词后的等值式为A. (A(a)A(b)A(c))(B(a)B(b)B(b))B. (A(a)A(b)A(c))(B(a)B(b)B(b))C. (A(a)A(b)A(c))(B(a)B(b)B(b))D. (A(a)A(b)A(c))(B(a)B(b)B(b))满分10 分5. 命题公式(P Q)Q 为( )A. 矛盾式B. 可满足式C. 重言式D. 合取范式满分10 分6. 命题公式 P Q 的主合取范式是( )A. (P Q)B. P QC. P QD.P Q满分10 分7. 命题公式的析取范式是( )A.B.C.D.满分10 分8. 下列公式 ( )为重言式A. P Q P QB. (Q(P Q)) (Q(P Q))C. (P(Q P))(P(P Q))D. (P(P Q)) Q满分10 分9. 命题公式(P Q)R 的析取范式是 ( )A. (P Q)RB. (P Q)RC. (P Q)RD. (P Q)R满分10 分10. 下列等价公式成立的为( )A. P Q P QB. P(Q P) P(P Q)C. Q(P Q) Q(P Q)D. P(P Q) Q满分10 分一、填空题1．命题公式 ( ) P Q P 的真值是 1 ．2．设 P：他生病了， Q：他出差了． R：我同意他不参加学习 . 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (P ∨ Q )→ R ．3．含有三个命题变项 P， Q， R的命题公式 P Q 的主析取范式是(P Q R)∨ (P Q ┐ R) ．4．设 P(x)： x 是人， Q(x)： x 去上课，则命题“有人去上课．”可符号化为)) ( ) ( ( x Q x P x．5．设个体域 D＝ { a, b} ,那么谓词公式 ) ( ) ( y yB x xA 消去量词后的等值式为)) ( ) ( ( ) ( ) ( b B a B b A a A．6．设个体域 D＝ {1 , 2, 3} ， A(x)为“ x 大于 3”，则谓词公式 ( x)A(x) 的真值为 0 ．7．谓词命题公式 ( x)((A(x) B(x)) C(y))中的自由变元为 y ．8．谓词命题公式 ( x)(P(x) Q(x) R(x， y))中的约束变元为 x ．三、公式翻译题1 ．请将语句“今天是天晴”翻译成命题公式．解：设 P：今天是晴天，命题“今天是晴天”翻译成命题公式为 P。