Bài giảng Toán rời rạc: Chương 5 - TS. Đặng Xuân Thọ

Chia sẻ: Elysale Elysale | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

27
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Toán rời rạc: Chương 5 Đại số Boole và cấu trúc mạch logic cung cấp cho người học những kiến thức như: 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc: Chương 5 - TS. Đặng Xuân Thọ

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, bB (luật đồng nhất)  b + 𝑏 = 1; b.𝑏 = 0, bB (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