程序逻辑结构设计

程序逻辑结构设计（共7篇）

程序逻辑结构设计 篇1

0 引言

机器学习的目标是从大量的经验数据中抽取出一般的判定规则和模式。传统的机器学习方法,如自顶向下的决策树家族[1],虽然取得了长足的进步和成功的应用[2],但其主要局限在命题逻辑(即属性-值表示)的框架内。随着机器学习应用领域的不断拓展,传统的机器学习方法已经不能满足实际应用的需求,主要体现在两个方面:一方面,命题逻辑的描述能力弱,包括对经验数据的描述和对规则的描述。在命题逻辑中,数据的描述和规则的描述都采用属性-值的形式。但这一描述方式却不适于描述复杂的对象,也不能刻画属性-值间的本质关系。因此,在涉及复杂对象间关系的学习任务中,属性-值表示在对象的描述和规则的描述方面存在着巨大的障碍。另一方面,知识的获取并不都是单纯地只从原始数据中获得。在人类获得知识的过程中,常常需要或多或少地利用已掌握的相关知识,即本文研究中所说的背景知识(background)。由于这些背景知识通常采用更具表达力的一阶谓词逻辑来描述,因此,传统的机器学习方法不便利用相关的背景知识[3]。在这种情况下,归纳逻辑程序设计(Inductive Logic Programming,ILP)应运而生。

ILP是机器学习与逻辑程序设计相结合而形成的新的研究领域[4]。ILP继承了逻辑程序设计坚实的理论基础,承续了机器学习实验的方法和面向应用的方向,采用比命题逻辑更具表达力的一阶谓词逻辑表示经验数据和学习到的规则,而且可以非常自然地利用背景知识。ILP克服了传统机器学习方法的两个主要限制:描述能力的限制和背景知识利用的限制,为机器学习提供了更深入的理论和方法,为知识工程等人工智能的应用领域提供了新的强有力的技术支持,成为机器学习的前沿研究课题。

一阶谓词逻辑表示机制使得ILP在无法用属性-值表示的领域取得了广泛的应用,这些领域包括植物生物学[5],蛋白质远程同源检测[6],共指消解问题[7],机器翻译[8],医学图像挖掘[9],多关系数据挖掘[10,11],符号识别[12],新陈代谢网络[13],化妆品产品选择[14],建筑结构规则[15]等。

1 ILP的问题背景(problem setting)描述

当前的ILP文献根据研究的侧重点不同,给出的ILP的问题背景的描述也有所不同。根据有无训练实例可分为两大类[3]:正规问题背景(Normal problem setting)和非单调问题背景(non-monotonic problem setting)。

1.1 正规问题背景

定义1正规问题背景

给定正例集E+、反例集E-(均为子句的集合)和背景知识B(子句有限集),寻找满足以下四个条件的假设H(子句有限集):

正规问题背景是ILP的最常见情况,其中的后验充分性也称为相对于正实例是完备的,后验满足性也称为与反实例是一致的。

在大多数的ILP系统中,背景知识和假设都被限定为是有定的,这样的问题背景也被称为有定问题背景。有定子句理论构建了唯一的最小Herbrand模型,因此与正规问题背景相比,有定问题背景要简单一些。

定义2有定问题背景

给定正例集E+、反例集E-(均为子句的集合)和背景知识B(有定子句有限集),寻找满足以下四个条件的假设H(有定子句有限集):

在有定问题背景的前提下,限定实例为基本事实,得到的则是实例问题背景。

1.2 非单调问题背景

在非单调问题背景下,实例是空的,背景知识是有定子句集,假设是由组成背景知识的字母表构成的一般子句集。实例为空的原因是正实例可以看成是背景知识,反实例可以通过封闭世界假设得到。

定义3非单调问题背景

给定背景知识B(有定子句有限集),寻找满足以下3个条件的假设H(由B的字母表组成的任意子句集):

(2)完备性(Completeness):若一般子句g在M+(B)中为真,则H|=g;

(3)最小性(Minimality):不存在H的真子集G满足有效性和完备性。

有效性保证了假设中的所有子句在背景知识中都成立,完备性保证了H逻辑蕴含所有在背景知识的最小Herbrand模型中成立的子句,最小性保证了最终得到一个没有冗余的假设。

2 归纳逻辑程序设计方法的研究现状

随着ILP研究的不断深入,各种ILP系统已陆续开发出来。根据学习系统在假设空间上的搜索方向,ILP学习方法可分为自顶向下(Top-Down)的方法和自底向上(Bottom-Up)的方法。自顶向下和自底向上分别对应ILP的两个基本技术,即特化技术和泛化技术。自顶向下的ILP系统从最一般的(体为空)子句开始,以特殊化为基本操作进行搜索。自底向上的方法从最特殊的假设(训练实例)开始,以泛化为基本操作得到最终的假设。特化技术比泛化技术更适合处理噪音问题,因为自顶向下的方法可以用启发函数直接方便地指导搜索。目前,还提出了自顶向下和自底向上相结合的方法及与其他成熟方法的结合。

2.1 自顶向下方法

自顶向下的方法从一个最一般的子句(体为空,头为要学习的谓词的子句)开始,对其执行某种特殊化操作,得到一个新的子句集,然后根据某种搜索策略在新的子句集中选择某个或某些子句,用其替换当前的某个或某些子句,重复以上过程,直至得到的子句满足终止条件为止。

在θ包含格下,主要有两种特殊化的操作:增加一个文字到子句体中;对子句执行置换操作。

目前的搜索策略主要分为盲目搜索策略和启发式搜索策略两类,其中,盲目搜索策略包括深度优先搜索策略、广度优先搜索策略等,启发式搜索包括最佳优先搜索策略、爬山法搜索策略和柱状搜索(beam search)策略等。

自顶向下方法从最一般的假设开始,使用特化操作搜索,后继假设的形成只与当前假设的语法有关,而与实例集无关,因而该方法更适合处理噪声数据,但由于搜索空间庞大,因此该方法效率不高。该方法最有代表性的系统是Shapiro的MIS[16]和Quinlan的FOIL[17]。

MIS从一个最一般的假设开始,采用广度优先的方式搜索当前假设的所有后继假设,逐步形成更复杂的子句。由于该方法是盲目搜索的,Shapiro无法证明该方法能够在合理的时间限制内学习到与“quick-sort”同样复杂的递归子句。

FOIL是一个基于封闭世界假设的高效系统,通过由信息熵作为标准指导的从一般到特殊的启发式搜索(爬山搜索策略),归纳学习不包含函数的一阶Horn子句。FOIL限定了背景知识为基本元组集,限定了单个子句包含的变量数和深度。虽然FOIL系统能够成功地学习机器学习领域的某些问题,但由于爬山搜索策略具有近视性(myopic),因此FOIL不能学习诸如乘法这一类的谓词。

