Logic mệnh đề được cho phép ta màn biểu diễn những sự kiện. Mỗi kí hiệu trong logic mệnh đềđược minh họa như thể một sự kiện trong quốc tế hiện thực, sử dụng những liên kết logic ta hoàn toàn có thể tạo ra những câu phức tạp trình diễn những sự kiện mang ý nghĩa phức tạp hơn. Như vậy, năng lực trình diễn của logic mệnh đề chỉ số lượng giới hạn trong khoanh vùng phạm vi quốc tế những sự kiện .
Đối tượng : một cái bàn, một cái nhà, một cái cây, một con người, một số lượng ….
Tính chất: Cái bàn có thể có tính chất: có bốn chân, làm bằng gỗ, không có ngăn kéo. Con số có
thể có tính chất là số nguyên, số hữu tỉ, là số chính phương…
Quan hệ : cha con, đồng đội, bè bạn ( giữa con người ) ; lớn hơn, nhỏ hơn, bằng nhau ( giữa những số lượng ) ; bên trong, bên ngoài nằm trên nằm dưới ( giữa những vật phẩm ) …
Hàm : Một trường hợp riêng của quan hệ là quan hệ hàm. Chẳng hạn, vì mỗi người có một mẹ, do đó ta có quan hệ hàm ứng mỗi người với mẹ của nó .
Mục này dành cho nghiên cứu và điều tra logic vị từ cấp một với tư cách là một ngôn từ màn biểu diễn tri thức. Logic vị từ cấp một đóng vai trò quan trọng trong màn biểu diễn tri thức vì năng lực trình diễn của nó ( nó được cho phép ta trình diễn tri thức về quốc tế với những đối tượng người tiêu dùng, những thuộc tính của đối tượng người dùng và những quan hệ của đối tượng người tiêu dùng ), không chỉ có vậy, nó là cơ sở cho nhiều ngôn từ logic khác .
3.5.6.1 Cú pháp và ngữ nghĩa của logic vị từ cấp 1
Logic vị từ cấp một là mở rộng của logic mệnh đề. Nó cho phép ta mô tả thế giới với các đối
tượng, các thuộc tính của đối tượng và các mối quan hệ giữa các đối tượng. Nó sử dụng các biến
(biến đối tượng) để chỉ các đối tượng trong một miền đối tượng nào đó. Để mô tả các thuộc tính
của đối tượng, các quan hệ giữa các đối tượng, trong logic vị từ, người ta đưa vào các vị từ
( predicate ). Ngoài những liên kết logic như trong logic mệnh đề, logic vị từ cấp một còn sử dụng những
lượng tử. Chẳng hạn, lượng tử
∀
(với mọi) cho phép ta tạo ra các câu nói tới mọi đối tượng trong
một miền đối tượng nào đó.
3.5.6.1.1 Cú pháp.
Các ký hiệu.
Logic vị từ cấp một sử dụng những loại ký hiệu sau đây. Các ký hiệu hằng : a, b, c, An, Ba, John, …
Các ký hiệu biến : x, y, z, u, v, w, …
Các ký hiệu vị từ : P, Q., R, S, Like, Havecolor, Prime, …
Mỗi vị từ là vị từ của n biến ( n
≥
0). Chẳng hạn Like là vị từ của hai biến, Prime là vị từ một biến.
Các ký hiệu vị từ không biến là các ký hiệu mệnh đề.
Các ký hiệu hàm : f, g, cos, sin, mother, husband, distance, …
Mỗi hàm là hàm của n biến ( n
≥
1). Chẳng hạn, cos, sin là hàm một biến, distance là hàm của ba
biến.
Các ký hiệu liên kết logic :
∧
(hội),
∨
(tuyển), ⎤ (phủđịnh),
⇒
(kéo theo),
⇔
(kéo theo nhau).
Các ký hiệu lượng tử:
∀
(với mọi),
∃
(tồn tại).
Các ký hiệu ngăn cách : dấu phẩy, dấu mở ngoặc và dấu đóng ngoặc .
Các hạng thức
Các hạng thức ( term ) là những biểu thức diễn đạt những đối tượng người tiêu dùng. Các hạng thức được xác lập đệ quy như sau .
Các ký hiệu hằng và những ký hiệu biến là hạng thức .
Nếu t1, t2, t3,…, tn là n hạng thức và f là một ký hiệu hàm n biến thì f(t1, t2,…, tn) là hạng thức.
Một hạng thức không chứa biến được gọi là một hạng thức cụ thể (ground term).
Chẳng hạn, An là ký hiệu hằng, mother là ký hiệu hàm một biến, thì mother(An) là một hạng thức
cụ thể.
Các công thức phân tử
Chúng ta sẽ màn biểu diễn những đặc thù của đối tượng người dùng, hoặc những quan hệ giữa những đối tượng người dùng bởi những
công thức phân tử(câu đơn).
Các công thức phân tử ( câu đơn ) được xác lập đệ quy như sau .
Các ký hiệu vị từ không biến (các ký hiệu mệnh đề) là công thức phân tử.
Nếu t1, t2, …, tn là n hạng thức và P là vị từ của n biến thì P ( t1, t2, …, tn ) là công thức phân tử. Chẳng hạn, Hoa là một ký hiệu hằng, Love là một vị từ của hai biến, husband là hàm của một biến, thì Love ( Hoa, husband ( Hoa ) ) là một công thức phân tử .
Các công thức
Từ công thức phân tử, sử dụng những liên kết logic và những lượng tử, ta thiết kế xây dựng nên những công thức ( những câu ) .
Các công thức được xác lập đệ quy như sau : Các công thức phân tử là công thức .
Nếu G và H là những công thức, thì những biểu thức ( G
∧
H), (G
∨
H), (⎤ G), (G
⇒
H), (G
⇔
H) là
công thức.
Nếu G là một công thức và x là biến thì những biểu thức (
∀
x G), (
∃
x G) là công thức.
Các công thức không phải là công thức phân tử sẽđược gọi là các câu phức hợp. Các công thức
không chứa biến sẽđược gọi là công thức cụ thể. Khi viết các công thức ta sẽ bỏđi các dấu ngoặc
không cần thiết, chẳng hạn các dấu ngoặc ngoài cùng.
Lượng tử phổ dụng được cho phép miêu tả đặc thù của cả một lớp những đối tượng người dùng, chứ không phải của một đối tượng người dùng, mà không cần phải liệt kê ra toàn bộ những đối tượng người tiêu dùng trong lớp. Chẳng hạn sử dụng vị
từ Elephant ( x ) ( đối tượng người tiêu dùng x là con voi ) và vị từ Color ( x, Gray ) ( đối tượng người tiêu dùng x có mầu xám ) thì câu “ tổng thể những con voi đều có mầu xám ” hoàn toàn có thể trình diễn bởi công thức
∀
x (Elephant(x)
⇒
Color(x,
Gray)).
Lượng tử sống sót được cho phép ta tạo ra những câu nói đến một đối tượng người tiêu dùng nào đó trong một lớp đối tượng người tiêu dùng mà nó có một đặc thù hoặc thỏa mãn nhu cầu một quan hệ nào đó. Chẳng hạn bằng cách sử dụng những câu
đơn Student ( x ) ( x là sinh viên ) và Inside ( x, P301 ), ( x ở trong phòng 301 ), ta hoàn toàn có thể trình diễn câu “ Có một sinh viên ở phòng 301 ” bởi biểu thức
∃
x (Student(x)
∧
Inside(x,P301).
Một công thức là công thức phân tử hoặc phủ định của công thức phân tử được gọi là literal.
Chẳng hạn, Play(x, Football), ⎤ Like(Lan, Rose) là các literal. Một công thức là tuyển của các
literal sẽđược gọi là câu tuyển. Chẳng hạn, Male(x)
∨
⎤ Like(x, Foodball) là câu tuyển.
Trong công thức
∀
x G, hoặc
∃
x G trong đó G là một công thức nào đó, thì mỗi xuất hiện của
biến x trong công thức G được gọi là xuất hiện buộc. Một công thức mà tất cả các biến đều là
xuất hiện buộc thì được gọi là công thức đóng.
Ví dụ : Công thức
∀
x P(x, f(a, x)) ∧ ∃y Q(y) là công thức đóng, còn công thức
∀
x P(x, f(y, x))
không phải là công thức đóng, vì sự xuất hiện của biến y trong công thức này không chịu ràng
buộc bởi một lượng tử nào cả (Sự xuất hiện của y gọi là sự xuất hiện tự do).
Sau này tất cả chúng ta chỉ chăm sóc tới những công thức đóng .
3.5.6.1.2. Ngữ nghĩa.
Cũng như trong logic mệnh đề, nói đến ngữ nghĩa là chúng ta nói đến ý nghĩa của các công thức
trong một thế giới hiện thực nào đó mà chúng ta sẽ gọi là một minh họa.
Để xác lập một minh họa, trước hết ta cần xác lập một miền đối tượng người tiêu dùng ( nó gồm có tổng thể những
đối tượng người tiêu dùng trong quốc tế hiện thực mà ta chăm sóc ) .
Trong một minh họa, những ký hiệu hằng sẽ được gắn với những đối tượng người dùng đơn cử trong miền đối tượng người tiêu dùng, những ký hiệu hàm sẽđược gắn với một hàm đơn cử nào đó. Khi đó, mỗi hạng thức đơn cử sẽ
chỉ định một đối tượng người tiêu dùng đơn cử trong miền đối tượng người dùng. Chẳng hạn, nếu An là một ký hiệu hằng, Father là một ký hiệu hàm, nếu trong minh họa An ứng với một người đơn cử nào đó, còn Father ( x ) gắn với hàm : ứng với mỗi x là cha của nó, thì hạng thức Father ( An ) sẽ chỉ người cha của An .
Ngữ nghĩa của các câu đơn.
Trong một minh họa, những ký hiệu vị từ sẽđược gắn với một thuộc tính, hoặc một quan hệ đơn cử
nào đó. Khi đó mỗi công thức phân tử ( không chứa biến ) sẽ chỉđịnh một sự kiện đơn cử. Đương nhiên sự kiện này hoàn toàn có thể là đúng ( True ) hoặc sai ( False ). Chẳng hạn, nếu trong minh họa, ký hiệu hằng Lan ứng với một cô gái đơn cử nào đó, còn Student ( x ) ứng với thuộc tính “ x là sinh viên ” thì
câu Student ( Lan ) có giá trị chân lý là True hoặc False tùy thuộc trong thực tiễn Lan có phải là sinh viên hay không .
Ngữ nghĩa của các câu phức hợp.
Khi đã xác lập được ngữ nghĩa của những câu đơn, ta hoàn toàn có thể xác lập được ngữ nghĩa của những câu phức tạp ( được tạo thành từ những câu đơn bằng những link những câu đơn bởi những liên kết logic ) như
trong logic mệnh đề .
Ví dụ : Câu Student ( Lan ) ∧ Student ( An ) nhận giá trị True nếu cả hai câu Student ( Lan ) và Student ( An ) đều có giá trị True, tức là cả Lan và An đều là sinh viên .
Câu Like ( Lan, Rose )
∨
Like(An, Tulip) là đúng nếu câu Like(Lan, Rose) là đúng hoặc câu
Like(An, Tulip) là đúng.
Ngữ nghĩa của các câu chứa các lượng tử
Ngữ nghĩa của các câu
∀
x G, trong đó G là một công thức nào đó, được xác định như là ngữ
nghĩa của công thức là hội của tổng thể những công thức nhận được từ công thức G bằng cách thay x bởi một đối tượng người tiêu dùng trong miền đối tượng người dùng. Chẳng hạn, nếu miền đối tượng người dùng gồm ba người { Lan, An, Hoa } thì ngữ nghĩa của câu
∀
x Student(x) được xác định là ngữ nghĩa của câu Student(Lan)
∧
Student ( An )
∧
Student(Hoa). Câu này đúng khi và chỉ khi cả ba câu thành phần đều đúng, tức là
cả Lan, An, Hoa đều là sinh viên.
Như vậy, công thức
∀
x G là đúng nếu và chỉ nếu mọi công thức nhận được từ G bằng cách thay x
bởi một đối tượng trong miền đối tượng đều đúng, tức là G đúng cho tất cả các đối tượng x trong
miền đối tượng.
Ngữ nghĩa của công thức
∃
x G được xác định như là ngữ nghĩa của công thức là tuyển của tất cả
những công thức nhận được từ G bằng cách thay x bởi một đối tượng người tiêu dùng trong miền đối tượng người tiêu dùng. Chẳng hạn, nếu ngữ nghĩa của câu Younger ( x, 20 ) là “ x trẻ hơn 20 tuổi “ và miền đối tượng người dùng gồm ba người { Lan, An, Hoa } thì ngữ nghĩa của câu
∃
x Yourger(x,20) là ngữ nghĩa của câu Yourger(Lan,20)
∨
Yourger ( An, 20 )
∨
Yourger(Hoa,20). Câu này nhận giá trị True nếu và chỉ nếu ít nhất một trong
ba người Lan, An, Hoa trẻ hơn 20 tuổi.
Như vậy công thức
∃
x G là đúng nếu và chỉ nếu một trong các công thức nhận được từ G
bằng cách thay x bằng một đối tượng trong miền đối tượng là đúng.
Bằng những giải pháp đã trình diễn ở trên, ta hoàn toàn có thể xác lập được giá trị chân lý ( True, False ) của một công thức bất kể trong một minh họa. ( Lưu ý rằng, ta chỉ chăm sóc tới những công thức
đóng ) .
Sau khi đã xác định khái niệm minh hoạ và giá trị chân lý của một công thức trong một
minh hoạ, chúng ta có thể đưa ra các khái niệm công thức vững chắc (thoảđược, không thoả
được), mô hìnhcủa công thức giống như trong logic mệnh đề.
Các công thức tương đương
Cũng như trong logic mệnh đề, ta nói hai công thức G và H tương tự ( viết là G
≡
H)
nếu chúng cùng đúng hoặc cùng sai trong mọi minh hoạ. Ngoài các tương đương đã biết trong
logic mệnh đề, trong logic vị từ cấp một còn có các tương đương khác liên quan tới các lượng tử.
Giả sử G là một công thức, cách viết G(x) nói rằng công thức G có chứa các xuất hiện của biến x.
Khi đó công thức G(y) là công thức nhận được từ G(x) bằng cách thay tất cả các xuất hiện của x
bởi y. Ta nói G(y) là công thức nhận được từ G(x) bằngcách đặt tên lại (biến x được đổi tên lại là
y).
Các công thức tương tự :
1.
∀
x G(x)
≡∀
y G(y)
∃
x G(x)
≡∃
y G(y)
Đặt tên lại biến đi sau lượng tử sống sót, nhận được công thức tương tự .
2. ⎤ (
∀
x G(x))
≡∃
x (⎤ G(x))
⎤ (
∃
x G(x))
≡∀
x (⎤ G(x))
3.
∀
x (G(x)
∧
H(x))
≡∀
x G(x)
∧∀
x H(x)
∃
x (G(x)
∨
H(x))
≡∃
x G(x)
∨∃
x H(x)
Ví dụ:
∀
x Love(x, Husband(x))
≡∀
y Love(y, Husband(y)).
3.5.6.2. Chuẩn hóa và công thức
Từ những câu phân tử, bằng cách sử dụng những liên kết logic và những lượng tử, ta hoàn toàn có thể tạo ra những câu phức tạp có cấu trúc rất phức tạp. Để thuận tiện cho việc tàng trữ những câu trong bộ nhớ, và thuận tiện cho việc kiến thiết xây dựng những thủ tục suy diễn, tất cả chúng ta cần chuẩn hóa những câu bằng cách đưa chúng về
dạng chuẩn tắc hội(hội của các câu tuyển).
Trong mục này tất cả chúng ta sẽ trình diễn thủ tục chuyển một câu phức hợp thành một câu ở
dạng chuẩn tắc hội tương tự .
Thủ tục chuẩn hoá các công thức gồm các bước sau:
• Loại bỏ các kéo theo
Để vô hiệu những kéo theo, ta chỉ cần thay công thức P ⇒ Q bởi công thức tương tự
⎤
P
∨
Q
thay P ⇔ Q bởi (
⎤
P
∨
Q)
∧
(
⎤
P
∨
Q)
• Chuyển các phủđịnh tới các phân tử
Điều này được triển khai bằng cách thay công thức ở vế trái bởi công thức ở vế phải trong những tương tự sau
⎤
(
⎤
P)
≡
P
⎤
(P
∧
Q)
≡⎤
P
∨⎤
Q
⎤
(P
∨
Q)
≡⎤
P
∧⎤
Q
⎤
(∀x P)
≡∃
x (
⎤
P)
⎤
(∃x P)
≡∀
x (
⎤
P)
• Loại bỏ các lượng tử tồn tại
Giả sử P(x,y) là các vị từ có nghĩa: “y lớn hơn x” trong miền các số. Khi đó, công thức
∀
x (
∃
y
(P(x,y)) có nghĩa là “với mọi sốx, tồn tại y sao cho sốy lớn hơn x”. Ta có thể xem y trong công
thức đó là hàm của đối số x. Chẳng hạn, loại bỏ lượng tử
∃
y, công thức đang xét trở thành
∀
Một cách tổng quát, giả sử
∃
y (G) là một công thức con của công thức đang xét và nằm
trong miền tác dụng của các lượng tử
∀
x1,…,
∀
xn. Khi đó, có thể xem y là hàm của n biến x1,…,xn.
của ví dụ f(x1…xn). Sau đó, thay các xuất hiện của y trong công thức G bởi hạng thức f(x1…xn) và
loại bỏ các lượng tử tồn tại. Hàm fđược đưa vào để loại bỏ các lượng tử tồn tại được gọi là hàm
Skolem.
Ví dụ: xét công thức sau:
∀
x (
∃
y (P(x,y) ∨
∀
u (
∃
v (Q(a, v)
∧∃
y
⎤
R(x,y))) (1)
Công thức con
∃
y P(x,y) nằm trong miền tác dụng của lượng tử
∀
x, ta xem y là hàm của x: f(x).
Các công thức con
∃
v (Q(a, v)) và
∃
y
⎤
R(x,y) nằm trong miền tác dụng của các lượng tử
∀
x,
∀
u
ta xem v là hàm g(x,u) và y là hàm h(x,u) của hai biến x,u. Thay các xuất hiện của y và ∨ bởi các
hàm tương ứng, sau đó loại bỏ các lượng tử tồn tại, từ công thức (1) ta nhận được công thức:
∀
x (P(x,f(x)) ∨
∀
u (Q(a,g(x,u))
∧⎤
R(x,h(x,u)))) (2)
• Loại bỏ các lượng tử phổ dụng
Sau bước 3 trong công thức chỉ còn lại những lượng tử phổ dụng và mọi Open của những biến đều nằm trong miền công dụng của những lượng tử phổ dụng. Ta hoàn toàn có thể vô hiệu tổng thể những lượng tử phổ
dụng, công thức ( 2 ) trở thành công thức :
P(x,f(x)) ∨ (Q(a,g(x,u))
∧⎤
R(x,h(x,u))) (3)
Cần chú ý quan tâm rằng, sau khi được triển khai bước này toàn bộ những biến trong công thức được xem là chịu tính năng của những lượng tử phổ dụng .
• Chuyển các tuyển tới các literal
Bước này được thực thi bằng cách thay những công thức dạng : P ∨ ( Q.
∧
R) bởi (P∨Q)
∧
(P∨R) và
thay (P
∧
Q)∨R bởi (P∨Q)
∧
(P∨R). Sau bước này công thức trở thành hội của các câu tuyển nghĩa
là ta nhận được các công thức ở dạng chuẩn tắc hội.
Chẳng hạn, câu ( 3 ) được chuyển thành công thức sau
(P(x,f(x)) ∨ (Q(a,g(x,u)))
∧
(P(x,f(x)) ∨
⎤
R(x,h(x,u))) (4)
• Loại bỏ các hội
Một câu hội là đúng nếu và chỉ nếu toàn bộ những thành phần của nó đều đúng. Do đó công thức ở
dạng chuẩn tắc hội tương tự với tập những thành phần. Chẳng hạn, câu ( 4 ) tương tự với tập hai câu tuyển sau
P(f(x)) ∨ (Q(a,g(x,u))
P(f(x)) ∨
⎤
R(x,h(x,u)) (5)
• Đặt tên lại các biến
Đặt tên lại những biến sao cho những biến trong những câu khác nhau có tên khác nhau, ví dụ điển hình, hai câu ( 5 ) có hai biến cùng tên là x, ta cần đổi tên biến x trong câu hai thành z, khi đó những câu ( 5 ) tương
đương với những câu sau
P(f(x)) ∨ (Q(a,g(x,u))
Như vậy, khi tri thức là một tập hợp nào đó những công thức trong logic vị từ, bằng cách vận dụng thủ
tục trên ta nhận được cơ sở tri thức chỉ gồm những câu tuyển ( tức là luôn hoàn toàn có thể xem mỗi câu trong cơ sở tri thức là tuyển của những literal ). Tương tự như logic mệnh đề, mỗi câu tuyển hoàn toàn có thể màn biểu diễn dưới dạng một kéo theo ; vế trái của những kéo theo là hội của những câu phân tử ; vế phải là tuyển của những câu phân tử. Dạng câu này được gọi là câu Kowalski. Một trường hợp quan trọng của câu Kowalski là câu Horn ( luật if – then ) .
3.5.6.3 Các luật suy diễn
Trong các phần trươc chúng ta đã đưa ra các luật suy diễn quan trọng trong logic mệnh đề: luật
Modus Ponens, luật Modus Tolens, luật bắc cầu,… luật phân giải. Chúng ta đã chỉ ra rằng, luật
phân giải là luật đầy đủ cho bác bỏ. Điều đó có nghĩa là, bằng phương pháp chứng minh bác bỏ,
chỉ sử dụng luật phân giải ta có thể chứng minh được một công thức có là hệ quả logic của một
tập các công thức cho trước hay không. Kết quả quan trọng này sẽđược mở rộng sang lôgic vị từ.
Tất cả các luật suy diễn đã được đưa ra trong logic mệnh đề đều đúng trong logic vị từ cấp một.
Bây giờ ta đưa ra một luật suy diễn quan trọng trong logic vị từ liên quan tới lượng tử phổ dụng
• Luật thay thế phổ dụng:
(Trang 56 -78 )
