布尔函数

✍ dations ◷ 2025-06-06 16:16:36 #布尔函数
在数学中,布尔函数(Boolean function)描述如何基于对布尔输入的某种逻辑计算确定布尔值输出。它们在复杂性理论的问题和数字计算机的芯片设计中扮演基础角色。布尔函数的性质在密码学中扮演关键角色,特别是在对称密钥算法的设计中(参见S-box)。在数学中,有限布尔函数是如下形式的函数f : Bk → B,这里的B = {0, 1}是布尔域,而k是非负整数。在k = 0的情况下,函数简单的是B的一个恒定元素。更一般的说,形如f : X → B函数,这里的X是任意集合,是布尔值函数。如果X = M = {1, 2, 3, …},则f是“二进制序列”,就是说0和1的无限序列。如果X = = {1, 2, 3, …, k},则f是长度为k的“二进制序列”有 2 2 k {displaystyle 2^{2^{k}}} 个这种函数。布尔函数可以唯一的写为积(AND)之和(XOR)。这叫做代数范式(ANF),也叫做Zhegalkin多项式。这里的 a 0 , a 1 , … , a 1 , 2 , … , n ∈ { 0 , 1 } ∗ {displaystyle a_{0},a_{1},ldots ,a_{1,2,ldots ,n}in {0,1}^{*}} 。 序列 a 0 , a 1 , … , a 1 , 2 , … , n {displaystyle a_{0},a_{1},ldots ,a_{1,2,ldots ,n}} 的值因此还唯一的表示一个布尔函数。布尔函数的代数次数被定义为出现在乘积项中的 x i {displaystyle x_{i}} 的最高次数。所以 f ( x 1 , x 2 , x 3 ) = x 1 + x 3 {displaystyle f(x_{1},x_{2},x_{3})=x_{1}+x_{3}} 有次数1(线性),而 f ( x 1 , x 2 , x 3 ) = x 1 + x 1 x 2 x 3 {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 ( x 2 , … , x n ) = f ( 0 , x 2 , … , x n ) {displaystyle g(x_{2},ldots ,x_{n})=f(0,x_{2},ldots ,x_{n})} 并且 h ( x 2 , … , x n ) = f ( 0 , x 2 , … , x n ) + f ( 1 , x 2 , … , x n ) {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)=xlor y} (逻辑或)的ANF:

相关

  • 兼性厌氧兼性厌氧菌是一类既可以进行有氧呼吸,也能够进行无氧呼吸或发酵的微生物。在氧气充足时,它们会通过有氧呼吸来产生ATP(三磷酸腺苷),但当氧气缺乏时,它们的呼吸方式就会变为无氧呼
  • 癌症疫苗癌症疫苗(英语:cancer vaccine)可以用来治疗或预防癌症,那些用来治疗已存在的癌症又被称作治疗性癌症疫苗。有些或很多疫苗是“自体”的,也就是说,它是从病人自己的身体中萃取的,所
  • 加拿大重水铀反应堆加拿大重水铀反应堆或称“CANDU反应堆”或是“坎度堆”,是加拿大原子能公司(英语:Atomic Energy of Canada Limited)、安大略水电公司(英语:Ontario Hydro)和加拿大通用电气(英语:Can
  • 临床流行病学临床流行病学是将流行病学知识应用于临床实践。从70年代以来开始盛行,循证医学是临床流行病学应用的表现。与一般的流行病学一样,临床流行病学也分为描述型和分析型两类。
  • Mo4d5 5s12, 8, 18, 13, 1蒸气压第一:684.3 kJ·mol−1 第二:1560 kJ·mol−1 第三:2618 kJ·mol主条目:钼的同位素钼(Molybdenum)是一种化学元素,它的化学符号是Mo,它的原子序数
  • 代谢中间产物代谢中间产物(英语:Metabolic intermediates)是指代谢途径中的中间产物。虽然这些中间产物通常对于细胞功能的影响相对较小,但他们可能在酵素的别构调节上,扮演重要的角色。有些
  • 苏格兰– 欧洲(绿色及深灰色)– 英国(绿色)苏格兰(英语、低地苏格兰语:Scotland,/ˈskɒt.lənd/;苏格兰盖尔语:Alba)是英国下属的构成国之一,位于大不列颠岛北部,英格兰之北,被大西洋环绕包
  • 内塞伯尔内塞伯尔(保加利亚语:Несебър、拉丁化:Nesebar)是保加利亚的一座历史古城,今天则是布尔加斯州的一个沿海度假城市。在色雷斯语中的名称是Menebria、现代希腊语中的名称是
  • 精子囊肿精子囊肿,或称精液囊肿、附睾囊肿,是睾丸网或附睾头部发生的一种潴留性囊肿,囊肿内含有精子。这种现象一般出现在青少年身上,一般是无痛的,也没有很大的危险性。而特大的精子囊肿
  • 真值表真值表是使用于逻辑中(特别是在连结逻辑代数、布尔函数和命题逻辑上)的一类数学用表,用来计算逻辑表示式在每种论证(即每种逻辑变数取值的组合)上的值。尤其是,真值表可以用来判断