布尔函数

✍ dations ◷ 2025-04-03 14:42:40 #布尔函数
在数学中,布尔函数(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:

相关

  • 醋(英语:Vinegar),旧称为醯、苦酒等,是烹饪中常用的一种液体酸味调味料。醋的成分通常含有3%-5%的醋酸,有的还有少量的酒石酸、柠檬酸等。理论上讲,几乎任何含有糖分的液体都可以发
  • 肠道沙门氏菌肠道沙门氏菌(学名:Salmonella enterica)是一种有鞭毛的革兰氏阴性菌及沙门氏菌属的一员。肠道沙门氏菌有着极其大量的血清型:大约有2000个不同的血清型。就如伤寒杆菌(学名Salmo
  • 塞拉利昂特别法庭塞拉利昂特别法庭(英语:Special Court for Sierra Leone,縮寫SCSL),是一个由塞拉利昂政府(英语:government of Sierra Leone)和联合国建立的司法机关,目的是审判在1996年11月30日以后
  • 加速器驱动次临界反应堆加速器驱动次临界反应堆(又称加速器驱动次临界系统,Accelerator driven sub-critical reactor,ADS)是一种利用加速器加速的质子束流轰击重核靶材产生的外源中子驱动次临界反应
  • 玻尔效应玻尔效应(英语:Bohr effect),1904年由丹麦生理学家克里斯蒂安·玻尔首先提出,即:氢离子(低 pH)和二氧化碳会降低血红蛋白与氧气的亲和力,促进血红蛋白释放氧气。产生该效应的原因为质
  • 伊本·阿拉比伊本·阿拉比(阿拉伯语:أبو عبد الله محمد بن علي بن محمد بن عربي الحاتمي الطائي‎,西班牙语:Abenarabi,1165年-1240年)是一个安达
  • 李希梅尔里西梅尔(Ricimer,或译李希梅尔,约405年-472年),苏维汇人,在5世纪中的西罗马帝国掌握政治实权多年。他青年时期在埃提乌斯军队服役,父母都是蛮族。450年进入政治界。472年,里西梅尔去
  • 游戏模块游戏模组,英文多简称为“MOD”、“Mod”(全称“Modification”),“修改”的名词含义。MOD通常对应可以修改的电子游戏,因此以电脑游戏为主。必须依赖与原作品方可执行游玩。游戏
  • 临床研究临床研究(Clinical research)是医疗科学的分支,确认药物、医疗设备、诊断及治疗的安全性及效能,这可以用来预防、治疗、诊断或是缓解疾病中的症状。临床研究和临床实践(clinical
  • 躯干躯干是动物或人类身体的轴心。动物身体除了头颈部及肢体(包括翼、鳍)外,皆属躯干。人体躯干包括以横膈膜分界的胸部及腹部,包含了重要的身体器官。人体躯干正面由胸部及腹部组成