Đại Học Quốc Gia Thành Phố Hồ Chí Minh
Trường Đại Học Công Nghệ Thông Tin
Lớp Cao Học khóa 5 ngành Khoa Học Máy Tính
12.2012BÀI THU HOẠCH MÔN HỌC
Biểu diễn tri thức
Đề tài
Tìm hiểu về đồ thị khái niệm
Giảng viên hướng dẫn: PGS.TS Đỗ Văn Nhơn
Người thực hiện: Nguyễn Thế Thắng (CH1001128)
26
Mục lục
1. Giới thiệu 3
2. Từ đồ thị hiện sinh đến đồ thị khái niệm 3
3. Logic tổng quát (Common Logic) 9
4. Lập luận với đồ thị 16
5. Mệnh đề, tình huống và siêu ngữ 24
6. Kết luận 27
7. Tài liệu tham khảo 27
26
1. Giới thiệu
Đồ thị khái niệm (conceptual graph) là sự biểu diễn đồ thị cho logic dựa trên những mạng
ngữ nghĩa của trí tuệ nhân tạo và những đồ thị hiện sinh của Charles Sanders Peirce. Vài
phiên bản của đồ thị khái niệm đã được thiết kế và hiện thực hơn ba mươi năm qua. Cái
đơn giản nhất là những đồ thị lõi không có kiểu mà tương ứng với đồ thị hiện sinh
nguyên thủy của Peirce. Tổng quát hơn là đồ thị khái niệm mở rộng là một tập lớn có
kiểu của đồ thị lõi. Đồ thị khái niệm nghiên cứu đã khám phá những kĩ thuật mới lạ cho
lập luận, biểu diễn tri thức, và ngữ nghĩa ngôn ngữ tự nhiên. Ngữ nghĩa của đồ thị khái
niệm lõi và mở rộng được xác định bởi việc ánh xạ hình thức đến và từ chuẩn ISO của

Toán tử tồn tại và toán tử giao là toán tử tổng quát nhất trong việc dịch từ ngôn ngữ tự
nhiên và nhiều mạng ngữ nghĩa trước đây không thể biểu diễn.
Với Begriffsschrift, Frege thông qua kí hiệu cây cho việc biểu diễn đầy đủ logic cấp một
chỉ sử dụng 4 toán tử: khẳng định cửa xoay ), phủ định (biểu diễn bằng đường thẳng
dọc đứng), suy ra (biểu diễn bằng hình như cái móc) và với mọi (biểu diễn bằng một cái
26
cốc chứa biến ràng buộc). Hình 2.2 là biểu diễn Begriffsschrift tương đương với hình 2.1.
Dưới đây là biểu diễn dạng vị từ:
Hình 2.2 Begriffsschrift của Frege cho câu “John is going to Boston by bus”.
Sự lựa chọn toán từ của Frege đơn giản hóa những luật suy luận nhưng dẫn đến những
diễn giải vụng về: không đúng với mọi x và y, nếu x là instance của going thì nếu John là
người thì nếu Boston là thành phố thì nếu y là xe bus thì nếu agent của x là John thì nếu
nơi đến của x là Boston thì phương tiện của x không phải là y.
Không giống như Frege, Peirce đã phát triển kí hiệu đại số cho logic bậc nhất như sự tổng
quát hóa của các toán tử kiểu Boolean. Từ khi Boole xem sự phân rã như việc cộng logic
và sự kết hợp như nhân logic, Peirce biểu diễn toán tử tồn tại bằng Σ cho việc phân rã lặp
đi lặp lại và toán từ với mọi bằng Π cho việc kết hợp lặp đi lặp lại. Sơ đồ hình 2.1 được
biểu diễn theo kí hiệu của Peirce như sau:
26
Thông qua kí hiệu của Peirce, Peano đã tạo ra những biểu tượng mới vì muốn kết hợp
những kí hiệu toán học và logic trong công thức. Trong khi đó, Peirce bắt đầu thử nghiệm
với đồ thị quan hệ cho việc biểu diễn logic như trong hình 2.3. Trong đồ thị đó, lượng từ
tồn tại được biểu diễn bằng một đường nhận diện và sự kết hợp là toán tử Boolean mặc
định. Vì đồ thị của Peirce không phân biệt những tên đúng, những vị từ monadic isJohn
và isBoston có lẽ được sử dụng để biểu diễn những tên. Sau đây là kí hiệu đại số của cho
hình 2.1:
Hình 2.3 đồ thị quan hệ của Peirce cho câu “John is going to Boston by bus”.
Peirce đã thử nghiệm với nhiều phương pháp đồ thị khác nhau cho việc biểu diễn những
toán tử khác của kí hiệu đại số của ông nhưng giống như những nhà nghiên cứu AI của
thập kỉ 60 ông ta không thể tìm ra cách hay để thể hiện được phạm vi của những lượng từ

