3.1. KHÁI NIỆM CO BẤN, CÔNG THỨC VÀ ĐỊNH L Í
3.1.2. Công thức và định ỉi
Vỉ trong đại số logic chỉ có hai hằng 8Ố 0, 1, các biến logic cũng chỉ lấy một trong hai giá trị đđ, và cũng chỉ có ba phép toán logic cơ bản nhất, cho nên cũng chỉ cđ các quan hệ dưới đây ;
Công thức 1 0 . 0 = 0 (3 -1 -8 )
Công thức 1’ 1 + 1 = 1 (3 -1 -9 )
Công thức 2 0 . 1 = 0 (3-1-10)
Công thức 2 ’ 1 + 0 = 1 (3-1-11)
Công thức 3 1 . 1 = 1 (3 -1 -1 2 )
Công thức 3’ 0 + 0 = 0 (3-1-13)
Công thức 4 õ = 1 (3-1-14)
Công thức 4 ’ ĩ = 0 (3-1-15)
Những quan hệ trôn đây giữa hai hằng số làm tiên để của đại số logic. Nghĩa là, chúng là các quy tác phép toán cơ bản đối với tư duy logic.
2) Quan hệ giữa biến số vâ hằng số
Công thức 5 A.1 = A (3-1-16)
Công thức 5’ A + 0 = A (3-1-17)
Công thức 6 A . 0 = 0 (3-1-18)
Công thức 6’ A + 1 = 1 (3-1-19)
Công thức 7 A . Ã = 0 (3 -1-20)
Công thức 7’ A + Ã = 1 (3-1-21)
3) Các định lí tương tự đại số thường Luật giao hoán :
Công thức 8 A . B = B . A (3 -1-22)
Công thức 8’ A + B = B + A (3-1-23)
Luật kết hợp :
Công thức 9 (A . B) . c = A . (B . C) (3-1-24) Công thức 9’ (A + B) + c = A + (B + C) (3 -1-25) Luật phán phối :
Công thức 10 A . ( B + C ) = A . B + A . C (3-1-26) Công thức 10’ A + BC = (A + B) . (A + C) (3 -1 -2 7 ) 4) Các định lí đặc thù chi có trong đại số logic
Luật đồng nhất :
Công thức 11 A . A = A (3-1-28)
Công thức 11’ A + A = A (3 -1-29)
Định lí De Morgan :
Công thức 12 A .B = A + B (3 -1 -3 0 )
Công thức 12’ A + B = A .B (3-1-31)
91
Luật hoàn nguyên :
Công thức 13 Ä = A (3-1-32)
Phương pháp chứng minh các công thức trên là lập bảng tất cả các giá trị ctí thể của các biến và tính tương ứng với vế phải, vế trái riêng rẽ. Nếu đảng thức giữa hai vế tồn tại với tất cả các giá trị có thể thì công thức là đúng. Công thức 5 và công thức 13 rất dễ chứng minh. Dưới đây sẽ chứng minh làm mẫu các cồng thức 1 0’ và công thức 1 2.
Ví dụ 3 -1 -1 . Chứng minh công thức 10’
A + B . c = (A + B) . (A + C)
Giải : lập bảng tất cả các giá trị cđ thể của biến và tính như sau
Bàng 3 - 1 - 1
A B c B .c A + B .c A+B A +C (A +B )
(A +C )
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 ^ 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 0 1 0 1 1 1 1
1 I ‘ 0 0 1 1 1
1 1 1 1 1 1 1 1
Tẵt cả các giá trị của 3 biến A, B, c tạo thành 8 tổ hợp. Bảng chân lí của hàm A + B .c trùng với bảng chân lí của hàm (A + B)(A + C). Vậy công thức A + B .c
= (A + B) (A + C) đã được chứng minh.
Ví dụ 3 -1 -2 : Chứng minh công thức 12
à 7 1 = à + B
Giải : Lập bảng tất cả các giá trị cd thể của biến và tính như sau
Bàng 3 - 1 - 2
A B A.B A .B A B A + B
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0
Tất cả các giá trị của 2 biến A, B tạo t ^ n h 4 tổ hợp. Bảng chân lí của hàm A . B trùng với bảng chân lí của hàm A + B . Vậy công thức 12 đã được chứng minh.
5) 3 quy tắc vầ đẳng thúc a) Quy tắc thay thế
Trong bất kì đẳng thức logic nào, nếu thay một biến nào đ<5 bàng một hàm số thì đẳng thức vẫn thiết lập.
Quy tắc này ctí ứng dụng rất lớn trong biến đổi công thức để tạo ra công thức mới từ một cồng thức đã biết, mở rộng phạm vi ứng dụng của công thức đã biết.
Ví dụ : Công thức đă biết A . B = A + B. Dùng z = A.C thay vào biến A, ta có ; (A . C) . B = Ă T c + B = (Ã + C) + B hay là A . C . B = Ã + C + I
b) Quy tắc tim đảo cùa một hàm số
z là đảo của hàm số z sẽ ctí được từ z bằng cách đổi dấu thành dấu "+" ;
"+" thành dấu ; "0" thành "1", "1" thành "0", biến số thành đảo của biến số đđ, đảo biến số thành nguyên biến số.
Ví dụ : z = A . B + c . D + 0 có hàm đảo tương ứng là Z = (A + B ) . (C + D) . 1.
Z = A + B + C + ĩ) + È cđ hàm đảo là z = A . B . c . D . E
Khi tìm đảo của một hàm số, những gạch ngang nào (biểu thị phép toán đảo) ở trên nhiểu biến thì vẫn giữ nguyên. Cũng cẩn chú_ý _thứ tự ưu tiên xử lí các kí hiệu : dấu mđc, dấu nhâ^, dấu cộng. Ví dụ, z = A . B + c . D, theo thứ tự phép tính phải làm phép nhân A . B và C.D trước, sau mới tôi phép cộng ^ ữ a chúng. Vậy thứ tự xử lí kí hiệu để tìm đảo sẽ dẫn tới kết quả z = (A + B ) . (C + D)
(Nếu viết Z = A + B . C + D , là sai !) c) Quy tắc đối ngẫu
Hàm z và hàm Z’ gọi là đối ngẫu, khi các dấu "+" và các giá trị "1" và "0"
đổi chỗ cho nhau một cách tương ứng.
Ví dụ : z = A.(B + C) Z’ = A + B .c z = A + B -C Z’ = A . (B + C)
Z = A . B + A . ( C + 0 ) Z’ = (A + B ) . (A + c . 1) z = (A + B ) . (A + c . 1) Z’ = A . B + A . (C + 0)
Z = A + B + C Z’ = A . B . C z = A . B . C Z’ = A + B + c
Vì đối ngẫu là tương hỗ, nên nếu một đẳng thức đâ tổn tại đối với biểu thức vế trái và biểu thức vế phải, thì đối ngẫu của vế trái và đối ngẫu của vế phải cũng là một đẳng thức.
93
Quy tắc đối ngẫu ndi trên cho phép từ các công thức 1 + 12 suy ra các công thức 1’ -í- 1 2’ (và ngược lại)
Ví dụ :
Th đâ biết A + B.C.D = (A + B).(A + C).(A + D) Cđ thể suy ra A.(B + c + D) = A.B + A .c + A.D
Cẩn lưu ý thứ tự ưu tiên xử lí kí hiệu khi tim biểu thức đối ngẫu.
Áp dụng quy t lc đối ngẫu cd thể làm cho số công thức cẩn chứng minh giảm đi một nửa. Sau khỉ đã chứng minh bai biểu thức bằng nhau, căn cứ quy tấc đối ngẫu, các đối ngẫu của đẳng thức đã chứng minh cũng phải bàng nhau. Vậy nên, khi giới thiệu những công thúc sau đây, chúng ta sẽ không đưa ra các cống thức dạng đối ngẫu của chúng.
6) Một số công thức ihưbng dùng
Sừ dụng những cồng thức và quy tắc ở phẩn trên, chúng ta cd thể được càng nhiểu công thức mới, dưối đây là các công thức thường dùng
Công thức 1 4 ; A . B + A . B = A (3 -1-33)
Chứng minh :
A . B + A . B = A . ( B + B ) = A
Vậy, nếu biến số B và đảo biến số B cùng_nhân một biến số A thì tổng hai tích đtí bằng A (gộp A.B với A . B được A bỏ B, B)
Công thứe 15 : A + A.B = A (3-1-34)
Chứng minh :
A + A.B = A .(l + B) = A (Theo công thức 6’, 1 + B = 1)
Vậy, nếu trong tổng các tích cđ một số hạng là thừa số trong một số hạng khác, thỉ số hạng ctí nhiều thừa số hơn là thừa (cố thể bỏ đi)
Công thức 1 6 ; A + Ã . B = A + B (3-1-35)
Chứng minh :
Theo công thức 10’, ta cd :
A + Ã . B = (A + Ã ) . (A + B) = 1 . (A + B) = A + B
Vậy, nếu trong tổng các tích, cd đảo của một số hạng là thừa số trong một số hạng khác, thi thừa sổ đó ià thừa (không cấn viết)
Công thức 17 : A . B + Ã . C + B C = A . B + Ã . C (3-1-36) Chứng minh ;
A .B + Ã c + BC = A .B + Ã c + B. C( A + Ã)
= A .B + Ã c + B . C . A + B . C . Ã
= A . B + A . B . C + Ã C + ĂCB
= A . B + Ã c
Hệ q u ả ; A . B + Ã . C + B . C . D = A . B + Ã . C (3-1-37) (lưu ý áp dụng công thức 17 và 15 để chứng minh)
Vậy, nếu trong tổng các tích, xuẵt hiện một biến và đảo của biến đđ trong hai
BỐ hạng khác nhau, các thừa số còa lại trong hai số hạng đtí làm thành thừa số cùa một số hạng thtì ba, thì số hạng thứ ba là thừa (ctí thể bỏ đi).
Công thức 18 : A .B + A .B = A .B + A .B (3 -1 -3 8 ) Chứng minh ;
A .B + Ã .B = A .B + Ã .B = (Ã + B)(A + B)
= (Ã . A + Ã . B) + (B . A + B . B)
= 0 + Ã I + 4 B + 0
Cồng thức 19 : A . B + A . c = A . B + A . c (3 -1 -3 9 ) Chứng minh :
A . B + A , c = A . B . A C = (A + B ) . ( A + C )
= ( Ã. A + ÃC) + ( BA + B ẽ )
= 0 + AC + AB + B C = AC + AB (theo công thức 17)
Vậy công thức 18 là một trường hợp riêng của công thức 19, nếu một hàm ỉà tổng của hai tích, có một biến trong số hạng thổ nhất và đảo của biến đố trong số hạng thứ hai, thì nếu lấy đảo tất cả các íhừa số còn lại, ta sẽ được đảo của hàm đâ cho.
7J Nkững cổng thức vói XOR (phép cộng với sự loại trừ) Định nghĩa phép XOR :
A © B = A . B + Ã . B (3-1-40)
Hàm logic XOR = 1 khi các biến A, B lấy các giá trị khác nhau, và XOR = 0 khi các biến A, B lấy các giá tn bàng nhau.
Tên hàm XOR, vì vậy, mang ý nghỉạ DỊ HOẶC, HOẶC TUYỆT Đ ố l Đảo của XOR là :
A . B = A ® B = A .B + A .B = A .B + A .B (3-1-41) (áp dụng công thức 19)
Hàm A . B = 1 khi các biến A, B lấy các giá trị bàng nhau A . B = 0 khi các biến A, B lấy các giá trị khác nhau A . B cđ tên là hàm TƯƠNG ĐƯƠNG
1. Luật giao hoán A © B = B © A (3 -1 -4 2 )