1991~1996年,Deroski,Quinlan等分别在FOIL的基础上进一步推出了m FOIL[18],FOIDL[19],FFOIL[20]等。

2.2 自底向上方法

自底向上的方法利用逻辑程序设计理论对实例进行泛化,从而避免了搜索整个假设空间,但对子句集进行泛化需要付出很大的代价,且不适合处理噪声数据。目前主要有三种泛化技术:逆归结(Inverse Resolution)、逆蕴涵(Inverse Entailment)、相对最小一般泛化(Relative Least General Generalisation)。

2.2.1 逆归结

归结推理是机器定理证明的核心手段,这一推理方式不仅有效而且是完备的。归纳可以看成是演绎的逆过程,因而取归结的逆过程(逆归结)进行归纳推理。

Muggleton首先在命题Horn理论上引入了基于逆归结的V操作和W操作,并在DUCE系统上实现了这些操作,用来学习命题Horn子句[21]。文献[22]证明了DUCE是归结定理证明器的逆过程,提出了下一步研究方向是将DUCE系统的命题知识表示形式扩展为一阶谓词逻辑表示形式。于是,Muggleton提出了一阶逻辑理论的V算子和W算子[23]。V算子是已知子句C1,C逆归结出子句C2,并且满足存在置换θ1,θ2,文字L1∈C1,L2∈C1,L1θ1=┓L2θ2使得C=邀C1-L1妖θ1∪邀C2-L2妖θ2。若L1为正文字,则称该V算子为吸收(absorption)算子,否则为识别(identification)算子。Muggleton给出了假定子句(C1-邀L1妖)θ1与子句(C2-邀L2妖)θ2不包含相同文字时的C2的形式并给出了求解算法。W算子是已知子句B1,B2,逆归结出子句B,C1,C2,并且满足B1,B2分别是C1,C2与A中同一文字L的归结结果,若A中参与归结的文字L为正文字,则该W算子为内部构建(inter-construction)算子,否则为外部构建(intra-construction)算子,同样也给出了有一定限制条件的A的形式和求解算法。由于文字L被归结掉了,因此逆归结时可以选择B1,B2中一个没有的谓词来构造L,所以W算子引入了新的谓词,也称为谓词发明(predicate invention)。W算子虽然可以学习更加复杂的对象(能够学习新的谓词),但在谓词发明时却要搜索巨大的新谓词空间。为此,文献[24]分析了谓词发明的逻辑背景,并根据实用性(utilisation)建立了一个偏序格,不需搜索整个谓词空间,就可以得到一个最保守的谓词。1991年,Muggleton给出了V算子和W算子的最特殊形式[4]。

使用该方法的代表系统有MARVIN[25]和CIGOL[23]。这两个系统都是利用逆归结学习一阶有定子句。Sakama讨论了逆归结的性质,并将其扩展到了正规逻辑程序(normal logic programs)[26]。

逆归结虽然取得了一些进展,还需要在以下三个方面进行深入的研究:

(1)噪声数据。目前,使用该方法的算法没有考虑噪声数据;

(2)时间。没有考虑构造假设的时间;

(3)不加限制的算子。系统在实现V算子或W算子时,都加上了一些限制条件,下一步是寻找不加任何限制条件实现V算子和W算子的算法。

2.2.2 逆蕴含

2.2.3 相对最小一般泛化

泛化的定义及泛化的求法是建立一个有效的符号学习系统的基础。1970年,Plotkin依据θ-包容(q-subsumption)来定义泛化,因为一般情况下,θ-包容的理论性质是:若Aθ-包含B,则A|=B,即A比B泛化。θ-包容建立了子句集泛化的偏序关系,在此关系上可以定义子句集的最小一般泛化(Least General Generalization),即偏序格上的最大下界[34]。1971年,Plotkin将LGG的概念推广到了相对最小一般泛化(Relative Least General Generalization),给出了RLGG的形式化定义及通过LGG求RLGG的方法,并给出了一个通过求RLGG进行学习的算法,但该算法存在以下问题[35,36]:

(1)背景知识是受限的有定子句形式。当背景知识任意时,RLGG不是有穷的;

(2)在最坏的情况下,RLGG包含的文字的个数为(n+1)m,n和m分别为背景知识和实例包含的基单元子句个数。当m很大时,无法构造RLGG;

(3)只能学习单子句目标。由于通过RLGG得到的是一个子句,因此由多个子句构成的目标不能学习。

Muggleton定义了扩展的背景知识(extensional background knowledge),扩展的背景知识是由原背景知识实现h次归结所得到的全部基单元子句组成,h由用户决定,从而解决了第一个问题;通过限定假设空间是ij-determinate子句类,解决了第二个问题;通过使用负实例来学习多子句的概念。

基于上述思想,Muggleton构建了Golem系统,使得该系统的RLGG泛化规模是训练样本的一个多项式,Golem成为有效地工作于大规模背景事实下的一个成功ILP系统[37]。

2.3 自顶向下与自底向上相结合

自顶向下的方法需要搜索大的假设空间,而且对变量的深度进行限定;自底向上的方法虽不用搜索巨大的假设空间,但进行泛化时代价较高,并且限定为确定(determinate)子句。ILP的研究者致力于将这两种方法结合在一起,类似传统机器学习方法,寻找变型空间。Zelle提出了自顶向下与自底向上相结合的算法CHILLIN,该算法已被成功地应用于学习自然语言分析的学习系统[38]。

2.4 与其他成熟方法的结合

归纳逻辑程序设计是机器学习和逻辑程序设计的一个交叉研究领域,以一阶逻辑为知识表示机制,其表达能力高于命题学习系统。归纳逻辑程序设计能处理命题逻辑无法表示的复杂的关系数据。然而,很多领域的知识都是用命题形式表示的,ILP系统要取得广泛的应用,就必须能有效地处理这些基于命题表示的学习领域的知识。

Roberts等人对归纳逻辑程序设计系统PROGOL、TILDE与传统的机器学习系统C4.5进行了实验比较,实验数据是基于命题表示形式的交通事故。实验结果表明:在预测精度上,PROGOL、TILDE略低于C4.5;在时间上,PROGOL比TILDE慢6倍,TILDE比C4.5慢100倍[39]。

因而,归纳逻辑程序设计研究者已试图将归纳逻辑程序设计方法同传统的机器学习方法结合起来。

(1)与遗传算法(GA)相结合

