二人同行-呆若木鸡翻译

第六章序关系和结构Order Relations and
Structures
§6.1 偏序集Partial Ordered Sets
关系 Relation
定义
A Relation R From A to B is a subset of AB
A relation on A is a subset of AA
矩阵表示，图表示。
性质
自反 reflextive
R
对称 symmetric, asymmetric, antisymmetric
R=R, RR, RR=
传递 transive
RR or R=R
2

-1-1-1

传递闭包 Wallshall算法O(n)
等价关系 =

偏序关系Partial Order 
Definition
1. 自反 Reflexive
aA, (a,a)R
2．反对称antisymmetric
a,bA (a,b)∈R∧(b,a)∈R  a=b
3．传递Transitive
a,b,cA (a,b)∈R ∧ (b,c)∈R  (a,c)∈R.
Examples
, , , 12
,|>,
3

例4． R，S都是A上等价关系,
RSxRy→xSy, R：A上全体
等价关系， (R ，)构成偏序。
对偶偏序集：
如 果R是A上偏序，则R也是A上偏序。
－1
（A，R）称为（A，R）的对偶偏序集。 （A，
≥）是（A，≤）的对偶偏序
。
全序关系，线性序关系linear order，链
chain
偏序1.2.3.＋4
4． a,bA,(a,b)R∨(b,a)∈R.
字典序
偏序乘积
定理1如果(A,≤)，(B,≤)是偏序，则(A×
B，≤)是乘积偏序product partial order，
其中≤定义为： (a,b)≤(a’,b’)a
≤a’b≤b’
偏序与严格序
设（A，≤）是偏序， 令a－1

