Bài giảng Thiết kế luận lý 1 - Chương 2: Đại số Boole các cổng luận lý - Nguyễn Quang Huy
dce
2012
Khoa KH & KTMT
Bộ môn Kỹ Thuật Máy Tính
BK
TP.HCM
©2012, CE Department
dce Tài liꢀu tham khꢁo
2012
• “Digital Systems, Principles and Applications”,
8th/5th Edition, R.J. Tocci, Prentice Hall
• “Digital Logic Design Principles”, N.
Balabanian & B. Carlson – John Wiley &
Sons Inc., 2004
©2012, CE Department
2
dce
2012
Đại số Boole &
các cổng luận lý
BK
TP.HCM
©2012, CE Department
dce Nꢂi dung
2012
• Đꢃi sꢄ Boole
• Đꢃi sꢄ chuyꢅn mꢃch
• Các cꢆng luꢇn lý
©2012, CE Department
4
dce Đꢃi sꢄ Boole
2012
• Đꢃi sꢄ Boole đưꢈc thꢉ giꢊi biꢉt đꢉn lꢋn đꢋu tiên bꢌi
George Boole qua tác phꢍm “An Investigation of the
Laws of Thought” vào năm 1854
• Các hꢎng và biꢉn Boole chꢏ đưꢈc mang 2 giá trꢐ 0
hoꢑc 1 ( LOW / HIGH )
– Các biꢉn Boole biꢅu diꢒn cho mꢂt khoꢁng điꢀn áp trên
đưꢓng dây hoꢑc tꢃi ngõ nhꢇp/ngõ xuꢔt cꢕa mꢃch
– Giá trꢐ 0 hoꢑc 1 đưꢈc gꢖi là mꢗc luꢇn lý (logic level)
A
x
F
y
Mꢃch
luꢇn lý
ngõ nhꢇp
ngõ xuꢔt
©2012, CE Department
5
dce Đꢃi sꢄ Boole
2012
• Đꢃi sꢄ Boole, cũng tương tꢘ như các hꢀ đꢃi sꢄ khác,
đưꢈc xây dꢘng thông qua viꢀc xác đꢐnh nghĩa mꢂt
sꢄ nhꢙng vꢔn đꢚ cơ bꢁn sau:
– Miꢚn (domain), là tꢇp hꢈp (set) các phꢋn tꢛ (element) mà
trên đó đꢐnh nghĩa nên hꢀ đꢃi sꢄ
miꢚn
– Mꢂt tꢇp hꢈp các đꢐnh đꢚ (postulate), hay tiên đꢚ (axiom)
đưꢈc công nhꢇn không qua chꢗng minh. Đꢐnh đꢚ phꢁi
đꢁm bꢁo tính nhꢔt quán (consistency) và tính đꢂc lꢇp
(independence)
– Mꢂt tꢇp hꢈp các hꢀ quꢁ (consequence) đưꢈc gꢖi là đꢐnh lý
(theorem), đꢐnh luꢇt (law) hay quy tꢜc (rule)
©2012, CE Department
6
dce Đꢐnh đꢚ Huntington
2012
• Phát biꢅu bꢌi nhà toán hꢖc Anh E.V.Huntington trên
cơ sꢌ hꢀ thꢄng hóa các công trình cꢕa G. Boole
– Sꢛ dꢝng các phép toán trong luꢇn lý mꢀnh đꢚ
(propositional logic)
• Tính đóng (closure)
toán + và • sao cho:
• Nꢉu x và y là các phꢋn tꢛ thuꢂc B thì x + y cũng là
1 phꢋn tꢛ thuꢂc B (phép cꢂng luꢇn lý - logical addition)
• Nꢉu x và y là các phꢋn tꢛ thuꢂc B thì x • y cũng là
1 phꢋn tꢛ thuꢂc B (phép nhân luꢇn lý - logical
multiplication)
©2012, CE Department
7
dce Đꢐnh đꢚ Huntington …
2012
• Tính đꢞng nhꢔt (identity)
Nꢉu x là mꢂt phꢋn tꢛ trong miꢚn B thì
– Tꢞn tꢃi 1 phꢋn tꢛ 0 trong B , gꢖi là phꢋn tꢛ đꢞng nhꢔt vꢊi
phép toán + , thꢟa mãn tính chꢔt x + 0 = x
– Tꢞn tꢃi 1 phꢋn tꢛ 1 trong B , gꢖi là phꢋn tꢛ đꢞng nhꢔt vꢊi
phép toán • , thꢟa mãn tính chꢔt x • 1 = x
• Tính giao hoán (commutative)
– Giao hoán cꢕa phép + :
x + y = y + x
– Giao hoán cꢕa phép • :
x • y = y • x
©2012, CE Department
8
dce Đꢐnh đꢚ Huntington …
2012
• Tính phân phꢄi (distributive)
– Phép • có tính phân phꢄi trên phép +
x • (y + z) = (x • y) + (x • z)
– Phép + có tính phân phꢄi trên phép •
x + (y • z) = (x + y) • (x + z)
• Bù (complementation)
Nꢉu x là 1 phꢋn tꢛ trong miꢚn B thì sꢠ tꢞn tꢃi mꢂt phꢋn tꢛ
khác gꢖi là x’ (hay x ), là phꢋn tꢛ bù cꢕa x thꢟa mãn:
– x + x’ = 1 và
– x • x’ = 0
©2012, CE Department
9
dce Tính đꢄi ngꢡu (duality)
2012
• Quan sát các đꢐnh đꢚ Hungtinton, ta thꢔy chúng
mang tính đꢄi xꢗng (symmetry) tꢗc là các đꢐnh đꢚ
xuꢔt hiꢀn theo cꢑp
• Mꢢi đꢐnh đꢚ trong 1 cꢑp có thꢅ đưꢈc xây dꢘng tꢣ
đꢐnh đꢚ còn lꢃi bꢎng cách
– Thay đꢆi các phép toán 2 ngôi ( + | • )
– Thay đꢆi các phꢋn tꢛ đꢞng nhꢔt ( 0 | 1 )
• Có thꢅ suy ra mꢂt kꢉt quꢁ nào đó tꢣ các đꢐnh đꢚ
bꢎng cách
– Hoán đꢆi phép toán + vꢊi phép toán •
– Hoán đꢆi phꢋn tꢛ đꢞng nhꢔt 0 vꢊi phꢋn tꢛ đꢞng nhꢔt 1
• Điꢚu này thꢅ hiꢀn tính đꢄi ngꢡu ꢌ đꢃi sꢄ Boole
©2012, CE Department
10
dce
2012
Các đꢐnh lý cơ bꢁn (fundamental theorem)
• Các đꢐnh lý đưꢈc chꢗng minh tꢣ các đꢐnh đꢚ
Huntington và các đꢐnh đꢚ đꢄi ngꢡu theo 2 cách
– Chꢗng minh bꢎng phꢁn chꢗng (contradiction)
– Chꢗng minh bꢎng quy nꢃp (induction)
• Đꢐnh lý 1 (Null Law)
• Đꢐnh lý 2 (Involution)
– (x’ )’ = x
• Đꢐnh lý 3 (Idempotency)
– x + x = x
– x • x = x
• Đꢐnh lý 4 (Absorption)
– x + x • y = x
– x • (x + y) = x
©2012, CE Department
11
dce Các đꢐnh lý cơ bꢁn …
2012
• Đꢐnh lý 5
– x + x’ y = x + y
– x (x’ + y ) = x y
• Đꢐnh lý 6 (Associative Law)
(Simplification)
– x + (y + z) = (x + y ) + z = x + y + z
– x (y z) = (x y) z = x y z
• Đꢐnh lý 7
(Consensus)
– x y + x’ z + y z = x y + x’ z
– (x + y) (x’ + z) (y + z) = (x + y) (x’ + z)
• Đꢀnh lý 8
– (x + y)’ = x’ y’
– (x y)’ = x’ + y’
(De Morgan’s Law)
©2012, CE Department
12
dce Bꢁng sꢘ thꢇt (Truth table)
2012
• Phương tiꢀn mô tꢁ sꢘ phꢝ thuꢂc cꢕa ngõ xuꢔt vào mꢗc luꢇn
lý (logic level) tꢃi các ngõ nhꢇp cꢕa mꢃch
– Liꢀt kê tꢔt cꢁ các tꢆ hꢈp có thꢅ cꢕa mꢗc luꢇn lý tꢃi các ngõ
nhꢇp và kꢉt quꢁ mꢗc luꢇn lý tương ꢗng tꢃi ngõ xuꢔt cꢕa mꢃch
– Sꢄ tꢆ hꢈp cꢕa bꢁng N-ngõ nhꢇp: 2N
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
x
0
1
1
0
0
0
0
1
0
0
1
1
0
1
0
1
1
0
1
0
A
B
x
?
©2012, CE Department
13
dce
2012
Đꢃi sꢄ chuyꢅn mꢃch (switching algebra)
• Đꢄi vꢊi đꢃi sꢄ Boole, miꢚn không bꢐ hꢃn chꢉ (không có giꢊi
hꢃn đꢑt ra đꢄi vꢊi sꢄ lưꢈng các phꢋn tꢛ trong miꢚn)
• Các đꢐnh đꢚ Huntington giꢊi hꢃn xem xét đꢃi sꢄ Boole vꢊi 2
phꢋn tꢛ đꢞng nhꢔt mà thôi
ꢀ Đꢁi sꢂ Boole 2 phꢃn tꢄ
• Năm 1937, Claude Shannon hiꢀn thꢘc đꢃi sꢄ Boole 2 phꢋn
tꢛ bꢎng mꢃch điꢀn vꢊi các chuyꢅn mꢃch (switch)
– Chuyꢅn mꢃch là thiꢉt bꢐ có 2 vꢐ trí bꢚn: tꢜt (off) hay mꢌ (on)
– 2 vꢐ trí này phù hꢈp đꢅ biꢅu diꢒn cho 0 hay 1
ꢀ Đꢁi sꢂ Boole 2 phꢃn tꢄ còn đưꢅc gꢆi là đꢁi sꢂ chuyꢇn mꢁch
– Các phꢋn tꢛ đꢞng nhꢔt đưꢈc gꢖi là các hꢎng chuyꢅn mꢃch
(switching constant)
– Các biꢉn (variable) biꢅu diꢒn các hꢎng chuyꢅn mꢃch đưꢈc gꢖi
là các biꢉn chuyꢅn mꢃch (switching variable) ꢁ tín hiꢈu
©2012, CE Department
14
dce Các phép toán chuyꢅn mꢃch
2012
• Đꢃi sꢄ chuyꢅn mꢃch sꢛ
dꢝng các phép toán trong
luꢇn lý mꢀnh đꢚ vꢊi tên
gꢖi khác
x
0
0
1
1
y x • y x + y x’
0
1
0
1
0
0
0
1
0
1
1
1
1
1
0
0
• Phép toán AND
– Phép toán 2 ngôi tương
đương vꢊi phép nhân
luꢇn lý
Bꢁng sꢘ thꢇt các phép
chuyꢅn mꢃch
• Phép toán OR
• Phép toán NOT
– Phép toán 2 ngôi tương
đương vꢊi phép cꢂng
luꢇn lý
– Phép toán 1 ngôi
tương đương vꢊi
phép bù luꢇn lý
©2012, CE Department
15
dce Các phép toán chuyꢅn mꢃch …
2012
• Các phép toán chuyꢅn mꢃch có thꢅ đưꢈc hiꢀn thꢘc bꢌi
mꢃch phꢋn cꢗng
• Bꢁng sꢘ thꢇt có thꢅ sꢛ dꢝng như 1 công cꢝ dùng đꢅ xác
minh quan hꢀ giꢙa các phép toán chuyꢅn mꢃch
• Sꢛ dꢝng bꢁng sꢘ thꢇt đꢅ chꢗng minh đꢐnh lý De Morgan
(x + y)’ = x’ y’
x
0
0
1
1
y
0
1
0
1
x’
1
1
0
0
y’
1
0
1
0
x + y (x + y)’ x’ y’
0
1
1
1
1
0
0
0
1
0
0
0
©2012, CE Department
16
dce
2012
Biꢅu thꢗc (expression) chuyꢅn mꢃch
• Biꢅu thꢗc chuyꢅn mꢃch là mꢂt quan hꢀ hꢙu hꢃn các
hꢎng, biꢉn, biꢅu thꢗc chuyꢅn mꢃch liên kꢉt vꢊi nhau
bꢌi các phép toán AND, OR và NOT
• Ví dꢝ
y + 1 , x x’ + x ,
z ( x + y’ )’
E = ( x + y z ) ( x + y’ ) + ( x + y )’
• literal đưꢈc sꢛ dꢝng đꢅ ám chꢏ biꢉn hay bù cꢕa biꢉn
©2012, CE Department
17
dce
2012
Biꢅu thꢗc (expression) chuyꢅn mꢃch...
• Mꢂt biꢅu thꢗc có thꢅ đưꢈc chuyꢅn thành nhiꢚu dꢃng
tương đương bꢎng cách sꢛ dꢝng các luꢇt Boole
E = (x + y z) (x + y’) + (x + y)’
E1 = x x + x y’ + x y z + y y’ z + x’ y’
E2 = x + x (y’ + y z) + x’ y’
E3 =x + x’ y’
E4 =x + y’
• Tꢃi sao phꢁi chuyꢅn đꢆi dꢃng cꢕa các biꢅu thꢗc ?
• Các thành phꢋn thꢣa (redundant) trong biꢅu thꢗc
– literal lꢑp ( x x hay x + x)
– biꢉn và bù ( x x’ hay x + x’)
– hꢎng (0 hay 1)
• Không hiꢈn thꢉc các thành phꢃn thꢊa cꢋa biꢇu
thꢌc vào mꢁch
©2012, CE Department
18
dce Hàm (function) chuyꢅn mꢃch
2012
• Hàm chuyꢅn mꢃch (switching function) là mꢂt phép gán xác
đꢐnh và duy nhꢔt cꢕa nhꢙng giá trꢐ 0 và 1 cho tꢔt cꢁ các tꢆ
hꢈp giá trꢐ cꢕa các biꢉn thành phꢋn
• Hàm đưꢈc xác đꢐnh bꢌi danh sách các trꢐ hàm tꢃi mꢢi tꢆ hꢈp
giá trꢐ cꢕa biꢉn (bꢀng sꢁ thꢂt)
– Tꢞn tꢃi nhiꢚu biꢅu thꢗc biꢅu diꢒn cho 1 hàm
• Sꢄ lưꢈng hàm chuyꢅn mꢃch vꢊi n biꢉn là 2 luꢤ thꢣa 2n
x
0
0
1
1
y x’ y’
0 1 1
1 1 0
0 0 1
1 0 0
x’ y’
1
E1 = x + x’ y’ E2 = x + y’
1
0
1
1
1
0
1
0
0
0
1
©2012, CE Department
19
dce Các phép toán chuyꢅn mꢃch khác
2012
• Phép toán NAND
• Phép toán Exclusive OR
– Phép toán 2 ngôi tương
đương vꢊi (NOT AND)
– E = x y = x’ y + x y’
• Phép toán NOR
• Phép toán XNOR (Ex. NOR)
– Phép toán 2 ngôi tương
đương vꢊi (NOT OR)
– E = ( x y )’ = x y + x’ y’
Biꢍn
NAND
NOR
Ex. OR
XNOR
x
0
0
1
1
y
0
1
0
1
(x . y)’
(x + y)’
x y
(x y)’
1
1
1
0
1
0
0
0
0
1
1
0
1
0
0
1
©2012, CE Department
20
Tải về để xem bản đầy đủ
34 trang
18200
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thiết kế luận lý 1 - Chương 2: Đại số Boole các cổng luận lý - Nguyễn Quang Huy", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_thiet_ke_luan_ly_1_chuong_2_dai_so_boole_cac_cong.pdf
