多元逻辑函数的基础等价变值表示

开篇：润墨网以专业的文秘视角，为您筛选了一篇多元逻辑函数的基础等价变值表示范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要: 传统的逻辑函数表示以AND-OR和OR-AND这2种逻辑函数标准范式为代表.基于变值逻辑体系，描述了一类基础等价变值表示，将经典的多元逻辑表达式转化成为变值等价表示形式.选择二元0-1函数集合列表，按真值和变值表示作为典型示例，并给出了2个函数表示结果.

关键词: 逻辑函数;变值体系;等价逻辑表示

中图分类号:O 141 文献标志码:A 文章编号:1672-8513(2011)05-0396-02

Equivalent Expressions of Multiple-Variable Logic and Variant Logic Functions

ZHENG Jeffrey

（Department of Information Security,School of Software,Yunnan University, Kunming 650091, China）

Abstract: Classical logic equations are normally expressed as two canonical forms: AND-OR and OR-AND expressions. Using the variant logic principle, a new form of logic expression is described to express multiple logic functions as equivalent variant logic forms. Two variable functions are selected as typical cases, while sample functions are used in representations.

Key words: logic function; variant logic; equivalent expression

在经典的逻辑中有2种标准范式表示方法［1-2］处理各类函数.为方便转化处理，需要将n元逻辑集合全体按照各个函数编号，顺序以行按位展开，形成一个具有2n列和22n行0-1真值总表.利用完整真值表示结构，选择1项形成AND-OR范式，或者选择0项形成OR-AND范式群集.从等价逻辑表示的角度，选择其它的扩展算符，[JP2]不同的对应关系可能通过经典真值总表建立起对应的表示关系.[JP]

变值逻辑体系是基于0-1逻辑的理论结构［3-5］，通过扩展经典0-1逻辑的∩,∪,运算形成的表示体系.在已有3种基本逻辑运算基础上，再增加2种基本运算，分别为置换P和互补Δ.在这样的扩展模式下，变值体系包含5个基本算符∩,∪,,P,Δ.

[HJ1.75mm]

由于基础等价变值表示，不需要考虑置换算符P的影响，本文仅需要处理Δ算符的变化：Δ=Δ2n－1...ΔI...Δ0，ΔI∈B2=0,1，Δ∈B2n2，ΔI作用在第I列向量位值上，当ΔI=0时，将第I列向量位值反转，各自从01，10；而当ΔI=1时，整个列向量位值保持不变.

对n元变量x=xn-1…xi…x0，0≤i＜n,xi∈{0,1}=B2.令在n元变量中的第j位为选定特征位，0≤j