≤b，a≠b， 称（A，<）严格序，
大于，小于都是严格线性序。
反之若（A，<）是严格序， 令a≤
ba字典序
二元
(A×B，≤)中，令(a,b)<(a’,b’)aa=a’,bn元(A，≤）是偏序，
n
A＝A×A×……×A
(a
1
,a
2
,……, a
n
)<(b
1
,b
2
,……,b
n
)
 a
1
1
∨a
1
=b
1
∧ a
2
2
∨……
∨a
1
=b
1
∧……∧a
n
n

不等长
(a
1
,a
2
,……,a
n
)<(b
1
,b
2
,……,b
m
)

If n=m
If n( a
1
,a
2
,……,a
n
)(b
1
,b
2
,……,b
n
)

If n>m
(a
1
,a
2
,……,a
m
)<(b
1
,b
2
,……,b
m
)

定理2. 偏序集的有向图中没有长度大于1
的圈。
12
哈斯图Hasse Diagram
2
3
4
parital order，digraph and the matrix of D
6
？
1
从关系图到哈斯图
Deleting all the self-circles
Deleting all the edges which can be induced
by transive property
Replacing vertices by dots
Make sure the greater elements are located at
higher place.

例11．D
12
的哈斯图？
例12．S＝{a,b,c}, A=P(S).
问题（6.1.1）
给定偏序关系R，哈斯图是否唯一？
计算哈斯图的算法？
0
传递闭包逆运算？
拓扑排序
（A，≤）是偏序集，构造一个线性序（A，
≤’）使 a算法原理：
1. 选择一个没有前驱的顶点输出，
2. 去掉这个顶点以及从这点出发的所有
边。
重复1.2.直到所有顶点都输出完毕
时间复杂性？
O(n
3
)
同构Isomorphic
定义

f：（A, ≤）→（A’, ≤’）
f是A→A’的一一对应，
a≤b iff f(a)≤’f(b)。
例15．（Z，≤）→（2Z，≤）
f：（Z，≤）→（2Z，≤）是同构。
f(a)=2a
a≤b iff 2a≤2b
定理3. 设f：(A,≤) (A’,≤’)。则A,
A’对应的性质都相同。
序同构与哈斯图的关系
1． 如果f是同构，则A的哈斯图中所有标
记a换成对应的标记f(a), 得到A’的哈斯
图。
2． 如果A的哈斯图中所有标记a换成对应
的标记f(a), 得到A’的哈斯图，则f是同
构。

例17．A＝{1,2,3,6},
A’=P({a,b})={ ,{a},{b},{a,b}}
Homework P200－201
5，6，14，16，24，28，35，36
§6.2偏序集的极大极小元 Extremal
elements of Partial Ordered Sets
极大元maximal element：
a∈A，b∈A，a极小元minimal element：
a∈A，b∈A，b定理1. 有限偏序集A中，至少有一个极大
元，至少有一个极小元。
最大元greatest element：
a∈A，任意b∈A，ba.
最小元least element：
a∈A，任意b∈A，ab.

定理2. 类似定理1
偏序集A中，至多有一个最大元，至多有一
个最小元。
偏序集A中，如果有最大元，称之为单位元
1，如果有最小元，称之为零元0。
上界 upper bound
偏序集A中，BA，a∈A，b∈B，ba.
下界lower bound
偏序集A中，BA，a∈A，b∈B，ab.
上确界LUB least upper bound
偏序集A中，BA，a是B的最小上界，即a
是B的上界，对B的任意上界a’，aa’.
下确界GLB greatest lower bound
偏序集A中，BA，a是B的最大下界，即a
是B的下界，对B的任意下界a’，a>a’.

定理3. 偏序集A中，BA，B至多一个上确
界，至多一个下确界。
定理4. 设f：（A，≤）→（A’,≤’）
是偏序同构，
（a） a是A的极大（极小）元，则f(a)
是A’的极大（极小）元。
（b） a是A的最大（最小）元，则f(a)
是A’的最大（最小）元。
（c） BA，a是B的上（下）界，则f(a)
是f(B)的上（下）界
（d） BA，a是B的上确（下）界，则f(a)
是f(B)的上（下）确界
Homework P206－207
16，26，33

§6.3 格 Lattices
定义 格是一个偏序集（L，≤），任意a，b
∈L，a，b有上下确界。
令a∨b＝LUB(a,b),

a∧b＝GLB(a,b).
格 (L,≤，∨，∧)
例1．（P(S), ）是格，
A∨B＝A∪B，A∧B＝A∩B。
记做（P(S), ,∪,∩）
例2．（Z，| ）是格，
a∨b＝LCM(a,b),
a∧b＝GCD(a,b).
例3．令D
n
是n的所有正因子的集合，（D
n
，
|）是格。
D
20
＝{1,2,4,5,10,20},
D
30
={1,2,3,5,6,10,15,20}
＋

线性序是格
例4． Hasse图是否格的判断。
d
c
d
b
b
c

a

a


e
d
d
b
c
b
e
a

a

c

g
f
d
e
b
c
d
a
b
c

e

a

例5． R：A上全体等价关系，偏序（R ，）
是格。
R∧S＝R∩S
∞
R∨S＝(R∪S)
设（L，≤）是格，则对偶（L，≥）也是格。
问题6.3.1 1)格的判定算法？2)格的运算
表生成？
定理1.乘积格
设（L
1
,≤,∨,∧），
（L
2
,≤,∨,∧）都是格。
则（L
1
×L
2
，≤,∨,∧）也是格。
(a,b)∨(c,d)=(a∨c, b∨d)
(a,b)∧(c,d)=(a∧c, b∧d)

