最简理论

2024-11-27

最简理论（共4篇）

最简理论篇1

汉语动词复制句(学界常称为重动句)是现代汉语中一种比较常见的句式,由“动词”、“宾语”、“重复的动词”和“补语”四个成分组成。赵元任先生在《汉语口语语法》中,把汉语动词复制句中动宾、动补的短语标写为V-O和V-R,解释为连动和主谓并存的关系,认为两者中间不但可以插入主语,还可以插入副词,两者的关系取决与两个成分间的语义关系。笔者认为,动词复制句式是一种动补句式,其多数句子是“主-谓-补”类句式的延伸。

一.语义特征分析

汉语动词复制句在语义结构上总是遵循先宾后补的语序,其成分顺序如下:

施事者+动作+客体+动作+其他+结果补语

主语+谓语+宾语+重复谓语+(得、了、到)+补语

S+V1+O+V2(Functional Mark dele)+R

其中动词性成分(动词或者动词性语素)在形式上完全相同,S为主语,O为直接宾语,R为补语成分,O与R之间存在“得、到、了”为具有句法功能意义的标记语素。在大多数的动词复制中,动词性成分都是由动作动词(action verb)充当的,如:

(1)小王吃瓜子吃得口焦舌燥。

(2)我想卖力气都想疯了。

(3)我爱你爱了那么久。

具有终止意义的、不能重复的行为动词则不能进入动词复制结构,试对比例(4)和(5):

(4)她上课上了三个钟头。

(5)她下课下了三个钟头。

“上课”是具有持续性的、可反复的动作;而“下课”却是不可延续的、不可重复的动作;因此前者的动词成分可以出现表示完成体的助词“了”的前面,形成表示完成的事件。而后者“下课”的动词成分“下”却无法出现在动词复制句式中:“下课下了三个钟头”,“下了三个钟头的课”。

在语法功能方面,V1和V2的表现不同,多数研究认为V2可带体标记词“了、过”或者是带表完成意义的功能标记“得”而V1不可以。如“她上了课上三个钟头”、“她上了课上了三个钟头”不符合汉语的语法要求;而“她上课上过(了)三个钟头”、“她上课上得很累”却成立。可见V1和V2分别与其后成分组成的两个结构在功能上是不完全相同的。

在补语特征方面,Li&Thompson对汉语动词复制结构的研究,结合了结构和语用方面的特征,将动词复制(该文中的动词拷贝)的补语成分R分为四种类型:普通结果补语、时间词补语、地点介词补语和趋向动词补语。本文以生成语法为框架,结合动词复制句补语的语义特征,在上述分类的基础上把动词复制句的归为四种类型,它们分别是含时间、频率类补语(DF补语)的动词复制句,含目的、处所类补语(DL补语)的动词复制句,含“得”字补语的动词复制句和含复合类补语的动词复制句。其中“得”字的动词复制句由于没有可替代的非动词复制句式,即为强制性的动词复制句,因此可以以“得”为标准将动词复制句分为含“得”字补语的动词复制句和不含“得”字补语的动词复制句两类。

二、结构特征分析

汉语中,当动词的直接宾语、补语和动词需要共现的时候,除了采用动词复制这一结构外,表述同一语义关系时还可以采用“动词+补语+宾语”、“动词+宾语+补语”、“把字句”、“被子句”、“主谓谓语句”和“准定中结构主语句”等句式。而动词复制句往往有独特的语义结构,如表述事件的因果关系和表述事件结果的超常性,该特性体现为一种隐含“致使”的语义关系。

程工、黄月圆的研究探讨了动词复制句和把字句的转换关系,其中程工认为把字句和动词复制句是在同一深层结构的基础上产生的不同表层结构,两者具有同源性;而黄月圆则认为两者基于不同的深层结构,而且是对立分布的。

这从另一个角度说明了动词复制句与“把字句”、“被子句”、“主谓谓语句”和“准定中结构主语句”在深层结构上是同源的,即这些结构有同一个语义关系,但是在表层结构的生成得出了不同的结果。

这种汉语动词复制结构与其他句式的句法同源性是值得进一步探讨的话题,而本文并不认为动词复制句或是把字句是在彼此转换的基础之上产生的,因为从语义表达和功能方面这两个句式明显不同,他们是各自在其语言环境下产生的独立结构,在使用上,语言系统则依据语言使用的不同要求,选择合适的句式。

三、句法分析

