




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、智能计算研究中心X. First order logic (FOL) Autumn 2012Instructor: Wang XiaolongHarbin Institute of Technology, Shenzhen Graduate SchoolIntelligent Computation Research Center(HITSGS ICRC)2Outline Why FOL? Syntax and semantics of FOL Using FOL Wumpus world in FOL Knowledge engineering in FOL3Pros and cons of
2、 propositional logicJ Propositional logic is declarativeJ Propositional logic allows partial/disjunctive/negated information (unlike most data structures and databases)J Propositional logic is compositional: meaning of B1,1 P1,2 is derived from meaning of B1,1 and of P1,2J Meaning in propositional l
3、ogic is context-independent (unlike natural language, where meaning depends on context) Propositional logic has very limited expressive power (unlike natural language) E.g., cannot say pits cause breezes in adjacent squares“ except by writing one sentence for each square4First-order logic Whereas pr
4、opositional logic assumes the world contains facts First-order logic (like natural language) assumes a car contains Objects: people, houses, numbers, colors, baseball games, wars, Relations: red, round, prime, brother of, bigger than, part of, comes between, Functions: father of, best friend, one mo
5、re than, plus, 5Examples:“One plus two equals three”Objects:Relations:Properties:Functions:“Squares neighboring the Wumpus are smelly”Objects:Relations:Properties:Functions:6Examples:“One plus two equals three”Objects:one, two, three, one plus twoRelations:equalsProperties:-Functions:plus (“one plus
6、 two” is the name of the object obtained by applying function plus to one and two;three is another name for this object)“Squares neighboring the Wumpus are smelly”Objects:Wumpus, squareRelations:neighboringProperties:smellyFunctions:-7Semanticsthere is a correspondence between functions, which retur
7、n values predicates, which are true or falseFunction: father_of(Mary) = BillPredicate: father_of(Mary, Bill)8Syntax of FOL: Basic elements ConstantsKingJohn, 2, HIT,. PredicatesBrother, ,. FunctionsSqrt, LeftLegOf,. Variablesx, y, a, b,. Connectives, , , , Equality= Quantifiers , 9Atomic sentencesAt
8、omic sentence =predicate (term1,.,termn) or term1 = term2Term =function (term1,.,termn) or constant or variable E.g., Brother(KingJohn,RichardTheLionheart) (Length(LeftLegOf(Richard), Length(LeftLegOf(KingJohn)10Complex sentences Complex sentences are made from atomic sentences using connectivesS, S
9、1 S2, S1 S2, S1 S2, S1 S2,E.g. Sibling(KingJohn,Richard) Sibling(Richard,KingJohn) (1,2) (1,2) (1,2) (1,2) 11Truth in first-order logicSentences are true with respect to a model and an interpretationModel contains objects (domain elements) and relations among themInterpretation specifies referents f
10、orconstant symbols objectspredicate symbols relationsfunction symbols functional relationsAn atomic sentence predicate(term1,.,termn) is trueiff the objects referred to by term1,.,termnare in the relation referred to by predicate12Models for FOL: Example13Universal quantification Everyone at HIT is
11、smart:x At(x,HIT) Smart(x) x P is true in a model m iff P is true with x being each possible object in the model Roughly speaking, equivalent to the conjunction of instantiations of PAt(KingJohn, HIT) Smart(KingJohn) At(Richard, HIT) Smart(Richard) At(HIT, HIT) Smart(HIT) .14A common mistake to avoi
12、d Typically, is the main connective with Common mistake: using as the main connective with :x At(x, HIT) Smart(x)means “Everyone is at HIT and everyone is smart”15Existential quantification Someone at HIT is smart:x At(x, HIT) Smart(x) x P is true in a model m iff P is true with x being some possibl
13、e object in the modelRoughly speaking, equivalent to the disjunction of instantiations of PAt(KingJohn, HIT) Smart(KingJohn) At(Richard, HIT) Smart(Richard) At(HIT, HIT) Smart(HIT) .16Another common mistake to avoid Typically, is the main connective with Common mistake: using as the main connective
14、with :x At(x, HIT) Smart(x)is true if there is anyone who is not at HIT!17Properties of quantifiersx y is the same as y xx y is the same as y x x y is not the same as y xx y Loves(x,y) “There is a person who loves everyone in the world”y x Loves(x,y) “Everyone in the world is loved by at least one p
15、erson”Quantifier duality: each can be expressed using the otherx Likes(x,IceCream) x Likes(x,IceCream)x Likes(x,Broccoli) x Likes(x,Broccoli)18Equalityterm1 = term2 is true under a given interpretation if and only if term1 and term2 refer to the same object E.g., definition of Sibling in terms of Pa
16、rent:x,y Sibling(x,y) (x = y) m,f (m = f) Parent(m,x) Parent(f,x) Parent(m,y) Parent(f,y)19Using FOLThe kinship domain: Brothers are siblingsx,y Brother(x,y) Sibling(x,y) Ones mother is ones female parentm,c Mother(c) = m (Female(m) Parent(m,c) “Sibling” is symmetricx,y Sibling(x,y) Sibling(y,x)20Us
17、ing FOLThe set domain: s Set(s) (s = ) (x,s2 Set(s2) s = x|s2)x,s x|s = x,s x s s = x|sx,s x s y,s2 (s = y|s2 (x = y x s2)s1,s2 s1 s2 (x x s1 x s2)s1,s2 (s1 = s2) (s1 s2 s2 s1)x,s1,s2 x (s1 s2) (x s1 x s2)x,s1,s2 x (s1 s2) (x s1 x s2)21Interacting with FOL KBsSuppose a wumpus-world agent is using an
18、 FOL KB and perceives a smell and a breeze (but no glitter) at t=5:Tell(KB,Percept(Smell,Breeze,None,5)Ask(KB,a BestAction(a,5)I.e., does the KB entail some best action at t=5?Answer: Yes, a/Shoot substitution (binding list)Given a sentence S and a substitution , S denotes the result of plugging int
19、o S; e.g.,S = Smarter(x,y) = x/Hillary,y/BillS = Smarter(Hillary,Bill)Ask(KB,S) returns some/all such that KB 22Knowledge base for the wumpus world Perception t,s,b Percept(s,b,Glitter,t) Glitter(t) Reflex t Glitter(t) BestAction(Grab,t)23Deducing hidden properties x,y,a,b Adjacent(x,y,a,b) a,b x+1,
20、y, x-1,y,x,y+1,x,y-1 Properties of squares: s,t At(Agent,s,t) Breeze(t) Breezy(s)Squares are breezy near a pit: Diagnostic rule-infer cause from effects Breezy(s) r Adjacent(r,s) Pit(r) Causal rule-infer effect from causer Pit(r) s Adjacent(r,s) Breezy(s) 24Knowledge engineering in FOL1.Identify the
21、 task2.Assemble the relevant knowledge3.Decide on a vocabulary of predicates, functions, and constants4.Encode general knowledge about the domain5.Encode a description of the specific problem instance6.Pose queries to the inference procedure and get answers7.Debug the knowledge base25The electronic
22、circuits domainOne-bit full adder26The electronic circuits domain1.Identify the taskDoes the circuit actually add properly? (circuit verification)2.Assemble the relevant knowledgeComposed of wires and gates; Types of gates (AND, OR, XOR, NOT)Irrelevant: size, shape, color, cost of gates3.Decide on a
23、 vocabularyAlternatives:Type(X1) = XORType(X1, XOR)XOR(X1)27The electronic circuits domain4.Encode general knowledge of the domaint1,t2 Connected(t1, t2) Signal(t1) = Signal(t2)t Signal(t) = 1 Signal(t) = 01 0t1,t2 Connected(t1, t2) Connected(t2, t1)g Type(g) = OR Signal(Out(1,g) = 1 n Signal(In(n,g
24、) = 1g Type(g) = AND Signal(Out(1,g) = 0 n Signal(In(n,g) = 0g Type(g) = XOR Signal(Out(1,g) = 1 Signal(In(1,g) Signal(In(2,g)g Type(g) = NOT Signal(Out(1,g) Signal(In(1,g)28The electronic circuits domain5.Encode the specific problem instanceType(X1) = XOR Type(X2) = XORType(A1) = AND Type(A2) = ANDType(O1) = ORConnected(Out(1,X1),In(1,X2)Connected(In(1,C1),In(1,X1)Connected(Out(1,X1),In(2,A2)Connecte
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 西安农村灌溉管理办法
- 财政调研经费管理办法
- 学校物资申请管理办法
- 学校作业改革管理办法
- 什么是面试培训课件
- 创意绘画培训课件下载
- 东莞初中面试数学试卷
- 福州九上开门考数学试卷
- 大学英语拓展0-英美文化习俗之英国历史文化举要
- 广东博罗县期中数学试卷
- HF-01型电除尘器高频电源使用说明书
- 消毒供应室专科理论考试题库(单选、多选共500题)
- 询价单(表格模板)
- 2023年5月FDA口服速释制剂根据BCS分类系统的生物利用度与生物等效性研究及生物等效性豁免
- 蓝色海洋经济海事航海渔业水产养殖港口码头海运PPT模板
- 病原学检测阴性肺结核诊断流程T∕CHATA 008-2020
- 广东省大学生校外实践教学基地
- 生物质气化耦合高效发电与多联产技术20161127 (1) (1)
- 正畸头影测量分析
- 如何使用S1000D规范
- 二十四山择吉天机(全)
评论
0/150
提交评论