第1章 逻辑代数基础(new)

1、复旦大学电子工程系 陈光梦数字逻辑基础复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础2数字逻辑与数字电路的历史逻辑代数的历史1849年，爱尔兰数学家乔治布尔(George Boole)创立布尔代数。20世纪30年代，在贝尔实验室工作的香农(Claude Shannon)继承了布尔的工作并加以发展和应用。随着电子技术和计算机技术的发展，布尔代数在数字逻辑电路的分析和设计中得到了广泛的应用，统称为逻辑代数。复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础3集成电路的历史1947年晶体管发明引起了电子学的一次革命。晶体管由巴丁(John Bardeen) 、布雷登(Wailte

2、r Houser Brattain)和肖克莱(William Schokley)共同发明，该发明促成了计算机、通信等方面的飞速发展。鉴于它的重要价值，这些人共同获得了1956年的诺贝尔物理学奖。1958年，德克萨斯仪器公司的基尔白(Clair Kilby)、仙童半导体公司的诺依斯(Robert Noyce)等人研究实现了集成电路。以后集成度越来越高，出现了超大规模集成电路，这是电子学的又一次革命，也是近代科学技术发展的新的标志。复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础4集成电路的分类与数字集成电路的特点集成电路分类模拟集成电路，处理的信号是连续的（模拟信号）数字集成电路，处理

3、的信号是离散的（数字信号）数字集成电路分类逻辑集成电路、存储器、各类ASIC数字集成电路特点信息表示形式统一、便于计算机处理可靠性高制造工艺成熟、可以大规模集成复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础5数字集成电路的发展集成度SSI（1-10门，逻辑门电路）MSI（10-100门，计数器、移位寄存器器）LSI（100-1000门，小型存储器、8位算术逻辑单元）VLSI（1000-100万门，大型存储器、微处理器）ULSI（超过100万门，可编程逻辑器件、多功能集成电路）摩尔定律集成度每18个月翻一番复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础6本课程的内容l数字

4、逻辑的基本理论：逻辑代数l无记忆的逻辑电路：组合逻辑电路l有记忆的逻辑电路：触发器及时序逻辑电路（同步和异步）l可编程逻辑器件和数字系统：软件实验、后续课程学习复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础7教科书与参考书教科书：陈光梦，数字逻辑基础，复旦大学出版社参考书：l陈光梦等，数字逻辑基础学习指导与教学参考，复旦大学出版社l阎石，数字电子技术基础，高教出版社lVictor P. Nelson etc，Digital Logic Circuit Analysis and Design，清华大学出版社lJohn M. Yarbrough，数字逻辑应用与设计，机械工业出版社l刘宝

5、琴，数字电路与系统，清华大学出版社l唐竞新，数字电子技术基础解题指南，清华大学出版社l曾繁泰等，VHDL程序设计，清华大学出版社复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础8与教师的联系l虚拟校园： http:/l电子邮件： l电话： 65643789复旦大学电子工程系 陈光梦第1章逻辑代数基础复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础10本章要求掌握逻辑代数的基本公式和基本定理掌握逻辑函数的化简方法复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础111.1 逻辑代数概述l二值逻辑：逻辑关系中的条件和结论只取对立的两个值，例如是和非、对和错、真和假等等。

6、l在逻辑代数中，通常用“1”代表“真”，用“0”代表“假”。l二值逻辑的“1”与“0”是逻辑概念，仅代表真与假，没有数量大小。l在数字逻辑中，有时也用“1”与“0”表示二进制数。这仅仅是一种代码，实际的运算规律还是依照逻辑运算进行。复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础12常用二十进制代码十进制码二进制码（8421码）余三码余三循环码移位码5211码5421码0000000110010000000000000010001010001100000100010001200100101011100011010000103001101100101001110101001140100