Mhigham和Mckay首先提出了将ILP的泛化和特化技术发展为重组(recombination)和变异(mutation)操作,以实现在整个搜索空间上进行直接搜索[40]。Wong等人给出了一个ILP与GA相结合的框架,该框架以逻辑语法为基础,实现了LOGENPRO系统,并与FOIL以及m FOIL进行了实验比较,在处理噪声数据时,某些情况下表现要强于FOIL和m FOIL[41]。Wong的方法在执行复制(reproduction)、交叉、变异等操作时,要保证产生的后代(子句)符合且实现规定的语法规则,效率则比较低。Tveit用向量表示个体,向量的长度依赖于背景知识和训练实例中变量的个数。搜索空间随问题规模成指数级增长。目标子句用向量表示,向量长度固定,而且无法用项来替换子句中的变量[42]。杨新武等人提出了基于变长位串表示的一阶规则挖掘算法GILP,该方法不预先设定向量长度,扩大了知识发现的范围[43]。TamaddoniNezhad等人提出了一个ILP与GA结合的新框架,用一个新的二进制表示机制定义子句,给出了该表示方法下的遗传操作算子和较快的评价机制[44,45]。2002年,TamaddoniNezhad等人又提出了在基因型层面进行评价的机制,在学习复杂问题时,效率更高[46]。

(2)与支持向量机(SVM)相结合

SVM是一种有坚实理论基础的新颖的小样本学习方法,因其基本上不涉及概率测度的定义及大数定律等,所以不同于现有的统计方法。从本质上看,该方法避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”(transductive inference),大大简化了通常的分类和回归等问题。

SVM方法又称为核方法或核机器,这是因为核的展开和计算是这一方法的关键。ILP研究者开始致力于研究ILP与SVM相结合的方法。Gaertner回顾了在结构化数据上定义正定核的方法,并给出了一种实用的定义正定核的方法[47,48]。这些核的定义都是以一阶公式之间的语法测量距离为基础的,不能利用背景知识。Muggleton定义了支持向量归纳逻辑程序设计(SVILP),定义了一个能反映数据的语义和语法关系信息的核,在Cprogol5.0中实现,并与毒素测试的工业标准系统(TOPKAT)在数据集DSSTOX(a new broad-ranging toxicity dataset)上进行了比较。应用结果表明SVILP方法胜过TOPKAT[49,50]。但Gaertner和Muggleton提出的方法的结果模型复杂而且难以解释。Landwehr将FOIL系统与SVM相结合实现了系统KFOIL[51]。Cannon等人则将ILP与SVM相结合的方法和ILP与bayes相结合的方法进行了比较,发现前者性能高于后者[52]。

3 归纳逻辑程序设计研究的发展方向

归纳逻辑程序设计克服了传统机器学习中知识表示机制的限制和学习中背景利用知识的限制,是一种强有力的机器学习方法。随着ILP的发展,也必将在更多的领域表现出广阔的潜力和理论意义。但其本身却仍然存在一些缺点和局限性,可考虑的未来研究的主要方向有:

(1)在自顶向下的学习方法中,采用信息增益驱动的算法(如FOIL)学习效率比较高,但不能学习带函数符号的关系,寻找高效的能够学习带函数符号关系的搜索策略是下一步的研究工作。

(2)在自底向上的学习方法中,如何实现逆蕴涵的新定义则是将来要解决的问题。

(3)寻找更为高效的学习系统。应该将多种方法进行综合,以开发出功能实现更加全面的算法。

(4)解决训练样本不足问题,可以考虑与半监督学习相结合的方法。

(5)并行实现。ILP的任务是在一个预先定义的假设空间中寻找一个子集,该子集和背景知识能够解释实例。人们考虑能否将实例和背景知识分成若干个子集,对每个子集学习假设,对这些子集的学习就可并行执行,提高效率,即所谓的并行实现。Luc Dehaspe提出了并行ILP,并在非单调问题背景下实现了CLAUDIEN的一个并行版本[53]。但在正规问题背景下,处于主导地位的数据通常都是背景知识而非训练实例,因此必须对背景知识进行划分,该划分还要和对实例的划分保持一致(即背景知识能解释实例),于是,协调地划分背景知识和实例则成为将来要研究的问题。

摘要：归纳逻辑程序设计是机器学习与逻辑程序设计交叉所形成的一个研究领域,克服了传统机器学习方法的两个主要限制:即知识表示的限制和背景知识利用的限制,成为机器学习的前沿研究课题。首先从归纳逻辑程序设计的产生背景、定义、应用领域及问题背景介绍了归纳逻辑程序设计系统的概貌,对归纳逻辑程序设计方法的研究现状进行了总结和分析,最后探讨了该领域的进一步的研究方向。

关键词：人工智能,机器学习,逻辑程序设计,归纳逻辑程序设计,背景知识

程序逻辑结构设计 篇2

拟订预选决策方案的逻辑程序、要求和方法

决策的可行方案是多种多样的,决策方案的产生过程又是极其复杂的,并不是随便怎样进行都可以的..因此,提出多个决策设想,拟订预选决策方案必须遵守一定的逻辑程序和要求,运用一定的逻辑方法,以有效地保证决策方案的严密性和合理性.

作 者：王新建 赵平WANG Xin-jian ZHAO Ping 作者单位：淮北职业技术学院,安徽,淮北,235000刊 名：淮北职业技术学院学报英文刊名：JOURNAL OF HUAIBEI PROFESSIONAL AND TECHNICAL COLLEGE年，卷(期)：6(6)分类号：B81关键词：预选决策方案 逻辑程序 逻辑要求 逻辑方法

程序逻辑结构设计 篇3

在我们的研究对象中,在社会系统中的人类生存问题、进化问题,还有在经济系统中的经济增长问题、股票问题、市场预测等等方面,具有动态模糊性的问题是普遍存在的。如,在知识处理系统中,常常会有这样的例子:“天渐渐昏暗下来了”,此例中的“渐渐”和“昏暗”就分别具有“动态性”和“模糊性”。苏州大学的李凡长教授在1996年以美籍伊朗数学家L.A.Zadeh在1973年提出的模糊逻辑为理论基础,提出了动态模糊逻辑(DFL)[1]作为解决动态模糊问题的理论工具,到目前为止已取得了一系列研究成果。为了进一步推动DFL的广泛应用,使其成为一种切实可实现的逻辑系统,我们有必要对动态模糊问题的解决提供软件支持,研究设计一种可以模拟处理动态模糊问题的程序设计语言。

