§1-3 逻辑函数的标准形式
11
逻辑函数表达式的形式与变换
任何一个逻辑函数,任何一个逻辑函数,其表达式的形式都不是唯一的。其表达式的形式都不是唯一的。下面从分析与应用的角度出发,面从分析与应用的角度出发,介绍逻辑函数表达式的基本形式、标准形式及其相互转换。标准形式及其相互转换。
1 逻辑函数表达式的1 逻辑函数表达式的两种逻辑函数表达式的两种基本形式两种基本形式
两种基本形式:两种基本形式:“与-或”表达式和“或-与”表达式。表达式
一、“与-或”表达式
“与-或”表达式:表达式:是指由若干“是指由若干“与项”与项”进行“进行“或”运算构成的表达式。构成的表达式。每个“每个“与项”与项”可以是单个变量的原变量或者反变量,反变量,也可以由多个原变量或者反变量相“也可以由多个原变量或者反变量相“与”组成。组成。
22
“与项”与项”有时又被称为“有时又被称为“积项”积项”,相应地“相应地“与-或”表达式又称为“式又称为“积之和”积之和”表达式。表达式。
二、“或-与”表达式
“或-与”表达式:表达式:是指由若干“是指由若干“或项”或项”进行“进行“与”运算构成的表达式。算构成的表达式。
每个“每个“或项”或项”可以是单个变量的原变量或者反变量,可以是单个变量的原变量或者反变量,也可以由多个原变量或者反变量相“可以由多个原变量或者反变量相“或”组成。组成。
例如,+B 、B +、A ++C 、D 均为“例如,均为“或项”或项”,将这4将这4个“或项”或项”相“与”便可构成一个4便可构成一个4变量函数的“变量函数的“或-与”表达式。达式。即F(A,B, C, D) =(A +B)(B+C )(A+B +C)D
“或项”或项”有时又被称为“有时又被称为“和项”和项”,相应地“相应地“或—与”表达式又称为“表达式又称为“和之积”和之积”表达式。表达式。33
逻辑函数表达式可以被表示成任意的混合形式。逻辑函数表达式可以被表示成任意的混合形式。例如,例如,
F(A,B, C) =(A+C)(A+B ) +B
该逻辑函数是“与—或”式?不是!不是!是“或—与”式?也不是!但不论什么形式都可以变换成两种基本形式。但不论什么形式都可以变换成两种基本形式。2 逻辑函数表达式的标准形式2 逻辑函数表达式的标准形式
逻辑函数的两种基本形式都不是唯一的。逻辑函数的两种基本形式都不是唯一的。例如
F =AB +
+BC =AB +为了在逻辑问题的研究中使逻辑功能能和唯一的逻辑表达式对应,达式对应,引入了逻辑函数表达式的标准形式。引入了逻辑函数表达式的标准形式。
逻辑函数表达式的标准形式是建立在最小项和最大项概念的基础之上的。念的基础之上的。44
一、最小项和最大项
1.最小项
(1)定义:定义:如果一个具有n 个变量的函数的“与项”包含全部n 个变量,个变量,每个变量都以原变量或反变量形式出现一次,且仅出现一次,且仅出现一次,则该“与项”被称为最小项。有时又将最小项称为标准“与项”。
(2)最小项的数目:最小项的数目:n 个变量可以构成2个变量可以构成2个最小项。个最小项。
⋅⋅C 、…、例如,例如,3个变量A 、B 、C 可以构成A ⋅B ⋅C 、
A B C共8个最小项。个最小项。
(3)简写:简写:用m i 表示最小项。表示最小项。
下标i 的取值规则是:的取值规则是:按照变量顺序将最小项中的原变量用1表示,表示,反变量用0反变量用0表示,表示,由此得到一个二进制数,由此得到一个二进制数,与该二进制数对应的十进制数即下标i进制数对应的十进制数即下标i 的值。的值。55n
例如,例如,3变量A变量A 、B 、C 构成的最小项A C 可用A C 可用m 5 表示。因为
A C m
5
101(5)10
ABC 的取值最小项编号
000m 0
001m 1
010m 2
011m 3
100m 4
101m 5
110AB C m 6
111ABC m 7
66
(4)性质:性质:最小项具有如下四条性质。最小项具有如下四条性质。
性质1:任意一个最小项,任意一个最小项,其相应变量有且仅有一种取值使这个最小项的值为1。并且,并且,最小项不同,最小项不同,使其值为1的变量取值不同。量取值不同。
在由n在由n 个变量构成的任意“个变量构成的任意“与项”与项”中,最小项是使其值为1的变量取值组合数最少的一种“的变量取值组合数最少的一种“与项”与项”,这也就是最小项名字的由来。项名字的由来。
7
性质2性质2:相同变量构成的两个不同最小项相“相同变量构成的两个不同最小项相“与”为0。因为任何一种变量取值都不可能使两个不同最小项同时为1,故相“故相“与”为0。
即m i ·m j = 0
性质3性质3:n 个变量的全部最小项相“个变量的全部最小项相“或”为1。通常借用数学中的累加符号“通常借用数学中的累加符号“Σ”,将其记为
2n −1m =1∑
i =0i
性质4性质4:n 个变量构成的最小项有n个变量构成的最小项有n 个相邻最小项。个相邻最小项。
相邻最小项:相邻最小项:是指除一个变量互为相反外,是指除一个变量互为相反外,其余部分均相同的最小项。相同的最小项。例如,例如,三变量最小项A B C三变量最小项A B C和A B C和A BC 相邻。相邻。
88
2.最大项
定义:定义:如果一个具有n如果一个具有n 个变量函数的“个变量函数的“或项”或项”包含全部n 个变量,个变量,每个变量都以原变量或反变量形式出现一次,每个变量都以原变量或反变量形式出现一次,且仅出现一次,仅出现一次,则该“则该“或项”或项”被称为最大项。
有时又将最大项称为标准“标准“或项”或项”。
数目:数目n 个变量可以构成2个变量可以构成2个最大项。个最大项。
例如,例如,3个变量A个变量A 、B 、C 可构成A +B +C 、A +B +、
个最大项。++、…共8个最大项。
简写:简写:用M i 表示最大项。表示最大项。
下标i下标i 的取值规则是:的取值规则是:将最大项中的原变量用0将最大项中的原变量用0表示,表示,反变量用1变量用1表示,表示,由此得到一个二进制数,由此得到一个二进制数,与该二进制数对应的十进制数即下标i十进制数即下标i 的值。的值。例如,例如,3变量A变量A 、B 、C 构成的最大项
9+B +可用M 5表示。表示。因为n
+B +M 5101(5)10
最大项编号
ABC 的取值最大项编号000A +B +C M 0001A +B +C M 1010A +B +C M 2011A +B +C M 3100A +B +C M 4101M 5110A +B +C M 6111A +B +C M 7
10
性质:性质:最大项具有如下四条性质。最大项具有如下四条性质。
性质1:任意一个最大项,任意一个最大项,其相应变量有且仅有一种取值使这个最大项的值为0。并且,并且,最大项不同,最大项不同,使其值为0的变量取值不同。的变量取值不同。
在n 个变量构成的任意“个变量构成的任意“或项”或项”中,最大项是使其值为1的变量取值组合数最多的一种“的变量取值组合数最多的一种“或项”或项”,因而将其称为最大项。大项。
11
性质2性质2:相同变量构成的两个不同最大项相“相同变量构成的两个不同最大项相“或”为1。因为任何一种变量取值都不可能使两个不同最大项同时为0因为任何一种变量取值都不可能使两个不同最大项同时为0,故相“故相“或”为1。
即M i + M j = 1 性质3性质3:n 个变量的全部最大项相“个变量的全部最大项相“与”为0。通常借用数学中的累乘符号“数学中的累乘符号“Π”将其记为
2−1
i =0
n
∏M
i
=0
12
性质4:n 个变量构成的最大项有n个变量构成的最大项有n 个相邻最大项。个相邻最大项。相邻最大项是指除一个变量互为相反外,最大项是指除一个变量互为相反外,其余变量均相同的最大项。12
第二章逻辑代数基础
两变量最小项、两变量最小项、最大项的真值表如下。最大项的真值表如下。
变量最小项、2变量最小项、最大项真值表
变量最小项最大项A B1 1
⋅A AB A +B
m
A ++B
M
1
+M 31 1 1 0
m 10 10 0
m 20 0 10
m
3
M
M 21 1 01
10 0 00 0 0 101 1 11 01 1
真值表反映了最小项、真值表反映了最小项、最大项的有关性质。最大项的有关性质。
1313
3.最小项和最大项的关系
在同一问题中,在同一问题中,下标相同的最小项和最大项互为反函数。或者说,或者说,相同变量构成的最小项m i 和最大项M i 之间存在互补关系。互补关系。即
i =M i 或者m i =i
例如,例如,由3变量A变量A 、B 、C 构成的最小项m构成的最小项m 3和最大项M和最大项M 3之间有
3==A ++=M 33=A +
+==m 3
1414
二、逻辑函数表达式的标准形式
逻辑函数表达式的标准形式有标准“标准“与-或”表达式和标准“标准“或-与”表达式两种类型。两种类型。1.标准“标准“与-或”表达式
由若干最小项相“由若干最小项相“或”构成的逻辑表达式称为标准“与-或”表达式,表达式,也叫做最小项表达式。
例如,例如,如下所示为一个3如下所示为一个3变量函数的标准“变量函数的标准“与-或”表达式
F(A,B, C) =⋅
++A ⋅+ABC
该函数表达式又可简写为 F(A,F(A,B ,C) = m1 + m2 + m4 + m7
∑m(1,2,4,7)=
1515
2.标准“标准“或-与”表达式
由若干最大项相“由若干最大项相“与”构成的逻辑表达式称为标准“或-与”表达式,表达式,也叫做最大项表达式。
该表达式又可简写为
F(A,B, C) =M 1M 5
M 7=∏M(1,5,7)
1616
列出函数F列出函数F 的真值表及其最小项和最大项代号如下表。的真值表及其最小项和最大项代号如下表。
17
因此,因此,同一函数的最小项表达式和最大项表达式之间的关系为:之间的关系为:
F (A ,B ,C )=∑m (1,3,6,7)
=∏M (0,2,4,5)
推广到一般情况,推广到一般情况,同一逻辑函数从一种标准形式变换为另一种标准形式时,符号互换,并在其后一种标准形式时,只需将∑只需将∑m 和∏M 符号互换,的括弧中填入原标准形式缺少的数字即可。的括弧中填入原标准形式缺少的数字即可。如:F (A ,B ,C ,D )=∑m (1,3,6,7,11,12,14)=∏M (0,2,4,5,8,9,10,13,15)
18
2.3.3 逻辑函数表达式的转换2.3.3 逻辑函数表达式的转换
将一个任意逻辑函数表达式转换成标准表达式有两种常用方法,常用方法,一种是代数转换法,另一种是真值表转换法。一、代数转换法
所谓代数转换法,所谓代数转换法,就是利用逻辑代数的公理、就是利用逻辑代数的公理、定理和规则进行逻辑变换,则进行逻辑变换,将函数表达式从一种形式变换为另一种形式。
1. 求标准1. 求标准“求标准“与-或”式
一般步骤如下:一般步骤如下:
第一步:第一步:将函数表达式变换成一般“将函数表达式变换成一般“与-或”表达
式。
第二步:第二步:反复使用X =X(Y+
) 将表达式中所有非最
1919小项的“小项的“与项”与项”扩展成最小项。扩展成最小项。
例如,例如,将逻辑函数表达式F(A,B, C) =(A+B ) ⋅转换成标准“与-或”表达式。表达式。
解: 第一步:第一步:将函数表达式变换成“将函数表达式变换成“与-或”表达式。表达式。即
F(A,B, C) =(A+B ) ⋅=A +B +AB
=(+
B)(+C) +AB
=⋅++BC +AB
第二步:第二步:把“与-或”式中非最小项的“与项”扩展成最小项。扩展成最小项。具体地说,具体地说,若某“与项”缺少函数变量Y ,则用(+Y ) 和这一项相与,相与,并把它拆开成两项。并把它拆开成两项。即
F(A,B, C) =⋅(+C) ++B) +(+A)BC +AB +C)
=A ⋅B ⋅C +A ⋅B ⋅C +A ⋅B ⋅C +A BC +A BC +ABC +AB C +ABC =⋅⋅+⋅⋅C +++ABC 2020
所得标准“ 所得标准“与-或”式的简写形式为 F(A,B, C) = m0 + m1 + m3 + m6 + m7 = ∑ m(0,1,3,6,7) 当给出函数表达式已经是“ 表达式时, 当给出函数表达式已经是“与-或”表达式时,可直接 进行第二步。 进行第二步。 求一个函数的标准“ 2. 求一个函数的标准“或-与”式 一般步骤: 一般步骤: 第一步:将函数表达式转换成一般“ 第一步:将函数表达式转换成一般“或-与”表达式。 表达式。 第二步: 第二步:反复利用定理 A = (A + B)(A + B) 把表达式中 所有非最大项的“或项”扩展成最大项。 所有非最大项的“或项”扩展成最大项。
21 21
例如, 例如,将逻辑函数表达式 F(A,B, C) = (AB + AC) + BC 变 表达式。 换成标准“或 与 表达式 换成标准 或-与”表达式。 表达式。 解:第一步:将函数表达式变换成“或-与”表达式。即 第一步:将函数表达式变换成 或 与 表达式
F(A, B, C) = (AB + AC) + BC
= AB ⋅ AC + BC
= ( A + B)(A + C) + BC
= [(A+ B)(A+ C) + B][(A+ B)(A+ C) + C]
= ( A + B + B)(A + C + B)( A + B + C)(A + C + C)
= ( A + B)(A + B + C)( A + B + C)
=1
22 22
第二步:将所得“ 第二步:将所得“或-与”表达中的非最大项扩展成最 大项。 大项。即
F(A, B, C) = (A + B)(A + B + C)(A + B + C)
= (A + B + C)(A + B + C)(A + B + C)(A + B + C) = (A + B + C)(A + B + C)(A + B + C)
该标准“或-与”表达式的简写形式为 该标准“ 表达式的简写形式为
F(A, B, C) = M3 ⋅ M 6 ⋅ M 7 = ∏ M(3,6,7)
当给出函数已经是“ 表达式时, 当给出函数已经是“或-与”表达式时,可直接进行第 二步。 二步。
23 23
二、真值表转换法 求标准“ 1. 求标准“与-或”式 逻辑函数的最小项表达式与真值表具有一一对应的关 系。 假定函数F的真值表中有k组变量取值使F的值为1 假定函数F的真值表中有k组变量取值使F的值为1,其他 变量取值下F的值为0 那么,函数F的最小项表达式由这k 变量取值下F的值为0,那么,函数F的最小项表达式由这k组 变量取值对应的k个最小项相或组成。 变量取值对应的k个最小项相或组成。 因此,可以通过函数的真值表写出最小项表达式。 因此,可以通过函数的真值表写出最小项表达式。 具体:真值表上使函数值为1 具体:真值表上使函数值为1的变量取值组合对应的最 小项相“ 即可构成一个函数的标准“ 小项相“或”,即可构成一个函数的标准“与-或”式 。
24 24
例如, 例如,将函数表达式 F(A, B, C) = A B + BC 变换成标准 表达式。 “与-或”表达式。 首先,列出F的真值表如下表所示,然后, 解:首先,列出F的真值表如下表所示,然后,根据真 值表可直接写出F 值表可直接写出F的最小项表达式
F(A, B, C) = ∑ m(2,4,5,6)
函数F(A,B,C) = AB + BC的真值表 A B C F F ( A, B, C ) = 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0
∑ m(2,4,5,6)
25 25
求一个函数的标准“ 2. 求一个函数的标准“或-与”式 逻辑函数的最大项表达式与真值表之间同样具有一一 对应的关系。 对应的关系。 假定在函数F的真值表中有p组变量取值使F的值为0 假定在函数F的真值表中有p组变量取值使F的值为0, 其他变量取值下F的值为1 那么,函数F 其他变量取值下F的值为1,那么,函数F的最大项表达式由 组变量取值对应的p个最大项“相与”组成。 这p组变量取值对应的p个最大项“相与”组成。 具体:真值表上使函数值为0 具体:真值表上使函数值为0的变量取值组合对应的最 大项相“ 即可构成一个函数的标准“ 大项相“与”即可构成一个函数的标准“或-与”式 。
26 26
例如, 例如,将函数表达式 F ( A, B, C ) = AC + A B ⋅ C表示成最 大项表达式的形式。 大项表达式的形式。 首先,列出F的真值表如下表所示。然后, 解:首先,列出F的真值表如下表所示。然后,根据真 值表直接写出F的最大项表达式 值表直接写出F
F ( A, B , C ) =
A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 F 0 1 0 1 1 0 0 0
∏ M ( 0 , 2 ,5 , 6 , 7 )
F( A, B, C) = ∏M (0,2,5,6,7)
函数 F(A,B,C) = AC + AB ⋅ C 的真值表
27 27
由于函数的真值表与函数的两种标准表达式之间存在一 一对应的关系,而任何一个逻辑函数的真值表是唯一的, 一对应的关系,而任何一个逻辑函数的真值表是唯一的,可 见,任何一个逻辑函数的两种标准形式也是唯一的。 任何一个逻辑函数的两种标准形式也是唯一的。 逻辑函数表达式的唯一性给我们分析和研究逻辑问题带 来了很大的方便。 来了很大的方便。
28 28
第一章作业( 第一章作业(3): 1. P.66 11(1,4)。 2. P.66 12(1,3)。
29
questions ?
30