逻辑代数及逻辑函数化

逻辑代数及逻辑函数化数字逻辑

(2002级本科生课程)清华大学计算机系杨士强yangshq@赵有建zhaoyj@第2页,共57页，2024年2月25日，星期天引言“数字逻辑”课程的地位数字与逻辑数字与模拟数字逻辑领域的前沿问题课程的主要内容如何学好这门课第3页,共57页，2024年2月25日，星期天CC2001(ComputingCurricula)计算机学科人才的专业能力要求：计算思维能力—抽象思维能力和逻辑思维能力算法设计与分析能力程序设计能力计算机系统的认知、分析、设计和应用能力为实现上述要求设置的四大系列课程：公共基础系列，基础理论系列，软件技术系列，硬件技术系列第4页,共57页，2024年2月25日，星期天“数字逻辑”是计算机硬件技术系列的基础计算机系统结构计算机组成原理数字逻辑计算机系统的软硬件功能分配计算机系统的逻辑实现计算机组成的物理实现第5页,共57页，2024年2月25日，星期天数字与逻辑(Digital&Logic)逻辑：研究思维的规律性；关于思维形式及其规律的科学；研究概念、判断和推理以及相互联系的规律、规则，以帮助人们正确地思维和认识客观真理。学习工作时时处处离不开“逻辑”：讲话要有逻辑性、写论文逻辑层次要清晰；逻辑推理能力、逻辑判断能力……数理逻辑：研究推理、计算等逻辑问题，又称符号逻辑，是离散数学的重要内容，是计算机科学的基础。数字逻辑：用二进制为基础的数字化技术解决逻辑问题。第6页,共57页，2024年2月25日，星期天数字与逻辑(Digital&Logic)逻辑代数：应用代数方法研究逻辑问题，又称布尔代数，开关代数（还有开关理论，开关电路等），是逻辑化简的主要工具。

数字逻辑电路的设计、分析，要借助于逻辑代数这一数学工具。逻辑代数中二值运算的公式、运算及定律要应用到数字逻辑电路。实现逻辑功能可用的数字电路：

1、数字集成电路

2、可编程逻辑器件(PLD)第7页,共57页，2024年2月25日，星期天数字与模拟(Digital&Analog)

（离散与连续）digit原意泛指“数目的文字”。在计算机领域，digital与其它词一起使用，主要用于区别“模拟”，指将连续变化的模拟量用二进制数表达和处理。现实世界中存在模拟与数字两大系统，电子数字计算机是最典型的数字系统。模拟量经采样、量化可转换为数字量。数字量更便于加工、处理、传输、存储等，可靠，抗干扰能力强。数字集成电路是实现数字量处理和运算的功能单元。第8页,共57页，2024年2月25日，星期天+V-V电压p2p时间+V-V电压p2p时间+V-V电压p2p时间(a)模拟表示(b)离散表示(c)脉冲表示第9页,共57页，2024年2月25日，星期天无所不在的“数字化”技术以二进制为代表的数字化技术已经渗透到人们日常生活的各个领域，改变了人们的工作和生活方式。现代数字化技术的核心就是计算机和网络，计算机和网络已经溶入到各个领域，各个方面，无所不在，无所不能。DigitalX举例：数字电视，数字电话，数码相机，数字化仪表，数字化医疗设备，数字图书馆，数字博物馆，数字化地球，数字化城市，西部数字鸿沟……第10页,共57页，2024年2月25日，星期天数字逻辑领域的前沿技术多值逻辑模糊逻辑计算机辅助逻辑设计集成电路设计自动化可编程逻辑设计数字系统与模拟系统的混合设计数字电路的故障诊断与可靠性，等等第11页,共57页，2024年2月25日，星期天软件固化的设计方法

计算机系统演变过程系统的设计过程：第一步：软件算法模拟；第二步：硬件固化硬件系统的发展：

onsystemonboardonchip专用与通用结合，逐步由专用到通用软件：灵活，可任意修改，但速度慢硬件：速度快，不可任意修改软件与硬件在逻辑功能上是统一的，在硬件设计中逐步引进软件可编程的思想，“以存代算的思想，各种可编程逻辑器件（PLD）为硬件设计带来方便。第12页,共57页，2024年2月25日，星期天课程主要内容CC2002“数字逻辑”课程大纲数制与码制逻辑代数逻辑电路表示组合电路分析与设计时序电路分析与设计逻辑门阵列组合逻辑时序逻辑（同步时序）可编程逻辑（PROM，PAL，GAL等）5次实验，最后一次综合实验第13页,共57页，2024年2月25日，星期天学习数字逻辑电路的分析、设计和实现通过计算机系统中用到的典型逻辑电路的设计、分析，达到：

1、掌握逻辑设计和分析的基本方法

2、实现逻辑设计中应当注意的问题