现有的比较常用、比较流行的高级程序设计语言,如,C语言、VC++、JAVA、.Net类语言等基本上都适用于对精确的、确定性的数据和结构进行处理。当然也有一些比较特殊的程序设计语言,如,唐秩松院士领导的科研小组以时序逻辑为理论工具研制并实现的时序逻辑语言XYZ/E[2]可以在一定程度上解决动态性问题,国内外专家学者研究的Fuzzy Prolog[3,4]和武汉大学陈世鸿教授正在研究设计的FLL语言[5,6]等用来研究解决模糊性问题。经过分析我们发现可以解决动态模糊性问题的程序设计语言不多见,李凡长教授曾在文献[7]中给出过动态模糊数据程序设计语言的一个框架,除此之外,到目前为止,极少有人再尝试去研究设计可以解决动态模糊问题的程序设计语言。本文试图做这方面的研究工作,鉴于DFL程序设计语言的初始研究阶段,我们将先通过结构化操作语义给出它的语言定义。

1 基本概念

1.1 动态模糊数据[8]

公约1 把既是“动态的”又是“模糊的”的数据特性称作动态模糊性。

公约2 把具有动态模糊性的数据称作动态模糊数据。

例1 她越来越帅气了。“越来越”体现了“动态性”;“帅气”体现了模糊性,因此把整个子句称作动态模糊数据。

1.2 动态模糊逻辑(DFL)简介

略,参看文献[1]。

2 动态模糊逻辑的程序设计语言的语法

要定义一种程序设计语言,最基本的是要定义它的语法和语义。动态模糊逻辑的程序设计语言与以往的程序设计语言的重要区别在于它可以处理动态模糊数据。要做到这一点我们可以借鉴Dijkstra所提出的监督命令的程序结构[9,10],这种程序结构的特点是在程序中引入了不确定性,为每个可能被执行的语句提供一个监督条件。

从文献[1]中我们知道动态模糊集是由指称集到[0,1]×[←,→]的映射来定义的,为了引入动态模糊集我们有必要增加一个特殊集合D=[0,1]×[←,→],程序中的每个变量通过映射对应到D集合中的一个元素,以描述隶属度。下面我们给出DFL程序设计语言的抽象语法。

S::= skip|

abort|

$(\overleftarrow{\text{v}},\overrightarrow{\text{v}}=\text{E}|$

(S;S)|

if G fi|

do G od

$\begin{array}{l}\text{E}::=(\overleftarrow{\text{v}},\overrightarrow{\text{v}})|\\ (\overleftarrow{\text{n}},\overrightarrow{\text{n}})(\overleftarrow{\text{d}},\overrightarrow{\text{d}})|\\ \text{E}\text{o}\text{p}\text{E}\end{array}$

G::=B→S|

(G□G)

$\begin{array}{l}\text{B}::=(\text{t}\text{r}\text{u}\text{e},(\overleftarrow{\text{d}},\overrightarrow{\text{d}}))|\\ (\text{f}\text{a}\text{l}\text{s}\text{e},(\overleftarrow{\text{d}},\overrightarrow{\text{d}}))|\\ \text{B}\text{B}\text{o}\text{p}\text{B}|\end{array}$

E rel E

上述语法的语法范畴是:

S是语句集

E是表达式集

G是监督命令集

B是布尔表达式集

$(\overleftarrow{\text{v}},\overrightarrow{\text{v}}))$是变量

$(\overleftarrow{\text{n}},\overrightarrow{\text{n}}))$是常量

$(\overleftarrow{\text{d}},\overrightarrow{\text{d}}))\in \text{D}$是隶属度

op表示运算操作

Bop表示布尔运算

rel表示关系运算

只给出抽象语法是不够的,我们还需要给出每一个结构的精确定义,也就是给出语句的语义。

3 动态模糊逻辑程序设计语言的结构化操作语义

定义语义的方法[9]有很多种,主要的有:操作语义、指称语义、公理语义和代数语义。鉴于操作语义可以得到语言的抽象模型,对实现者具有很好的指导意义的优点,本文将使用操作语义给出动态模糊逻辑的程序设计语言的抽象模型。操作语义有多种不同的描述方法[9]。在这里我们采用Plotkin在1981年提出的结构化操作语义[9],它的基本思想为:复合成分的操作语义应该可以归结为它的各个组成部分的操作语义。我们用一个三元组<DFSC,DFO,DFSS>的形式给出动态模糊逻辑的程序设计语言的结构化操作语义模型,其中DFSC表示动态模糊语法范畴,DFO表示动态模糊算子,DFSS表示动态模糊语义。

3.1 动态模糊语法范畴DFSC

动态模糊语法范畴指的是语言所使用的所有语法符号。在第三部分的抽象语法中我们已经给出了我们所要设计的程序设计语言的语法范畴,在这里就不赘述了。

3.2 动态模糊算子DFO

动态模糊算子DFO用[←,→]表示,表明在某一时刻,其当前状态有两种发展趋势:“→”指示好的或前进的趋势,“←”指示坏的或后退的趋势。

3.3 动态模糊语义DFSS

动态模糊语义DFSS描述了具有动态性和模糊性语句结构的含义。在这里我们依据Plotkin的结构化操作语义引入动态模糊算子DFO即可得到动态模糊语义的基本内容。

从抽象语法中我们可以看出动态模糊程序设计语言的操作语义包含四种关系术语:表达式,布尔表达式,语句和监督命令。表达式与布尔表达式的模糊语义比较容易理解,在这我们就不具体给出,我们主要介绍动态模糊语句和动态模糊监督命令的语义。

3.3.1 语句

介绍两个状态:failure,当监督语句中的所有监督条件都不成立时执行条件语句出现的错误状态;abortion,因执行abort语句或由于其他原因而造成的程序不正常终止状态。

