[離散數學課本]

第十三章。

1、13-39例25：
    請問此題有其他解法嗎？還是說為了討論i不等於j所以非得拆開討論..

2、13-43範例2之(b)：
    請問為何是 context-sensitive，不是 context-free 的原因是？

3、13-46範例6：
    grammar這種東西應該很難有標準答案吧。不過我想問的是，如果題目沒限制，
    那麼有幾條production rules應該都可以吧？比如這題我是寫..
    P = { S→Ab, A→aAb, A→空, B→Aa, B→空 }

4、13-61範例6：
    S0跟S4的0.0是不是應該是接到S1跟S4？

5、13-71範例5之(a)：
    最後F接到C的地方感覺是錯的..題目不是規定須以abc為字首，雖然C有b,c 的loop，
    不過C若走a不就錯了？還是說FSA定義我搞錯，應該是要滿足L的所有規定吧..

以上，請多指教。

[線性代數] 99台大數學所推甄

請問老師第4.及6題

第4題我的寫法如第2張照片 我這樣寫對嗎？

第6題中 題目說A矩陣的特徵根都是正數 但沒說A＝A^t 那麼A還是正定矩陣嗎?這提示不是就是在問A是正定矩陣 則有一個可逆矩陣B 使得B^2=A??

[線代分類題庫] 3-25 答案

這題答案是不是有錯~?


經過列運算後，
行列式最右下方那一項 : (-1)^n-1 * 2^n


我算是 : 1+(-1)^n-1 * 2^n


這樣右邊等式就會變成

( 1+(-1)^n-1 * 2^n ) an = 0

但是因為 n >1 ，所以 ( 1+(-1)^n-1 * 2^n ) 一定不等於 0
所以 an = 0 不影響答案

這樣對嗎??

關於排列組合

金毛中學舉行兩天的畢業旅行，共有四台車，欲安排八位導遊隨車服務， 每天每車兩位，但第一天在同車的兩個導遊，第二天不安排在一起，則兩天下 來共有╴╴╴種安排方法。（同一個導遊可以兩天都在同一車）

想問一下答案是不是


(以修正)
第一天 第二天
(C82+C62+C42+C22/4!)*4! + C84*D4*4!/2!(亂序) // C82代表 8個相異物挑2個出來做排列

第二天 先任意選4人排列乘上4! 視為相異車後 接下來由於選ABCD = 選EFGH 所以/2!

或是有其他更適合的想法?

離散習題詳解 P519

9-58 請問這題的 congruence relation 是什麼意思?

跟第二章關係的 congruence relation 有關係嗎....


另外9-55 題目問 show that (S,*) is isomorphic to the group R* .....
函數 f 不是要定義成 由 (S,*) -> R* ? 還是我觀念錯誤呢

麻煩解答了

[離散數學課本]

9-113範例二：
    假設要證明S為R的子環，定義不是寫存在a,b屬於S, a+(-b)屬於S, a‧b屬於S嗎？
    但是(a)小題為何是證a+b屬於S？

10-21範例二；
    可以大致解釋一下此題嗎？看不太懂意思....

