第四章 二元關系和函數

4.

A={1,2,3}

恒等關系

IA={<1,1>,<2,2>,<3,3>}I_A=\{ <1,1>,<2,2>,<3,3>\}IA?={<1,1>,<2,2>,<3,3>}

全域關系EA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}E_A=\{<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>\}EA?={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}

小于等于關系

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}L_A=\{<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>\}LA?={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

整除關系

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}D_A=\{<1,1>,<1,2>,<1,3>,<2,2>,<3,3>\}DA?={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

6.2

A={1,2,4,6}，列出R

R={(x,y)|x,y$\in$A$\wedge$ |x-y|=1}

R={<1,2>,<2,1>}R=\{<1,2>,<2,1>\}R={<1,2>,<2,1>}

9

R={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>,<2,3>}R=\{<0,1>,<0,2>,<0,3>,<1,2>,<1,3>,<2,3>\}R={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>,<2,3>}

求R$°$R，$R^{?1}$

R°R={<0,2>,<0,3>,<0,3>,<1,3>}R\circ R=\{<0,2>,<0,3>,<0,3>,<1,3>\}R°R={<0,2>,<0,3>,<0,3>,<1,3>}

R?1={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}R^{-1}=\{<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>\}R?1={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>}

11

設A={1,2...10}A=\{1,2...10\}A={1,2...10}

R={<x,y>∣x,y∈A∧x+y=10}R=\{<x,y>|x,y\in A\wedge x+y=10 \}R={<x,y>∣x,y∈A∧x+y=10}

對稱性，非自反性(含$<5,5>$)

12

關系圖：

關系矩陣：
$$\left[\begin{array}{ccccc}& 0& 1& 2& 3\\ 0& 1& 0& 0& 1\\ 1& 0& 0& 0& 0\\ 2& 1& 1& 0& 1\\ 3& 0& 0& 1& 0\end{array}\right]$$

16

$ 自反閉包：r?=R\cup R^0$

$對稱閉包:s(R)=R\cup R^{?1}$

$傳遞閉包:t(R)=R\cup R^2\cup ...$

18.1

是$Z^{+}$ 的劃分

1. $?$ $\notin$ $\pi$

2. S1，S2不交

3. S2=$Z^{+}$-S1=$Z^{+}$$\cap$ ~S1

   S1$\cup$S2=($Z^{+}$$\cap$~S1)$\cup$S1=($Z^{+}$$\cup$ S1)$\cap$(~S1$\cup$S1)=$Z^{+}$

20.2

22.1

極大元：e

極小元：a

最大元：e

最小元：a

23

藍色圈住的地方為B

上界：12

下屆：1

最小上屆：12

最大下屆：1

28

回答是否為滿射、單射、雙射。若為雙射，求反函數。求A在f下的像f(A)

為滿射，單射，雙射。

反函數為$f(x{)}^{?1}=<x,x?1>$

f(A)=6

非滿射，非單射。

f(A)={1,2}

非滿射，為單射

f(A)={1,$\frac{2}{3}$}

34

(1)

g$°$f=f(g(x))=f(x+4)=$(x+4{)}^2?2$

f$°$g=g(f(x))=g($x^2$-2)=$x^2$+2

(2)

g$°$f非單射，非滿射，非雙射

g$°$f非單射，非滿射，非雙射

(3)

g,h有反函數

$g(x{)}^{?1}$=x-4

$h(x{)}^{?1}$=$(x+1{)}^{\frac{1}{3}}$

第五章 代數系統(tǒng)的一般概念

2判斷二元運算是否封閉

(2) 封閉

(4) 封閉

(8) 封閉

3

(2)不符合交換律、適合結合律。不符合分配律，分配律是兩個二元運算之間的

(4) 不符合交換律，符合結合律。不符合分配律，分配律是兩個二元運算之間的

(8) 適合交換律、結合律。符合分配律，乘法對加法適合分配律

4

(2) 無單位元（僅右單位元1），無零元，顯然可得，無逆元

(4) 單位元為nxn的單位矩陣，零元為nxn的零矩陣。有逆矩陣的矩陣A的逆元為$A^{?1}$

(8) 加法：無單位元，無零元，顯然可得，無逆元 //乘法：單位元為1,無零元，無逆元

8

(1)

1. 滿足交換律：*、 $°$、$?$
2. 滿足結合律：*、$°$、$?$ 、$\square$
3. 冪等：$\square$

(2)

*：沒有單位元，零元為a，無逆元

$°$： 單位元為a，無零元，a的逆元為a，b的逆元為b

$?$ ：無單位元，無零元，無逆元

$\square$： 無單位元(左單位元為a)，無零元(右零元為b)，無逆元

11

(2) S2構成V的子代數，S2對+,$?$ 都是封閉的

12

設V1=({1,2,3},°，1)，其中x°y表示取x和y之中較大的數，V2=({5,6},*,6),其中x*y表示取x和y之中較小的數.

(1) 求出V1的所有子代數，其中哪些是平凡的子代數？哪些是真子代數？

(2)求積代數y,×y,給出積代數(V,×V,·,)的運算表和代數常數k,并說明k是什么特異元素

(1)

子代數系統(tǒng)的B的條件：

1. B$?$S
2. B$\notin$ $?$
3. B和S含有相同的子代數常數
4. B對V中所有運算封閉

1為單位元

B1={1},B2={1,2},B3={1,3},B4={1,2,3}

其中平凡子代數為：B1,B4

真子代數為：B2,B3

(2)

設$V_1\times V_2=<S1\times S2,?,k>$

S1×S2={<1,5>,<1,6>,<2,5>,<2,6>,<3,5>,<3.6>}S_1\times S_2=\{<1,5>,<1,6>,<2,5>,<2,6>,<3,5>,<3.6>\}S1?×S2?={<1,5>,<1,6>,<2,5>,<2,6>,<3,5>,<3.6>}

$<x_1,y_1>,<x_2,y_2>\in S_1\times S_2$

$<x_1,y_1>?<x_2,y_2>=<x1°x_2,y_1?y_2>$

運算表：
$$\left[\begin{array}{ccccccc}& <1,5>& <1,6>& <2,5>& <2,6>& <3,5>& <3.6>\\ <1,5>& <1,5>& <1,5>& <2,5>& <2,5>& <3,5>& <3,5>\\ <1,6>& <1,5>& <1,6>& <2,5>& <2,6>& <3,5>& <3,6>\\ <2,5>& <2,5>& <2,5>& <2,5>& <2,5>& <3,5>& <3,5>\\ <2,6>& <2,5>& <2,6>& <2,5>& <2,6>& <3,5>& <3,6>\\ <3,5>& <3,5>& <3,5>& <3,5>& <3,5>& <3,5>& <3,5>\\ <3,6>& <3,5>& <3,6>& <3,5>& <3,6>& <3,5>& <3,6>\end{array}\right]$$
$k=<1,6>$

k是單位元

14

$$\begin{gathered} 若\psi 為V_1到V_2的同態(tài) \\ V1=<S_1,°>(V{)}_2=<S_2,?> \\ 則\psi (x°y)=\psi (x)?\psi (y) \\ 普通加法和矩陣加法 \\ \psi (a)=\left[\begin{array}{cc}a& 0\\ 0& a\end{array}\right]\psi (bi)=\left[\begin{array}{cc}0& b\\ ?b& 0\end{array}\right] \\ \psi (a)+\psi (b)=\left[\begin{array}{cc}a& b\\ ?b& a\end{array}\right](+為矩陣加法) \\ 故可知\psi (a+bi)=\psi (a)+\psi (bi)(第一個+為普通加法，第二個為矩陣加) \end{gathered}$$

$$\begin{gathered} 普通乘法和矩陣乘法 \\ \psi (a?bi)=\left[\begin{array}{cc}0& a?b\\ ?a?b& 0\end{array}\right] \\ \psi (a)=\left[\begin{array}{cc}a& 0\\ 0& a\end{array}\right] \\ \psi (bi)=\left[\begin{array}{cc}0& b\\ ?b& 0\end{array}\right] \\ \psi (a)?\psi (b)=\left[\begin{array}{cc}0& a?b\\ ?a?b& 0\end{array}\right] \\ 可知\psi (a?bi)=\psi (a)?\psi (bi)(第一個?為普通乘法，第二個?為矩陣乘法) \end{gathered}$$

故可知$\psi$為$V_1到V_2$的同態(tài)

不為單同態(tài)，因為對于*來說，$<a,b>和<b,a>的結果相同\psi (a?bi)=\psi (a)?\psi (bi)=\psi (b?ai)$

為滿同態(tài)

不為同構

第六章 幾個典型的代數系統(tǒng)

1.

(1)可結合、1為單位元、其中任何元素都有逆元。故為群

(4)lcm:最小公倍數 gcd:最大公約數。

可結合。對于lcm有單位元1，對gcd有零元1。在S不僅只有一個元素時，零元無逆元。故為半群

(5)可結合。單位元為0。0的逆元為0，1的逆元為1；故其中任何元素都有逆元。為群

5.

可結合。2為單位元。其中任何元素都有逆元，為4-x。故可構成群

6.

(1)給出$°$運算表

$°$	f1=x	f2=$x^{?1}$	f3=1-x	f4=$(1?x{)}^{?1}$	f5=$(x?1)x^{?1}$	f6=$x(x?1{)}^{?1}$
f1=x	x	$x^{?1}$	1-x	$(1?x{)}^{?1}$	$(x?1)x^{?1}$	$x(x?1{)}^{?1}$
f2=$x^{?1}$	$x^{?1}$	x	1-$x^{?1}$	$(1?x^{?1}{)}^{?1}$	$(x^{?1}?1)x$	$x^{?1}(x^{?1}?1{)}^{?1}$
f3=1-x	1-x	$(1?x{)}^{?1}$	x	$x^{?1}$	$?1$	-1
f4=$(1?x{)}^{?1}$	$(1?x{)}^{?1}$	1-x	$1?(1?x{)}^{?1}$	$(1?(1?x{)}^{?1}{)}^{?1}$	x	$(1?x{)}^{?1}((1?x{)}^{?1}?1{)}^{?1}$
f5=$(x?1)x^{?1}$	$(x?1)x^{?1}$	$(x?1{)}^{?1}x$	$1?(x?1)x^{?1}$	x	$((x?1)x^{?1}?1)(x?1{)}^{?1}x$	$(x?1)x^{?1}((x?1)x^{?1}?1{)}^{?1}$
f6=$x(x?1{)}^{?1}$	$x(x?1{)}^{?1}$	$x^{?1}(x?1)$	$1?x(x?1{)}^{?1}$	$(1?x(x?1{)}^{?1}{)}^{?1}$	$(x(x?1{)}^{?1}?1)x^{?1}(x?1)$	x

可結合。f1為其單位元，所以元素都有逆元。故$<F,°>$ 是一個群

7.

(1)可結合，a為單位元，所有元素均有逆元。故$<G,°>$ 為群

(2)生成元有b,c。因為$b^k,c^k$涵蓋了G里的所有元素

11.

G={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}G=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19\}G={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19}