3、熟悉计算机系统中常用IC器件的性能及设计方法BACK第14页,共57页，2024年2月25日，星期天与“数字逻辑”相关的课程数字电路（电子系课程）数字电子技术（自动化系课程）数字技术与系统数字逻辑重点是结合计算机设计中的逻辑问题和常用的集成电路特性，为“计算机原理”课程学习打下基础。数字逻辑可以认为是“数字逻辑电路”，“数字逻辑设计”，“数字逻辑系统”等的简称。英文参考书关键词：”DigitalLogic”,“LogicDesign”,“DigitalDesign”,”DigitalLogicDesign”,“DigitalCircuitDesign”，”DigitalLogicCircuitDesign”,“LogicandComputerDesign”

，”DesignofLogicSystems”,……第15页,共57页，2024年2月25日，星期天如何学好这门课1.计算机学科是实践性极强的学科，重视实践环节，多动手2.掌握研究型的学习方法，学会独立思考，掌握“知识发现过程中大师们的思维过程”3.熟练掌握典型电路的分析方法和设计方法4.作业和实验独立完成成绩比例：20（平时实验）＋20（实验考试）＋60（期末考试）第16页,共57页，2024年2月25日，星期天让我们共同走进数字化世界，开创更加美好的数字化生活！加强交流，教学相长!yangshq@预祝同学们取得优异成绩！第17页,共57页，2024年2月25日，星期天第1章逻辑代数及

逻辑函数化简（数制与编码一章自学）1.1逻辑代数的基本运算与公式1.2公式法化简逻辑函数1.3逻辑函数的标准形式1.4图解法(卡诺图)化简（重点）1.5表格法化简(Q-M法)1.6逻辑函数的实现第18页,共57页，2024年2月25日，星期天1.1逻辑代数的基本运算与公式逻辑代数：二进制运算的基础。应用代数方法研究逻辑问题。由英国数学家布尔(Boole)和德.摩根于1847年提出，又叫布尔代数，开关代数。逻辑函数的表示：真值表，表达式，逻辑门逻辑函数的生成：逻辑问题的描述，由文字叙述的设计要求，抽象为逻辑表达式的过程。然后才能化简、实现，逻辑设计的第一步。逻辑代数的基本运算：与、或、非

(1)“与”运算，逻辑乘

(2)“或”运算，逻辑加

(3)“非”运算，取反第19页,共57页，2024年2月25日，星期天逻辑代数的基本运算ABF真值表F=ABABF001001111110信息论的创始人香侬(Shannon)在1940年首先建立了用电子线路来实现布尔代数表达式，0，1分别代表电路的开、关状态或高、低电平；命题为真，线路建立连结；命题为假，线路断开连结。与非门（A、B是输入，F是输出）第20页,共57页，2024年2月25日，星期天真值表，表达式，逻辑门ABF真值表F=ABABF001001111110实现“与非”逻辑

(NAND——NOT-AND)例：与非门（A、B是输入，F是输出）第21页,共57页，2024年2月25日，星期天真值表，表达式，逻辑门ABF+实现“或非”逻辑(NOR——NOT-OR)真值表ABF001001111000第22页,共57页，2024年2月25日，星期天真值表，表达式，逻辑门ABF+实现“或非”逻辑(NOR——NOT-OR)真值表ABF001001111000第23页,共57页，2024年2月25日，星期天基本公式互补律1律0律BACK第24页,共57页，2024年2月25日，星期天基本公式（续）交换律结合律分配律

第25页,共57页，2024年2月25日，星期天基本公式（续）吸收律反演律(德·摩根定律)第26页,共57页，2024年2月25日，星期天基本公式（续）包含律 推论：对合律重叠律第27页,共57页，2024年2月25日，星期天如何验证公式的正确性真值表利用基本定理化简公式例：真值表验证摩根定律1000A＋B1110A＋B1110AB100000011011ABAB第28页,共57页，2024年2月25日，星期天如何验证公式的正确性真值表利用基本定理化简公式AB+AC+BC=AB+AC(?)（包含律）证明：AB+AC+BC=AB(C+C)+AC(B+B)+BC(A+A)=ABC+ABC+ABC+ABC+ABC+ABC=ABC+ABC+ABC+ABC=AB+AC第29页,共57页，2024年2月25日，星期天1.2公式法化简逻辑函数逻辑函数化简的目的:省器件！用最少的门实现相同的逻辑功能，每个门的输入也最少。主要掌握与或表达式的化简：(1)乘积的个数最少(用门电路实现，所用与门的个数最少)(2)在满足(1)的条件下，乘积项中的变量最少(与门的输入端最少)最简的目标不同，达到的效果也不同。如果功耗最小或者可靠性最高是目标，化简的结果完全不同！BACK第30页,共57页，2024年2月25日，星期天与或表达式化简例：展开：结合：互补律：互补律：BACK第31页,共57页，2024年2月25日，星期天与或表达式化简（续）例：BACK反演律:B+C=BC吸收律：A＋AB＝AB第32页,共57页，2024年2月25日，星期天与或表达式化简（续）包含配项展开合并例：第33页,共57页，2024年2月25日，星期天与或表达式化简（续）续上页吸收律D+DC＝D＋C分配反演D＋C＝DC吸收律：BACK第34页,共57页，2024年2月25日，星期天1.3逻辑函数的标准形式逻辑函数可以表示为最小项之和的形式（与或表达式）或者最大项之积的形式（或与表达式）应用最多的是最小项之和的形式，也叫最小项标准式。最小项也是卡诺图化简的基础。BACK第35页,共57页，2024年2月25日，星期天最小项(MinTerm)逻辑函数有n个变量，由它们组成的具有n个变量的乘积项中，每个变量以原变量或反变量的形式出现且仅出现一次，这个乘积项为最小项。N个变量有2n个最小项。例如：n=3，对A、B、C，有8个最小项第36页,共57页，2024年2月25日，星期天最小项(续)对任意最小项，只有一组变量取值使它的值为1，其他取值使该最小项为0为方便起见，将最小项表示为mi n=3的8个最小项为：