Những toán tử bình thường của Kamp giống như của Peirce: lượng từ mặc định là tồn tại,
toán từ Boolean mặc định là kết hợp; phủ định được biểu diễn bởi một hộp ngữ cảnh và
suy ra được biểu diễn bởi hai hộp ngữ cảnh. Như trong hình 2.5 trình bày, việc lồng của
những ngữ cảnh của Peirce cho phép những lượng từ trong tiền đề của phép suy ra bao
gồm kết quả bên trong tầm vực của lượng từ. Mặc dù Kamp đã kết nối những hộp với
mũi tên, một giả sử được tạo ra một cách chính xác về tầm vực của lượng từ. Kamp và
Reyle đã đi xa hơn Peirce trong phân tích ngôn ngữ và tạo ra những luật cho việc diễn
dịch những tham chiếu trùng lặp nhưng luật bất kì phát biểu trong những thuật ngữ của kí
hiệu DRS cũng có thể được áp dụng cho kí hiệu EG hoặc CG.
CG trong hình 2.4 đại diện cho những động từ “owns” và “beats” như quan hệ cặp đôi.
Đó là sự lựa chọn những quan hệ được lưa chọn bởi Kamp và nó cũng có thể được sử
dụng với kí hiệu EG hoặc CG. Tuy nhiên, Peirce lưu ý rằng các sự kiện hoặc trạng thái
được thể hiện bởi một động từ cũng là một thực thể có thể được tham chiếu bởi một biến
định lượng. Điểm đó được tìm thấy lại một cách độc lập bởi những nhà ngôn ngữ học,
26
những nhà ngôn ngữ máy tính và những nhà triết học. Đồ thị khái niệm trong hình 2.6
trình bày một biểu diễn mà xem những sự kiện và những trạng thái như những thực thể
liên kết với những thành phần tham gia của chúng bởi những quan hệ trường hợp hoặc
vai trò theo chủ đề.
Hình 2.6 đồ thị khái niệm với những quan hệ trường hợp được trình bày một cách tường
minh.
Những nhãn kiểu If và Then trong hình 2.6 được định nghĩa như những từ đồng nghĩa
cho những ngữ cảnh bị phủ định. Trạng thái của việc sở hữu được liên kết với những
thành phần tham gia của nó bởi những quan hệ (Expr) và (Thme) và hoạt động đánh bại
bởi những quan hệ (Agnt) và (Ptnt).
3. Logic tổng quát (Common Logic)
Logic tổng quát phát triển từ hai dự án nhằm phát triển những chuẩn ANSI song song cho
các đồ thị khái niệm và định dạng trao đổi tri thức (Knowledge Interchange Format).
Cuối cùng hai dự án được sát nhập thành một dự án ISO để phát triển cú pháp trừu tượng
chung và nền tảng lí thuyết mô hình cho một họ những kí hiệu dựa trên logic. Ngoài cú

