Toán Rời Rạc(Chương IV: Đại Số Bool) - Toán Học - Nguyễn Huy Long

Đăng nhập / Đăng ký

• ViOLET.VN
• Bài giảng
• Giáo án
• Đề thi & Kiểm tra
• Tư liệu
• E-Learning
• Kỹ năng CNTT
• Trợ giúp

Thư mục

Các ý kiến mới nhất

jjjj...

" Đội Tuyển Bóng Chuyền Nữ – Những Cô Gái Vàng...

MT5 Cd3 NGÀY TẾT TRONG GIA ĐÌNH...

Tuyển tập những bức tranh vẽ chủ đề lễ hội...

Động vật hoang dã ở Châu Phi...

TUẦN 16-BÀI 6 T3 VIẾT TÌM Ý CHO ĐOẠN VĂN...

TUẦN 16-BÀI 6 T2 NÓI VỀ 1 HĐ CỘNG ĐỒNG...

TUẦN 16-BÀI 6 T1 NGÔI NHÀ CHUNG CỦA BUÔN LÀNG...

TUẦN 16-BÀI 5 T4 VIẾT ĐV GT NV PHIM HOẠT...

TUẦN 16-BÀI 5 T3 LUYỆN TẬP VỀ ĐẠI TỪ VÀ...

TUẦN 16-BÀI 5 T1,2 NHỮNG LÁ THƯ...

TUẦN 17-BÀI 51 T2 THỤC HANH VA TRAI NGHIEM...

TUẦN 16-BÀI 51 T1 THỤC HANH VA TRAI NGHIEM...

TUẦN 16-BAI 50 EM LÀM ĐƯỢC NHỮNG GÌ...

Thành viên trực tuyến

122 khách và 63 thành viên

Lê Thị Hoa

Lê Ngọc Thành

Nguyễn Văn Huy

Dương Minh Thanh

Tuong Vi

Chau Tinh Tri

Nguyễn Văn Hùng

Phạm Thị Ngọc Bích

Trần Hoàng Hà

Nguyễn Thị Huyền

lê thị bông

nguyễn phúc vinh

Trần Huỳnh Long

nguyễn nam

Võ Thị Uyên Lan

Phạm Thị Thanh Hương

Lý Thị Vân Dương

Trieu Thi Luong Sau

Phạm Văn Thắng

Nguyễn Văn Ấu

Tìm kiếm theo tiêu đề

Đăng nhập

Tên truy nhập Mật khẩu Ghi nhớ   Quên mật khẩu ĐK thành viên

Tin tức cộng đồng

5 điều đơn giản cha mẹ nên làm mỗi ngày để con hạnh phúc hơn

Tìm kiếm hạnh phúc là một nhu cầu lớn và xuất hiện xuyên suốt cuộc đời mỗi con người. Tác giả người Mỹ Stephanie Harrison đã dành ra hơn 10 năm để nghiên cứu về cảm nhận hạnh phúc, bà đã hệ thống các kiến thức ấy trong cuốn New Happy. Bà Harrison khẳng định có những thói quen đơn...

Hà Nội công bố cấu trúc định dạng đề minh họa 7 môn thi lớp 10 năm 2025

23 triệu học sinh cả nước chính thức bước vào năm học đặc biệt

Xem tiếp

Tin tức thư viện

Chức năng Dừng xem quảng cáo trên violet.vn

Kính chào các thầy, cô! Hiện tại, kinh phí duy trì hệ thống dựa chủ yếu vào việc đặt quảng cáo trên hệ thống. Tuy nhiên, đôi khi có gây một số trở ngại đối với thầy, cô khi truy cập. Vì vậy, để thuận tiện trong việc sử dụng thư viện hệ thống đã cung cấp chức năng...

Khắc phục hiện tượng không xuất hiện menu Bộ công cụ Violet trên PowerPoint và Word

Thử nghiệm Hệ thống Kiểm tra Trực tuyến ViOLET Giai đoạn 1

Xem tiếp

Hướng dẫn sử dụng thư viện

Xác thực Thông tin thành viên trên violet.vn

