电子科大数字电路课件4-1定理 chenyu

Idempotency (同一律): (同一律 同一律):
变量和 常量的 关系
(T3) X + X = X (T3’) X · X = X
变量和 其自身 的关系
(还原律 还原律) Involution (还原律)：(T4) ( X’ )’ = X
(互补律 互补律): Complements (互补律):
X+XY=X X X + Y = X(错) 错 X(X+Y)=X 例： 写出下面函数的对偶函数 F1 = A + B (C + D) F2 = ( A’(B+C’) + (C+D)’ )’
对偶定理 （Duality Theorems）
证明公式： 证明公式：A+BC = (A+B)(A+C) A(B+C) AB+AC
4.1 Switching Algebra
Axioms（ 4.1.1 Axioms（公理 ） P185
（A1）X = 0 if X ≠ 1, ） （A3）00 = 0 ） （A4） 11 = 1 ） （A5） 01 = 10 = 0 ） （A1’） X = 1 if X ≠ 0 ） （A3’） 1+1 = 1 ） （A4’） 0+0 = 0 ）
Similar Relationship with General Algebra (与普通代数相似的关系 与普通代数相似的关系) 与普通代数相似的关系 Commutativity (交换律) 交换律)
(T6)X + Y = Y + X (T6’) X · Y= Y ·X (T7’) X+(Y+Z) = (X+Y)+Z (T8’) X+Y·Z = (X+Y)·(X+Z)
complement of a logic expression (F)’
(反演定理 反演定理) 反演定理
' 1
( P192)
' 2 ' n
[F(X1, X2 ,L, Xn,+,•)]' = F(X , X ,L, X ,•,＋ )
反演规则(Complement Rules)： swapping + and . and complementing all variables. · ⇔ +，0 ⇔ 1，变量取反 遵循原来的运算优先（Priority） 遵循原来的运算优先（Priority）次序 不属于单个变量上的反号应保留不变
Logical addition 逻辑加 Plus sign(+)
（A2）If X = 0,then X’ = 1（A2’）If X = 1,then X’ =0 ） （ ）
（A5’） 1+0 = 0+1 = 1 ）
逻辑乘 logical multiplication dot 乘点 multiplication dot We stated these axioms as a pair, with the only difference between A1 and A1’ being the interchange of the symbols 0 and 1. This is a characteristic of all the axioms of switching algebra . P（185）
4.1.2 Single-Variable Theorems (单变量开关代数定理 P188 单变量开关代数定理) 单变量开关代数定理
(自等律 自等律) Identities (自等律)：
(T1) X + 0 = X (T1’) X · 1 = X Elements(0Null Elements(0-1律)： (T2) X + 1 = 1 (T2’) X · 0 = 0
(T5) X + X’ = 1 (T5’) X · X’ =0
4.1.3 Two- and Three-Variable Theorems(1)
Each of these theorems is easily proved by perfect induction. (可以利用完备归纳法证明公式和定理 P188 可以利用完备归纳法证明公式和定理) 可以利用完备归纳法证明公式和定理
v
Basic Concept (基本概念 基本概念) 基本概念
Logic circuits are classified into two types（逻辑电路分为两大类） combinational logic circuit（组合逻辑电路） A combinational logic circuit is one whose outputs depend only on its current inputs.（任何时刻的输出仅取决与当时的输入）
错！
A=1, B=0, C=1
4.1.4 n-Variable Theorems (n变量定理 变量定理) 变量定理
Generalized idempotency(广义同一律 广义同一律) Most of these theorems广义同一律proved can be (T12) X + X + … + X =method called · … · X = X (T12’) X · X using a two-step X DeMorgan’s 摩根定理) DeMorgan s Theorems(德.摩根定理that the finite induction—first proving ) (T13) (X1·X2is true nfor n =X2 +……+X n’ step) theorem ·……·X )’=X1’+ 2’ (the basis (T13’)thenX2+ ……+Xthat X1’the2’theorem’ is (X1+ proving n)’= if · X ·……· X n and Generalized DeMorgan s Theorems (广义德.摩根定理) DeMorgan’s 广义德. 广义德 摩根定理) true for n = i, then it is also true for (T14)[F(X1 ,X2 …,X n,+, ·)]’=F(X1’, X2’,…,X n’, ·,+) n = i + 1 (the induction step). P(190)
finite induction (P190)
X + X + X + … + X = X + (X + X + …+ X) (i + 1 X’s on either side) = X + (X) (if T12 is true for n = i) = X (according to T3)
Demorgan’s Theorems(摩根定理) (P191)
(T9) X + X·Y = X (T9’) X·(X+Y) = X
Combining(合并律) Combining(合并律) 合并律
(T10) X·Y + X·Y’ = X (T10’) (X+Y)·(X+Y’) = X
Consensus（添加律（一致性定理）） Consensus（添加律（一致性定理））
⇔ +；0 ⇔ 1 ； FD(X1 , X2 , … , Xn , + , , ’ ) = F(X1 , X2 , … , Xn , , + , ’ )
变换时不能破坏原来的运算顺序（优先级） 变换时不能破坏原来的运算顺序（优先级）
对偶原理 (Principle of Duality)
若两逻辑式相等， 若两逻辑式相等，则它们的对偶式也相等
(AB + A’C)’ (A’+B’)(A+C’) A’A +A’C’ + AB’ + B’C’ A’C’ + AB’ + B’C’ A’C’ + AB’ AB + A’C + BC = AB + A’C
4.1.5 duality(对偶定理 (P193) 对偶定理) 对偶定理
Principle of Duality Any theorem or identity in switching algebra remains true if 0 and 1 are swapped and . and + are swapped throughout.
the dual of a logic expression
FD(X1 , X2 , … , Xn , + , , ’ ) = F(X1 , X2 , … ,Xn , , + , ’ )
[F(X1,X2,…,Xn)]’ = FD(X1’,X2’,…,Xn’)
4.1.5 duality(对偶定理 (P193) 对偶定理) 对偶定理 对偶规则
characteristic：no feedback circuit ：
sequential logic circuit（时序逻辑电路）
The outputs of a sequential logic circuit depend not only on the current inputs, but also on the past sequence of inputs, possibly arbitrarily far back in time.（任一时刻的输出不仅取决于当时的输入，还取决于过去的输入顺序） （
(T11) X·Y + X’·Z + Y·Z = X·Y + X’·Z (T11’) (X+Y)·(X’+Z)·(Y+Z) = (X+Y)·(X’+Z)
Notes
no power of number(没有变量的乘方) A·A·A ≠ A3 common factor(允许提取公因子) AB+AC = A(B+C) no division(没有定义除法) A=1, B=0, C=0 if AB=BC A=C ?? 错！ AB=BC=0, A≠C No subtracting(没有定义减法 没有定义减法) 没有定义减法 if A+B=A+C B=C ??
chapter
4
Combinational Logic Design Principles
v
v
Fra Baidu bibliotek
chapter
4
Switching Algebra Combinational Circuit Analysis Combinational Circuit Synthesis Timing Hazards
Duality and Complement (对偶和反演 (P194.P195) 对偶和反演) 对偶和反演
对偶(Duality)： 对偶(Duality)：F (X1 , X2 , … , Xn , + , , ’ ) (Duality) = F(X1 , X2 , … , Xn , , + , ’ ) 反演(Complement)： 反演(Complement)： [ F(X1 , X2 , … , Xn , + , ) ]’ (Complement) = F(X1’ , X2’, … , Xn’ , , + ) [ F(X1 , X2 , … , Xn) ]’ = F (X1’ , X2’, … , Xn’ )
结合律) Associativity (结合律)
(T7) X·(Y·Z) = (X·Y)·Z (T8) X·(Y+Z) = X·Y+X·Z
(分配律 分配律) Distributivity (分配律)
4.1.3 Two- and Three-VariableTheorems(2) Covering(吸收律) Covering(吸收律) 吸收律
' ' (X1 ⋅ X2 ⋅L Xn )'= X1' + X2 +L+ Xn ⋅
(X1 X2 L Xn )' = X ⋅ X ⋅L⋅ X ＋ ＋＋
' 1 ' 2
' 1 ' 2
' n
' n
[F( X1, X2 ,L, Xn ,+,•)]' = F( X , X ,L, X ,•,＋ )
(A B)’ = A’ + B’ (A + B)’ = A’ B’
合理地运用反演定理能够将一些问题简化
例1：写出下面函数的反函数 （Complement function ) F1 = A (B + C) + C D F2 = (A B)’ + C D E’
例2：证明 (AB + A’C)’ = AB’ + A’C’
合理地运用反演定理能够将一些问题简化 Example 2：prove (A·B + A’·C)’ = A·B’ + A’·C’ ：