在动词复制句的生成机制中,轻动词的出现与动词的“完成”语义和情态的表达是密不可分的,即使在不含“得”与“了”标记的动词复制句中也存在及物性轻动词Tr,这个轻动词所表达的语义和功能是及物性的动作事件,其构成的动词复制句在表达上是相对灵活的,可以有多种变体。

首先,在结果性“得”字动词复制句中,“得”是体词性成分,根据Chomsky,体词性成分时在词库中就与动词结合的成分。当源动词与其补语成分在推导中合并时,动词仍有一个题元角色没有指派。其原因是“V得”构成的动词是非及物性的,由以下两例对比可知:

(6)老王愁那件事愁得满头白发。

(7)那件事愁得老王满头白发。

例(6)的“愁得”是一个不及物的,因为同样的语义表达中(7)中的“愁得”是一个非宾动词(不能指派宾格的动词),而(7)也就是一个作格结构(非宾动词中的使役动词结构)。根据Levin Rappaport的非使役化的研究,在(S-R)词法层,动词的“施事”受到了形态上的抑制而转变为不及物动词(潜及物动词)因而不能指派宾格,导致宾语“那件事”提升到句首。因此结果性动词复制句(7)的“V得”也非及物性的,而补语是一个含有空代词PRO(与主语或者宾语同指)的从句。

根据生成语法理论,非及物性的动词需要经过复制来为宾语赋格,因此运算系统从词库中选出一个“动词拷贝”嫁接到原有的VP上。在这个句法操作模式中,动词复制句的第一个动词是第二个动词的复制体,“得”这一体词成分则是表达动作“愁”的已然发生,则可视为占有一定句法位置的另一轻动词Pr,表达上只有语音形式却能够表达一个完整的命题,该轻动词往往以Tr P为补语。

笔者认为命题性轻动词Pr并不能够核查宾语成分的格特征,因此由位于Pr与V之间的Tr来完成探针操作,发现DP的特征并完成特征的核查和匹配,如下句所示:

其中,“得”标记轻动词Pr,而NP1、NP2则分别是主语“老王”和宾语“那件事”,通过上移,两者分别被Pr和Tr赋予主格和宾格,实现题元特征的核查与删除,得到结果性动词复制句的结构。

其次,在描写状态性“得”字动词复制句中,“得”的语义功能和句法位置则大有不同。“得”是一个单纯的结构助词,与补语合并为“得P”结构,充当动词的补足语成分。但是如何在“V得”成为一个成分之后又能形成“得P”则需要句法操作的重新解释。

程工就将“得”字句的分析置于最简方案的框架之下,并且利用最简方案的最新进展,提出用Larson理论中对双宾语结构的处理方法来分析描写性“得”字句。他指出在VP壳内可能有的几种操作,即扩展、转换、论元移动(如在Larson假设V’重新分析来为论元移动提供条件),V’重新分析是指:

如果甲是一个短语[V’……],并且其题元角色中有一个内部语义角色没有释放,则甲可以重新分析为[V……],如例句(8):

(8)他开车开得很稳。

(8)中动词短语“开得很稳”同样恰好有一个没有释放的论元角色(宾格),因此V’首先经过重新分析为“开[de P得很稳]”。然后动词再经过动词拷贝与提升产生“开车开得很稳”,满足了宾语的格需求,操作过程为:

[Pr P NP1[Tr P Vi-v NP2[VP Vi[de P de XP]]]]]]

同样,句中的轻动词Tr因含有及物性,即包含φ特性(形式特征)和动词性探针而探测到复制体“开”,与之合并。然后Tr通过特征匹配核查宾语“车”的格特征,而外层轻动词Pr则分配标示语“他”的论元角色。

而在不含“得”的动词复制句中,如在含DF补语的动词复制句中,动词复制是非强制的执行的操作。由于时间和频率两类短语的功能却不同,表示持续时间的补语名词在充当不及物性动词的补足语时,常要借助功能标记词“了”,形成轻动词Tr的投射;而频率补语则形成附加语(句中可删除的修饰性成分),其位置与“了”没有必然的联系。

在含复合动词的动词复制中,只有补语中含有宾语名词的动词复制句有“了”标记的轻动词DO,而复制句中的其他句式的轻动词均是无标记的。最后,在含DL补语的动词复制句中,由于多数句子不含有“得”、“了”,因此也视为无标记的轻动词Tr。

动词复制句中普遍存在着表示完成意义的轻动词Pr和Tr,这两类轻动词中Tr以“得”、“了”为标记词,而轻动词Pr的EPP特征则诱发动词的上移,与之合并,使其功能得以实现。