7、0111010001111011101005010110001100111111000100060110100111011111010011001701111010111111100110010108100010111110110001101101191001110010101000011111100复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础13逻辑函数用一个数学表达式来描述一个逻辑关系问题逻辑条件 输入变量（自变量）逻辑结论 输出变量（因变量）),(BAfY 复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础14逻辑函数的表示方法l真值表l逻辑函数l逻辑图l卡诺图l硬

8、件描述语言（HDL）以上5种表示方法可以相互转换，各有特定用途复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础15真值表ABY000010100111A B Y复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础16逻辑函数：基本逻辑运算l与 Y = A B l或 Y = A + Bl非 Y =AAAA + BA B复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础17“与” 运算ABY = AB000010100111A B Y复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础18“或” 运算ABY = AB000011101111ABY复旦大学电子工程系 陈

9、光梦2021-11-20数字逻辑基础19“非”运算AY0110AY =A Y复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础20反函数l两个逻辑函数互为反函数，是指两个逻辑函数对于输入变量的任意取值，其输出逻辑值都相反。下面真值表中 F 和 G 互为反函数。ABF(A,B)G(A,B)0001010110011110复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础21复合逻辑运算1. 与非2. 或非 3. 异或4. 同或 ABY BAYYABABABY = A B BABA 复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础22复合逻辑运算的真值表ABABABABA

10、 B001101011010101010110001复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础23逻辑图：基本逻辑单元&11逻辑与逻辑或逻辑非&1=1与非或非异或=同或复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础24逻辑图符号标注规定（GB4728.12-1996）所有逻辑符号都由方框（或方框的组合）和标注在方框内的总限定符号组成 &总限定符号& 1 =1 = 外部逻辑状态逻辑约定小圈表示逻辑非也可采用极性指示符内部逻辑状态复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础25组合形式的逻辑图&=1=1&=1

11、一般表示法组合表示法ABCABCYY)()(CBBAY复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础26国外逻辑图符号对照与门或门非门美、日常用符号国标符号GB4728.12-1996&11复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础27异或门或非门与非门同或门&1=1=美、日常用符号国标符号GB4728.12-1996复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础281.2 逻辑代数的基本定理一、变量与常量的运算(0-1律) A 1 = AA + 0 = AA 0 = 0A + 1 = 1二、等幂律A A = AA+A = A三、互补律A

12、 = 0A+ = 1四、自反律 = AAAA复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础29五、交换律 AB = BA A+B = B+A六、结合律 A(BC) = (AB)C A+(B+C) = (A+B)+C七、分配律 A(B+C) = AB+AC A+BC = (A+B)(A+C)八、反演律（De Morgan定理 ） BABABAAB复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础30代入定理在任何一个逻辑等式中，若将其中一个逻辑变量全部用另一个逻辑函数代替，等式仍然成立。 例： 若 Y=AC + BC， C = P + Q则 Y = A (P + Q) + B

13、 (P + Q)复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础31反演定理对于任何一个逻辑函数式，将其中的:所有逻辑符号 “ + ”、“ ” 交换;所有逻辑常量 “ 1 ”、“ 0 ” 交换;所有逻辑变量取反;不改变原来的运算顺序。得到的逻辑函数是原来逻辑函数的反函数。 例：1)(0DCBAYDCBAY复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础32对偶定理对偶关系：逻辑符号“ + ”和“” 逻辑常量“ 1 ”和“ 0 ”对偶式： 所有逻辑符号“ + ”“”交换 所有逻辑常量“ 1 ”“ 0 ”交换若两个函数相等，则由他们的对偶式形成的两个函数也相等。 例：若 则1)

