《复旦数字逻辑基础课件chapter+1》由会员分享，可在线阅读，更多相关《复旦数字逻辑基础课件chapter+1（81页珍藏版）》请在金锄头文库上搜索。
1、第1章 逻辑代数基础 范益波 2014.92014.9 Video Image Processing (VIP) Research Group Fudan 本章内容 如何用0、1来描述逻辑关系？ 如何通过简单逻辑构建复杂逻辑？ 逻辑可以“化简”么？ 逻辑的终极构件“与”“非” 本章要求 掌握逻辑代数的基本公式和基本定理 逻辑函数的各种表达方式 掌握逻辑函数的化简方法 1.1 逻辑代数概述 二值逻辑：逻辑关系中的条件和结论只取对立的两个值， 例如是和非、对和错、真和假等等。 在逻辑代数中，通常用“1”代表“真”，用“0”代表“假”。 二值逻辑的“1”与“0”是逻辑概念，仅代表真与假，没有数 量大
2、小。 在数字逻辑中，有时也用“1”与“0”表示二进制数。这仅仅 是一种代码，实际的运算规律还是依照逻辑运算进行。 逻辑函数 用一个数学表达式来描述一个逻辑关系问题 逻辑条件 输入变量（自变量） 逻辑结论 输出变量（因变量） ),(BAfY 举例：用A表示是否有空闲，B表示是否有电影票，Y表示是 否去看电影，Y=f(A,B)表示三者逻辑关系。 逻辑函数的表示方法 真值表 逻辑函数 逻辑图 卡诺图 硬件描述语言（HDL） 以上5种表示方法可以相互转换，各有特定用途 真值表 真值表：将逻辑关系用表格的形式表达出来。N个输入变 量时，有2N种可能的输入组合，每种组合对应一行。这样 逐一列出逻辑函数逻辑
3、值的表格，称为该逻辑函数的真值 表(truth table) A B Y ABY 000 010 100 111 例：看电影问题 的逻辑真值表 逻辑函数：基本逻辑运算 与(AND) Y = A B 或(OR) Y = A + B 非(NOT) = AA A + B A B 可简记为AB “与” 运算 ABY = A B 000 010 100 111 A B Y 只有参与运算的所有输 入变量都为“真”，运 算结果才为“真”。 “或” 运算 ABY = AB 000 011 101 111 B A Y 只要任一参与运算的 输入变量为“真”， 运算结果即为“真”。 “非”运算 AY 01 10 A
4、 A Y 运算结果是输入变 量的相反值。 = 三种基本运算的优先级 逻辑非的优先级最高 逻辑与的优先级其次 逻辑或的优先级最低 可以用加括号的方法来改变运算顺序。不引起误 解的情况下可省略括号。 例如： YABCD 反函数 两个逻辑函数互为反函数，是指两个逻辑函数对 于输入变量的任意取值，其输出逻辑值都相反。 下面真值表中 F 和 G 互为反函数。 ABF(A,B)G(A,B) 0001 0101 1001 1110 复合逻辑运算 1. 与非 2. 或非 3. 异或 4. 同或 Y = AB= + 可用穷举法验证异或、同或的上述等式。 = = + = + = 练习：画真值表，验证异或、同或的等
5、式是否正确。 复合逻辑运算的真值表 ABAB 001101 011010 101010 110001 + 逻辑图：基本逻辑单元 所有逻辑常量 “ 1 ”、“ 0 ” 交换; 所有逻辑变量取反; 不改变原来的运算顺序。 得到的逻辑函数是原来逻辑函数的反函数。 例： 例：利用反演定理可方便地 写出反函数. 参考书p9.是反演律的推广是反演律的推广 = + + 0 = ( + )( + ) 1 对偶定理 对偶关系：逻辑符号“ + ”和“” 逻辑常量“ 1 ”和“ 0 ” 对偶式：所有逻辑符号“ + ”“”交换 所有逻辑常量“ 1 ”“ 0 ”交换 若两个函数相等，则由他们的对偶式形成的两个函 数也相
6、等。 例：若 则 利用对偶定理，可以帮助我们记忆逻辑公式。另外，在证明某些复杂的逻辑 等式时，有时通过证明它们的对偶式来完成可能更方便。 ( + ) = + + 0 + = ( + )( + ) 1 注意点 反演定理：描述原函数和反函数的关系（两个函数 之间的关系） 对偶定理：描述原函数构成的逻辑等式和对偶函数 构成的逻辑等式的关系（两个命题之间的关系） 在一般情况下，一个逻辑函数的反函数和对偶函数 是不同的 常用逻辑恒等式 上述恒等式的简要证明，参考书p8. 一、吸收律 ,() ,() , ,()() AABAA ABA AABABA ABAB A ABABAABAB ABABBAB ABB
7、 上述恒等式的简要证明，参考书p8. 二、冗余律 ()()()()() ()()()()() ABACBCABAC AB AC BCAB AC ABACBCDABAC AB AC BCDAB AC 1.3 逻辑函数的化简与形式转换 目标函数形式（原因：实际电路的需要） 与或形式 或与形式 与非与非形式 或非或非形式 与或非形式 混合形式 目标函数的要求 逻辑电路的数量最少（面积约束） 逻辑电路的级数最少（速度约束） 输入端的数量最少（混合约束） 电路稳定可靠 （避免竞争冒险） 具体问题具体分析，没有一成不变的规定 代数法化简逻辑函数 公式法化简可以适用于任何场合，但是通 常没有一定的规律可循，
8、需要敏锐的观察 力和一定的技巧。 最常用的化简手段是吸收律、冗余律和反 演律。 代数法化简的例子 () 例一、化简函数 解：利用，将原式化简： YABCABCAB ABABA YABCABCAB ABAB B 其它证明：例如把(ab)反使用反演定理。 () () 例二、化简函数 解：利用反演律和，将原式化简 YABACDBCD ABAA YABACDBCD ABAB CD ABABCD AB AB 1 ()() ()()() 例三、化简函数 解：利用，在原式中添加一些项，然后化简 YABBCBCAB AA YABBCAA BCAB CC ABBCABCABCABCABC ABABCBCABCA
9、BCABC ABBCAC 例1-7到例1-17，参考书p18-p19 其它证明：例如把(abc)反使用反演定理。 0 () () 例四、化简函数 解:利用，在原式中添加一些项，然后化简 YABCABC AB A A YAB ABABCABC AB AB ABCABC AB AB ABCABC ABABC 逻辑函数形式转换的例子 “与或”变“或与”：先取对偶式变或与，再利用分配律变与或，再对偶成或与 例1-17 *() () ( *)* ()()()() 以逻辑函数为例： 例一、将“与或”函数化为“或与”式 利用对偶定理实现之： YABCD YABCD ACBCADBD YY AC BCAD B
10、D “与“与- -或”变“与或”变“与- -非”，利用两次求反非”，利用两次求反 例二、将“与或”函数 转化为“与非与非”式 利用两次求反，将原式转换： YABCD YABCD AB CD “与“与- -或”或”变“或变“或- -非”非”，利用对偶变或与，两利用对偶变或与，两次求反次求反 ( *)* ()()()() ()()()() ()()()() 例三、将“与或”函数 化为“或非或非”式 解：先利用对偶定理变成“或与”式，再两次求反 YABCD YY AC BCAD BD AC BCAD BD ACBCADBD () () 例四、将“与或”函数 化为“与或非”式 解：利用两次求反，将原式
11、转换 YABCD YABCD AB CD ABCD ACB CA DB D “与“与- -或”变“与或”变“与- -或或- -非非”，两，两次求次求反，底部展开反，底部展开 变换总结： “与或”变“与非” “或与”变“或非” “与或”变“或与” “或与”变“与或” “与或”变“或非” “或与”变“与非” “与或”变“与或非” 练习： 写出同或函数的与或、或与、与非、或 非、与或非式表达 逻辑函数的卡诺图表示和卡诺图化简法 特点 图形化简法 标准的表达方式 规律的化简过程 变量数目有限制（最多56个） 最小项 ()f abcabcabcabc abc abc abc 在n个逻辑变量的逻辑函数中，
12、若m为包含n个因子 的乘积项（逻辑与），且其中每个逻辑变量都以 原变量或反变量的形式出现一次并仅仅出现一次， 则称m为这n个变量的最小项。 例： 记为m2 记为m5 记为m7 最大项 在n个逻辑变量的逻辑函数中，若M为包含n个因子 的和项（逻辑或），且其中每个逻辑变量都以原 变量或反变量的形式出现一次并仅仅出现一次， 则称M为这n个变量的最大项。 例： 记为M2 记为M5 记为M7 ()()()()f abcabcabcabc abc abc abc 最小项与最大项的比较 以3变量函数为例 00 11 22 33 44 55 66 77 最小项：最大项： 最小项：最大项： 最小项：最大项： 最
13、小项：最大项： 最小项：最大项： 最小项：最大项： 最小项：最大项： 最小项：最大项： mA B CMABC mA B CMABC mA B CMABC mA B CMABC mA B CMABC mA B CMABC mA B CMABC mA B CMABC 最小项和最大项的性质 对于一个具有 n 个变量的逻辑问题，在输入变量 的任意一种取值情况下，总有： 一、必有且仅有一个最小项的逻辑值为1；必有且仅 有一个最大项的逻辑值为0。 二、任意2个不同的最小项之积为0；任意两个不同的 最大项之和为1。 = 0,+ = 1 三、全体最小项之和为1；全体最大项之积为0。 四、下标相同的最大项和最小
14、项互补。 反演反演定理定理 p13p13 =0 21 = 1, =0 21 = 0 = 逻辑函数的两种标准表达式 最小项之和形式，简称为积之和(SOP)形式 最大项之积形式，简称为和之积(POS)形式 (1,2,.,) = 0 21 ，01 (1,2,.,) = 0 21 + ，01 标准表达式的关系 性质1、一个逻辑函数的两种标准逻辑表达式之间，存 在以下关系： 若则 性质2、一个逻辑函数与其反函数的逻辑表达式之间， 存在以下关系： 若则 练习：给出最小项表示，写出最大项表示、写出反函数表示等。 P14, 例1-4 反演定理证明两个反演定理证明两个性质性质 p14p14 = = 其中 = = 将逻辑函数化成标准形式 要求按积之和形式展开函数，可以将非最小项的积项 乘以形如的项，其中A 是那个非最小项的积 项中缺少的输入变量，然后展开，最后合并相同的最 小项