而轻动词的名词特征则是诱发汉语动词复制的重要原因,而在补语不同的动词复制句中,有些含有标记“得”与“了”标记的轻动词,这两词所标记的轻动词所处的句法位置和基本功能不同,语义蕴含也不同:前者含有“致使+达成”的情态义,而后者只含“做”的语义。而在不含有“得”与“了”标记的动词复制句中也普遍存在着前一种轻动词Pr和Tr则与复杂的补语结构结合在一起构造出多种动词复制句变体形式。

笔者认为动词复制句中普遍存在着表示完成意义的轻动词Tr及命题性轻动词Pr,两者分别以“了”和“得”为标记词,轻动词的EPP特征诱发动词和名词的上移,动词与宾语名词合并,得以实现轻动词的句法功能。因此汉语的轻动词成分的EPP特征是诱发汉语动词复制句式的重要原因之一。

参考文献

[1]CHANG,CLAIRE HSUN-HUEI.Verb Copying:Toward A Balance Between Formalism and Functionalism[J].Journal of theChinese Language Teachers Association,1991,26(1):1-32.

[2]CHANG,JUNG-HSING.Event Structure and Argument Linking in Chinese[J].Language and Linguistics,2003,4(2):317-351.

[3]CHAO,YUAN-REN.A Grammar of Spoken Chinese[M].Berkerley:University of California Press,1968.

[4]CHOMSKY,NOAM.Lectures on Governing and Binding[M].Dordrecht:Foris Publications,1981.

[5]CHOMSKY,NOAM.The Minimalist Program[M].Massachusetts:M.I.T.Cambridge,1995.

[6]范晓.复动“V得句”[J].语言教学与研究,1993,(4):57-74.

最简多元最小上界算法研究篇2

1 最小上近似

令Q1,Q2为本体,C为Q1中概念,T是Q2中所有概念的集合且|T|=n。称T中i个概念的集合为T中i-概念集。Q1中概念C在T中可能有多个不同的上近似,它们的质量是不一样的。通过比较其查准率和查全率,可以找到C的最小上近似。可以用查询间的蕴涵关系[4,5]定义它们,并通过比较查全率和查准率说明它们确实是最佳的。

因为上近似的查全率都是1,所以只需比较它们的查准率。

定义1:令R1,R2是C在T中的上近似,如果⊆R1⊆2,则有precision(C,R1)≥precision(C,R2),所以R1的质量好于R2,称R1比R2更接近C。如果R是C在T中的一个上近似,而且对于任何C在T中的上近似Ri,都有C哿R哿Ri,则称R为C在T中的最小上近似。

2 概念的多元最小上界

定义2:令mlub(C,T)是T中概念析取的集合,如果满足:

1)对于∀Ĕ∈mlub(C,T),有C⊆Ĕ;

2)对于∀ĔT且C⊆Ň,都存在Ĕ∈mlub(C,T)满足Ĕ⊆Ň

则称mlub(C,T)是C在T中的多元最小上界。

下面约定概念C在Q2中的上近似也称为C在T中的上近似。令

由mlub(C,T)中的成员都蕴涵C,可知C⊆mua(C,T),所以mua(C,T)是C在T中的上近似。可以证明mua(C,T)是C在T中的最小上近似[6]。

定理1:对Q1中任何概念C,mua(C,T)是C在T中的最小上近似[7]。

定义3:令slub(C,T)是C在T中的多元最小上界,如果对于∀Ĕ∈slub(C,T)都有:

则称slub(C,T)为最简多元最小上界。

这三个条件去除了多元最小上界中的冗余:第一个条件说明slub(C,T)只包含蕴涵C的最小概念析取,第二、三个条件说明多个等价的概念析取中,slub(C,T)只保留包含概念最少的一个。

3 概念最简多元最小上界

3.1 算法思路

概念C在T中可能存在多个合法的最简多元最小上界,约定slub(C,T)是由算法1找到的最简多元最小上界。令概念集集合ps={E|E姚∈slub(C,T)},psi为ps中的i-概念集的集合。算法的目标就是在T中的所有概念集中找到ps的所有成员。

实际上,部分概念集存在这样的特性:它的所有超集都不在ps中,这些概念集组成的集合记为ns,即。因此只要证明一个概念集属于ns,那么它的所有超集就不再需要检查,即这些概念集一定不属于ps。这样可大大减少蕴涵检查的次数,比如只要证明概念集{D}属于ns,则需要进行检查的概念集就只剩下2n-1个,减少了一半。