14、(0)(DCCACADDCCACDA复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础33注意点l反演定理：描述原函数和反函数的关系（两个函数之间的关系）l对偶定理：描述原函数构成的逻辑等式和对偶函数构成的逻辑等式的关系（两个命题之间的关系）l在一般情况下，一个逻辑函数的反函数和对偶函数是不同的复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础34常用逻辑恒等式,(),(),()()AABAA ABAAABABA ABABA ABABAABABABABBAB ABB一、吸收律复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础35()()()()()()()()()()A

15、BACBCABACAB AC BCAB ACABACBCDABACAB AC BCDAB AC二、冗余律复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础361.3 逻辑函数的化简与形式转换目标函数形式（原因：实际电路的需要）l与或形式l或与形式l与非与非形式l或非或非形式l与或非形式l混合形式复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础37目标函数的要求：l逻辑电路的数量最少（面积约束）l逻辑电路的级数最少（速度约束）l输入端的数量最少（混合约束）l电路稳定可靠 （避免竞争冒险）具体问题具体分析，没有一成不变的规定复旦大学电子工程系 陈光梦2021-11-20数字逻辑基

16、础38代数法化简逻辑函数l公式法化简可以适用于任何场合，但是通常没有一定的规律可循，需要敏锐的观察力和一定的技巧。 l最常用的化简手段是吸收律、冗余律和反演律。复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础39代数法化简的例子()YABCABCABABABAYABCABCABABABB例一、化简函数解：利用，将原式化简：复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础40()()YABACDBCDABAAYABACDBCDABAB CDABABCDABAB例二、化简函数解：利用反演律和，将原式化简复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础411()()()

17、()()YABBCBCABAAYABBCAA BCAB CCABBCABCABCABCABCABABCBCABCABCABCABBCAC例三、化简函数解：利用，在原式中添加一些项，然后化简复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础420()()YABCABC ABA AYAB ABABCABC ABAB ABCABC ABAB ABCABC ABABC例四、化简函数解:利用，在原式中添加一些项，然后化简复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础43逻辑函数形式转换的例子*() ()( *)*()()()()YABCDYABCDACBCADBDYYAC BCAD

18、BD以逻辑函数为例：例一、将“与或”函数化为“或与”式利用对偶定理实现之：复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础44YABCDYABCDAB CD例二、将“与或”函数转化为“与非与非”式利用两次求反，将原式转换：复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础45( *)*()()()()()()()()()()()()YABCDYYAC BCAD BDAC BCAD BDACBCADBD例三、将“与或”函数化为“或非或非”式解：先利用对偶定理变成“或与”式，再两次求反复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础46() ()YABCDYABCDAB

19、 CDABCDACB CA DB D例四、将“与或”函数化为“与或非”式解：利用两次求反，将原式转换复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础47逻辑函数的卡诺图表示和卡诺图化简法特点：l图形化简法l标准的表达方式l规律的化简过程l变量数目有限制（最多56个）复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础48最小项在n个逻辑变量的逻辑函数中，若m为包含n个因子的乘积项（逻辑与），且其中每个逻辑变量都以原变量或反变量的形式出现一次并仅仅出现一次，则称m为这n个变量的最小项。例： 记为m2 记为m5 记为m7abccbacbaabccbacbaabcf)(复旦大学电子工

20、程系 陈光梦2021-11-20数字逻辑基础49最大项在n个逻辑变量的逻辑函数中，若M为包含n个因子的和项（逻辑或），且其中每个逻辑变量都以原变量或反变量的形式出现一次并仅仅出现一次，则称M为这n个变量的最大项。例： 记为M2 记为M5 记为M7cbacbacbacbacbacbaabcf)()()(复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础50最小项与最大项的比较以3变量函数为例CBAMCBAmCBAMCBAmCBAMCBAmCBAMCBAmCBAMCBAmCBAMCBAmCBAMCBAmCBAMCBAm7766554433221100最大项：最小项：最大项：最小项：最大项：

21、最小项：最大项：最小项：最大项：最小项：最大项：最小项：最大项：最小项：最大项：最小项：复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础51最小项和最大项的性质对于一个具有 n 个变量的逻辑问题，在输入变量的任意一种取值情况下，总有：一、必有且仅有一个最小项的逻辑值为1；必有且仅有一个最大项的逻辑值为0。二、任意2个不同的最小项之积为0；任意两个不同的最大项之和为1。1, 0jijiMMmm复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础52三、全体最小项之和为1；全体最大项之积为0。四、下标相同的最大项和最小项互补。1201200, 1nniiiiMmiiMm 复旦大学电

22、子工程系 陈光梦2021-11-20数字逻辑基础53逻辑函数的两种标准表达式最小项之和形式，简称为积之和(SOP)形式 最大项之积形式，简称为和之积(POS)形式 10),.,(12021ormxxxfiiiinn，10)(),.,(12021orMxxxfiiiinn，复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础54标准表达式的关系性质1、一个逻辑函数的两种标准逻辑表达式之间，存在以下关系： 若 则性质2、一个逻辑函数与其反函数的逻辑表达式之间，存在以下关系： 若 则imFjMFimFiMF复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础55将逻辑函数化成标准形式l要

23、求按积之和形式展开函数，可以将非最小项的积项乘以形如 的项，其中A 是那个非最小项的积项中缺少的输入变量，然后展开，最后合并相同的最小项。l要求按和之积形式展开函数，可以将非最大项的和项加上形如 的项，其中A 是那个非最大项的和项中缺少的输入变量，然后展开，最后合并相同的最大项。AAAA复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础56卡诺图l每个方格代表一个最小项或者最大项。 l变量排列按照相邻规则进行，即在卡诺图中相邻的方格在逻辑上也相邻。（相邻的意义：两个最小项或最大项之间只有一个变量发生变化）BCA000111100101326457BA01010123CDAB000111

24、10013264570001111012131514108911复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础57卡诺图的填法X3 X4X1 X200011110100001100001111001110111)12,10, 7 , 6 , 3 , 2, 1 ()15,14,13,11, 9 , 8 , 5 , 4, 0(),(4321Mmxxxxf最小项填 1最大项填 0复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础58卡诺图化简法根据相邻的方格在逻辑上也相邻的原理，只要相邻的方格满足以下条件：一、逻辑值相同；二、小方格数为 2n 个。就可以将相邻的方格合并为一个卡诺

25、圈。卡诺圈越大，可以消去的变量越多，最后得到的逻辑函数越简单。若卡诺圈包含的小方格数为 2n 个，而这个逻辑函数具有 m 个变量，则这个卡诺圈对应的项中包含的变量数目为 mn 个。复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础59卡诺图的圈法（SOP）圈“1”包含2n个方格尽可能大不遗漏X3 X4X1 X200011110100001100001111001110111X1 X2 X3X1 X4X2 X3 X4X1 X2 X341321321432xxxxxxxxxxxf复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础60卡诺图的圈法（POS）圈“0”包含2n个方格尽可能

26、大不遗漏X3 X4X1 X200011110100001100001111001110111X2+X3+X4X1+X3X1+X2+X4X1+X2+X3+X4)()()(314324321421xxxxxxxxxxxxf复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础61卡诺图化简法的要点l将逻辑函数化为标准形式（或真值表）l填卡诺图l圈卡诺圈（满足2n个方格要求、尽可能大、不遗漏）l根据卡诺圈写出化简后的逻辑函数l若有必要，运用反演律对所得结果进行变换复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础62卡诺图化简的例（一）12( , , , ) ( , , , ) (3,4

27、,6,11,12,14) (0,1,2,5,8,10,13)Ff a b c dFf a b c dmm00110011000 01 11 1000101101ab0001100cd11000100100 01 11 1000101101ab1010001cd复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础63卡诺图化简的例（二）34( , , , ) ( , , , ) (0,1,2,5,8,10,13) (3,5,7,9,11)Ff a b c dFf a b c dMM00111011000 01 11 1000101101ab0101110cd11110010100 01 1

28、1 1000101101ab1110101cd复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础64卡诺图化简法的一些术语l蕴涵：逻辑函数的“与或”表达式中的各项 l质蕴涵 ：不能再与其他蕴涵合并的蕴涵l必要质蕴涵：包含一个或多个唯一的最小项的质蕴涵l覆盖：包含了逻辑函数中所有最小项的一些蕴涵之“或”l非冗余覆盖：其中每一个蕴涵都是必不可少的覆盖l最小覆盖：包含蕴涵个数最少的非冗余覆盖复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础65最小覆盖的不惟一性X3 X4X1 X200011110100101110001111001101001 一个逻辑函数，其最小覆盖总是由必要质蕴

29、涵和部分质蕴涵组成，所以它的最小覆盖可能不是惟一的，即它的最简逻辑表达式可能不是惟一的。 绿色：必要质蕴涵红色和白色：质蕴涵最小覆盖： 绿色红色或：绿色白色复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础66利用卡诺图运算来进行逻辑化简逻辑函数 卡诺图逻辑函数的运算 卡诺图的运算卡诺图的运算 对应的方格进行运算 证明（以“与”运算为例）：11221212121212,()()()iiiiiiiiiiiiiijiiiiijifmfmffmmmm mm设则有证明的最后一步运用了最小项的性质 2思考题:试证明“或”、“非”运算亦符合上述规则复旦大学电子工程系 陈光梦2021-11-20数字

30、逻辑基础67利用卡诺图运算来进行逻辑化简的例CD000111101111111100011110111111ABCD000111101111000111101111ABCD00011110111100011110111ABYBCDA=)14,13,12, 7 , 6 , 5 , 4(),(mDCBAYBADBCBYCDABY常规化简运算化简复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础68CD00011110110001111011111ABCD00011110110001111011111ABCD000111101000111101111ABYAB+CDAD+BC=)15,14,

