Re: [問題] DLD 投影片-6
要證明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次方種
依此類推......
但通常證明是這樣
因為{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
: ※ 引述《gglk (錦州挖挖)》之銘言：
: : 老師不好意思，
: : 也許我問的有些問題您上課有講過，
: : 或是您覺得很直觀，
: : 不過還是請您指點一下愚昧的學生。
: : 請問
: : 2.最後一行，可以說明一下NUMBERS OF FUNCTIONS的定義對於證明COMPLETENESS
: : 是怎樣USEFUL嗎?
: : 謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.41.66
※ 編輯: asleepzzz 來自: 122.116.41.66 (10/06 01:44)
推
10/06 11:32, , 1F
10/06 11:32, 1F
→
10/06 11:32, , 2F
10/06 11:32, 2F
討論串 (同標題文章)