Re: [問題] DLD 投影片-6
※ 引述《asleepzzz (睡魔)》之銘言：
: 要證明COMPLETENESS 不必窮舉
: 用數學歸納法
: 有點類似漢明碼的概念
: 1個variable
: 有0->0
: 1->0
: 0->1
: 1->1
: 0->0
: 1->1
: 0->1
: 1->0
: 2的2的1次方種
: 2個variable時
: 可以想成4種前面各加1或0
: 00->0 10->0
: 01->0 11->0
: 00->1 10->1
: 01->1 11->1
: 00->0 10->0
: 01->1 11->1
: 00->1 10->1
: 01->0 11->0
: 每個00各自找11搭配
: 所以有(2的2的1次方)*(2的2的1次方)=2的2的2次方種
: 依此類推......
我是想說，要證COMPLETENESS除了列出N個INPUT可能找到的FUNCTION
(共2的2的N次方種)
不是還要確定這2的2的N次方種FUNCTION都可以被這個SET實際做出來?
(我上一篇說的窮舉是舉出(做出)這些電路，不是指舉出這些可能的FUNCTION)
(然後假設是還沒有任何一組COMPLET SET被證出來的情況下，EX:現在要證{AND OR NOT}是COMPLETE SET)
還是說這也是靠歸納法證的 。
謝謝。
: 但通常證明是這樣
: 因為{AND,OR,NOT}是已知的COMPLETE SET
: 所以只要證明你的SET和上面的set等價
: 就能證明completeness了
: ※ 引述《asleepzzz (睡魔)》之銘言：
: : 給ㄧ個logic gate的set
: : 要看它滿不滿足completeness
: : 只要看這個set任意組合出來的電路
: : 能夠符合每個function
: : 就是COMPLETENESS
: : 我舉個例
: : 如有2個logic variable--A B
: : 則FUNCTION有2的2的2次方 也就是16種
: : 只要能用gate的set完成(在此我用and or not示範)
: : 就符合completeness
: : (A,B)---->OUTPUT
: : FUNCTION1(A*NOT A)
: : (0,0)->0
: : (0,1)->0
: : (1,0)->0
: : (1,1)->0
: : FUCTION2(A+NOT A)
: : (0,0)->1
: : (0,1)->1
: : (1,0)->1
: : (1,1)->1
: : FUCTION3(NOT(A+B))
: : (0,0)->1
: : (0,1)->0
: : (1,0)->0
: : (1,1)->0
: : FUCTION4(NOT A*B)
: : (0,0)->0
: : (0,1)->1
: : (1,0)->0
: : (1,1)->0
: : FUCTION5(A*NOT B)
: : (0,0)->0
: : (0,1)->0
: : (1,0)->1
: : (1,1)->0
: : FUCTION6(A*B)
: : (0,0)->0
: : (0,1)->0
: : (1,0)->0
: : (1,1)->1
: : FUCTION7(NOT A)
: : (0,0)->1
: : (0,1)->1
: : (1,0)->0
: : (1,1)->0
: : FUCTION8(NOT B)
: : (0,0)->1
: : (0,1)->0
: : (1,0)->1
: : (1,1)->0
: : FUCTION9(A*B+NOT A*NOT B)
: : (0,0)->1
: : (0,1)->0
: : (1,0)->0
: : (1,1)->1
: : FUCTION10((NOT A+NOT B)*(A+B))
: : (0,0)->0
: : (0,1)->1
: : (1,0)->1
: : (1,1)->0
: : FUCTION11(B)
: : (0,0)->0
: : (0,1)->1
: : (1,0)->0
: : (1,1)->1
: : FUCTION12(A)
: : (0,0)->0
: : (0,1)->0
: : (1,0)->1
: : (1,1)->1
: : FUCTION13(NOT A+NOT B)
: : (0,0)->1
: : (0,1)->1
: : (1,0)->1
: : (1,1)->0
: : FUCTION14(A+NOT(A+B))
: : (0,0)->1
: : (0,1)->0
: : (1,0)->1
: : (1,1)->1
: : FUCTION15((NOT A*NOT B)+B)
: : (0,0)->1
: : (0,1)->1
: : (1,0)->0
: : (1,1)->1
: : FUCTION16(A+B)
: : (0,0)->0
: : (0,1)->1
: : (1,0)->1
: : (1,1)->1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.14.204
※ 編輯: gglk 來自: 59.112.14.204 (10/06 11:56)
※ 編輯: gglk 來自: 59.112.14.204 (10/06 11:58)
推
10/06 15:01, , 1F
10/06 15:01, 1F
推
10/06 15:41, , 2F
10/06 15:41, 2F
推
10/06 17:54, , 3F
10/06 17:54, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：