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 khác:

Nhờ định lý De Morgan, hai định lý trên có thể chuyển đổi qua lại.

Trở lại thí dụ trên, thêm cộtZ ngangvào bảng sự thật:

Diễn tả Z ngag theo dạng tổng chuẩn:

Lấy đảo hai vế:

Dùng định lý De Morgan một lần nữa cho từng thừa số trong biểu thức, ta được:

Diễn tả Z ngang theo dạng tích chuẩn:

Lấy đảo hai vế:

Dạng số

Để đơn giản cách viết người ta có thể diễn tả một hàm Tổng chuẩn hay Tích chuẩn bởi tập hợp các số dưới dấu tổng (tổn) hay tích (Π). Mỗi tổ hợp biến được thay bởi một số thập phân tương đương với trị nhị phân của chúng. Khi sử dụng cách viết này trọng lượng các biến phải được chỉ rõ.

Thí dụ :Cho hàm Z xác định như trên, tương ứng với dạng chuẩn thứ nhất, hàm này lấy giá trị của các hàng 1, 2, 3, 5, 7, ta viết

Tương tự, nếu dùng dạng chuẩn thứ hai ta có thể viết Z =f(A,B,C)= Π(0,4,6).

Chú ý: Khi viết các hàm theo dạng số ta phải chỉ rõ trọng số của các bit, thí dụ ta có thể ghi kèm theo hàm Z ở trên 1 trong 3 cách như sau: A=MSB hoặc C=LSB hoặc A=4, B=2, C=1