Lưới và Đại số Boolean

Một lưới là một tập hợp có thứ tự trong đó mọi cặp phần tử đều có cận trên nhỏ nhất và cận dưới lớn nhất, và một đại số Boolean là một lưới phân phối có phần tử bù, mô hình hóa đại số của logic và các tập hợp.

Definition

Một lưới là một tập hợp được sắp thứ tự một phần trong đó bất kỳ hai phần tử nào cũng có một phép nối và một phép gặp; một đại số Boolean là một lưới phân phối với các phần tử nhỏ nhất và lớn nhất trong đó mọi phần tử đều có một phần tử bù.

Scope

Chủ đề này xem xét các lưới như các cấu trúc đại số và lý thuyết thứ tự kép, các phép toán nối và gặp, các lưới phân phối và mô-đun, các phần tử bù, và các đại số Boolean với lý thuyết biểu diễn của chúng. Nó bao gồm biểu diễn của Birkhoff về các lưới phân phối hữu hạn và biểu diễn của Stone về các đại số Boolean, liên kết thứ tự, đại số và tô-pô.

Core questions

• Khi nào thì cận trên và cận dưới của các cặp tồn tại, và chúng thỏa mãn những quy luật nào?
• Những lưới nào là phân phối hoặc mô-đun, và chúng được đặc trưng như thế nào?
• Các lưới phân phối hữu hạn được biểu diễn bằng các tập hợp các ideal thứ tự như thế nào?
• Các đại số Boolean hình thức hóa logic của các mệnh đề và đại số của các tập hợp như thế nào?

Key concepts

• Phép nối và phép gặp
• Các lưới bị chặn, đầy đủ và có phần tử bù
• Các lưới phân phối và mô-đun
• Đại số Boolean
• Biểu diễn Birkhoff
• Biểu diễn Stone

Key theories

Định lý biểu diễn của Birkhoff

Mọi lưới phân phối hữu hạn đều đẳng cấu với lưới của các tập hợp con giảm của poset các phần tử không thể phân tách bằng phép nối của nó, đưa ra một mô tả đầy đủ và cụ thể về các lưới phân phối hữu hạn.

Định lý biểu diễn của Stone

Mọi đại số Boolean đều đẳng cấu với một trường các tập hợp, và mọi đại số Boolean hữu hạn đều đẳng cấu với tập hợp lũy thừa của một tập hợp hữu hạn, đặt nền tảng cho đại số trừu tượng của logic trong các phép toán tập hợp cụ thể.

Clinical relevance

Các đại số Boolean mô hình hóa các mạch logic số, logic mệnh đề và các phép toán tập hợp, trong khi các lưới cấu trúc hệ thống phân cấp kiểu, mức độ bảo mật trong kiểm soát truy cập và các tập hợp đóng của phân tích khái niệm hình thức.

History

Đại số logic của Boole năm 1854, lý thuyết lưới của Birkhoff những năm 1930, và định lý biểu diễn của Stone năm 1936 cùng nhau thiết lập lý thuyết đại số hiện đại về thứ tự và logic.

Key figures

• George Boole
• Garrett Birkhoff
• Marshall Stone

Seminal works

• davey2002

Frequently asked questions

Mọi lưới có phải là phân phối không?

Không; các lưới không phân phối nhỏ nhất là hình thoi và hình ngũ giác, và một lưới là phân phối chính xác khi nó không chứa cả hai như một lưới con.

Một đại số Boolean liên quan đến lý thuyết tập hợp như thế nào?

Tập hợp lũy thừa của bất kỳ tập hợp nào, được sắp thứ tự theo quan hệ bao hàm với phép hợp, phép giao và phép bù, là một đại số Boolean, và mọi đại số Boolean hữu hạn đều có dạng này.