当前位置： >>
离散数学---代数系统的一般性质5.2-3
5.2 代数系统及其子代数、积代数? ? ? ?代数系统定义 同类型与同种的代数系统 子代数积代数1代数系统定义与实例定义 非空集合 S 和 S 上 k 个一元或二元运算 f1, f2, … , fk 组成的系统称为一个代数系统, 简称代 数，记做 V=&lt
;S, f1, f2, … , fk&.S 称为代数系统的载体， S 和运算叫做代数系 统的成分. 有的代数系统定义指定了S中的特殊 元素，称为代数常数, 例如二元运算的单位元. 有时也将代数常数作为系统的成分.2实例&N,+&, &Z,+,? &R,+,? &, &是代数系统， + 和? 分别表示普通加法和乘法. &Mn(R),+,? &是代数系统， +和? 分别表示n 阶 (n≥2) 实矩阵的加法和乘法. &Zn,?,?&是代数系统，Zn＝{0, 1, … , n-1}， ? 和 ? 分别表示模 n 的加法和乘法，?x,y∈Zn， x?y = (x＋y) mod n，x?y = (xy) mod n &P(S),∪,∩,~& 也是代数系统， ∪和∩为并和交，~为绝对补3同类型与同种代数系统定义 (1) 如果两个代数系统中运算的个数相同， 对应运算的元数相同，且代数常数的个数也相同， 则称它们是 同类型的 代数系统. (2) 如果两个同类型的代数系统规定的运算性质 也相同，则称为 同种的 代数系统. 例1 V1 = &R, +, ?0, 1&, , V2 = &Mn(R), +, ??, E&, , ? 为 n 阶全 0 矩阵，E 为 n 阶单位矩阵 V3 = &P(B), ∪, ∩, ?, B&4同类型与同种代数系统（续）V1+ 可交换, 可结合 ?可交换, 可结合 + 满足消去律 ?满足消去律 ?对+可分配 + 对 ?不可分配 +与 ?没有吸收律V2+ 可交换, 可结合 ? 可交换, 可结合 + 满足消去律 ?满足消去律 ?对+可分配 + 对 ?不可分配 +与 ?没有吸收律V3∪可交换, 可结合 ∩可交换, 可结合 ∪不满足消去律 ∩不满足消去律 ∩对∪可分配 ∪对∩可分配 ∪与∩满足吸收律V1, V2, V3是同类型的代数系统 V1, V2是同种的代数系统 V1, V2与V3不是同种的代数系统5子代数定义 设V=&S, f1, f2, … , fk& 是代数系统，B 是 S 的非空子集 ，如果 B 对 f1, f2, … , fk 都是封闭的， 且 B 和 S 含有相同的代数常数，则称 &B, f1, f2, … , fk& 是 V 的子代数系统，简称 子代数. 有时 将子代数系统简记为 B. 实例 N是&Z,+& 和&Z,+,0&的子代数. N?{0}是 &Z,+&的子代数，但不是&Z,＋,0&的子代数 说明： 子代数和原代数是同种的代数系统 对于任何代数系统 V ，其子代数一定存在.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 的非平凡的真子 代数.7积代数定义 设 V1=&S1,o&和 V2=&S2,?&是代数系统，其中 o 和 ? 是二元运算. V1 与 V2 的 积代数 是V=&S1?S2,?&, ?&x1,y1&, &x2,y2&?S1?S2 , &x1,y1& ? &x2,y2&=&x1ox2, y1?y2& 例3 V1=&Z,+&, V2=&M2(R), ? &, 积代数& Z?M2(R),o& ?&z1,M1&, &z2,M2&?Z?M2(R) , &z1,M1& o &z2,M2& = &z1+z2, M1?M2&?1 0? ? 2 ? 1? ? 2 ? 1? ? 5, ? ? 1 1 ? ? ? ? ?2, ? 0 1 ? ??? 3, ? 2 0 ? ? ? ? ? ? ? ? ? ? ? ? ?8积代数的性质定理 设 V1 = &S1,o&和 V2 = &S2,?&是代数系统，其中 o 和 ?是二元运算. V1 与 V2 的积代数是 V=&S1?S2,?& (1) 若 o 和 ? 运算是可交换的，那么? 运算也是可交换的 (2) 若 o 和 ? 运算是可结合的，那么? 运算也是可结合的 (3) 若 o 和 ? 运算是幂等的，那么? 运算也是幂等的 (4) 若 o 和 ? 运算分别具有单位元 e1 和 e2，那么? 运算 也具有单位元&e1,e2& (5) 若 o 和 ? 运算分别具有零元 ?1 和 ?2，那么? 运算 也具有零元& ?1, ?2& (6) 若 x 关于 o 的逆元为 x?1, y 关于 ? 的逆元为 y?1，那 么&x,y&关于? 运算也具有逆元&x?1,y?1&95.3 代数系统的同态与同构同态映射的定义 ? 同态映射的分类?? 单同态、满同态、同构? 自同态?同态映射的性质10同态映射的定义定义 设 V1=&S1,?&和 V2=&S2,?&是代数系统，其中 ? 和 ?是二元运算. f: S1?S2, 且?x,y?S1, f (x?y) = f(x) ?f( y), 则称 f 为V1到 V2 的同态映射，简称同态.11更广泛的同态映射定义定义 设 V1=&S1,?,?&和 V2=&S2,?, ?&是代数系统，其 中 ?和 ?是二元运算. f: S1?S2, 且?x,y?S1 f (x ? y) = f(x) ? f(y) , f (x ? y) = f(x) ? f(y) 则称 f 为V1到 V2 的同态映射，简称同态. 设 V1=&S1, ?,?, ?&和 V2=&S2,?, ?, ?&是代数系统， 其中? 和 ? 是二元运算. ? 和 ?是一元运算， f: S1?S2, 且?x,y?S1 f (x?y)=f(x)?f(y), f (x?y)=f(x)?f(y), f (? x)=?f(x) 则称 f 为V1到 V2 的同态映射，简称同态.12例题例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 解 (2) , (5), (6) 不是自同态. (1) 是同态， f(x?y) = |x?y| = |x| ?|y| = f(x) ?f(y) (3) 是同态， f(x?y) = (x?y)2 = x2 ?y2 = f(x) ?f(y) (4) 是同态， f(x?y) = 1/(x?y) =1/x ?1/y = f(x) ?f(y)13特殊同态映射的分类同态映射如果是单射，则称为单同态； 如果是满射，则称为 满同态，这时称 V2 是 V1的同态像，记作 V1?V2；如果是双射，则称为 同构，也称代数系统 V1 同构于V2，记作 V1?V2 . 对于代数系统 V，它到自身的同态称为自同态. 类似地可以定义单自同态、满自同态和自同构.14同态映射的实例例2 设V=&Z,+&，?a?Z，令 fa：Z?Z，fa(x)=ax 那么 fa是V的自同态. 因为?x,y?Z，有 fa(x+y) = a(x+y) = ax+ay = fa(x)+fa(y) 当 a = 0 时称 f0为零同态； 当a=?1时，称 fa为自同构； 除此之外其他的 fa 都是单自同态.15同态映射的实例（续）例3 设V1=&Q,+&, V2= &Q*,?&，其中Q*= Q?{0}，令 f ：Q?Q*, f(x)=ex那么 f 是V1到V2的同态映射，因为?x, y?Q有f(x+y) = ex+y = ex?ey = f(x) ? f(y). 不难看出 f 是单同态.16同态映射的实例（续）例4 V1=&Z,+&，V2=&Zn,? &，Zn={0,1, … , n-1}, ?是模 n 加. 令 f：Z→Zn，f(x) = (x)mod n 则 f 是V1到 V2 的满同态. ?x, y∈Z有 ?? f(x+y) = (x+y)mod n = (x)mod n ? (y)mod n = f(x) ? f(y)17同态映射的实例（续）例5 设 V=&Zn,?&，可以证明恰有 n 个G 的自同态， ?? fp：Zn→Zn, fp (x) = (px)mod n，p = 0,1, … , n?1 例如 n = 6, 那么 f0为零同态； f1与 f5为同构； f2 与 f4的同态像是{ 0, 2, 4 }； f3 的同态像是{ 0, 3 }.18同态映射保持运算的算律设V1,V2是代数系统. o,?是V1上的二元运算，o’,?’是V2上对应的二元运算，如果 f： V1?V2是满同态，那么 (1)若o运算是可交换的（可结合、幂等的），则o’运 算也是可交换的（可结合、幂等的）. (2) 若o运算对?运算是可分配的，则o’运算对?’运 算也是可分配的；若o 和?运算是可吸收的，则 o’ 和?’运算也是可吸收的。19同态映射保持运算的特异元素(3) 若e为o 运算的单位元，则 f(e)为o’运算的单位元.(4) 若 ?为o 运算的零元，则 f(?) 为o’运算的零元.(5) 设 u?V1，若 u?1 是 u 关于o运算的逆元，则 f(u?1)是 f(u)关于o’运算的逆元。20同态映射的性质说明： 上述性质仅在满同态时成立，如果不是满同态， 那么相关性质在同态像中成立. 同态映射不一定能保持消去律成立. 例如 f : Z?Zn 是 V1=&Z,? 到 V2=&Zn,?&的同 & 态，f(x)=(x)mod n, V1中满足消去律，但是当 n 为合数时, V2中不满足消去律.21例题例3 设V1=&Q,+& ，V2=&Q*,? &，其中 Q 为有理数 集合，Q*=Q?{0}，+ 和 ? 分别表示普通加法和乘法. 证明不存在 V2 到 V1 的同构.证 假设 f 是 V2 到 V1 的同构，那么有f：V2→V1，f(1)=0. 于是有?? ??f(?1)+f(?1) = f((?1)(?1))= f(1)=0从而 f(?1)=0，又有 f(1)=0，这与 f 的单射性矛盾.22
离散数学习题解答 习题五(第五章 格与布尔代数) 1...{1,2,3,4,5,6,8,9,10} [解] a) 〈L,?...[证] a) 方法一,根据上、下确界的性质,由 a*...离散数学答案【5】_理学_高等教育_教育专区。离散数学第十四章部分课后习题参考答案 5、设无向图 G 有 10 条边,3 度与 4 度顶点各 2 个,其余顶点的度数均...离散数学数理逻辑、集合论、代数、图论的定义性质。...代数系统:代数系统,子代数,积代数,同态,同构。 3....2. 3. 4. 5. A ? (A?B) (A?B) ? A ...离散数学填空题及答案_计算机软件及应用_IT/计算机_...(个 5 度结点。 )答:6 填 2 空题 6.1 3 ...] 是代数系统,则 [ L,?,?] 满足幂等律,即对...离散数学复习题及答案_公务员考试_资格考试/认证_...A(1) ? A(2) ? A(3) ? A(4) 5.求下图...设代数系统 ? S ,* ? 是个独异点,对任意 a, ...y =(x+y) mod n,则 代数系统(G, ? )___。 (1) 是半群但不是群 (2) 是无限群 (3) 是循环群 (4) 是变换群 (5)是交换群 10、仅有一个结点...(5)除非 2&1,否则 3?2。 (6)2&1 仅当 3&2。 -1- 离散数学 专业...A},则 R 的性质为( ). A.自反的 B.对称的 C.传递且对称的 D.反自反且...离散数学习题答案_理学_高等教育_教育专区。离散数学...r 15、设 p:2+3=5. q:大熊猫产在中国. r:......,10?,问下面的运算能否与S 构成代数系统 S ...自​考​22离​散​数​学​第​五​章​课​后​答​案自考2324 离散数学课后答案 5.1 习题参考答案 1、设无向图 ...离散数学习题解答 习题五(第五章 格与布尔代数) 1...8 10 4 6 9 5 2 3 7 1 2.设 A,B 是两...3 (利用*运算结合律) 方法二:根据上,下确界性质...
All rights reserved Powered by
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。离散数学答案 79_离散数学答案-牛宝宝文章网
离散数学答案 79 离散数学答案
第一章 集合论基础1.设S = {2，a，{3}，4}，R ={{a}，3，4，1}，指出下面的写法哪些是对的，哪些是错的？ {a}?S,{a}?R,{a,4,{3}}?S,{{a},1,3,4}?R,R=S,{a}?S,{a}?R,??R,??{{a}}?R?E,{?}?S,??R,??{{3},4}。解： {a}?S?，{a}?R?，{a，4，{3}} ? S?，{{a}，1，3，4 } ? R?，R = S?，{a}? S?，{a}? R?，? ? R?，? ? {{a}} ? R ? E?，{?} ? S?，??R?，? ? {{3}，4 }?2写出下面集合的幂集合{a，{b}}，{1，?}，{X，Y，Z}解： 设A={a，{b}}，则?(A)={ ?，{a}，{{b}}，{a，{b}}}；设B={1，?}，则?(B)= { ?，{1}，{?}，{1，?}}；设C={X，Y，Z}，则?(C)= { ?，{X}，{Y}，{Z}，{X，Y }，{X，Z }，{ Y， Z }，{X，Y，Z}}；3对任意集合A，B，证明：(1)A?B当且仅当?(A)? ?(B)；(2)?(A)??(B)??(A?B)；(3)?(A)??(B)=?(A?B)；(4)?(A-B) ?(?(A)-?(B)) ?{?}。举例说明：?(A)∪?(B)≠?( A∪B)证明：(1)证明：必要性，任取x??(A)，则x?A。由于A?B，故x?B，从而x??(B)，于是?(A)? ?(B)。充分性，任取x?A，知{x}?A，于是有{x}??(A)。由于?(A)? ?(B)，故{x}??(B)，由此知x?B，也就是A?B。（2）证明：任取X??(A)∪?(B)，则X??(A)或X??(B)∴ X?A或X?B∴ X?(A∪B)∴ X??(A∪B)所以?(A)∪?(B) ? ?( A∪B)（3）证明：先证?(A)∩?(B) ? ?( A∩B)任取X??(A)∩?(B)，则X??(A)且X??(B)∴ X?A且X?B∴ X? A∩B∴ X??( A∩B)所以?(A)∩?(B) ? ?( A∩B)再证?( A∩B) ? ?(A)∩?(B)任取Y??(A∩B)，则Y? A∩B∴ Y?A且Y?B∴ Y??(A)且Y??(B)∴ Y??(A)∩?(B)所以?( A∩B) ? ?(A)∩?(B)故?(A)∩?(B) = ?( A∩B)得证。举例：A={1}，B={a}则?(A)={ ?，{1}}，?(B)={ ?，{a}}?(A)∪?(B) = { ?，{1}，{a}}A∪B={1，a}?( A∪B)={ ?，{1}，{a}，{1，a}}可见{1，a}??( A∪B)，{1，a}??(A)∪?(B)所以?(A)∪?(B)≠?( A∪B)(4)对任意的集合x，若x=?，则x??( A-B) 且x?(?( A) -?( B))∪{?}。若x??，则x??( A-B)当且仅当x? ( A-B)当且仅当x?
A?x?B当且仅当x??( A) ?x??( B) 当且仅当x?(?(A)-?(B))。综上所述，可知?(A-B) ?(?(A)-?(B)) ?{?}。4.设A,B,C为任意三个集合，下列各式对否？并证明你的结论。（1）若A?B且B?C，则A?C；（2）若A?B且B?C，则A?C；（3）若A?B且B?C，则A?C；（4）若A?B且B?C，则A?C。解：（1）正确；（2）不正确，举一个反例即可；（3）不正确，举一个反例即可；（4）不正确，举一个反例即可。5.对24名科技人员进行掌握外语情况的调查，其统计资料如下：会英、日、德、法语的人数分别是13，5，10和9。其中同时会英语、日语的人数为2。同时会说英语、德语或同时会说英语、法语，或同时会说德语、法语两种语言的人数均为4。会说日语的人既不会说法语也不会说德语。试求只会说一种语言的人数各为多少？同时会说英、德、法语的人数为多少？解：设A，B，C，D分别代表会说英、日、德、法语人的集合。由已知条件知：?A?=13，?B?=5，?C?=10，?D?=9，?A?B?=2，而?A?C?=?A?D?=?C?D?=4，?B?C?=?B?D?=?A?B?C?=?A?B?D?=?B?C?D?=?A?B?C?D?=0，?A?B?C?D?=24。对集合A，B，C，D应用容斥原理，并代如入已知条件得方程24=37-14+?A?C?D?于是?A?C?D?=1，这说明同时会说英、德、法语的人只有1人。设只会说英、日、德、法语的人数分别是x1，x2，x3，x4，则x1=?A?-?（B?C?D）?A?=?A?-?（B?A ）?(C?A )?( A ?D)?对B?A，C?A，A ?D应用容斥原理，得x1=4。同理可求出：x2=3，x3=3，x4=2。6.设A，B是两个集合，问在什么条件下有A?B?A成立？等号能成立吗？解：当A或B为空集时能够成立；当A为空集时等号能够成立。2.设A是m元集合，B是n元集合。问A到B共有多少个不同的二元关系？设A={a，b}，B={1， 2}，试写出A到B上的全部二元关系。解：A到B上共有2个二元关系。本题中A?B的全部子集?，{(a,1)}，{(a,2)}，{(b,1)}，{(b,2)}， {(a,1),(a,2)}，{(a,1),(b,1)}，{(a,1),(b,2)}，{(a,1),(b,2)}，{(a,2),(b,1)}，{(a,2),(b,2)}，{(a,1),(a,2),(b,1)}，{(a,1),(a,2),(b,2)}，{(a,1),(b,1),(b,2)}，{(a,2),(b,1),(b,2)}，{(a,1),(a,2),(b,1),(b,2)}为A到B的全部二元关系。7.R，S是集合A上的两个关系。试证明下列等式：（1）(R?S)-1= S-1?R-1（2）(R-1)-1= R（3）(R∪S)-1= R-1∪S-1（4）(R∩S)= R∩S证明：（1）先证(R?S)-1? S-1?R-1，对任意(x，y) ?(R?S)-1，则(y，x) ?(R?S)，则存在a?A，满足(y，a) ?R且(a，x) ?S，那么(x，a) ?S且(a，y) ?R，所以(x，y) ? S?R，因此(R?S)? S-1?R-1；再证S-1?R-1 ?(R?S)-1，对任意(x，y) ? S-1?R-1，则存在a?A，满足(x，a) ?S-1且(a，y) ?R，所以(y，a) ?R且(a，x) ?S，所以(y，x) ?(R?S)，所以(x，y) ?(R?S)，因此S?R ?(R?S)-1。（2）先证(R-1)-1? R，对任意(x，y) ?(R-1)-1，则(y，x) ? R-1，则(x，y) ? R，所以(R-1)-1? R；再证R ?(R-1)-1，对任意(x，y) ? R，则(y，x) ? R-1，则(x，y) ?(R-1)-1，所以R ?(R-1)-1。故(R-1)-1= R得证。-1-1-1-1
（3）先证(R∪S)? R∪S，对任意(x，y) ?(R∪S)，则(y，x) ? R∪S，则(y，x) ? R或(y，x) ?S，则(x，y) ?R-1或者(x，y) ?S-1，所以(x，y) ? R-1∪S-1，所以(R∪S)-1? R-1∪S-1； 再证R∪S ?(R∪S)，对任意(x，y) ? R∪S，则(x，y) ?R或者(x，y) ?S，则(y，x) ? R或(y，x) ?S，所以(y，x) ? R∪S，所以(x，y) ?(R∪S)-1，所以R-1∪S-1 ?(R∪S)-1。故(R∪S)-1= R-1∪S-1得证。（4）先证(R∩S)-1? R-1∩S-1，对任意(x，y) ?(R∩S)-1，则(y，x) ? R∩S，则(y，x) ? R且(y，x) ?S，则(x，y) ?R-1且(x，y) ?S-1，所以(x，y) ? R-1∩S-1，所以(R∩S)-1? R-1∩S-1； 再证R-1∩S-1?(R∩S)-1，对任意(x，y) ? R-1∩S-1，则(x，y) ?R-1且(x，y) ?S-1，则(y，x) ? R且(y，x) ?S，所以(y，x) ? R∩S，所以(x，y) ?(R∩S)，所以R∩S?(R∩S)。故(R∩S)= -1-1R∩S得证。8.设R是集合A上的关系，令R+={(x, y)|x?A，y?A，并且存在n&0，使得xRny}，则称R+是R的传递闭包，证明：R+是包含R的最小具有传递性的关系。证明： -1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1mn（1）证明R ? R，对任意(x，y)?R，即x R y，即存在n=1，使得x Ry，所以(x，y)?R，所以R ? R；（2）证明R+具有传递性：++
方法一：（根据传递性的定义）对于任意x，y，z?A，若xRy，yRz，则存在m，n(m&0，n&0)，使得xRmy，yRnz，因此有xRm?Rnz，即xRm+nz，所以xR+z，故R+具有传递性。
方法二：（根据定理1.2.4）对于任意(x，y)?R?R，则存在a?A，满足(x，a)?R，(a，y)?R，故存在m，n(m&0，n&0)，使得x Rm a，a Rny，因此有xRm?Rny，即x Rm+n y，所以xR+y，所以R?R ? R，故R具有传递性。+
（3）证明R的最小性：方法一：设任意的集合P，P ? R且P具有传递性，往证R+ ? P。对任意的(x，y)?R，则存在n(n&0)，使得x R y，若n=1，则有x R y，即(x，y)?R，所以(x，y)? P；若n&1，则存在a1,a2,??,an-2,an-1，满足x R a1，a1 R a2，a2 R a3，??，an-2 R an-1，an-1 R y，因为P ? R，所以有x P a1，a1 P a2，a2 P a3，??，an-2 P an-1，an-1 P y，又P具有传递性，所以有x P y，即(x，y)? P，因此R+ ? P。方法二：（用数学归纳法）设集合T(n)＝R∪R2∪R3∪R4∪?∪Rｎ (n&0)，根据R+的定义，有R+＝T(∞)，设任意的集合P，P ? R且P具有传递性，往证T(∞)? P。用数学归纳法：当ｎ＝１时，显然T(1)＝R ? P成立；假设当n=k时，结论成立，即有T(k)＝R∪R∪R∪R∪?∪R? P那么当ｎ＝k+1时T(k+1)＝R∪R∪R∪R∪?∪R∪R＝T(k) ∪Rｋ＋１根据假设有T(k) ? P，这里只需证明Rｋ＋１? P即可。对任意的(x，y)? Rｋ＋１，则存在a?A，满足(x，a)? Rｋ, (a，y)? R，根据假设，Rｋ?T(k) ? P，且由已知R ? P，所以(x，a)? P , (a，y)?P，又P具有传递性，所以(x，y)? P，故Rｋ＋１? P，从而T(k+1) ? P成立。因此，T(∞)? P，故R＋? P成立得证。9.若非空集合上的非空关系R是反自反的，是对称的，试证明R不是传递的。证明：反证法：假设R是传递的，对于任意(a，b)?R，因为R是对称的，所以(a，b)? R，则有(a，a)? R，这与R是不反身的矛盾，故假设不成立，原结论成立。10.集合A上的关系是对称的，反对称的，试指明关系R的结构。解：R的结构是A 中元素只可能与自身有关系。8.若集合A上的关系R具有传递性，则R+=R。证明：R是包含R的最小具有传递性的关系，则对任意包含R的且有传递性的关系都包含R+，又因为R?R ，且R具有传递性，所以R+?R，又R+?R，所以R+＝R11.设R是非空集合A上的关系，如果1）对任意a?A，都有a R a ；2）若aRb，aRc，则bRc ；证明：R是等价关系。 +234ｋｋ＋１ +n +++++++++++n234ｋ证明：根据已知，对任意a?A，都有a R a，故R具有反身性；对任意a、b?A，若aRb，又有a R a，根据2），有bR a，故R具有对称性；对任意a、b、c?A，若a R b，b R c，又R具有对称性，则有bRa，bRc，根据2），有 a R c，故R具有传递性因此，R是等价关系。12.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a ? b可得b ? a，再由传递性得a ? a”。你的意见呢？解：这种说法是错误的。对于任意a?A，和一个A上的等价关系R，可能不存在a R b，也就推不出a R a了，而反身性则要求对于每一个a?A，都有a R a。13.若集合A上的关系R，S具有对称性，证明：R?S具有对称性的充要条件为R?S= S?R。证明：充分性：若R?S= S?R，往证R?S具有对称性。对于任意x，y?A，若(x，y)? R?S，则存在a?A，满足(x，a)?R，(a，y)? S，又R，S具有对称性，所以有(y，a)? S，(a，x)? R，所以(y，x)? S?R，又S?R= R?S，故(y，x)? R?S，因此R?S具有对称性；必要性：若R?S具有对称性，往证R?S= S?R。先证R?S? S?R：对于任意(x，y)? R?S，因R?S具有对称性，则有(y，x)? R?S，则存在a?A，满足(y，a)?R，(a，x)? S，又R，S具有对称性，所以有(x，a)? S，(a，y)? R，所以(x，y)? S?R，故R?S? S?R；再证S?R? R?S：对于任意(x，y)?S?R，则存在a?A，满足(x，a)? S，(a，y)? R，又R，S具有对称性，所以有(y，a)?R，(a，x)? S，故(y，x)? R?S，因R?S具有对称性，所以(x，y)? R?S，故S?R? R?S；因此，R?S= S?R得证。14.若R是等价关系，试证明R-1也是等价关系。-1-1证明：因为R是等价关系，所以R有对称性，所以有R= R，所以R也是等价关系。15.证明：映射的乘法满足结合律，举例说明：映射的乘法不满足交换律。证明：设?是集合A到集合B内的映射，?是集合B到集合C内的映射，?是集合C到集合D内的映射，对于任意a?A，有( (???)??)(a)= (???)(? (a) ) = ?(? (? (a) ) )(??(???))(a)= ?((???) (a) ) = ?(? (? (a) ) )可见( (???)??)(a)= (??(???))(a)，所以映射的乘法满足结合律。举例：设映射?：a?bb?cc?a映射?：a? cb?bc? a则(???)(a)= ?(? (a) )= ?(b)=b离散数学答案 79_离散数学答案(???)(a)= ? (? (a) )= ? (c)=a可见(???)(a) ? (???)(a)，映射的乘法不满足交换律。16.设?是集合M到集合N内的映射，证明对M的任意子集A，B，有?( A∩B) ? ? (A)∩? (B)，举例说明：?( A∩B) = ? (A)∩? (B)不成立。证明：对任意y??(A∩B) ?N，则存在y的原象x，使得?(x)=y，因y??( A∩B)，所以x?A∩B，即x?A并且x?B，所以有y??(A)且y??(B)，即y?? (A)∩? (B)，故?( A∩B) ? ? (A)∩? (B)。例：设M={1，2，3，4}，A={1，2，3}，B={2，3，4}
3?c4?a则?( A∩B)= ?( {2，3})={b，c}? (A)∩? (B)= {a，b，c}∩{a，b，c}={a，b，c}17.设?是集合M到集合N内的映射，A是N的子集，M中所有在?下映射到A中的元素集合称为A的逆象集，记为?-1 (A)，若A，B是N的任意子集，求证：?-1 ( A∩B) = ? -1 (A)∩?-1 (B)。
证明：先证? ( A∩B) ? ?
(A)∩? (B)。对任意x??-1 ( A∩B)，则?(x)?A∩B，所以?(x)?A且 ?(x)?B，那么
x??-1 (A)且x?? (B)，即x??
(A)∩? (B)，故? ( A∩B) ? ?
(A)∩? (B)。再证? -1 (A)∩?-1 (B) ??-1 ( A∩B)。对任意x?? -1 (A)∩?-1 (B)，则x??-1 (A)且x??-1 (B)，所以?(x) ? A且?(x)? B，即?(x) ? A∩B，所以x??-1 (A∩B)，故? -1 (A)∩?-1 (B) ??-1 ( A∩B)。因此，?-1 ( A∩B) = ? -1 (A)∩?-1 (B)。-1-1-1-1-1-1-1-1-1第二章 命题逻辑1. 设P是命题“天下雪”；Q是命题“我上街”；R是命题“我有时间”。 （1）用逻辑符号写出以下命题：a． 如天不下雪并且我有时间，那么我上街。 b． 我去上街，仅当我有时间。 c． 天不下雪。d． 天正在下雪，我也没去上街。 解： a可表示为：(?P?R) ?Q； b可表示为：Q?R； c可表示为：?P；d可表示为：P??Q。（2）对下述命题用中文写出语句。
a．Q?（R??P）b．R?Qc．（Q?R）?（R?Q）
d．?（R?Q）解： a为：我上街当且仅当我有时间并且天不下雪； b为：我有时间并且上街了； c为：我上街了当且仅当我有时间； d为：我每时间又没上街。2. 说出下述每一命题的逆命题和逆否命题： （1） 如果天下雨，我将不去。 （2） 仅当你去我将逗留。（3） 如果n是大于2的正整数，则方程x+y=z无正整数解。（4） 如果我不获得更多帮助，我不能完成这个任务。解： （1）逆命题为：如果我不去，那么天下雨；逆否命题为：如果我去，那么天不下雨。（2）逆命题为 ：仅当我将逗留你去；逆否命题为：你不去我将不逗留。（3）逆命题为：如果方程x+y=z无正整数解，则n是大于2的正整数；逆否命题为：如果方程xn+yn=zn有正整数解，则n是不大于2的正整数。(4)逆命题为：我不能完成这个任务，因为我没有获得更多帮助。逆否命题：如果我完成了任务，则我获得了更多帮助。3. 给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值： a) (P?(Q?R))??((P?Q)?(R?S))b) (?(P?Q)??R)?(((?P?Q)??R)?S) c) (?(P?Q)??R)?((Q??P)?(R??S)) d) (P?(Q?(R??P)))?(Q??S) 解：a)令G= (P?(Q?R))??((P?Q)?(R?S))
则：TI(G) = (1?(1?0))??((1?1)?(0?0))
= 0??0=1b)令G=(?(P?Q)??R)?(((?P?Q)??R)?S) 则：TI (G) = (?(1?1)??0)?(((?1?1)??0)?0)
= 1?0=1c) 令G =(?(P?Q)??R)?((Q??P)?(R??S))
=(?(P?Q)??R)?( ? ( (?Q??P) ?(P ?Q)) ?(R??S))
=(?P??Q??R)?( (Q?P) ? (?P ??Q) ?(R??S)) 则：TI (G) =(?1??1??0)?( (1?1) ? (?1 ??1) ?(0??0)) = 1?1=1 d) 令G
=(P?(Q?(R??P)))?(Q??S)=(P?(Q?(R??P)))?(Q??S)
=(P?(?Q?(R??P)))?(Q??S)=(? (P?(?Q?(R??P))) ? (Q??S)) ?(? (Q??S) ? (P?(?Q?(R??P)))) =(? P ? (Q? (?R?P))) ? (Q??S)) ?((? Q?S) ? (P?(?Q?(R??P))))TI (G) =(? 1 ? (1? (?0?1))) ? (1??0)) ?((?1?0)nnnnnn? (1?(?1?(0??1))))=1 ?1=14. 指出下列公式哪些是恒真的哪些是恒假的： (1)P?（P? Q）?Q(2)（P? Q）?（?P?Q）(3)（P? Q）? （Q?R）?（P? R ）(4)（P? Q）?（P? Q??P?? Q）解：（1）是恒真的，（2）是恒真的，（3）是恒真的，（4）是可满足的。5. 对P和Q的所有值，证明P? Q与?P?Q有同样的真值。证明（P? Q）?（?P?Q）是恒真的。解： 对P? Q的任意解释I，若I使P? Q为真，则I使P为假或P和Q同时为真，若I使P为假，则使?P，此时?P?Q为真，若I使P和Q同时为真，则Q为真，此时?P?Q为真，也就是说P? Q为真时?P?Q为真。若I使P? Q为假，则I使P为真Q为假，此时?P?Q为假，也就是说P? Q为假时?P?Q为假。综上知P? Q与?P?Q同真同假，由定义知（P? Q）?（?P?Q）是恒真的。6.判断下列公式是恒真？恒假？可满足？
a) (P?(Q?R))?(?P?(?Q??R))；
b) P?(P?(Q?P))；c) (Q?P)?(?P?Q)； d) (?P??Q)?(P??Q)。解： （1）设G=(P?(Q?R))?(?P?(?Q??R))=(?P?(Q?R)) ?(P? (?Q??R))=(((?P?( Q?R)) ?P) ? ((?P?(Q?R)) ??Q??R) =((?P?P)?( P?Q?R)) ? ((?P?(Q?R)) ??Q??R) =((?P?P)?( P?Q?R)) ? ((?P?Q)? (?P?R)??Q??R) =((?P?P)?( P?Q?R)) ? (((?P?Q) ??Q) ?((?P?R)? ?R))（2）设G= P?(P?(Q?P)) =?P?( P?(?Q?P))=?P? P =T其真值表如下：因此G是恒真的。(3) G=(Q?P)?(?P?Q)
=(?Q? P) ?(?P?Q) =?(?P?Q) ?(?P?Q)=F因此G是恒假的。(4) G=(?P??Q)?(P??Q)=(P?Q) ? ((P??Q) ?( ?Q?P))=(P?Q) ? ((?P? ?Q) ?( Q?P))
=( P?Q) ?(?P?Q) ?( P??Q)7.证明下面的等价式：(1) (?P?(?Q?R))?(Q?R)?(P?R)=R (2) P?(Q?P)=?P?(P?Q) (3) P?(Q?R)=(P?Q)?(P?R) (4) (P?Q)?(R?Q)=(P?R)?Q(1)证明：(?P?(?Q?R))?(Q?R)?(P?R)=(((?P?(?Q?R)) ?Q) ?((?P?(?Q?R)) ? R) )?(P?R) =((((?P?Q) ?(R ?Q)) ?((?P? R) ? R)) ?(P?R) =((?P?Q) ?(R ?Q) ? R) ?(P?R) =((?P?Q) ?R) ?(P?R) =(?P ?R) ? (Q ?R) ?(P?R) =R?(?P?P) ? (Q ?R) =R
得证。(2) 证明：左边= P?(Q?P)= ?P? (?Q? P) 因此G是可满足的。= ?P? ?Q? P= P??P? ?Q
=T右边=?P?(P?Q)=P??P? Q=T可有：左边=右边，得证(3)证明：左边= ?P? Q?R右边= ?P? Q??P? R
=?P? Q?R可有：左边=右边，得证 (4)证明：左边= (?P? Q) ? (? R? Q)8设S={G1，?，Gn}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。提示：考虑G1???Gn的主合取范式。解：任设一公式G’为从S出发演绎出来的公式。则可知G’为G= G1???Gn的一个逻辑结果。而G有唯一一个与其等价的主合取范式，设为G’’。可设G’’共有m个极大项，则可以知道令G’’取1的解释使这m 个极大项也取1。则从S出发的演绎出来的的所有命题公式正是从这m个极大项中任取n(0≤n≤m)个合取组成，共有2m个，其中包括恒真公式这里用1表示。设H为由若干极大项构成的合取公式。现在证明：1) S=&H，即G=&H。从定义出发，设有一解释I使G=G1???Gn 取1值，必使G的主合取范式也取1值。即使每一个极大项都取1值。从而使由若干极大项合取组成的公式H也取1值，则有S=&H。2) 任意设公式H是S的一个逻辑结果，H是一些极大项的合取。现在要证组成H的极大项都在G的主合取范式G”中。反证法：若不然，假设H中有一个极大项mk不在G的主合取范式中。则取使mk为0的解释I，可有解释I使H取0值。而I使所有不等于mk的极大项都为1，则可有G的主合取范式G’’在I下取1值，即G在I下取1值，这与G=&H矛盾。9.证明：两个公式之间的蕴涵关系具有反身性，反对称性和传递性。 证明：a)任意设一公式P,由于P?P是恒真的，则有P=&P 即蕴涵关系有反身性。b)任取两个命题公式P，Q如果P=&Q 并且Q=&P，则有P?Q恒真，Q?P恒真，则（P?Q）?（Q?P）恒真，那么有P?Q恒真，得出P=Q，所以蕴涵关系有反对称性。 c)任取命题公式P，Q，R如果P=&Q，Q=&R；对于P，Q，R的任意一个解释I。如果I满足P则I也满足Q，=(?P? ? R) ? Q =? (P ?R) ? Q=(P ?R) ? Q=右边 得证离散数学答案 79_离散数学答案若I满足Q则I满足R。则有I满足P时，也满足R，故有P=&R。因此蕴涵关系有传递性。10.证明：若前提集合S中的公式都是恒真的，G是从S出发的一个演绎的逻辑结果，则G必是恒真公式。证明：设S是由G1，?，Gn构成的，则G1，?，Gn是恒真的，那么G1?…? Gn是恒真的，而由已知有：G1?…? Gn=&G，因此由蕴涵定义有G必为恒真公式。11.设G1，?，Gn是公式。证明：从{G1，?，Gn}出发可演绎出公式G的充要条件是从{G1，?，Gn，?G}出发可演绎出公式(R??R)。其中R为任意公式。证明： 充分性，即{G1，?，Gn，?G}=&(R??R)，可有G1?…? Gn??G=&(R??R)，因(R??R)恒假，则G1?…? Gn??G恒假。那么有?（G1?…? Gn）?G恒真，即（G1?…? Gn）?G恒真，则有(G1?…? Gn )=&G，因此有{G1，?，Gn}蕴涵G。必要性，即已知：{G1，?，Gn}=&G，有（G1?…? Gn）?G恒真，即?（G1?…? Gn ）? G恒真，那么对上式取非有G1?…? Gn??G恒假，也就是(G1?…? Gn??G) ?(R??R)恒真，其中R为任意一个公式，则有(G1?…? Gn??G) =& (R??R)，即从{G1，?，Gn，?G}出发可演绎出公式(R??R)。命题得证。12.证明下列蕴涵式：(1)(P?Q)?(P?Q)证明：要证上式成立即证(P?Q) ? (P?Q)恒真，则：(P?Q) ? (P?Q)=? (P?Q) ? (?P?Q)=(?P ??Q) ? (?P?Q)=?P ??Q?Q=T即：(P?Q) ? (P?Q)恒真命题得证。(或从P?Q?Q，Q?(P?Q))(2)P?(Q?P)证明：同a)，P? (Q?P)=?P ?(?Q?P)=?P ?P??Q=T命题得证。(或从P ?(?Q?P)出发)(3) (P?(Q?R))?(P?Q)?(P?R)证明：(P?(Q?R)) ? (P?Q)?(P?R)=(P?Q??R) ?? (P?Q??R)=T得证。(4) P?Q?P?(P?Q)证明:若P?(P?Q)为假，则P?Q为假，P为真。因而有Q为假，则P?Q为假，(后件假推出前件假等价于前件真推出后件真)得证。(5) (P?Q)?Q?P?Q证明：(P?Q)?Q=? (?P ? Q) ? Q=(P? ?Q) ? Q=(P? Q) ?(Q ??Q)=&(P? Q)
(基本蕴涵式)(6) ((P??P)?Q)?((P??P)?R)?(Q?R)证明：若(Q?R)为假，则R为假，Q为真，则(P??P)?R为假，而(P??P)?Q为真，则有((P??P)?Q)?((P??P)?R)为假，得证。（用P?Q证明也可）(7) (Q?(P??P))?(R?(P??P))?(R?Q)证明：若(R?Q)为假，则Q为假，R为真，则R?(P??P)为假，而Q?(P??P)为真。有(Q?(P??P))?(R?(P??P))为假，得证。13.证明{C?D，(C?D)??H，?H?(A??B)，(A??B)?(R?S)}共同蕴涵R?S。 证明：1) C?D
规则12) (C?D)??H
规则13) ?H
规则2，根据1),2)4) ?H?(A??B)
规则15) (A??B)
规则2，根据3),4)6) (A??B)?(R?S)
规则17) R?S
规则2，根据5),6)14.证明{P?Q，Q?R，P?M，?M}共同蕴涵R?(P?Q)。证明：1) P?M
规则12) ?M? ?P
规则2，根据1)3) ?M
规则14) ?P
规则2，根据2),3)5) P?Q
规则16) ?P?Q
规则2，根据5)7) Q
规则2，根据4),6)8) Q?R
规则2，根据7),8)10) R?(P?Q)
规则2，根据5),9)15.证明{?P?Q，?Q?R，R?S}共同蕴涵P?S。证明：1) ?P?Q
规则3（附加前提）3)Q
规则2，根据1),2)4) ?Q?R
规则2，根据3),4)6) R?S
规则2，根据5),6)8) P?S
规则3，根据2),7)16.试证明公式：((P?Q)??(?P?(?Q??R)))?(?P??Q)?(?P??R)是恒真公式。证明：原式=((P?Q)??(?P?(?Q??R)))?(?P??Q)?(?P??R)=((P?Q)? (P ? (Q?R))) ?(?P??Q)?(?P??R) =((P?Q)? (P ? Q)?( P ?R)) ?? (P?Q)? ? ( P?R)=( P? (Q ? R)) ??( P? (Q ? R))=T17.模仿主析取范式的概念，引进主合取范式的概念。 并证明： 对任意命题公式，存在唯一一个与其等价的主合取范式。首先引进极大项概念：定义6：设P1，?，Pn是n个不同原子，一个子句如果恰好包含所有这n个原子或其否定，且其排列顺序与P1，?，Pn的顺序一致，则称此子句为关于P1，…，Pn的一个极大项。 定义7：设命题公式G中所有不同原子为P1，?，Pn，如果G的某个合取范式G’中的每一个子句，都是关于P1，?，Pn的一个极大项，则称G’为G的主合取范式。证明：（对任意命题公式，存在唯一一个与其等价的主合取范式。）由定理1知对于命题公式G，存在与它等价的合取范式G’,设G中的不同原子为P1，?，Pn。对于G’中的每一个子句G’i进行检查，如果G’i不是关于P1，?，Pn的极大项，则G’i必然缺少原子Pj1,…Pjk。则可以通过如下方式扩展G’iG’i= G’i? (Pj1?? Pj1) ?…?( Pjk?? Pjk)=Mi1?…?Mi2k于是将G’中的非极大项G’i化成了一些极大项的合取。对其它非极大项也做同样处理，得到等价于G的主合取范式G’’。现在证唯一性，也就是证明对任意两个关于P1，?，Pn的主合取范式，如果公式不完全相同，则G与H不等价。任意取两个命题公式G、H是关于P1，?，Pn的两个主合取范式。若G和H不完全相同。则必然存在一个极大项Mi在G’中而不在H中（或相反），则取一解释I使Mi取0值，即使公式G取0值。由定义可知I使非Mi的极大项都为1，从而有I使H取1值。所以G与H不等价。从而有对任意命题公式，存在唯一一个与其等价的主合取范式。18. 证明： 命题公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。证明：设公式G的合取范式为：G’=G1?G2?…?Gn若公式G恒真，则G’恒真，即子句Gi；i=1,2,…n恒真为其充要条件。Gi恒真则其必然有一个原子和它的否定同时出现在Gi中，也就是说无论一个解释I使这个原子为1或0 ，Gi都取1值。若不然，假设Gi恒真，但每个原子和其否定都不同时出现在Gi中。则可以给定一个解释I，使带否定号的原子为1，不带否定号的原子为0，那么Gi在解释I下的取值为0。这与Gi恒真矛盾。因此，公式G是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。19. 试将下列公式化为析取范式和合取范式：a) P?(P?Q)b) ?(P?Q)?(P?Q)解：a)P?(P?Q)=P?(?P?Q)
(合取范式)
=(P??P) ?(P?Q)
(析取范式)=P?Q
(合取、析取范式)b) ?(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))=(P?Q) ?(?P??Q)
(合取范式)=((P?Q) ??P) ?((P?Q) ??Q)=( ?P ? Q) ? (P ??Q)
(析取范式)20. 试将下列公式化为主析取范式和主合取范式：(1) P?((P?Q)??(?Q??P))；(2) P?(?P?(Q?(?Q?R)))。解：(1) P?((P?Q)??(?Q??P))=?P?((?P?Q) ? Q?P)=?P?(Q?P)=(?P ?(Q??Q)) ?(Q?P)=(?P ?Q) ?(?P??Q) ?(Q?P)
(主析取范式)=?P?(Q?P)=(?P?Q) ?(?P?P)=?P?Q
（主合取范式）(2) P?(?P?(Q?(?Q?R)))=P?(P?(Q?(Q?R)))=P?(P?Q?R)=P?Q?R
（主合取范式）=(P?(Q?? Q) ?(R??R)) ?(Q?(P?? P) ?(R??R)) ?(R?(P?? P) ?(Q??Q))=(P?Q?R)?(P??Q?R) ? (P?Q??R) ?(P??Q??R)? (Q?P?R) ? (Q??P?R) ? (Q?P??R) ? (Q??P??R)? (R?P?Q) ? (R??P?Q) ? (R?P??Q) ? (R??P??Q)=(P?Q?R)?(P??Q?R) ? (P?Q??R) ?(P??Q??R) ?(Q??P?R) ? (Q??P??R) ? (R??P??Q)=(P?Q?R)?(P??Q?R) ? (P?Q??R) ?(P??Q??R) ?(?P?Q?R) ? (?P?Q??R) ? (?P??Q ?R)(主析取范式)第三章 谓词逻辑1.设下面所有谓词的定义域都是{a，b，c}。试将下面谓词公式中的量词消除，写成与之等价的命题公式。(1) ?xR(x)??xS(x)(2) ?x(P(x)?Q(x))(3) ?x?P(x)??xP(x)解： （1） ?xR(x)??xS(x)等价的命题公式为：R(a) ? R(b) ? R(c) ?( S(a) ? S(b)? S(c))（2） ?x(P(x)?Q(x))等价的命题公式为：(P(a)?Q(a)) ? (P(b)?Q(b)) ? (P(c)?Q(c))（3）?x?P(x)??xP(x)等价的命题公式为：(?P (a) ??P (b) ??P (b)) ? (P (a) ?P (b) ?P (b))2．指出下列表达式中的自由变量和约束变量，并指明量词的作用域：（1）(?xP(x)??xQ(x))?(?xP(x)?Q(y))（2）?x?y((P(x)?Q(y))??zR(z))（3）A(z)?(??x?yB(x，y，a))（4）?x A(x)??yB(x，y)（5）(?xF(x)??yG(x，y，z))??zH(x，y，z)解： （1）中的自由变量是Q(y)中的y，约束变量是P(x)、Q(x))和P(x)中的x，第一个量词?x的作用域是P(x)，第2个量词?x的作用域是Q(x)，第三个量词?x的作用域是P(x)。（2）此式中没有自由变量，x，y，z都是约束变量，?x和?y的作用域都是(P(x)?Q(y))??zR(z)，而?z的作用域是R(z)。（3）z是自由变量，x和y是约束变量，?x?y的作用域是B(x，y，a)。（4）x是自由变量，x和y是约束变量，?x 的作用域是A(x)，?y的作用域是B(x，y)。（5）x，y和z是自由变量并且x，y和z又是约束变量，?x的作用域是F(x)，?y的作用域是G(x，y，z)，?z的作用域是H(x，y，z)。3.设I是如下一个解释：D={a，b}离散数学答案 79_离散数学答案1
1 试确定下列公式在I下的真值： (1) ?x?yP(x，y)；真值为1 (2) ?x?yP(x，y)；真值为0 (3) ?x?yP(x，y)；真值为0 (4) ?y?P(a，y)；真值为1(5) ?x?y(P(x，y)?P(y，x))；真值为1 (6) ?xP(x，x) 真值为14.设G=?xP (x)??xP(x)。(1)若解释I的非空区域D包含仅仅一个元素，则G在I下取1值。 解： 设仅含的元素为a，则G＝P(a)?P(a)。故G在I下取1值 (2)设D={a，b}，试找出一个D上的解释I，使G在I下取0值。P(a)
05.设I是如下一个解释：
0 试求出下列公式在I下的真值：（1） (a，f(a))?P(b，f(b))；真值为0 （2） x?yP(y，x)；真值为1（3） x?y(P(x，y)?P(f(x)，f(y)))；真值为06.设G1=?x(P(x)?Q(x))，G2=?Q(a)，证明：?P(a)是G1和G2的逻辑结果。 证明：设G =G1 ?G2，往证若解释I满足G，则必满足?P(a)。反证法：若解释I满足G，而弄假?P(a)，则在解释I下，P(a)为真；G2也必为真，所以Q(a)为假。故P(a)?Q(a)为假，则G1为假，因此G为假，这与解释I满足G矛盾。从而结论得证。7.试将下列公式化成等价的前束范式： (1)?x(P(x)??yQ(x，y))； =?x(?P(x) ? ?y Q(x，y)) =?x?y(?P(x) ? Q(x，y))(2)?x((??yP(x，y))?(?zQ(z)?R(x)))； =?x((??yP(x，y)) ?(?(?zQ(z)) ? R(x))) =?x((?yP(x，y)) ? (?(?zQ(z)) ? R(x))) =?x((?yP(x，y)) ? (?z (?Q(z)) ? R(x))) =?x?y (P(x，y) ? (?z (?Q(z)) ? R(x))) =?x?y?z (P(x，y) ? ?Q(z) ? R(x) )(3)?x?y(?zP(x，y，z)?(?uQ(x，u)??vQ(y，v)))。 =?x?y?z (P(x，y，z) ? (?(?uQ(x，u)) ? ?vQ(y，v))) =?x?y?z (P(x，y，z) ? (?u(?Q(x，u)) ? ?vQ(y，v))) =?x?y?z (P(x，y，z) ? ?u ?v (?Q(x，u) ? Q(y，v))) =?x?y?z?u?v(P(x，y，z) ? (?Q(x，u) ? Q(y，v)))8.找出下面公式的Skolem范式： (1)?(?xP(x)??y?zQ(y，z))； =?(?(?xP(x)) ??y?zQ(y，z)) =?xP(x) ??(?y?zQ(y，z))) =?x(P(x) ? ?y?(?zQ(y，z))) =?x?y (P(x) ? ?z(?Q(y，z))) =?x?y ?z (P(x) ??Q(y，z))用f(x，y)代替z得Skolem范式:?x?y(P(x) ??Q(y，f(x，y)))(2)?x(?E(x，0)?(?y(E(y，g(x))??z(E(z，g(x))?E(y，z)))))。 ＝?x(?E(x，0)?(?y(E(y，g(x))??z(?E(z，g(x))?E(y，z))))) ＝?x(E(x，0) ? (?y(E(y，g(x))??z(?E(z，g(x))?E(y，z))))) ＝?x?y?z (E(x，0) ? (E(y，g(x))? (?E(z，g(x))?E(y，z))))＝?x?y?z ((E(x，0) ? E(y，g(x)) )? (E(x，0) ??E(z，g(x))?E(y，z))) 用f(x)代替y得Skolem范式:Skolem范式: ?x?z((E(x，0) ? E( f(x)，g(x))) ? (E(x，0) ??E(z，g(x)) ? E( f(x)，z)))9.假设?x?yM(x，y)是公式G的前束范式，其中M(x，y)是仅仅包含变量x，y的母式。设f是不出现在M(x，y)中的函数符号，证明：G是恒真的当且仅当?xM(x，f(x))是恒真的。证明： ?若G=?x?yM(x，y)恒真，而G1=?xM(x，f(x))不恒真，则有解释I弄假G1,于是在解释I下，对于任意x?D，有f(x)?D，使得M(x，f(x))为假，但解释I也是G的解释，于是I弄假G，矛盾。?若G1恒真，而G不恒真，则有解释I弄假G，于是存在（x0，y0）?D，使得M(x0，y0)为假，扩充解释I为I?，使包含函数符号f(x)的解释为f(x0)= y0，则I?弄假G1，矛盾。 因此，原结论成立。2第四章 图与网络221.若G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：n?Cm ，其中Cm 表示m中取2的组合数。证明：如果G=(P,L)为完全图，即对于任意的两点u、v（u≠v）,都有一条边uv，则此2时对于元数为m的P(G)，L(G)的元数取值最大为Cm。因此，若G=(P,L)为一有限图，设P(G)22的元数为m，则有L(G)的元数n ?Cm，其中Cm 表示m中取2的组合数。2.设G是有限图，M，A分别是G的关联矩阵和相邻矩阵，证明：MM’和A的对角线2上的元素是G中所有点的度。证明：设P(G)的元数为m，L(G)的元数为n。则可知M为m×n阶矩阵，M’为n×m阶矩阵。n1) 设B=M?M’为一m×m阶矩阵。则其对角线上的元素为：dii=?aija' i=1,2,…m。j?1nn2ijn而M’是M的转置矩阵，因此aij=a’ji并且aij为0或1，因此有dii=?aija'ji=?aj?1j?1=?aij。j?1即dii等于M中第i行的1的个数，因此dii等于点vi（i=1,2,…,n）的度。2) 设C=A，则C中对角线上元素为Cii=? i=1,2,…m。由于A是mxm阶对称j?1nn2ij2n矩阵，有bij=bji 并且bij为0或1，则有Cii=?bj?1=?bij。即Cii为A中第i行对应的1j?1的个数，即第i行对应的点vi（i=1,2,…,n）的度。3.设G是有限图，P(G)，L(G)的元数分别为m，n。?，?分别是G中点的最小度和最大度。证明：??2n/m??。证明：因为 m???dv?P(G)G同时由定理1知(v)?m?，?dv?P(G)G于是有 m??2n?m?。 (v)=2n。故由m&0有：??2n/m??。24.设G=(P，L)是有限图，P(G)，L(G)的元数分别为m，n。证明：如果n&Cm ，则G?1是连通的。证明：反证法，假设此时G不是连通的，则将G中的一个连通分支作为一个子图记为G1，剩余的部分记为G2。可设P(G1)的元数为m1，P(G2) 的元数为m2，其中1≤m1，m2&m，m1+m2=m。则：2n≤Cm1?Cm22= m1(m1-1)/2+ m2(m2-1)/2=1/2(m12+m22- m1- m2) =1/2(m12+(m-m1)2- m) =1/2(m2-m-2mm1+2m1)=1/2(m-m-2m1(m-m1)) =1/2(m2-m-2m1m2)由于(m1-1) (m2-1) ≥0所以有：m1 m2- (m1+m2)+1≥0 即 m1 m2≥ m-1
则有：n ≤1/2(m2-m-2m1m2)≤1/2(m2-m-2(m-1)) =1/2(m2-3m+2)2=1/2(m-1)(m-2)2=Cm ?12显然这与已知n&Cm矛盾，命题得证。 ?15.证明：连通图中任意两条最长的简单路必有公共点。证明：设有限图G=(P，L)是连通的，且有两条最长的简单路：l1：(v1, v2,……vn) l2：(v1, v2,……vm)’假设l1和l2无公共点，取l1中一点v1，l2中一点v1，则由于G连通知必然有一条简单路l3 : (x1, x2,……,xk)，其中x1= v1，xk = v1’。设xj是l3中从左往右看第一个l2中的点vh’，得一简单路l4：(x1, x2,……,xj)，设xi是l4中从右往左看第一个l1中的点vg，则又得到一个简单路l5：(xi, xi+1,……,xj)，| l5|?1，且l5中除了xi和xj外，没有l1，l2中的点，不妨设|(v1, v2,……xi)| ?|(xi, vg+1,……vn)|, |(v1, v2,……xj) |?|( xj, vh+1,……vm)|,则可以取到简单路l6：(v1, v2,……xi, xi+1,……,xj, vh-1’, ……v1’),因为| l5|?1，所以| l6|&min{| l1|,| l2| },这样我们就可以得到一条更长的路，矛盾。因此，命题得证。6.一公司在六个城市c1，c2，?，c6中的每一个都有分公司。从ci到cj的班机旅费由下’’’’’’’列矩阵中的第i行第j列元素给出(?表示没有直接班机)：0
0公司所关心的是计算两城市间的最便宜路线的表格。请准备一张这样的表格。解：先求出C1到C2,…,C6的最短路线。L(C1)
{C1, C6}C1?C635
{C1, C6, C5}C1?C535
{C1, C6, C5, C2, C4}C1?C6 ?C2
C1?C6 ?C4或C1?C5 ?C445
{C1, C6, C5, C2, C4, C3}
C1?C5 ?C3或C1?C6 ?C4?C3同理可得出任意两城市间的最便宜路线。最后表格如下：7.设G为图（可能无限），无回路，但若任意外加一边于G后就形成一回路，试证G必为树。证明：从树的定义出发， 1）由已知有G中无回路。 2）要证G连通，反证法，假设G不连通，则一定存在点u和v，满足在G中没有从u到v的路，现在连接u、v，即在G中添加一条边uv，由已知G中加一条边后形成一回路可知，G中u、v两点间有一回路，即若G中删除边uv后，点u、v仍然连通，矛盾。所以G连通。因此，G必为树。8.证明：一个有限连通图G是一条非回路的简单路，当且仅当G中有两个点的度为1，且其余点的度均为2。证明：必要性，因为G是一条非回路的简单路，G有限，所以显然G路的两个端点度数为1，其余各点度数为2。设P(G)的元数为n，k=3时显然成立。假设k=n-1时，G中有两个点的度为1，且其余点的度均为2。充分性，k=3时显然成立，假设k=n-1时，G是一条非回路的简单路。则当k=n时，设v1是路G中度为1的一点，v2是与v1相邻的另一点，把点v1及边v1v2从G中删去得G?，此时v2的度必为1（若为0则与G是连通图矛盾；若为2则在G中v2的度为3，矛盾），有假设知G?是一条非回路的简单路。把点v1及边v1v2加入到G?中得G显然仍成立，归纳法完成。离散数学答案 79_离散数学答案9. 试举出一个连通的(即漠视为图后是连通的)，但无根的有向图。
解：下图是连通但无根的有向图。10.设G是有向图，其中含一有向路(e1，?，en)，其中fin(en)=init(e1)，证明：G不是有向树。证明：若(e1，?，en)是一条简单路，则由fin(en)=init(e1)可知(e1，?，en)是一有向回路，得出G不是有向树。若(e1，?，en)不是一条简单路，则由已知一定有一点k满足：k=min{i|i≤n，且fin(ei)=init(ej)，1≤i,j≤n}，即k是(e1，?，en)中第一条有向回路中最大的弧的编号。因此，由于G中存在有向回路得出G不是有向树。11.设G为有向图，若G具有有向树定义中的1)和2)，并且没有有向回路。问：若G有限，G是否是有向树？若G不是有限的，如何？解：1）G有限，由已知有：①G中每一点恰是一条弧e 的起点。②r不是任一条弧的起点现只需证r是根，即对于任意一点v必有一条到r的有向路。由于每一个点只发出一条弧，设v发出弧e1到v’，若v’不为r，则v’必发出一条弧到达v”（因为无回路，v”，v’，v互不相同）。假设已经找到点v(k) ，若v(k) =r则得到v到r的有向路，否则可以继续向前找，但因为G有限，有向路必然终止在某一点设为u，若u≠r，则u必为已经找到的一点v(i) ，因而形成回路，产生矛盾，则可知u=r，故有从u到r的有向路，因v任意，则r为根，所以G是有向路。2如：12. 有n个人，任何两个人合起来都认识其余n-2个人，证明：这n个人可排成一列，使得任何人都认识其前后邻人（首尾人为单侧）。如果n?4，则这n个人可排成一圈，任何人都认识其左右邻人。证明：把这n(n?3)个人看作n个节点，所有认识的人之间连一条线，构成一个图G，我们只要证明G中有Hamilton回路即可。设u, v是G中不相邻两点（即u,v代表的人互相不认识），则对任意vk(?u,v)必与u或v相邻，否则与题设条件矛盾（即v, vk代表的两人至多只能与除u外的n-3个人认识）。设vk与u相邻，同样又因为u与v不相邻，故vk必与v也相邻。于是d(u)+d(v)=2(n-2)=n+n-4?n-1。不是有向树，有向树。若u,v是G中相邻两点，则显然有d(u)+d(v) ?n-2+2&n-1。总之，对G中任意两点有d(u)+d(v) ?n-1。由第3题知G中存在Hamilton路，也就是能够把这n个人可排成一列，使得任何人都认识其前后邻人（首尾人为单侧）。当n?4时，若u,v不相邻，则同样道理有d(u)+d(v)=2(n-2)=n+n-4?n。若u,v相邻，则d(u)+d(v)?n-2+2=n。总之有d(u)+d(v)?n，从而C(G)是完全的，于是G是Hamilton图。13 证明：若一个图G的任意两点度数之和?n-1，n=|P(G)|，则该图有Hamilton路。 证明：先证G为连通图。若不然，假设G有若干连通分支，设G1, G2是G的两个连通分支且各有n1, n2个节点。显然n1+n2&n。设v1, v2分别属于P(G1), P(G2)，于是dG(v1)?n1-1，dG(v2)?n2-1，从而dG(v1)+dG(v2)?n1-1+n2-1?n1+n2-2?n-2&n-1，这与题设矛盾，1212因此假设不成立。其次证明G中存在Hamilton路。设L=(v1, v2, …, vl)为G中一条长度为l-1的简单路，不妨设此通路的端点不再与L以外的点相邻，否则将相邻的节点扩充到该路中来。（1） 若l=n，则L为G中的Hamilton路。（2） 若l&n，则我们证明G中存在经过v1, v2, …, vl的回路。（i） （ii）若v1与vl相邻，则(v1, v2, …, vl)就是G中的一条回路。若v1与vl不相邻，设v1与vi=v2,vi,…,vi相邻，则vi,vi,…,vi均在L中，且k?2。假若k=1，则因v1与vl不相邻，因而d(vl) ?l-2，于是12k12k12kd(v1)+d(vl) ?1+l-2=l-1&n-1与题设矛盾。又vl至少与vi-1,vi-1,…, vi-1中的一个点相邻，否则vl至多与l-1-1-(k-1)=l-k-1个点相邻。于是d(v1)+d(vl) ?k+l-k-1=l-1&n-1，与题设矛盾。不妨设vl与vi-1相邻，2?j?k见下图，删除边(vi-1, vi )得回路(v1, vi ,…,vl, vi-1,…,v2, v1)。jjjjjl（3）由于l&n，所以G中必存在不在回路上的点。由G的连通性，存在回路外的点vx与回路上点vk相邻。删除边(vk-1, vk)得一路(vk-1, vk-2,…,v1, vi,…,vl-1, vl, vi-1,…, vk, vx)，这是一条比原来的路多一条边的新路，再对新的路重复(1)、(2)、(3)过程，直到全部节点扩充到路L中jj来，得到G中一条Hamilton路为止，证毕。此题还可以采用另外一种增加点的方法证明，请读者尝试。14.试说明下面彼得森图4.4.10是非Hamilton图。图4.4.10解：设彼德森图G是Hamilton图。令边集T={16,27,38,49,50}，则G-T是非连通图，所以G中任一条Hamilton回路必含T中偶数条边。容易看出，若G中某回路只含T中两条边，则该图必不是Hamilton回路。于是G中每一条Hamilton回路必含T中4条边。不妨设C是一条含27，38，49，50而不含16的Hamilton回路，则C必含边12，15，68，69。并且不含边23，45。由于点3和4在C中，所以边34必在C中，于是边集{34,49,96,68,83}构成一条回路且含在C中。这不可能，因而彼德森图G不是Hamilton图。15. 设图G有6个点，12条边，问能否肯定G为Hamilton图？若能，说明原因；若不能举一反例。试进一步讨论n个节点的图，边数最多的非Hamilton图是怎样的图？边数是多少？解：有6个点，12条边的图G一定是Hamilton图，可以证明当图G的边数=1/2(n-1)(n-2)+2时,G是Hamilton图，其中n是图G的点数。边数最多的非Hamilton图如下图，边数是1/2(n-1)(n-2)+1上图是有6个点11条边构成的非Hamilton图。事实上，我们有如下命题：设G是图，P(G)=n，L(G)=m，若m≥1/2(n-1)(n-2)+2，则Ｇ是Hamilton图。即n个点的边数最多的非Hamilton图是边数为 1/2(n-1)(n-2)+1的图。 证明：设Ｇ是非Hamilton图，由定理4.4.5知，Ｇ由某个Ｃm,n所度增大，于是Ｇ的边数≤Ｃm,n的边数。而Ｃm,n是非Hamilton图，所以当n给定边数最多的非Hamilton图必是某个Ｃm,n。下面证明在Ｃm,n中Ｃ1,n是边数最多的图。 对于给定的n，令f(m)=Cn-2m2+Cm2+Cn-2m1Cm1+Cm1Cm1其中Cuv表示u中取v的组合数，则f(m)表示图Ｃm,n的边数。于是
f(m)=1/2(n-2m)(n-2m-1)+1/2m(m-1)+(n-2m)m+m222=3/2m-(n-1/2)m+1/2(n-n) 从而f’(m)=3m-(n-1/2) 即，当1≤m≤1/3(n-1/2)时，f(m)单调递降，1/3(n-1/2)≤m≤(n-1)/2时单调递增。注意到，f(1)≥f((n-1)/2)，所以f(m)在[１，(n-1)/2]中的最大值在m＝１点取得。因此，对于给定的n，在Ｃm,n中Ｃ1,n是边数最多的图。又 f(1)=1/2(n-1)(n-2)+1，因此n个点的边数最多的非Hamilton图是边数为 1/2(n-1)(n-2)+1的图。16. 试证若允许转动骨牌，则砌平面问题无条件地可解。证明：对于任意张骨牌，我们可以任取一张形如图6-1-1所示的骨牌X。为可以翻转骨牌，我们可以由X得到形如图6-1-2所示的骨牌Y。从而得到图6-1-3所示2×2的正方形，显然可以无限地使用这个正方形进行堆砌，因此可以砌出整个平面。图6-1-1图6-1-217 若允许使用无限张骨牌，请举出一个能砌成第一象限，却砌不成整个平面的例子。 举例：现给出形如n≥0）的无限张骨牌可以由图6-2-1知，可以砌满第一图6-1-3象限，但是由于骨牌中没有形如 的骨牌，因此不能砌满整个平面。图6-2-11. 设W1、W2、W3分别为是模6的剩余类集合Z6的子集：W1={0，3}，W2={0，2，4}，W3={1，3，5}，试问剩余类加法是不是这些子集的二元代数运算？解：剩余类加法对W1，W2是二元代数运算，而W3不是。2. S={2| n?N}，加法是S上的二元代数运算吗？乘法呢？ 解：加法不是S上的二元代数运算，乘法是。3. 自然数集N 上的二元代数运算 * 定义为x * y = x，* 是否满足结合律？是否满足交换律？解：都不满足。4. 设 * 是集合S上的二元代数运算，且满足结合律，设x，y是S中任意元素，如果x * y = y * x，则x = y。试证明 * 满足等幂律。证明：由于对S中任意的x，y和z，有x*(y*z)=(x*y)*z，故x*(x*x)=(x*x)*x，于是有x*x=x。5. 设 + 和 * 是集合S上的两个二元代数运算，对于S中任意元素x和y，x + y = x。证明 * 对于 + 满足分配律。证明：设x，y和z是S中任意三个元素，则x*(y+z)=x*y=x*y+x*z，且(y+z)*x=y*x=y*x+z*x，故* 对于 + 满足分配律。6. 设（G， ?）是代数系统，则（G×G，*）是代数系统，这里G×G的运算“*”规定如下：（a，b）*（c，d）=（a?c，b?d）， 其中，a，b，c，d为G中任意元素。证明：当（G， ?）是半群时，（G×G，*）是半群；当（G， ?）有单位元素时，（G×G，*）有单位元素；当（G， ?）是群时，（G×G，*）是群；证明：设（G， ?）是半群，a，b，c，d，e，f为G中任意元素，若有(a，b),(c，d)，(e，f)属于G×G，则有(a，b)*((c，d)*(e，f))=(a，b)*(c?e，d?f)=(a?(c?e)，b?(d?f))=((a?c)?e，(b?d)?f))=((a?c)，(b?d))*(e，f)=((a，b)*(c，d))*(e，f)， 这就证明了当（G， ?）是半群时，（G×G，*）是半群。设（G， ?）有单位元素1，(a，b)是（G×G，*）中任意元素，则有(a，b)=(a?1，b?1)=(a，b)*(1，1)且(a，b)=(1?a，1?b)=(1，1)*(a，b)，故(1，1)就是（G×G，*）的单位元素。 设（G， ?）是群，1是群（G， ?）的单位元素，则由前面的证明知(1，1)就是（G×G，*）的1且（G×G，*）是半群。我们来证明（G×G，*）中的任意元素(a，b)有逆元素。(1，1)=(a?a’，b?b’ )=(a，b)*(a’，b’ )，其中a’和b’分别是a和b在群（G， ?）中的逆元素。同样有(1，1)=(a’?a，b’?b )=(a’，b )*(a，b )，这就证明了(a，b )是(a，b)的逆元素，从而说明（G×G，*）是群。7. 举例说明不要求可除条件而要求消去条件，即要求由aχ=ay可推出χ=y，由χ?a=y?a可推出χ=y，则G不见得是一个群，若G有限怎么样？解：例如，全体自然数在普通乘法下，适合消去律，但不是群。若G={a1，a2，?an}，用a右乘G中各元素得a1a，a2a，?，ana必不相同，否则若aia=aja (i?j) ，由消去条件有ai=aj，矛盾。对任意b?G，必有ai，使aia=b，因之方程xa=b有解。同理可知ay=b有解。故G是’’’yn离散数学答案 79_离散数学答案群。8. 举例说明定理6.2.2中的（1）@和（2）@分别改成：（1）@G中有一个元素1适合-1-11?a=a，（2）@对于任意a有一个a适合a?a=1，则G不见得是一个群。解：例如，a
a，b是实数 。0 01
，但G不是群
因当b?0时a
0而不难知道G中无1。9. 设集合G={a，b，c}上的二元运算表如下：则（G，?）是否为半群？是否为群？为什么？解：由于G非空且对任意的a，b属于G，有a?b 属于G，故（G，?）是代数系统。又由于?运算满足结合律，故（G，?）是半群，但（G，?）不是群，因为元素c没有逆元素。10. 计算（1 2 3）（2 3 4）（1 4）（2 3）。解：（1 2 3）（2 3 4）（1 4）（2 3）=（1 3）（2 4）。11. 用1，2，…，n代表M中元素。求证M的任意置换可以表为（1 2），（1 3），…，（1 n）的乘积。又可表为（1 2），（2 3），…，（n-1 n）的乘积。解：M的任意置换都可分为对换之乘积，又注意到：（ar as）=(1 ar)(1 as)(1 ar)，(ar，as?1)，而(1 ar)=(1 2)(2 3)…(ar-2 ar-1)(ar-1 ar)(ar-2 ar-1)…(2 3)(1 2)。12. 设?，?是两个置换。把?表示为不相杂的轮换的乘积。求证???-1只要用?变换?-1中文字。例如?=（1 2 3）。?=（1 2）（3 4）则???=（2 3）（1 4）。即按照?的变法把?中之1换成2，2换成3，3换成1，即得???。证明：若?=(a11 a12 …a1r)(a21… a2s)…(am1…amt)a11 …a1r a21…a2s…am1…amt而?
11 …b1r b21…b2s…bm1…b取典型元素bjk，我们有bjk???ajk???ajk?1???bjk?1??1-1-1??所以在???-1下，bjk?bjk+1。12. 试证明n 个元素的所有置换作成一个群（通常叫做n次对称群）。证明n个元素的所有偶置换作成群（叫做n次交代群）。写出四次交代群中的元素。n次交代群的元数为何？ 证明：只需验证满足群的各条件，略。注意到偶置换×偶置换=偶置换。易知偶置换成群。 A4：(1)，(1 2 3)，（1 3 2），（1 2 4），（1 4 2），（1 3 4），（1 4 3），（2 3 4），（2 4 3），（1 2）（3 4），（1 3）（2 4），（1 4）（2 3），12n!。14. （1）（1 2）（3 4），（1 3）（2 4），（1 2）（2 3）四个置换作成一个群叫klein四元群，求证klein四元群是四次对称群的正规子群。证明：用H记Klein四元群，对任??S4，??H，???－1只须用?变?中文字，不变轮换长度，结果仍是二对换之积，而这种乘积全在H中，故???－1?H，故?H?－1?H。15. 写出三次对称群的所有子群。 解：｛（1），（1 2），（1 3），（2 3），（1 2 3），（1 3 2）｝，｛（1），（1 2 3），（1 3 2）｝，｛（1），（1 2）｝， ｛（1），（1 3）｝， ｛（1），（2 3）｝， ｛（1）｝。16. 求证G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。证明：设G的任意多个子群的交为H。显然1?H。故H非空。若a，b?H，则a，b?各子群，故ab?各子群。ab?H。从而H是群。设任意多个正规子群的交为H。对任g?G，h?H，h?每个正规子群，故ghg-1?每个正规子群。ghg?H，所以gHg?H。17. 设H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合。求证HN是G的子群。证明：显然1?HN，NH非空。对任a，b?HN，可以有：a=h1n1，b= h2n2-1-1-1-1ab-1=h1n1(h2n2)-1=h1n1n2-1h2-1 =h1n1h2?n2?=h1h2?n1?n2??HN 由此推知HN是G的子群。18. 设H是群G的一个有限非空子集，求证只要H中任意两个元素的积仍在H内，则H是G的子群。证明：由子群的定义知，只要证按G中的乘法H是群即可。现在G中的消去律成立，当然按G中的乘法，消去律在H中也成立，又H有限，故H是群，所以H是G的子群。19. 求证循环群的子群仍是循环群。证明：若循环群G由其中元a生成。H是G的子群，但不是单位元群。则H中必含有幂m&0的元a。因为若m&0，a的逆元a也在H内，而-m&0。假定a是H中的最小正幂，显然H包含a的任意乘幂。假如又有H中任意元a，由S=tm+r。0≤r&m知ar=aS-tm=(aS)?(am)-t是H中元，但m最小。而0≤r&m，故r=0，因此有aS=(am)t这表明H中任意元aS也是am的乘幂，而知H为am生成的循环群。r20. 设G是一个n元循环群，a是一个生成元素。若r和n的最大约数为d。问a的周期等于什么？由此看来，G中有多少个元素可以作为生成元素？nrndnrrmm-mmmS证明：设e是G中的单位元，显然有(a)d?am，则m?rd?m…（1）。又(a)=e，即a=e得n?rm，则ndnmrmr?(a)d?ed?e。设a的周期为r?m。因(ndrnd?d)=1，所以drnd?m…(2)。由（1）和（2）知m=，即ar的周期为rnd。由此知G 中周期为n的元a必使d=1，而有(r，n)=1，故共有?（n）个元素可作为生成元。21. 求证若G的元数是一个质数，则G必是循环群。证明：设G的元数为质数P，任取G中非单位元a，则(a)是G的一个循环子群，设a的周期为r，则(a)的元数为r，因此r?P。但P是质数。显然r?1,故r=P，所以G=(a)，即G是由a生成的循环群。22. （1）设G是群，a∈G，试证明：若a的周期为2，
则a-1 = a。（2）设群G除了单位元以外每一个元素的周期均为2，试证明G是Abel群。 证明：（1）令1是G中的单位元素，则有1=a2，设a-1是a的逆元素，用其右乘等式两端有1a-1=a2a-1，得到a-1 = a。（2）首先由a2=1可得a-1 = a。设a，b是G中任意两个元素，有ab?G和(ab)2?G，因而ab=(ab)-1=b-1a-1=ba，所以G是Abel群。23. 设G是6元循环群，试找出G的所有生成元，并找出G的所有子群。解：设G={1,a，a2，a3，a4，a5}，由第9题容易证明a和a5是G的生成元，因为由第8题知循环群的子群仍是循环群，故用G的每个元素去生成群，即得G的子群，它们是{1}，&a&={1，a}，&a&={1，a，a}，以及G本身。24. 设K和H都是群G的子群，试证明：若H?K是G的子群，则K?H = H?K。 证明：对任意的k?h?K?H，(k?h)-1=h-1?k-1?H?K，由于H?K是G的子群，所以((k?h)-1)-1?H?K，因此K?H? H?K。同样，对于任意的h?k?H?K，(h?k)-1?H?K，即存在h1?H，k1?K使得(h?k)-1=h1?k1，所以h?k=(h1?k1)-1=k1?h1?K?H，因此H?K? K?H。由集合论知识知K?H = H?K。（有兴趣的读者可以证明本题的逆命题也成立）3322425. 设?是G到G’上的同态映射。?是G’到G”上同态映射，说明??是G到G”上的-1-1同态映射。并说明??的核为??(1”)，其中1”是G”的壹。证明：显然??是G到G”上的映射。对任意a?G，b?G，有?b(a?b)=?(?(a?b))=?(?(a)??(b))=?(?(a))??(?(b))=??(a)???(b)， 故??为同态映射。因此??是G到G”上的同态映射。1”在??下在G中原像集是??(1”)， ??(?-1?-1(1”))=I(1”)=1”，所以??的核为?-1?-1(1”)。26. 设?是G到G’上的同态映射。H是包含?的核N的G的正规子群。H’＝?（H），求证H’是G’的正规子群。并证明“第一同构定理”：GH?GH''-1-1。证明：显然H’是G’的子群。对任g’?G’，必有g?G，使?(g)=g’。所以由gHg-1?H，有?( gHg-1)= ?(g)?(H)?(g)-1??(H)=H’。所以g’H’g’-1?H’。这表明H’是G’的正规子群。因H’是G’的正规子群。故有同态映射?，使G’~GH''，其核为H’，1”为G'H'的壹。又在?下，G～G’，故在??下G～GHGH''同态核为??(1”)=?(H’)。因为H?N，所以?(H’)=H。-1-1-1-1故??的核为H，因此?G'H'.27. 设H和N都是G的正规子群。H?N由第一同构定理推出GH?G/NH/N。证明：因为N是G的正规子群，则有同态映射?使G～G/N，看?（H）在G/N中所有的象。注意到G/N中元是G中对N来看的陪集Na1,Na2,…,其中代表ai?G(i=1,2,…,)。因此H中任意元在G/N中的象也是N的陪集。代表元应取自上面属于H的各ai,可见H在G/N中的象正是H/N。根据第一同构定理，H/N是G/N的正规子群，并且G/H?G/NH/N。28. 设N是G的正规子群。H是G的任意子群。求证HNN?HH?N。证明：因N是G的正规子群，故有同态映射?，使G～G/N＝G’。在此映射下?（H）-1-1＝H’是G’的子群，而?(H’)=?(?(H))=HN。故?（HN）＝H’。即HN在?下的象是H’。所以在同态映射?下，HN～H’，同态核仍是N，故H’ ?HN/N。又在?下?（H）＝H’，所以H~H’。这个同态的核是N中所有属于H的元素，即H?N。H?N作为这个同态的核是正规子群，所以H’ ?H/H?N。由上便知HN/N?H/N?N。29. 试证明群G的所有自同构映射在映射的乘法下作成群。证明：由6.3节的知识容易验证群G的所有自同构映射在映射的乘法下是一个代数系统，并且满足结合律，其中的同一变换是单位元素。对任意的自同构映射σ?G，σ30. 设G是群，证明对?a?G,σa：x?axa-1（x?G）是G的自同构映射，称为G的内自同构映射。证明：不难证明σa是G到G的一个1-1映射。另外，对任意的g1，g2?G，因为σa(g1g2)=a (g1g2)a-1=(ag1a-1)(ag2a-1)=σa(g1)σa(g2)，所以σa是G的自同构映射。31. 试证明群G的所有内自同构映射在映射的乘法下作成群。证明：同一变换可表示成σ1，故此集合非空。对任意属于该集合的σx，σy，因为对任意的g?G，有σy(σx(g))= σy(xgx)=y（xgx）y=(yx) g(yx)= σyx (g)，所以此集合在乘法运算下是封闭的。显然该集合在乘法运算下满足结合律。该集合内有单位元素σ1，容易验证σ-1x =σx-1在该集合中。32. 设G是一个循环群，N是G的一个子群，试证明G/N也是循环群。 证明：由G为循环群知，G一定是交换群，故N是正规子群，G/N有意义。 设G=(a)，则任取G/N中元素bN，其中b∈G，故b=ak，因此kkbN=aN=（aN），33. 证明f：x→x是群G的一个自同构映射当且仅当G是交换群，其中x∈G。 证明：（必要性）任取a,b∈G，则ab=f(a-1) f(b-1)=f(a-1b-1)=(a-1b-1)-1 =ba。 故G为交换群。（充分性）（a）显然f是G到G上的1-1映射。（b）任取a，b∈G，由G为交换群知，ab=ba。于是，f(ab)= (ab)-1 = (ba)-1 = a-1b-1= f(a)f(b)。 因此，f是G到G的同态映射。由(a),(b)知，f是群G的自同构映射。-1-1-1－1-1?G。-134. 试证明元数为pm的群一定包含一个元数是p的子群，其中p为质数，m≥1。 证明：设G为元数为pm的群，任取G中一非单位元的元素a，则a的周期n一定整除离散数学答案 79_离散数学答案p，且n≠1,不妨设n= p,k≥1。若k=1，则a的周期为p，(a)即为元数为p的G的子群。若k&1，则取b=a35. 求证任意无零因子的有限环必是一个体。假定环中不只有一个元素。证明：因若ax=ay,则a(x-y)=0，无零因子故，若a?0必x-y=0，x=y，由此不难推知，无零因子的有限环中消去律成立。又有限元，所以环中非零元做成乘法群因而是体。36. 设R是有1的环，a∈R有右逆，试证明下述条件等价：（1）a至少有两个右逆。（2）a无左逆。（3）a是左零因子，即存在非零元素b∈R，有ab=0。证明：（1）=&（2）。设a＇和a＇＇为a的两个不同的右逆元，往证a无左逆元。 （用反证法）假设a有左逆元a1，则a1= a1(a a＇)= (a1a)a＇=a＇,a1= a1(a a＇＇)= (a1a)a＇＇=a＇＇,故a＇=a＇＇,这与a＇≠a＇＇矛盾，因此原假设不对，a无左逆元。（2）=&（3）。由a无左逆元知，a＇a≠1，即a＇a - 1≠0，其中a＇为a的右逆元。而a(a＇a - 1)= (aa＇)a - a = a-a=0，故a为左零因子。（3）=&（1）。设a＇为a的右逆元，则a a＇=1。由a是左零因子知，G中存在非零元素b有，ab=0。所以，a( b + a＇)=1。因此，a至少有两个右逆元a＇和b + a＇。37. 若环（L，+，×）对×运算满足等幂律，即对R中任意元素a，都有a×a=a，证明：（1）对R中任意元素a，有a + a = 0。（2）R是交换环。证明：（1）一方面，（a + b）×（a + b）=(a×a)+(a×b)+(b×a)+(b×b)=a+(a×b)+(b×a)+b另一方面，由题设知，（a + b）×（a + b）=a+b所以，a+(a×b)+(b×a)+b=a+b，即，(a×b)+(b×a) = 0 ??(*)。在（*）式中取a=b，则(a×a)+(a×a) = 0，故a+a=0。（2） 由（1）的结论知，(a×b)+(a×b) = 0，而由（*）式又知，(a×b)+(b×a) = 0，因此， pk?1mk，显然b的周期为p，故(b)是一个元数为p的G的子群。 因此，元数为pm的群一定包含一个元数是p的子群，其中p为质数，m≥1。(a×b)+(a×b)=(a×b)+(b×a)，即，a×b= b×a，故R是交换环。38. 试证明一个至少有两个元素而没有零因子的有限环R是一个体。证明：只需证明若去掉0，R的其余元素构成的集合R★做成乘法群。(1)由R中无零因子知，R对乘法封闭。★(2)乘法对R元素适合结合律，对R的元素当然也适合。(3)由于R无零因子，所以消去律对R★的元成立。综上，又由R有限知，R做成乘法群。因此，R是一个体。39. 设K是一个体。而K同态于R。求证：R或只有一个元素0或和K同构。证明：设此同态映射为?，则?或为一对一映射，或为多对一映射。若?为一对一映射，则R与K同构；若?为多对一映射，往往R只有一个元素，事实上，在K中可取到不同的二个元素a,b，而?(a)=?(b)，于是对C=a-b?0,有?（C）＝0，因C?K，故有逆C，CC－1＝1，所以，?(1)=?(CC-1)=?(C)?(C-1)，?(C-1)=0。从而对任意x?K有?(x)=?(x?1)=?(x)??(1)=0，可见，任意元均映射成0。故R或只有一个元素0或和K同构。40. 列举I/12I的所有理想。解： {0,1,2,3,4,5,6,7,8,9,10,11}; {0,2,4,6,8,10}; {0,3,6,9};{0,4,8}; {0,6};{0}41. 设F是一个域。求证：多项式环F(x,y)中所有常数项为0的多项同式作成一个理想，不是主理想。证明：设所有常数项为0的多项式集合为N。(1)若f,g ?N,则f-g常数项仍为0，故f-g ?N(2)取 f?N，任取g?F(x,y)，则g?f常数项仍为0，故g?f?N。因而N为理想。现证N不是主理想，因若不然，可设N=f(x,y)F(x,y)。因x?N，y?N，则必存在r,S?F(x,y)使得x=f(x,y)?ry=f(x,y)?S由上式得：
r=x或f(x,y)=x
f(x,y)=1 －1★★★若f(x,y)=1则N=f(x,y)?F(x,y)=F(x,y)矛盾。若f(x,y)=x代入下式得y=f(x,y)?S得y=x?S而S=因而S?F(x,y)矛盾。故N不是主理想。yx42. A，B是理想N在环R中的两个剩余类。命P为所有ab的集合，a?A,b?B，则自然P?AB，举例说明P不见得等于AB。解：对整数环I，取理想5I，I/5I={0,1,2,3,4}令A=0={0，5，10，…，}，B=2={2，7，12，…}不难验证，5?AB，故P?AB。43. 设?是R到R?上面的同态映射，N是R?的理想，求证：?(N)是R的理想。证明：对任a,b??-1(N)，则?(a) ?N,?(b) ?N，故[?(a)-?(b)] ?N，从而?(a-b)=[?(a)-?(b)] ?N这表明：(a-b) ??-1(N)。再取任意a??-1(N)，x?R，?(ax)=?(a)??(x) ?(a) ?N,?(x) ?R’,故?(a)?(x) ?N，这表明ax??-1(N)。同理：xa??-1(N)，故?-1(N)是R的理想。44. 试证明两个理想的交集仍是理想。证明：设A和B是环R的两个理想，因为0?A且0?B，故0?A?B，即A?B非空。对任意的x，y ?A?B，有x，y?A，而A是R的理想，故x-y?A，同理有x-y? B。于是x-y?A?B。 对任意的x?A?B，r?R，有x?A，r?R，而A是R的理想，故xr?A，rx?A。同理又有xr?B，rx?B，于是xr?A?B，rx?A?B。-1第八章 格与布尔代数1. 设S是所有命题做成的集合，说明S在什么运算下做成代数格？在什么部分序下做成半序格。解：S在合取运算(?)和析取运算(?)下做成代数格。不难验证这两种运算有交换律、结合律、吸收律。S在蕴涵(?)这个部分序下做成半序格。A?B?A?B=A且A?B=B.2. 设(L，?，)是一个格，a,b?L。令S={x|(x?L)?(a?x?b)}其中?是与(L,?, )等价的半序格中的部分序。证明：(S, ?，)是L的子格。设c，d?S,则c,d?L，且a?c,d?b所以 a?c*d 而显然有c*d?bcd?b
a?cd故S对*，运算封闭即(S，*，)是L的子格。3. 设D是集合S上的整除关系。以下部分序集是否为格：(1) S = {1，2，3，4，6，12}(2) S = {1，2，3，4，6，8，10，12}(3) S = {1，2，3，4，5，6，7，8，9，10}(4) S = {2，3，6，12，24，36}解：（1）和（4）是格。4. 设(L，?)是格，若a,b,c?L,a?b?c，则ab=b*c(a*b)(b*c)=(ab)*(ac)证明：因a?b?c故ab=b=b*c
a*b=a,b*c=b,ab=b,ac=c故(a*b)(b*c)=(ab)=b
(ab)*(ac)=b*c=b即(a*b)(b*c)=(ab)*(ac).5 设(L,?)是格，若a ?b,c?d,a,b,c,d?L,则a?c?b*d
ac?bd证明：(a*c)*(b*d)=a*c*b*d=(a*b)*(c*d)=(a*c)故a*c?b*d,(ac)(bd)=acbd=(ab)(cd)=bd,故ac?bd.6
设(L，?)是一个格。证明：(a*b) (c*d)?(ac)*(bd);(a*b) (b*c)(c*a)?(ab)*(bc)*(ca)证明：(a*b) (c*d)?[(a*b) (c)]*[(a*b) d]]?(ac)*(bc) (ad)*(bd)?[(ac)*(ad)]*[(bd)*(bc)]?(ac)*(bd)(a*b) (b*c)(c*a)?[((a*b) ((a*b)c))(c*a)=[b*((a*b) c)](c*a)?[(b*((a*b) c))c]*[(b*(a*b)c)a]?[(bc)*((a*b)c)c])]*(ba)*[((a*b)c)a]=[(bc)*(a((a*bc)))*(ab)*[(a*b)c]?(bc)*(ab)*(ac)*(bc)=(ab)*(bc)*(ca)7. 若(L，?)是有限格，则L中必有最大最小元素。证明：L有限，可设L={a1,a2,…,an}与其等价的代数格记为(L，*，),则a=a1*a2*…*anL
b=a1a2?anL不难看出，对任ai?L，有a?ai?b，即L中最大最小元素分别为a,b。8. 令S={所有正偶数集合}。证明：(I+，D)与(S，D)同构。证明：对任意n?I+，规定I+到S的映射：g:n?2n显然此映射是一对一的。与这两个格等价的代数格的*，运算都是求最大公因和最小公倍。对任n1,n2?I+,n1*n2为其最大公因，记为d.而2n1,2n2?S,2n1*2n2为2n1和2n2的最大公因。为2d 。故g(n1*n2)=g(d)=2d=2n1*2n2=g(n1)*g(n2).同理可证g(n1n2)=g(n1)g(n2)即g是同态映射，故(I+，D)和(S，D)同构。9. 证明：4个元素的格(L，*，)必同构于格(I4，?)或者格(S6，D)。证明：设4个元素的格L={a1,a2,a3,a4}，L有限，故必有最大，最小元素，不妨设为a4,a1,则a1?a2,a3?a4。其中，a2,a3有两种可能：(1)a2?a3(a2,a3有关系?，不妨设为如此)则成为链，因此与(I4，?)同构。(2)a2,a3没有?关系，则此格与(S6，D)同构.10. 证明：格(E，?)和格(O，?)同枸。其中，E是正偶数集。O是正奇数集。?是数的小于等于关系，给出的同构映射是否格(E，D)和格(O，D)之间的同构映射？其中D是整除关系。证明：规定(E，?)到(O，?)上的映射g:m?m-1，m?E。这显然是一对一的。与这两格等价的代数格的*，?运算即求两个数中最大，最小者的运算。对任m1,m2?E，不妨设m1?m2有
g(m1*m2)=g(m1)=m1-1= (m1-1)*(m2-1)=g(m1)*g(m2)g(m1?m2)=g(m2)=m2-1=(m1-1) ?(m2-1)=g(m1) ?g(m2)因此格(E，?)和格(O，?)同构。此映射不是关于(E，D)和(O，D)的同构映射。例：在该映射中6?5，12?11，而与(E，D)和(O，D)等价的代数格中的乘加运算分别是求最大公因和最小公倍的运算。若记两格中的乘运算分别为*1和*2。则有g(6*112)=g(6)=5，而g(6)*2g(12)=5*211=1，因此，g不是关于(E，D)和(O，D)的同构映射。11. 设(L，*，?)，(S，?，?)是两个格，证明：若g是L到S上的一一映射，则g是同构映射的充要条件是g与g-1是保序映射。证明：?)若g是L到S上的同构映射，则显然g-1存在并且是S到L上的同构映射，而同构映射当然是同态故保序。?)设a,b?L,a’,b’?S且有g(a)=a’，g(b)=b’,a*b=c,a’?b’=c’，则c?a,c?b。由g是保序的，所以g(c )?’a’,g( c)?’b’，因此g(c)?’(a’?b’)，即g(c)?’c’。由a’?b’=c’，我们又得到c’?’a’ c’?’b’。由g-1是保序的，得g-1( c’)?a,g-1(c’)?b。于是gg-1( c’)?’g(c)，所以c’=g (c)，即c’?g (c)。所以c’=g(c)，即g(a*b)=g(c)=c’=a’?b’=g(a) ? g(b)。同理可得，g(a?b)=g(a)?g(b).故g是同构映射。12. 设(L，*，?)是有限格，g是L到L的映射。如果对a,b?L，有g(a*b)=g(a)*g(b)，则必有e?L,使得g(e)=e。证明： 由g(a*b)=g(a)*g(b)，不难推得对任m有g(a1*a2*?*am)=g(a1)*g(a2)*?*g(am)。取L中任一元，记为a1,g(a1)=a2,若a2=a1,则取e=a1，得证.否则,令a3=g(a2)，如此下去，必有两种可能:(Ⅰ)对某个j出现g(aj)=aj(1?j?n),则e=a，j得证。(Ⅱ)g(aj)=ai其中1?i?j.因此,令e=ai*ai+1*?*ajg(e)=g(ai*ai+1*?*aj)=g(ai)*g(ai+1)*?*g(aj)=ai+1*ai+2*?*aj*ai=e离散数学答案 79_离散数学答案原命题成立。13．证明：在有余分配格（L，×，?）中，对任意a，b∈L，有a≤b?a×b′= 0b′≤a′?a′?b= 1a≤b?b′≤a′证明：①a?b?a?b’=0?)∵a≤b， ∴a?b=a，∴a?b’=(a?b)?b’=a?(b?b’)=a?0=a?)a?b=(a?b)?0=(a?b)?(a?b’)=a?(b+b’)=a?1=a故a?b②?)∵b’?a’， ∴b’?a’=a’，∴a’?b=(b’?a’)?b=a’?(b’?b)=a?1=1?)a’?b’=(a’?b’)?1=(a’?b’)?(a’?b’)=a’?(b’?b)=a’?0=a’∴b’?a’。③a?b?b’?a’a?b?a?b=a?a’?b’=a’?b’?a’14．设（L，×，?）为模格，试证明若有（a?b） ×c = b×c则有
（c?b）×a = b×a。证明：一方面，由c?b≥b知，(c?b)×a≥b×a。另一方面,(c?b)×a≤(c?b)×(a?b)由（L，×，?）为模格，且b≤a?b，知(a?b)×(b?c) = b?((a?b)×c)而(a?b)×(b?c)= (c?b)×(a?b)，且由已知，（a?b）×c = b×c，得：(c?b)×a≤(c?b)×(a?b)=(a?b)×(b?c)= b?((a?b)×c)= b?(b×c)=b，因此,(c?b)×a≤b，又显然，(c?b)×a≤a，因此，(c?b)×a≤b×a。综上(c?b)×a=b×a.15.设(B，?，+，-，0，1)是布尔代数，定义B上两种代数运算如下： a?b=a?b?a?ba×b=a?b于是，称代数(B，×, ?)为布尔环。证明：在布尔环中，有如下性质： ①a?a=0a+a?a=0+0=0 a?a=a?②a?0=aa?0=a?0=a?1+0=a+0=a 0+a?③a?1=aa?1=a?1=a?0+a?1=0+a=a 1+a?④a×(b?c)=(a×b) ?(a×c)a×(b?c)=a?(b?+?c)=a?b?+a??c)(a×b) ?(a×c)=(a?b) ?(a?c)=(a?b)?(a?c)⑤a=b?a?b=0?
a?b=a?a=0?
∵ a?b=0∴ a?b=0 b+a?∴ a=a?1+0=a?(b+b)+a?b b+a?=a?b+a?b=(a?b+a?b)+a?b+a?b =(a+a)?b+a?b=b+a?bb+ab)=a?b+0=a?b 故a×(a?b)=a?(a?又a×(a?b)=a×0=0⑥a?b=a?ba?b?a?b?a?b?a?b?a?b?a?b ⑦(a?b)?a?b=a?b(a?b)?a?b?a?b)?(a?b)?(a?b)?(a?b)?(a?b)?c?a?a?b?b?a?b?b =0+a?b?a?b?0?a?b?a?ba?b?a?b?a?ba?b?a?b?a?b?a?b?a?b故(a?b?a?b?a?b⑧若a×b=0,则a?b=a+ba?b=a?b?a?b?0?a?b?a?b?a?b?a?b?a?b?a?b?a?b?a?b?(a?b?a?b)?(a?b?a?b)?a?(b?b)?(a?a)?b?a?b⑨若a?c=b，则a=b由有：(a?c)?(b?c)=0即a?c?b?c=(a?b)?(c?c)=a?b?c=a?b=0再由因a?b=0, ∴a=b.16. 在布尔代数中，证明下列等式：1)
a?a?b?a?b?a?a?b?(a?a?b)?a?b?a?(a?b?a?b)?a?(a?a)?b?a?b2)
a?(a?b)?a?ba?(a?b)?a?a?a?b?0?a?b?a?b3)4) a?b?a?b?aa?b?a?b?a?(b?b)?a?1?a(a?b)?(a?b)?a(a?b)?(a?b)?(a?b)?a?(a?b)?b?a?b?a?a?b?a?(a?b?a?b)?0?a?a?a17. 试举出满足下列条件的例子：（1）是部分序集，但不是格。（2）是有界格，但不是有余格。（3）是有余格，但不是分配格。（4）是模格，但不是分配格。（5）是分配格，但不是布尔代数。解：（1）设D是S上的整除关系，则集合S = {1，2，3，4，6，8，10，12} S = {1，2，3，4，5，6，7，8，9，10}是部分序关系但不是格。（2）下图(a)是一个有界格，但不是有余格，因为x1，x2都无余元素。xx2
(d)(3)图(b)是有余格，但不是分配格。(4)图(c)是模格，但不是分配格。欢迎您转载分享：
更多精彩：