Bài giảng Hệ chuyên gia (Expert System) - Chương 2: Biểu diễn tri thức nhờ logic vị từ bậc một (Phần 3) - Phan Huy Khánh

HHệệ chuyênchuyên giagia ((ExpertExpert SystemSystem))
 PGS.TS. Phan Huy Khánh
 khanhph@vnn.vn
 Chương 2
 Biểu diễn tri thức
 nhờ logic vị từ bậc một 
 2.3
 Chương 2
 BiBiểểuu didiễễnn tritri ththứứcc nhnhờờ logiclogic vvịị ttừừ bbậậcc mmộộtt
a Phần 2.3 :
 V Lôgic vị từ bậc một
 V Biểu diễn tri thức nhờ logic vị từ bậc một
 2/69
 LimitationsLimitations ofof PropositionalPropositional LogicLogic 22
aa Can'tCan't directlydirectly talktalk aboutabout propertiesproperties ofof individualsindividuals
 oror relationsrelations betweenbetween individualsindividuals
 V E.g., how to represent the fact that John is tall?
aa WeWe havehave nono wayway toto concludeconclude thatthat JohnJohn isis goodgood atat 
 basketballbasketball!! 
aa Generalizations,Generalizations, patterns,patterns, regularitiesregularities can'tcan't easilyeasily bebe 
 representedrepresented
 V E.g., all triangles have 3 sides
 3/69
 PredicatePredicate LogicLogic OverviewOverview
a Predicate Logic
 V Principles
 V Objects
 V Relations
 V properties
a Syntax
a Semantics
a Extensions and Variations
a Proof in Predicate Logic 
a Important Concepts and Terms
 4/69
 AlphabetAlphabet
ConstantsConstants VarialeVariale FunctionFunction PredicatePredicate PP00 ConnectiveConnective QuantifierQuantifier DelimitersDelimiters
 a..za..z A..ZA..Z ff gg hh PP QQ RR ¬∧∨→↔¬∧∨→↔ ∀∃∀∃ ,, (( ))
 TermTerm
 AtomAtom
 ttii
 PP QQ RR
 TermTerm 
 f(tf(t11,, ttnn))
 AtomAtom
 P(tP(t11,, ttnn))
 WffWff
 PP∧∧ QQ →→ RR
 WWffff
 ∃∃XX ∀∀YY (P(X,(P(X, Y)Y) →→ R(Y))R(Y))
 5/69
 BBảảngng kýký hihiệệuu ((AlphabetAlphabet))
a Bảng ký hiệu để xây dựng các biểu thức đúng gồm :
 V Các dấu phân cách (separator signs) :
 dấu phẩy ( , ), dấu mở ngoặc ( ( ) và dấu đóng ngoặc ( ) )
 V Các hằng (constant) : 
 có dạng chuỗi sử dụng các chữ cái in thường a..z
 Ví dụ : a, block 
 V Các biến (variable) :
 có dạng chuỗi sử dụng các chữ cái in hoa A..Z
 Ví dụ : X, NAME. 
 V Các vị từ (predicate) :
 được viết tương tự các biến, sử dụng các chữ cái in hoa A..Z
 Ví dụ : ISRAINING, ON(table), P(X, blue), BETWEEN(X, Y, Z)
 6/69
 BBảảngng kýký hihiệệuu ((AlphabetAlphabet))
a Các phép nối logic (logical connector) :
 V ¬, ∧, ∨, → và ↔
 tương ứng với các phép phủ định, và, hoặc, kéo theo và kéo 
 theo lẫn nhau (tương đương)
a Các dấu lượng tử
 V ∃ lượng tử tồn tại (existential quantifier) 
 V ∀ lượng tử toàn thể (universal quantifier)
 7/69
 NamesNames
a Constants are used to name existing objects:
 V The interpretation identifies the object in the real world
 V No constant can name more than one object
 V An object can have more than one name or no name at all
 Gaius Tiberius
 Sempronius Sempronius
 Honest Abe
 Gracchus Gracchus
 Lincoln
a Variables: Leonard Euler
 V = {X, Y, Z, }
 8/69
 BNFBNF GrammarGrammar PredicatePredicate LogicLogic
 → 
 | ( )
 | , ... 
 | ¬ 
 → (, ...) | = 
 → ( , ...) 
 | | 
 → ∧ | ∨ | → | ↔ 
 → ∀| ∃ 
 → a, b, c, max, carl, jim, jack
 A, B, C, X , X , COUNTER, POSITION
 → A, B, C, X1 , X2, COUNTER, POSITION
 → father-of, square-position, sqrt, cosine
 → P, Q, LARGER, BETWEEN, YOUNGER-THAN
 Ambiguities are resolved through precedence or parentheses
 9/69
 FirstFirst OrderOrder PredicatePredicate LogicsLogics SyntaxSyntax
term ::= variable
 | function_symbol_of_arity_n(t , , t ) n>0
 1 n
 | function_symbol_of_arity_0 constant
atom ::= predicate_symbol_of_arity_n(t1,  , tn) n>0
 | predicate_symbol_of_arity_0 constant
literal ::= atom positive literal 
 | ¬ atom negative literal
wff ::= atom well formed formula (sentence)
 | (¬ wff) negation
 | (wff ∧ wff) conjunction
 | (wff ∨ wff) disjunction
 | (wff → wff) implication
 | (wff ↔ wff) equivalence
 | (∀ variable wff) universal formula
 | (∃ variable wff) existential formula
 10/69
 CCáácc hhààmm (function)(function)
a Các hàm :
 V có cách viết tương tự các hằng
 V sử dụng các chữ in thường a..z
 V Mỗi hàm có bậc (hay số lượng các đối) cố định, là một số 
 nguyên dương
