ĐẠI SỐ BOOLEAN: LỊCH SỬ, ĐỊNH LÝ VÀ ĐỊNH ĐỀ, VÍ DỤ - TOÁN HỌC - 2025

Các đại số Boolean hoặc đại số Boolean là ký hiệu đại 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ể xảy ra, 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 sai, bật hoặc tắt là cơ sở của nghiên cứu đại số Boolean.

Đại số Boolean tạo thành nền tảng của điện tử kỹ thuật số, khiến nó trở nên phổ biến ngày nay. Nó bị chi phối bởi khái niệm cổng logic, nơi các phép toán đã biết trong đại số truyền thống bị ảnh hưởng đáng kể.

Nguồn: pexels.com

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 ông nảy sinh từ một cuộc tranh cãi hiện có giữa Augustus De Morgan và William Hamilton, về các tham 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, trong lĩnh vực logic, tương ứng với cách giải thích Không có gì và Vũ trụ.

Mục đích 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 kiểu nhị phân.

Năm 1854, 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 quy luật tư duy 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 sau này là "Các quy luật của tư tưởng" ("Các quy luật của tư tưởng"). Tiêu đề đã trở nên nổi tiếng do sự chú ý ngay lập tức mà nó nhận được từ cộng đồng toán học thời đó.

Năm 1948, Claude Shannon đã áp dụng nó vào việc thiết kế các mạch chuyển đổi điện có thể phân tích được. Đây là phần 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ố.

Kết cấu

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 phép toán cơ bản trong đại số Boolean là 3:

- Hoạt động AND hoặc kết hợp. Được thể hiện bằng dấu chấm (.). Từ đồng nghĩa của sản phẩm.

- HOẶC hoạt động hoặc kết nối. Được biểu diễn bằng dấu thập (+). Từ đồng nghĩa của tổng.

- KHÔNG hoạt động hoặc phủ định. Được biểu diễn bằng tiền tố NOT (KHÔNG PHẢI A). Nó còn được gọi là chất bổ sung.

Nếu trong một tập hợp A có 2 luật thành phần bên trong được định nghĩa là tích và tổng (. +), Thì bộ ba (A. +) được cho là đại số Boolean nếu và chỉ khi bộ ba nói trên đáp ứng điều kiện là mạng tinh thể phân phối.

Để xác định một mạng tinh thể phân phối, các điều kiện phân phối phải được đáp ứng giữa các hoạt động đã cho:

. 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à hệ nhị phân, do đó có giá trị vũ trụ hoặc giá trị rỗng.

Các ứ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 hóa mạch có lợi cho việc tối ưu hóa các quy trình là kết quả của việc áp dụng đúng và thực hành đại số Boolean.

Từ việc chế tạo bảng điện, truyền dữ liệu, cho đến lập trình bằng các ngôn ngữ khác nhau, chúng ta thường có thể 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 của 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 cấu trúc trong mã 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ữ thừa nhận các biến Boolean để xác định các quy trình.

Định đề

Có những định lý chi phối các luật logic cấu trúc của đại số Boolean. Theo cách tương tự, có các định đề để biết kết quả có thể có trong các kết hợp khác nhau của các biến nhị phân, tùy thuộc vào hoạt động được thực hiện.

Tổng (+)

Toán tử OR có phần tử logic là liên hợp (U) được định nghĩa 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 (∩) được định nghĩa cho các biến nhị phân như sau:

0. 0 = 0

0. 1 = 0

một . 0 = 0

một . 1 = 1

Ngược lại (KHÔNG)

Toán tử NOT có phần tử logic là phần bổ sung (X) 'được định nghĩa 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 các định đề 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ụ, phép cộng các phần tử vũ trụ trong đại số Boolean (1 + 1) không thể mang lại kết quả quy ước 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 phần tử với các biến nhị phân, được định nghĩa:

0 + A = A

1 + A = 1

0. A = 0

một . A = A

Quyền hạn ngang nhau hoặc tính vô hiệu

Các phép toán giữa các biến bằng nhau được định nghĩa là:

A + A = A

ĐẾN . A = A

Hoàn thiện

