zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

Bài tập ví dụ Toán rời rạc - Chương 7: Hàm Boole

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

Báo xấu

8
lượt xem 1
download

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

Bài tập ví dụ Toán rời rạc - Chương 7: Hàm Boole gồm có các bài tập kèm theo hướng dẫn giải các dạng như: Tìm dạng nối rời chính tắc cho các hàm boole, tìm các công thức đa thức tối tiểu cho các hàm boole f có 4 biến, vẽ mạng các cổng tổng hợp cho các hàm boole. Mời các bạn cùng tham khảo để biết thêm chi tiết!

Chủ đề:

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

Lưu

Nội dung Text: Bài tập ví dụ Toán rời rạc - Chương 7: Hàm Boole

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP.HCM KHOA CÔNG NGHỆ THÔNG TIN BTC ÔN THI HỌC KỲ 1 KHÓA 2016 BÀI TẬP VÍ DỤ TOÁN RỜI RẠC Chương 7: Hàm Boole  Phạm Anh Quốc Cập nhật: 03/02/2017
Khoa Công nghệ thông tin – ĐH KHTN TP.HCM Ôn thi Học kỳ 1 – Khóa 2016 1. Tìm dạng nối rời chính tắc cho các hàm Boole sau đây: a. f ( x, y, z )  x  y  x( y  z ) b. f ( x, y, z, t )  ( xy  zt )( x  z)( xz  yt )( xt  yz ) c. f ( x, y, z, t )  ( x  yz )( y  xz )( z  xy) d. f ( x, y, z , t )  yz  ( z  x)t  ( xy  yz  xt ) xyt e. f ( x, y, z , t )  ( xy  yt ) z  xt ( x  y )( z  t )  ( x  z )( y  t )  ( x  t )( y  z ) Giải /*Dạng nối rời chính tắc là dạng mà các đơn thức của f đều có bậc cao nhất (gọi là các đơn thức tối tiểu), cũng là dạng phức tạp nhất của f*/ a) ĐS: f  xyz  xyz  xyz  xyz  xyz  xyz  xyz  xyz b) f ( x, y, z, t )  ( xy  zt )( x  z)( xz  yt )( xt  yz )  ( xyx  xyz  xzt  zzt )( xzxt  xzyz  ytxt  ytyz )  ( xy  xyz  xzt  zt )( xzt  xyz  xyt  yzt )  xy  xyz  xy Theo luật hấp thu, ta có  , suy ra  xzt  zt  zt f  ( xy  zt )( xzt  xyz  xyt  yzt )  xyzt  xyz  xyt  xyzt  xzt  xyzt  xyzt  yzt  xyzt  xyz  xyt  xzt  yzt  ( xyzt  xyz )  xyt  xzt  yzt  xyz  xyt  xzt  yzt  xyz.1  xy.1.t  x.1.zt  1. yzt /*Nhân thêm 1 vào các đơn thức chưa tối tiểu và dùng luật bù 1 = 𝑥 ∨ 𝑥̅ */  xyz (t  t )  xy ( z  z )t  x( y  y ) zt  ( x  x ) yzt  xyzt  xyzt  xyzt  xyz t  xyzt  xyzt  xyzt  x yzt  xyzt  xyzt  xyz t  xyzt  x yzt (dạng nối rời chính tắc) c) ĐS: f  x yz  xyz d) ĐS: f  xyzt  x yzt  xyzt  x yzt  x yzt  xyzt  xyz t  xyz t e) f ( x, y, z, t )  ( xy  yt ) z  xt ( x  y )( z  t )  ( x  z )( y  t )  ( x  t )( y  z )  ( xyz  yzt )  xt ( xz  xt  yz  yt )  ( xy  xt  yz  zt )  ( xy  xz  yt  zt )  xyz  yzt  ( xt z  xt t  xt yz  xyt t )  xy  xt  yz  zt  yt  xz  xyz  yzt  xt z  x.0  xt yz  xy.0  xy  xt  yz  zt  yt  xz  xyz  yzt  xt z  xt yz  xy  xt  yz  zt  yt  xz  ( xyz  xt yz )  ( yzt  zt )  ( xt z  xz )  xy  xt  yz  yt  xyz  zt  xz  xy  xt  yz  yt  ( xyz  xy )  zt  xz  xt  yz  yt  xy  zt  xz  xt  yz  yt Ta có xy  xy.1.1  xy ( z  z )(t  t )  xy ( zt  zt  z t  z t )  xyzt  xyzt  xyz t  xyz t
Khoa Công nghệ thông tin – ĐH KHTN TP.HCM Ôn thi Học kỳ 1 – Khóa 2016 Tương tự, với các đơn thức khác, ta được f  xyzt  xyzt  xyz t  xyzt  x yzt  xyz t  x yzt  xyzt  xyz t  x yzt  x yz t 2. Tìm các công thức đa thức tối tiểu cho các hàm Boole f có 4 biến rồi viết dạng nối rời chính tắc cho f và f biết rằng S = Kar( f ) = {(1,1), (1,4), (2,2), (2,3), (3,1), (3,2), (3,3), (4,1)} /*Công thức đa thức tối tiểu là dạng đa thức đơn giản nhất của f */ Ta có sơ đồ Karnaugh của hàm f như sau: x x z x x 4 5 5 1 1 z x x t 1 1 x x x t 2 3 2 x 4 3 y y /*Dòng 1 là dòng đầu tiên bên trên, cột 1 là cột đầu tiên bên trái*/ Các tế bào lớn trong S là: T1  yt T2  xzt T3  xyz T4  xyt T5  yzt /*Tế bào lớn là 1 tế bào (hình chữ nhật mở rộng) mà không có tế bào nào khác có thể chứa nó. Ta sẽ xét lần lượt tế bào lớn 16 ô, 8 ô, 4 ô, 2 ô, 1 ô. Lưu ý: bảng mã có thể xem như 1 mặt trụ nên có thể uốn cong theo chiều dọc hoặc chiều ngang để dòng (cột) 4 có thể kề với dòng (cột) 1. Ví dụ bài này ta có tế bào lớn T4 và T5 là do mặt trụ uốn công tạo thành*/ /*Tế bào lớn 4 ô ở 4 góc (1,1),(1,4),(4,1),(4,4) là 1 trong những tế bào lớn dễ bị bỏ quên*/ Ưu tiên 1: (1,4)  T5 , (2,2)  T1 , ta có S \ (T1  T5 )   /*Ưu tiên chọn những ô chỉ thuộc 1 tế bào lớn*/ Ưu tiên 2: chọn (3,1)  S \ (T1  T5 ) và để ý (3,1)  (T2  T3 ) /*chọn cho đến khi thu được phép phủ*/ Do S \ (T1  T5  T3 )   nên S  T1  T5  T3 (1) Ta có S \ (T1  T5  T2 )   nên chọn (4,1)  S \ (T1  T5  T2 ) và để ý (4,1)  (T4  T3 ) Do S \ (T1  T5  T2  T4 )   nên S  T1  T5  T2  T4 (2) Do S \ (T1  T5  T2  T3 )   nên S  T1  T5  T2  T3 (3)
Khoa Công nghệ thông tin – ĐH KHTN TP.HCM Ôn thi Học kỳ 1 – Khóa 2016 Ta có sơ đồ phủ của S là: T1 → T5 → T3 ↓ T2 → T4 ↓ T3 Phép phủ (3) chưa tối tiểu vì dư T2 so với phép phủ (1) nên loại /*Phép phủ tối tiểu là phép phủ không thể loại bỏ tế bào lớn nào (nếu loại bỏ thì không thể phủ hết S)*/ Các phép phủ (1), (2) đều tối tiểu. /*Phép phủ tối tiểu nhưng công thức đa thức tương ứng chưa chắc đã tối tiểu*/ Từ (1) và (2) ta viết các công thức đa thức tương ứng cho f: f ( x, y, z , t )  yt  xyz  yzt (*) f ( x, y, z , t )  yt  xz t  xyt  yzt (**) Loại (**) vì nó phức tạp hơn (*) /*(**) có 4 đơn thức, lớn hơn số đơn thức của (*) và bậc của đơn thức 1,2,3 trong (**) lần lượt bằng bậc của đơn thức tương ứng trong (**) nên (**) phức tạp hơn (*) */ Vậy công thức đa thức tối tiểu của f là f ( x, y, z , t )  yt  xyz  yzt Ta viết dạng nối rời chính tắc của f f ( x, y, z , t )  yt  xyz  yzt  1. y.1.t  xyz .1  1. yzt  ( x  x ) y ( z  z )t  xyz .(t  t )  ( x  x ) yzt  ( xy  x y )( zt  z t )  xyz t  xyz t  xyzt  x yzt  xyzt  xyz t  x yzt  x yz t  xyz t  xyz t  xyzt  x yzt  xyzt  x yzt  xyz t  x yz t  xyz t  xyzt  xyz t  x yzt 3. Vẽ mạng các cổng tổng hợp cho các hàm Boole sau a. f ( x, y, z , t )  xz  yt  yz t  xyt  x yz b. f ( x, y, z, t )  xzt  yzt  xzt  xyt /* Các dây nối giao nhau, nếu có nối với nhau thì chấm lớn tại đó, nếu không nối với nhau thì không chấm gì hết, hoặc vẽ dây này vòng lên dây kia.
Khoa Công nghệ thông tin – ĐH KHTN TP.HCM Ôn thi Học kỳ 1 – Khóa 2016 - Trước và sau mỗi chỗ “chấm lớn” hoặc mỗi cổng NOT, nên có dấu mũi tên chỉ đường chạy của dây*/

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.