布尔函数

✍ dations ◷ 2025-04-04 05:22:53 #布尔函数
在数学中,布尔函数(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:

相关

  • 蠕虫病蠕虫病,也称为蠕虫感染,是人和其他动物一部分身体被寄生蠕虫感染导致的一种巨噬细胞疾病。这些寄生虫种类很多,大致分为绦虫、吸虫和线虫。它们通常生活在宿主的胃肠道中,但也可
  • 润肤剂润肤膏,是一种日用品,功能是润肤及护肤。润肤膏由天然物料或者石油等化学物料合成。在商品市场上定位为化妆品或药品。润肤膏在冬日令皮肤避免干燥损伤。润肤膏保持皮肤湿润,可
  • ACEI血管紧张肽I转化酶抑制剂(英语:ACE inhibitor,简称为ACEI)是一类抗高血压药。血管紧张素转化酶(ACE)是肾素-血管紧张素-醛固酮(RAA)系统中的一个重要环节,该系统对血压的调节有着及其
  • 骑士骑士或称武士,原为欧洲中世纪受过正规军事训练的骑兵,后来成为一种贵族阶层。骑士的头衔来自另一位骑士或是领主的册封,骑士除了能获得自己的封地之外,也必须为所效忠的领主作战
  • 扩展元素周期表目前的元素周期表中有七个周期,并以118号元素鿫(Og)终结。如果有更高原子序数的元素被发现,则它将会被置于第八周期、甚至第九周期。这额外的周期预期将会比第七周期容纳更多的
  • 塔梅县塔梅县(越南语:Huyện Tháp Mười)是越南同塔省下辖的一个县,位于同塔梅平原,此地多芦苇。1976年,美安县并入高岭县,隶属同塔省。1981年1月5日,高岭县以兴盛社、美安社、美和社、
  • 割礼割礼(又名包皮切割),天主教名割损,是一种宗教仪式,通常是指对男孩施行的割礼,方法是把阴茎上的包皮割去。早期的山洞壁画和古埃及坟穴已有关于割礼的描述,中东的不少宗教也有施行割
  • 十二指肠溃疡消化性溃疡(英语:peptic ulcer disease,简称PUD),又称胃及十二指肠溃疡。这是指胃、小肠前段(十二指肠)或幽门,有时也包含了食道下端的黏膜损伤(溃疡)。在胃发生的溃疡称作胃溃疡(英语:s
  • 凡士林凡士林(英语:Vaseline)是一种石油胶(英语:petroleum jelly)(石化制胶状物)的通用商标,同时亦为联合利华所生产的个人清洁用品、除臭用品、体香剂、润肤霜与润滑剂品牌。凡士林的最早
  • 双及物动词在语法学上,双及物动词是需要支配一个主词及两个受词的动词。此与支配单个受词的单及物动词相对。1.双及物结构的语义表达研究,外语教学与研究,2009.1