Đồ thị khái niệm trong hình 2.1 biểu diễn câu “John is going to Boston by bus” có thể
được viết ở dạng CGIF mở rộng:
Trong CGIF, khái niệm được đánh dấu bằng những dấu ngoặc vuông và quan hệ khái
niệm được đánh dấu bằng dấu ngoặc đơn. Một chuỗi kí tự bắt đầu với dấu sao, chẳng hạn
như *x đánh dấu một nút định nghĩa mà có thể được tham chiếu bởi cùng một chuỗi bắt
đầu với dấu hỏi, ?x. Những chuỗi này được gọi là chuỗi tên trong Logic tổng quát biểu
diễn những nhãn cùng tham chiếu trong CGIF và những biến trong những phiên bản logic
khác. Sau đây là biểu thức tương đương trong CLIF:
Trong chuẩn CL, CGIF mở rộng được xác định bằng việc biên dịch sang CGIF cốt lõi
được định nghĩa bằng việc biên dịch thành cú pháp trừu tượng CL. Sau đây là CGIF cốt
lõi không định kiểu và CLIF tương ứng cho những ví dụ trên:
Mặc dù CGIF và CLIF nhìn tương tự nhau, chúng có vài sự khác nhau cơ bản:
- Vì CGIF là một biểu diễn tuần tự của đồ thị, những nhãn như x hoặc y biểu diễn
những kết nối giữa những nút trong CGIF nhưng lại la biểu diễn những biến trong
CLIF hoặc tính toán vị từ.
26
- Vì các nút của đồ thị không có trật tự vốn có, một câu CGIF là một danh sách
không có thứ tự của nút. Trừ phi được nhóm bởi dấu ngoặc ngữ cảnh, danh sách
có thể được hoán vị mà không ảnh hưởng đến ngữ nghĩa.
- Toán từ trong CLIF không xuất hiện trong CGIF bởi vì sự kết hợp của những nút
bên trong ngữ cảnh nào đó là không tường minh. Bỏ qua những toán tử kết hợp
trong CGIF có xu hướng giảm số lượng của các dấu ngoặc đơn.
- Vì những nhãn trong CGIF hiển thị những kết nối của nút, chúng có lẽ được bỏ
qua khi chúng không cần thiết. Một cách để giảm số lượng những nhãn là chuyển
những nút khái niệm bên trong những dấu ngoặc của những nút quan hệ.
Khi được viết theo cách này, CGIF trông giống như kí hiệu khung (frame). Tuy
nhiên nó tổng quát hơn khung vì nó có thể biểu diễn ngữ nghĩa đầy đủ của CL.
Hình 3.1 đồ thị khái niệm cho câu “If a cat is on a mat, then it is a happy pet”.
26
Xem xét hình 3.1, đường nét đứt mà kết nối khái niệm [Cat] đến khái niệm [Pet] được gọi

ra là tương đương về logic với một actor của IntergerDivide với những giá trị đầu vào và
đầu ra giống nhau:
26
Mỗi dòng của ví dụ trên mô tả một hoặc nhiều đặc trưng của CGIF. Dòng đầu biểu diễn
những lượng từ tồn tại cho hai thực thể của Function. Trên dòng thứ hai, dấu móc vuông
ngữ cảnh bao những nút khái niệm với những lượng từ với mọi đánh dấu bởi @every. Sự
tương đương trên ba dòng cuối mà một actor của IntergerDivide là sự tương đương logic
với một sự kết hợp của hàm thương số và phần dư. Cuối cùng kí tự # trên hai dòng cuối
trình bày những nhãn đồng tham chiếu ?Quotient và ?Remainder được sử dụng như nhãn
kiểu. Sau đây là CLIF tương đương:
Giới thiệu ngắn trên đã mô tả gần như mội tính năng của CGIF và CLIF. Một tính năng
quan trọng mà chưa được đề cập là việc sử dụng các biến tuần tự để hỗ trợ những quan hệ
với một số tham số thay đổi. Tính năng khác là việc sử dụng của những bình luận mà có
thể được đặt trước, sau hoặc bên trong nút khái niệm hoặc quan hệ trong CGIF. Các đặc
tả trong chuẩn CL đảm bảo rằng một câu bất kì được thể hiện trong bất kì trong 3 phương
ngữ tuân thủ đầy đủ CLIF, CGIF hoặc XCL có thể được dịch thành những dạng khác ở
dạng tương đương về logic. Mặc dù việc dịch sẽ giữ nguyên ngữ nghĩa, không đảm bào
giữ nguyên những toàn chi tiết cú pháp: một câu được dịch từ một phương ngữ thành
phương ngữ khác và sau đó quay lại cái đầu tiên sẽ tương đương logic với cái nguyên
thủy nhưng vài biểu thức con có lẽ được sắp xếp thứ tự lại hoặc được thay thế bởi những
tương đương về ngữ nghĩa.
Nhìn chung, logic tổng quát là một tập bao trùm của những ngôn ngữ dựa trên logic khác
nhau và những kí hiệu bao gồm kí hiệu tính toán vị từ truyền thống cho logic bậc nhất.
Nhưng vì những ngôn ngữ khác nhau đã được thiết kế và được hiện thực tại những thời
điểm và địa điểm cách biệt nhau mà việc khái quát hóa phải thỏa điều kiện với những tổ
chức khác nhau cho mỗi trường hợp sau:
- Ngôn ngữ Web ngữ nghĩa: Chuẩn CL nháp hỗ trợ các URI được định nghĩa bởi W3C
như chuỗi tên CL hợp lệ và nó cho phép văn bản được lưu trữ trên web được nạp vào
trong CLIF, CGIF hoặc những tài liệu XCL. Những công cụ mà nạp văn bản nếu cần có
26