$\begin{array}{l}a.\overline{<\text{s}\text{k}\text{i}\text{p},\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <\sigma >}\\ b.\overline{<\text{a}\text{b}\text{o}\text{r}\text{t},\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <\text{a}\text{b}\text{o}\text{r}\text{t}\text{i}\text{o}\text{n}>}\\ c.\frac{<e,\sigma >\to <((\overleftarrow{n},\overrightarrow{n}),(\overleftarrow{{\displaystyle d{}_1}},\overrightarrow{{\displaystyle d{}_1}}))>}{<(\overleftarrow{x},\overrightarrow{x}):=e,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to }\\ <\sigma [(\overleftarrow{n},\overrightarrow{n})/(\overleftarrow{x},\overrightarrow{x}),t((\overleftarrow{d},\overrightarrow{d}),(\overleftarrow{{\displaystyle d{}_1}},\overrightarrow{{\displaystyle d{}_1}}))]>\\ d.\frac{<s{}_1,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{\prime }>,<s{}_2,{\sigma }^{\prime },(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{″}>}{<s{}_1;s{}_2,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{″}>}\\ \frac{<s{}_1,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{a}\text{b}\text{o}\text{r}\text{t}\text{i}\text{o}\text{n}}{<s{}_1;s{}_2,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{a}\text{b}\text{o}\text{r}\text{t}\text{i}\text{o}\text{n}}\\ e.\frac{<g,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{\prime }>}{<\text{i}\text{f}g\text{f}\text{i}‚\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{\prime }>}\\ \frac{<g,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{f}\text{a}\text{i}\text{l}\text{u}\text{r}\text{e}}{<\text{i}\text{f}g\text{f}\text{i},\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{a}\text{b}\text{o}\text{r}\text{t}\text{i}\text{o}\text{n}}\\ \frac{<g,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{a}\text{b}\text{o}\text{r}\text{t}\text{i}\text{o}\text{n}}{<\text{i}\text{f}g\text{f}\text{i},\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{a}\text{b}\text{o}\text{r}\text{t}\text{i}\text{o}\text{n}}\\ f.\frac{<g,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{″}>,<\text{d}\text{o}g\text{o}\text{d},{\sigma }^{″},(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{\prime }>}{<\text{d}\text{o}g\text{o}\text{d},\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{\prime }>}\\ \frac{<g,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{f}\text{a}\text{i}\text{l}\text{u}\text{r}\text{e}}{<\text{d}\text{o}g\text{o}\text{d}‚\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <\sigma >}\\ \frac{<g,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{a}\text{b}\text{o}\text{r}\text{t}\text{i}\text{o}\text{n}}{<\text{d}\text{o}g\text{o}\text{d},\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{a}\text{b}\text{o}\text{r}\text{t}\text{i}\text{o}\text{n}}\end{array}$

其中t表示t模数运算。

3.3.2 监督命令

$\begin{array}{l}a.\frac{<\text{b}\text{e},\sigma >\to <((\overleftarrow{{\displaystyle true}},\overrightarrow{{\displaystyle true}}),(\overleftarrow{d},\overrightarrow{d}))>,<s,\sigma >\to <\sigma \text{'}>}{<\text{b}\text{e}\to s,\sigma >\to <\sigma \text{'}>}\\ \frac{<\text{b}\text{e},\sigma >\to <((\overleftarrow{{\displaystyle false}},\overrightarrow{{\displaystyle false}}),(\overleftarrow{d}{}_2,\overrightarrow{d}{}_2))>}{<\text{b}\text{e}\to s,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to \text{f}\text{a}\text{i}\text{l}\text{u}\text{r}\text{e}}\\ b.\frac{<g{}_1,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{\prime }>,<g{}_2,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <{\sigma }^{″}>}{<g{}_1\square g{}_2,\sigma ,(\overleftarrow{d},\overrightarrow{d})>\to <\{{\sigma }^{\prime },{\sigma }^{″}\}>}\\ (\text{下}\text{转}\text{第}146\text{页})\end{array}$

摘要：动态模糊问题在客观世界中是普遍存在的,作为解决动态模糊问题的理论工具-动态模糊逻辑(DFL)已有十年的研究历史了,为了更有效地解决动态模糊问题,使DFL成为一种切实可实现的逻辑系统,有必要研究设计一种适合解决动态模糊性问题的程序设计语言。仿照监督命令的程序结构,给出动态模糊程序设计语言的结构化操作语义,其内容包括:动态模糊逻辑程序设计语言的抽象语法、动态模糊语义并通过一个简单实例说明其有效性。

关键词：动态模糊逻辑,动态模糊逻辑程序设计语言,结构化操作语义

参考文献

[1]李凡长,刘贵全,佘玉梅.动态模糊逻辑引论[M].昆明:云南科技出版社,2005,7.

[2]唐秩松,等.时序逻辑程序设计与软件工程[M].北京:科学出版社,2002.

[3]Munakata,Toshinori.Notes on implementing fuzzy sets in Prolog[J].Fuzzy Sets and Systems,1998,98:311317.

[4]HUA Hong,WANG Yi de.The Implementation of Fuzzy Prolog Lan-guage[J].Chinese Journal of Cumputer,1988,11(6):378383.

[5]陈世鸿,等.FLL语言的说明性语义与过程性语义[J].武汉大学学报:自然科学版,1999,45(3):287290.

[6]陈世鸿,等.模糊逻辑语言FLL的并行计算模型FPCM[J].数学物理学报,2002,22A(1):4854.

[7]李凡长,等.动态模糊数据模型及其设计语言[J].计算机科学,1997,24(12):4953.

[8]李凡长,等.动态模糊数据模型研究.计算机研究与发展,1998,35(8):714718.

[9]陆汝钤.计算机语言的形式语义.北京:科学出版社,1992,12.

组合逻辑设计教学设计 篇4

新都职校

一、教材分析

《数字电路》是一门理论性和实践性都很强的专业核心课程，而“组合逻辑电路”在教材的知识体系中处于中间地位，起着“承前启后”的作用。

《组合逻辑电路的设计》应该在学生学习了“数字电路基础”、“逻辑门电路”“组合逻辑电路分析”的基础上进行，既可以检验前面所学知识又可以延伸后续知识。

教学重点：介绍组合逻辑电路的设计方法和步骤。

教学难点：引导学生按步骤设计出经济又实用的组合逻辑电路。

二、学情分析

本次授课对象是10机电8班的全体同学，在前面的学习中，他们已经掌握了基本逻辑门电路、逻辑代数基本公式、逻辑表达式的化简和组合逻辑电路的分析等基础知识做铺垫，故对本次课内容有接受的能力。

三、教学目标

知识目标：使学生熟练掌握组合逻辑电路的设计方法及步骤，提高学生学以致用的能力。能力目标：培养学生认真学习、勇于探索的精神；启发学生举一反

三、触类旁通的创新思维能力。情感目标：通过课堂的师生交流，生生交流，培养学生与人交流团结协作的能力。

四、教学方法

教师的准备工作：熟悉教学大纲和课程标准；钻研教材写好教案；设计好教学过程，准备好课件、教学工具等。

为了激发学生的兴趣，调动学生的积极性，教学过程中我主要采用“任务驱动法”来进行教学，结合学生特点，精心设计任务，引导学生分析任务探究新知，然后启发学生运用所学知识解决实际任务。中间配合使用类比法、仿真法、讨论法、演示法来达到我们的教学目标。

五、教学过程

教学过程共设计了：温故知新、任务驱动、探究新知、巩固提高等教学环节，用时1个课时。温故知新——采用教师提问、学生回答的互动方式来进行，共复习了三个知识点：（1）基本常用门的符号、表达式、真值表及功能；

（2）逻辑代数运算的基本定律及化简办法。这两个知识点是基础工具，学习了之后学生才可以用门电路来搭建一个个具有某种功能的数字电路。

（3）接着提问 2个问题：①何为组合逻辑电路的分析？②组合逻辑电路分析的一般步骤有哪几步？(要求学生用流程图回答)。然后用一道题来简单演练分析步骤，加深学生印象,并为新知识的教授做好 铺垫。

任务驱动——引领学生进行思考：给出一个组合逻辑电路图，我们能分析出它的逻辑功能，那么给出一个逻辑命题，我们能否根据要求的逻辑功能设计出逻辑电路呢？如何设计一个三人表决器呢？学生根据课前预习情况会做出相应回答，即跟组合逻辑电路的分析过程相反，需要五步——相反顺序的五步。其实本次课的“设计”过程是上次课“分析”过程的逆过程，也是本次课的主题。

接下来教师用板书导出教学重点。任务启动好之后，学生们根据提示的方法步骤，分析思考，分组交流，教师则巡回指导，一段时间后各小组就开始展示成果了。通过这个“生生交流”“师生交流”的过程，引导学生进行自主探究、合作学习，同时也巩固加深了教学重点内容的理解和运用。

探究新知——引导学生思考：如何设计出经济又实用的组合逻辑电路？第一次的设计是不是最完美的？如果用“与非门”来设计会有什么不同？两种方案设计的“三人表决器”逻辑电路哪种更好？为什么？学生们在经过逻辑代数的变换、化简后很快又展示了第二种设计方案。

教师引领学生对比分析这两种设计方案，发现两种设计方案都只用了4个门电路，不同的是：方案 1中的四个门，有3个是“与门”1个是“或门”，而方案2中的4个门都是“与非门”，对比之下门电路种类单一，相对好些。通过层层设疑，再次激发了学生的学习热情，突出了本节课的教学难点：在实际应用中，组合逻辑电路的设计多用“与非门”来实现，可以降低成本，避免不必要的人力、物力浪费。

任务1结束后，继续布置第2个任务，将任务1的只有1个输出量的设计任务，提升到2个，加大了工作量，提高了难度，目的是鼓励学生，开阔思路，创新思维，突破重点难点，也使枯燥、乏味的新课内容很流畅的就被“由浅入深”“化难为易”了。最后教师用板书将重点、难点提炼出来，巩固所学，加深印象。

“巩固提高”环节——在同学们共同完成任务1,2之后，教师又给学生们设置了两个加强任务，要求学生独立完成，以此自行消化、吸收、巩固掌握本次课的知识点的目的。

六、结束语

加权约束逻辑程序 篇5

关键词：加权约束逻辑程序,smodels系统,高级程序设计语言

1 概述

通常的高级程序设计语言属于过程性语言, 需要在程序执行前详细规定运行步骤。而基于逻辑的计算机语言的出现, 给某些逻辑问题提供了更有效的解决途径。1972年, 法国科莫劳埃小组在实现了第一个逻辑程序设计语言PROLOG。1974年以后R.科瓦尔斯基进一步阐明了PROLOG的理论基础, 并丰富了逻辑程序的设计思想, 使得逻辑程序的设计思想更加具体化、系统化。目前, 国际上, 具有回答集语义的逻辑程序方面的研究非常活跃。

具有回答集语义的逻辑程序, 从一般的逻辑程序, 到扩展的逻辑程序, 再到加权约束逻辑程序, 不管是在语法形式上, 还是语义上都有了新的发展和突破。加权的约束逻辑程序的出现, 为逻辑问题的解决提供了一种新的表达形式, 是逻辑程序所能解决的问题复杂度增大, 范围也更广。

文章首先介绍加权约束逻辑程序, 并通过该程序语言解决经典的逻辑问题, 并和传统的程序设计做比较, 充分说明该类逻辑程序的特点和优势。

2 加权约束逻辑程序

加权约束逻辑程序和一般的回答集程序一样, 都具有稳定模型语义, 并已经成功应用于组合问题, 图以及规划等各个领域的问题解决。随着具有稳定模型语义的逻辑程序的研究越来越成熟, smodels系统的功能也越来越符合实际应用的需求。在smodels的版本2.0以及以后的版本中, 程序中除了包含基本的规则之外, 还包括选择规则、约束规则和加权规则三种扩展的规则。这使得逻辑程序设计可以处理更多更多复杂、更多领域的问题。

从smodels系统可以处理的规则类型, 我们可以看出它可以处理加权规则和约束规则。因此, 文章中, 我们使用加权约束逻辑程序解决例子中给出的问题。

这三种类型的形式语义都可以通过使用加权约束规则来定义, 加权约束是下面的形式:

其中a1, ..., an, b1, ..., bm是原子, L和U是整数的上界和下界, w1, ..., w (m+n) 是文字 (Literal) 的权重。随后, 用w (l) 表示文字l (Literal) 的权重。在这里, 只考虑正的加权, 对于负的加权的情况, 可以通过把负的加权否定和转化文字的方式去掉程序中的负的权重。

3 加权约束逻辑程序实例应用分析

不同类型的问题需要不同风格的程序设计方法。对于一些比较复杂的经典的问题, 通过使用逻辑规则来解决问题, 会大大简化编程的难度。逻辑程序设计使开发者集中精力于逻辑的描述, 而无需花很多精力来关注程序运行的过程。这类逻辑推理问题包括经典的问题, 如皇后问题、汉诺塔问题、着色问题等。下面举例说明在处理这类问题时逻辑程序的一些优势。

八皇后问题是十九世纪著名的数学家高斯1850年提出的。问题描述为:在8X8格的国际象棋上摆放八个皇后, 使其不能互相攻击, 即任意两个皇后都不能处于同一行、同一列或同一斜线上, 问有多少种摆法。

若使用逻辑程序设计语言——加权约束逻辑程序来解决, 则其代码如下:

程序在smodels平台下运行结果如图1。

该程序的运行结果表明该问题有92个稳定模型:耗时1.217秒等信息。

若使用高级语言这种传统的解决思路, 则需要编写更长的、更复杂的代码, 不容易理解和修改, 并且还容易出错。而通过以上方法, 我们可以看出用逻辑程序解决此类问题写出的程序, 更简洁, 更灵活, 更容易编写、阅读和理解。对于这类经典的逻辑问题, 采用这种逻辑程序语言写出的程序, 只含有规则和事实, 短小精悍, 易于编写, 且不容易出错。

4 总结

用逻辑程序设计编写程序时, 用户不用太多关语句的顺序和执行过程的控制顺序;而用一般程序设计方法, 需考虑过程, 程序较复杂, 且需由系统做更多的分析工作, 运行时间会较长。逻辑程序设计更符合人的思维方式, 更适合解决逻辑推理问题。逻辑程序语言的这些特点和优势, 使其在产品配置问题、语义网、生物信息学、以及医学诊断问题中都有了广泛的应用和研究。

参考文献

[1]刘椿年, 曹德和.PROLOG语言的应用与实现[M].北京:科学出版社, 1990.

[2]M.Gelfond and V.Lifschitz.The stable model semantics for logic programming.Logic programming:proc.of the Fifth int.Conf.and Symp.pages, 1988.

程序逻辑结构设计 篇6

用于汽轮发电机矽钢片冲剪的一台J36—400双点压力机,该设备系20世纪70年代制造,控制系统采用常规继电器控制,由于产量高,负荷大,经常发生制动器磨损,滑块偏离上死点等故障;同时润滑系统无监控措施, 润滑系统出现故障时,经常会造成连杆铜瓦和曲轴支撑瓦烧坏抱死,从而加大了维修成本,同时给正常生产带来较大的影响。为了降低故障率,提高生产效率和产品成品率,利用PLC改造控制系统,解决滑块偏离上死点问题;同时利用PLC与电子凸轮控制器的结合,监控润滑状况,一旦润滑系统有故障,可及时报警,提醒排除润滑故障,保证设备正常运行。

1实施

PLC作为一种性能稳定可靠、功能强大的电子器件,已广泛应用于控制领域。针对400t压力机,选用日本三菱公司FX1N-40MR控制器[1],主要控制3个部分:1) 电动机的启动、停止;2) 滑块的行程控制;3) 润滑的监控。

