计量逻辑学中的旋转对称逻辑公式

《计量逻辑学中的旋转对称逻辑公式》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第29卷第2模糊系统与数学Vo1．29．No．22()15印4J】FuzzySystemsandMathematicsApr．，2O15文章编号：l001—7402(2015)02—0062—06计量逻辑学中的旋转对称逻辑公式李骏，何金龙(兰州理工大学理学院，甘肃兰州730050)摘要：密码学中的旋转对称布尔函数是一类具有多输入单输出性质的函数，本文以此类函数为基础提出了旋转对称逻辑公式的概念。初步研究了此类公式的性质，并给出了此类公式真度的轨道刻画。接着给出了全体旋转对称公式等价类的个数统计。最后证明了

2、旋转对称逻辑公式经过反射变换后得到的公式依然是旋转对称逻辑公式。关键词：旋转对称逻辑公式；旋转对称布尔函数；真度；轨道；反射变换中图分类号：O141文献标识码：A1引言由于数理逻辑的高度符号化和形式化，计量逻辑学从对基本概念的程度化人手，将数值计算的思想引入到数理逻辑中，提出了公式的真度的概念，又以真度为基础提出了公式间的相似度和伪距离，建立了逻辑度量空间，进而提出了一套完整的近似推理机制并引发了大量的研究成果口]。布尔函数是数理逻辑中的重要概念，它在密码学的研究中也发挥着重要作用，利用布尔函数实现密码学

3、与逻辑学的交叉研究是一个有吸引力的研究课题，如文献[10]在引入密码学中对称布尔函数的概念后，提出了对称逻辑公式和准对称逻辑公式的概念，最后在拓扑学的观点下证明了全体对称公式之集在经典逻辑度量空间中无处稠密，文献[11]将密码学中线性布尔函数的概念引入到了经典逻辑中提出了线性逻辑公式的概念，并研究了反射变换下线性逻辑公式的性质，文献[12—13]将密码学中满足严格雪崩准则的布尔函数的概念引入到计量逻辑学中提出了雪崩逻辑公式的概念，给出了雪崩逻辑公式的构造，并研究了反射变换下雪崩逻辑公式的相关性质，这些研究

4、成果初步建立了密码学与逻辑学之间的联系，也使得借助逻辑学来研究密码学成为可能。旋转对称布尔函数最初是在研究Hash算法的快速实现时提出的，它是一类具有良好性质的多输入单输出布尔函数，并且在密码学的研究中扮演重要角色l_1。本文将旋转对称布尔函数引入到计量逻辑学中，提出了旋转对称逻辑公式的概念，给出了旋转对称逻辑公式真度的轨道刻画，解决了全体旋转对称逻辑公式中等价类的计数问题，证明了旋转对称逻辑公式经过反射变换后得到的公式依然是旋转对称逻辑公式。2预备知识定义2．1[1称映射f：{0，1)一{0，1)为元布

5、尔函数，记为厂()，其中zE{0，l收稿日期：2Ol3-12—31基金项目：国家自然科学基金资助项目(11261032)作者简介：李骏，兰州理工大学理学院副教授，博士，研究方向：不确定性推理，非经典数理逻辑；何金龙，兰州理工大学理学院研究生，研究方向：不确定性推理，非经典数理逻辑。第2期李骏，何金龙：计量逻辑学中的旋转对称逻辑公式定义2．2E对向量(z”，z)中分量曩，其中1≤i≤n，且1≤k≤，定义五cz一j一：n，’z十萋／Lx,+k而V(z··z)∈{0，1}，我们扩展以上定义为(一，z)一((z)

6、，⋯，(z))。定义2．3[州设厂是一个元布尔函数，若V∈{0，1)”和Vk(1≤志≤)，都有厂((z))一f(sc)，则称f(sc)为旋转对称布尔函数。令G()一{(z)l1≤忌≤}表示由向量生成的轨道。将{0，1}中轨道的个数记为g，则阶循环群{(z)I1≤志≤)将{0，1)分成g个互不相交的轨道G(z)，即{0，1}===UG(z)，且当i≠时，G(z)nG(，)一．其中G(z)中元素的个数1G(五)1为的因子，称lG(蕾)I一的轨道为长圈；称IG(墨)I—d(d<，dl)的轨道为短圈。记R为全体元

7、旋转对称布尔函数的集合。定义2．4E设原子命题集S一{P。，P，⋯}，F()是由生成的(一，一)型自由代数，称F()中元素为公式或命题，称S中的元素为原子公式或原子命题。定义2．5[1映射：F()一{0，1)，若是(一，一)型同态，即V(—A)一-7'0()，v(A—B)一()一V(B)则称V为F()的赋值，()也称为公式的赋值。记为F(S)的全体赋值之集。定义2．6L】设公式，B∈F()，(i)如果V∈力，均有()一1，则称A为重言式，记作}A；如果V∈，均有()一0，则称为矛盾式。(ii)如果V∈，均

8、有(A)一(B)，则称A与B逻辑等价，记作A≈B．定义2．7E妇设是含有个原子命题的公式，记为A(p一，P)，它是由逻辑连接词一，一，V，八连接而成。设(z”，z)∈{0，1)，分别用z“，取代A(p”，P)中的P“，P，且对_．7，一，V，^解释为1O一1，]1—0；1一z2—0当且仅当z1—1，2—0；z1V2一max(x1，z)；l^z。=min(x，z)，这样得到的一个元函数，叫作公式诱导出的布尔函数，记为A(x“，z