[关闭]
@rihkddd 2015-01-19T00:47:37.000000Z 字数 1311 阅读 1423

为什么只有NAND和NOR操作可以是自足算子?

作业


自足算子

自足算子或自足连结词是在一特定类的算子中只靠自身就能生成所有这些算子的算子。在逻辑中,它是足够生成所有布尔值函数的一个逻辑算子,f:XB,这里的 X 是一个任意集合而 B 是一个通用的 2-元素集合,典型为 B=0,1=false,true,特别是生成所有的有限布尔函数,f:BkB


Table of binary truth functions [1]

p q ¬q ¬p p q
1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

定义  为一个二元操作,我们来分析一下如果  是自足算子,  需要满足的条件:

p=1,q=1,如果  是函数完全的,那么经过有限次  的操作,必然既可以得到1也可以得到0
pq=1,因为p=1,q=1,pq=1 而且无法从其它途径得到0,因此,无论经过多少次  操作也得不到0。故  不可能满足自足算子的性质,因此必然有pq=0.
同理可以得出若p=0,q=0,则必然有pq=1.

然后分析若p=1,q=0pq应该是什么?

因此若p=1,q=0pq既可以为0,也可以为1.
同理可知p=0,q=1pq也是既可以为0,也可以为1.

又因为,若要考虑到  要满足结合律,即

(01)0=0(10)

故要满足p=1,q=0p=0,q=1结果相同,因此综上  可能代表的二元运算只有

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注