Đại số Boolean: lịch sử, định lý và định đề, ví dụ
Đại số Boolean hoặc đại số Boolean là ký hiệu đại số được sử dụng để điều trị các biến nhị phân. Nó bao gồm các nghiên cứu về bất kỳ biến nào chỉ có 2 kết quả có thể, bổ sung và loại trừ lẫn nhau. Ví dụ, các biến có khả năng duy nhất là đúng hoặc sai, đúng hoặc không chính xác, bật hoặc tắt là cơ sở của nghiên cứu về đại số Boolean.
Đại số Boolean tạo thành nền tảng của thiết bị điện tử kỹ thuật số, khiến nó khá hiện diện trong thời hiện đại. Nó bị chi phối bởi khái niệm cổng logic, trong đó các hoạt động được biết đến trong đại số truyền thống bị ảnh hưởng đáng kể.
Lịch sử
Đại số Boolean được giới thiệu vào năm 1854 bởi nhà toán học người Anh George Boole (1815 - 1864), một học giả tự học thời bấy giờ. Mối quan tâm của anh nảy sinh từ một cuộc tranh cãi giữa Augustus De Morgan và William Hamilton, về các thông số xác định hệ thống logic này.
George Boole lập luận rằng định nghĩa của các giá trị số 0 và 1 tương ứng, trong lĩnh vực logic, với cách giải thích của Không có gì và Vũ trụ tương ứng.
Ý định của George Boole là xác định, thông qua các thuộc tính của đại số, các biểu thức của logic mệnh đề cần thiết để xử lý các biến của loại nhị phân.
Năm 1854, các phần quan trọng nhất của đại số Boolean được xuất bản trong cuốn sách " Một cuộc điều tra về các định luật về suy nghĩ dựa trên các lý thuyết toán học về logic và xác suất".
Tiêu đề gây tò mò này sẽ được tóm tắt dưới đây là " Quy luật của suy nghĩ" ("Quy luật của suy nghĩ"). Tiêu đề đã nhảy lên danh tiếng do sự chú ý ngay lập tức mà nó đã có một phần của cộng đồng toán học thời đó.
Năm 1948, Claude Shannon đã áp dụng nó trong thiết kế các mạch chuyển mạch điện có thể hàn được. Điều này phục vụ như là một giới thiệu về ứng dụng của đại số Boolean trong toàn bộ sơ đồ điện tử-kỹ thuật số.
Cấu trúc
Các giá trị cơ bản trong loại đại số này là 0 và 1, tương ứng với FALSE và TRUE. Các hoạt động cơ bản trong đại số Boolean là 3:
- Hoạt động VÀ hoặc kết hợp. Đại diện bởi một khoảng thời gian (.). Đồng nghĩa cho sản phẩm
- HOẶC hoạt động hoặc phân ly. Đại diện bởi một chữ thập (+). Đồng nghĩa của tổng.
- Hoạt động KHÔNG hoặc phủ định. Đại diện bởi tiền tố KHÔNG (KHÔNG A). Nó cũng được gọi là một bổ sung.
Nếu một tập hợp A xác định 2 định luật về thành phần bên trong được ký hiệu là sản phẩm và tổng (. +), Người ta nói rằng bộ ba (A. +) là đại số Boolean khi và chỉ khi bộ ba đáp ứng điều kiện là một mặt kẻ ô phân phối
Để xác định mạng phân phối, các điều kiện phân phối giữa các hoạt động đã cho phải được đáp ứng:
. là phân phối đối với tổng + a. (b + c) = (a. b) + (a. c)
+ là phân phối đối với sản phẩm. a + (b. c) = (a + b). (a + c)
Các phần tử tạo nên tập A phải là nhị phân, do đó có các giá trị vũ trụ hoặc trống.
Ứng dụng
Kịch bản ứng dụng chính của nó là nhánh kỹ thuật số, nơi nó phục vụ để cấu trúc các mạch tạo nên các hoạt động logic liên quan. Nghệ thuật đơn giản của các mạch theo hướng tối ưu hóa các quy trình là kết quả của ứng dụng và thực hành đúng của đại số Boolean.
Từ sự phát triển của bảng điện, thông qua truyền dữ liệu, đến lập trình bằng các ngôn ngữ khác nhau, chúng ta có thể thường xuyên tìm thấy đại số Boolean trong tất cả các loại ứng dụng kỹ thuật số.
Các biến Boolean rất phổ biến trong cấu trúc lập trình. Tùy thuộc vào ngôn ngữ lập trình được sử dụng, sẽ có các hoạt động mã cấu trúc sử dụng các biến này. Các điều kiện và đối số của mỗi ngôn ngữ hỗ trợ các biến Boolean để xác định các quy trình.
Định đề
Có những định lý chi phối các định luật logic cấu trúc của đại số Boolean. Tương tự, có các định đề để biết các kết quả có thể có trong các tổ hợp biến nhị phân khác nhau, tùy thuộc vào thao tác được thực hiện.
Tổng (+)
Toán tử OR có phần tử logic là union (U) được xác định cho các biến nhị phân như sau:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Sản phẩm (.)
Toán tử AND có phần tử logic là giao điểm (∩) được xác định cho các biến nhị phân như sau:
0 0 = 0
0 1 = 0
1 0 = 0
1 1 = 1
Đối lập (KHÔNG)
Toán tử NOT có phần tử logic là phần bù (X) 'được xác định cho các biến nhị phân như sau:
KHÔNG 0 = 1
KHÔNG 1 = 0
Nhiều định đề khác với tương đương của chúng trong đại số thông thường. Điều này là do miền của các biến. Ví dụ, việc thêm các phần tử vũ trụ trong đại số Boolean (1 + 1) không thể mang lại kết quả thông thường là 2, vì nó không thuộc về các phần tử của tập nhị phân.
Định lý
Quy tắc không và thống nhất
Bất kỳ hoạt động đơn giản nào liên quan đến một yếu tố với các biến nhị phân được xác định:
0 + A = A
1 + A = 1
0 A = 0
1 A = A
Quyền hạn tương đương hoặc idempotencia
Hoạt động giữa các biến bằng nhau được định nghĩa là:
A + A = A
A. A = A
Bổ sung
Mọi hoạt động giữa một biến và phần bù của nó được định nghĩa là:
A + KHÔNG A = 1
A. KHÔNG A = 0
Từ chối hoặc từ chối kép
Bất kỳ phủ định kép sẽ được coi là biến tự nhiên.
KHÔNG (KHÔNG A) = A
Giao hoán
A + B = B + A; Giao hoán của tổng.
A. B = B A; Tính giao hoán của sản phẩm.
Liên kết
A + (B + C) = (A + B) + C = A + B + C; Tính kết hợp của tổng.
A. (B. C) = (A. B). C = A B. C; Sản phẩm kết hợp.
Phân phối
A + (B. C) = (A + B). (A + C); Phân phối của tổng số đối với sản phẩm.
A. (B + C) = (A. B) + (A + C); Phân phối của sản phẩm đối với tổng.
Định luật hấp thụ
Có nhiều định luật hấp thụ giữa nhiều
A. (A + B) = A
A. (KHÔNG phải A + B) = A. B
KHÔNG A (A + B) = KHÔNG A. B
(A + B). (A + KHÔNG B) = A
A + A. B = A
A + KHÔNG A. B = A + B
KHÔNG phải là A + A. B = KHÔNG A + B
A. B + A. KHÔNG B = A
Định lý của Morgan
Chúng là các định luật biến đổi, xử lý các cặp biến tương tác giữa các hoạt động được xác định của đại số Boolean (+.).
KHÔNG (A. B) = KHÔNG A + KHÔNG B
KHÔNG (A + B) = KHÔNG A. KHÔNG B
A + B = KHÔNG (KHÔNG A + KHÔNG B)
A. B = KHÔNG (KHÔNG A. KHÔNG B)
Nhị nguyên
Tất cả các định đề và định lý đều có khoa đối ngẫu. Điều này ngụ ý rằng khi trao đổi các biến và hoạt động, đề xuất kết quả được xác minh. Điều đó có nghĩa là, khi trao đổi 0 cho 1 và AND cho OR hoặc ngược lại; một biểu thức được tạo ra cũng sẽ hoàn toàn hợp lệ.
Ví dụ: nếu bạn lấy định đề
1 0 = 0
Và tính hai mặt được áp dụng
0 + 1 = 1
Một định đề hoàn toàn hợp lệ khác có được.
Bản đồ Karnaugh
Bản đồ Karnaugh là một sơ đồ được sử dụng trong đại số Boolean để đơn giản hóa các hàm logic. Nó bao gồm một sự sắp xếp hai chiều tương tự như các bảng chân lý của logic mệnh đề. Dữ liệu từ các bảng chân lý có thể được thu thập trực tiếp trên bản đồ Karnaugh.
Bản đồ Karnaugh có thể chứa các quy trình lên tới 6 biến. Đối với các hàm có số lượng biến lớn hơn, nên sử dụng phần mềm để đơn giản hóa quy trình.
Được đề xuất vào năm 1953 bởi Maurice Karnaugh, nó được thành lập như một công cụ cố định trong lĩnh vực đại số Boolean, bởi vì việc triển khai nó đồng bộ hóa tiềm năng của con người với nhu cầu đơn giản hóa các biểu thức Boolean, một khía cạnh quan trọng trong sự trôi chảy của các quy trình kỹ thuật số.
Ví dụ
Đại số Boolean được sử dụng để giảm các cổng logic trong mạch, trong đó ưu tiên là đưa độ phức tạp hoặc mức độ của mạch đến biểu thức tối thiểu có thể có của nó. Điều này là do sự chậm trễ tính toán mà mỗi cửa giả định.
Trong ví dụ sau, chúng ta sẽ quan sát sự đơn giản hóa của một biểu thức logic thành biểu thức tối thiểu của nó, sử dụng các định lý và định đề của đại số Boolean.
KHÔNG (AB + A + B). KHÔNG (A + KHÔNG B)
KHÔNG [A (B + 1) + B]. KHÔNG (A + KHÔNG B); Bao thanh toán A với yếu tố chung.
KHÔNG [A (1) + B]. KHÔNG (A + KHÔNG B); Theo định lý A + 1 = 1.
KHÔNG (A + B). KHÔNG (A + KHÔNG B); theo định lý A. 1 = A
(KHÔNG A. KHÔNG B). [KHÔNG phải là A. KHÔNG (KHÔNG B)];
Theo định lý của Morgan KHÔNG (A + B) = KHÔNG A. KHÔNG B
(KHÔNG A. KHÔNG B). (KHÔNG A. B); Theo định lý phủ định kép KHÔNG (KHÔNG A) = A
KHÔNG phải là A. KHÔNG B. KHÔNG phải là A. B; Phân nhóm đại số
KHÔNG phải là A. KHÔNG phải là A. KHÔNG B. B; Giao hoán của sản phẩm A. B = B Một
KHÔNG phải là A. KHÔNG B. B; Theo định lý A. A = A
KHÔNG phải là A. 0; Theo định lý A. KHÔNG A = 0
0; Theo định lý A. 0 = 0
A. B. C + KHÔNG A + A. KHÔNG B. C
A. C. (B + KHÔNG B) + KHÔNG A; Bao thanh toán (A. C) với yếu tố chung.
A. C. (1) + KHÔNG A; Theo định lý A + KHÔNG A = 1
A. C + KHÔNG A; Theo quy tắc quy tắc bằng không và đơn vị 1. A = A
KHÔNG A + C ; Theo luật Morgan A + KHÔNG A. B = A + B
Đối với giải pháp này, luật của Morgan cần được mở rộng để xác định:
KHÔNG (KHÔNG A). C + KHÔNG A = KHÔNG A + C
Bởi vì KHÔNG (KHÔNG A) = A bằng cách xâm nhập.
Đơn giản hóa chức năng logic
KHÔNG phải là A. KHÔNG B. KHÔNG C + KHÔNG A. KHÔNG B. C + KHÔNG A. KHÔNG C đến biểu thức tối thiểu của nó
KHÔNG phải là A. KHÔNG B. (KHÔNG C + C) + KHÔNG A. KHÔNG C; Bao thanh toán (KHÔNG A. KHÔNG B) với yếu tố chung
KHÔNG phải là A. KHÔNG B. (1) + KHÔNG A. KHÔNG C; Theo định lý A + KHÔNG A = 1
(KHÔNG A. KHÔNG B) + (KHÔNG A. KHÔNG C); Theo quy tắc quy tắc bằng không và đơn vị 1. A = A
KHÔNG A (KHÔNG B + KHÔNG C); Bao thanh toán KHÔNG A với yếu tố chung
KHÔNG phải là A. KHÔNG (B. C); Theo luật của Morgan KHÔNG (A. B) = KHÔNG A + KHÔNG B
KHÔNG [A + (B. C)] Theo luật của Morgan KHÔNG (A. B) = KHÔNG A + KHÔNG B
Bất kỳ trong số 4 tùy chọn in đậm thể hiện một giải pháp khả thi để giảm mức độ của mạch
Đơn giản hóa hàm logic thành biểu thức tối thiểu của nó
(A) KHÔNG B, C + A, KHÔNG B, B, D + KHÔNG A, KHÔNG B). C
(A, KHÔNG B, C + A, 0, D + KHÔNG, KHÔNG B). C; Theo định lý A. KHÔNG A = 0
(A, KHÔNG B, C + 0 + KHÔNG A, KHÔNG B). C; Theo định lý A. 0 = 0
(A, KHÔNG B, C + KHÔNG A, KHÔNG B). C; Theo định lý A + 0 = A
A. KHÔNG B. C. C + KHÔNG A. KHÔNG B. C; Theo phân phối của sản phẩm liên quan đến tổng
A. KHÔNG B. C + KHÔNG A. KHÔNG B. C; Theo định lý A. A = A
KHÔNG B. C (A + KHÔNG A) ; Bao thanh toán (KHÔNG B. C) với yếu tố chung
KHÔNG B. C (1); Theo định lý A + KHÔNG A = 1
KHÔNG B. C; Theo quy tắc quy tắc bằng không và đơn vị 1. A = A