Bất kỳ hoạt động nào giữa một biến và phần bù của nó được định nghĩa là:

A + KHÔNG PHẢI A = 1

ĐẾN . KHÔNG A = 0

Phép phủ định hoặc phủ định kép

Mọi phủ định kép sẽ được coi là biến tự nhiên.

NOT (KHÔNG A) = A

Giao hoán

A + B = B + A; Tính giao hoán của tổng.

ĐẾN . B = B. ĐẾN ; 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 liên kết của tổng.

ĐẾN . (B. C) = (A. B). C = A. B. C; Tính liên kết của sản phẩm.

Phân phối

A + (B. C) = (A + B). (A + C); Phân phối của tổng đối với sản phẩm.

ĐẾN . (B + C) = (A. B) + (A + C); Sự phân phối của sản phẩm đối với tổng.

Quy luật hấp thụ

Có nhiều định luật hấp thụ trong số nhiều tài liệu tham khảo, một số định luật được biết đến nhiều nhất là:

ĐẾN . (A + B) = A

ĐẾN . (KHÔNG A + B) = A. B

KHÔNG A (A + B) = KHÔNG PHẢI A. B

(A + B). (A + KHÔNG PHẢI B) = A

A + A. B = A

A + KHÔNG PHẢI A. B = A + B

KHÔNG PHẢI A + A. B = KHÔNG A + B

ĐẾN . B + A. KHÔNG B = A

Định lý Morgan

Chúng là các luật biến đổi, xử lý các cặp biến tương tác giữa các phép toán xác định của đại số Boolean (+.).

NOT (A. B) = NOT A + NOT B

NOT (A + B) = NOT A. KHÔNG PHẢI B

A + B = NOT (KHÔNG A + KHÔNG PHẢI B)

ĐẾN . B = NOT (KHÔNG A. KHÔNG PHẢI B)

Tính hai mặt

Tất cả các định đề và định lý đều có tính đối ngẫu. Điều này ngụ ý rằng bằng cách trao đổi các biến và phép toán, mệnh đề kết quả được xác minh. Tức là khi đổi 0 lấy 1 và AND lấy 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 định đề được sử dụng

một . 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 thu đượ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 sự thật 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 đến 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, 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 tính lưu động 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ột mạch, trong đó ưu tiên là đưa độ phức tạp hoặc mức độ của mạch xuống biểu thức thấp nhất có thể. Điều này là do độ trễ tính toán mà mỗi cổng giả định.

Trong ví dụ sau, chúng ta sẽ quan sát sự đơn giản hóa một biểu thức logic thành biểu thức nhỏ nhất của nó, sử dụng các định lý và định đề của đại số Boolean.

KHÔNG PHẢI (AB + A + B). KHÔNG (A + KHÔNG PHẢI B)

KHÔNG PHẢI. NOT (A + NOT B); Bao thanh toán A với một thừa số chung.

KHÔNG PHẢI. NOT (A + NOT B); Theo định lý A + 1 = 1.

KHÔNG PHẢI (A + B). NOT (A + NOT B); theo định lý A. 1 = A

(KHÔNG A. KHÔNG PHẢI B). ;

Theo định lý Morgan NOT (A + B) = NOT A. KHÔNG PHẢI B

(KHÔNG A. KHÔNG PHẢI B). (KHÔNG A. B); Theo định lý phủ định kép NOT (NOT A) = A

KHÔNG PHẢI A. KHÔNG PHẢI B. KHÔNG PHẢI A. B; Phân nhóm đại số.

KHÔNG PHẢI A. KHÔNG PHẢI A. KHÔNG PHẢI B. B; Tính giao hoán của tích A. B = B. ĐẾN

KHÔNG PHẢI A. KHÔNG PHẢI B. B; Theo định lý A. A = A

KHÔNG PHẢI A. 0; Theo định lý A. KHÔNG A = 0

0; Theo định lý A. 0 = 0

ĐẾN . B. C + KHÔNG PHẢI A + A. KHÔNG PHẢI B. C

ĐẾN . C. (B + KHÔNG PHẢI B) + KHÔNG PHẢI A; Bao thanh toán (A. C) với một thừa số chung.