[FL(2K2]

Sj0(n)={x|xj=0,x∈Bn2} ,

Sj1(n)={x|xj=1,x∈Bn2} ,

S(n)={Sj0(n),Sj1(n)} .

对给定函数f，通过选择特征位的输入/输出序对的取值关系，确定4个基元逻辑函数{f,f+,f－,fT}如下：

f(x)={f(x)|x∈Sj0(n),y=0}，

f+(x)={f(x)|x∈Sj0(n),y=1}，

f-(x)={f(x)|x∈Sj1(n),y=0}，

fT(x)={f(x)|x∈Sj1(n),y=1}.

在传统的2类标准逻辑范式表示中，AND-OR范式通过选择基元函数集合{f+(x),fT(x)}作为y=1项集合，以真值表达式的形式来实现；而OR-AND范式则是通过选择基元函数集合{f－(x),f(x)}作为y=0项集合，作为假值表达式的形式来实现.在基元函数集合{fT(x),f(x)}之中，特征和输出取值xj=y是等同的，从输入/输出序对取值的角度，数值保持不变.

当选择基元函数集合{f+(x),f－(x)}时，xj≠y形成基础变值逻辑表示.

令f(x)=〈f+|x|f－〉为变值逻辑表示，在〈f+|x|f－〉表示结构中，f+从Sj0(n)中选择1项集合为AND-OR表达式形式，而f－部分从Sj1(n)中选择0项集合为OR-AND表达式形式.在变值表示中，2个投影函数与基元函数之间的关系是f(x)=〈f+|x|f-〉，f+(x)=〈f+|x|〉，f-(x)=〈|x|f-〉.

为方便理解变值表示，下面利用2变量的逻辑函数全体，将其16个函数的标准真值集合表达式和等价的变值集合表达式在表1中并排1-1列出.在表1中，n=2,j=0,S(2)={11,10,01,00}={3,2,1,0}分别为二进制和整数集合表示，对应的2个子集合为S00(2)={10,00}={2,0},S01(2)={11,01}={3,1}.

特征向量的互补运算定义为：对δ∈B2，

zδ=z,δ=1 ,z,δ=0 .

特征向量的互补运算作用在基元状态对应的整个列上，整列的0-1数值都会受到算符的影响.在对应的表示下，变值函数表达式在表1中给出.

从表1中，分别检查f=3和f=6这2个函数及其对应的基础变值等价表示：

f=3:=〈0|3〉,f+=11:〈0|〉,f-=2:=〈|3〉 .

f=6:=〈2|3〉,f+=14:〈2|〉,f-=2:=〈|3〉 .

通过查阅变值总表，任意函数能确定在变值条件下唯一的基础等价表示形式，由于f+和f－为2个投影函数也同样包含在相同的表中，标准函数表示都能从对应的等价函数表示中找到.

观察变值逻辑体系表示的基础对应关系，任意的逻辑函数，根据不同的Δ选择，形成不同的等价变值表示对应形式.这类在泛函分析中同广义函数描述特征相对应的附加群集特性，将为实际利用等价变值表示方法解决复杂大系统逻辑优化方面的问题提供新的工具［6-9］.整个变值体系包含众多的精巧作用原理和方法，除了直接选择f+和f－的表达形式之外，其它的不同等价表示模式和优化应用方法将在后续的文章中逐步进行描述.

参考文献:

［1］LEE S C. Modern switching theory and digital design［M］. New Jersey:Prentice-Hall, 1978.

［2］杨炳儒.布尔代数及其泛化结构 ［M］. 北京:科学出版社，2008.

［3］ ZHENG J，ZHENG C，KUNII T L. A framework of variant-logic construction for cellular automata,cellular automata-Innovative modelling for science and engineering ［M/OL］//SALCIDO A.Cellular automata-innovative modeling for science and engineering.Rijeka:InTech Press, 2011: 325-352. www.省略/articles/show/title/a-framework-of-variant-logic-construction-for-cellular-automata.

［4］[ZK(#]LI Q, ZHENG J. 2D spatial distributions for measures of random sequences using conjugate maps［C/OL］//11th Australian Information Warfare Conference. Edith Cowan University:Research Online,2010.ro.ecu.edu.au/isw/34.

［5］ ZHENG J，ZHENG C H. A framework to express variant and invariant functional spaces for binary logic［J/OL］. Frontiers of Electrical and Electronic Engineering in China, 2010,5(2):163-172. www.省略/content/91474403127n446u/.

［6］FEYNMAN R. The character of physical law［M］.Cambridge: The MIT Press,2001.

［7］HAWKING S, MLODINOW L. The grand design［M］. New York:Bantam Books, 2010.

［8］NEUMANN J V. Mathematical foundations of quantum mechanics［M］.Princeton:Princeton University Press, 1996.

［9］PENROSE R. The road to reality: a complete guide to the laws of the universe ［M］. London: Vintage Books, 2004.

收稿日期:2011-05-20.

基金项目:云南省信息安全特色专业建设基金（X3108042）；云南省软件工程重点实验室建设基金.

作者简介:郑智捷（1956-），男，澳大利亚籍，博士，教授，云南大学软件学院信息安全系主任，中国自然科学基金委信息科学部海外评审专家、杰出青年和创新团队项目评委.主要研究方向：信息系统安全、量子密码、物理基础理论、分层结构化设计模式方法等.