卡诺图:逻辑相邻与几何相邻的统一

2024-02-03 10:52

本文主要是介绍卡诺图:逻辑相邻与几何相邻的统一,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 1.一句话记住卡诺图
    • 2.卡诺图的由来、定义和特点
    • 3.填写卡诺图(用卡诺图表示逻辑函数)
      • ⑴根据真值表填写卡诺图
      • ⑵根据最小项(或最大项)填写卡诺图
      • ⑶根据函数的与或表达式填写卡诺图
    • 4.用卡诺图化简逻辑函数
      • ⑴化简步骤
      • ⑵画圈原则
    • 综合题★★★
    • 后记:关于列表法(Q-M法)

今天是南方小年,春节渐近,提前祝大家新春快乐!

这节内容斟酌再三,今天终于成稿,主要是希望内容既全面又易于理解,可能比通用教材啰嗦,但是讲的更透。卡诺图既是一种图形化方法,也是一种有助于计算机辅助分析的逻辑化简思想,重要性不言而喻。

1.一句话记住卡诺图

卡诺图是化简逻辑函数的重要工具,是一张二维表格,相当于变形的真值表,主要特点是实现了几何相邻和逻辑相邻的统一,能帮助我们直观地表示逻辑函数并写出最简逻辑式,而判断相邻的直观方法就是对折重合。

2.卡诺图的由来、定义和特点

1953年,贝尔实验室的电信工程师莫里斯·卡诺(Maurice Karnaugh)在维奇图(一种逻辑函数的图形表示)的基础上改进发明了卡诺图,使逻辑函数的化简相较代数法变得简单且直观,从而在数字逻辑设计等领域中得到了广泛应用。

卡诺图是按照逻辑相邻性原则组成的二维表格(方格图)。它跟真值表是完全对应的,其中每个方格相当于真值表中的一行,代表一个最小项或最大项,如图1所示为二变量函数的真值表和卡诺图的对应关系。

在这里插入图片描述

图1

图1中,卡诺图左上角斜线两侧为函数 Y Y Y的输入变量符号,横边和侧边的数字为相应变量的取值,取值的排列按格雷码分布(详见图3、图4、图5),这是实现逻辑相邻(对应变量组合的取值只有一位不同)与几何相邻相统一的原因;图1中,方格中的数字表示最小项或最大项的序号(变量取值组合对应的十进制数),对一个确定的函数,方格中填写相应的函数输出值,如图2所示。

在这里插入图片描述

图2

实际使用中,一般将方格默认为最小项,因此,大部分教材直接用最小项定义卡诺图:

n {\boldsymbol{n}} n变量的全部最小项各用一个小方格表示,并使具有逻辑相邻性的最小项在几何位置上也相邻地排列起来,得到的图形称为 n {\boldsymbol{n}} n变量最小项的卡诺图

将卡诺图定义于最小项,主要是基于人们的使用习惯和应用便捷性,因为无论是真值表还是卡诺图,我们最习惯、最容易写的是与或式。但是,我们知道最小项与最大项天然互反,一一对应,逻辑相邻性和几何相邻性也是一样的,所以,如果你更习惯于使用最大项,也可以将每个方格用最大项表达,写出函数的或与式。具体来说,跟真值表一样,函数值为1的所有方格按最小项加起来就是最小项之和式,函数值为0的所有方格按最大项乘起来就是最大项之积式(这些项也可以写成最小项之和式,代表反函数),例如,对图2,有 Y = Σ m ( 1 , 2 , 3 ) Y=\Sigma m(1,2,3) Y=Σm(1,2,3),或 Y = M 0 Y=M_0 Y=M0,或 Y ‾ = m 0 \overline{Y}=m_0 Y=m0

从以上构图和定义可知, n n n变量卡诺图由 2 n 2^n 2n个方格组成,最终,任何两个位置相邻和轴对称的方格均具有逻辑相邻性,所谓轴对称就是对折重合,也就是将卡诺图横向或纵向对折,且可以对折分割后再对折,每次对折后所有重合的方格为逻辑相邻项。有的资料又将几何相邻分为位置相邻、相对相邻和相重相邻三种情况,所谓相对相邻是指每一行(或列)的两端,均在对折重合的范畴之内。

图3、图4、图5分别为用最小项表示的三变量、四变量和五变量卡诺图。

在这里插入图片描述

图3

在这里插入图片描述

图4

在这里插入图片描述
在这里插入图片描述

图5

以图5为例, m 0 m_0 m0分别与 m 1 m_1 m1 m 8 m_8 m8 m 4 m_4 m4 m 2 m_2 m2 m 16 m_{16} m16逻辑相邻。