a Ví dụ :
 V f(X), weight(elephan), successor(M, N)
 là các hàm có bậc lần lượt là 1, 1, và 2
a Người ta quy ước rằng :
 V Các hằng là những hàm bậc không (nil)
 V Ví dụ : a, elephan, block là các hằng
 11/69
 FunctionFunction SymbolsSymbols
a Function symbols
 V function_name(arg1, arg2, , argn)
 V Identifies the object referred to by a tuple of objects
 V May be defined implicitly through other functions, or explicitly
 through tables
a Function names begin with a lowercase letter or are 
 expressed with a symbol
 V F = {f, g, h, } = F0 ∪ F1 ∪ F2 ∪ 
a Function arities: 
 V F0: function symbols of arity 0 (constants): a, b, max, jim
 V F1: function symbols of arity 1 (one argument)
 V F2: function symbols of arity 2 (two arguments)
 V 
 12/69
 FunctionsFunctions ExamplesExamples
a A function is used to express complex names
 V age(max) Max’s age
 V password(claire) Claire’s password
a A function may be nested
 V Max’s age’s double double(age(max))
 V father(mother(max)) Max’s mother’s father
 V starship(son(dr_crusher)) Dr_Crusher’s son’s starship
a A function is never a predicate
 V Can’t nest predicates TALL(TALL(max))
a Function symbols of arity >1
 V youngestChild(max, ann) Max and Ann’s youngest child
 V *(5, +(2, 4)) 30
a A predicate forms a sentence,
 while a function names an individual
 13/69
 HHạạng,ng, hayhay hhạạngng ttửử (term)(term)
a Hạng được tạo thành từ hai luật sau :
 V Các hằng và các biến là các hạng
 V Nếu f là một hàm có bậc n ≥ 1
 và nếu t1,..., tn đều là các hạng,
 thì hàm f (t1,..., tn) cũng là một hạng
a Ví dụ các hàm sau đây đều là các hạng :
 V successor(X, Y), weight(b), successor(b, wight(Z))
a Nhưng các hàm sau đây không phải là hạng :
 V P(X, blue) vì P là vị từ
 V weight (P(b))
 vì P(b) không phải là hạng (vị từ không làm đối cho hàm)
 14/69
 PredicatesPredicates
a Predicate symbols :
 V PREDICATE(arg1, arg2, , argn)
 V A (determinate) property possessed by an object: Shape, Size
 V A (determinate) relationship among objects:
 Shape relationship, size relationship, positional relationship
 V The number of arguments is called the predicate’s arity
 V The order of the arguments is important
a Predicates have names beginning with an uppercase letter 
 or are represented by an operator symbol
 V P = P0 ∪ P1 ∪ P2 ∪ 
a Predicate arities: 
 P0: predicate symbols of arity 0 (constants: proposition) : P, Q, R, 
 P1: predicate symbols of arity 1 (one argument)
 P2: predicate symbols of arity 2 (two arguments) 
 15/69
 NguyênNguyên ttửử (atom)(atom)
a Nguyên tử được tạo thành từ hai luật sau :
 V Các mệnh đề (vị từ bậc 0) là các nguyên tử
 V Nếu P là một vị từ bậc n (n ≥ 1)
 và nếu t1,..., tn đều là các hạng,
 thì P(t1,..., tn) cũng là một nguyên tử
a Ví dụ các vị từ sau đây là các nguyên tử :
 V P(X, blue), EMPTY, BETWEEN(table, X, sill(window))
