First-Order Logic - Logic vị từ bậc nhất

Logic mệnh đề phù hợp khi số facts và đối tượng còn nhỏ. Nhưng nếu hệ thống quản lý hàng nghìn sinh viên, ta không muốn viết một rule riêng cho từng người.

Ví dụ, thay vì tạo:

AnPassedPython -> AnCanRegisterAI
BinhPassedPython -> BinhCanRegisterAI
ChiPassedPython -> ChiCanRegisterAI
...

Ta muốn viết một rule tổng quát cho mọi sinh viên. First-Order Logic - FOL cung cấp cách biểu diễn đó.

Mục tiêu

Sau bài này, bạn cần:

• hiểu giới hạn của Propositional Logic khi có nhiều object;
• dùng constants, predicates và variables;
• đọc và viết $\forall$ và $\exists$;
• hiểu thứ tự quantifier có thể thay đổi hoàn toàn ý nghĩa;
• biểu diễn facts, relations và rules đơn giản bằng FOL;
• biết vị trí của symbolic logic trong các hệ AI hiện đại.

Giới hạn của Propositional Logic

Propositional Logic hoạt động tốt khi có ít đối tượng.

Nhưng giả sử cần biểu diễn:

Mọi sinh viên đã hoàn thành môn tiên quyết đều được đăng ký môn AI.

Nếu có 10,000 sinh viên, dùng propositional symbols riêng cho từng sinh viên sẽ rất dài:

AnPassedPrerequisite
AnCanRegisterAI
BinhPassedPrerequisite
BinhCanRegisterAI
...

Ta muốn một rule tổng quát cho mọi x.

Đó là lúc First-Order Logic trở nên hữu ích.

First-Order Logic - Logic vị từ bậc nhất

First-Order Logic - FOL mở rộng logic mệnh đề bằng:

• constants - hằng;
• predicates - vị từ;
• variables - biến;
• quantifiers - lượng từ.

Các connective $\neg$, $\land$, $\lor$, $\to$, $\leftrightarrow$ vẫn được dùng như trước.

Constant Symbols

Constant đại diện cho một đối tượng cụ thể.

Ví dụ:

An
Binh
AI101
RoomA203

Predicate Symbols

Predicate mô tả thuộc tính hoặc quan hệ và trả về True/False.

Ví dụ một đối số:

đọc là:

An là sinh viên.

Ví dụ hai đối số:

đọc là:

An đăng ký môn AI101.

Ví dụ:

đọc là:

Python là môn tiên quyết của AI101.

Universal Quantification - với mọi

Ký hiệu:

Ví dụ:

Đọc là:

Với mọi $x$, nếu $x$ là sinh viên thì $x$ có mã sinh viên.

Chú ý ngoặc ngầm:

Existential Quantification - tồn tại ít nhất một

Ký hiệu:

Ví dụ:

Đọc là:

Tồn tại ít nhất một người vừa là sinh viên vừa đăng ký AI101.

$\exists$ không có nghĩa là “chỉ có đúng một”. Nó chỉ yêu cầu ít nhất một.

Kết hợp $\forall$ và $\exists$

Câu:

Mỗi sinh viên đều đăng ký ít nhất một môn học.

Có thể viết:

Đọc từng lớp:

1. chọn một đối tượng bất kỳ $x$;
2. nếu $x$ là sinh viên;
3. thì phải tồn tại ít nhất một $y$;
4. $y$ là course và $x$ enrolled vào $y$.

Thứ tự lượng từ rất quan trọng

Hai câu sau khác nhau:

Mọi sinh viên có một môn nào đó mà họ đăng ký

Mỗi sinh viên có thể đăng ký một môn khác nhau.

Có một môn mà mọi sinh viên đều đăng ký

Ở đây phải có một course chung cho mọi sinh viên.

Đổi vị trí $\forall$ và $\exists$ có thể đổi hẳn nghĩa của câu.

Propositional Logic và First-Order Logic

FOL biểu đạt mạnh hơn nhưng inference cũng phức tạp hơn.

Một Knowledge Base bằng First-Order Logic

Ta có facts:

Rule:

Từ đó suy ra:

Đây là cách viết gọn hơn nhiều so với tạo rule riêng cho từng sinh viên.

Từ Symbolic AI tới hệ thống hiện đại

Knowledge representation bằng logic thuộc nhóm thường được gọi là Symbolic AI.

Ta mô tả rõ:

• symbol có nghĩa gì;
• rule nào được phép;
• inference diễn ra như thế nào.

Ưu điểm:

• dễ kiểm tra logic;
• dễ giải thích đường suy luận;
• phù hợp với rule rõ ràng;
• không cần training data để hoạt động.

Hạn chế:

• knowledge engineering có thể tốn công;
• thế giới thật có ngoại lệ và thông tin thiếu;
• số rule có thể tăng rất lớn;
• dữ liệu có thể mâu thuẫn hoặc không chắc chắn.

Vì vậy các hệ AI thực tế có thể kết hợp:

• symbolic rules;
• search;
• probabilistic reasoning;
• machine learning;
• neural networks.

Không có yêu cầu rằng một hệ AI chỉ được dùng một trường phái.

Chốt lại

Propositional Logic coi mỗi phát biểu như một khối True/False riêng. First-Order Logic mở khối đó ra thành:

đối tượng + thuộc tính + quan hệ + lượng từ

Nhờ vậy, một rule có thể áp dụng cho cả một lớp đối tượng thay vì phải lặp lại cho từng trường hợp.

Đổi lại, khả năng biểu đạt lớn hơn cũng khiến suy luận phức tạp hơn. Trong môn nhập môn, mục tiêu quan trọng nhất là đọc đúng biểu thức và biết khi nào nên dùng proposition, predicate, $\forall$ hay $\exists$.

Bản tiếng Anh đang soạn.