10-29範例十：
    如果照解答更正後，答案為{{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}，
    那圖形不就等同10-10頁的直線圖，這種圖形不是有著1≦2≦3≦4(POS，那個圖打不出來..)的關係？這樣還會是antichain嗎？

10-30範例十一(c)小題：
    如果有k!種方法形成空集合到A的chains，不是最長只能形成k!的maximal chain嗎？

10-84例49(a)小題：
    題目限制x,y,z皆在Z內；在若同樣取X=1，不是依舊無法找到y跟z滿足x=3y+5z嗎？

不好意思，10-1問題有點多....。
請指教。

離散習題詳解 第四版 P650

13-25證明

(2)這點

到第八行時證明了 入屬於A 再加上 (1) 證明了 A=A+
那不是就可以說 A=A*
還是我認知有錯?
解答為什麼還要多証這麼多呢?

麻煩解答了 謝謝

生成函數

請問
0,0,1,a,a^2,a^3...
的生成函數是否為
1/1-ax再乘x^2 = x^2/1-ax

河內塔

5-42的例14的說明 我想知道是不是跟我畫的意思一樣?
應該說從第4步開始遞回才對

常係數線性遞回計算問題

課本第5-37 第9題
我令
an = 2an-1 +1
a1=1
可是這樣算下去
在最後齊次解+非齊次解 帶入原式求解的地方 會把兩邊都相等 結果係數(齊次解的係數)算不出來 一一"
想知道要怎樣避免這種情況 是否有什麼要注意的事項?

[離散] 習題詳解 p.92

(e) If R is antisymmetric , then R^-1 is antisymmetric


課本解答的證法是:

若 a R^-1 b 且 b R^-1 a 推到 a=b 就得證。


想問我的證法是否ok

for all a,b 屬於 A (a!=b)
若(a,b) 屬於 R^-1
→(b,a) 屬於 R

因為 R 具 antisymmetric
→(a,b) 不屬於R
→(b,a) 不屬於R^-1

R^-1 : antisymmetric

寫完在想，是否要加上(a!=b)
如果有加上，是否還要考慮 a=b

不知道這樣寫夠不夠嚴謹，

謝謝

離散習題講解第四版 邏輯問題

P582 10-80
看不大懂解答的想法
而我自己的想法是

所有x { 有些y [xy=1] 且 有些z [xz=1]} -> y=z
不知道這樣是否有錯
有錯的話 錯在哪呢?

麻煩解答 謝謝

[離散數學分類題庫]

1、9-3(b)
    取1的話，是否具identity？

2、9-5
    同哩，"*"是否也可取max成為identity？

3、9-14(b)
    為何不具closed？

以上，感謝。

nullity

A:m*n, m不等於n
rank(A)等於rank(A^T)
而nullity(A)是否等於nullity(A^T)?

~by 不明白

97輔大~線代4.4

T:V-->V' linear
T:1-1<=>ker(T)={0}

pf:
(<=)
設T(u)=T(v) =>
T(u)-T(v)=0 =>
T(u-v)=0 =>
u-v屬於ker(T)=>
u-v=0 =>
u=v

疑問:u-v=0表示承認0-->0, 0真的只會送到0嗎??這是定義嗎

離散習題詳解第四版 關於Hasse diagram

P542 10-11題 12和36是否應該要有邊相連?
P543 10-12題 10和30也是否應該有邊相連?

麻煩解答了 謝謝

(97交大)4.2座標化

T:R^2-->R^2
B={11}
01
B
求[T]B?

課堂老師給答案根號20 -1
1/2 1

但是學生計算後好像有出入!!請助教撥冗予以解惑
r
好像在[T]B就有疑問

關於bigO證明

題目是 show that x^2 is not O(x)
解答是用 定義來證

想請問可不可以用
lim (x^2 ) / x = 無限大
(n->無限大)

的概念來證明
若可以 要怎樣寫會比較恰當呢?

麻煩解答了 謝謝

[線性代數] idempoent 算子的對角化

請問一下 線代第5章 推廣5-31
A為idempoent matrix
書上證明（3）寫說：
A^2=A
所以F^n =CS(A)直和ker(A)

但是老師教到第八章說
F^n =CS(A)直和ker(A^t)

idempoent operator 沒有 A^t=A的性質
第五章 推廣5-31 為什麼會這樣寫呢？
不懂ㄋㄟ...
請指教

[線性代數] 93清大數學所

如第3題，

對於T-cyclic subspace不太瞭解，

如題目{v, T(v), T^2(v), T^3(v)} is a T-cylic basis for R^4

題目又說：each eigenspace of T is one-dimensional
加上代數重數大於幾何重數，那就等價{v, T(v), T^2(v), T^3(v)} 有4個相異eigenvalue了

我一直以為 v 即使不是取 eigenvector,

但{v, T(v), T^2(v), T^3(v)} 應該會共用同一個eigenvalue吧？

（類似上課教的做Jordan form的第一列點圖）

看了題目顯然我的理解是錯的

但是我不知道我的觀念錯在哪裡

請指正 謝謝...........................

關於老師上課的証明(布林代數)

第十章裡

證明 Dm : Boolean algebra <=> m 之質因數分解為 m= p1*p2*...*pk
註: Dm = {aa為m之正因數}

這個方向 <= 為什麼這樣證明就可以了

所有a屬於Dm 不失一般性 a=p1*p2*...*pl
取 a' =p(l+1)*.....*pk => lcm(a,a')=m
gcd (a,a')=1 所以 a'為 a 之complement

為什麼只證明了 互補性質還是因為 bounded 和 distrubutive 性質比較簡單所以沒打算証?

麻煩了 謝謝

[線性代數] 95清大數學所

請問第2題 他是在考A的eigenvalue 等於 A^t的eigenvalue

我們習慣的就是right(column) eigenvectors of A

A的行向量依序乘以eigenvalue

如果換成題目所說的row(left) eigenvector of A

是要怎麼乘呢？

是誰對誰乘呢？

謝謝..

[線性代數] 95清大數學所

95清大數學所第7題的（b）小題 求T的Jordan form
老師我不懂為何解答有注意那一段文字

「需保證T的eigenvalue皆為實數，才保證T的Jordan canonical form 為一個對角矩陣」??

第八章教正交矩陣或是么正矩陣的eigenvalue 都說其絕對值為 1

｜eigenvalue｜= 1
且即使是正交矩陣則其eigenvalue亦有可能為複數

為什麼解答要特地加那2行注意文字呢 不懂ㄋㄟ.....

[線性代數] 97台聯大數學所

請問一下圖中第3題的（e）選項
老師的歷屆解答沒有選e:
f(x)= x^2 + 1 = 0
反例是舉
A＝
｜i 1｜
｜0 i ｜
B＝

｜-i 1 ｜
｜ 0 -i｜

因為A與B的Jordan form不同 所以A與B不相似

我的疑問是當有複數eigenvalue 的時候

我們在取eigenvalue 不是要取共軛嗎？

所以如果取共軛eigenvalue,

則Jordan form分別為
A＝

｜i 0｜
｜0 -i ｜
B＝

｜i 0 ｜
｜ 0 -i｜

那A與B就相似了耶.....

還是我的觀念錯了呢？？

謝謝指教

離散習題詳解四版 P412 7-25題

(b)
書上解答直接列出來的 不清楚如何來

我先從(d)開始解
我的想法是 T(n)=T(n-1)+T(n-2)+1 //T(n) 是總node數
T(1)=T(2)=1
解出來 T(n) 等於 2Fn-1
且 T(n)=L+I //L是 leaf I是 internal node
L=I+1 得 T(n)=2I+1
得出 (b)和(C)的答案

我想問的是 如何直接做(b)小題

麻煩老師解答了

線代 7-25

請問範例9的第B小題

要怎麼積分@@
我拆成alnx 和bxlnx 做分部積分
但是做不出書上那樣

[離散數學]

一、8-41：範例1
    可否解釋一下這題 cut edge的解答意思

二、9-39：例20
    請問一下(b)的P^2以及(c)的P^3是該怎麼求出(即，取。後該怎麼化簡)？

三、9-85：範例2
    (a)跟(b)的第二行求ker時 ξ(x)=1 這是怎麼假設出的？

感謝解答

[線性代數] 97台聯大數學所

Let T : V→W and U : W → Z be linear maps on the finite dimensional vector spaces V,W, and Z.
Prove:
Rank(UT)≦Rank(U)
Rank(UT)≦Rank(T)

解答中在證明 Rank(UT)≦Rank(T)寫：
given x 屬於 ker(T)
＝> T(x)=0
＝> (UT)(x)=U(T(x)) = 0
＝> x 屬於ker(UT)
..........................
nullity(T)≦nullity(UT)
＝> rank(UT) ≦ rank(T)

我的疑問是：
在第四章有教過矩陣版的 (AB) ≦ min {rank(A), rank(B)}
所以我寫台聯大這個題目，可不可以用矩陣版的寫法，即
given y 屬於 RS (UT)
存在 x 屬於 Z ，
使得 y = x UT
＝> y 屬於 RS (UT)
..............往下推得rank(UT) ≦ rank(T)？？

[線性代數] 97台聯大數學所

Determine the minimal polynomial of the matrix A and A^-1 (A inverse):
｜0 0 0 1 ｜
｜0 0 1 1 ｜
｜0 -2 0 0｜
｜-2 0 0 0｜

A的極小多項式算出來是：（x^2+2）^2 還滿好算的...

那麼A^-1的極小多項式 跟A的極小多項式有關連嗎？

歷屆解答中A^-1的極小多項式：（x^2+1/2）^2

所以A與A^-1的極多項式有eigenvalue倒數之後，次方相同，的關係嗎？

謝謝

關於離散習題詳解第四版 p377 6-84題

解答討論B小題是用拆解方法
請問是否可以用討論的方法 從ac這兩點同色及不同色的觀點去討論
如6-82題那樣
因為我自己用討論的方法 答案不一樣
以下是我的想法
1- ac同色
對a點 有入種
c點1種
e點 入-1
b點 入-1
d點 入-2
共 入*(入-1)^2*(入-2)

2-ac不同色
a點 入種
c點 入-1
e點 入-2
b點 入-2
d點 入-3
共 入*(入-1)*(入-2)^2*(入-3)
1.2相加答案不一樣
是我觀念有錯?還是討論方法有錯?
另外什麼情形下用拆解方法比較好
什麼情形用討論比較好?
麻煩老師解答了 謝謝

[線性代數] C.8 課本習題 P.8-185 57題 90中原數學

本題57題題目 矩陣A長相
............｜ 3 0 1 ｜
A=1/2 ｜ 0 4 0 ｜
.............｜ 1 0 3 ｜
欲找B使B^2=A，所以要先找特徵多項式。

我的疑問是A的特徵多項式，用3種方法找答案都不同>< 請指正：
法一. 純量1/2 進入矩陣裡面，所以
........｜3 0 1 ｜
A= ｜0 2 0 ｜
........｜ 1 0 3｜ 則得到A的特徵多項式為：det(A-xI)=(x-2)^2 (x-4) 得特徵根為：2,2,4
法二. 在整個A外面取det, 所以 det(A-xI)
.................｜ [ (3-x) 0 1 ] ｜
=det (1/2) ｜ [ 0 (4-x) 0 ] ｜
................｜ [ 1 0 (3-x) ] ｜
然後因為1/2從det出來要變成（1/2）^3， 所以 =1/8 (x-2) (x-4)^2 =0 得特徵根為：2,4,4

法三.解答說A的特徵根為1,2,2

因為解答沒運算過程 我自己用法一法二兩種方法答案還不同..><..
所以請問
1.法一.法二是錯在哪裡呢？整個觀念看似正確ㄋㄟ....
2.正確算法過程？

感謝....

[離散] 3-45 例題29

想請問一下這題的答案有沒有錯誤~?

SURREPTITIOUS

(a) exactly three pairs of consecutive identical letters

ans: C(5,3) * 10! / 2!^2 - 4 * C(5,4) * 9!/2! + C(5,2)*8!
↑

想請問上面的4，是如何得到~~?


(b) at most three pairs of consecutive identical letters

ans: 13! / 2!^5 - C(5,4) * 9! / 2! + C(4,3) * 8!
↑

上面這個最後面那項不知道怎麼來的

(b) 解法應該是用全部去扣掉 4-pairs 5-pairs 吧~


謝謝

[離散數學]5-80頁

1.紅色線為何是相當於求呢？「問題在為何是{1,,,n-1}」到{1,,,n-1}？（2)也是一樣」
2.為何（2）f(n-1)與f(n)可能為n?
3.f(n)=n+1也是一對一和映成函數為何沒有出現呢？
是因為化在（2）裡 所以f(n-1)可能為n嗎？

