我有一些簡單的"關係"方面的問題想要請教
請大家幫忙！謝謝！
::::::::::::::::::::::::::::
第一個問題如圖1
圖1太小可看這邊：http://i.imgur.com/ruqFE.jpg
遇到Pn的問題我一直都是用S(n,n)+...+s(n,1)的方式去解她
(n個相異物丟到n個相同箱子，允許空箱)
但是原先筆記課本上的這個方法一直看不懂
心裡總覺得不踏實
想請助教幫忙，讓我看懂他！謝謝。
::::::::::::::::::::::::::::
第一個問題如圖2
圖2太小請看 http://i.imgur.com/X6B4N.jpg
::::::::::::::::::::::::::::
第三個問題如圖3
圖3太小請看 http://i.imgur.com/Yzvmc.jpg
綠筆的部份全部都是我抄老師黑板的(字很醜抱歉)
根據左邊的例子小證明可以知道本題是FLASE
可是右邊看起來很厲害的矛盾證法卻又正出來他是矛盾
表示本題是TRUE
(他是設 不ANTISYMMETRIC，最後結果會和題目條件矛盾...表示本命題結果應是ANTISYMMETRIC，是TRUE)
可是這個證明很合理啊
請問倒底發生什麼事了，怎麼會變成這樣？
:::::::::::::::::::::::::::::
第四個問題如圖4
圖4太小請看http://i.imgur.com/wfBP7.jpg
畫紅線的地方是topological orders
我知道有topological sort這個東西
他是將POS轉成TOS的演算法，方法是在POS上多加個關係使其變成TOS
但是我沒有聽過topological orders這個東西啊
請告訴我那是什麼？還有本題答案是？
::::::::::::::::::::::::::::::
第五個問題
(1)就算不是TOS或POS是不是也能畫HASSE DIAGRAM？只是沒有意義...
還是只要不是TOS或POS就算造那規則畫出來的就不算是HASSE DIAGRAM？
(2)我知道TOS的HASSE DIAGRAM會是一條線(chain)，那有沒有說POS畫出來應該會長怎麼樣？
---------------------------
我知道這些問題沒什麼水準，不過還是懇請高手助教幫忙解答
拜託了！謝謝助教！
謝謝！
2 則留言:
1. 要把 1,2,...,n 這幾個東西丟到 k 個箱子裡(一個箱子就是一個等價類), 問你有幾種分法, 此時我們只要觀察 n 這個元素被丟到的那個箱子(假設叫 X)裡面有幾個元素, 就可以將遞迴式列出來了, 因為假設 X 這個等價類裡有 i 個元素, 那麼所形成的等價類個數就會是 c(n-1,i-1)*P_(n-i), 其中 c(n-1,i-1) 就是 1,2,...,n-1 這n-1個數要取i-1個放在 X 理的方法數, 然後P_(n-i)就是除了 X 裡面的元素以外的其他 n-i 個元素所可以形成的等價關係個數, 那麼因為 |X| 可以是 1,2,...,n, 所以把這些加總起來就是 P_n 了
2. R*就是Reflexive transitive closure
3. 這題是true, 老師舉左邊的那個例子不是反例 (因為這個例子有(1,1), 所以此R不具irreflexive), 那只是老師用來說明利用矛盾證法來證明的想法是甚麼而已, 右邊的那個才是證明
因為要看有沒有反對稱性, 我們關心的是有沒有可能出現有(1,2)又有(2,1)但1和2是兩個不同東西的狀況, 因為有這樣的狀況發生就代表 R 為 antisymmetric, 所以我們就來看看有(1,2)又有(2,1)時會發生甚麼事:
(1) 因為題目規定 R 要具有遞移性, 所以(1,1)∈R
(2) 可是題目又要 R 為irreflexive, 所以(1,1)不可以屬於R, 這樣(1)和(2)就產生矛盾
把上述的觀念整理起來就是右邊的證明了
4. 和topological sort是一樣的東西, 這題答案是true, 書上在第10-1節描述拓樸排序演算法的地方後面的note有給例子說明為何順序不會唯一
5. Hasse diagram是定義在偏序關係上的, 就是一種用來簡易表示偏序關係的表式法, 只要給定一個偏序集我們就可以畫出他對應的Hasse diagram, 所以沒有偏序關係就沒有Hasse diagram, 書上第十章有提供很多Hasse diagram可以參考
謝謝線代助教
以上這幾題已經全部弄懂了
偏序全序的部分我會好好拼完的
謝謝！
張貼留言