a Còn :
 V successor (X, Y, sill (window) 
 không phải nguyên tử, mà là các hàm
 16/69
 AtomicAtomic SentencesSentences
a A atomic sentence:
 V Expresses a claim that is either true or false
 V Formed by a single predicate followed by one or more arguments
a Example:
 V Max is tall
 TALL(max)
 V A is larger than B
 LARGER(A, B)
 V B is not larger than A
 ¬LARGER(B, A)
 V C is smaller than D, or D is not smaller than C
 SMALLER(C, D), ¬SMALLER(D, C)
 V A is between B and E:
 BETWEEN(A, B, E)
 17/69
 CCáácc côngcông ththứứcc chchỉỉnhnh
a Các công thức chỉnh (CTC) được tạo thành từ ba luật sau :
 V Các nguyên tử là các CTC
 V Nếu G và H là các CTC,
 thì (¬G), (G ∧ H), (G ∨ H), (G → H) và (G ↔ H)
 cũng là các CTC được tạo thành từ G và H
 V Nếu G là một CTC và X là một biến,
 thì (∃X)G và (∀X)G cũng là các CTC
a (∃X)G được đọc là :
 V Tồn tại biến X sao cho G được thoả mãn
a (∀X)G được đọc là :
 V Với mọi biến X thì G đều được thoả mãn
 18/69
 BBààii ttậậpp ởở llớớpp :: ChuyChuyểểnn ththàànhnh vvịị ttừừ
a Ai đủ 18 tuổi mới được phép lái xe
a Gái đủ 18 tuổi, trai 20 tuổi mới được phép lập gia đình
a Kiểm tra hồ sơ
 V Nhập học tại các trường ĐH, CĐ
 V Sản phẩm
 V Quy trình công nghệ...
 Mần reng tui lấy ví dụ ?
 1. Xác định không gian các sự kiện, 
 nhân vật thật liên quan 
 2. Tìm các hằng, biến, hàm và/hoặc vị từ 
 tương ứng với các phát biểu
 3. Gán nghĩa cho tứng thành phần để 
 kiểm tra tính đúng đắn
 4. Nh ận kết quả 
 19/69
 19/69
 WellWell--formedformed FormulaFormula ((wffwff))
a Any atomic sentence is a wff
a If A are B are wffs then so are
 ¬A
 A ∧ B
 A ∨ B 
 A → B 
 A ↔ B 
a B is a cube or B is large (a large cube):
 CUBE(B) ∨ LARGE(B)
a E and C are in the same row and E is in back of B:
 SAMEROW(E, C) ∧ BACKOF(E, B)
 20/69
 EqualityEquality
a Equality indicates that two terms refer to the same object 
 =(A, B)
 V A and B are identical
 V Usually, written in infix form A = B
 V The equality symbol “=“ is an (in-fix) shorthand
 V FATHER(jane) = jim, or =(FATHER(jane), jim)
 V E.g. Jim is Jane’s and John’s father
a Equality by reference and equality by value
 V Sometimes the distinction between referring to the same object 
 and referring to two objects that are identical (indistinguishable) 
 can be important
a E ≠ E E is not identical to iteself
 21/69
 VVíí ddụụ
a Các công thức sau đây là chỉnh :
 V (∃X) (∀Y) ((P(X, Y) ∨ Q(X, Y) → R(X))
 V ((¬(P(a) → P(b))) → ¬P(b))
a Còn các công thức sau đây không chỉnh :
 V (¬(f(a)) : phủ định của một hàm,
 V f (P(a)) : hàm có đối là một vị từ
a Chú ý :
 V CTC được gọi là một trực kiện (literal) hay trị đúng nếu nó là
 một nguyên tử hay có dạng (¬G), với G là một nguyên tử
 V Trong một CTC, trước hoặc sau các ký tự nối, ký tự phân 
 cách, các hằng, các biến, các hàm, các vị từ, người ta có thể 
 đặt tùy ý các dấu cách (space hay blank)
 22/69
 CCáácc bbưướớcc xâyxây ddựựngng CTCCTC
a Cho một phát biểu (sự kiện) trong NNTN :
 V (Chơ ai) đi mô cũng nhớ về Hà Tịnh
a Xác định các miền đối tượng :
 V Người : cu Tý, cu Tèo, cái Nơ X ∈ D1
 V Quê : Hà Tịnh, Hà Tây, Hà Giang Y ∈ D2
a Xác định các quan hệ để xây dựng các mệnh đề
 V Cu Tý quê Hà Tịnh : QUÊ(cutý, hàtịnh), QUÊ(X, Y)
 V Cu Tý xa quê Hà Tịnh : XAQUÊ(cutý, hàtịnh), XAQUÊ(X, Y)
 V Cu Tý nhớ quê Hà Tịnh :
 NHỚQUÊ(cutý, hàtịnh), NHỚQUÊ(X, Y)
a Xây dựng CTC
 V ∀X, ∃Y (QUÊ(X, Y) ∧ XAQUÊ(X, Y) → NHỚQUÊ(X, Y))
 23/69
 PredicatePredicate Logics:Logics: somesome terminologyterminology
a There is a predicate logic for each basis B=(F, P)
 of function and predicate symbols
a Terms formed on basis B are called B-terms:
 the set of all B-terms is denoted TB
a Formulas formed on basis B are called B-formulas:
 the set of all B-formulas is denoted WFFB
a Formulas with all variables bound to a quantifier
 are called closed formulas
a Formulas with no quantifier
 are called quantifier free formulas
a Formulas with no quantifier and no variable
 are called ground formulas
 24/69
 MMộộtt ssốố nhnhậậnn xxéétt 11
a Từ nay ta quy ước rằng, trong một CTC :
 V Một biến được lượng tử hóa sẽ xuất hiện ngay sau ∃ hay ∀
 V Phạm vi lượng tử hóa của biến kể từ vị trí xuất hiện trở đi
 V Có thể có các biến tự do (free variable),
 là các biến không được lượng tử hóa
 V Ví dụ : P(X) và (∃Y) Q(X, Y) có chứa biến tự do X
a Logic vị từ được gọi là «bậc một» (first−order) :
 V Trong CTC không định nghĩa lượng tử cho vị từ hay cho hàm
 V Ví dụ : (∀P)P(a) và (∀f) (∀f) (∀X) P(f (X), b)
 không phải là những vị từ bậc một,
 mà có bậc cao hơn (higher-order) 
 25/69
 MMộộtt ssốố nhnhậậnn xxéétt 22
a Tri thức diễn tả theo ngôn ngữ tự nhiên hay toán học 
 không phải luôn luôn dễ dàng chuyển đổi thành các CTC 
 trong lôgic vị từ bậc một
a Chẳng hạn, để diễn tả rằng :
 «Nếu hai vật y chang nhau thì chúng có cùng tính chất», 
 người ta có thể viết :
 (∀P) (∀X) (∀Y) (EQUAL(X, Y) → (P(X) ↔ P(Y)))
a Nhưng biểu thức trên không phải là logic v ị từ bậc một
 vì có lượng tử ∀ áp dụng cho một ký tự vị từ là P
a Trong lôgic vị từ bậc một, sự kiện trên được viết :
 (∀X) (∀Y) (SAME_P(X, Y) → (P(X) ↔ P(Y))), hoặc
 (∀X) (∀Y) (SAME_P(X, Y) → (HAVE(X, p) ↔ HAVE (Y, p)))
 26/69
 Example:Example: FamilyFamily RelationshipsRelationships
a Objects: people
a Properties: gender, 
 V Expressed as unary predicates:
 MALE(X), FEMALE(Y) hoặc SEX(X, male), SEX(Y, female)
a Relations: parenthood, brotherhood, marriage
 V Expressed through binary predicates
 PARENT(X, Y), BROTHER(X, Y), 
a Functions: motherhood, fatherhood
 V Because every person has exactly one mother and one father:
 mother(X), father(Y)
 V There may also be a relation
 mother-of(X, Y), father-of(X, Y)
 27/69
 AtomicAtomic SentencesSentences TranslationTranslation
a Function translation:
 V Brando is Nancy’s favorite actor:
 brando = favoritecctor(nancy)
 V Sean is his own favorite actor
 sean = favoriteactor(sean)
a Sentences Translation:
 V Nancy’s favorite actor is better than Max’s favorite actor:
 BETTERACTOR(favoriteactor(nancy), favoriteactor(max))
 28/69
 ExamplesExamples AtomicAtomic SentencesSentences
FATHER(jack, john), MOTHER(jill, john), SISTER(jane, john)
PARENTS(jack, jill, john, jane)
MARRIED(jack, jill)
MARRIED(father-of(john), mother-of(john))
MARRIED(father-of(john), mother-of(jane))
FATHER(jack, john) ∧ MOTHER(Jill, john) ∧ SISTER(jane, john)
¬ SISTER(john, jane) 
PARENTS(jack, jill, john, jane) ∧ MARRIED(jack, jill)
PARENTS(jack, jill, john, jane) → MARRIED(jack, jill)
OLDER-THAN(jane, john) ∨ OLDER-THAN(john, jane)
OLDER(father-of(john), 30) ∨ OLDER (mother-of(john), 20)
 29/69
 AvoidAvoid AmbiguityAmbiguity
a Both C and E are cubes
 CUBE(c) ∧ CUBE(e)
a Either C or E is a cube
 CUBE(c) ∨ CUBE(e)
a Neither C nor E is a cube
 ¬(CUBE(c) ∨ CUBE(e))
a Both A or B and C
 A ∨ B ∧ C
a Either A or both B and C
 A ∨ (B ∧ C)
a Either both A and B or C
 A ∧ B ∨ C 
a Both A and either B or C
 A ∧ (B ∨ C)
a Either both Max is at home and Claire is tall or Carl is happy
 (HOME(max) ∧ TALL(claire)) ∨ HAPPY(carl)
 30/69
 QuantifiersQuantifiers
a Quantifiers can be used to express properties of collections 
 of objects
a Quantifiers eliminates the need to explicitly enumerate all 
 objects
a The universal quantifier, represented by the symbol ∀
 means “for every” or “for all”
a The existential quantifier, represented by the symbol ∃
 means “there exists”
a Limitations of predicate logic – most quantifier
 31/69
 UniversalUniversal QuantifiersQuantifiers ∀∀ (for(for all)all)
a ∀X P(x) states that
 V a predicate P is holds for all objects X in the universe (domain) 
 under discourse
 V The sentence is true if and only if all the individual sentences 
 where the variable X is replaced by the individual objects it can 
 stand for are true
a Example
 V All dogs are happy
 ∀ X (DOG(X) → HAPPY(X))
 V No dog is happy 
 All dogs are unhappy
 ∀ X (DOG(X) → ¬HAPPY(X))
 32/69
 UsageUsage ofof UniversalUniversal QualificationQualification
a Universal quantification is frequently used to make 
 statements like:
 V “all humans are mortal”
 V “all cats are mammals”
 V “all birds can fly” 
a T ...  H) 
 V ? 
 ∀X MALE(X) ↔ ¬FEMALE(X)
 V ? 
 ∀G, ∀C GRANDPARENT(G, C) ↔ ∃P PARENT(G, P) ∧ PARENT(P, C) 
 V ? 
 ∀X, ∀Y SIBLING(X, Y) ↔
 ¬(X=Y) ∧ ∃P PARENT(P, X) ∧ PARENT(P, Y)
 39/69
 TranslatingTranslating EnglishEnglish toto FOLFOL
a Every gardener likes the sun
 ∀X GARDENER(X) → LIKES(X, sun) 
a You can fool some of the people all of the time
 ∃X ∀T (PERSON(X) ∧ TIME(T)) → CAN-FOOL(X, T)
a You can fool all of the people some of the time
 ∀X ∃T (PERSON(X) ∧ TIME(T) → CAN-FOOL(X, T) 
a All purple mushrooms are poisonous 
 ∀X (MUSHROOM(X) ∧ PURPLE(X)) → POISONOUS(X)
a No purple mushroom is poisonous 
 ¬(∃X) PURPLE(X) ∧ MUSHROOM(X) ∧ POISONOUS(X) 
 or, equivalently, 
 (∀X) (MUSHROOM(X) ∧ PURPLE(X)) → ¬POISONOUS(X) 
 40/69
 TranslatingTranslating EnglishEnglish toto FOLFOL
a There are exactly two purple mushrooms
 (∃X)(∃Y) MUSHROOM(X) ∧ PURPLE(X) ∧ MUSHROOM(Y) ∧ PURPLE(Y) 
 ∧ ¬(X=Y) ∧ (∀Z) (MUSHROOM(Z) ∧ PURPLE(Z))
 →
 ((X=Z) ∨ (Y=Z))
a Bob is not tall 
 ¬TALL(bob)
a X is above Y if X is on directly on top of Y or else there is a 
 pile of one or more other objects directly on top of one 
 another starting with X and ending with Y
 (∀X)(∀Y) ABOVE(X, Y) ↔ (ON(X, Y) ∨ (∃Z) (ON(X, Z) ∧ ABOVE(Z, Y))) 
 41/69
 ColonelColonel WestWest ExampleExample
a Assume:
 V It is a crime for an American to sell weapons to a hostile nation.
 The country Nono, an enemy of America, has some missiles, and 
 all its missiles were sold to it by Colonel West, who is an American
 V Constants: nono, america, west
 V Predicates: CRIMINAL, AMERICAN, WEAPON, HOSTILE, NATION, 
 ENEMY, MISSILE, OWNS, SELLS
a Then
 V It is a crime for an American to sell weapons to a hostile nation
 ⇒ If any american X sells any weapon Y to any hostile nation Z, then 
 that american X is a criminal
 ∀∀ X,Y,ZX,Y,Z (AMERICAN(X)(AMERICAN(X) ∧∧ WEAPON(Y)WEAPON(Y) ∧∧ NATION(Z)NATION(Z) 
 ∧∧ HOSTILE(Z)HOSTILE(Z) ∧∧ SELLS(X,SELLS(X, Z,Z, Y)Y) →→ CRIMINAL(X))CRIMINAL(X))
 42/69
 OtherOther TranslatingTranslating
a Nono’s missiles
 V Nono has some missiles
 ∃∃ XX (MISSILE(X)(MISSILE(X) ∧∧ OWNS(nono,OWNS(nono, X))X))
 V All of Nono’s missiles were sold to it by West
 ⇒ If X is a missile owned by Nono then West sold X to Nono
 ∀∀ XX ((((MISSILE(X)MISSILE(X) ∧∧ OWNS(nono,OWNS(nono, X))X)) →→ SELLS(west,SELLS(west, nono,nono, X))X))
a The other facts 
 V An enemy of America is hostile
 ∀∀ XX (ENEMY(X,(ENEMY(X, america)america) →→ HOSTILE(X))HOSTILE(X))
 V West is an American 
 AMERICAN(west)AMERICAN(west)
 V Nono is an enemy of America
 NATION(nono)NATION(nono) ∧∧ NATION(america)NATION(america) ∧∧ ENEMY(nono,ENEMY(nono, america)america)
 43/69
 OtherOther ExamplesExamples
a Love 
 V There is a girl who is loved by every boy
 ⇒ There is a girl X and if Y is a boy then Y loves her
 ∃∃XX (GIRL(X)(GIRL(X) ∧∧∀∀Y(BOY(Y)Y(BOY(Y) →→ LOVES(Y,X)))LOVES(Y,X)))
 V Every boy loves some girl 
 V For every boy Y there exists a girl X that he loves
 ∀∀Y(BOY(Y)Y(BOY(Y) →→∃∃XX (GIRL(X)(GIRL(X) ∧∧ LOVES(Y,X)))LOVES(Y,X)))
a Socrates Example 
 V All men are mortal
 ∀∀XX (MAN(X)(MAN(X) →→ MORTAL(X))MORTAL(X))
 V Socrates is a man 
 MAN(socrates)MAN(socrates)
 V Socrates is mortal
 MORTAL(socrates)MORTAL(socrates)
 44/69
 CuriosityCuriosity ExampleExample
a Assume:
 Jack owns a dog
 Every dog owner is an animal lover
 No animal lover kills an animal
 Either Jack or Curiosity killed the cat
 The cat’s name is Tuna
 Then
 V Constants: jack, curiosity, tuna.
 V Predicates: OWNS, DOG, ANIMALLOVER, KILLS, ANIMAL
 45/69
 CuriosityCuriosity ExampleExample
a Dog owners
 V Jack owns a dog
 ⇒ Some dog is owed by Jack
 ∃∃ XX (DOG(X)(DOG(X) ∧∧ OWNS(jack,OWNS(jack, X))X))
 V Every dog owner is an animal lover
 ∀∀ XX ((((∃∃ YY (DOG(Y)(DOG(Y) ∧∧ OWNS(X,Y)))OWNS(X,Y))) →→ ANIMALLOVER(X))ANIMALLOVER(X))
aaAnimalAnimal LoversLovers 
 V No animal lover kills an animal
 ⇒ An animal lover does not kill an animal
 ⇒ For any animal lover X and any animal Y,
 then Y is not killed by X 
 ∀∀ X,X, YY ((ANIMALLOVER(X)((ANIMALLOVER(X) ∧∧ ANIMAL(Y))ANIMAL(Y)) →→ ¬¬KILLS(X,Y))KILLS(X,Y))
 46/69
 CuriosityCuriosity ExampleExample
aaCatCat KnowledgeKnowledge
 V The cat’s name is Tuna
 CAT(tuna)CAT(tuna)
 V Either Jack or Curiosity killed the cat
 KILLS(jack,KILLS(jack, tuna)tuna) ∨∨ KILLS(curiosity,KILLS(curiosity, tuna)tuna)
 V All cats are animals 
 ∀∀XX CAT(X)CAT(X) →→ ANIMAL(X)ANIMAL(X)
 47/69
 BBààii ttậậpp 11
a Cho các câu sau :
 V Marcus là một người
 V Marcus là người xứ Pompeii
 (hay xứ Campanie gần Naple nước Ý)
 V Mọi người Pompeii đều là người La Mã
 V Ceasar là một kẻ cầm quyền
 V Người La Mã hoặc là trung thành với Ceasar,
 hoặc là thù ghét Ceasar
 V Mỗi người đều trung thành với một người nào đó
 V Nhân dân chỉ muốn giết những kẻ cầm quyền
 mà họ không trung thành
 V Marcus muốn giết Ceasar
a Biểu diễn các câu trên thành các wff’s
 48/69
 BiBiểểuu didiễễnn wffwff’’ss trongtrong lôgiclôgic vvịị ttừừ
a Marcus là một người 
 MAN(marcus)
a Marcus là một người Pompeii
 POMPEIAN(marcus)
a Mọi người Pompeian đều là người La Mã
 ∀x : POMPEIAN(X) → ROMAN(X)
a Caesar là một kẻ cầm quyền 
 (giả sử không có sự trùng tên)
 RULER(caesar)
a Người La Mã hoặc là trung thành với Caesar,
 hoặc là thù ghét Caesar
 ∀x : ROMAN(X) → LOYALTO(X, caesar) ∨ HATE(X, caesar)
a Tuy nhiên khi sử dụng vớ i nghĩa hoặc có loại trừ, c ó thể viết lại :
 ∀x : ROMAN(X) → ((LOYALTO(X, caesar) ∧ HATE(X, caesar)) ∧
 (¬LOYALTO(X, caesar) ∧ HATE(X, caesar))) 
 49/69
 BiBiểểuu didiễễnn wffwff’’ss trongtrong lôgiclôgic vvịị ttừừ
a Mọi người đều trung thành với một người nào đó
 ∀X, ∃Y LOYALTO(X, Y) hoặc ∃Y, ∀X LOYALTO(X, Y)
a Nhân dân chỉ muốn giế t những kẻ cầm quyền
 mà họ không trung thành
 ∀X, ∀Y PERSON(X) ∧ RULER(Y) ∧ TRYASSASSINATE(X, Y) →
 LOYALTO(X, Y)
 ¬LOYALTO(X, Y) 
 Mệnh đề này tỏ ra mập mờ (ambiguous). Có phải chỉ những kẻ cầm 
 quyền mà nhân dân muốn giết là những kẻ họ không trung thành (theo 
 nghĩa đã biểu trưng) hay chỉ những điều mà nhân dân có ý định là giết 
 những kẻ cầm quyền mà họ không trung thành ?
a Marcus muố n giết Ceresar 
 V TRYASSASSINATE(marcus, caesar)
a Câu hỏi : Marcus có trung thành với Caesar không ?
 50/69
 BBààii ttậậpp 22
a Cho các câu sau :
 V Marcus là một người
 V Marcus là người Pompeii
 V Marcus sinh năm 40 trong công nguyên (A.D.: Anno Domini)
 V Mọi người đều (ai cũng phải) chết
 V Tất cả mọi người dân Pompeii đều bị chết
 vì núi lửa phun vào năm 79 A.D.
 V Không có người nào (không ai) sống nhiều hơn 150 tuổi
 V Bây giờ là năm 2007
 V Còn sống có nghĩa là không chết
 V Nếu ai đó chết, thì người ấy có thể chết ở mọi thời điểm sau đó
 V Marcus còn sống không ?
a Biểu diễn các câu trên thành các wff’s
 51/69
a Marcus là một người
 MAN(marcus)
a Marcus là người Pompeii
 POMPEIAN (marcus)
a Marcus sinh năm 40 trong công nguyên
 (A.D.: Anno Domini)
 BORN(marcus, 40)
a Mọi người đều (ai cũng phải) chết
 ∀X MAN(X) Ø MORTAL(X)
a Tất cả mọi ngườ i dân Pompeii đều bị chết
 vì núi lửa phun vào năm 79 A.D.
 ∀X ERUPTED(vocalno, 79) ∧ POMPEIAN(X) Ø DIED(X, 79)
 52/69
a Không có người nào (không ai) sống nhiều hơn 150 tuổi
 ∀X ∀T1 ∀T2
 MAN(X) ∧ BORN(X, T1) ∧ GT(T2 - T1, 150) Ø DIED(X, T2)
 MAN(X) ∧ BORN(X, T1) ∧ GT(T2 - T1, 150) Ø DIED(X, T2)
a Bây giờ là năm 2007 
 now = 2007
a Còn sống có nghĩa là không chết
 ∀X ∀T (ALIVE(X, T) Ø ¬DEAD(X, T))
 ∧ ( (DIED(X, T) Ø ¬ ALIVE(X, T)) 
a Nếu ai đó ch ết, 
 thì người ấy có thể chết ở mọi thời điểm sau đó
 ∀X ∀T1 ∀T2 DIED(X, T1) ∧ GT(T2, T1) Ø DEAD(X, T2)
 53/69
 DiDiễễnn gigiảảii (Interpretation)(Interpretation)
a Cho G là một CTC, một diễn giải của G, ký hiệu I, được xác 
 định từ năm bước sau đây :
 V Chọn miền diễn giải (Interpretation Domain) là các tập hợp 
 khác rỗng, ký hiệu D ≠ ∅
 V Gán (Assignation) cho mỗi hằng của G một phần tử của Di
 V Gán cho mỗi mệnh đề (hay vị từ bậc 0)
 một giá trị true (T) hoặc false (F)
 V Gán cho mỗi vị từ bậc n (n≥1) ánh xạ từ Dn lên { T, F } :
 n
 P (T1,... Tn) : D → { T, F }
 V Gán cho mỗi hàm bậc n (n≥1) ánh xạ từ Dn lên D :
 n
 f(X1,... Xn) : D → D
 54/69
 MôMô hhììnhnh didiễễnn gigiảảii II ttừừ GG lênlên DD 
 GG
 MMệệnhnh đđềề
 HHằằngng VVịị ttừừ bbậậcc nn HHàmàm bbậậcc nn
 (v(vịị ttừừ bbậậcc 0)0)
 a..za..z P(TP(T1,...,... TTn)) f(Xf(X1,...,... XXn))
 P,P, QQ 1 n 1 n 
 DD ≠≠∅∅ {{ T,T, FF }} DDnn →→ {{ T,T, FF }} DDnn →→ DD
a Khi một CTC G có giá trị là T theo một diễn giải I, 
 người ta nói rằng diễn giải I là một mô hình của G
 55/69
 QuanQuan hhệệ TranslationTranslation--InterpretationInterpretation
 Translation Interpretation
 Ngôn ngữ Ngôn ngữ
 Ngôn ngữ lôgic vị từ diễn giải
 tự nhiên WFF D, {T, F}
 Application
QuêQuê hhươươngng mmỗỗii ngngườườii chchỉỉ mmộột,t,
nhnhưư làlà chchỉỉ mmộộtt mmẹẹ thôithôi TT
 ∀∀XX∃∃YY∃∃ZZ (QUE(X,Y)(QUE(X,Y) ∧∧ (QUE(X,Z)(QUE(X,Z) →→ EQ(Y,Z))EQ(Y,Z)) 
 ↔↔
 ∀∀TT∃∃UU∃∃VV (FEMALE(U)(FEMALE(U) ∧∧ (MOTHER(U,T))(MOTHER(U,T)) 
 ∧∧ (FEMALE(V)(FEMALE(V) ∧∧ (MOTHER(V,T))(MOTHER(V,T)) →→
 EQ(U,V))EQ(U,V)) 
 56/69
 TTíínhnh gigiáá trtrịị ccủủaa CTCCTC theotheo didiễễnn gigiảảii
a Cho G là một CTC và một diễn giải I trên một miền D
a Khi đó :
 V Nếu G là một mệnh đề, giá trị gán cho G qua I là I(G)
 V Nếu G là một trực kiện, G nhận một giá trị T hay F
 V Nếu G có dạng (∀X)G’ :
 ™ I(G) = T nếu I(G’) = T cho mọi giá trị của biến X trong D
 ™ I(G) = F nếu không phải
 V Nếu G có dạng (∃X)G’ :
 ™ I(G) = T nếu I(G’) = T với ít nhất một giá trị của X trong D
 ™ I(G) = F nếu không phải
 57/69
 TTíínhnh gigiáá trtrịị ccủủaa CTCCTC theotheo didiễễnn gigiảảii (ti(tiếếp)p)
a Nếu G có dạng (¬ G’) :
 V I(G) = T nếu I(G’) = F trong D
 V I(G) = F nếu I(G’) = T trong D
a Nếu G có dạng (G’ ∧ G’’), hoặc (G’ ∨ G’’),
 hoặc (G’ → G’’), hoặc (G’ ↔ G’’), khi đó :
 G’ G’’ (G’ ∧ G’’) (G’ ∨ G’’) G’ → G’’ G’ ↔ G’’
 F F F F T T 
 F T F T T F
 T F F T F F
 T T T T T T
 58/69
 TTíínhnh hhợợpp ththứứcc vvàà ttíínhnh nhnhấấtt ququáánn 
aMột CTC được gọi là :
 V Hằng đúng (tautology), hay hợp thức (valid)
 nếu và chỉ nếu mọi diễn giải đều cho giá trị T
 V Nếu không, được gọi là không hợp thức (non−valid) 
aMột CTC được gọi là :
 V Mâu thuẫn (contradiction), hay không nhất quán (inconsistent)
 nếu và chỉ nếu với mọi diễn giải đều cho giá trị F
 V Nếu không, được gọi là nhất quán (consistent)
aQuy ước :
 V  biểu diễn một CTC hợp thức-hằng đúng
 V ∇ biểu diễn một CTC mâu thuẫn-không nhất quán
 59/69
 CôngCông ththứứcc ttươươngng đươđươngng
a Cho G và H là hai CTC
a G và H được gọi là tương đương, G ≡ H :
 V Nếu và chỉ nếu G và H có cùng giá trị (T hoặc F)
 cho mọi diễn giải I, I(G) = I(H)
a Ví dụ :
 V (P(a) → Q(b)) ≡ ((¬P(a) ∨ Q(b))
a Có thể dùng bảng chân lý
 để kiểm tra tính tương đương của các CTC
 60/69
 BBảảngng ccáácc côngcông ththứứcc ttươươngng đươđươngng
Công thức tương đương Tên công thức
(G → H) ((¬G) ∨ H)
(G ↔ H) ((G → H) ∧ (H → G))
(¬(¬ G)) G 
(¬(G ∧ H)) ((¬G) ∨ (¬H))
 Luật De Morgan
(¬(G ∨ H)) ((¬G) ∧ (¬H)) 
((G ∧ (H ∨ K)) ((G ∧ H) ∨ (G ∧ K))
 Luật phân phối
((G ∨ (H ∧ K)) ((G ∨ H) ∧ (G ∨ K)) 
(G ∧ H) (H ∧ G) 
 Luật giao hoán
(G ∨ H) (H ∨ G) 
((G ∨ H) ∨ K) (G ∨ (H ∨ K)) Luật kết hợp cho phép loại bỏ
 dấu ngoặc
((G ∧ H) ∧ K)) (G ∧ (H ∧ K)) 
(G → H) ((¬H) → (¬G)) Luật đối vị
 61/69
 BBảảngng ccáácc côngcông ththứứcc ttươươngng đươđươngng
Công thức tương đương Tên công thức
(G ∧ ) G
(G ∧ ∇) ∇
(G ∨ ) 
(G ∨ ∇) G
(G ∨ (¬G)) 
(G ∧ (¬G)) ∇
(∀X)(G(X)) (∀Y)(G(Y))
 Luật dùng chung các biến
(∃X)(G(X)) (∃Y)(G(Y))
(∃X)(G(X)) (∃Y)(G(Y))
¬((∀X)G(X)) (∃Y)(¬G(Y))
¬((∃X)G(X)) (∀Y)(¬G(Y))
(∀X)(G(X) ∧ H(X)) ((∀X)G(X) ∧ (∀Y)H(Y))
(∃X)(G(X)) ∨ H(X)) (( ∃X)G(X) ∨ (∃Y)H(Y)) 
 62/69
 Biến đổi các CTC : loại bỏ lượng tử ∀∀ vvàà ∃∃
a Standardize Variables
 V Make sure that you are not using the same variable name twice 
 in a single sentence (unless you really meant to)
 Eg. 
 (∀X P(X)) ∨ (∃X Q(X)) becomes (∀X P(X)) ∨ (∃Z Q(Z))
a Move all quantifiers left, but keep them in order! 
 V Eg.
 (∀X P(X) ∨ ∃Y Q(Y)) becomes (∀X ∃Y P(X) ∨ Q(Y))
a Translation into the form: 
 QQ MM
 with Q: quantifiers, in order ∀s and then ∃s
 M: Matrix: wffs including V, : Variable 
 63/69
 Biến đổi các CTC
a Skolemize: Eliminate Existential Quantifiers
 V Existential quantifiers can be eliminated by the introduction
 of a new constant that does not appear elsewhere
 in the database
 V SUBST{ X|a, a∈D } /* Substitution
 V Eg.Eg.
 ∃X P(X) becomes P(a) 
 “Có người vào lớp muộn”
 “Có người vào lớp muộn” 
 becomes “Cu Tý vào lớp muộn”
 becomes “ Cu Tý vào lớp muộn”
 ∃X P(X) ∨ Q(X) becomes P(a) ∨ Q(a)
 “Chàng tìm đ ồng kia bãi nọ” 
 becomes
 becomes 
 “Chàng tìm đồng dưới đồng trên”
 “Chàng tìm đồng dưới đồng trên ”
 64/69
 Biến đổi các CTC
a Skolemize: Drop Existential Quantifiers
 V One possible complication occurs if we also have Universal 
 quantifiers Consider
 ∀X PERSON(X) → ∃Y (HEART(Y) ∧ HAS(X, Y))
 becomes by SUBST{Y|h}: 
 ∀X PERSON(X) → HEART(h) ∧ HAS(X, h)
 V Instead we have to create a new (Skolem) function to map from a 
 person to their HEART(f(x))
 ∀X ∃Y PERSON(X) → (HEART(Y) ∧ HAS(X, Y)) becomes: 
 ∀X PERSON(X) → HEART(f(X)) ∧ HAS(X, f(X))
 Eg., in general:
 ∀X ∀Y ∀Z ... ∃T ... P(X, Y, Z,...T,...) becomes: 
 ∀X ∀Y ∀Z ... P(X, Y, Z,...f(X, Y, Z,...),...) 
a Drop all Universal Quantifiers in the end:
 V ∀X ∀Y ∀Z... P(X, Y, Z,...) becomes: P(X, Y, Z,...)
 65/69
 Biến đổi các CTC
a Move the ↔:
 V P ↔ Qbecomes (P → Q) ∧ (Q → P)
a Distribute ∧ over ∨
 V (A ∧ B) ∨ Cbecomes (A ∨ C) ∧ (A ∨ B) 
 V Just like distribution in arithmetic 
 V (5 + 4) * 6 becomes (5 * 6 ) + (4 * 6 )
a Flatten nested conjunctions and disjunctions
 V (A ∧ B) ∧ Cbecomes (A ∧ B ∧ C) 
 V (A ∨ B) ∨ Cbecomes (A ∨ B ∨ C)
 66/69
 Done!!Done!!
a Biến đổi các CTC :
 V Standardize Variables
 V Move the ↔
 V Move Quantifiers left
 V Skolemize:
 ™ Eliminate Existential Quantifiers
 ™ Drop Universal Quantifiers
 V Distribute ∧ over ∨
 V Flatten nested conjunctions and disjunctions
a Attention:
 V In Proof Theory by Robinson Resolution, they need to before:
 ™ Eliminate Implications
 ™ Move ¬ inwards
 67/69
 XâyXây ddựựngng ccơơ ssởở luluậậtt chocho HCGHCG
a Sự kiện 1 : 
 V Con mèo mà trèo cây cau
 Hỏi thăm chú chuột đi đâu vắng nhà
 Chú chuột đi chợ đường xa
 Mua mắm, mua muối về giỗ cha con mèo
a Hỏi :
 V Mèo có ăn đuợc (gặp) chuột không rứa ?
a Sự kiện 2 :
 V Ông Trăng mà lấy bà Trời
 Tháng Năm đi cưới, tháng Mười nộp cheo
 Làng xã làm thịt một con mèo
 Làng ăn không hết làng treo cột đình
 Ông Xã đánh trống thình thình
 Bao nhiêu con nít ra đình gặm xương
a Hỏi :
 V Cu Tý có gặm đuợc xương không rứa ?
 68/69
 TTạạoo khôngkhông giangian :: ccáácc mimiềềnn xxáácc đđịịnhnh
aaSSựự kikiệệnn 11 ::
 V Con mèo mà trèo cây cau : TREO(X, Y)
 V Hỏi thăm chú chuột đi đâu vắng nhà :THAM(X, Y), VANGNHA(X)
 V Chú chuột đi chợ đường xa
 V Mua mắm, mua muối về giỗ cha con mèo
 cau
 cha_mèo
 mèo
 chuột mắm Các vật
 muối
 Các con vật
 Gợi ý dùng luật :
 MEO(X) ∧ CHUOT(Y) ∧ THAM(X, Y) ∧ COONHA(Y) → ANTHIT(X,Y)
 69/69