简介

代数范式

在应用程序中的布尔函数

参见

参考文献

简介

在数学中，布尔函数通常是如下形式的函数

F(b1, b2, ..., bn)

带有 n 个来自两元素布尔代数 {0,1} 的布尔变量 bi，F 的取值也在 {0, 1} 中。

在一般的定义域上的，取值在 {0, 1} 中的函数也叫做布尔值函数，所以布尔函数是它的特殊情况。带有定义域 {1, 2, 3, ... } 的这种函数通常叫做二进制序列，就是说 0 和 1 的无限序列；通过限制到 { 1, 2, 3, ..., n }，布尔函数是编码长度为 n 的序列的自然的方法。

它有 <math>2^{2^n}</math> 个布尔函数；它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色，特别是在对称密钥算法的设计中(参见 S-box)。

在布尔值函数上的布尔运算逐点(point-wise)组合值(比如通过 XOR 或其他布尔运算符)。

布尔函数可以唯一的写为积(AND)之和(XOR)。这叫做代数范式 (ANF)。

<math>f(x_1, x_2, \\ldots , x_n) = \\!</math> <math>a_0 + \\!</math>

<math>a_1x_1 + a_2x_2 + \\ldots + a_nx_n + \\!</math>

<math>a_{1,2}x_1x_2 + a_{n-1,n}x_x_n + \\!</math>

<math>\\ldots + \\!</math>

<math>a_{1,2,\\ldots,n}x_1x_2\\ldots x_n \\!</math>

序列 <math>a_0,a_1,\\ldots,a_{1,2,\\ldots,n}</math> 的值因此还唯一的表示一个布尔函数。布尔函数的代数度被定义为出现在乘积项中的 <math>x_i</math> 的最高数。所以 <math>f(x_1,x_2,x_3) = x_1 + x_3</math> 有度数 1 (线性)，而 <math>f(x_1,x_2,x_3) = x_1 + x_1x_2x_3</math> 有度数 3 (立方)。

代数范式

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

这里的序列 的值因此还唯一的表示一个布尔函数。布尔函数的代数次数被定义为出现在乘积项中的 xi 的最高次数。所以 f(x1,x2,x3) = x1 + x3 有次数 1 (线性)，而 f(x1,x2,x3) = x1 + x1x2x3 有次数 3 (立方)。

对于每个函数 f 都有一个唯一的 ANF。只有四个函数有一个参数: f(x) = 0, f(x) = 1, f(x) = x, f(x) = 1 + x (它们都可以在 ANF 中给出)，要表示有多个参数的函数，可以使用如下等式: ，这里的 并且 。实际上，如果 x1 = 0 则 x1h = 0 并因此 ；如果 x1 = 1 则 x1h = h 并因此 。因为 g 和 h 二者都有比 f 少的参数，可以得出递归的使用这个过程将完成于只有一个变量的函数。例如，让我们构造一个 (逻辑或)的 ANF: f(x,y) = f(0,y) + x(f(0,y) + f(1,y))；因为 并且 ，可以得出 f(x,y) = y + x(y + 1)；通过打开括号我们得到最终的 ANF: f(x,y) = y + xy + x = x + y + xy。

在应用程序中的布尔函数

一个布尔函数介绍了如何确定一个布尔值输出基于某种逻辑输入计算的布尔值。 这些职能发挥作用的问题的基本理论，复杂性 ，以及作为设计的电路芯片和数字电脑 。 布尔函数的性质研究中发挥关键作用密码学 ，特别是在设计的对称密钥算法 （见替代框 ）。

布尔函数通常代表中的句子命题逻辑 ，有时作为多元多项式超过绿 （2），但更有效的申述， 二元决策图 （BDD）的， 正常的否定形式 ，与命题向无环图 （PDAG）。

在合作博弈论，布尔函数被称为游戏） 简单的游戏 （表决;这个概念应用到解决问题的社会选择理论 。

参见

代数集

布尔代数（逻辑）

布尔代数主题

布尔域

布尔逻辑

布尔值函数

逻辑连词

真值函数

真值表

对称布尔函数

决策树模型

回避的布尔函数

参考文献

数字化设计，马诺。 米莫里斯

德拉甘，斯坦科维奇，Radomir诚聘英才莫拉加，克劳迪奥（2003年11月）。扬科维奇“算术表达式的优化使用双极性财产” （PDF格式））， 电气工程 。 塞尔维亚杂志 1（71 - 。 2010-04-06查阅 。