图1算法采用迭代递增的过程生成概念集并测试它们是否属于ps。在第一步,处理1-概念集;在第二步,处理2-概念集;……。在第i步,生成的i-概念集的集合称为i-候选集,记作ci;然后测试ci中的成员,判断是否属于psi或ns。所有可能属于psi的放到一个集合中等待进一步验证,称为i-待验集,记作vi;一部分成员可以确定属于ns,从ci中删除

这些成员后构成的集合为ri。在第i+1步,ci+1由ri生成。算法提高效率的关键是在每一步最小化i-待验集和i-剩余集。在算法的每一步,i-待验集越小,最后的验证工作量越少;i-剩余集越小,由它生成的(i+1)-候选集就越小,相应地减少了后续步骤的搜索空间。

为了了解算法主框架的基本思想,下面分析如何从第一步过渡到第二步。令c1={{D}|D∈T}为第一步开始时生成的1-候选集。通过测试c1中的成员,可以得到关于它们属于ps1或ns的性质。一部分成员可能属于ps1,就把它们放到v1中;一部分成员可以确定属于ns,从c1中删除这些成员后构成的集合为r1。第二步的2-候选集c2只需包含所有1-子集都在r1中的2-概念集。因为如果一个2-概念集E,它存在1-子集不在r1中,由r1定义,则该1-子集必属于ns;由ns定义,E?ps2,且E∈ns。由此可知E本身及其超集都不可能属于ps,而算法的目标是求ps,所以E不需要放入c2中进行测试。以上讨论也适用于从第i步过渡到第i+1步。一般地,ci为所有(i-1)-子集都在ri-1中的i-概念集的集合。

3.2 函数find1()

在介绍第一步的测试函数find1()之前,先引入一个可以消去冗余概念的定理[8]。

定理2.如果有概念A,B T,满足A⊆B⊆C或A≡B,令T’=T-{A},则有C在T’中的最简多元最小上界也是C在T中的最简多元最小上界,即对求C在T中的最简多元最小上界来说,概念A是冗余的。

图2中的函数find1()通过测试c1中的成员找到v1,r1。

3.3 函数validate()

当生成和测试阶段完成后,有两种可能:一是已经找到了和C等价的查询并赋给了ps,这时无需验证,算法可以结束;如果没有找到和C等价的查询,由定理3,所有vi的并集v必然包含ps的所有成员。函数validate()根据定义9中最简多元最小上界的条件,除去v中的冗余成员,得到正确且完备的ps。验证函数validate()见图3。

3.4 算法分析

整个算法的主要运算是检查两个概念或概念析取之间的蕴涵关系,即执行check()函数。在第一步find1()中,要求出所有T中概念间蕴涵关系,并以此排序,然后从c1中求得v1和r1,时间复杂度为O(n2),其中n是T中概念总数。算法将T中所有冗余的等价概念,和C不相交的概念,C的子类,以及C的间接超类都从c1中删除,只有很少的概念留在r1中,不妨设其数量为m,有m远小于n。这样即使是在最坏情况下,之后寻找vi的时间复杂度也不会超过O(2m)。假设找到的待验概念集数目为l,validate()的最坏时间复杂度为O(l2);因为在算法中对vi有严格的定义,最终的l不会大。这样算法总的时间复杂度不会超过O(n2+2m+l2)。以上是最坏情况下的分析,实际上由于算法的每一步都尽可能的缩减搜索空间,通常只需检查其中的很少一部分。

由于算法1采用了迭代递增的过程,算法执行中随时可以停机并给出一个近似的结果。如仅执行一次迭代,得到的就是现有方法中使用的概念最小上界。随着迭代次数的增多,结果越来越接近概念的多元最小上界。通过这些近似结果求得的概念上近似也越来越接近概念的最小上近似。这个性质说明,即使在极少数较坏情况下,算法1也能够在可接受的时间内得到较好的近似结果。

4 结束语

通过把最小上近似转化为最简多元最小上界问题研究,可以大大提高最小上近似的质量和消除多元界中的冗余。基于本体的查询中除了概念,还有一个重要的关系元素[9]。因此要实现近似查询,除了求概念的近似,还需要求关系的近似,基于本体的关系查询是困难的,现有方法主要是把关系查询转化为概念查询,如果确保高质量转化还有待于研究。

参考文献

[1]袁洋,李善平.基于语义Web的本体映射方法综述[J].重庆:计算机科学,2004,31(5):5-8.