3.填写卡诺图(用卡诺图表示逻辑函数)

⑴根据真值表填写卡诺图

上文图2即是一例,再举一个三变量的例子,逻辑函数 F ( A , B , C ) F(A,B,C) F(A,B,C)的真值表如表1所示,将每一行的函数值填入三变量卡诺图对应的最小项方格中,得卡诺图如图6所示。
在这里插入图片描述

在这里插入图片描述

图6

⑵根据最小项(或最大项)填写卡诺图

将函数化为最小项(或最大项)表达式,再将相应的最小项方格填1。

例如函数 F = Σ m ( 1 , 4 , 5 , 6 , 7 ) F=\Sigma m(1,4,5,6,7) F=Σm(1,4,5,6,7),只需在卡诺图的 m 1 m_1 m1 m 4 m_4 m4 m 5 m_5 m5 m 6 m_6 m6 m 7 m_7 m7方格中填写1,其余填0,如图6所示。同理,若 F = ∏ M ( 0 , 2 , 3 ) F=\mathrm{∏}M(0,2,3) F=M(0,2,3),则将卡诺图 m 0 m_0 m0 m 2 m_2 m2 m 3 m_3 m3方格填0,其余填1,同图6。

⑶根据函数的与或表达式填写卡诺图

对任何“与或式”函数,只需要将每一个乘积项对应的所有方格填写1即可。对乘积项中的各变量因子,原变量取1,反变量取0,找到相应的行和列并取交集,就是该乘积项对应的方格。例如,分别求 F 1 = A + B ‾ C F_1=A+\overline{B}C F1=A+BC F 2 = A ‾ C F_2=\overline{A}C F2=AC的卡诺图,方法如下:

①参考图3和图6,设 A A A为行, B C BC BC为列。 F 1 F_1 F1第一个乘积项为 A A A,找到 A = 1 A=1 A=1,即第二行,全部填1,如图7所示。

在这里插入图片描述

图7

F 1 F_1 F1第二个乘积项为 B ‾ C \overline{B}C BC,所以找到 B C = 01 BC=01 BC=01的列,全部填1,剩余的方格填0,如图8所示,此即为 F 1 F_1 F1的卡诺图。

在这里插入图片描述

图8

F 2 F_2 F2只有一个乘积项 A ‾ C \overline{A}C AC,找到 A = 0 A=0 A=0的行和 C = 1 C=1 C=1的两列,二者交集所在方格填1,其余填0,得 F 2 F_2 F2的卡诺图如图9所示。

在这里插入图片描述

图9

4.用卡诺图化简逻辑函数

卡诺图化简的依据:两个相邻最小项可以合并为一个乘积项并消去一个变量因子。

因此,对卡诺图中具有相邻性的项不断合并,可得到函数的最简逻辑式。相邻项合并时,消去取值发生变化的变量因子,保留公共因子, 2 i 2^{\boldsymbol{i}} 2i个相邻项,可消去 i \boldsymbol{i} i个变量因子

⑴化简步骤

①画卡诺图;

②圈“1”(求原函数)或者圈“0”(求反函数),合并最小项;

③将每个圈对应的乘积项相加,得最简与或式。

⑵画圈原则

①相邻单元的个数是 2 i 2^i 2i个,并成矩形时,可合并。

②每个圈中所含“1”的个数要尽可能多。

③画圈的个数要尽可能少。

④“1”方格可重复圈定,但每个圈内须有新的“1”。

综合题★★★

题1 用卡诺图化简下列函数:
Y = A B C + A B D + A C ˉ D + C ˉ ⋅ D ˉ + A B ˉ C + A ˉ C D ˉ Y=ABC+ABD+A\bar{C}D+\bar{C}\cdot \bar{D}+A\bar{B}C+\bar{A}C\bar{D} Y=ABC+ABD+ACˉD+CˉDˉ+ABˉC+AˉCDˉ
解析:首先用卡诺图表示该函数,如图10所示。
在这里插入图片描述

图10

圈“1”,如图11所示,得最简逻辑式为
Y = A + D ˉ Y=A+\bar{D} Y=A+Dˉ

在这里插入图片描述

图11

也可圈“0”,如图12所示,合并最大项结果同上(不推荐),或合并最小项得反函数为
Y ‾ = A ‾ D \overline{Y}=\overline{A}D Y=AD

在这里插入图片描述

图12

题2 化简下列函数为最简与或式:
F ( A , B , C , D ) = ∏ M ( 3 , 4 , 6 , 7 , 11 , 12 , 13 , 14 , 15 ) F(A,B,C,D)=\mathrm{∏}M(3,4,6,7,11,12,13,14,15) F(A,B,C,D)=M(3,4,6,7,11,12,13,14,15)