a) 电动机的控制:

对主电动机的控制,相对于原控制系统,省去了控制电动机启动的时间继电器,由PLC延时功能实现,由于其简单易行,这里不在赘述。

b) 滑块的行程控制

原来滑块的行程控制依据的主要元件为机械式凸轮控制器。由于凸轮控制器的微动开关每天动作上万次,并且所带负载为继电器,相对负载较重,很容易造成微动开关的损坏。鉴于上述原因把原来的机械式凸轮控制器换成了电子凸轮控制器[2],电子凸轮控制器具有:1) 转角位置显示清晰,角度可读;2) 设定角度可直接在操作面板上完成,无须爬到设备上部的去调整角度,并且可一人完成(原机械式需两人密切配合);3) 上死点定位可自动修补;4) 具有机械运转侦察功能,可预告离合器、制动器磨损,达到预防维修的目的。电子凸轮与PLC接线见图1。该程序利用电子凸轮检测滑块在离合器脱开前的运动速度,为下一次离合器脱开时间作好调节,实现上死点的自动修正,因此免去了机械式凸轮的调节。

PLC控制程序(指令表)如下:

c) 润滑监控改造

原来该设备的润滑采用的是直接供脂式的阀分配润滑系统,动力由电动机驱动,其润滑系统如图2所示。