子格sublattice
设（L，≤）是格，SL，S对∨，∧封闭，
即a，b∈Sa∨b，a∧b∈S。
记做(S，≤,∨,∧)  (L，≤,∨,∧)或 格
S  L。
例如(Dn，LCM, GCD)
+
, |, LCM,GCD) |, (Z

例9
g
ef
d
b
a
g
ef
b
d
b
a
c
c
c
g
ef< br>d
b
a
c

格的同构Isomorphic Lattices
f：(L
1
,≤,∨,∧)→(L
2
,≤,∨,∧)，
f是L1到L2的序同构，则f保持
∨，∧运算，
f(a∨b)=f(a)∨f(b)
f(a∧b)=f(a)∧f(b)
格同构也记做L
1
L
2
。

D
6
P({a,b}).
问题 （6.3.2） 1） D
n
同构与 (P(S), ≤)
的充分必要条件？ 2）D
n
同构与D
m
的充分必
要条件是什么？
格的性质Properties of Lattices
定理2
设L是格，
则a≤b  a∨b＝b  a∧b＝a.
定理3.
设L是格，则L具有如下性质：
幂等律

a∨a＝a， a∧a＝a
交换律
a∨b＝b∨a，a∧b＝b∧a
结合律
a∨(b∨c)=(a∨b)∨c,
a∧ (b∧c)=(a∧b)∧c
吸收律
a∨(a∧b)=a, a∧(a∨b)=a
定理3’
设集合L上有运算 ∨，∧，（L,∨,∧）满足
幂等律，交换律，结合律，吸收律，则L是
格。
证明.
1）a∨b＝b iff a∧b＝a。
 a∧b＝a∧(a∨b)=a.
 a∨b＝a∨(a∧b)=a.
2）定义L上≤关系：
a≤b iff a∨b＝b iff a∧b＝a。

3）≤是L上偏序：
1）自反性：
由a∨a＝a，得a≤a
2）反对称性：
设a≤b，b≤a，
a＝a∧b＝b∧a＝b，
3）传递性
设a≤b，b≤c，
a∨c＝a∨(b∨c)＝(a∨b)∨c＝b∨c＝c
a≤c
4）a∨b，a∧b分别是上下确界
a∨b上界：
a∧(a∨b)=a, a≤a∨b
b∧(a∨b)=b, b≤a∨b
a∨b上确界
设a≤c，b≤c，
(a∨b)∨c=a∨(b∨c)=a∨c＝c
a∨b≤c
a∨b是a，b的最小上界。

定理4.
设L是格，
1）如果a≤b，则
（a）a∨c≤b∨c
（b）a∧c≤b∧c
2）a≤c，b≤c iff a∨b≤c
3）c≤a，c≤b iff c≤a∧b
4）如果a≤b，c≤d则
a∨c≤b∨d 且a∧c≤b∧d
有界格
有界格Bounded lattice：有最大元
小元0的格叫有界格。
L是有界格，则对任意a∈L，
有0，1律成立。
1）0≤a≤1
2）a∨0＝a，a∧0＝0
3）a∨1＝1，a∧1＝a
，最1

定理5. L是有限格，则L有界。
分配格Distributive Lattice：
1. a∧(b∨c)＝(a∧b)∨(a∧c)
2. a∨(b∧c)＝(a∨b)∧(a∨c)
12
(a∨b)∧(a∨c)
=((a∨b)∧a)∨((a∨b)∧c)
=a∨((a∨b)∧c)
=a∨((a∧c)∨(b∧c))
=a∨(b∧c)

例16．格(P(S),∪,∩)是分配格。
例18．下列格
1
a
b
d
d
1
0
e
a
c
b
0
c
b
c
b
ec
a

a

定理6格L不是分配格当且仅当L含有例18
中的子格。
可补格Complement Lattice.
有界格L是可补格，如果任意a∈L，有a’
∈L，使
a∨a’=1，a∧a’=0.
称a’为a的补元。

例19．格(P(S),∪,∩)是可补格。
例21．D
20
，D
30
都是可补格。
定理7. 设L是有界格，a∈L，如果a有补
元，则其补元唯一。

0
证明.
设a’,a”都是a的补元。
则a’=a’∨0＝a’∨(a∧a”)
＝(a’∨a)∧(a’∨a”)
= a’∨a”
a”=a”∨0＝a”∨(a∧a’)
＝(a”∨a)∧(a”∨a’)
= a’∨a”
因此 a’=a”.
Homework P216－217
12，14，18，21，23，24，27，31，
§6.4 有限布尔代数
Finite Boolean Algeblas
33

定理1 设S
1
＝{x
1
,x
2
,……,x
n
},S
2
＝
{y
1
,y
2
,……,y
n
}，则格（P(S
1
), ）
（P(S
2
),）.
证明. 令f：S
1
→S
2
，
f(x
i
)=y
i
, i=1,2,……,n.
则 f：P(S
1
)→P(S
2
)是格同构。
1. 任意A∈P(S
1
), AS
1
,
f(A)  S
2
,是一一对应。
2. 任意A，B∈P(S
1
), AB,
f(A)  f(B). f保序。


定义：|S|=n, 格（P(S
1
), ）记做Bn

B
n
是布尔代数。
定理2. n=p
1
p
2……p
k
时，D
n
是布尔代数。

证明. 令S＝{p
1
,p
2
,……,p
k
}
D
n
中的元素m=p
k1
*,...,p
km

P(S)中的元素 T={p
k1
,…,p
km
}
f: P(S)→Dn
f(T)=p
k1
*…*p
km

只需证明f是同构对应。
1） f是一一映射
2） T
1
T
2
→f(T
1
)|f(T
2
)
显然成立
例D
1001
是布尔代数。

定理3. 设B是布尔代数，x，y∈B，
1．(x’)’=x,
2. (x∧y)’=x’∨y’. De. Morgan律
3. (x∨y)’=x’∧y’
布尔代数的性质：
交换律commutativeproperties
x∧yy∧x
x∨yy∨x
结合律associative properties
(x∧y) ∧rx∧(y∧r).
(x∨y)∨rx∨(y∨r).
分配律distributive properties
x∧ (y∨r) x∧y∨x∧r.
x∨(y∧r)  (x∨y) ∧(x∨r).
幂等律idempotent properties
x∨xx.
x∧xx.
双重否定property of negation
9． x’’x
De Morgan’s law
10. (x∨y)’ x’∧y’

11. (x∧y)’ x’∨y’
吸收律
12 x∨(x∧y)＝x
13 x∧(x∨y)＝x
01律
14．x∨0＝x，x∧0＝0
15．x∨1＝1，x∧1＝x
16. x∨x’=1, x∧x’=0
17. 1’=0, 0’=1

例7．P230图6.62不是布尔代数。

例8．p
2
|n, p是素数，则Dn不是布尔代数。

证明.
设D
n
是布尔代数。
22
p|n, n=pk. p∈D
n
，p’∈D
n
。
p∧p’＝0，GCD(p,p’)=1,
p∨p’＝1，LCM(p,p’)=n.

GCD(p,p’)＝1～p|p’.
2
LCM(p,p’)=n=pkp|p’.
矛盾。

例9．D
12
不是布尔代数。

定理4. B
n
B×B×……×B
BnB×B×……×B， n个
B的卡氏积。


证明.
令f：B
n
→B×B×……×B

S＝{ x
1
x
2
……x
n
}, Bn＝P(S).
B
n
中任意元素A ={x
k1
,…,x
km
}
B×B×……×B 中的任意元素a=(a
1
,…,a
n
),
a
i
{0,1}

令f(A)= (a
1
,…,a
n
)
If x
i
A then a
i
=1
If x
i
A then a
i
=0
其中
只需证明f是同构对应。
1) f是一一映射
2) AB iff (a
1
,…,a
n
)≤(b
1< br>,…,b
n
)，
显然成立

