有限布尔函数

在数学中，有限布尔函数是如下形式的函数f : B → B，这里的B = {0, 1}是布尔域，而k是非负整数。在k = 0的情况下，函数简单的是B的一个恒定元素。

更一般的说，形如f : X → B函数，这里的X是任意集合，是布尔值函数。如果X = M = {1, 2, 3, …}，则f是“二进制序列”，就是说0和1的无限序列。如果X = [k] = {1, 2, 3, …, k}，则f是长度为k的“二进制序列”

有22k{\displaystyle 2^{2^{k}}}个这种函数。

代数范式

布尔函数可以唯一的写为积（AND）之和（XOR）。这叫做代数范式（ANF），也叫做Zhegalkin多项式。

这里的a0,a1,… … -->,a1,2,… … -->,n∈ ∈ -->{0,1}∗ ∗ -->{\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{序列1\}^{*}}。 序列a0,a1,… … -->,a1,2,… … -->,n{\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}}的值因此还唯一的表示一个布尔函数。

布尔函数的代数次数被定义为出现在乘积项中的xi{\displaystyle x_{i}}的最高次数。所以f(x1,x2,x3)=x1+x3{\displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{3}}有次数1（线性），而f(x1,x2,x3)=x1+x1x2x3{\displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{1}x_{2}x_{3}}有次数3（立方）。

对于每个函数f{\displaystyle f}都有一个唯一的ANF。只有四个函数有一个参数: f(x)=0{\displaystyle f(x)=0} ，f(x)=1{\displaystyle f(x)=1} ，f(x)=x{\displaystyle f(x)=x} ，f(x)=1+x{\displaystyle f(x)=1+x} ；它们都可以在ANF中给出。要表示有多个参数的函数，可以使用如下等式：

这里的g(x2,… … -->,xn)=f(0,x2,… … -->,xn){\displaystyle g(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})} 并且 h(x2,… … -->,xn)=f(0,x2,… … -->,xn)+f(1,x2,… … -->,xn){\displaystyle h(x_{2},\ldots ,x_{n})=f(0,x_{2},\ldots ,x_{n})+f(1,x_{2},\ldots ,x_{n})} 。

实际上，

因为g{\displaystyle g}和h{\displaystyle h}二者都有比f{\displaystyle f}少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。

例如，让我们构造一个f(x,y)=x∨ ∨ -->y{\displaystyle f(x,y)=x\lor y}（逻辑或）的ANF：

参见

布尔代数主题列表

真值函数

零阶逻辑

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。