该系统加油周期设定为机床刚启动时人工加油,因此润滑状况难以保证;同时,系统也无法监控,往往润滑有故障了,操作人员也无法知道,等传动部分发现问题,造成铜瓦烧坏后,才发现润滑系统出现故障。针对上述缺陷,把润滑系统由直接供油脂式润滑系统改造成单线间接供油脂递进式润滑系统,用PLC控制,实现润滑周期依据滑块行程次数控制,润滑时间依据分油器的动作次数控制,同时设立了监控时间,当监控时间到而分油器动作次数不够时,认为润滑有故障,PLC记录下故障的次数,当故障次数连续达到4次时,切断电动机控制回路,同时输出润滑故障报警信号,提醒维修人员检修故障。间接供油脂式的阀分配润滑系统,如图3所示。

PLC润滑系统的程序流程图如图4所示。

3结论:

电气控制系统采用了PLC的控制,监控了电子凸轮和润滑,两项改造,使得电子凸轮调整方便,大大缩短了调整时间,同时内部的磨损侦察功能,为设备作好预防性维修提供了依据;润滑的改造,保证了设备的润滑,避免了因铜瓦烧坏引起的长期停机,使设备故障率由原来的7.52%降低到2.13%;延长了设备使用寿命。

参考文献

[1]FX1N系列微型可编程控制器使用手册[S].MITSUBISHI E-LECTRIC CORPORATION,2000.

程序逻辑结构设计 篇7

通过化简实现逻辑函数的最小化是数字逻辑系统设计过程中非常重要的一个步骤, 但诸如公式法、卡诺图法等常用的化简方法仅适用于简单的逻辑函数, 对于复杂的多变量 (5变量以上) 逻辑函数的化简则可使用蕴涵化简法。

蕴涵法又叫制表法, 是由奎恩 (Q u i n e) 提出, 并经由麦克拉斯基 (McCluskey) 改进和完善的一种逻辑函数系统化简法, 故又称为Q-M化简法。虽然与卡诺图法一样也是以公式为基本理论依据, 但蕴涵法又有着化简步骤规律性强的优点, 应用于多变量逻辑函数的化简, 虽然工作量大, 但操作可以按部就班地进行, 适合于计算机处理[1]。

上述特点, 在蕴涵法化简逻辑函数的第一个步骤即求本原蕴涵项的过程中表现得尤为突出。所谓本原蕴涵项就是不含多余变量的乘积项, 即其已不能再通过同其它乘积项合并而减少变量了[2]。本文以5变量逻辑函数为例, 应用蕴涵法进行计算机辅助设计, 给出求解多变量逻辑函数本原蕴涵项的结构化程序流程。

1. 程序流程

1.1 初始化

初始化操作除了定义程序运行所需的多个相关变量外, 最主要的工作就是定义如下两个数组。

1.1.1 二维数组m[3,212]

m数组的每个数组元素为一个字节, 同一列的三个数组元素构成一个数据单元, 数组元素的列号即为数据单元的序号, 如图1所示, 数据单元是存储逻辑函数标准与或式中包含的最小项或操作过程中产生的一般乘积项的基本单位。

数据单元中标记“×”的位没有定义 (用“0”填充) , 其余位根据不同的存储对象有着不同的定义和使用方法。

(1) 存储最小项

按照使最小项、数据单元的序号对应相等的方法, 将逻辑函数包含的最小项mi存储于m数组的第i (=0~31) 个数据单元并由输入程序作相应设置。

1) m[2][i].7位为“1”, 表示逻辑函数包含最小项mi, 此时, 数据单元的其它各位定义如下。

(1) m[2][i].6位为“0”, 表示mi尚未被消去任何变量, 一旦mi参与化简, 此位将被置“1”;

(2) m[0][i].4~m[0][i].0位组存储mi的序号i对应的5位二进制数, 其中“1”对应mi中的原变量, 而“0”对应反变量;

(3) m[1][i].4~m[1][i].0位组存储5个连续的二进制“1”表示mi包含所有逻辑变量;

(4) m[2][i].2~m[2][i].0位组用于存储3位二进制值, 表示位组m[0][i].4~m[0][i].0中“1”的个数, 即mi中原变量的个数。

