作者gglk (锦州挖挖)
看板CSIE_ASM
标题Re: [问题] DLD 投影片-6
时间Sat Oct 6 11:50:01 2007
※ 引述《asleepzzz (睡魔)》之铭言：
: 要证明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次方种
: 依此类推......
我是想说，要证COMPLETENESS除了列出N个INPUT可能找到的FUNCTION
(共2的2的N次方种)
不是还要确定这2的2的N次方种FUNCTION都可以被这个SET实际做出来?
(我上一篇说的穷举是举出(做出)这些电路，不是指举出这些可能的FUNCTION)
(然後假设是还没有任何一组COMPLET SET被证出来的情况下，EX:现在要证{AND OR NOT}是COMPLETE SET)
还是说这也是靠归纳法证的 。
谢谢。
: 但通常证明是这样
: 因为{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
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.112.14.204
※ 编辑: gglk 来自: 59.112.14.204 (10/06 11:56)
※ 编辑: gglk 来自: 59.112.14.204 (10/06 11:58)
1F：推 asleepzzz:此为代数相关部分 请在礼拜一来找我(下午2点之後不在) 10/06 15:01
2F：推 gglk:喔好，是302吗? 上次去不确定结果没进去 10/06 15:41
3F：推 asleepzzz:恩 10/06 17:54