逻辑度量空间中的仿射变换和几类特殊公式的性态研究及其应用

【作者】 王庆平；

【导师】 王国俊；

【作者基本信息】 陕西师范大学 ， 基础数学， 2012， 博士

【摘要】 计量逻辑学从基本概念的程度化入手,系统地引入了公式的真度理论和公式间的相似度理论,定义了公式间的伪距离,最终建立起了逻辑度量空间(Logic Metric Space,简称LMS)理论.由于有了度量工具,在LMS中就可以研究给定的逻辑理论r的发散度和相容度问题,可以研究各种类型的近似推理问题,等等.当前LMS理论已从经典的二值命题逻辑推广到了多种n值命题逻辑之中(n>2).值得注意的是,作为度量空间,LMS自身结构的研究似尚未展开.最近已见到从反射变换入手探讨经典LMS结构的研究,虽然只是起步性的研究,但却是一个新的开端.本文将上述研究进行推广,进一步研究经典LMS中的仿射变换问题,得到了包括真度不变性和相似度不变性在内的较为系统的研究成果.同时,本文还将经典LMS中的反射变换理论推广到了(?)*-Lindenbaum代数之中.另一方面,由于布尔函数理论既是经典LMS中真度理论的基础,又是密码学中常用的基本工具,可见计量逻辑学与密码学之间存在着紧密的联系.基于这种思想,本文在LMS中先后引入了线性逻辑公式、对称逻辑公式和雪崩逻辑公式的概念,并从它们在整个空间中的分布得出了各类公式稀疏程度的描述,这又可反馈到密码学中,使得从事密码学研究的学者对是否使用相应的函数传送密码有更全面的掌握.此外,本文还将布尔函数的Shannon展开式的巧妙思想应用到了Lukasiewicz n值逻辑系统Ln中,给出了MaNaughton函数的表示方法,解决了m元n值MaN-aughton函数的计数问题.全文共分五章.第一章介绍了有关计量逻辑学与密码学中布尔函数的基本知识,这些知识是阅读后续内容所必须的,是概述性的.第二章首先将反射变换的概念引入到连续值逻辑系统￡*之中,研究了￡*逻辑度量空间中反射变换的性质.然后将仿射变换的概念引入到经典逻辑系统之中,定义了公式集F(S)到F(S)上的仿射变换φ,证明了该仿射变换φ：F(S)→F(S)是F(S)上的自同构变换.而且公式的真度,公式间的相似度与伪距离在仿射变换下保持不变.在经典逻辑系统中,反射变换是仿射变换的特殊情形,即,仿射变换是公式集F(S)到F(S)上的一类更广泛的变换.第三章基于线性布尔函数的概念,在经典逻辑度量空间中提出了线性逻辑公式的概念,并给出了n元线性逻辑公式的构造方法.研究了反射变换下线性逻辑公式的性质,证明了所有线性逻辑公式的真度等于1/2,而全体n元逻辑公式的真度共有2n+1种之多,这表明线性逻辑公式在全体逻辑公式之中的分布很稀疏.这就从计量学的角度验证了线性布尔函数的结构比较简单.而且,我们可以通过线性布尔函数作乘积得到一类代数次数等于k的布尔函数,这类布尔函数所对应的逻辑公式的真度为1/2k,这表明这类代数次数等于k的非线性布尔函数所对应的逻辑公式在全体逻辑公式之中的分布也很稀疏,可在密码设计中使用该类布尔函数.第四章将符号化计算树逻辑中的Shannon展开式做了推广,在n值Lukasiewicz逻辑系统L。中,研究了由逻辑公式导出的n值McNaughton函数的展开式,给出了m元n值McNaughton函数的准析取范式和准合取范式.在此基础上,给出了m元n值McNaughton函数的计数问题.并在n值Lukasiewicz逻辑系统Ln中,给出了m元逻辑公式的构造方法及其逻辑等价类的计数问题.在弄清楚了多值McNaughton函数的构造方法和结构之后,我们将对称布尔函数的概念引入到多值McNaughton函数之中,提出了对称三值McNaughton函数的概念.在此基础上,在三值Lukasiewicz逻辑系统L3中,提出了对称逻辑公式和准对称逻辑公式的定义.研究了在逻辑等价意义下对称逻辑公式的性质,比较了L3和经典逻辑系统L中对称逻辑公式之间的关系及其计数问题,证明了n元对称逻辑公式占全体n元逻辑公式的比例随n的增大而趋向于零,而且全体对称逻辑公式的真度之集在[0,1]中稠密.但是,全体对称逻辑公式之集又是逻辑度量空间中的无处稠密集.最后,给出了L3中对称逻辑公式的构造方法.第五章将密码学中满足严格雪崩准则的布尔函数的概念引入到计量逻辑学之中,提出了雪崩逻辑公式的概念,并研究了雪崩逻辑公式的真度及其性质.证明了雪崩逻辑公式A的真度T(A)满足条件1/4≤τ(A)≤3/4特别是证明了至少含有三个原子公式的雪崩逻辑公式的真度之集为H1={k/2n-1|2n-3≤k≤3×2n-3;n-3,4,…},或者用密码学的术语来说,n(n≥3)元雪崩布尔函数的汉明重量之集为w(n)={ω(f(x))|2n…2≤ω(f(x))≤3×2n-2且ω(F(x))为偶数},这就排除了不满足此条件的n元布尔函数的个数计算,从而在一定程度上简化了雪崩布尔函数的计数问题.然后,我们通过引入函数ξ建立了n(n≥3)元雪崩布尔函数个数的表达式,并给出了不同真度的雪崩逻辑公式的构造方法.研究了k阶雪崩逻辑公式与反射变换下k阶雪崩逻辑公式的性质.最后,研究了满足严格雪崩准则的布尔函数的计数问题,得到了满足严格雪崩准则的n元布尔函数个数的上界和下界.更多还原

