逻辑代数基础课件

逻辑代数基础用数学方法表示命题陈述的逻辑结构，将形式逻辑归结为代数演算，称为“布尔代数”。将布尔代数用于集成电路逻辑门，称为逻辑代数。

2．1逻辑代数的基本概念

逻辑代数由逻辑变量集K，常量0和1，以及“或”、“与”、“非”三种基本运算所构成。该系统满足以下公理，对应不同的律。交换律：，结合律：，分配律：

0

–

1

律：互补律：2．1．1逻辑变量和基本逻辑运算逻辑变量取值0或1，用开关的通与断、电压的高与低、晶体管的导通与截止来表征。可通过逻辑变量和“或”、“与”、“非”组合的逻辑算式描述数字系统。1．“或”运算决定某一事件发生的条件中有一个以上条件成立，事件便发生。这种因果关系称为“或”。记做：F=A+B

或F=A∨B。运算法则为：0+0=0，0+1=1，1+0=1，1+1=1，见“1”为“1”。实现该运算的门电路称为“或”门。2．“与”运算决定某一事件发生的条件同时成立，事件便发生。这种因果关系称为“与”。记做：F=A•B

或F=A∧B。运算法则为：0•0=0，0•1=0，1•0=0，1•1=1，见“0”为“0”。实现该运算的门电路称为“与”门。2．1．1逻辑变量和基本逻辑运算3．“非”运算某一事件的发生取决于条件的否定，这种因果关系称为“非”。记做F=，运算法则为：A为0则F为1，A为1则F为0。

+UAB+U+UFAFBF“或”示意图“与”示意图“非”示意图

2．1．2逻辑函数的表示法

1．逻辑表达式由变量通过“或”、“与”、“非”三种运算符进行组合，三种运算符的优先级排序为“非”、“与”、“或”。2．1．2逻辑函数的表示法“与”运算符可省略，如

，“非”运算、先“与”后“或”运算可省略括弧，如：，。2．真值表用表格的形式描述逻辑函数的方法称为真值表。每个逻辑变量有两种取值，n个变量有2n

种取值组合。真值表左边一栏为变量，右边一栏为逻辑函数值。例：对应的真值表为：3．卡诺图将n个变量的2n

种取值组合按某种顺序填ABCF00000011010001111001101111001110真值表入小方格构成的平面图，构成一种描述逻辑函数的图形。称为卡诺图。2．2

逻辑函数的基本定理和规则2．2．1基本定理定理1：0+0=0、0+1=1、1+0=1、1+1=10•0=0、0•1=0、1•0=0、1•1=1定理2：A+A=A、A•A=A定理3：A+A•B=A、A•（A+B）=A定理4：定理5：定理6：，定理7：定理8：2．2．2重要规则1．代入规则将逻辑式中所有出现同一变量的地方用某一逻辑函数代替，等式仍然成立。例：A(B+C)=AB+AC，将所有出现C的地方都用(C+D)代替，则等式仍然成立。A(B+(C+D))=AB+A(C+D)。2．反演规则将函数式中的“

•

”变成“+”，“+”变成“

•”，“0”变成“1”，“1”变成“0”，原变量变成反变量，反变量变成原变量，并保持运算次序不变，得到的新函数为原函数F的反函数，这一规则称为反演规则。例：，则3．对偶规则将函数式中的“

•

”变成“+”，“+”变成“•

”，“0”变成“1”，“1”变成“0”，并保持运算次序不变，得到的新的逻辑表达式为原函数式的对偶式，记做F

’。F与F

’互为对偶式。2．2．2重要规则例：根据对偶规则，当两个逻辑表达式相等时，其对偶式也相等。如：，则2．2．3复合逻辑1．与非逻辑由与、非两种逻辑复合而成，实现与非逻辑的门电路称为与非门。逻辑表达式为：。仅当输入全为1时

F

输出为0，输入有一个为0时

F

输出为1。用与非门可以实现与、或、非三种操作。与或非2．2．3复合逻辑2．或非逻辑由或、非两种逻辑复合而成，实现或非逻辑的门电路称为或非门。逻辑表达式为：。输入全为0时F

输出为1，输入有一个为1时F输出为0。用或非门也可以实现与、或、非三种操作。与或非3．与或非逻辑由与、或、非三种逻辑复合而成，实现与或非逻辑的门电路称为与或非门。逻辑表达式为：。仅当每一个“与项”均为0时F输出为1，否则F

