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