[2]张蓉,申德荣,于戈等.基于本体的Web服务查找和合成技术研究[J].北京:计算机集成制造系统,2003,9(10):921-925.

[3]高军,王腾蛟,杨冬青,等.基于Ontology的Web内容二阶段半自动提取方法[J].北京:计算机学报,2004,27(3):310-318.

[4]王洪伟,吴家春,蒋馥.基于本体模型的信息检索机制研究[J].北京:情报学报,2004,23(1):3-9.

[5]董慧.基于本体论和数字图书馆的信息检索[J].北京:情报学报,2003,22(6):648-652.

[6]Chang K C-C,Garcia-Molina H.Mind Your Vocabulary:Query Mapping across Heterogeneous Information Sources[C]//Proceedings of the1999ACM SIGMOD Conference.New York:ACM Press,1999.335–346.

[7]Preece A,Hui K,Gray P.Kraft:An Agent Architecture for Knowledge Fusion[J].International Journal of Cooperative Information Sys-tems,1999,10(1-2):171-195.

[8]Mena E,Illarramendi A,Kashyap V,et al.OBSERVER:An Approach for Query Processing in Global Information Systems based on Interoperation across Preexisting Ontologies[J].International journal on Distributed and Parallel Databases,2000,8(2):223-271.

最简理论篇3

1 最优二叉树的建立和算法

1.1 最优二叉树的概念

设一棵二叉树有n个叶子结点，每个叶子结点拥有一个权值W1, W2, …, Wn，从根结点到每个叶子结点的路径长度分别为L1L2, …, Ln，那么树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和，通常记作：

而在有相同叶子结点权值构成的二叉树中，带权路径长度各不相同，在n个带树叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为最优二叉树。

1.2 最优二叉树的建立

最优二叉树的构造思想是由哈夫曼得出的，下面先介绍哈夫曼提出的思想方法：

对于已知的一组叶子的权值W1, W2，…，Wn:

1) 首先把n个叶子结点看作n棵树，每棵树的树根为叶子结点的权值，把这n棵树看做一个森林。

2) 在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和。这时森林中还有n-1棵树。

3) 重复第 (2) 步直到森林中只有一棵树为止[2]。此树就是最优二叉树，也称哈夫曼树。

为了能方便快速地计算出带权路径长度，现要求叶子结点用方框表示，树根结点用圆圈表示，圆圈中的数值是叶子结点权值的总和，现给一组 (n=4) 具体权值为2, 4, 5, 8的序列，下边是构造哈夫曼树的具体过程：首先，将2, 4, 5, 8看成是4棵只有根结点的子树，构成一个森林，如图1 (a)所示。然后将最小的权值2和次小的权值4组合成一棵子树，根结点为2+4=6，这时还有三棵子树，根结点分别为6, 5, 8, 如图1 (b)所示。再将图中最小的权值5和次小的权值6组合成一棵子树，根结点为11，如图1 (c)所示。最后只剩下两棵子树，权值分别为8和11，将它们组合成一棵子树，根结点的权值为19，此时，森林中只剩下最后一棵树，这棵树就是哈夫曼树。

上面所构造的哈夫曼树是不唯一的，它的形状可以发生变化，但是它的最短路径长度只有一个，且每个根结点都有两棵子树，是一棵严格的二叉树，在这棵二叉树中，权值越大的叶子结点离根结点就越近。

1.3 构造最优二叉树的算法

为了简化程序，本文采用顺序存储结构的方法给出最优二叉树的存储结构。

该程序采用了数组的存储方式，是因为最优二叉树中没有度为1的结点。由二叉树的性质可以知道度为0的结点的个数等于度为2的结点的个数加1，即为n0=n2+1，所以总的结点数为n0+n2，也就是2n0-1，所以定义数组的大小就为2n-1。在这个程序中有一个二重循环，内循环的平均循环次数为O (n) ，外循环大约为n次，所以该算法的时间复杂度为O (n2) 。

2 最短带权路径长度的计算

设一棵二叉树有n个叶子结点，每个叶子结点拥有一个权值W1, W2，…，Wn，从根结点到每个叶子结点的路径长度分别为L1, L2，…，Ln，那么树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和[1]，记为WPL。则上面构造的最优二叉树的最短带权路径长度为：WPL=(2+4)*3+5*2+8*1=36。

在上面的计算过程中，要求学生掌握关于路径和路径长度的概念。树中两个结点之间的路径由一个结点到另一个结点的分支构成。两结点之间的路径长度是路径上分支的数目。树的路径是从根结点到每一个结点的路径长度之和。对于这些概念，在计算带权路径长度的过程中，学生又经常会将它们与树的深度、层次等概念混淆在一起，因此，在计算带权路径长度的过程中也就经常出现错误。