(1)所有生成元為：

n=20，生成元為小于等于20且與20互質的數

1 3 7 9 11 13 17 19

(2)G的所有子群

$G=<1>=<3>=<7>=<9>=<11>=<13>=<17>=<19>$（生成元的生成子群=G)

20的正因子為 1 2 4 5 10 20,故有6個子群

H1=<0>={0}H1=<0>=\{0\}H1=<0>={0}

$H2=<1>=G$

H3=<2>={0,2,4,6,8,10,12,14,16,18}=<20?2>=<18>H3=<2>=\{0,2,4,6,8,10,12,14,16,18\}=<20-2>=<18>H3=<2>={0,2,4,6,8,10,12,14,16,18}=<20?2>=<18>

H4=<4>={0,4,8,12,16}=<20?4>=<16>H4=<4>=\{0,4,8,12,16\}=<20-4>=<16>H4=<4>={0,4,8,12,16}=<20?4>=<16>

H5=<5>={0,5,10,15}=<15>H5=<5>=\{0,5,10,15\}=<15>H5=<5>={0,5,10,15}=<15>

H6=<10>={0,10}H6=<10>=\{0,10\}H6=<10>={0,10}

(3)[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-FJb3ITaF-1678012348161)(課外學習資料/所需圖片/QQ截圖20221205145804.png)]