sánh sự phù hợp của các phương án khác nhau. Mỗi qui tắc có một trong ba tác động có
thể trên mối quan hệ logic giữa đồ thị bắt đầu u và đồ thị kết quả v:
- Sự tương đương (equivalence): Sao chép và đơn giản hóa là những qui tắc tương
đương mà sinh ra đồ thị v mà tương đương logic với đồ thị gốc: u ⊃ v và v ⊃ u.
Đồ thị tương đương là đúng chính xác trong các mô hình tương tự.
- Cụ thể hóa (specialization): Kết hợp và giới hạn là những qui tắc cụ thể hóa tạo ra
đồ thị v mà suy ra đồ thị gốc: v ⊃ u. Những qui tắc cụ thể hóa giảm một cách đều
đều tập hợp những mô hình trong đó kết quả là đúng.
- Tổng quát hóa (generalization): Tách rời và không giới hạn là những qui tắc tổng
quát hóa tạo ra đồ thị v được suy ra bởi đồ thị gốc: u ⊃ v. Những qui tắc tổng
quát hóa tăng đều tập những mô hình trong đó kết quả là đúng.
Mỗi qui tắc có một qui tắc nghịch đảo. Nghịch đảo của sao chép là đơn giản hóa, nghịch
đảo của hạn chế là không hạn chế và nghịch đảo của nối là tách rời. Những qui tắc dễ
dàng được trình bày bằng hình ảnh hơn là mô tả.
26
Hình 4.1 qui tắc sao chép và đơn giản hóa.
Đồ thị khái niệm bên trên của hình 4.1 biểu diễn câu “The cat Yojo is chasing a mouse.”.
Mũi tên chỉ xuống biểu diễn hai ứng dụng của qui tắc sao chép. Một ứng dụng sao chép
quan hệ Agnt và ứng dụng thứ hai sao chép đồ thị con → (Thme) → [Mouse]. Liên kết
cùng tham chiếu kết nối hai khái niệm [Mouse] mô tả rằng cả hai khái niệm nói đến cùng
một cá thể. Mũi tên lên biểu diễn hai ứng dụng của luật đơn giản hóa thực thi tác vụ
nghịch đảo của việc xóa những bản sao dư thừa. Sau đây là câu CGIF cho cả hai đồ thị:
26

Hình 4.2 qui tắc hạn chế và không hạn chế.
Đồ thị khái niệm bên trên của hình 4.2 biểu diễn câu “A cat is chasing an animal.”. Bởi
hai ứng dụng của qui tắc hạn chế, nó được biến đổi thành đồ thị khái niệm cho câu “The
cat Yojo is chasing a mouse.”. Trong bước đầu, khái niệm [Cat] nói rằng tồn tại con mèo
được hạn chế bởi tham khảo đến khái niệm đặc trưng hơn [Cat: Yojo] nói rằng tồn tại
một con mèo có tên là Yojo. Trong bước thứ hai, khái niệm [Animal] nói rằng tồn tại một