ĐẾN . C. (1) + KHÔNG PHẢI A; Theo định lý A + NOT A = 1

ĐẾN . C + KHÔNG PHẢI A; Theo quy tắc của định lý số không và sự thống nhất 1. A = A

KHÔNG PHẢI A + C ; Theo luật Morgan A + NOT A. B = A + B

Đối với giải pháp này, định luật Morgan phải được mở rộng để xác định:

NOT (KHÔNG PHẢI A). C + KHÔNG A = KHÔNG PHẢI A + C

Bởi vì NOT (NOT A) = A bởi phép ứng biến.

Đơn giản hóa hàm logic

KHÔNG PHẢI A. KHÔNG PHẢI B. KHÔNG PHẢI C + KHÔNG PHẢI A. KHÔNG PHẢI B. C + KHÔNG PHẢI A. KHÔNG C xuống biểu thức tối thiểu của nó

KHÔNG PHẢI A. KHÔNG PHẢI B. (KHÔNG C + C) + KHÔNG PHẢI A. KHÔNG C; Bao thanh toán (KHÔNG A. KHÔNG PHẢI B) với thừa số chung

KHÔNG PHẢI A. KHÔNG PHẢI B. (1) + KHÔNG A. KHÔNG C; Theo định lý A + NOT A = 1

(KHÔNG A. KHÔNG PHẢI B) + (KHÔNG A. KHÔNG PHẢI C); Theo quy tắc của định lý số không và sự thống nhất 1. A = A

KHÔNG A (KHÔNG PHẢI B + KHÔNG PHẢI C); Bao thanh toán KHÔNG PHẢI A với một thừa số chung

KHÔNG PHẢI A. KHÔNG (B. C); Theo luật Morgan KHÔNG (A. B) = KHÔNG A + KHÔNG PHẢI B

KHÔNG Theo định luật Morgan KHÔNG (A. B) = KHÔNG A + KHÔNG PHẢI B

Bất kỳ lựa chọn nào trong 4 lựa 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 dạng đơn giản nhất

(A. NOT B. C + A. NOT B. B. D + NOT A. NOT B). C

(A. KHÔNG B. C + A. 0. D + KHÔNG A. KHÔNG PHẢI B). C; Theo định lý A. KHÔNG A = 0

(A. NOT B. C + 0 + NOT A. NOT B). C; Theo định lý A. 0 = 0

(A. NOT B. C + NOT A. NOT B). C; Theo định lý A + 0 = A

ĐẾN . KHÔNG PHẢI B. C. C + KHÔNG PHẢI A. KHÔNG PHẢI B. C; Theo phân phối của sản phẩm đối với tổng

ĐẾN . KHÔNG PHẢI B. C + KHÔNG PHẢI A. KHÔNG PHẢI B. C; Theo định lý A. A = A

KHÔNG PHẢI B. C (A + KHÔNG PHẢI A) ; Bao thanh toán (KHÔNG B. C) với thừa số chung

KHÔNG PHẢI B. C (1); Theo định lý A + NOT A = 1

KHÔNG PHẢI B. C; Theo quy tắc của định lý số không và sự thống nhất 1. A = A

Người giới thiệu

1. Đại số Boolean và các ứng dụng của nó J. Eldon Whitesitt. Công ty xuất bản Continental, 1980.
2. Toán học và Kỹ thuật trong Khoa học Máy tính. Christopher J. Van Wyk. Viện Khoa học Máy tính và Công nghệ. Cục tiêu chuẩn quốc gia. Washington, DC 20234
3. Toán cho Khoa học Máy tính. Eric Lehman. Google Inc.
   F Thomson Leighton Khoa Toán học và Phòng thí nghiệm Khoa học Máy tính và AI, Học viện Công nghệ Massachussetts; Akamai Technologies.
4. Các yếu tố của Phân tích Trừu tượng. Tiến sĩ Mícheál O'Searcoid. Khoa toán học. Cao đẳng đại học Dublin, Beldfield, Dublind.
5. Giới thiệu về Logic và Phương pháp luận của Khoa học Suy luận. Alfred Tarski, New York Oxford. Báo chí Đại học Oxford.