B
n
= B×B×……×B
设x＝a
1
a
2
……a
k
，< br>y＝b
1
b
2
……b
k
∈B
n

1．x≤y iff a
k
≤b
k
，k＝1,2,……,n
2. x∧y＝c
1
c
2
……c
k
，
c
k
＝min{ a
k
，
b
k
}
3. x∨y＝d
1
d
2
……d
k
，
d
k
＝max{ a
k
，
b
k
}
4．x’= z
1
z
2
……z
k
，
z
k
＝a
k’.

Homework P224－225
16，18，20，22，24，26

§6.5 布尔函数Function on Boolean
Algebra
布尔函数定义f:B
n
→B，
0元的布尔函数
0,1
1元的布尔函数
X
0
1



F
0
0
0
F
1

0
1
F
2

1
0
F
3

1
1

2元的布尔函数
X
1
X
2
F
0
F
1
F
2
F
3
F
4
F
5
F
6
F
7
F
8
F
9
F
10
F
11
F
12
F
13
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
名称 0 *

多元的布尔函数
f(x
1
,x
2
,……,x
n
)
x
1
x
2
x
3

0 0 0
0 0 1
0 1 0
f(x
1,
x
2
,x
3
)
1
0
0

0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
1
0
0
1
布尔函数的公式表示：
布尔多项式Boolean Polynomials
布尔表达式Boolean expression
p(x
1
,x
2
,……,x
n
):
1. 单个变元x
i
，1≤i≤n，是布尔多项式。
2. 0，1是布尔多项式。
3. 若p(x
1
,x
2
,……,x
n
)， q( x
1
,x
2
,……,x
n
)是布
尔多项式，则p( x
1
,x
2
,……,x
n
)∨
q(x
1< br>,x
2
,……,x
n
)，p(x
1
,x
2< br>,……,x
n
)∧
q(x
1
,x
2
,……, x
n
)，
（p(x
1
,x
2
,……,x
n
)）’，也是布尔多项式。
(x∨y)∧z, (x∨y’)∨(y∧1)，
(x∨(y’∧z))∨(x∧(y∧1))，
都是布尔多项式。