事实上，上面所构造的这棵哈夫曼树的最短带权路径长度可以很简便的算出结果，也就是将圆圈当中的数值累加起来就可以，而不必理解关于路径和路径长度的概念。比如2和4的叶子结点的权值，在哈夫曼树当中第一次被累加成了7，在第二次时被累加成了11，第三次被累加成了19，所以2和4的叶子结点的权值被累加了3次，刚好相当于(2+4)*3的结点，其它的叶子权值也依此类推计算。所以哈夫曼树的简单计算如下：WPL=19+11+6=36。

3 结束语

本文给出了一种静态建立哈夫曼树的方法和算法，并提出一种最简计算最小带权路径长度的方法，在实际的教学过程中学生接受快，容易理解，而且计算方便，比书本上常用的方法更简单。

参考文献

[1]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 2007:144-146.

卡诺图在化简最简逻辑式中的应用篇4

卡诺图是一种用几何图形表示逻辑关系的方法。从美国工程师卡诺(Karnaugh) 提出该方法以来,卡诺图就被广泛的应用于数字电路的设计与教学中。在传统教学过程中,主要运用卡诺图中具有相邻性、对称性的最小项可以合并,消去不同因子的原理,主要将卡诺图用于函数式的化简。

一个逻辑函数的最简表达式,常按照式中变量之间运算关系不同,分成最简与或式、最简与非-与非式、最简或与式、最简或非-或非式、最简与或非式等五种。在教材中常用的方法为公式法化简法,利用卡诺图的相邻性、对称性,这五种最简式均可以用卡诺图进行化简,方便而快捷的得到结果。

1卡诺图在化简最简式的基本原理

1.1圈“1”法

最小项定义:n个变量X1,X2,…,Xn的最小项是n个因子的乘积,每个变量都以它的原变量或非变量的形式在乘积项中出现,且仅出现一次。

n变量的卡诺图:将n变量的全部最小项都用小方块表示,并使具有逻辑相邻的最小项在几何位置上也相邻地排列起来,这样,所得到的图形叫n变量的卡诺图。

在卡诺图中,凡两个逻辑相邻项,可合并为一项,其合并的逻辑函数是保留相同的,消去相异的变量。合并规律:21个相邻项合并时消去一个相同的变量,22个相邻的项合并时消去两个相同的变量,以此类推,2n个相邻的项合并时消去n个相同的变量。圈“1”法是利用最小项的相邻性而定的圈“1”的相关规则的,主要规则是:圈的1的个数只能是2n,并以卡诺图中的线为对称;圈尽可能大;允许重复,但要有新的“1”;孤立的“1”独圈。

在正逻辑中,卡诺图中的“1”表示为真,在化简最简式时,按圈“1”法所得到的输出也为“真”。根据圈“1”法的规则,对应每个包围圈写成一个新的乘积项,将所有包围圈对应的乘积项相加,即写为与或式。

1.2圈“0”法

n变量的最大项:是指n个因子的和项,每个变量都以它的原变量或非变量的形式在和项中出现,且只出现一次。

方法1:在正逻辑中,卡诺图中的“0”表示为“假”,在化简最简式时,按圈“0”法所得到的输出也为“假”。根据圈“0”法的规则(将圈“1”法的规则中的“1”换为“0”),对应每个包围圈写成一个新的乘积项,将所有包围圈对应的乘积项相加,即写为与或式,但此时的结果为“假”,对应的结果一定要加“非”即:“undefined”、“undefined”等。

方法2:利用最大项根据圈“0”法的规则(将圈“1”法的规则中的“1”换为“0”),对应每个包围圈写成一个新的或项,将所有包围圈对应的或项相与,即写为或与式。

2卡诺图在化简最简式的应用举例

以逻辑式F(A,B,C)=m(1,3,6,7)为例来化简成各种最简式。

2.1最简与或式

作出如图1所示:关于逻辑式的最小项的卡诺图,并由圈“1”的规则圈出相关项。

undefined (1)

2.2最简与非-与非式

F(A,B,C)=m(1,3,6,7)

可以利用式1的结果用摩根定理进行变形:

undefined

2.3最简或与式

方法1:作出如图2所示的关于逻辑式的最大项的卡诺图,并由圈“0”的规则圈出相关项,用与或式的形式表示出圈“0”的圈。