卡诺图化简法_Samplay的博客-程序员信息网_卡诺图

技术标签: 离散数学  karnaugh  卡诺图  

目录

1.学前需要了解知识点

2.卡诺图(karnaugh map)

3.逻辑函数的卡诺图化简法

4.总结


1.学前需要了解知识点

  • 最小项的定义
  • 最小项的表示方法
  • 最小项的相邻性

最小项的定义:一个函数的某个乘积项包含了函数的全部变量,其中每个变量都以原变量或反变量的形式出现,且仅出现一次,则这个乘积项称为该函数的一个标准积项,通常称为最小项

最小项的表示方法:通常用来表示最小项。

下标i的确定方式:把最小项中原变量记为1,反变量记为0,当变量顺序确定后,可以按顺序排列成一个二进制数,则这个二进制数相对应十进制数,就是这个最小项的下标i

例1:

函数L(A,B,C)中有3个变量,他们的最小项是:

如果把原变量记为1,反变量记为0:

以上就是下标i的确认方式。

既然i已经确认,也就是说(m0、m1...m7)可以记成:

最小项的的相邻性:任何两个最小项如果他们只有一个因子不同其余因子都相同,则称这两个最小项为相邻最小项

例如:m0和m1具有相邻性,m1和m2却没有,因为他们有两个不同的因子;m3和m4也不相邻,但是m3和m2相邻。

相邻的两个最小项之和可以合并一项消去一个变量。如:

到此,已经具备接下来学习卡诺图的准备知识点,接下来看看怎么画卡诺图以及卡诺图化简法。

2.卡诺图(karnaugh map)

基本知识:

  • 卡诺图是由美国工程师卡诺(Karnaugh)首先提出的一种用来描述逻辑函数的特殊方格图。

  • 在这个方格图中,每一个方格代表逻辑函数的一个最小项,而且几何相邻(在几何位置上,上下或左右相邻)的小方格具有逻辑相邻性,即两相邻小方格所代表的最小项只有一个变量取值不同

  • 对于有n个变量的逻辑函数,其最小项有2^n个。因此该逻辑函数的卡诺图由 2^n  个小方格构成,每个小方格都满足逻辑相邻项的要求。

稍微整理下上面的基本知识点:

  1. 一种描述逻辑函数特殊方格图。
  2. 每格代表一个最小项,上下左右相邻就具备相邻性。
  3. 有n个变量,最小项就有2^n且卡诺图也由2^n个格子构成。

两变量的卡诺图:

三变量的卡诺图:

四变量的卡诺图以此类推吧!就不画了,累啊,偷懒一下。

例2:画出逻辑函数的卡诺图。

解:

通过上面的例子,我们已经掌握如何画卡诺图,接下来就是如何使用卡诺图进行化简。

3.逻辑函数的卡诺图化简法

卡诺图相邻性的特点保证了几何相邻两方格所代表的最小项只有一个变量不同。因此,若相邻的方格都为1(简称1格)时,则对应的最小项就可以合并。合并的结果是消去这个不同的变量,只保留相同的变量。这是图形化简法的依据。     

综上所述,卡诺图具备以下特性:

  1. 卡诺图中两个相邻1格的最小项可以合并成一个与项,并消去一个变量。
  2. 卡诺图中四个相邻1格的最小项可以合并成一个与项,并消去两个变量。
  3. 卡诺图中八个相邻1格的最小项可以合并成一个与项,并消去三个变量。

利用这3点特性来接着看下面的例子:

上图两个相邻1格的最小项可以合并成一个与项,并消去一个变量,化简式子如下:

根据上面3个特性再来看几个例子加深理解,以下是4个相邻1格的:

再来看一题:

用卡诺图化简法求最简与或表达式

先画出卡诺图,然后转换十进制对应1,2,3,6,7的地方填入为1,其余填写为0(这个步骤有前面的知识点支撑,应该不难理解了。)

然后获得式子:F =m1+m3+m2+m3+m6+m7

即:

好了到此,我们已经清楚如何化简了,接下来是对如何对卡诺图进行画圈进行探讨。

