Xem mẫu
- TOÁN RỜI RẠC
(DISCRETE MATHEMATICS)
Bùi Thị Thủy
Đặng Xuân Thọ
- Support
2
TS. Đặng Xuân Thọ
Mobile: 091.2629.383
Email: thodx@hnue.edu.vn
Website: http://fit.hnue.edu.vn/~thodx/
Toán rời rạc - ĐHSPHN
- NỘI DUNG
3
Chương 1. Logic mệnh đề
Chương 2. Lý thuyết tập hợp
Chương 3. Một số công thức tổ hợp
Chương 4. Suy luận và kiểm chứng chương trình
Chương 5. Đại số Boole và cấu trúc mạch logic
Chương 6. Thuật toán
Chương 7. Lý thuyết đồ thị
Toán Rời Rạc - ĐHSPHN
- Chương 5. Đại Số Boole & Cấu Trúc
Mạch Logic
4
Giúp tính toán các biểu thứ logic trên bảng giá
trị chân lý 0 và 1 cho ra đời một ngành toán
học mới là đại số Boole.
Biểu thức Boole và hàm Boole
Xác định biểu thức Boole của hàm Boole
Sơ đồ mạch logic
Toán Rời Rạc - ĐHSPHN
- 5 Biểu thức Boole và hàm Boole
Toán Rời Rạc - ĐHSPHN
- Biểu thức Boole & hàm Boole
6
Định nghĩa. Đại số Boole là một tập hợp B với 3
phép toán: phép lấy phần bù (-), phép lấy tổng Boole
(+), và phép nhân (). Tập hợp B có 2 phần tử đặc
biệt là 0 và 1 sao cho các đẳng thức sau thỏa mãn:
b.1 = b + 0 = b, bB (luật đồng nhất)
b + 𝑏 = 1; b.𝑏 = 0, bB (luật bù)
(x + y) + z = x + (y + z); (x.y).z = x.(y.z) (kết hợp)
x + y = y + x; x.y = y.x (giao hoán)
x.(y + z) = x.y + x.z; (x.y) + z = (x + z). (y + z)
(phân phối)
Toán Rời Rạc - ĐHSPHN
- Biểu thức Boole & hàm Boole
7
Thứ tự thực hiện của các phép tính của đại số
Boole như sau:
Lấy phần bù > Phép lấy tích > Phép lấy tổng
Khi có các dấu ngoặc, thực hiện theo thứ tự
thông thường là ngoặc trong cùng được thực
hiện trước.
Phép lấy phần bù, phép nhân, và phép tổng
của đại số Boole tương ứng với các toán tử
logic: phần bù, ⋀, và ⋁.
Toán Rời Rạc - ĐHSPHN
- Các hằng đẳng thức của đại số Boole
8
0
1
- Các hằng đẳng thức của đại số Boole
9
Ví dụ: Tính giá trị của x x(1 y )
Ta có:
x x(1 y) x ( x.1 x. y )
x ( x x. y )
( x x) x. y
1 x. y
1
Toán Rời Rạc - ĐHSPHN
- Biểu thức Boole & hàm Boole
10
Một hàm số Boole F với n biến x1, x2, …, xn
được kí hiệu F(x1, x2, …, xn) là một ánh xạ
f : {0, 1}n {0, 1}
Hàm Boole có thể được mô tả bằng lời hoặc
dùng bảng tương tự bảng logic toán.
Ví dụ: hàm F(x,y) sau x y F(x,y)
1 1 1
1 0 0
0 1 0
0 0 0
Toán Rời Rạc - ĐHSPHN
- Biểu thức boole & hàm boole
11
Hai hàm boole F(x1,x2,…,xn) và G(x1,x2,…,xn)
là hai hàm Boole bằng nhau nếu
F(x1, x2, …, xn) = G(x1, x2, …, xn)
cho mọi giá trị của các biến.
Toán Rời Rạc - ĐHSPHN
- 12 Xác định biểu thức Boole của hàm Boole
Toán Rời Rạc - ĐHSPHN
- Xác định biểu thức Boole của hàm Boole
13
Quy tắc 1: Khai triển các bảng thành
các bảng sơ cấp x1 x2 F1(x1,x2)
1 1 1
x1 x2 F(x1,x2) 1 0 0
1 1 1 0 1 0
1 0 0 0 0 0
0 1 0 x1 x2 F2(x1,x2)
0 0 1 1 1 0
1 0 0
0 1 0
𝐹 𝑥1, 𝑥2 = 𝐹1 𝑥1, 𝑥2 + 𝐹2(𝑥1, 𝑥2) 0 0 1
- Xác định biểu thức Boole của hàm Boole
14
Quy tắc 1
Nếu hàm F(x1, x2, …, xn) nhận duy nhất giá trị 1
tại (a1,a2, …,an) và 0 tại mọi giá trị khác của
(x1,x2, …, xn) thì ta có:
F(x1, x2, …, xn) = y1y2…yn
quy ước: yi = xi nếu ai = 1
yi = 𝑥𝑖 nếu ai = 0
Toán Rời Rạc - ĐHSPHN
- Xác định biểu thức Boole của hàm Boole
15
Quy tắc 1 x1 x2 F1(x1,x2)
Ví dụ: 1 1 1
𝐹1 𝑥1, 𝑥2 = 𝑥1𝑥2 1 0 0
0 1 0
0 0 0
𝐹 𝑥1, 𝑥2 = 𝑥1𝑥2+𝑥1𝑥2
x1 x2 F2(x1,x2)
1 1 0
𝐹2 𝑥1, 𝑥2 = 𝑥1𝑥2 1 0 0
0 1 0
0 0 1
Toán Rời Rạc - ĐHSPHN
- Xác định biểu thức Boole của hàm Boole
16
Quy tắc 2: Khai triển các bảng thành
các bảng sơ cấp x1 x2 G1(x1,x2)
1 1 1
x1 x2 F(x1,x2) 1 0 0
1 1 1 0 1 1
1 0 0 =× 0 0 1
0 1 0 x1 x2 G2(x1,x2)
0 0 1 1 1 1
1 0 1
0 1 0
𝐹 𝑥1, 𝑥2 = 𝐺1 𝑥1 , 𝑥2 × 𝐺2(𝑥1, 𝑥2) 0 0 1
- Xác định biểu thức Boole của hàm Boole
17
Quy tắc 2
Nếu hàm F(x1, x2, …, xn) nhận duy nhất giá trị 0
tại (a1,a2, …,an) và 1 tại mọi giá trị khác của
(x1,x2, …, xn) thì ta có:
F(x1, x2, …, xn) = y1 + y2 + …+ yn
quy ước: yi = 𝑥𝑖 nếu ai = 1
yi = xi nếu ai = 0
Toán Rời Rạc - ĐHSPHN
- Xác định biểu thức Boole của hàm Boole
18
Quy tắc 2 x1 x2 G1(x1,x2)
Ví dụ: 1 1 1
𝐺1 𝑥1, 𝑥2 = 𝑥1 + 𝑥2 1 0 0
0 1 1
0 0 1
𝐹 𝑥1, 𝑥2 =
(𝑥1 + 𝑥2)(𝑥1 + 𝑥2) x1 x2 G2(x1,x2)
1 1 1
1 0 1
𝐺2 𝑥1, 𝑥2 = 𝑥1 + 𝑥2
0 1 0
0 0 1
Toán Rời Rạc - ĐHSPHN
- Luyện tập
19
Tìm các hàm chỉ nhận giá trị 1 tại giá trị sau:
a) (x, y, z) = (0, 0, 1)
b) (x, y, z) = (0, 1, 1)
c) (x, y, z) = (0, 1, 0)
Tìm các hàm chỉ nhận giá trị 0 tại giá trị sau:
a) (x, y, z) = (0, 0, 1)
b) (x, y, z) = (0, 1, 1)
c) (x, y, z) = (0, 0, 0)
Toán Rời Rạc - ĐHSPHN
- 20 Sơ đồ mạch logic
Toán Rời Rạc - ĐHSPHN
nguon tai.lieu . vn