图1 (a) 为一个特例, 描述最小项m 2尚未参与化简合并时的存储状态。

2) m[2][i].7位为“0”表示逻辑函数不包含最小项m i, 此数据单元的其它位皆不被定义使用。

(2) 存储一般乘积项

在求解本原蕴涵项过程中, 一般会产生被消去若干个变量的一般乘积项, 它们将被依次存储于m数组中序号大于或等于32的数据单元中, 除以下两点外, 各数据位取“0”、“1”状态的含义与存储最小项时基本相同。

1) 一个一般乘积项在m数组中的具体存储位置由被处理的逻辑函数的结构决定;

2) m[1][i].4~m[1][i].0位组中的某位为“0”, 表明其对应的变量已被从乘积项中消去, 其在m[0][i].4~m[0][i].0位组中对应位的状态也失去意义。

图1 (b) 为另一个特例, 描述了一个一般乘积项的存储状态, 此一般乘积项由逻辑函数F (在后文的实现实例部分中详细说明) 包含的两个最小项m9、m1 1合并得到, 其所在数据单元的序号为36, 尚需进一步化简。

(3) m数组中数据单元数目的定义问题

对于m数组, 实际所需的数据单元的数目由被处理的逻辑函数决定, 随逻辑函数包含的最小项数目及最小项分布情况不同而变化。在此, 对5变量逻辑函数, 设定数据单元的个数为212, 即m数组的列号范围为0~211, 这是一个存储单元数目极端大的选择, 对应逻辑函数的标准与或式中共包含31个最小项的情况。

1.1.2 二维比较合并数组comp[6][10]

为了比较、合并逻辑相邻的最小项, 根据蕴涵法理论定义6行10列的二维字节数组c o m p, 并依据表1 (最小项比较合并表) 的结构和内容将comp数组初始化, c o m p数组具有如下特征。

(1) 内容非“-1”的数组元素共32个, 分别对应被处理逻辑函数可能包含的序号为0~31的32个最小项, 而内容为“-1”的数组元素不对应最小项。每行的第一个内容为“-1”的数组元素用于控制某一轮寻找、比较与合并最小项的循环过程的结束。

(2) 同一行数组元素对应的最小项拥有相同个数的原变量, 并且原变量的个数等于行号。

(3) 某行一个数组元素对应的最小项与相邻上一行另一个数组元素对应的最小项相比较, 原变量个数多1, 如果这种关系是由于逻辑函数的同一个变量在两个最小项中分别取原、反变量状态引起的, 则相应的两个最小项即为一对逻辑相邻项。

1.2 逻辑函数输入

输入程序依据前述要求设置m数组的相关数组元素。特别地, 对于逻辑函数包含所有最小项 (逻辑函数值恒为1) 和逻辑函数不包含任何最小项 (逻辑函数值恒为0) 两种情况要在输入流程中直接进行处理说明, 而不必进入后续的求解本原蕴涵项流程。

1.3 求解本原蕴涵项流程

求解本原蕴涵项操作的程序流程结构为一个整体, 为描述方便, 将其分为主体和子模块两个部分。

1.3.1 主体部分

图2以N-S图的形式给出主体部分的结构化流程。

这一部分的核心流程是一个严格遵循蕴涵法基本步骤设计的, 分别以i1、j1和k1为外、中和内层循环控制变量的三重嵌套循环结构。借助于comp数组为主要的控制依托, 通过此循环结构正常运行, 可实现主体部分的基本功能, 即进行逻辑相邻最小项的寻找、比较与合并操作, 得到因消去一个变量而拥有4个变量的所有一般乘积项, 并依次存储于m数组中相应位置的数据单元中。

当得到的4变量一般乘积项的个数大于或等于2时, 求解本原蕴涵项的操作过程就需要继续进行, 流程进而由此部分结束处的二重嵌套选择结构的最左端分支进入子模块部分, 否则, 本原蕴涵项已经求出, 整个流程结束。

1.3.2 子模块部分

图3以N-S图的形式给出子模块部分的结构化流程。

子模块部分实现的功能是:针对主体部分求得的两个或两个以上的4变量一般乘积项, 继续进行逻辑相邻的一般乘积项的寻找、比较与合并操作。

这一部分程序流程整体上为一个四重嵌套的循环结构。以r为循环控制变量的外层循环最多可能执行3次, 先后求得可能存在的由3、2或1个逻辑变量组成的一般乘积项;i2、j2控制中间两层循环, 实施求解这些一般乘积项的具体操作;而k2控制的最内层循环则用于防止同一个一般乘积项在m数组中的重复存储。

1.4 本原蕴涵项的输出

上述相关流程执行完毕后, 化简得到的所有本原蕴涵项都被存储在m数组中, 假设某个本原蕴涵项所在数据单元的序号为i, 则有:

(1) i的范围为0~PointEnd;

(2) m[2][i].7~m[2][i].6位组的内容为“1 0” (此为本原蕴涵项的标志) ;

(3) m[1][i].4~m[1][i].0位组中内容为“1”的位对应的变量被保留在本原蕴涵项中;

(4) 本原蕴涵项中一个被保留变量的原、反状态由m[0][i].4~m[0][i].0位组中此变量对应位的取值确定, “1”对应原变量, “0”对应反变量。

根据上述特征, 可设计相应的程序流程对所有本原蕴涵项进行依次输出。

2. 实现实例

用蕴涵法化简逻辑函数F (A、B、C、D、E) =∑m (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31) , 求全部本原蕴涵项[3]。用C语言实现上述流程, 程序运行的结果是在m数组中得到3个存储着本原蕴涵项的数据单元, 它们是:

(1) m[0][51]=00000000、m[1][51]=00011001、m[2][51]=1000000;

(2) m[0][55]=00010001、m[1][55]=00010011、m[2][55]=1000010;

(3) m[0][59]=00001001、m[1][59]=00001001、m[2][59]=1000010。

即函数F的本原蕴涵项为:

3. 结束语

本文介绍的求解多变量逻辑函数本原蕴涵项的方法严格遵循蕴涵法理论, 设计的程序流程清晰、准确, 符合结构化标准, 用C、V B等高级编程工具很容易实现。对于6变量以上的逻辑函数, 也仅仅需要对m数组的列数、comp数组的结构和内容及部分循环结构的循环次数进行简单的修改即可。实践表明, 通过上述流程对逻辑函数进行处理的结果, 与用公式法、卡诺图法等手工方法进行处理的结果完全一致, 但在提高可靠性、减小复杂度和降低工作成本等方面优点是明显的。

参考文献

[1]黎诣远, 李林曙主编.经济数学基础.高等教育出版社[M].2005年7月