第二章谓词逻辑.ppt

,*,/86,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,/73,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 谓词逻辑,在命题逻辑中，主要研究命题与命题之间的逻辑关系，其组成单元是原子命题，而原子命题是以一个具有真假意义的完整的陈述句为单位，不考虑其结构、成分,(,如主语，谓语等,),，对原子命题的联接关系的研究，不可能揭示原子命题的内部的特征。因此存在着很大的局限性：不能表达出每个原子公式的内部结构之间的关系，使得很多思维过程不能在命题逻辑中表示出来，例如著名的苏格拉底三段论,第二章 谓词逻辑,P,：所有的人都是要死的；,Q,：苏格拉底是人；,R,：所以，苏格拉底是要死的。,显然，这三个命题有着密切的关系，当,P,和,Q,为真时，,R,必定为真，即,R,应该是,P,，,Q,的逻辑结果：即,PQR,永真。但实际上并非如此：当,P,，,Q,取“,1”,，而,R,取“,0”,时,PQR 0,，即,PQR,不是永真公式，即,P,，,Q=R,不成立。用命题逻辑已无法正确地描述上述情况。,第二章 谓词逻辑,问题出现在哪里呢？,问题在于这类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现在构成原子命题的内部成分之间，即体现在命题结构以及深层次上，对此，命题逻辑无能为力。,所以在研究某些推理时，有必要对原子命题作进一步的分析，因此有必要引入谓词逻辑的概念。,2.1,谓词逻辑的基本概念与表示,在命题逻辑中，命题是具有真假意义的陈述句，从语法上分析，一个陈述句由主语和谓语两部分组成，比如：,“阿星是中科大学生”，“小强是中科大学生”，此时若用命题,P,，,Q,分别表示上述两句话，则,P,，,Q,显然是两个毫无关系的命题。用这两个命题所表达的判断之间，没有任何逻辑关系，但事实上并非如此，它们有一个共同的特性：“是中科大学生”。,因此，若将句子分解为：主语,+,谓语，同时将相同的谓语部分抽取出来，则可以表示这一类的语句。,2.1,谓词逻辑的基本概念与表示,此时，若用,P,表示：,P,：是中科大学生，,P,后紧跟：“某某人”，则上述两个句子可写为：,P(,阿星,),；,P(,小强,),。,因此，为了揭示命题内部结构以及命题的内部结构的关系，就按照这两部分对命题进行分析，分解成主语和谓语，并且把主语称为个体词或客体，而把谓语称为谓词。,2.1,谓词逻辑的基本概念与表示,例,2-1,：指出下列命题的个体词和谓词。,(1).,合肥是一个省会城市，,(2).,离散数学是计算机的基础课程，,(3).,姚明是一名篮球健将，,(4).,人是聪明的。,2.1,谓词逻辑的基本概念与表示,定义,2.3,：,(1),个体词的取值范围称为个体域,(,或论域,)(Individual Field),，常用,D,表示；,(2),宇宙间所有个体域聚集在一起构成的个体域称为全总个体域,(Universal Individual Field),。,定义,2.4,：,设,D,为非空的个体域，定义在,(,表示,n,个个体都在个体域,D,上取值,),上取值于,0,，,1,上的,n,元函数，称为,n,元命题函数或,n,元谓词,(Propositional Function),，记为,P(x1,x2,xn,),，此时个体变量,x1,x2,xn,的定义域都为,D,，,P(x1,x2,xn),的值域为,0,，,1,。,2.1,谓词逻辑的基本概念与表示,例,2-2,：符号化如下命题。,P,：上海是一个现代化城市；,Q,：甲是乙的父亲；,R,：,3,介于,2,和,5,之间；,T,：布什和萨达姆是同班同学。,注意：,(1).,谓词中个体词的顺序是十分重要的，不能随意变更。如前面的,F(b,c),与,F(c,b),的真值就不同；,(2).,一元谓词用以描述一个个体的某种特性，而,n,元谓词则用以描述,n,个个体之间的关系；,2.1,谓词逻辑的基本概念与表示,(3).0,元谓词,(,不含个体词的,),实际上就是一般的命题；,(4).,一个,n,元谓词不是一个命题，但将,n,元谓词中的个体变元都用个体域中具体的个体取代后，就成为一个命题。,2.1.1,量词,有了个体词和谓词的概念后，我们可以用具体的个体常量代换谓词中的个体变量，来获得相应的命题。但对有些命题，还是不能准确的符号化。,2.1,谓词逻辑的基本概念与表示,例,2-3,：,(1).,所有的老虎都会吃人的；,所有的,x,，,R(x),，,R(x),：,x,会吃人，,x,老虎,；,(2).,每一个人都会犯错误；,每一个,x,，,P(x),，,P(x),：,x,会犯错误，,x,人,；,(3).,有些人是大学生；,有一些,x,，,Q(x),，,Q(x),：,x,是大学生，,x,人,；,(4).,有一些自然数是素数。,有一些,x,，,S(x),，,S(x),：,x,是素数，,x,自然数,；,2.1,谓词逻辑的基本概念与表示,对这几个例子，我们仅仅符号化了一部分内容，而对句子中的“每一个”，“任意的”，“有一些”等等与个体词的数量有关的语句，无法用谓词来表示。因此我们需要在,n,元谓词前端加入限制词，即引入“量词”的概念。,定义,2.5,：,(1).,将日常生活和数学中常用的“一切的”，“所有的”，“每一个”，“任意的”等词称为全称量词,(Universal Quantifier),，符号化为“”；,2.1,谓词逻辑的基本概念与表示,(2).,将日常生活和数学中常用的“存在”，“有一个”，“至少有一个”，等词称为存在量词,(Existential Quantifier),，符号化为“”。,x/x,：表示个体域里的所有的,/,有的个体；,x F(x)/x,：,F(x),：表示个体域里所有的,/,存在个体具有性质,F,；,x,：作用变量；,F(x),：量词的辖域。,2.1,谓词逻辑的基本概念与表示,我们再来看前面的例子：,上面表示有不好之处：,总是要注明个体域；,如果个体域注明不是很清楚的话，冗余造成无法确定真值；,不同命题函数中的个体可以居于不同的个体域，将它们组成复合函数时，不易表达。,2.1,谓词逻辑的基本概念与表示,因此，有必要对个体域进行统一，全部使用全总个体域，而此时，对每一个句子中个体变量的变化范围用一个特性谓词来刻划。统一成全总个体域后，在公式中就不必特别说明。,特性谓词在加入到命题函数中式遵循如下规则：,(1).,对应全称量词，刻划其对应个体域的特性谓词作为蕴含式的前件加入；,(2).,对应存在量词，刻划其对应个体域的特性危险作为合取项加入。,2.1,谓词逻辑的基本概念与表示,例,2-5,：符号化下列语句。,(1).,天下乌鸦一般黑；,(2).,那位身体强健的，用功的，肯于思考问题的大学生解决了一个数学难题；,(3).,张强和李平都是足球运动员；,(4).,每一个实数都存在比它大的另外的实数；,(5).,并非所有的动物都是脊椎动物；,(6).,尽管有些人很聪明，但未必一切人都聪明；,(7).,对于任意给定的,0,，必存在着,0,使得对任意的,x,，只要,|x-a|,，就有,|f(x)-f(a)|y,”,;,2.2,谓词的合式公式及解释,注意：,封闭式在任何解释下都变成命题，而含有自由变元的公式在解释后一般仍为命题函数，但也可能变成命题。,2.2.4,一些特殊的公式,(,判定问题,),例,2-14,：,给出公式：和,在给定的解释下求其公式的真值。,例,2-15,：判断下列公式的真假：,2.2,谓词的合式公式及解释,从上述例子可知，谓词公式和命题公式一样，有可满足问题。,定义,2.13,：,设,A,为公式，若,A,在任何解释下均为真，则称,A,为永真式，或有效公式。若,A,在任何解释下均为假，则称,A,为矛盾式，或永假式，若,A,至少存在一个解释使,A,为真，则称,A,为可满足式。,2.2,谓词的合式公式及解释,(1).,永真式与矛盾式互为否定；,(2).,永真式一定为可满足公式。,判定问题：,谓词逻辑的判定问题，指的是对任何一公式的有效性的判定，若说谓词逻辑是可判定的，就是要求给出一个可行的方法，使得对任一公式都能判断是否是有效的。所谓可行的方法，乃是一个机械方法，可一步一步做下去，并在有穷步内实现判断。一般来说，像数学定理的证明是不可行的。,2.2,谓词的合式公式及解释,哪些公式是可判定的呢？,(1).,谓词逻辑是不可判定的。也就是说，还没有一个可行的算法，可用来判断任意一个公式是否是可满足的。判定问题的困难在于个体域是个无穷集以及对谓词设定的任意性。但我们并不排除谓词公式的子类是可判定的,;,(2).,只含有一元谓词变项的公式是可判定的；,(3).,如下公式：,若,P,中无量词和其它自由变元时，也是可判定的；,(4).,个体域有穷时的谓词公式是可判定的。,2.2,谓词的合式公式及解释,例,2-16,：判定下列公式的类型。,定义,2.14,：,设,0,是含命题变元,p,1,p,2,p,n,的命题公式，,A,1,A,n,是,n,个谓词公式，用,A,i,(1,in,),处处代替,0,中的,p,i,，所得公式,A,称为,A,0,的代换实例或代入实例。,定理,2.1,：,永真公式的代换实例都是有效公式，矛盾式的代换实例也都是矛盾式。,2.2,谓词的合式公式及解释,2.2.5,等值式,定义,2.15,：,设,A,，,B,是谓词逻辑中任意两个公式，若,AB,是永真公式，则称,A,与,B,是等价的或等值的，记作,AB,，称为等价式或等值式。,常用的等价式,第一组：我们在命题逻辑中给出了,24,个等价式，我们由定理,2.1,知道，这,24,个等价式对应的永真公式的代换实例仍是永真公式。因此，这,24,个等价式的代换实例也是谓词逻辑中的等价式。,2.2,谓词的合式公式及解释,例：,第二组：由于谓词公式本身的特殊性，即引入了谓词和量词的概念，所以还有以下一些等价式：,1.,消去量词等值式。设个体域为有限集,D=,a,1,a,n,，则由谓词公式的真值定义，有,2.2,谓词的合式公式及解释,2.,量词否定等值式,公式可由消去量词等值式推出。,3.,量词辖域收缩与扩张等值式,设,A(x),是任意的含个体变元,x,的公式，,B,中不含有,x,，则,(1):,2.2,谓词的合式公式及解释,(2):,4.,量词分配律,5.,改名规则,2.2,谓词的合式公式及解释,6.,补充四条,置换规则：设,(A),是合式公式,A,的公式，,(B),是用公式,B,取代,(A),中所有的,A,之后的公式，若,AB,，则,(A),(B),。,例,2-17,：证明下列等值式。,2.2,谓词的合式公式及解释,定义,2.16,：,设,A,，,B,是谓词逻辑中的任意两个公式，若,AB,为永真式，则称,A,永真蕴含,B,，记作,A=B,。,常用的永真蕴含式,2.3,范式,在命题逻辑中，每个公式都有与之等值的范式，范式是一种统一的表达形式，对研究一个公司的判定问题起着重要的作用。对谓词逻辑公式来说，也有范式。,2.3.1,前束范式,定义,2.17,：,设,A,为一个一阶逻辑公式，如果,A,中的一切量词都位于该公式的最前端，且这些量词的辖域都延伸到公式的末端，即,A,具有如下形式：,Q,1,x,1,Q,2,x,2,Q,k,x,k,B,，,其中,Q,i,(1,i,k,),为,或,，,B,为不含量词的公式。则称,A,为前束范式。,2.3,范式,例：,定理,2.2,：,(,前束范式存在定理,),一阶逻辑中的任何公式都存在与之等值的前束范式。,(,注：前束范式并不唯一,),。,2.3,范式,证明,：在一阶逻辑中，任何一个公式均可通过等值演算化为前束范式，化解过程如下：,(1).,消去除，之外的联结词；,(2).,反复运用得摩根定律，直接将否定符移动到原子公式的前端,(,量词符后,),；,(3).,换名使各变元不同名；,(4).,使用谓词的等价公式，将所有量词提到公式的最前端。,例,2-20,：将下列公式化成前束范式,2.3,范式,2.3.2SKolem,标准形,定义,2.18,：,设公式,G,是一个前束范式，如消去,G,中所有的存在量词如全称量词，所得到的公式称为,SKolem,标准形。,定理,2.3,：,任意一个公式,G,都有相应的,Skolem,标准形存在，但此,Skolem,标准形不一定与原公式等值。,证明：由定理,2.2,知，公式,G,必有与之等价的前束范式，设,G,的前束范式为：,G=(,Q,1,x,1,)(,Q,2,x,2,)(,Q,n,x,n,),M,(,x,1,x,2,x,n,),(1).,如果,Q,i,是存在量词，且,Q,i,的左边没有全称量词，则直接用一个常量符号,a,来取代,x,i,在,M,中的一切出现，且该,a,不同于,M,中的任何其他常量符号；,2.3,范式,(2).,如果,Q,i,是存在量词，且,Q,i,的左边有全称量词,(,任意,x,j,),，,(,任意,x,l,),，,(,任意,x,k,),，则直接用一个函数,f,(,x,j,x,l,x,k,),来取代,x,i,在,M,中的一切出现，该函数符号,f,不同于,M,中的任何其他函数符号；,(3).,如果,Q,i,是全称量词，则直接用一个变量符号,x,来取代,x,i,在,M,中的一切出现，且该变量,x,不同于,M,中的任何其他变量符号：,(4).,反复使用上述,(1),(2),(3),，可消去前束范式中的所有存在量词的全称量词，此时得到的公式为该公式的,Skolem,标准形。,例,2-21,：求下公式的,Skolem,标准形。,2.4,一阶逻辑的推理,在前面我们讨论了命题逻辑的推理理论，而谓词逻辑是命题逻辑的扩大系统，我们也就完全可以将命题逻辑中相应的术语，符号，规则扩展并借用过来。,在谓词逻辑中，从前提,A1,，,，,An,出发推理结论,B,的形式结构，依然可以采用如下的蕴含式形式：,A1,A2,An B,，若该式永真，则推理正确，否则称推理不正确，也就是说，判断推理是否正确，也就 是判断,A1,A2,An,是否永真蕴含,B,。,2.4,一阶逻辑的推理,2.4.1,推理规则,我们知道在推理理论中，最重要的是推理规则，我们首先对谓词逻辑中的推理规则作一个小结：,(,我们还是采用构造证明法,),第一组：直接从命题逻辑逻辑中借用过来的规则，如：前提引入规则、结论引入规则、置换规则、,CP,规则；,第二组：谓词逻辑中由于引入量词而需要引进新的规则：,1.,全称量词消去规则,(,简记为,UI,规则或,VI),或叫全称特指规则，,2.4,一阶逻辑的推理,其中,y,为任意的不在,A(x),中约束出现的个体变量，,c,为任意的不在,A(x),中出现过的个体常量；,例,2-22,：考虑个体域为实数集合，公式 ，其中,F(x,y),：,xy,。,2.,存在量词消去规则,(,简记为,EI),或叫存在特指规则，,2.4,一阶逻辑的推理,其中，,c,是使,A,为真的个体域中的某个个体，即一个特定的个体常项，,c,不在,A(x),中出现，要求 中无其它自由出现的个体变项，如有，必须用函数符号来取代。,例,2-23,：,2.4,一阶逻辑的推理,3.,全称量词引入规则,(,记为,UG),也叫全称推广规则，其中无论,A(y),中自由出现的个体变量,y,取何值，,A(y),应该均为真，,x,不能在,A(y),中约束出现。,例,2-24,：,2.4,一阶逻辑的推理,4.,存在量词引入规则,(,简记,EG),也叫存在推广规则，其中，,c,是特定的个体常量，,x,不能在,A(c),中出现过。,例,2-25,：,第三组：由推理定律而来的推理规则，,我们知道，推理规则实际上来源于推理定律，本质上是来源于一些永真蕴含式的，谓词逻辑中的推理定律,(,或永真蕴含式,),有三个来源：,2.4,一阶逻辑的推理,(1).,命题逻辑中的推理定律的代换实例，例：化简律：,附加率：,(2).,谓词逻辑中的每个等值式可以生成相应的两个推理定律，例：由全称量词的否定等值式 可得：,或,(3).,谓词逻辑中因为引入量词后的所得永真蕴含式，前面给出的永真蕴含式。,2.4,一阶逻辑的推理,2.4.2,推理规则的应用,一般情况下，总是假定相同的个体域,(,即全总个体域,),下进行的。,(1).,推理过程中，可以直接引用：前提引入、结论引入、置换、,CP,等规则以及谓词逻辑中的等价式和永真蕴含式导出的规则；,(2).,可以引用,UI,，,EI,规则消去量词，此时量词必须位于整个公式的最前端，且其辖域延伸到公式的末端；,(3).,可以引用,UG,，,EG,规则加入量词；,2.4,一阶逻辑的推理,(4).,在推理过程中，如既要使用,UI,规则，又要使用,EI,规则消去量词，而且选用的个体是同一个符号，则必须先使用规则,EI,，再使用规则,UI,；,(5).,如果一个变量是永规则,EI,消去量词，对该变量在添加量词时，则只能使用规则,EG,，而不能使用规则,UG,，如使用规则,UI,消去量词，对该变量在添加量词时，则可使用规则,EG,和,UG,。,2.4,一阶逻辑的推理,2.4.3,举例,例,2-26,：证明苏格拉底三段论。,例,2-27,：证明下述论断的正确性：,所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物。故有些脊椎动物不是胎生的。,例,2-28,：给出下面推理的证明：,前提：,结论：,2.4,一阶逻辑的推理,例,2-29,：构造下面推理的证明：,前提：,结论：,例,2-30,：证明下面论断的正确性。,有些学生相信所有的老师，任何一个学生都不相信骗子。所以，教师都不是骗子。,2.4,一阶逻辑的推理,例,2-31,：用反证法证明：,例,2-32,：证明：,2.5,谓词逻辑在计算机科学中的应用,2.5.1,谓词逻辑与数据库语言,1,张二维表可表示一个,n,元有序组的集合，可以用一个,n,元特性谓词来刻划：某元组属于二维表的充要条件是给其对应的谓词为真,如：,F(x,y)=N(x)(x=y),即,(x,y)|F(x,y),。,x,y,1,1,2,2,3,3,2.5,谓词逻辑在计算机科学中的应用,对数据库而言，基本操作插入，删除等；,此外，修改，选择等都可以用谓词公式来表示，因而，可以用谓词逻辑这一工具来研究关系数据库。,基本操作,关系代数,逻辑公式,插入,RS,(x1,xn)|P(x1,xn)Q(x1,xn),删除,R-S,(x1,xn)|P(x1,xn)Q(x1,xn),2.5,谓词逻辑在计算机科学中的应用,2.5.2,谓词逻辑与逻辑程序设计语言,我们知道谓词逻辑是不可判定的，但,1965,年美国数理逻辑学家罗宾逊,Robinson,，证明了谓词逻辑的“半可判定性”，即在谓词逻辑中存在一种算法，只要公式是永真的，就能用此算法推出，他们使用的算法叫消解原理，,1972,年法国马赛大学的,Colmerauer,设计了一种逻辑程序设计语言，,Prolog,语言，实现了消解法。,现实世界,=,谓词逻辑表示,=Prolog,程序,=,计算机实现,2.5,谓词逻辑在计算机科学中的应用,1.,子句和子句集,谓词公式斯科林范式子句集,Horn,子句,(1).,谓词公式斯科林范式，一个命题公式；,(2).,斯科林范式：化为合取范式，将每个合取项用蕴含式表示，这种蕴含式称为子句；,(3).,一个公式总可以用一组子句来表示，每个子句具有单一的蕴含形式，公式是永真的，则该子句集中的每一个子句永真。,2.5,谓词逻辑在计算机科学中的应用,例,2-34,：求下公式的子句集。,例,2-35,：试将“每个人都犯错误”用子句形式表示。,例,2-36,：试将祖先关系“父母是祖先，祖先的祖先是祖先”用子句集表示。,2.5,谓词逻辑在计算机科学中的应用,2.,消解原理,我们知道，在公理系统中，有公理和定理两部分，公理是已知的永真公式，定理是要求证明的永真公式，公理可用子句集表示，设子句集,S,，则,S=E1,，,E2,，,，,En,，其中,Ei(i=1,，,n),表示子句。设定理用,E,表示，则,2.5,谓词逻辑在计算机科学中的应用,(1).,子句集的相容性。,一个子句集如存在语义解释，则称它是相容的，否则称为不相容的。如,P,，,P,是不相容的子句集，而,P Q,，,Q R,，,x,，,y,都是相容的，因为在现实世界中总可以找到一种语义解释使每个子句为永真。,相容性是一个公理系统的必备条件，一个不相容的公理系统在现实世界中是不存在的。,由相容子句集,S,可推得结论,E,，相当于,SE,是不相容的。,2.5,谓词逻辑在计算机科学中的应用,例如：我们可以由,A B,，,B,可得出,A,，它相当于,A B,，,B,，,A,是不相容的。,也就是说，要证明由,S,可推得定理,E,，相当于证明,SE,是不相容的。,(2).,不相容性的证明方法。,定理,2.4,：,设有永真公式,其中,则必有永真公式：,2.5,谓词逻辑在计算机科学中的应用,推论,2.1,：,设有永真公式，,其中，则必有永真公式，,推论,2.2,：,由,P,，,P,可得,(,空子句,),。,说明：,(1).,两个子句其不同的两边如有相同命题可消去，这是消解原理的基本思想，此方法叫反驳法；,(2).,由推论,2.2,知，由不相容的子句集可得空子句。,2.5,谓词逻辑在计算机科学中的应用,这样我们可以得到一种证明方法，即由,S,为公理系统证明,E,为定理的过程可以改为：,(1).,作,S1=SE=E1,，,E2,，,，,En,，,E,公理系统；,(2).,从,E,开始在,S1,内不断用反驳法；,(3).,最后如出现空子句则结束。,例,2-37,：试证由,可推出,2.5,谓词逻辑在计算机科学中的应用,例,2-38,：试证由,可推出,P,。,(3).,代换合一与匹配。,在消解原理中，关键问题是合一式匹配，即要在两个子句中不同端寻找相同的命题，其它并非容易，两个谓词相同的含义有：,两个谓词符相同；,个体变元的数目相同；,对应个体变元相同，这又可分为三种情形：,2.5,谓词逻辑在计算机科学中的应用,(a).,两者均为变量，此时需要对作代换使之相同；,(b).,一个为变量，另一个为常量，此时必须对变量作代换使之与常量一致；,(c).,两者均为常量，此时两常量应相等。,代换：对一组变元,x1,x2,xn,它可分别用,t1,替换,x1,，,t2,替换,x2,，,tn,替换,xn,，从而得到另一组变元,t1,t2,tn,这种替换过程叫代换，它可写成：,2.5,谓词逻辑在计算机科学中的应用,例,2-39,：设有公式,E=F(x,，,y),，代换,Q=ax,，,by,，则,EQ=F(a,，,b),。,例,2-40,：设公式 ，代换,则有,例,2-41,：试用反驳法消解子句集,2.5,谓词逻辑在计算机科学中的应用,合一：使两个公式相同的代换，称为合一，即对,E1,，,E2,，,En,，如果存在一种代换,，使得,E1,=En,，则称此代换为合一。,匹配：合一不是唯一的，它可以有多个，其中最一般性的合一称为匹配，即对,E1,，,E2,，,En,，如果存在一个合一,，使得对其他任一一个合一,Qi,，均存在代换,i,，满足,则称,为,E1,，,E2,，,En,的匹配。,例,2-42,：设有,P(u,，,y,，,g(y),，,P(x,，,f(u),，,z),，试给出其匹配。,2.5,谓词逻辑在计算机科学中的应用,为了消解，我们引入了代换，使得若干个公式相同的代换称为合一，最一般的合一为匹配，在消解过程中，我们使用合一与匹配。,例,2-43,：设有一种关于父母和祖父母的客观事实，要求某些祖孙关系。,Father(John,Ares)Father(Ares,Bob),Mother(Mary,Ares)Mather(Ann,Bob),Parent(x,y)Father(x,y),Parent(x,y)Mather(x,y),Grandparent(x,y)Parent(x,z),Parent(z,y),2.5,谓词逻辑在计算机科学中的应用,求证：,Grandparent(John,bob),例,2-44,：试证明下列的智力测试题目,(,水容器问题,),。设有两个分别盛,7,升与,5,升的水容器，开始时两个容器均空，允许对容器做三种操作：容器倒满水，将容器中的水倒光，从一个容器倒水至另一个容器，使一个容器倒光而另一个容器倒满。最后要求能使大容器中有,4,升水，并求其操作过程。,数理逻辑,命题逻辑：,1.,命题的表示：命题，联结词，命题公式,2.,命题的判定：真值表，等值演算，范式,3.,命题的推理,谓词逻辑：,1.,谓词的表示：谓词，量词，谓词公式,2.,谓词的判定：解释，等值演算，前束范式与,Skolem,范式,3.,谓词的推理,数理逻辑,例,1,：有一会议室，四周都有出入门，门旁边都有开关,(,双控开关,),，为了控制会议室的照明，要求设计一线路使得改变任一只开关的状态，就能改变全室的明暗，假设，室中无人时灯暗，有人时灯亮，写出控制电路的逻辑表达式并画出电路图。,数理逻辑,例,2,：设计一台自动售货机，它只能接受一分和二分硬币，当投入硬币总值超过三分时，给出一根棒棒糖，并找回余额。,数理逻辑,例,3,：有一逻辑学家误入某部落，被拘于牢狱，酋长有意放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可以任意开启一门。为协助你脱逃，今加派两名战士负责解答你所问的任何问题。唯可虑者，此两战士一名天性诚实，一名说谎成性，今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问，然后从容离开，该逻辑学家应该如何发问？,