12

(1)

$\sigma =$(1 4 6 2 5 3 ),$\tau$=(1 3 2)(4 5 6)

(2)

$\sigma {\tau }^{?1}\sigma =(1,2,6)(3,5,4)$

${\sigma }^2=(1,6,5)(2,3,4)$

(3)

$\sigma$是6階輪換，$\tau$是3階輪換

15

(1)

由于已知為布爾代數，$\vee$對$\wedge$有可分配，$\wedge$對$\vee$也可分配

(a$\wedge$b)$\vee$(a$\wedge$b$\wedge$c)$\vee$(b$\wedge$c)$\vee$(a$\wedge$b$\wedge$c)

=((a$\wedge$b)$\wedge$(1$\vee$c))$\vee$((b$\wedge$c)$\wedge$(1$\vee$a))

=(a$\wedge$b)$\vee$(b$\wedge$c)

=b$\wedge$(a$\vee$c)

(2)

$f^{?}$=b$\vee$(a$\wedge$c)

16

18

根據 $\vee$對$\wedge$的分配律可得

a$\vee$(b$\wedge$c)=(a$\vee$b)$\wedge$(a$\vee$c)

又因為a《=c，故a$\vee$c=c

帶入可得

a$\vee$(b$\wedge$c)=(a$\vee$b)$\wedge$(a$\vee$c)=(a$\vee$b)$\wedge$c