范式normal formulas
析取范式
极小项
命题变元p
1
,p
2
,……,p
n
的极小项
minimal terms
Q
1
∧Q
2
∧……∧Q
n
其中每个
Q
i
=p
i
或 ~p
i
1≤i≤n.

p
1
p
2
…p
n
有2
n
个极小项。

p
1
p
2
p
3
的8个极小项为
p
1
∧p
2
∧p
3
， p
1
∧p
2
∧~p
3
，
p
1
∧~p
2
∧p
3
， ~p
1
∧p
2
∧p
3
，
p
1
∧~p
2
∧~p
3
， ~p
1
∧~p
2
∧p
3
，
~p
1
∧p
2
∧~p
3
， ~p
1
∧~p
2
∧~p
3
。

每个极小相，只有一个对应的成真赋值。
p, q, r的8个极小项对应的赋值:

若干极小项的析取叫析取范式
normal disjunction formulas
定理 每个可满足的命题公式都等价于唯
一一个析取范式。

先给出命题公式的真值 表，找出取值为1
的所有赋值，这些赋值对应的基本合取项
的析取就是所求的析取范式。

也可以通过等价变换得到析取范式：
p→(q→r)  ~p∨~q∨r  ~p∧(q∨~q)
∧(r∨~r)∨(p∨~p) ∧~q
∧(r∨~r)∨(p∨~p) ∧(q∨~q)∧r
~p∧q∧r∨~p∧~q
∧r∨~p∧q∧~r∨~p∧~q∧~r∨p ∧~q
∧r∨p∧~q∧~r∨~p∧~q ∧r∨~p∧~q∧~
r∨p∧q∧r∨p∧~q∧r∨~p∧q∧r∨~p∧

~q∧r
~p∧q∧r∨~p∧q∧~r∨~p∧~q∧~r∨
p ∧~q
∧r∨p∧~q∧~r∨~p∧~q∧r∨~p∧~q∧~
r∨p∧q∧r
合取范式
命题变元p
1
,p
2
,……,p
n
的基本析取项
basic disjunction terms
Q
1
∨Q
2
∨……∨Q
n

其中每个
Q
i
=p
i
或 ~p
i
1≤i≤n.

p
1
p
2
…p
n
有2
n
个基本合取项。

