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

文章目录

    • 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法就是一种可通过计算机编程实现的系统化简法,也称为列表法或表格法,若专业从事集成电路底层设计,应予掌握,详情可查阅有关教材或资料。

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/367788.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

c#的反汇编对抗

文章目录 前记nim攻防基础FFI内存加载加解密、编码 后记C#类型转换表nim基础 前记 随便编写一个c#调用winapi并用vs生成dll,同时用csc生成exe using System; using System.Runtime.InteropServices; namespace coleak {class winfun{[DllImport("User32.dll")]publ…

AutoCAD .NET 层次结构介绍

AutoCAD .NET API 提供了一种面向对象的编程接口,通过它可以与AutoCAD进行深度集成和自定义功能开发。以下是基于.NET框架下AutoCAD对象层次结构的基本介绍: Autodesk.AutoCAD.ApplicationServices 命名空间 根对象,代表运行中的AutoCAD应用程…

模板简要介绍,C++读书笔记

2014年2月3日 内容整理自《程序设计教程: 用C语言编程 第三版》 陈家骏 郑滔 --------------------------------------------------------------------------------------------------------------------------------- (一)函数模板 1…

苹果的ipad可能会缓存vue项目的数据或者pinia数据

如果你发现开发的vue项目在ipad上出现了异常,比如数据出现NaN的情况,或者computed计算属性没生效,或者pinia里面的数据没生效,可能就是ipad浏览器safari缓存了数据导致的,只需要清空safari里面缓存的数据就可以了&…

(java版)排序算法----【冒泡,选择,插入,希尔,快速排序,归并排序,基数排序】超详细~~

目录 冒泡排序(BubbleSort): 代码详解: 冒泡排序的优化: 选择排序(SelectSort): 代码详解: 插入排序(InsertSort): 代码详解: 希尔排序(ShellSort): 法一…

深度学习图像分类相关概念简析+个人举例1(ANN相关概念与计算)

(1)神经网络:英文全称Artificial Neural Network,简称为ANN。 神经网络是一种模仿人脑神经元结构和功能的人工智能模型。它由多个神经元(也称节点、单元)组成,每个神经元通过计算输入和权重的线…

从零开始复现GPT2(六):生成代码的实现

源码地址:https://gitee.com/guojialiang2023/gpt2 GPT2 模型文本生成配置生成框架文本生成类实现文本生成代码 模型 文本生成 配置 class GenerateConfig(object):def __init__(self,seq_len: int,nucleus_prob: float,use_gpu: bool):self.seq_len seq_lenself…

【C/C++ 10】扫雷小游戏

一、题目 写一个扫雷小游戏,每次输入一个坐标,若该处是地雷,则游戏失败,若该处不是地雷,则显示周围地雷数量,若扫除全部非地雷区域,则扫雷成功。 二、算法 设置两张地图(二维数组&…

手把手教你开发Python桌面应用-PyQt6图书管理系统-主界面UI设计实现

锋哥原创的PyQt6图书管理系统视频教程: PyQt6图书管理系统视频教程 Python桌面开发 Python入门级项目实战 (无废话版) 火爆连载更新中~_哔哩哔哩_bilibiliPyQt6图书管理系统视频教程 Python桌面开发 Python入门级项目实战 (无废话版) 火爆连载更新中~共计24条视频&…

移远(Quectel)物联网通信解决方案

一、方案简介 无线通信模块是具备无线通信的电路模块,它能通过无线连接传输数据,能识别分析主控制器发来的命令,控制节点设备的工作,或者向主控制器发送当前节点设备的工作状态。 市面上常用的无线通信模组包括蓝牙模组、WLAN模…

2024年【上海市安全员B证】最新解析及上海市安全员B证复审考试

题库来源:安全生产模拟考试一点通公众号小程序 上海市安全员B证最新解析根据新上海市安全员B证考试大纲要求,安全生产模拟考试一点通将上海市安全员B证模拟考试试题进行汇编,组成一套上海市安全员B证全真模拟考试试题,学员可通过…

算法练习-二叉树的节点个数【完全/普通二叉树】(思路+流程图+代码)

难度参考 难度:中等 分类:二叉树 难度与分类由我所参与的培训课程提供,但需要注意的是,难度与分类仅供参考。且所在课程未提供测试平台,故实现代码主要为自行测试的那种,以下内容均为个人笔记,旨…

ubuntu22.04 安装部署01:禁用内核更新

一、前言 ubunut22.04系统安装以后,内核更新会导致各种各样的问题,因此锁定初始安装环境特别重要,下面介绍如何锁定内核更新。 二、操作方法 2.1 查看可用内核 dpkg --list | grep linux-image dpkg --list | grep linux-headers dpkg --…

STM32--USART串口(2)串口外设

一、USART简介 可配置数据位:不需要校验就是8位,需要校验就选9位; 停止位:决定了帧的间隔; STM32F103C8T6USART:USART1挂载在APB2总线上,USART2和USART3挂载在APB1总线上; 二、USART框图 TXE…

Python中使用Opencv-python库绘制直线、矩形、圆、文本

Python中使用Opencv-python库绘制直线、矩形、圆、文字 在Python中使用Opencv-python绘制直线、矩形、圆、文本非常简单,分别使用到line、rectangle、circle、putText这几个函数,具体可以参考https://docs.opencv.org/4.9.0/d6/d6e/group__imgproc__dra…

如何部署Node.js服务并实现无公网ip远程访问本地项目【内网穿透】

文章目录 前言1.安装Node.js环境2.创建node.js服务3. 访问node.js 服务4.内网穿透4.1 安装配置cpolar内网穿透4.2 创建隧道映射本地端口 5.固定公网地址 前言 Node.js 是能够在服务器端运行 JavaScript 的开放源代码、跨平台运行环境。Node.js 由 OpenJS Foundation&#xff0…

【C++】类与对象(三)—运算符重载|const成员函数|取地址及const取地址操作符重载

前言 运算符重载,自增自减运算符重载,const成员函数,取地址及const取地址操作符重载 文章目录 一、运算符重载自增和自减运算符重载 二、const 成员函数三、取地址及const取地址操作符重载(了解即可) 一、运算符重载 运…

P1967 [NOIP2013 提高组] 货车运输

[NOIP2013 提高组] 货车运输 题目背景 NOIP2013 提高组 D1T3 题目描述 A 国有 n n n 座城市,编号从 1 1 1 到 n n n,城市之间有 m m m 条双向道路。每一条道路对车辆都有重量限制,简称限重。 现在有 q q q 辆货车在运输货物&#x…

Unity Meta Quest MR 开发(三):Scene API 配置+实现虚拟与现实之间的碰撞

文章目录 📕教程说明📕 Scene 配置⭐开启场景理解功能和应用访问空间数据的权限⭐OVRSceneManager⭐制作 Plane Prefab 和 Volume Prefab⭐运行场景⭐添加透视材质 📕虚拟与现实物体的碰撞(弹球 Demo)📕Mes…

【JavaSE篇】——继承

目录 🎓继承 ✅为什么需要继承 ✅继承概念 ✅继承的语法 ✅父类成员访问 🚩子类中访问父类的成员变量 1. 子类和父类不存在同名成员变量的情况 2. 子类和父类成员变量同名 🚩子类中访问父类的成员方法 1. 成员方法名字不同 2. 成员…