要證明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)