Sau khi đã đăng ký thành công và trở thành thành viên của Thư viện trực tuyến, nếu bạn muốn tạo trang riêng cho Trường, Phòng Giáo dục, Sở Giáo dục, cho cá nhân mình hay bạn muốn soạn thảo bài giảng điện tử trực tuyến bằng công cụ soạn thảo bài giảng ViOLET, bạn...

Bài 4: Quản lí ngân hàng câu hỏi và sinh đề có điều kiện

Bài 3: Tạo đề thi trắc nghiệm trực tuyến dạng chọn một đáp án đúng

Bài 2: Tạo cây thư mục chứa câu hỏi trắc nghiệm đồng bộ với danh mục SGK

Bài 1: Hướng dẫn tạo đề thi trắc nghiệm trực tuyến

Lấy lại Mật khẩu trên violet.vn

Kích hoạt tài khoản (Xác nhận thông tin liên hệ) trên violet.vn

Đăng ký Thành viên trên Thư viện ViOLET

Tạo website Thư viện Giáo dục trên violet.vn

Hỗ trợ trực tuyến trên violet.vn bằng Phần mềm điều khiển máy tính từ xa TeamViewer

Xem tiếp

Hỗ trợ kĩ thuật

• (024) 62 930 536
• 0919 124 899
• [email protected]

Liên hệ quảng cáo

• (024) 66 745 632
• 096 181 2005
• [email protected]

Tìm kiếm Bài giảng

Đưa bài giảng lên Gốc > THCS (Chương trình cũ) > Toán >

• Toán Rời Rạc(Chương IV: Đại số Bool)
• Cùng tác giả
• Lịch sử tải về

Toán Rời Rạc(Chương IV: Đại số Bool)

• 
• 
• 
• 
• 
• 
• 0 / 0
• 

