离散数学证明题专项训练
——09软件班
1 设群具幺元e果G意元素a
a²e交换群
证明：条件意ab
外
两边时左右利结合律
交换群
2．试证明：
证明
(1) S CP规
(2) ØSÚP P
(3) P (1)(2)析取三段
(4) P®(Q®R) P
(5)Q®R (3)(4)假言推理
(6)Q P
(7)R (5)(6)假言推理
3设 AB两集合证明 A—BA仅A∩B ø
证明：A—BA
A∩~BA
>A∩~B∩BA∩B
>A∩B ø
A∩B ø
>(A∩B)∪~B~B
>A∪~B~B
>A∩(A∪~B)A∩~B
>A∪(A∩~B)AB
>AAB
4 设RS非空集合A二元关系称证明：RoS具称性仅 RoSSoR
证明：
1）必性
意∈RoS
<>RoS
<>存z(∈S ∧∈R)
<>存z(∈S ∧∈R)
<>∈SoR
RoSSoR
2)充分性
意∈RoS
<>∈SoR
<>存z(∈R ∧∈S)
<>存z(∈S ∧∈R)
<>∈RoS
：RoS具称性
5（7分）A{(00)(01)(10)(13)(22)(23)(31)}
R{<(ab)(cd)>| (ab)(cd)Aa+bc+d }
(1)证明：RA等价关系．
(2)出R确定A划分(分类)
5证明：（1）（5分）
反性 反性成立
称性
称性成立
传递性
传递性成立
（2）AR{{(00)}{(01)(10)}{(13)(22)(31)}{(23)}}
6（6分）设群
证明SG子群
6证明：（步2分）
（1）S空：群设单位元
S空
（2）
（3）
SG子群
7（15分）设函数g：A→Bf：B→C
(1)fog满射f满射
(2)fog单射g单射
证明 g：A→Bf：B→C定理55知fogAC函数
(1)意z∈Cfog满射存x∈Afog(x)＝zf(g(x))＝zg：A→B知g(x)∈By＝g(x)∈Bf(y)＝zf满射
(2)意x1x2∈Ax1≠x2fog单射fog(x1)≠fog(x2)f(g(x1))≠f(g(x2))必g(x1)≠g(x2)g单射
8（15分）设R集合A具传递反性质关系TA关系ÎTÛÎRÎR证明T等价关系
证明 R反意a∈A∈RT定义∈TT反
∈T∈R∈R∈R∈R∈TT称
∈T∈T∈R∈R∈R∈RR传递∈R∈R∈R∈R∈R∈R∈R∈R∈TT传递
9（15分）群HG非空子集子群Û意ab∈Ha*b－1∈H
证明 必性：意ab∈H子群必b－1∈Ha*b－1∈H
充分性：H非空必存a∈He＝a*a－1∈H
取a∈Hea∈Ha－1＝e*a－1∈H
意ab∈Ha*b＝a*(b－1)－1∈Ha*b∈H
HG非空子集*H满足结合律
综知子群
10 (6分) G群 HG子群 ∀g1g2∊G (g1g2) ∊R Û g1g21 ∊H 证明RG等价关系
证明 ◆意a∊G∵ a·a1e∊H
∴ (aa) ∊ RR反
◆意ab∊G(ab) ∊ R
∴ a·b1∊H∴(a·b1)1b·a1∊H
∴ (ba) ∊ RR称
◆意abc∊G(ab) ∊ R(bc) ∊ R
∴ a·b1∊H b·c1∊H
∴ (a·b1)·(b·c1)a·c1∊H
∴ (ac) ∊ RR传递
11 已知 f A→B g B→C f单射g单射证明g∘f 单射 g∘f满射证明g满射
证明 (1) 意x1x2∊A g∘f (x1) g∘f (x2) g(f(x1)) g(f(x2))
g单射f(x1)f(x2) f单射x1x2 g∘f 单射
(2) 意z∊C 存x∊A
g∘f (x)z g(f(x))z 存 yf(x) ∊B g(y)z g满射
12 (8分) (G ·)群取定u ∊ G ∀g1g2∊G定义：
g1*g2 g1·u1·g2 证明 (G*)群
证明 (1) 封闭性 (2) 结合性 (3) 幺元 e*u
事实 g*e*g*ug·u1·ug·eg
e**gu*gu·u1·ge·gg
(4) 逆元
∀g∊G 代数运算*逆元记g*1
g*1u·g1·u 里 g1代数运算·逆元
13 已知(G *)(A △)两群f G→A群态
证明 (1) f(eG)eA (eG ÎG幺元 eA ÎA幺元)
(2) ∀g∊G f(g1)(f(g))1
证明 (1) f(eG＊eG)＝f(eG)
f(eG＊eG)＝f(eG) △ f(eG)
f(eG) △ f(eG)＝f(eG*eG) ＝f(eG)＝f(eG)△eA
根群左消律 f (eG) ＝ eA
(2) 意g∊Gf(g*g1)＝f(g) △ f(g1)
f(g*g1)＝f(eG)＝eA
f(g) △ f(g1)＝eA ＝ f(g) △(f(g))1
左消律f(g1) ＝ (f(g))1
14设代数系统*R二元运算0幺元独异点（10分）
+·R封闭*R封闭
〈R*〉独异点
15设半群e左幺元
群（10分）
（1）
(2) e幺元
事实：e左幺元现证e右幺元
（3）
（2）（3）知：群
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
——09软件班
1 设
a²e
证明：条件意ab
外
两边时左右利结合律
2．试证明：
证明
(1) S CP规
(2) ØSÚP P
(3) P (1)(2)析取三段
(4) P®(Q®R) P
(5)Q®R (3)(4)假言推理
(6)Q P
(7)R (5)(6)假言推理
3设 AB两集合证明 A—BA仅A∩B ø
证明：A—BA
A∩~BA
>A∩~B∩BA∩B
>A∩B ø
A∩B ø
>(A∩B)∪~B~B
>A∪~B~B
>A∩(A∪~B)A∩~B
>A∪(A∩~B)AB
>AAB
4 设RS非空集合A二元关系称证明：RoS具称性仅 RoSSoR
证明：
1）必性
意
<>
<>存z(
<>存z(
<>
RoSSoR
2)充分性
意
<>
<>存z(
<>存z(
<>
：RoS具称性
5（7分）A{(00)(01)(10)(13)(22)(23)(31)}
R{<(ab)(cd)>| (ab)(cd)Aa+bc+d }
(1)证明：RA等价关系．
(2)出R确定A划分(分类)
5证明：（1）（5分）
反性 反性成立
称性
称性成立
传递性
传递性成立
（2）AR{{(00)}{(01)(10)}{(13)(22)(31)}{(23)}}
6（6分）设群
证明SG子群
6证明：（步2分）
（1）S空：群设单位元
S空
（2）
（3）
SG子群
7（15分）设函数g：A→Bf：B→C
(1)fog满射f满射
(2)fog单射g单射
证明 g：A→Bf：B→C定理55知fogAC函数
(1)意z∈Cfog满射存x∈Afog(x)＝zf(g(x))＝zg：A→B知g(x)∈By＝g(x)∈Bf(y)＝zf满射
(2)意x1x2∈Ax1≠x2fog单射fog(x1)≠fog(x2)f(g(x1))≠f(g(x2))必g(x1)≠g(x2)g单射
8（15分）设R集合A具传递反性质关系TA关系
证明 R反意a∈A
9（15分）
证明 必性：意ab∈H
充分性：H非空必存a∈He＝a*a－1∈H
取a∈Hea∈Ha－1＝e*a－1∈H
意ab∈Ha*b＝a*(b－1)－1∈Ha*b∈H
HG非空子集*H满足结合律
综知
10 (6分) G群 HG子群 ∀g1g2∊G (g1g2) ∊R Û g1g21 ∊H 证明RG等价关系
证明 ◆意a∊G∵ a·a1e∊H
∴ (aa) ∊ RR反
◆意ab∊G(ab) ∊ R
∴ a·b1∊H∴(a·b1)1b·a1∊H
∴ (ba) ∊ RR称
◆意abc∊G(ab) ∊ R(bc) ∊ R
∴ a·b1∊H b·c1∊H
∴ (a·b1)·(b·c1)a·c1∊H
∴ (ac) ∊ RR传递
11 已知 f A→B g B→C f单射g单射证明g∘f 单射 g∘f满射证明g满射
证明 (1) 意x1x2∊A g∘f (x1) g∘f (x2) g(f(x1)) g(f(x2))
g单射f(x1)f(x2) f单射x1x2 g∘f 单射
(2) 意z∊C 存x∊A
g∘f (x)z g(f(x))z 存 yf(x) ∊B g(y)z g满射
12 (8分) (G ·)群取定u ∊ G ∀g1g2∊G定义：
g1*g2 g1·u1·g2 证明 (G*)群
证明 (1) 封闭性 (2) 结合性 (3) 幺元 e*u
事实 g*e*g*ug·u1·ug·eg
e**gu*gu·u1·ge·gg
(4) 逆元
∀g∊G 代数运算*逆元记g*1
g*1u·g1·u 里 g1代数运算·逆元
13 已知(G *)(A △)两群f G→A群态
证明 (1) f(eG)eA (eG ÎG幺元 eA ÎA幺元)
(2) ∀g∊G f(g1)(f(g))1
证明 (1) f(eG＊eG)＝f(eG)
f(eG＊eG)＝f(eG) △ f(eG)
f(eG) △ f(eG)＝f(eG*eG) ＝f(eG)＝f(eG)△eA
根群左消律 f (eG) ＝ eA
(2) 意g∊Gf(g*g1)＝f(g) △ f(g1)
f(g*g1)＝f(eG)＝eA
f(g) △ f(g1)＝eA ＝ f(g) △(f(g))1
左消律f(g1) ＝ (f(g))1
14设
+·R封闭*R封闭
〈R*〉独异点
15设
群（10分）
（1）
(2) e
事实：e左幺元现证e右幺元
（3）
（2）（3）知：
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
