人工智能第2章(知识表示方法3-谓词逻辑)

人工智能ArtificialIntelligence(AI)第2章知识表示方法2.1状态空间法2.2问题归约法2.3谓词逻辑法五房间问题：1、有5栋5种颜色的房子2、每一位房子的主人国籍都不同3、这5个人只喝一个牌子的饮料，只抽一个牌子的香烟，只养一种宠物4、没有人有相同的宠物，抽相同牌子的香烟，喝相同的饮料谁养鱼？已知条件：1、英国人住在红房子里2、瑞典人养了一条狗3、丹麦人喝茶4、绿房子在白房子左边5、绿房子主人喝咖啡6、抽PALLMALL烟的人养了一只鸟7、黄房子主人抽DUNHILL烟8、住在中间那间房子的人喝牛奶9、挪威人住在第一间房子10、抽混合烟的人住在养猫人的旁边11、养马人住在DUNHILL烟的人旁边12、抽BLUEMASTER烟的人喝啤酒13、德国人抽PRINCE烟14、挪威人住在蓝房子旁边15、抽混合烟的人的邻居喝矿泉水房间号12345颜色国籍香烟饮料宠物挪威人牛奶4、绿房子在白房子左边5、绿房子主人喝咖啡咖啡1、英国人住在红房子里英国人7、黄房子主人抽DUNHILL烟11、养马人住在DUNHILL烟的人旁边DUNHILL马3、丹麦人喝茶12、抽BLUEMASTER烟的人喝啤酒矿泉水2、瑞典人养了一条狗3、丹麦人喝茶12、抽BLUEMASTER烟的人喝啤酒13、德国人抽PRINCE烟瑞典人BLUEMASTER啤酒狗丹麦人茶德国人PRINCE混合烟PALLMALL鸟猫鱼domainsID=symbolHOUSE=h(ID,NO)HLIST=referenceHOUSE*NO=integerNOLIST=NO*CHARLIST=CHAR*CHARLISTS=CHARLIST*predicatesnondetermsolvenondetermcandidate(HLIST,HLIST,HLIST,HLIST,HLIST)nondetermperm(HLIST)nondetermconstraints(HLIST,HLIST,HLIST,HLIST,HLIST)nondetermpermutation(NOLIST,NOLIST)nondetermdelete(NO,NOLIST,NOLIST)member(HOUSE,HLIST)nondetermnext(NO,NO)nondetermlleft(NO,NO)clausessolve():-constraints(Colours,Drinks,Nationalities,Cigarettes,Pets),candidate(Colours,Drinks,Nationalities,Cigarettes,Pets),member(h(water,WaterHouse),Drinks),member(h(WaterColour,WaterHouse),Colours),member(h(zebra,ZebraHouse),Pets),member(h(ZebraColour,ZebraHouse),Colours),write(Theydrinkwaterinthe,WaterColour,house\n),write(Thezebraliveinthe,ZebraColour,house\n).candidate(L1,L2,L3,L4,L5):-perm(L1),perm(L2),perm(L3),perm(L4),perm(L5).perm([h(_,A),h(_,B),h(_,C),h(_,D),h(_,E)]):-permutation([A,B,C,D,E],[1,2,3,4,5]).constraints(Colours,Drinks,Nationalities,Cigarettes,Pets):-member(h(englishman,H1),Nationalities),member(h(red,H1),Colours),member(h(spaniard,H2),Nationalities),member(h(dog,H2),Pets),member(h(norwegian,1),Nationalities),member(h(kools,H3),Cigarettes),member(h(yellow,H3),Colours),member(h(chesterfields,H4),Cigarettes),next(H4,H5),member(h(fox,H5),Pets),member(h(norwegian,H6),Nationalities),next(H6,H7),member(h(blue,H7),Colours),member(h(winston,H8),Cigarettes),member(h(snails,H8),Pets),member(h(lucky_strike,H9),Cigarettes),member(h(orange_juice,H9),Drinks),member(h(ukrainian,H10),Nationalities),member(h(tea,H10),Drinks),member(h(japanese,H11),Nationalities),member(h(parliaments,H11),Cigarettes),member(h(kools,H12),Cigarettes),next(H12,H13),member(h(horse,H13),Pets),member(h(coffee,H14),Drinks),member(h(green,H14),Colours),member(h(green,H15),Colours),lleft(H16,H15),member(h(ivory,H16),Colours),member(h(milk,3),Drinks).permutation([],[]).permutation([A|X],Y):-delete(A,Y,Y1),permutation(X,Y1).delete(A,[A|X],X).delete(A,[B|X],[B|Y]):-delete(A,X,Y).member(A,[A|_]):-!.member(A,[_|X]):-member(A,X).next(X,Y):-lleft(X,Y).next(X,Y):-lleft(Y,X).lleft(1,2).lleft(2,3).lleft(3,4).lleft(4,5).goalsolve.推理的一般形式已知：事实一，事实二，…如果事实一，那么结论一；如果事实二，那么结论二；…得到：结论一，结论二，…如果将事实和规则抽象出来，不涉及具体内容，借助一些符号来表示，推理过程可形式化为：P：某已知事实P→Q：如果P，则Q结论：Q自然语言不适合计算机推理如：小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系逻辑经典逻辑：命题逻辑、谓词逻辑非经典逻辑：不确定性推理、非单调性推理命题逻辑谓词逻辑如果今天不下雨，我就去你家今天没有下雨我去了你家Q﹃P﹃P→Q命题逻辑核心思想：原子命题不可再分凡人都会死苏格拉底是人苏格拉底会死Man(Socrates)Mortal(Socrates)x(Man(x)→Mortal(x))2.3谓词逻辑法数理逻辑（符号逻辑）是用数学方法研究形式逻辑的一个分支。它通过符号系统来表达客观对象以及相关的逻辑推理。常用的是命题逻辑和谓词逻辑谓词逻辑是数理逻辑的基本形式，是基于谓词分析的一种形式化（数学）语言人工智能中的谓词逻辑法是指用一阶谓词来描述问题求解和定理证明（限于本课程）2.3.0命题逻辑的复习1、命题逻辑的基本概念命题是能够判断真或假的陈述句通常用大写字母来表示，如A,B,P,Q等命题的真假值一般用T或F来表示例：雪是白的。（陈述句，T）雪是蓝的。（陈述句，F）雪是黑的。（陈述句，F）他是学生。（陈述句，他泛指，无法判断真假）你今天上课没有？（疑问句）去北校区，请坐校车！（祈使句）命题逻辑是研究命题及命题之间关系的符号逻辑系统。在命题逻辑中，表示单一意义的命题，称之为原子命题。原子命题通过“联结词”构成复合命题。五个联结词：①“～”表示“非”复合命题～P为真，当且仅当P为假。②“∧”表示“合取”复合命题“P∧Q”为真，当且仅当P和Q都为真。④“”表示“蕴含”复合命题“PQ”为假，当且仅当P为真且Q为假。③“∨”表示“析取”复合命题“P∨Q”为真，当且仅当P、Q两者之一为真。⑤“”表示“等价”复合命题“PQ”为真，当且仅当P、Q同时为真、或者同时为假。联接词的优先顺序：非～、合取∧、析取∨、蕴含、等价注：可以用括号表示优先级真值表PQ～PP∧QP∨QPQPQFFTFFTTFTTFTTFTFFFTFFTTFTTTT命题变元：用符号P、Q等表示的不具有固定、具体含义的命题。它可以表示具有“真”、“假”含义的各种命题。命题变元可以利用联结词构成所谓的合适公式。合适公式的定义①若P为原子命题，则P为合适公式，称为原子公式。②若P是合适公式，则～P也是一个合适公式。③若P和Q是合适公式，则P∧Q、P∨Q、PQ、PQ都是合适公式。④经过有限次使用规则1、2、3，得到的由原子公式、联结词和园括号所组成的符号串，也是合适公式。对于合适公式，规定下列运算优先级：①逻辑联结词的运算优先次序为：～、∧、∨、、②同级联结词按出现顺序优先运算在命题逻辑中，主要研究推理的有效性。即：能否根据一些合适公式（前提）推导出新的合适公式（结论）。一些合适公式（前提条件）合适公式（结论）？在命题逻辑中，最基本的单元是命题，它是作为一个不可分割的整体。例如：雪是黑的命题逻辑具有较大的局限性，不合适于表达比较复杂的问题。例：所有科学都是有用的（假设1）。数理逻辑是科学（假设2）。所以，数理逻辑是有用的（结论）。很明显，我们无法用两个假设推断出结论。谓词逻辑是命题逻辑的扩充和发展。它将一个原子命题分解成客体和谓词两个组成部分。例如：雪是黑的客体谓词本课程主要介绍一阶谓词逻辑。2.3.1谓词演算1、语法与语义谓词逻辑的基本组成部分谓词变量函数常量圆括号、方括号、花括号和逗号例“机器人（Robot）在第一个房间（Room1）内”，可以表示为：INROOM（ROBOT，r1）其中INROOM是谓词ROBOT和r1是常量谓词是指个体（客体）所具有的性质或者若干个体之间的关系。用大写字母来表示。个体是可以具体的（如:小张、3、5）也可以是抽象的（如:x,y）。例：小明是学生，A表示是“是学生”，x表示“小明”，记作A(x)。x大于y，G表示“大于”，记作G（x,y）。论域：由个体组成的集合。（个体）变量：定义在某一个论域上的变量。用x,y,z来表示。函数（或函词）：以个体为变量，以个体为值的函数。一般用小写字母来表示，例如f(x),f(x,a)。如果谓词有n个变量，称之为n元谓词，并约定0元谓词就是命题（谓词的特例）。如果函数有n个个体，称之为n元函数，并约定0元函数就是常量。常量习惯上用小写字母来表示，如a,b,c。项的定义：①常量是项②变量是项③如果f是n元函数，且t1,…,tn(n≥1)是项，则f(t1,…,tn)也是项④所有的项都必须是有限次应用上述规则产生的项的例子：常量：a变量：x函数：f(x,a)g(f(x,a))原子（谓词）公式的（递归）定义：①原子命题是原子公式②如果t1,…,tn(n≥1)是项，P是谓词，则P(t1,…,tn)是原子公式③其它表达式都不是原子公式原子公式的例子1、原子公式：P（原子命题）2、项：x,a,f(x,a)，谓词：P原子公式：P(x,a,f(x,a))2、连词和量词联结词（连词）就是命题逻辑中的五个，它们的含义也是一样的。两个量词：①全称量词，记作“x”,含义是“对每一个x”或“对一切x”。②存在量词，记作“x”，含义是“存在某个x”、“有一个x”或者“某些x”。AllAExistE例1：“所有的机器