Đang chuẩn bị liên kết để tải về tài liệu:
Toán rời rạc part 10

Tham khảo tài liệu 'toán rời rạc part 10', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chương ỉ. Mở đấu 1.4. Biểu diễn tối thiểu của hàm đại số lôgic Biểu diễn một hàm đại só logic f qua một hệ hàm đầy đủ H là không duy nhất. Thí dụ hàm Sheffer khi biểu diễn qua hệ tuyển hội và phủ định có thể có các cách XI y X y V X y V X y X V y . Mỗi một biểu diễn f tương ứng với một cách ghép các thành viên của H mà ta gọi là các yếu tố cơ bản để thu được . Hiển nhiên một vấn đề có ý nghĩa thực tế quan trọng là cần tìm một biểu diên sao cho việc ghép như thế là tốn ít yếu tố cơ bản nhất. Theo một nghĩa nào đó điều này dẫn vế việc tìm một công thức trên hệ H biểu diễn hàm với sô ký hiệu các yếu tố này là ít nhất. Một công thức như vây được gọi là một biểu diễn tối thiểu của hàm trong hệ H. Về nguyên tắc số công thức biểu diễn là hữu hạn nên bằng cách duyệt tất cả các khả năng ta luôn tìm được biểu diễn tối thiểu của . Tuy nhiên số khả năng này là rất lớn và việc duyệt nó đòi hỏi một khôi lượng tính toán khổng lồ do đó trên thực tế khó mà thực hiện được dù rằng ngay cả với những siêu máy tính. Việc xây dựng những thuật toán hữu hiệu tìm biểu diễn tối thiểu của các hàm đại sô ôgic vì thê càng trở nên cấp bách nhưng đổng thời nó cũng là bài toán rất khó. Cho đến nay bài toán này vẫn chưa được giải quyết thoả đáng ngay cả trong một sô trường hợp đơn giản và còn đang được tiếp tục nghiên cứu. Một hệ đầy đủ được nghiên cứu nhiều nhất là hệ tuyển hội và phủ dịnh. Bài toán tìm biểu diễn tối thiểu của các hàm đại sô lôgic trong hệ này đã được nghiên cứu nhiều trong vài chục năm gần đây. Tuy nhiên các kẽ t quả đạt được thường mới chỉ để cập đến một dạng biểu diễn riêng biệt trong hệ đó là dạng tuyển chuẩn tắc của các hàm đại số lôgic mà ta sẽ xét kỹ trong chương sau. 269 Phần 3. Hàm đại số lôgic Bài tập 1. Xét các hàm đại sô lôgic 3 đối số f x y z . Cho tập đặc trưng Tf. Xác định dạng tuyển chuẩn tắc hoàn toàn của a ĩ 0 1 1 1 0 0 1 1 0 b 7 1 0 0 1 0 1 í 1.0 0 1 0 1 1 1 l c Tf I 0 0 0 1 1 1 0 1 1 1 0 0 2. Có bao nhiêu hàm đại sô lôgic 3 đối số mà tập đặc trưng Tj- của nó có