可求和布尔函数的性质
2016-10-29曾利全许道云
曾利全,许道云
(1.贵州大学数学系,贵州贵阳 550025;2.贵州大学计算机科学系,贵州贵阳 550025)
可求和布尔函数的性质
曾利全1,许道云2*
(1.贵州大学数学系,贵州贵阳550025;2.贵州大学计算机科学系,贵州贵阳550025)
可求和布尔函数是临界布尔函数判定理论中比较重要的内容之一。该类函数有一个参数k,k表示布尔函数存在k个成真点X1,X2,…Xk和k个成假点Y1,Y2,…Yk,并且它们的和相等。本文主要研究了n元2-可求和布尔函数和n元3-可求和布尔函数的基本性质。
临界布尔函数;2-可求和布尔函数;3-可求和布尔函数
一个n元布尔函数f(X)是指:f:{0,1}n→{0,1},其中n为正整数,Bn为n维{0,1}向量。对于每一个X=(x1,x2,…,xn)∈Bn,其中,xi∈ {0,1},i=1,2,…,n。若X为成真点,则f(X)=1,若X为成假点,则f(X)=0。用T(f)表示f(X)的成真点集,F(f)为f(X)的成假点集。n元布尔函数f(X)称为k-可求和布尔函数[1],是指对于r布尔函数f(X)存在r个错误点X1,X2,…Xr和 r个正确点 Y1,Y2,…Yr,使得成立。n元布尔函数f(X)是否为可求和布尔函数是判定该函数为临界布尔函数的充要条件。它是一个判定n元布尔函数f(X)是否为临界布尔函数的有效方法。自从上世纪五六十年代由Paul和McCluskey[2]首次提出了临界布尔函数的概念之后,国内外有许多的科学家对其进行了深入的研究。在文献[3]中,Winder和Margo对临界布尔函数进行了重新命名,同时得到了很多重要的结果,主要工作是找出了在含有7个布尔变量的布尔函数中存在的所有临界布尔函数,以及应用simplex-方法来判定临界布尔函数,这类布尔函数的推广和不断被人们接受则是在Winder[4]、Moraga[5]和Gamelan[6]三位学者不断研究和努力之下实现的,他们证明了权值和变量之间的关系,临界函数和它的对偶函数之间的关系,真假值点之间的关系。……