第37页,共57页，2024年2月25日，星期天最小项(续)任何逻辑函数均可表示为唯一的一组最小项之和的形式，称为标准的与或表达式某一最小项不是包含在F的原函数中，就是包含在F的反函数中例：BACK第38页,共57页，2024年2月25日，星期天最大项(MaxTerm)n个变量组成的或项，每个变量以原变量或反变量的形式出现且仅出现一次，则称这个或项为最大项

例如：n=3的最大项为第39页,共57页，2024年2月25日，星期天最大项(续)对任意一个最大项，只有一组变量取值使它的值为0，而变量的其他取值使该项为1将最大项记作Mi任何一个逻辑函数均可表示为唯一的一组最大项之积，称为标准的或与表达式n个变量全体最大项之积必为“0”某个最大项不是含在F的原函数中，就是在F的反函数中第40页,共57页，2024年2月25日，星期天最大项(续)例如：BACK第41页,共57页，2024年2月25日，星期天1.4图解法(卡诺图)化简逻辑函数卡诺图(KarnaughMap):逻辑函数的图示表示，把最小项填入卡诺图，利用相邻最小项的互补性，消去一个变量，实现化简。卡诺图的构成

(1)、由矩形或正方形组成的图形

(2)、将矩形分成若干小方块，每个小方块对应一个最小项BACK第42页,共57页，2024年2月25日，星期天2变量卡诺图(KarnaughMap)2变量卡诺图1整体为1左、右部分表示上、下部分表示第43页,共57页，2024年2月25日，星期天2变量卡诺图(KarnaughMap)2变量卡诺图可由代表4个最小项的四个小方格组成m1

m2

m3m0

AB改画成

2变量卡诺图第44页,共57页，2024年2月25日，星期天3变量KarnaughMap3变量卡诺图由8个最小项组成，对应图中8个小方格

BAC1000110110m1

m0

m3

m2

m5

m4

m7

m6

注意：表中最小项编码按00－01―11－10循环码顺序排列，而不是00－01－10－11（二进制计数的顺序）第45页,共57页，2024年2月25日，星期天什么是循环码相邻两个编码之间只有一位数不同，而且首尾两个编码之间也只有一位数不同，这种编码叫循环码。

2位循环码：

00

01

11

10

3位循环码：

000

001

011

010

110

111

101

100

特点：每次只变一位，相邻两数间只有一位不同；用在卡诺图上，可以消去最小项的多余变量。循环码是无权码，而且不是唯一的编码，如：01，00，10，11同样具有2位循环码的性质。第46页,共57页，2024年2月25日，星期天4变量KarnaughMapBADC0011011000110110m1

m0

m3

m2

m5

m4

m7

m6

m13

m12

m15

m14

m9

m8

m11

m10

第47页,共57页，2024年2月25日，星期天卡诺图化简的步骤1按照循环码规律指定卡诺图变量取值；2在函数最小项对应的小方块填“1”，其他方块填“0”；3合并相邻填“1”的小方块，两个方块合并消去一个变量（一维块）；4个方块合并消去两个变量（二维块）；4合并过程中先找大圈合并，圈越大消去的变量越多；5使每一最小项至少被合并包含过一次；每个合并的圈中，至少要有一个“1”没有被圈过，否则这个圈就是多余的。第48页,共57页，2024年2月25日，星期天“与或”式化简：例1将表达式F=AB+AC填入卡诺图

BAC10001101100

0

10

01

1

1第49页,共57页，2024年2月25日，星期天“与或”式化简：例2BADC

110011011000110110第50页,共57页，2024年2月25日，星期天“与或”式化简：例2（续）BADC

1111110011011000110110第51