输出为0。可以将任一个逻辑表达式转换成与或非表达式。例：2．2．3复合逻辑4．异或逻辑一种双变量逻辑关系。函数表达式为：。输入相同时F输出为0，输入不同时F输出为1。多个变量做异或时，若变量中1的个数为奇数，则异或结果为1，若变量中1的个数为偶数，则异或结果为0。因此常用于奇偶校验。

5．同或逻辑一种双变量逻辑关系。函数表达式为：F=A⊙B

。输入相同时F

输出为1，输入不同时F

输出为0。同或和异或的关系即互为相反又互为对偶。

A⊙BA⊙B

2．3逻辑函数表达式的形式与变换2．3．1逻辑函数表达式的基本形式1．“与–或”表达式由若干“与项”进行“或”运算构成的表达式。每个“与项”可以是单个变量的原变量或反变量，也可以是多个原变量或反变量相“与”组成。如：“与项”又被称为“积项”，“与–或”表达式称为“积之和”表达式。2．“或–与”表达式由若干“或项”进行“与”运算构成的表达式。每个“或项”可以是单个变量的原变量或反变量，也可以是多个原变量或反变量相“或”组成。如：“或项”又被称为“和项”，“或–与”表达式称为“和之积”表达式。2．3．2逻辑函数表达式的标准形式1．最小项和最大项⑴最小项的定义和性质定义：一个n个变量的函数的“与项”包含全部n个变量，每个变量都以原变量或反变量的形式出现一次，则该“与项”被称为最小项。n

个变量可构成

2n

个最小项，如三个变量可构成、、…。用mi表示最小项，将最小项中原变量用1表示，反变量用0表示，得到的二进制数对应的十进制数值即下标i的值。例如三变量函数中，m3

表示，m6

表示。性质

1：任意一个最小项，其变量仅有一种取值使这个最小项为1。性质2：相同变量构成的两个最小项相“与”为0。性质3：n个变量的全部最小项相“或”为1。即=1性质4：n个变量构成的最小项有n个相邻最小项。相邻最小项是指除一个变量互为相反外，其余部分相同。如与。2．3．2逻辑函数表达式的标准形式⑵最大项的定义和性质一个n个变量的函数的“或项”包含全部n个变量，每个变量都以原变量或反变量的形式出现一次，则该“或项”被称为最大项。n个变量可构成2n

个最大项，三变量可构成‘…等。用Mi表示最大项，将最大项中原变量用0表示，反变量用1表示，得到的二进制数对应的十进制数值即下标i的值。例如三变量函数中，M4

表示，M6

表示。性质

1：任意一个最大项，其变量仅有一种取值使这个最大项为0。性质2：相同变量构成的两个最大项相“或”为1。性质3：n个变量的全部最大项相“与”为0。即=0性质4：n个变量构成的最大项有n个相邻最大项。相邻最大项是指除一个变量互为相反外，其余部分相同。如。2．3．2逻辑函数表达式的标准形式2．逻辑函数表达式的标准形式⑴标准“与–或”表达式由若干最小项相“或”构成的逻辑表达式称为标准“与–或”表达式，或最小项表达式。例：

=m1+m2+m4+m7=

⑵标准“或–与”表达式由若干最大项相“与”构成的逻辑表达式称为标准“或–与”表达式，或最大项表达式。例：

=M0+M5+M7=2．3．3通用函数表达式的转换目的：将任意逻辑函数表达式转换为标准“与–或”表达式或标准“或–与”表达式。1．代数转换法转换成“与–或”表达式的步骤分为两步：第一步：将函数表达式转换成一般“与–或”表达式。第二步：使用X=X•（Y+）将表达式中所有非最小项的“与项”扩展成最小项。例：

F(A，B，C)=m0+m1+m3+m6+m7=2．3．3通用函数表达式的转换转换成“或–与”表达式的步骤分为两步：第一步：将函数表达式转换成一般“或–与”表达式。第二步：使用A=(A+B)(A+)将表达式中所有非最大项的“或项”扩展成最大项。例：

假定在函数F的真值表中有k组变量取值使F值为0，则函数F的最大项表达式由这k组变量对应的k个最大项组成。例：将变换成最大项表达式解：列出真值表，有五项F