首先,有这么几点需要明确:

  1. 列出逻辑函数的最小项表达式,由最小项表达式确定变量的个数(如果最小项中缺少变量,应按例的方法补齐)。
  2. 画出最小项表达式对应的卡诺图。
  3. 将卡诺图中的1格画圈,一个也不能漏圈,否则最后得到的表达式就会与所给函数不等;1格允许被一个以上的圈所包围。
  4. 圈的个数应尽可能得少。即在保证1格一个也不漏圈的前提下,圈的个数越少越好。因为一个圈和一个与项相对应,圈数越少,与或表达式的与项就越少。
  5. 按照2k个方格来组合(即圈内的1格数必须为1248等),圈的面积越大越好。因为圈越大,可消去的变量就越多,与项中的变量就越少。
  6. 每个圈应至少包含一个新的1格,否则这个圈是多余的。
  7. 用卡诺图化简所得到的最简与或式不是唯一的。

带着这7点来看

例3:用卡诺图化简以下表达式


:  从表达式中可以看出此为四变量的逻辑函数,但是有的乘积项中缺少一个变量,不符合最小项的规定。因此,每个乘积项中都要将缺少的变量补上:

因此,获得整个表达式如下:

这里演示了刚才提示的(1)点,最小项缺少变量补齐。

例2:

错误 (多画一个圈)


正确

例3:

错误(圈的面积不够大)


正确

例4:

错误(圈的面积不够大)


 

例5:

错误(有一个圈无新的1格)


 

到此为止,已经学会了如何利用卡诺图化简法来化简函数。

4.总结

  • 逻辑函数的化简有公式法和卡诺图化简法等。
  • 公式法是利用逻辑代数的公式和规则(定理)来对逻辑函数化简,这种方法适用于各种复杂的逻辑函数,但需要熟练地运用公式和规则(定理),且具有一定的运用技巧。
  • 卡诺图化简法简单直观,容易掌握,但变量太多时卡诺图太复杂,一般说来变量个数大于等于5时该法已不适用。
  • 在对逻辑函数化简时,充分利用无关项可以得到更为简单的结果。(有关无关项的知识点,在此文章没有提及。自己查找相关学习吧)

 

 

 

 

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/hahasusu/article/details/88244155

智能推荐

放弃循环依赖 linux,--aid 解决rpm安装过程中循环依赖_weixin_39736606的博客-程序员信息网

redhat的包管理怎么都比apt要差些,有时候会被他的依赖弄得想杀人了.....你安装一个包,结果他告诉你依赖另外一个包,再安装那个包,又是依赖下一个.....特别当产生循环依赖的情况下,很让人郁闷,如下:libselinux-1.33.4-5.5.el5.i386.rpmlibselinux-devel-1.33.4-5.5.el5.i386.rpmlibselinux-python-1.33...

Mac 终端解压缩命令大全_chase…的博客-程序员信息网_mac终端解压命令

tar解包:tar xvf FileName.tar打包:tar cvf FileName.tar DirName(注:tar是打包,不是压缩!)———————————————.gz解压1:gunzip FileName.gz解压2:gzip -d FileName.gz压缩:gzip FileName———————————————.tar.gz 和 .tgz解压:tar zxvf FileName.tar.gz压缩:tar zcvf FileName.tar.gz DirName

一些 iOS问题解决_XLsn0w的博客-程序员信息网