第七章 圖的基本概念

1

(1)

(2)

d(v1)=2

d(v2)=4

d(v3)=2

d(v4)=3

d(v5)=1

d(v6)=0

$\stackrel{6}{\sum _{i=1}}d(v_i)=2+4+2+3+1+0=12=2?6=2?m$

(3)

奇度頂點的個數為2個。驗證了：在任何圖中，度數為奇數的頂點個數是偶數

(4)

無平行邊。環(huán)為$e_2$ 。孤立點為$v_6$ 。懸掛頂點為$v_5$ 。懸掛邊為$e_4$

(5)

多重圖：含平行邊

簡單圖：不含平行邊也不含環(huán)

G無平行邊，G不是多重圖。G含環(huán)，G不是簡單圖

2

由握手定理。$\stackrel{6}{\sum _{i=1}}d(v_i)=2?m=24$。減去3*6度，還剩下6度，若剩下n-3個頂點均為2度時,n最小。計算可得G中至少有6個頂點

4

設：n階無向圖中，度數為k+1的頂點個數為x,度數為k的頂點個數為y。

由題可得

x+y=n

根據握手定理得

(k+1)*x+k*y=2*m

(k+1)*(x+y)-y=2*m

(k+1)*n-y=2*m

y=(k+1)*n-2*m

7

(1)

4階自補圖有一種非同構

5階自補圖有兩種非同構

(2)

不存在3階自補圖：

3階完全圖一共有3條邊。其生成子圖，與其生成子圖的補圖，邊數不同，不可能同構。

不存在6階自補圖：

6階完全圖一共有6*5/2=15條邊。其生成子圖，與其生成子圖的補圖，邊數不同，不可能同構。

9

n為奇數，則n階完全圖每個頂點的度數為偶數。

若G中$v_i$ 的度數為奇數。根據補圖的定義可得$d_G(vi)+d_{\bar{G}}(v_i)=d_{k_n}(v_i)$ ，n階完全圖每個頂點的度數為偶數。則若$\bar{G}$中$v_i$ 的度數為奇數。同理可推廣至其他的點

可證，G與G的補圖的奇度頂點的個數相等

11

(1)

4條不同的初級回路:$c{e}_{3}c,e{e}_{2}d{e}_{1}e,bd{e}_{1}eb,baeb$

5條不同的簡單回路:$c{e}_{3}c,ede,bdeb,beab,baedeb$

(2)

a到d的短程線為:$ae{e}_{2}d$，距離為$d<a,d>=2$

(3)

d到a的短程線為:$d{e}_{1}eba$，距離為$d<d,a>=3$

(4)

D是單向連通圖

經過每個頂點至少一次的通路:$bae{e}_{2}dc$

12

D的鄰接矩陣為
$$A^1=\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 0& 0& 0\end{array}\right]$$

$$A^2=\left[\begin{array}{cccc}0& 0& 1& 1\\ 2& 1& 0& 1\\ 1& 1& 1& 1\\ 0& 1& 0& 0\end{array}\right]$$

$$A^3=\left[\begin{array}{cccc}2& 1& 0& 1\\ 1& 2& 1& 1\\ 2& 2& 1& 2\\ 0& 0& 1& 1\end{array}\right]$$

$$A^4=\left[\begin{array}{cccc}1& 2& 1& 1\\ 2& 2& 2& 3\\ 3& 3& 2& 3\\ 2& 1& 0& 1\end{array}\right]$$

(1)

D中$v_1$到$v_4$長度為4的通路有多少條？

$a_{14}^{(4)}=2$,有兩條

(2)

D中$v_1$到$v_1$長度為4的通路有多少條？

$a_{11}^{(3)}=2$，有兩條

(3)

D中長度為4通路總數為多少？其中有多少條是回路？

總數為$\stackrel{4}{\sum _{i,j}}{a}_{ij}^{(4)}=29$條通路

其中$\stackrel{4}{\sum _{i,j}}{a}_{ii}^{(4)}=6$條為回路

15

正則圖為無向簡單圖，不可有平行邊和環(huán)

有2種非同構情況

6和3,3