p
1
p
2
p
3
的8个基本合取项为
p< br>1
∨p
2
∨p
3
，p
1
∨p
2∨~p
3
，
p
1
∨~p
2
∨p
3< br>，~p
1
∨p
2
∨p
3
，
p
1< br>∨~p
2
∨~p
3
，~p
1
∨~p∨p
3< br>，
~p
1
∨p
2
∨~p
3
，~p
1
∨~p
2
∨~p
3
。

命题变元p
1
,p
2
,…,p
n
的赋值σ(p
1
,p
2
,…,p
n
)

对应的基本析取项：
Q
1
∨Q
2
∨……∨Q
n


其中每个
σ
Q
i
=p
i
if p
i
=0

σ

Q
i
=~p
i
if p
i
=1.


设Q
1
∨Q
2
∨……∨Q
n
是命题变元
p
1
,p
2
,…,p
n
的一个基本析取 项，σ是
p
1
,p
2
,…,p
n
的一个赋值，
σ
(Q
1
∨Q
2
∨……∨Q
n
)=0
当且仅当
Q
1
∨Q
2
∨……∨Q
n
是σ对应的基本析
取项。




若干基本析取项的合取叫合取范式
Normal conjunction formulas

定理 每个不恒真的命题公式都等价于
唯一一个合取范式。

先给出命题公式A的真 值表，找出取值为
0的所有赋值，这些赋值对应的基本析取项
的合取就是A的合取范式。

也可以先给出~A的析取范式，再用De
Morgan律算出A的合取范式。

布尔函数的门电路表示：

联结词的全功能集functional complete
set of logical connectives

定义F={f
1
,…f
m
}为m个真值函数的集合，
若任意的n元真值函数h(x
1
,…,x
n
) 都可以
由f
1
,…,f
m
来构造，就说F是一个全功能集
常见全功能集
{~，∨，∧} 是一个全功能集。每个命题
公式都能表示为析取范式，可以只用~，∨，
∧做联结词。
{~,∧}, {~, ∨}也是全功能集。
由p∨q  ~(~p∧~q)
p∧q  ~(~p∨~q)
{~，→}也是全功能集
由p∨q ~ p→q知
{↑}, {↓} 也是全功能集。
↑与非 p↑q ~( p∧q)
↓或非 p↓q  ~(p∨q)

p q p↑q p↓q

0 0 1 1
~p p↑p  p↓p
0 1 1 0
p∧q ~(p↑q) 
1 0 1 0
(p↑q)↑(p↑q)
1 1 0 0
p∨q  ~( p↓q)
( p↓q)↓( p↓q)

如何证明一组函数是全功能集？
常见的非全功能集
{∨}，{∧}，{→}，{~， }都不是全功能集。
如何证明一组函数不是全功能集？
真值函数的性质
1) 1保持的 f(1,1,…,1)=1;
2) 0保持的 f(0,0,…,0)=0;
3) 单调的. 任意(x1,..,xn)(y1,…,yn)
有f(x1,..,xn)f(y1,…,yn)
4) 自对偶的。f(x1,..,xn)= f(x1,..,
xn)
5) 计数的。每个变量要么是哑变量，
要么是计数变量。
Post 定理
Homework P229
4，6，8，11，14，15，16，17，18
§6.6 线路设计Circuit Designs
定义
设f：B
n
→B是一个布尔函数，
令S(f)={b∈B
n
| f (b)=1}

定理1. 令f，f
1
, f
2
都是Bn到B的布尔函数。
（a） 如果S(f)=S( f
1
)∪S(f
2
),
则对任意b∈Bn，f(b)= f
1
(b)∨f
2
(b)
（b） 如果S(f)=S( f
1
)∩S(f
2
),
则对任意b∈Bn，f(b)= f
1
(b)∧f
2
(b)

例f：B
2
→B。
f(x,y)=x, S(f)={(1,0),(1,1)}
f(x,y)=y, S(f)={(0,1),(1,1)}
f(x,y)=x’, S(f)={(0,0),(0,1)}
f(x,y)=y’, S(f)={(0,0),(1,0)}