【Abstract】 In Quantitative Logic, truth degree of formulas and similarity degree between formulas are systematically introduced through establishing graded versions of basic logical notions. Meanwhile the pseudo-distance between formulas is constructed and theory of the logic metric space (LMS for short) is established correspondingly. Based on these, one can further discuss the divergency degree and consistency degree of a logical theory Γ and several types of approximate reasoning can be studied in LMS. Up to the present, the theory of LMS has been generalized from classical two-valued propositional logic to many kinds of n-valued propositional logics (n>2).It is worth noting that the theory of the structure of LMS, as a metric space, has not been thoroughly developed. However, some discussion about reflexive trans-formations in classical LMS has been found recently and seems to be a new beginning of research on the structure of LMS although not mature. To furtherly develop this idea, the present paper studies the affine transformations and obtains that the con-cepts of truth degree as well as similarity degree keep unchanged under the affine transformations. Meanwhile, the theory of reflexive transformations is generalized into (?)*-Lindenbaum algebra.On the other hand, since the theory of Boolean functions sets a foundation for the concept of truth degree in classical LMS and also plays an important part in cryptog-raphy, one can see that the relationship between Quantitative Logic and cryptography seems very close in the sense. Based on this thought, the concepts of linear logic formu-las, symmetric logic formulas as well as avalanche logic formulas of LMS are proposed in this paper one after another, and the sparse degree of these formulas is obtained through their distribution in the whole space. More importantly, these results can be fed back to cryptography and offer useful informations for cryptographists during code transferring.Furthermore, the Shannon expansion of Boolean functions is applied to n-valued Lukasiewicz logic system Ln. The methods of expressing McNaughton functions are given and counting problem of m-ary n-valued McNaughton functions is solved.The present paper is divided into5chapters.The first chapter overviews some basic knowledge about Quantitative Logic and Boolean function in cryptography, which are preparatory for the latter chapters.Chapter2firstly gives a reflexive transformation in logic system (?)*. And the properties of reflexive transformation are studied in (?)*logic metric space. Then the concept of affine transformation is introduced into the classical logic system. The definition of affine transformation Φ on F(S) is proposed, which is proved to be an automorphism of F(S). It is obtained that the concepts of truth degree, similarity degree as well as pseudo-distance keep unchanged under the affine transformation Φ. In the classical logic system, the affine transformation is a new transformation with reflexive transformation being its special case.Based on the concept of linear Boolean functions in cryptology, Chapter3gives the concept of linear logic formulas in classical logic metric space. And methods of construction of n-ary linear logic formulas are given. In classical logic metric space, the properties of linear logic formulas under reflexive transformation are studied. It is proved that the truth degrees of all linear logic formulae are equal to1/2. However there are2n+1kinds of truth degrees to all Boolean functions which contain n variables. This shows that the distribution of linear logic formulas in all logic formulas is sparse. This also verifies from the theory of Quantitative Logic that the structure of linear Boolean function is relatively simple. Then a kind of Boolean functions of degree equaling to k can be obtained by multiplying k linear Boolean functions. It is also proved that the truth degree of logic formulas corresponding to this kind of Boolean functions is equal to1/2k. This shows that the distribution of logic formulas corresponding to this kind of Boolean functions of degree equaling to k in all logic formulas is sparse. Hence this kind of Boolean functions can be used in cryptography.Chapter4generalizes Shannon expansion in symbolic computation tree logic. In n-valued Lukasiewicz logic system, the expansion of n-valued McNaughton func-tions which are induced by logical formulas are studied. The quasi disjunctive normal form and quasi conjunctive normal form of m-ary n-valued McNaughton functions are given. Then the counting problems of m-ary n-valued McNaughton functions are solved. In n-valued Lukasiewicz logic system, the construction of formulas and counting problems of their logic equivalence class are solved.As the method of construction of many-valued McNaughton functions is given, we propose the concept of symmetric three-valued McNaughton functions. Then the concepts of symmetric logic formulas and pseudo-symmetric logic formulas are given in three valued Lukasiewicz logic system L3. The properties of symmetric logic formulas under logically equivalence are studied. The relationship of symmetric logic formulas in L3and classical logical system L, and the number of them are given. It is proved that the ratio of the number of symmetric formulas with n atoms over the number of all formulas with n atoms converges to zero when n tends to infinite. It is also proved that the set of truth degrees of symmetric logic formulas is dense in [0,1]. On the other hand, the set consisting of all symmetric logic formulas is a nowhere-dense set in the logic metric space. Finally, the construction of symmetric logic formulas in L3is given.Chapter5introduces the concept of Boolean functions satisfying strict avalanche criterion in cryptology into Quantitative Logic. The concept of avalanche logic formu-las is proposed. The truth degree of avalanche logic formulas and its properties are studied. It is proved that the truth degree τ(A) of avalanche logic formula A satisfies following equation1/4≤τ(A)≤3/4. In particularly, it is proved that the set of truth degrees of avalanche logic formulas which contain at least three atom formulas is H1={k/2n-1|2n-3≤k≤3×2n-3;n-3,4,…}, Using cryptography terms, the set of Hamming weight of n-ary (n≥3) Boolean functions satisfying strict avalanche criterion is w(n)={ω(f(x))|2n…2≤ω(f(x))≤3×2n-2, and ω(f(x)) is even number.}It can simplify the counting problem of avalanche Boolean functions through excluding the number of Boolean functions which do not satisfy this condition. Then, a formula for calculating the total number of n-ary (n≥3) avalanche Boolean functions is established by means of a newly introduced function ζ, and a method of construction of avalanche logic formulas are given. Finally, the properties of avalanche logic formulas of order k under reflexive transformation are studied. The upper and lower bounds of the number of Boolean functions satisfying strict avalanche criterion are obtained.更多还原