Trung tâm đào tạo thiết kế vi mạch Semicon


  • ĐĂNG KÝ TÀI KHOẢN ĐỂ TRUY CẬP NHIỀU TÀI LIỆU HƠN!
  • Create an account
    *
    *
    *
    *
    *
    Fields marked with an asterisk (*) are required.
semicon_lab.jpg

Boolean Algebra and Logic Circuits Part-II

Sunday, 19 December 2021 14:46 Semicon Editor 01
E-mail Print PDF

Boundedness Law
X + 1 = 1
X . 0 = 0

Elimination Law

 

X + (X . Y) = X
X . (X + Y ) = X

Elimination Law
X + (X' . Y) = X + Y
X.(X' + Y) = X.Y
Unique Complement theorem
If X + Y = 1 and X.Y = 0 then X = Y'
Involution theorem
X'' = X
0' = 1

Associative Properties

X + (Y + Z) = (X + Y) + Z
X . ( Y . Z ) = ( X . Y ) . Z
Duality Principle
In Boolean algebras the duality Principle can be is obtained by interchanging AND and OR operators and replacing 0's by 1's and 1's by 0's. Compare the identities on the left side with the identities on the right.
Example
X.Y+Z' = (X'+Y').Z
Consensus theorem
X.Y + X'.Z + Y.Z = X.Y + X'.Z
or dual form as below
(X + Y).(X' + Z).(Y + Z) = (X + Y).(X' + Z)
Proof of X.Y + X'.Z + Y.Z = X.Y + X'.Z:

X.Y + X'.Z + Y.Z

= X.Y + X'.Z

X.Y + X'.Z + (X+X').Y.Z

= X.Y + X'.Z

X.Y.(1+Z) + X'.Z.(1+Y)

= X.Y + X'.Z

X.Y + X'.Z

= X.Y + X'.Z

(X.Y'+Z).(X+Y).Z = X.Z+Y.Z instead of X.Z+Y'.Z

X.Y'Z+X.Z+Y.Z

(X.Y'+X+Y).Z
(X+Y).Z
X.Z+Y.Z

The term which is left out is called the consensus term.

Given a pair of terms for which a variable appears in one term, and its complement in the other, then the consensus term is formed by ANDing the original terms together, leaving out the selected variable and its complement.

Example 

The consensus of X.Y and X'.Z is Y.Z

The consensus of X.Y.Z and Y'.Z'.W' is (X.Z).(Z.W')

Shannon Expansion Theorem

The Shannon Expansion Theorem is used to expand a Boolean logic function (F) in terms of (or with respect to) a Boolean variable (X), as in the following forms.

F = X . F (X = 1) + X' . F (X = 0)
where F (X = 1) represents the function F evaluated with X set equal to 1; F (X = 0) represents the function F evaluated with X set equal to 0.
Also the following function F can be expanded with respect to X

F = X' . Y + X . Y . Z' + X' . Y' . Z

= X . (Y . Z') + X' . (Y + Y' . Z)
Thus, the function F can be split into two smaller functions
F (X = '1') = Y . Z'

This is known as the cofactor of F with respect to X in the previous logic equation. The cofactor of F with respect to X may also be represented as F X (the cofactor of F with respect to X' is F X' ). Using the Shannon Expansion Theorem, a Boolean function may be expanded with respect to any of its variables. For example, if we expand F with respect to Y instead of X,
F = X' . Y + X . Y . Z' + X' . Y' . Z
= Y . (X' + X . Z') + Y' . (X' . Z)
A function may be expanded as many times as the number of variables it contains until the canonical form is reached. The canonical form is a unique representation for any Boolean function that uses only minterms. A minterm is a product term that contains all the variables of F¿such as X . Y' . Z).
Any Boolean function can be implemented using multiplexer blocks by representing it as a series of terms derived using the Shannon Expansion Theorem.

Summary of Laws And Theorms

Identity

Dual

Operations with 0 and 1

  

X + 0 = X (identity)

X.1 = X

X + 1 = 1 (null element)

X.0 = 0

Idempotency theorem

  

X + X = X

X.X = X

Complementarity

  

X + X' = 1

X.X' = 0

Involution theorem

  

(X')' = X

  

Cummutative law

  

X + Y = Y + X

X.Y = Y X

Associative law

  

(X + Y) + Z = X + (Y + Z) = X + Y + Z

(XY)Z = X(YZ) = XYZ

Distributive law

  

X(Y + Z) = XY + XZ

X + (YZ) = (X + Y)(X + Z)

DeMorgan's theorem

  

(X + Y + Z + ...)' = X'Y'Z'... or { f ( X1,X2,...,Xn,0,1,+,. ) } = { f ( X1',X2',...,Xn',1,0,.,+ ) }

(XYZ...)' = X' + Y' + Z' + ...

Simplification theorems

  

XY + XY' = X (uniting)

(X + Y)(X + Y') = X

X + XY = X (absorption)

X(X + Y) = X

(X + Y')Y = XY (adsorption)

XY' + Y = X + Y

Consensus theorem

  

XY + X'Z + YZ = XY + X'Z

(X + Y)(X' + Z)(Y + Z) = (X + Y)(X' + Z)

Duality

  

(X + Y + Z + ...)D = XYZ... or {f(X1,X2,...,Xn,0,1,+,.)}D = f(X1,X2,...,Xn,1,0,.,+)

(XYZ ...)D = X + Y + Z + ...

Shannon Expansion Theorem

  

f(X1,...,Xk,...Xn)

Xk * f(X1,..., 1 ,...Xn) + Xk' * f(X1,..., 0 ,...Xn)

f(X1,...,Xk,...Xn)

[Xk + f(X1,..., 0 ,...Xn)] * [Xk' + f(X1,..., 1 ,...Xn)]

Boundedness Law

X + 1 = 1

X . 0 = 0

Elimination Law

 

X + (X . Y) = X
X . (X + Y ) = X

Elimination Law
X + (X' . Y) = X + Y
X.(X' + Y) = X.Y
Unique Complement theorem
If X + Y = 1 and X.Y = 0 then X = Y'
Involution theorem
X'' = X
0' = 1

Associative Properties

X + (Y + Z) = (X + Y) + Z
X . ( Y . Z ) = ( X . Y ) . Z
Duality Principle
In Boolean algebras the duality Principle can be is obtained by interchanging AND and OR operators and replacing 0's by 1's and 1's by 0's. Compare the identities on the left side with the identities on the right.
Example
X.Y+Z' = (X'+Y').Z
Consensus theorem
X.Y + X'.Z + Y.Z = X.Y + X'.Z
or dual form as below
(X + Y).(X' + Z).(Y + Z) = (X + Y).(X' + Z)
Proof of X.Y + X'.Z + Y.Z = X.Y + X'.Z:

X.Y + X'.Z + Y.Z

= X.Y + X'.Z

X.Y + X'.Z + (X+X').Y.Z

= X.Y + X'.Z

X.Y.(1+Z) + X'.Z.(1+Y)

= X.Y + X'.Z

X.Y + X'.Z

= X.Y + X'.Z

(X.Y'+Z).(X+Y).Z = X.Z+Y.Z instead of X.Z+Y'.Z

X.Y'Z+X.Z+Y.Z

(X.Y'+X+Y).Z
(X+Y).Z
X.Z+Y.Z

The term which is left out is called the consensus term.

Given a pair of terms for which a variable appears in one term, and its complement in the other, then the consensus term is formed by ANDing the original terms together, leaving out the selected variable and its complement.

Example 

The consensus of X.Y and X'.Z is Y.Z

The consensus of X.Y.Z and Y'.Z'.W' is (X.Z).(Z.W')

Shannon Expansion Theorem

The Shannon Expansion Theorem is used to expand a Boolean logic function (F) in terms of (or with respect to) a Boolean variable (X), as in the following forms.

F = X . F (X = 1) + X' . F (X = 0)
where F (X = 1) represents the function F evaluated with X set equal to 1; F (X = 0) represents the function F evaluated with X set equal to 0.
Also the following function F can be expanded with respect to X

F = X' . Y + X . Y . Z' + X' . Y' . Z

= X . (Y . Z') + X' . (Y + Y' . Z)
Thus, the function F can be split into two smaller functions
F (X = '1') = Y . Z'

This is known as the cofactor of F with respect to X in the previous logic equation. The cofactor of F with respect to X may also be represented as F X (the cofactor of F with respect to X' is F X' ). Using the Shannon Expansion Theorem, a Boolean function may be expanded with respect to any of its variables. For example, if we expand F with respect to Y instead of X,
F = X' . Y + X . Y . Z' + X' . Y' . Z
= Y . (X' + X . Z') + Y' . (X' . Z)
A function may be expanded as many times as the number of variables it contains until the canonical form is reached. The canonical form is a unique representation for any Boolean function that uses only minterms. A minterm is a product term that contains all the variables of F¿such as X . Y' . Z).
Any Boolean function can be implemented using multiplexer blocks by representing it as a series of terms derived using the Shannon Expansion Theorem.

Summary of Laws And Theorms

Identity

Dual

Operations with 0 and 1

  

X + 0 = X (identity)

X.1 = X

X + 1 = 1 (null element)

X.0 = 0

Idempotency theorem

  

X + X = X

X.X = X

Complementarity

  

X + X' = 1

X.X' = 0

Involution theorem

  

(X')' = X

  

Cummutative law

  

X + Y = Y + X

X.Y = Y X

Associative law

  

(X + Y) + Z = X + (Y + Z) = X + Y + Z

(XY)Z = X(YZ) = XYZ

Distributive law

  

X(Y + Z) = XY + XZ

X + (YZ) = (X + Y)(X + Z)

DeMorgan's theorem

  

(X + Y + Z + ...)' = X'Y'Z'... or { f ( X1,X2,...,Xn,0,1,+,. ) } = { f ( X1',X2',...,Xn',1,0,.,+ ) }

(XYZ...)' = X' + Y' + Z' + ...

Simplification theorems

  

XY + XY' = X (uniting)

(X + Y)(X + Y') = X

X + XY = X (absorption)

X(X + Y) = X

(X + Y')Y = XY (adsorption)

XY' + Y = X + Y

Consensus theorem

  

XY + X'Z + YZ = XY + X'Z

(X + Y)(X' + Z)(Y + Z) = (X + Y)(X' + Z)

Duality

  

(X + Y + Z + ...)D = XYZ... or {f(X1,X2,...,Xn,0,1,+,.)}D = f(X1,X2,...,Xn,1,0,.,+)

(XYZ ...)D = X + Y + Z + ...

Shannon Expansion Theorem

  

f(X1,...,Xk,...Xn)

Xk * f(X1,..., 1 ,...Xn) + Xk' * f(X1,..., 0 ,...Xn)

f(X1,...,Xk,...Xn)

[Xk + f(X1,..., 0 ,...Xn)] * [Xk' + f(X1,..., 1 ,...Xn)]

Bạn Có Đam Mê Với Vi Mạch hay Nhúng      -     Bạn Muốn Trau Dồi Thêm Kĩ Năng

Mong Muốn Có Thêm Cơ Hội Trong Công Việc

Và Trở Thành Một Người Có Giá Trị Hơn

Bạn Chưa Biết Phương Thức Nào Nhanh Chóng Để Đạt Được Chúng

Hãy Để Chúng Tôi Hỗ Trợ Cho Bạn. SEMICON  

Last Updated ( Tuesday, 29 March 2022 00:36 )  
Chat Zalo