作者s90413k64 (成言追口河與草)
看板Grad-ProbAsk
標題Re: [理工] 離散數學 關係封包
時間Wed Sep 4 20:19:27 2013
※ 引述《dearwen61 (Water Blue)》之銘言：
: 一、若A ={1,2,3,4}，R 為定義在集合A上之ㄧ關係（relation），R ={(1,2),(2,3),(3,4)}，試求
: (一)反身性閉包（reflexive closure）
: (二)對稱性閉包（symmetric closure）
: (三)遞移性閉包（transitive closure)
: 答
: (一)所求 = {(1,1),(2,2),(3,3),(4,4)}
http://en.wikipedia.org/wiki/Reflexive_closure
r(R) = R ∪ R^(0) = {(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(4,4)}
: (二)所求 = {(2,1),(3,2),(4,3)}
http://en.wikipedia.org/wiki/Symmetric_closure
根據維基所說的
定義s(R)為R的symmetric closure
s(R) = R ∪ R^(-1)
R^(-1) = {(2,1),(3,2),(4,3)}
所以
s(R) = {(1,2),(2,1),(2,3),(3,2),(3,4),(4,3)}
: (三)所求 = {(1,3),(2,4)}
http://en.wikipedia.org/wiki/Transitive_closure
令M為R的關係矩陣
M = 0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
M^(2) = 0 0 1 0
0 0 0 1
0 0 0 0
0 0 0 0
M^(3) = 0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 0
M^(4) = 0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Mt(R) = M ∪ M^(2) ∪ M^(3) ∪ M^(4)
= 0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0
因此 t(R) = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
: 請問小弟的擬答是否正確呢?
: 主要是想確認自己的觀念是否正確，有勞高手指點了，感謝。
原PO有買參考書嗎?
這個看書會比較清楚
如果沒有的話可以去弄本原文書或黃子嘉的書
這樣讀起來效果比較好
--
1F：推 dearwen61:非常感謝s大的解答，小弟真的獲益匪淺 09/04 21:00
2F：→ dearwen61:小弟並非資工系出身，純粹買了一本入門書自修 09/04 21:01
3F：→ dearwen61:所以有些東西較沒補充到，有打算過陣子買本厚一點的書 09/04 21:01
4F：→ s90413k64:恩恩 看書會比BBS好 我很多符號都打不出來 QQ 09/04 21:52
※ 編輯: s90413k64 來自: 1.160.31.67 (09/04 23:54)