1.解析详情页(是webView)遇到的3个问题:1.图片太大,超出屏幕范围2.怎么在webView上面添加一行文字3.文字太小1.解决方法webView.scalesPageToFit =YES;2.字符串拼接html代码3.解决方法设置代理- (void)webViewDidFinishLoad:(UIWebView *)webView{[w

Java从入门到入土之集合篇_开发的终极是测试的博客-程序员信息网

集合学习笔记概述Collection接口:Set接口:Queue接口:Map接口:概述Collection是集合层次结构中的根界面,依赖于 Iterator,Map接口。Collection下有3个重要子接口:List,Set,Queue。Collection接口:List:有序集合(也称为序列 )几个重要实现类:Arraylist: 底层使用动态数组实现。我们知道数组的长度一旦申...

青龙面板 Nolan 诺兰 2.4 安装教程_大熊猫i的博客-程序员信息网

什么是NolanJDC?NoLanJDC是NolanHzy大佬开发的通过短信验证获取ck的小工具。关注公众号不迷路。安装注意事项请先安装好青龙面板,拉库完毕以后,再进行以下操作!本教程基于Faker一键配置Docker脚本安装,服务器重置干净以后,先运行Faker仓库一键配置,再按本教程安装,基本上不会出错。如有出错,请自行查找原因。Faker仓库一键配置教程安装教程开始老样子我们打开Finalshell,连接好服务器。安装Gityum install -y git第一步 拉库

使用memcached进行内存缓存_太阳火神的美丽人生的博客-程序员信息网

使用memcached进行内存缓存Posted on 2009-01-14 11:11 linFen 阅读(254) 评论(0) 编辑 收藏通常的网页缓存方式有动态缓存和静态缓存等几种,在ASP.NET中已经可以实现对页面局部进行缓存,而使用memcached的缓存比ASP.NET的局部缓存更加灵活,可以缓存任意的对象,不管是否在页面上输出。而memcached最大的优点是可以分布式的部署,这对于

随便推点

对accuracy、precision、recall、F1-score、ROC-AUC、PRC-AUC的一些理解_weixin_30919919的博客-程序员信息网

  最近做了一些分类模型,所以打算对分类模型常用的评价指标做一些记录,说一下自己的理解。使用何种评价指标,完全取决于应用场景及数据分析人员关注点,不同评价指标之间并没有优劣之分,只是各指标侧重反映的信息不同。为了便于后续的说明,先建立一个二分类的混淆矩阵 ,以下各参数的说明都是针对二元分类 ...

zabbix5.0版本监控环境安装部署(CentOS7.5)_蜗牛速度在更新的博客-程序员信息网_zabbix5.0安装部署

zabbix官方网址:https://www.zabbix.com/cn/download?zabbix=5.0&os_distribution=centos&os_version=7&db=mysql&ws=nginx基于LNMP模式,进行安装部署。zabbix5.0中文使用手册https://www.zabbix.com/documentation/5.0/zh/manual/quickstart/loginzabbix原理图示如下图,也可

linux下如何使用自己安装的SunJDK替换默认的OpenJDK_rj042的博客-程序员信息网

在linux系统中,由于涉及到版权问题,在大部分linux系统的发行版本中,默认都安装了OpenJDK,并且OpenJDK的java命令也已经加入到环境变量中了。在刚装好的linux系统中,运行java -version,输出如下(根据JDK版本不同,输出的版本可能不同):java version "1.7.0_131"OpenJDK Runtime Environment (rh

java compile方法_Java中带有示例的模式compile()方法_jian bao的博客-程序员信息网

java.regex包的模式类是正则表达式的编译表示。此类的compile()方法接受表示正则表达式的字符串值,并返回Pattern对象。示例importjava.util.Scanner;importjava.util.regex.Matcher;importjava.util.regex.Pattern;publicclassCompileExample{publicstatic...

超硬核!11 个非常实用的 Python 和 Shell 拿来就用脚本实例!_Jack Tian的博客-程序员信息网

作者:养乐多 编辑:JackTian来源:公众号「杰哥的IT之旅」ID:Jake_Internet原文链接:超硬核!11 个非常实用的 Python 和 Shell 拿来就用脚本实例!转载请联系授权(微信ID:Hc220088)关注公众号:「杰哥的IT之旅」后台回复:「脚本合集」可获取本文全部脚本实例文件关注公众号:「杰哥的IT之旅」后台回复:「wx」 可邀请你加入读者交流群大家好,我是JackTian。在上一篇分享的原创文章《7 个非常实用的 Shell 拿来就用脚本实例!》中.

Python——因子分析(KMO检验和Bartlett's球形检验)_蔡军帅的博客-程序员信息网

因子分析用Python做的一个典型例子一、实验目的采用合适的数据分析方法对下面的题进行解答二、实验要求采用因子分析方法,根据48位应聘者的15项指标得分,选出6名最优秀的应聘者。三、代码import pandas as pdimport numpy as npimport math as mathimport numpy as npfrom numpy impor...

推荐文章

热门文章

相关标签