→ enorm:.....第二題題目改了一點..... 10/09 21:54
我大約是這樣寫
1. (1) (2) 用 Boolean function 的定義直接就可以證明
(3) 用 (1) (2) 轉換
2. (1) z = r's+rs' = 一路帶換 = bc'+ab'd'+a'cd+a'c'd'+b'c'd'+abcd
(2) 用 a, b, c 依序算出 p, q, r, s, z --> z = bc'+c'd'+ab'd'+a'cd+abcd
接下來我覺得怪怪的，我沒有化成最簡，而是各自畫 BDD 在去 reduce 成一樣。
P.S. 最簡是 bc'+bd+c'd'+a'bd'+a'cd
3. (a) 數學歸納法證明奇數 node: 0 跳兩格，1 跳一格，最後一個 0 跳到最後的 0。
偶數 node: 0 跳一格，1 跳到最後的 1。
(b) 前 k 個 variable 的 node 數會不斷以 2 倍增加，
接下來 k 個 node variable 的 node 數會不斷以 2 倍減少，
最後加上 0 跟 1。
4. 三個形狀都是 a(c(d,d),b(d,c(d,d))) x(y,z) 就是 x 是 0/1 到 y/z node
但是最後 d 的會接到哪三個會不一樣。
化簡過後 AND a(0,b(d(1,0),0))
OR a(c(1,d(0,1)),b(1,c(d(1,0),1)))
XOR 不會表示啦...會有分支又指到同一個 node
歡迎討論囉:P
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.85.196.199