các dạng chuẩn của hàm logic

Dạng tổng chuẩn

Để có được hàm logic dưới dạng chuẩn, ta áp dụng các định lý triển khai của Shanon.

Dạng tổng chuẩn có được từ triển khai theo định lý Shanon thứ nhất:

Tất cả các hàm logic có thể triển khai theo một trong những biến dưới dạng tổng của hai tích như sau:

(1)

Hệ thức (1) có thể được chứng minh rất dễ dàng bằng cách lần lượt cho A bằng 2 giá trị 0 và 1, ta có kết quả là 2 vế của (1) luôn luôn bằng nhau. Thật vậy

Với 2 biến, hàm f(A,B) có thể triển khai theo biến A :

Mỗi hàm trong hai hàm vừa tìm được lại có thể triển khai theo biến B

f(i,j) là giá trị riêng của f(A,B) khi A=i và B=j trong bảng sự thật của hàm.

Với 3 biến, trị riêng của f(A, B, C) là f(i, j, k) khi A=i, B=j và C=k ta được:

Nhắc lại tính chất của các hàm AND và OR: b₁.b₂.... b_n = 1 khi b₁, b₂..., b_n đồng thời bằng 1 và để a₁ + a₂ + ... + a_p = 1 chỉ cần ít nhất một biến a₁, a₂, ..., a_p bằng 1

Trở lại thí dụ trên, biểu thức logic tương ứng với hàng 1 (A=0, B=0, C=1) được viết

đồng thời.

Biểu thức logic tương ứng với hàng 2 là đồng thời

Tương tự, với các hàng 3, 5 và 7 ta có các kết quả

:

Như vậy, trong thí dụ trên

Z = hàng 1 + hàng 2 + hàng 3 + hàng 5 + hàng 7

Tóm lại, từ một hàm cho dưới dạng bảng sự thật, ta có thể viết ngay biểu thức của hàm dưới dạng tổng chuẩn như sau:

- Số số hạng của biểu thức bằng số giá trị 1 của hàm thể hiện trên bảng sự thật

- Mỗi số hạng trong tổng chuẩn là tích của tất cả các biến tương ứng với tổ hợp mà hàm có trị riêng bằng 1, biến được giữ nguyên khi có giá trị 1 và được đảo nếu giá trị của nó = 0.

Dạng tích chuẩn

Đây là dạng của hàm logic có được từ triển khai theo định lý Shanon thứ hai:

Tất cả các hàm logic có thể triển khai theo một trong những biến dưới dạng tích của hai tổng như sau:

(2)

Cách chứng minh định lý Shanon thứ hai cũng giống như đã chứng minh định lý Shanon thứ nhất.

Với hai biến, hàm f(A,B) có thể triển khai theo biến A

Mỗi hàm trong hai hàm vừa tìm được lại có thể triển khai theo biến B

Vậy: Cũng như dạng chuẩn thứ nhất, f(i,j) là giá trị riêng của f(A,B) khi A=i và B=j trong bảng sự thật của hàm.

Với hàm 3 biến:

Số số hạng trong triển khai n biến là 2ⁿ. Mỗi số hạng là tổng (OR) của các biến và trị riêng của hàm.

- Nếu trị riêng bằng 0 số hạng được rút gọn lại chỉ còn các biến (0 là trị trung tính của phép cộng logic)

A + B + C + f(0,0,0) = A + B + C nếu f(0,0,0) = 0

- Nếu trị riêng bằng 1, số hạng triển khai = 1

A + B + + f(0,0,1) = 1 nếu f(0,0,1) = 1

và biến mất trong biểu thức của tích chuẩn.

Lấy lại thí dụ trên:

Các trị riêng của hàm đã nêu ở trên.

- Hàm Z có giá trị riêng f(0,0,0) = 0 tương ứng với các giá trị của biến ở hàng 0 là A=B=C=0 đồng thời, vậy A+B+C là một số hạng trong tích chuẩn.

- Tương tự với các hàng (4) và (6) ta được các tổ hợp

- Với các hàng còn lại (hàng 1, 2, 3, 5, 7), trị riêng của f(A,B,C) = 1 nên không xuất hiện trong triển khai.

Tóm lại, ta có

- Ý nghĩa của định lý thứ hai:

Nhắc lại tính chất của các hàm AND và OR: Để b₁.b₂.... b_n =0 chỉ cần ít nhất một biến trong b₁, b₂,..., b_n =0 và a₁ + a₂ + ... + a_p =0 khi các biến a₁, a₂, ..., a_p đồng thời bằng 0.

Như vậy trong thí dụ trên:

Z = (hàng 0).(hàng 4).(hàng 6)

Thật vậy, ở hàng 0 tất cả biến = 0: A=0, B=0, C=0 đồng thời nên có thể viết (A+B+C) = 0. Tương tự cho hàng (4) và hàng (6).

Tóm lại,

Biểu thức tích chuẩn gồm các thừa số, mỗi thừa số là tổng các biến tương ứng với tổ hợp có giá trị riêng =0, một biến giữ nguyên nếu nó có giá trị 0 và được đảo nếu có giá trị 1. Số thừa số của biểu thức bằng số số 0 của hàm thể hiện trên bảng sự thật.

Đổi từ dạng chuẩn này sang dạng chuẩn