解析:题目给的是最大项之积式,在卡诺图中将最大项序号对应的方格填0,其余填1,得该函数的卡诺图如图13所示。

在这里插入图片描述

图13

在卡诺图中圈“1”,如图14所示,得最简与或式为
F ( A , B , C , D ) = B ˉ ⋅ C ˉ + B ˉ ⋅ D ˉ + A ˉ ⋅ C ˉ ⋅ D ˉ F(A,B,C,D)=\bar{B}\cdot \bar{C}+\bar{B}\cdot \bar{D}+\bar{A}\cdot \bar{C}\cdot \bar{D} F(A,B,C,D)=BˉCˉ+BˉDˉ+AˉCˉDˉ

在这里插入图片描述

图14

题3 将题2中的函数化简为最简或与式:

解析:卡诺图同题2(图13),求或与式,所以圈“0”,如图15所示,然后写出反函数的最简与或式,再通过反演定理或摩根定理转换得原函数的最简或与式。(也可通过最大项合并直接写出最简或与式,除非对最大项特别熟练,否则不推荐。)
在这里插入图片描述

图15

由图15的合并结果,得
F ˉ = A B + B D ˉ + C D \bar{F}=AB+B\bar{D}+CD Fˉ=AB+BDˉ+CD

F = ( A ˉ + B ˉ ) ( B ˉ + D ) ( C ˉ + D ˉ ) F=(\bar{A}+\bar{B})(\bar{B}+D)(\bar{C}+\bar{D}) F=(Aˉ+Bˉ)(Bˉ+D)(Cˉ+Dˉ)

后记:关于列表法(Q-M法)

卡诺图对于六变量以上的复杂多变量逻辑函数显得无能为力,但是人们借助于卡诺图化简思想实现了多变量函数的计算机自动优化处理,Q-M法就是一种可通过计算机编程实现的系统化简法,也称为列表法或表格法,若专业从事集成电路底层设计,应予掌握,详情可查阅有关教材或资料。

更多内容,欢迎关注下方公众号!

这篇关于卡诺图:逻辑相邻与几何相邻的统一的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/673919

相关文章

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa

poj 3304 几何

题目大意:给出n条线段两个端点的坐标,问所有线段投影到一条直线上,如果这些所有投影至少相交于一点就输出Yes!,否则输出No!。 解题思路:如果存在这样的直线,过投影相交点(或投影相交区域中的点)作直线的垂线,该垂线(也是直线)必定与每条线段相交,问题转化为问是否存在一条直线和所有线段相交。 若存在一条直线与所有线段相交,此时该直线必定经过这些线段的某两个端点,所以枚举任意两个端点即可。

POJ 2318 几何 POJ 2398

给出0 , 1 , 2 ... n 个盒子, 和m个点, 统计每个盒子里面的点的个数。 const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;}struct Point{double x , y

poj 2653 几何

按顺序给一系列的线段,问最终哪些线段处在顶端(俯视图是完整的)。 const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;}struct Point{double x , y ;Point(){}Po

华为OD机试真题-学生方阵-2024年OD统一考试(E卷)

题目描述 学校组织活动,将学生排成一个矩形方阵。 请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上,方向可以是水平的,垂直的,成对角线的或者呈反对角线的。 注:学生个数不会超过10000 输入描述 输入的第一行为矩阵的行数和列数, 接下来的 n行为矩阵元素,元素间用""分隔。 输出描述 输出一个整数,表示矩阵中最长的位

UML- 统一建模语言(Unified Modeling Language)创建项目的序列图及类图

陈科肇 ============= 1.主要模型 在UML系统开发中有三个主要的模型: 功能模型:从用户的角度展示系统的功能,包括用例图。 对象模型:采用对象、属性、操作、关联等概念展示系统的结构和基础,包括类图、对象图、包图。 动态模型:展现系统的内部行为。 包括序列图、活动图、状态图。 因为要创建个人空间项目并不是一个很大的项目,我这里只须关注两种图的创建就可以了,而在开始创建UML图

逻辑表达式,最小项

目录 得到此图的逻辑电路 1.画出它的真值表 2.根据真值表写出逻辑式 3.画逻辑图 逻辑函数的表示 逻辑表达式 最小项 定义 基本性质 最小项编号 最小项表达式   得到此图的逻辑电路 1.画出它的真值表 这是同或的逻辑式。 2.根据真值表写出逻辑式   3.画逻辑图   有两种画法,1是根据运算优先级非>与>或得到,第二种是采