bởi bất cứ việc tổng quát hóa.
2 (i) Bất cứ đồ thị hoặc đồ thị con trong ngữ cảnh c nào đó có lẽ được sao chép
trong ngữ cảnh giống nhau c hoặc trong ngữ cảnh nào đó được lồng trong c. (Sự
ngoại lệ duy nhất là không có đồ thị được sao chép trực tiếp vào chính nó; tuy
nhiên nó có thể sao chép một đồ thị g trong ngữ cảnh c và sau đó sao chép bản sao
vào bản gốc g).
(e) Bất kì đồ thị hoặc đồ thị con mà có thể được xuất phát từ qui tắc 2(i) có thể
được xóa. (Có hoặc không có đồ thị trong thực tế xuất phát từ qui tắc 2(i) là
không thích hợp).
3 (i) Phủ định kép có thể được rút ra xung quanh đồ thị bất kì hoặc tập hợp của
những đồ thị trong ngữ cảnh nào đó.
(e) Bất kì phủ định kép trong ngữ cảnh nào đó có thể bị xóa.
Phiên bản này của những qui tắc được chuyển thể từ một hướng dẫn về đổ thị hiện sinh
bởi Peirce. Khi những qui tắc này được áp dụng cho CGIF, một số chỉnh sửa có thể cần
để đặt tên lại những nhãn đồng tham chiếu hoặc chuyển đổi một nhãn ràng buộc thành
một nhãn định nghĩa hoặc ngược lại.
Hình 4.4 Minh chứng của tiên đề đầu của Frege bởi những qui tắc của Peirce.
26
Tất cả các tiên đề và qui tắc của suy luận cho logic bậc nhất cổ điển bao gồm những qui
tắc của Principia Mathematia, rút gọn tự nhiên và giải pháp có thể được chứng minh theo
những qui tắc của Peirce. Tiên đề đầu tiên của Frege được viết trong kí hiệu Peirce-Peano
là a ⊃ (b ⊃ a). Trong CGIF cốt lõi, những mệnh đề a và b có thể được biểu diễn như
những quan hệ không có đối số. Sau đây là 5 bước của hình 4.4 được viết dưới dạng
CGIF cốt lõi:
1 Theo qui tắc 3(i), chèn một phủ định kép: ∼[∼[ ]]
2 Theo qui tắc 3(i), chè một phủ định kép vào biểu thức từ bước 1: ∼[ ∼[ ∼[
∼[ ]]]]
3 Theo qui tắc 1(i), chèn (a): ∼[ (a) ∼[ ∼[ ∼[ ]]]]
4 Theo qui tắc 2(i), sao chép (a): ∼[ (a) ∼[ ∼[ ∼[ (a) ]]]]
5 Theo qui tắc 1(i), chèn (b): ∼[ (a) ∼[ ∼[ (b) ∼[ (a) ]]]]

như sau: [*x] (t ?x) [(P [@every*y])].
26
5. Mệnh đề, tình huống và siêu ngữ
Những ngôn ngữ tự nhiên là những hệ thống diễn đạt cao mà có thể phát biểu bất cứ điều
gì mà đã được phát biểu ở dạng ngôn ngữ hình thức hoặc logic nào đó. Chúng thậm chí
có thể diễn đạt những phát biểu siêu cấp độ về bản than chúng, những quan hệ của chúng
đến những ngôn ngữ khác và tính chân thật của những phát biểu bất kì như vậy. Sức
mạnh diễn đạt mạnh như vậy có thể dễ dàng tạo ra những mâu thuẫn và nghịch lí chẳng
hạn như phát biểu “This sentence is false”. Hầu hết những ngôn ngữ hình thức tránh
những nghịch lí như vậy bằng cách đưa ra những hạn chết về sức mạnh diễn đạt.
Mặc dù những nghịch lí của logic là có thể diễn đạt trong ngôn ngữ tự nhiên, việc sử
dung tổng quát nhất của ngôn ngữ về ngôn ngữ là nói về những niềm tin, mong muốn và
ý định của người nói và những người khác. Nhiều phiên bản của logic và ngôn ngữ biểu
diễn tri thức bao gồm đồ thị khái niệm đã được sử dụng để diễn đạt ngôn ngữ này. Ví dụ,
câu “Tom believes that Mary wants to marry a sailor” chứa 3 mệnh đề mà việc lồng của
nó được đánh dấu bằng những móc vuông: Tom believes that [Mary wants [to marry a
sailor]].
Mệnh đề bên ngoài khẳng định rằng Tom có sự tin tưởng được diễn đạt bởi vị ngữ của
động từ believe. Sự tin tưởng của Tom là Mary muốn một tình huống được mô tả bởi lối
vô định được lồng vào mà chủ ngữ của nó là một người giống vậy mà muốn tình huống.
Mỗi mệnh đề tạo ra một bình luận về một mệnh đề hoặc nhiều mệnh đề được lồng trong
nó. Những tham chiếu đến các cá nhân được đề cập trong những mệnh đề đó có thể vượt
qua những ranh giới ngữ cảnh trong những cách khác nhau như trong 2 cách diễn giải sau
của câu tiếng Anh gốc.
Hai đồ thị khái niệm trong hình 5.1 biểu diễn những diễn giải đầu và thứ ba. Trong đồ thị
khái niệm bên trái của hình 5.1, lượng từ tồn tại cho khái niệm [Sailor] được lồng bên
26
trong tình huống mà Mary muốn. Sailor tồn tại hay không và liệu Tom và Mary có biết
danh tính của anh ta hay không là không được xác định. Đồ thị khái niệm bên phải phát
biểu một cách tường minh rằng một sailor như vậy tồn tại; những kết nối của ngữ cảnh và