多謝

離散非齊次遞迴的令法

假設有個題目是：
1.an=.....=n*3^n
這樣的題目該怎令特解？

[線代]七八章幾個問題

一、7-103第二行
    取[-1 -1 1]為N(A)的一組basis。
    這邊是因為原本矩陣是2*3(行大於列)，所以取出來的基底是N(A)嗎？
    反之，若是3*2(列大於行)，取出來的即為R(A)嗎？

二、7-103倒數第三行
    因為Ax=b有解   →   b屬於R(A)
    請問這是為什麼？

三、8-39倒數第二行
    k^2=4是不是有錯？

四、8-140例題40
    ||A||1的答案跟||A||無限的答案是不是錯？

3.2 subspace

w1,w2都是V的subspace
未必w1,w2聯集是V的subspace
V為R^2, w1為x軸, w2為y軸
聯集還是R^2
可以確定不是V的subspace
有哪位老師可以解惑一下
聯集後的平面是何定義或跟V有什麼關係?

[線代]第7-17頁

例16第一小題：

想請問一下，證明過程中的





這幾個條木是從哪裡出現的？
應該說為什麼要證這幾項？
感謝。

[離散]Partial order set

Let p q r s be four distinct primes

how many edges are there in the Hasse diagram of all positive divisors

(c)p^3q^2

(d)p^3q^2r^4

請各位幫忙

謝謝

[線性代數] Pfaffian determinant

老師您好
我在您出的97年歷屆考古題詳解中
其中政大應數的解答裡面
您有提到Pfaffian determinant
寫說：
der(M)={Pf(M)}^2 ,其中Pf(M)為M的Pfaffian determinant
他為M的entries polynomials,當Pf(M)不等於0時,則M為可逆矩陣....

可否解釋一下Pfaffian determinant，謝謝

離散數學的補充內容已更新

• 更新離散數學第四版第一至十章及第十三章之補充內容

關於歐氏空間與正定的關係

之前看了學校的教科書，上面描述歐氏空間具有正定的性質。我想問的問題是，正定和歐氏空間之間有什麼關聯性嗎？謝謝。

P4-45 例27

關於第B小題
如果用下面這種算法
L(x^2+2x+2)=10x+15
=10*1+5*(1+2x)


10
為什麼算出來是[5 ]