Nhấn vào đây để tải về Báo tài liệu có sai sót Nhắn tin cho tác giả (Tài liệu chưa được thẩm định) Nguồn: Nguyễn Tất Thành Người gửi: Nguyễn Huy Long Ngày gửi: 20h:10' 01-09-2013 Dung lượng: 2.3 MB Số lượt tải: 270 Số lượt thích: 0 người ĐẠI SỐ BOOLECHƯƠNG 4Nội dung1. Đại số Boole.2. Hàm Boole.3. Các cổng Logic.4. Mạch tối tiểu.5. Phương pháp biểu đồ Karnaugh.1. Đại số BooleĐịnh nghĩa 1:Một đại số Bool là tập hợp A cùng với 2 phép toán  và  thõa mãn các tính chất sau:Tính kết hợpTính giao hoánTính phân bốPhần tử trung hòaPhần tử bù1. Đại số BooleCác tính chất của đại số Bool:i. Tính kết hợp: x, y, z  A, ta có: x  (y  z) = (x  y)  z và x  (y  z) = (x  y)  zii. Tính giao hoán: x, y, z  A, ta có: x  y = y  x và x  y = y  x1. Đại số Booleiii. Tính phân bố: x, y, z  A, ta có: x  (y  z) = (x  y)  (x  z) và x  (y  z) = (x  y)  (x  z)iv. Phần tử trung hòa: Tồn tại 2 phần tử trung hòa 0 và 1 đối với 2 phép toán  và  sao cho x  A ta có: x  0 = x và x  1 = x1. Đại số Boolev. Phần tử bù: x  A, x  A sao cho: x  x = 1 và x  x = 01. Đại số BooleVí dụ: Xét tập hợp A = {0, 1} với 2 phép toán  và  như sau:x  y = x.y (x.y là x nhân với y)x  y = x + y – x.yTa kiểm tra 5 tính chất của đại số Bool:i. Tính giao hoán: x  y = x.y = y.x = y  x  dpcm1. Đại số Booleii. Tính kết hợp: Trường hợp 1: x  (yz) = x.(y.z) = (x.y).z = (xy)  z Trường hợp 2: Dùng bảng chân trị. 1. Đại số Booleiii. Tính phân bố: Dùng bảng chân trị.Xét trường hợp 1 (SV làm trường hợp 2)1. Đại số Booleiv. Phần tử trung hòa: x  0 = x + 0 – x.0 = x và x  1 = x.1 = x  0 và 1 là 2 phần tử trung hòa của Av. Phần tử bù: 0  0 = 0  1 = 0 + 1 – 0.1 = 1 1  1 = 1  0 = 1.0 = 0Kết luận: Tập hợp A = {0, 1} với 2 phép toán được định nghĩa trên là một đại số Bool2. Hàm BooleĐịnh nghĩa:Một hàm Bool n biến là một ánh xạ f: Bn  BTrong đó B = {0, 1}Như vậy, hàm Bool n biến là một hàm số có dạng : f = f(x1, x2, ..., xn); Trong đó mỗi biến x1, x2, ..., xn chỉ nhận hai giá trị 0, 1 và f nhận giá trị trong B = {0, 1}.2. Hàm BooleVì mỗi biến xi chỉ nhận 2 giá trị 0, 1 nên chỉ có 2n trường hợp của bộ biến (x1, x2, ..., xn)Do đó, để mô tả hàm f, ta có thể lập bảng gồm 2n hàng ghi tất cả các giá trị của f tùy theo 2n trường hợp của biến. Ta gọi đây là bảng chân trị của f Tập hợp các hàm Bool n biến được ký hiệu bởi Fn2. Hàm BooleVí dụ: Xét kết qủa f trong việc thông qua một quyết định dựa vào 3 phiếu bầu x, y, z. Mỗi phiếu chỉ lấy một trong hai giá trị: 1 (tán thành) hoặc 0 (bác bỏ).Kết qủa: f là 1 (thông qua quyết định) nếu được đa số phiếu tán thành, f là 0 (không thông qua quyết định) nếu đa số phiếu bác bỏ.Khi đó f là hàm Bool theo 3 biến x, y, z có bảng chân trị như sau:2. Hàm BooleCác phép toán trên hàm BoolPhép cộng: Ký hiệu: Cho 2 hàm Bool f, g  Fn, ta định nghĩa tổng Bool của f và g như sau: f  g = f + g – fg Phát biểu khác: x = (x1, x2, ..., xn)  Bn (f  g)(x) = f(x) + g(x) – f(x)g(x)Hiển nhiên: (f  g)  FnCác phép toán trên hàm BoolPhép nhân: Ký hiệu: Cho 2 hàm Bool f, g  Fn, ta định nghĩa tích Bool của f và g như sau: f  g = fgPhát biểu khác: x = (x1, x2, ..., xn)  Bn (f  g)(x) = f(x)g(x)Ta thường viết fg thay cho f  gHiển nhiên: (f  g)  FnCác phép toán trên hàm BoolPhép lấy hàm bù:Cho f  Fn, ta định nghĩa hàm bù của f như sau:Dạng nối rời chính tắc của hàm BoolCho các hàm Bool: x1, x2, ..., xn  Fn Ta có các định nghĩa như sau:Từ đơn: là mỗi hàm bool xi hay xi Đơn thức: là tích khác không của một số hữu hạn từ đơnTừ tối tiểu: là tích khác không của đúng n từ đơnDạng nối rời chính tắc của hàm BoolCông thức đa thức: là công thức biểu diễn hàm Bool thành tổng của các đơn thứcDạng nối rời chính tắc: là công thức biểu diễn hàm Bool thành tổng của các từ tối tiểuDạng nối rời chính tắc của hàm BoolVí dụ:Là công thức đa thức3. Các cổng LogicMạng logic:Xem hình ảnh tổng quát của một mạng logic sau:Trong đó:Ta nói mạng logic trên tổng hợp hay biểu diễn hàm Bool f3. Các cổng LogicCổng NOT: Ký hiệu cổng:Bảng chân trị:Biểu diễn hàm: Nếu đưa mức HIGH vào ngõ vào của cổng, ngõ ra sẽ là mức LOW và ngược lại3. Các cổng LogicCổng AND:Ký hiệu cổng: Bảng chân trị:Biểu diễn hàm:F(x, y) = xyCổng AND có ít nhất 2 ngõ vào. Ngõ ra là 1 khi tất cả các ngõ vào là 1. Ngược lại là 03. Các cổng LogicCổng OR:Ký hiệu cổng: Bảng chân trị: Biểu diễn hàm:F(x, y) = x  yCổng OR có ít nhất là 2 ngõ vào. Ngõ ra là 1, nếu có một ngõ vào là 1, Ngược lại là 03. Các cổng LogicCổng NAND:Ký hiệu cổng: Cổng NAND là kết hợp 2 cổngAND và NOTBảng chân trị:Là cổng bù của AND Có ngõ ra là ngược lại với cổng AND3. Các cổng LogicCổng NOR:Ký hiệu cổng: Cổng NOR là kết hợp 2 cổngOR và NOTBảng chân trị: Là cổng bù của OR. Có ngõ ra ngược với cổng OR4. Mạch tối tiểuMạch tối tiểu là mạng các cổng logic biểu diễn cho một đa thức tối tiểu.Ví dụ: Giả sử ta có các đa thức tối tiểu sau:Hãy vẽ mạch tối tiểu cho 2 đa thức tối tiểu trên.4. Mạch tối tiểuVí dụ một mạch logic của 1 hàm f5. Phương pháp biểu đồ KarnaughCông thức đa thức tối tiểu:Cho 2 công thức đa thức của 1 hàm bool:f = f1 v f2 v ... v fk vàg = g1 v g2 v ... v ghTa nói rằng công thức f đơn giản hơn công thức g nếu số từ đơn fi không nhiều hơn số từ đơn gj. Nếu f đơn giản hơn g và g đơn giản hơn f thì ta nói f và g đơn giản như nhau5. Phương pháp biểu đồ KarnaughCông thức đa thức tối tiểu (tt):Công thức đa thức tối tiểu của một hàm Bool f là một công thức đa thức của f trong đó không có công thức đa thức nào của f thực sự đơn giản hơn nó.Một hàm Bool f có thể có nhiều công thức đa thức tối tiểu5. Phương pháp biểu đồ KarnaughXét hàm Bool f theo n biến x1, x2, ..., xn với n = 3 hoặc 4Trường hợp n = 3:f là hàm Bool theo 3 biến x, y, z. Khi đó bảng chân trị của f gồm 23 = 8 hàng.5. Phương pháp biểu đồ KarnaughThay cho bảng chân trị của f, ta vẽ một bảng chữ nhật gồm 8 ô, tương ứng với 8 hàng của bảng chân trị, được đánh dấu như sau:Lưu ý: thứ tự xyz5. Phương pháp biểu đồ KarnaughQui ước trong bảng chữ nhật:Khi một ô nằm trong dãy được đánh dấu bởi x thì tại đó x = 1, bởi x thì tại đó x = 0, Tương tự cho y và z.Các ô tại đó f bằng 1 sẽ được đánh dấu (tô đậm hoặc gạch chéo). Tập các ô được đánh dấu được gọi là biểu đồ Karnaugh của f, ký hiệu là kar(f).5. Phương pháp biểu đồ KarnaughTrường hợp n = 4:f là hàm Bool theo 4 biến x, y, z, t. Khi đó bảng chân trị của f gồm 16 hàng. Thay cho bảng chân trị của f, ta vẽ một bảng chữ nhật gồm 16 ô, tương ứng với 16 hàng của bảng chân trị, được đánh dấu như sau:Lưu ý: thứ tự xyzt5. Phương pháp biểu đồ KarnaughQui ước trong bảng chữ nhật: Tương tự qui ước với hàm Bool 3 biến xyz5. Phương pháp biểu đồ KarnaughTrong cả hai trường hợp, hai ô được gọi là kề nhau (theo nghĩa rộng), nếu chúng là hai ô liền nhau hoặc chúng là ô đầu, ô cuối của cùng một hàng (cột) nào đó. Nhận xét rằng, do cách đánh dấu như trên, hai ô kề nhau chỉ lệch nhau ở một biến duy nhất.5. Phương pháp biểu đồ KarnaughQui định tên ô: có 2 cách:Yêu cầu: Nên sử dụng cách 1.Cách 1:Cách 2:5. Phương pháp biểu đồ KarnaughĐịnh lý:Cho f, g là các hàm Bool theo n biến x1, x2, ..., xn. Khi đó:kar(fg) = kar(f)  kar(g)kar(f v g) = kar(f)  kar(g)kar(f) gồm đúng một ô khi và chỉ khi f là một từ tối tiểu5. Phương pháp biểu đồ KarnaughTế bào:Tế bào là hình chữ nhật gồm 2k ô; Với k = 1..n-1, n là số biến của hàm Bool fNếu T là một tế bào thì T là biểu đồ karnaugh của một đơn thức duy nhấtCách xác định tế bào của 1 đơn thức:Lần lượt chiếu đơn thức lên các cạnh của nó. Nếu toàn bộ hình chiếu nằm trọn trong một tế bào thì thì đó chính là tế bào cần tìm 5. Phương pháp biểu đồ KarnaughVí dụ 1. Xét các hàm Bool theo 4 biến x, y, z, t.Biểu đồ karnaugh của đơn thức là:5. Phương pháp biểu đồ KarnaughVí dụ 2.Xét các hàm Bool theo 4 biến x, y, z, t.Biểu đồ karnaugh của đơn thức là:5. Phương pháp biểu đồ KarnaughVí dụ 3.Xét các hàm Bool theo 4 biến x, y, z, t.Biểu đồ karnaugh của đơn thức là:5. Phương pháp biểu đồ KarnaughVí dụ 4.Xét các hàm Bool theo 4 biến x, y, z, t.Biểu đồ karnaugh của đơn thức là:5. Phương pháp biểu đồ KarnaughVí dụ 5.Xét các hàm Bool theo 4 biến x, y, z, tBiểu đồ karnaugh sau đây là của đơn thức nào?5. Phương pháp biểu đồ KarnaughVí dụ 6.Xét các hàm Bool theo 4 biến x, y, z, tCác biểu đồ karnaugh sau đây là của đơn thức nào?xx zy z t5. Phương pháp biểu đồ KarnaughTế bào lớn:Cho hàm Bool f. Ta nói T là một tế bào lớn của kar(f) nếu T thoả 2 tính chất sau:T là một tế bào và T  kar(f)Không tồn tại tế bào T’ nào thỏa: T’  T và T  T’  kar(f)Thuật toán tìm đa thức tối tiểuBước 1: Vẽ biểu đồ karnaugh của f.Bước 2: Xác định tất cả các tế bào lớn của kar(f).Bước 3: Xác định các tế bào lớn T nhất thiết phải chọn.Ta nhất thiết phải chọn tế bào lớn T khi tồn tại một ô của kar(f) mà ô này chỉ nằm trong tế bào lớn T và không nằm trong bất kỳ tế bào lớn nào khác.Thuật toán tìm đa thức tối tiểuBước 4: Xác định các phủ tối tiểu gồm các tế bào lớn+ Nếu các tế bào lớn chọn được ở bước 3 đã phủ được kar(f) thì ta có duy nhất một phủ tối tiểu gồm các tế bào lớn của kar(f).+ Nếu các tế bào lớn chọn được ở bước 3 chưa phủ được kar(f) thì:- Xét một ô chưa bị phủ, sẽ có ít nhất hai tế bào lớn chứa ô này, ta chọn một trong các tế bào lớn này. Thuật toán tìm đa thức tối tiểuBước 4 (tt):- Cứ tiếp tục như thế ta sẽ tìm được tất cả các phủ gồm các tế bào lớn của kar(f). - Loại bỏ các phủ không tối tiểu, ta tìm được tất cả các phủ tối tiểu gồm các tế bào lớn của kar(f)Thuật toán tìm đa thức tối tiểuBước 5: Xác định các công thức đa thức tối tiểu của f.Từ các phủ tối tiểu gồm các tế bào lớn của kar(f) tìm được ở bước 4, ta xác định được các công thức đa thức tương ứng của f. Loại bỏ các công thức đa thức mà có một công thức đa thức nào đó thực sự đơn giản hơn chúng.Các công thức đa thức còn lại chính là các công thức đa thức tối tiểu của f.Thuật toán tìm đa thức tối tiểuVí dụ 1: Tìm tất cả các công thức đa thức tối tiểu của hàm Bool:f(x,y,z,t) = Cách làm:Thuật toán tìm đa thức tối tiểuThuật toán tìm đa thức tối tiểuBước 1: Vẽ kar(f)Bước 2: Kar(f) có các tế bào lớn như sau:xyzThuật toán tìm đa thức tối tiểuBước 3: Xác định các tế bào lớn nhất thiết phải chọnTa có thể đánh số ô để dể theo dõi:Thuật toán tìm đa thức tối tiểuÔ 1,4,7,8,9,10 nằm trong một tế bào lớn duy nhất là x  Ta chọn x.Ô 3,6 nằm trong một tế bào lớn duy nhất là yz  Ta chọn yzxyzThuật toán tìm đa thức tối tiểuBước 4: Xác định các phủ tối tiểu gồm các tế bào lớnTa được duy nhất một phủ tối tiểu gồm các tế bào lớn của kar(f): x v yzxyzx v yzThuật toán tìm đa thức tối tiểuBước 5: Xác định các công thức đa thức tối tiểu của f.Ứng với phủ tối tiểu gồm các tế bào lớn tìm được ở bước 4, ta tìm được duy nhất một công thức đa thức tối tiểu của f là5. Phương pháp biểu đồ KarnaughVí dụ 7: Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh như sau:5. Phương pháp biểu đồ KarnaughBước 1: Biểu đồ Karnaugh của f có 2 tế bào lớn:Bước 2: Ô (3,1) nằm duy nhất trongÔ (1,1) nằm duy nhất trongHai tế bào lớn này đã phủ kín kar(f) nên ta qua thẳng bước 4. 5. Phương pháp biểu đồ KarnaughBước 4: Ta chỉ có duy nhất 1 phép phủ ứng với công thức đa thức tối tiểu duy nhất của f : f = 5. Phương pháp biểu đồ KarnaughVí dụ 8: Xét hàm Bool f theo 4 biến x, y, z, t có biểu đồ karnaugh như sau:5. Phương pháp biểu đồ KarnaughBước 1: Biểu đồ kar(f) có 4 tế bào lớn:5. Phương pháp biểu đồ KarnaughBước 2: Ô (2,4) nằm trong tế bào lớn duy nhấtÔ (4,2) nằm trong tế bào lớn duy nhấtChọn (gạch chéo hoặc tô) 2 tế bào lớn này, ta được sơ đồ sau:Còn lại ô (3,3) chưa được phủ, nằm trong 2 tế bào lớn nên ta qua bước 3 Ô (3,3)5. Phương pháp biểu đồ KarnaughBước 3: Ô (3,3) nằm trong 2 tế bào lớn là và .Chọn tùy ý một trong 2 tế bào trên ta đều phủ kín kar(f).Bước 4: Ta được phép phủ tối tiểu tương ứng với 2 công thức đa thức:f = f = Bước 5: Cả 2 công thức này đều đơn giản như nhau nên ta được 2 công thức đa thức tối tiểu. 5. Phương pháp biểu đồ KarnaughVí dụ 9. Tìm các tết bào lớn của hàm Bool f có biểu đồ karnaugh như sau:5. Phương pháp biểu đồ KarnaughKar(f) có 6 tế bào lớn:5. Phương pháp biểu đồ Karnaugh5. Phương pháp biểu đồ Karnaugh5. Phương pháp biểu đồ KarnaughBài tập 1: Tìm CTĐTTT của hàm f với biểu đồ kar(f) sau:Bài tập 2: Tìm CTĐTTT của hàm f với biểu đồ kar(f) sau:ENDAdd your company slogan   ↓ ↓ Gửi ý kiến ©2008-2017 Thư viện trực tuyến ViOLET Đơn vị chủ quản: Công ty Cổ phần Mạng giáo dục Bạch Kim - ĐT: 04.66745632 Giấy phép mạng xã hội số 16/GXN-TTĐT cấp ngày 13 tháng 2 năm 2012