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