31、13,11, 7(),(mDCBAYACDBCDABCABDY)()(BCADCDABY常规化简 结果为 3、4 输入端，共16输入端运算化简 结果为 2 输入端，共14输入端复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础69卡诺图运算的一些有关规律 l0重心：0号方格（即全部变量为0的方格） 1重心：2n-1号方格（即全部变量为1的方格）l包含0重心但不包含1重心的质蕴涵，其表达式全部用反变量标注l包含1重心但不包含0重心的质蕴涵，其表达式全部用原变量标注l既不包含0重心也不包含1重心的质蕴涵，其表达式中一定既有原变量又有反变量l目标函数是与非形式并要求全部用原变量表达时，围绕1

32、重心进行。其中卡诺圈圈1，阻塞圈圈0l目标函数是或非形式并要求全部用原变量表达时，围绕0重心进行，其中卡诺圈圈0，阻塞圈圈1复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础70不完全确定的逻辑函数的化简不完全确定的逻辑函数： 由 n 个逻辑变量构成的逻辑函数中，有效的逻辑状态数小于2n个。那些无效的状态或者是不可能出现，或者无意义。这些无效的状态被称为任意项，或称为无关项、约束这些无效的状态被称为任意项，或称为无关项、约束项、禁止项，等等项、禁止项，等等 复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础71任意项的处理任意项的值既可为1也可为0带有任意项的逻辑函数在化简时既

33、可以将任意项圈入卡诺圈，也可以不圈入卡诺圈适当地将一些任意项圈入卡诺圈，可以使化简的结果得到极大的简化X3 X4X1 X2000111101100011110d11d1dd黄色：不考虑任意项红色：考虑任意项复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础7201001100100 01 11 1000101101uvd1ddd10wx56( , , , ) ( , , , ) (2,3,4,5,13,15) (1,5,7,9,13,15) (8,9,10,11) (8,10,11,14)Ff a b c dFf u v w xmmdd01000111000 01 11 1000101

34、101abd1dd0d1cd复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础73注意点任意项的表现形式除了直接用最小项形式表示外，还经常用逻辑表达式表示，称为约束方程对于用约束方程给出的逻辑问题，一般要将约束条件改写成用最小项表示的任意项形式，才能用卡诺图进行化简 例如：A =1、B =1这种输入状态不可能出现，可记为AB=0。在卡诺图中就是对应AB=11的最小项为任意项 复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础74使用异或函数的卡诺图化简异或运算的性质: ABBACBACBACBA)()(AAAA1,01, 0AAAABABABA复旦大学电子工程系 陈光梦2021

35、-11-20数字逻辑基础75异或（同或）函数的卡诺图l“棋盘格”特征 l异或函数的棋盘格特征：0号方格等于0l同或函数的棋盘格特征：0号方格等于1X3 X4X1 X2000111101100011110111111X3 X4X1 X2000111101100011110111111同或函数异或函数复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础76利用异或函数化简的例子（一）10000100000 01 11 1000101101ab0110000cd)(dbcaPdcbW00101010100 01 11 1000101101ab0110011cd复旦大学电子工程系 陈光梦2021-11-20数字逻辑基础77利用异或函数化简的例子（二）X3 X4X1