f(x,y)=x∧y, S(f)={(1,1)}
f(x,y)=x’∧y, S(f)={(0,1)}
f(x,y)=x∧y’, S(f)={(1,0)}
f(x,y)=x’∧y’, S(f)={(0,0)}

S(x’∧y’∧z)={(0,0,1)}

极小项minterm：
使S(f)是单元集的布尔函数f(x
1
,…，x
n
)叫极
小项。
极小项相当于基本合取范式。
x
1
’∧x
2
∧x
3
∧x
4
’，
S(x
1
’∧x
2
∧x
3
∧x
4
’)={(0,1,1,0)}

定理2.任意一个布尔函数都是布尔多项式。

证明.
令f: B
n
→B，S(f)={b
1
,b
2
,…,b
k
}
令f
i
：B
n
→B， S(f
i
)={b
i
},
f
i
可以表示为一个极小多项式，
f＝f
1
∨f
2
∨……∨f
k
，可以表示为布尔多项
式，极小多项式的析取，析取范式。

布尔函数的Karnaugh 图（卡诺图）
x y f(x,y)
0 0 b
0

0 1 b
1

1 0 b
2

1 1 b
3






例4．

x y f(x,y)
0 0 1
0 1 1
1 0 0
1 1 0
y’ y
x’ b
0
b
1

x b
2
b
3

y’ y
x’
x’∧y’ x’∧y
x
x∧y’ x∧y

f(x,y)=x’∧y’∨x’∧y＝x’

例5．
y’ y
x’ 1 1
x 0 0
x Y f(x,y)
y’ y
0 0 1
x’ 1 1
0 1 1
x 1 0
1 0 1
1 1 0

f(x,y)
=x’∧y’∨x’∧y∨x∧y’＝x’∨y’

f：B
3
→B，karnaugh图

y’ y
x’
x’∧y’∧z’ x’∧y’∧z

x’∧y∧z

x’∧y∧z’

x
X∧y’∧z’

x∧y’∧z

x∧y∧z

x∧y∧z’

z
z’ z’

y’





z z’





x’ x

＝y’
x’∧z
y
x’∧y’∧z’∨ x’∧y’∧z∨ x∧y’∧z’∨ x∧y’∧z



y’∧z’

x’∧z’ x∧y’∧z





例6．
x y z f(x,y,z)
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1

y’ y
x’
1 1 1 0
x
1 0 1 0

f(x,y,z)=y’∧z’∨x’∧y’∨y∧z






例7．
x y z
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
f(x,y,z)
1
0
1
0
1
0
1
1

y’ y
x’
1 0 0 1
x
1 0 1 1

f(x,y,z)=z’∨x∧y






f：B
4
→B

00 01 11 10
00 0000 0001 0011 0010
01 0100 0101 0111 0110
11 1100 1101 1111 1110
10 1000 1001 1011 1010

z’
z’
z z
x’
x’ Y
x Y

y’

x y’

w w
w’










z’





w’




z

y’ y










x’ x








w w’
例8．
1
0
0
1

0
1
1
0
0
1
1
0

1
0
0
1
z’ z’
z z

x’
1
x’
0
x
0

x
1
0 0 1
1 1 0
Y
1 1 0
Y
y’
0 0 1
y’

w w
w’ w’


f(x,y,z,w)=y’∧w’∨y∧w





例9．
1 1 1 1
0 0 0 0
0 0 1 0
1 1 0 0

z’ z’
z z
x’
1 1 1 1
y’
x’
0 0 0 0
Y
x
0 0 1 0
Y

x
1 1 0 0
y’

w w
w’ w’

f(x,y,z,w)=z’∧y’∨x’∧y’∧z∨x∧y∧z∧w

Homework
2，4，6，8，10，12，14，
16
本页为著作的 封面，下载以后可以删除本页！

【最新资料 Word版 可自由编辑！！】