APP下载

可求和布尔函数的性质

2016-10-29曾利全许道云

贵州大学学报(自然科学版) 2016年1期
关键词:性质研究

曾利全,许道云

(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]三位学者不断研究和努力之下实现的,他们证明了权值和变量之间的关系,临界函数和它的对偶函数之间的关系,真假值点之间的关系。……

登录APP查看全文

猜你喜欢

性质研究
FMS与YBT相关性的实证研究
一类非线性随机微分方程的统计性质
2020年国内翻译研究述评
辽代千人邑研究述论
随机变量的分布列性质的应用
一类多重循环群的剩余有限性质
完全平方数的性质及其应用
视错觉在平面设计中的应用与研究
九点圆的性质和应用
EMA伺服控制系统研究