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