为0，根据真值表可写出最大项表达式。2．3．3通用函数表达式的转换真值表2．真值表转换法假定在函数F的真值表中有k组变量取值使F值为1，则函数F的最小项表达式由这k组变量对应的k个最小项组成。例：将变换成最小项表达式解：列出真值表，有四项F为1，根据真值表可写出最小项表达式。ABCF000000100101011010011011110111102．3．3通用函数表达式的转换2．4逻辑函数化简化简目的：降低系统成本、减少复杂度、提高可靠性。2．4．1代数化简法1．“与-

或”表达式化简最简“与-

或”表达式应满足两个条件：ABCF00000011010001111001101011001110表达式中的“与”项个数最少，每个“与”项中变量个数最少。⑴并项法利用定理7中，将两个“与”项合并成一个“与”项。合并后可消去一个变量。如：2．4．1代数化简法⑵吸收法利用定理3中A+AB=A，消去多余的项。如：⑶

消去法利用定理4中，消去多余变量。如：⑷配项法利用公理4和公理5中的A•1=A及A+=1，选择某些“与”项，并配上所缺的变量，再利用并项、吸收和消去等方法进行化简。例1：2．4．1代数化简法2．“或–与”表达式的化简最简“或

–

与”表达式应满足两个条件：表达式中的“或”项个数最少，每个“或”项中变量个数最少。例：

2．4．2卡诺图化简法1．卡诺图的构成卡诺图是一种真值表图形化的平面方格图，n

变量卡诺图有2n个方格，方格坐标值给出变量的2n

种取值，每个方格与最小项对应。方格上方和左方的坐标值表示该方格所表示最小项的下标，即该项对应的二进制值。如4变量卡诺图中m5

的列坐标为01，行坐标也为01，则坐标0101对应的数值即为最小项的下标5。ABA012．4．2卡诺图化简法卡诺图的排列方案应保证能清楚地反映最小项的相邻关系。图中每列坐标仅有一位不同，每行坐标也仅有一位不同。在n个变量的卡诺图中，每个变量有n个相邻最小项。m0m2m1m3AB

0B1m0m2m6m4m1m3m7m5ABC0C1m0m4m12m8m1m5m13m9m3m7m15m11m2m6m14m10ABCD00011110

ABC00

01

11

1000

01

11

10D二变量卡诺图三变量卡诺图四变量卡诺图2．4．2卡诺图化简法例：4变量卡诺图中m5有4个相邻最小项m1、m4、m7、m13，这4个最小项对应的小方格与m5小方格在几何位置上相邻，称为几何相邻。m0的4个相邻最小项只有m1、m4

几何相邻，m8、m2在相对位置上相邻，称为相对相邻。5变量卡诺图中m3除了和m1、m2、m7几何相邻、和m11相对相邻之外，还与m19相邻。将左边矩形与右边矩形重叠，上下重叠的最小项也相邻，称为重叠相邻。BCm0m4m12m8m1m5m13m9m3m7m15m11m2m6m14m10ABCDE00011110D000

001

011

010

BCm16m20m28m24m17m21m29m25m19m23m31m27m18m22m30m26ABCD100101111

110EA五变量卡诺图2．4．2卡诺图化简法2．逻辑函数在卡诺图上的表示当逻辑函数为标准“与–或”表达式时，在卡诺图上与最小项对应的方格中填入1，其余方格填入0，即可得该函数的卡诺图。例：F（A，B，C，D）=在4变量卡诺图上找出和“与项”AB、CD、对应的方格填入1。由AB“与项”可知第三列均为1，由CD“与项”可知第三行均为1，由‘“与项”可知第一列第三、第四方格（ABC=001）均为1。由填好的卡诺图可得:3．卡诺图上最小项的合并规律0010001011111010ABCD0001111000

01

11

10

卡诺图上两个或若干个相邻项可以合并成一个或多个“与”项。几何相邻、相对相邻和重叠相邻均可合并。由一个简单与项代替的若干最小项的“圈”称为“卡诺圈”。AB01

0

12．4．2卡诺图化简法例1：两个变量卡诺图中2个相邻最小项合并。

，该函数式对应的卡诺图为图(a)，由图可见，m1、m3

为相邻最小项，可合并，。，该函数式对应的卡诺图为图(b)，m0、m1

为相邻最小项，可合并，。，该函数式对应的卡诺图为图(c)，m0、m1

