Đai số Bool ̣ pptx
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.92 MB, 55 trang )
Đi s Bool
1
Nội Dung Chính
!
"#
$
2
HÀM BOOL
Đi s Bool
Nội Dung Chính (tt)
%&
%%&
''
!"#$%
&
#$%
'
($#)*+
,
-./$#)*+
0
123
4
5/$
6
-7$ !"
Đi s Bool
3
()'*+,-
%%%&
.
8$9
!":;#"$
<=>?
&
*@
'
!":
,
!":
0
ABCABD
%/&
0.
ECE !"
"=
/&
.1 2.#
2
-F$DB8
AGA$F$F$H
&
I"JC2AGA$F$F$H
/%&
$
&
32445
32445
Đi s Bool 5
I. Hàm Bool
Đi s Bool
6
George Boole
(1815-1864)
I. Hàm Bool
1.
Đại số Bool nhị phân:
Đại số bool của các số nhị phân cũng thỏa các trường hợp (luật) như trong mệnh đề.
Đi s Bool
7
Luât phủ định kép ¬ ¬E <=> E
Luật lũy đẳng E ˄ E <=> E
E ˅ E <=> E
Luật giao hoán F˄ E <=> E ˄ F
F ˅ E <=> E ˅ F
Luật kết hợp (E ˄ F) ˄ G <=> E ˄ (F ˄ G)
(E ˅ F) ˅ G <=> E ˅ (F ˅ G)
Luật phân phối E ˄ (G ˅ F) <=> (E ˄ G) ˅ (E ˄ F)
E ˅ (G ˄ F) <=> (E ˅ G) (E ˅ F)
Luật phủ định De-Morgan ¬ (E ˄ F) <=> ¬E ˅ ¬F
¬ (E ˅ F) <=> (¬E) ˄ (¬F)
Luật hấp thụ E ˄ (E ˅ F) <=> E ; E ˅ (E ˅ F) <=> E
Luật trung hòa E ˄ 1 <=> E
E ˅ 0 <=> E
Luật thống trị E ˄ 0 <=> 0
E ˅ 1 <=> 1
Luật bù E ˄ ¬E <=> 0
E ˅¬E <=> 1
Luật kéo theo E → F <=> ¬E ˅ F
Phủ định kéo theo ¬( E → F) <=> E ˄ ¬F
I. Hàm Bool
6&
7
& .89-C
:;<7
→
=>?@A=BC
2):)D ><?<+;
B
=;
6
=E=;
-=>F:;
B
=;
6
=E=;
G<H8?@A=BC
I#J
H$:&
/*K7L?L+$
B
=$
6
=E=$
-M:$
B
=$
6
=E=$
):&
Đi s Bool
8
1≥n
Nn ∈
I. Hàm Bool
6&
7
&
NO8
PQ:<+;
B
=;
6
=E=;
-
/0F:;
H8A=BRH>6STU$"):+;
B
=;
6
=E=;
-&
'>=N<>$N6VN8"<WXM6STU$":&YOXNO
8"<&
Đi s Bool
9
%&
6&
7
&
NO8
/*K7#S0GZ
WXM[\==DZ>]#^2(&
N8
K
L
-
1
<
I. Hàm Bool
3.
Các phép toán trên hàm Bool:
Với ta định nghĩa tổng, tích, bù hàm Bool của f và g như sau
Đi s Bool
11
,
F
gf
n
∈
)( gfgf +=∨
gffggf .==∧
ff −=1
I. Hàm Bool
3.
Các phép toán trên hàm Bool:
Ví dụ: n = 2
Đi s Bool
12
M
K K
M
K K
KN>
O>
P K K K K
N>
O>
P
QN>
O>
P K K
$N>
O>
P K K
R
QN>
O>
P K K
R
$N>
O>
P K K
Q$N>
O>
P K K K
QS$N>
O>
P K
''
''
Đi s Bool 13
%%& ''
B&
_`7
PQ$U$":J
M:;
B
=;
6
=E=;
&
2F;
Xa;
SUY_`&
/*K7;
B
=;
6
=;
b
=E
6&
.`7
5cdd")D e_`&
X>7*"BXf_`DcXdA&
/*K7Jg;Q;
b
=;
B
;
6
=
;
B
;
6
;
b
;
g
+"`D $[;-
J`>_B:
;=a;=X=aX=h=ah==a_`
;aXha=a;aX`
Đi s Bool
14
%%& ''
b&
.` !J7
5`>ViJ&
'j^?X
B
X
6
&&&X
=
X
?;
ka;
Bll
/*K7Jg;Q` !g
;
B
;
6
;
b
;
g=
;
B
a;
6
;
b
;
g=
;
B
;
6
;
b
;
g
=a;
B
a;
6
a;
b
a;
g
g&
.J7
5j`<?
B
/
6
/
b
/E/
d
=>
`&
/*K7Jm;Q
<+;
B
=;
6
=;
b=
;
g
-?;
B
a;
m
/a;
6
;
b
a;
g
/a;
b
/a;
B
;
b
;
g
;
m
?njg`<+B=A=B=B=A-?BaA/aABaB/aB/aBBBA?B
'
%%& ''
m&
' T*o"7
<)J=<>G:SpD
<?
B
/
6
/
b
/E/
d
=+q-
Gp
` !?+?BE-
+q-SUY T*o"<
/*K7Jg>DOX
<+;=X=h=-?;aXah/a;Xh/;Xaha>+q-
,
%%& ''
r&
T*o"7
>6;8 T*o")
-TF"$UA"C
IDT;#!F$
IDTSDV"IHWBIDOJCDF$/$CD>X$BA"#$J
IDTAYG#!"IHWBIDCBZX$B#[$-7$"IH*/$#)
*+B\"
/*K7J
b
T*o<+;=X=h-?a;/aXh/;Xah
<?a;+X/aX-&+h/ah-/+a;/;-aXh/;Xah
<?a;Xh/a;Xah/a;aXh/a;aXah/a;aXh/;aXh/;Xah+q-
+q-* T*o
0
II. Các Dạng Biểu Diễn Hàm Bool
r&
T*o"7
>6;8 T*o")
-T/[$B8$#!]AC^#B#$B8$#
Q_OJS^#BG"
O"
O`O"
QN"
O"
O`O"
P_
/*KTQN>OaP_>SRabB!"/$#)*+Q
c=B8$#Q
-!2Q_KKOKO=IH !"I$$
S=a/$#)*+QQN>OaP_R>RaS>RaS>a
Đi s Bool
18
II. Các Dạng Biểu Diễn Hàm Bool
7.
Mệnh đề:
f F∈
n
Khi đó,
f có thể có nhiều dạng đa thức khác nhau , ta chọn ra các công thức
đơn giản nhất có thể được. Chúng chính là các công thức đa thức
tối tiểu của f.
f chỉ có một dạng nối dời chính thức duy nhất (không tính sự hoán
đổi của các đơn thức).
Đi s Bool
19
II. Các Dạng Biểu Diễn Hàm Bool
8.
So sánh các dạng đa thức của hàm Bool:
f F∈
n
và f có 2 dạng đa thức
f = u
1
V u
2
V… V u
p
(1)
f = v
1
V v
2
V… V v
q
(2)
a. Ta nói (1) và (2) đơn giản ngang nhau nếu
p = q
deg(u
j
) = deg(v
j
) (1 ≤ j ≤ p)
b. Ta nói (1) đơn giản hơn (2) hay (2) phức tạp hơn (1)
p ≤ q
deg(u
j
) ≤ deg(u
j
) (1 ≤ j ≤ p)
chú ý:
Có thể hoán vị v
1
, v
2
, …,v
q
trước khi so sánh bậc nếu cần thiết
Có thể có những cặp đa thức không so sánh được
Đi s Bool
20
II. Các Dạng Biểu Diễn Hàm Bool
8.
So sánh các dạng đa thức của hàm Bool:
Ví dụ:
a. f F∈
4
có 3 dạng đa thức
f(x,y,z,t) = x ¬y ¬t V ¬xyz V x ¬z ¬ t V xyz (1)
= x ¬y ¬t V ¬xyz V xy ¬z V yzt (2)
= x ¬y ¬t V ¬xyzt V ¬xyz ¬t V xy ¬z V yzt (3)
(1) và (2) đơn giản ngang nhau
vì p = q = 4
deg(u
j
) = deg(v
j
) = 3
(2) đơn giản hơn (3) hay (3) phức tạp hơn (2)
vì q = 4 < r = 5
deg(v
j
) ≤ deg(q
j
)
Đi s Bool
21
II. Các Dạng Biểu Diễn Hàm Bool
8.
So sánh các dạng đa thức của hàm Bool:
Ví dụ:
b. g F∈
4
có 2 dạng đa thức
g(x,y,z,t) = x ¬yz V z ¬t V ¬xyz V ¬xy ¬zt (4)
= z ¬t V x ¬yzt V ¬xyzt V ¬xy ¬zt (5)
ta thấy: p = q = 4
d(
B
) > d(G
B
); d(
6
) < d(G
6
)
nên cần phải hoán vị
(5) x ¬yzt V z ¬t V ¬xyzt V ¬xy ¬zt (5`) (q` = 4)
(4) đơn giản hơn 5`
vì p = q` = 4
deg(u
j
) ≤ deg(w
j
)
Đi s Bool
22
%st.u
%st.u
\v(\tw
\v(\tw
Đi s Bool 23
ddd!":;#"$
B& !7
/p< J∈
d>7
QJ!Ja3"/$G"E#/$
$8@J!IHOJ*7$
!"BQ
J!. !"BBe$I$
B!":G#"$NBG7$f"&BAP
&
III. Biểu Đồ Karnaugh
2. Bảng mã: B = {0;1}
Bảng mã cho B
2
( 2 biến bool x và y)
11 01
10 00
x
y
y
x
Bảng mã cho B
3
(3 biến bool x, y, z)
x
x
101 111 011 001
100 110 010 000
x
x
y
y
y
y
z
z
Đi s Bool
25