为相邻最小项，m0、m2

也为相邻最小项，均可合并，

(a)(b)(c)两个相邻最小项合并后变成一个最小项，可减少一个变量。0011AB01

0

11010AB01

0

111102．4．2卡诺图化简法例2：三个变量卡诺图中4个相邻最小项合并。例3：四个变量卡诺图中4个相邻最小项合并。⑴10011001ABC0100

01

11

1001100110ABC0100

01

11

10函数式对应的卡诺图中，最小项m0、m2、m8、m10相邻，经合并后为，最小项m5、m7、m13、m15相邻，经合并后为BD。函数式经化简后得：ABCD00011110100101100110100100

01

11

102．4．2卡诺图化简法ABCD00011110011010011001011000

01

11

10⑵函数式对应的卡诺图中，最小项m1、m3、m9、m11相邻，经合并后为，最小项m4、m12、m6、m14相邻，经合并后为。则函数式经化简后得：⑶

函数式对应的卡诺图中，最小项m4、m5、m7、m6、m12、m13、m15、m14相邻，经合并后为B。则函数式经化简后得：ABCD00011110011001100110011000

01

11

10

蕴涵项：“与

-

或”表达式中的每一个“与”项称为函数的蕴涵项。质蕴涵项：若函数的一个蕴涵项不是该函数中其他蕴涵项的子集，则此蕴涵项称为质蕴涵项，简称质项。必要质蕴涵项：若一个质蕴涵项含不被其他质蕴涵项所含的最小项，称为必要质蕴涵项，简称必要质项。在图中，若某个卡诺圈包含不被其他卡诺圈包含的1个方格，则卡诺圈所对应的“与”项为必要蕴涵项。ABCD00011110100110011001100100

01

11

102．4．2卡诺图化简法⑷函数式对应的卡诺图中，最小项m0、m1、m3、m2、m8、m9、m11、m10相邻，经合并后为得。则函数式经化简后得：4．卡诺图化简逻辑函数的步骤2．4．2卡诺图化简法⑴作出函数卡诺图，函数对应的最小项填1。⑵圈出函数全部质蕴涵项⑶从全部蕴涵项中找出必要蕴涵项⑷若所有必要蕴涵项不能覆盖所有为1的方格，则从剩余质蕴涵项中找出最简的所需蕴涵项，和必要蕴涵项构成函数最小覆盖。例4：简化逻辑函数按以上步骤用图形简化。图上带有“*”号的最小项只被一个卡诺圈包围，称为必要最小项。该题所有质蕴涵项均为必要质蕴涵项。ABCD00011110100001101111010100

01

11

10ABCD00011110100001101111010100

01

11

10ABCD000111101*00001*1*01*11101*01*00

01

11

102．4．2卡诺图化简法图中带“*”号的最小项为必要最小项。5个必要蕴涵项已将函数的全部最小项覆盖，故可得函数F的最简表达式：例5：简化逻辑函数选取必要质项后，尚有

m10未被覆盖。为覆盖m10，可选取质蕴涵项，这两个质蕴涵项都包含三个变量，可任选一个。若选第一个，则

F

的最简表达式为：。ABCD00011110001100001100110100

01

11

10ABCD00011110001100001100110100

01

11

10ABCD00011110001*100001*1*0011*0100

01

11

102．4．3列表化简法用列表的方式找出函数F的全部质蕴涵项、必要质蕴涵项以及最简质蕴涵项，求得最简表达式。具体步骤为：⑴用二进制代码表示每一个最小项⑵通过若干次相邻最小项的合并，每次消去一个变量，直至找出函数的全部质蕴涵项。⑶找出函数的必要质蕴涵项⑷找出函数的最小覆盖例：化简逻辑函数项号ABCDF项号ABCDF00000110101015010111110111701111141110181000115111119100112．4．3列表化简法相邻最小项的二进制代码中1的个数只能相差为1，将表中的最小项按二进制代码中1的个数进行分组，共分为5组。对相邻两组代码逐个进行比较，找出只有一个变量不同的最小项合并，消去一个变量，组成n-1个变量的“与”项列于表的第二栏中。（Ⅰ

）最小项（Ⅱ

）3变量“与”项（Ⅲ

）2变量“与”项组号miABCDPi组号

ABCDPi组号

ABCDPi000000√

00,8-000P108,9,10,1110-

-

P4181000√

18,