一阶逻辑等值演算与推理课件(离散数学)精讲

第五章一阶逻辑等值演算与推理1本章主要内容5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式5.3一阶逻辑的推理理论25.1一阶逻辑等值式与置换规则等值式的概念基本等值式等值演算与置换规则3所有的学生都上课了，这是错的。令F(x):x是学生,G(x):x上课了。))()((xGxFx这句话相当于“有些学生没有上课”。))()((xGxFx4一、等值式的概念定义：若AB为永真式，则称A与B是等值的，记作AB，并称AB为等值式。其中A、B是一阶逻辑中任意的两个合式公式。5二、基本等值式1.命题逻辑中16组基本等值式的代换实例例：xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y))xF(x)yG(y)即命题逻辑中的基本等值式在谓词逻辑中均适用。6二、基本等值式2.有限个体域中，消去量词等值式设个体域为D={a1,a2,…,an}xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)7二、基本等值式3.量词否定等值式“并不是所有的人都是黄皮肤。”这句话相当于“有的人不是黄皮肤。”)(xxA)(xAx)()(xAxxxA)()(xAxxxA8二、基本等值式4.量词辖域收缩与扩张等值式设A(x)是含x自由出现的公式，B中不含x的出现。关于全称量词：x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)9二、基本等值式关于存在量词:x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)10二、基本等值式5.量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对无分配律，对无分配律11三、等值演算与置换规则置换规则：设(A)是含有公式A的公式，用公式B置换(A)中所有的A后得到新的公式(B)，若AB,则(B)(A)等值演算的基础：（1）一阶逻辑的基本等值式；（2）置换规则、换名规则、代替规则。12例题例1：下面的命题都有两种不同的符号化形式，写出其中的一种，然后通过等值演算得到另一种。(1)没有不犯错误的人(2)不是所有的人都爱看电影13(1)没有不犯错误的人令F(x)：x是人，G(x)：x犯错误蕴涵等值式的代入实例摩根律的代入实例德量词否定等值式))()(())()(())()(())()((xGxFxxGxFxxGxFxxGxFx))()((xGxFx例题14(2)不是所有的人都爱看电影令F(x)：x是人，G(x)：爱看电影))()((xGxFx摩根律的代入实例德量词否定等值式蕴涵等值式的代入实例))()(())()(())()(())()((xGxFxxGxFxxGxFxxGxFx例题15例2：设个体域D={a,b,c}，在D中消去下列公式中的量词。))()((1yyGxFx）（))()()(()()()())()()(()())()()(()())()()(()()))()()(()(())()((cGbGaGcFbFaFcGbGaGcFcGbGaGbFcGbGaGaFcGbGaGxFxyyGxFx两次使用“消去等值式”例题16))()()(()()()()()())()((cGbGaGcFbFaFyyGxxFyyGxFx量词辖域收缩与扩张等值式解法二：小结：采用不同的演算过程同样可以达到消去量词的目的，但是如何演算才更简单呢？结论是将量词辖域尽可能的缩小，然后再消量词。例题17))()((2yGxFyx）（))()()(())()()((cGbGaGcFbFaF)))()(())()(())()(((cGxFbGxFaGxFx)))()(())()(())()((()))()(())()(())()((()))()(())()(())()(((cGcFbGcFaGcFcGbFbGbFaGbFcGaFbGaFaGaF)()())()((yyGxxFyGxFyx方法2：例题18)),(),((yxGyxFyx))),(),(()),(),(((bxGbxFaxGaxFx))),(),(()),(),((())),(),(()),(),(((bbGbbFabGabFbaGbaFaaGaaF(3)当个体域D={a,b}提问：如果先消去全称量词，后消去存在量词，结果会怎样？例题19该题量词的辖域已经不能再缩小了，所以演算过程无法再简化，演算结果也不易化的更简单。)),(),((yxGyxFyx)),(),(()),(),((ybGybFyyaGxaFy))),(),(()),(),((())),(),(()),(),(((bbGbbFabGabFbaGbaFaaGaaF两种消去顺序得到的结果相同。例题20例3给定解释I如下:(a)个体域D={2，3}(b)(c)(d)谓词如下页所示2a2)3(3)2()(ffxf，为：例题21在I下求下列各式的真值。.1)3(,0)2()(0)2,3(L)3,2(L)2,2(L:),(L0.)3,3(1,)2,3()3,2()2,2(:),(FFxFyxGGGGyxG为：为为例题22),()4(),()3()))(,())((()2()),()(()1(yxxLyyxyLxxfxGxfFxaxGxFx计算过程见教材例题23例4：证明下面的谓词公式是永真式。为任意公式、其中）（）（BAxBxABAxxxFxxF)()(2)()(1证明谓词公式是永真式不能像命题公式那样使用真值表。常用的方法是等值演算。例题24))()(()()()()()()(1xFxFxxxFxFxxxFxxFxxFxxF）（经过等值演算可知该公式是永真式。例题251)())(()()()()()()(2xBxBAxxBBxAxxBBAxxBABAxxBAxBAxxBxABAxxBxABAx）（例题26兔子比乌龟跑得快。令：F(x):x是兔子G(y):y是乌龟L(x,y):x比y跑得快))),()(()((yxLyGyxFx命题符号化为：)),()()((yxLyGxFyx另外一种等值的符号化形式为：275.2前束范式定义：设A为一个一阶逻辑公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi(1ik)为或，B为不含量词的公式。例：xy(F(x)(G(y)H(x,y)))x(F(x)G(x))x(F(x)G(x))不是前束范式。B前束范式B285.2前束范式(1)x(M(x)F(x))解：x(M(x)F(x))x(M(x)F(x))（量词否定等值式）x(M(x)F(x))两步结果都是原公式的前束范式。例1：求下列公式的前束范式295.2前束范式(2)xF(x)xG(x)解：xF(x)xG(x)xF(x)xG(x)（量词否定等值式）x(F(x)G(x))（量词分配等值式）另有一种形式如下：305.2前束范式xF(x)xG(x)xF(x)xG(x)xF(x)yG(y)(换名规则)x(F(x)yG(y))(量词辖域扩张)xy(F(x)G(y))(量词辖域扩张)315.2前束范式(3)xF(x)xG(x)解xF(x)xG(x)xF(x)xG(x)x(F(x)G(x))或xy(F(x)G(y))325.2前束范式(4)xF(x)y(G(x,y)H(y))解xF(x)y(G(x,y)H(y))zF(z)y(G(x,y)H(y))(换名规则)zy(F(z)(G(x,y)H(y)))或xF(x)y(G(t,y)H(y))(代替规则)xy(F(x)(G(t,y)H(y)))335.2前束范式(5)x(F(x,y)y(G(x,y)H(x,z)))解：既可用换名规则,也可用代替规则x(F(x,y)y(G(x,y)H(x,z)))x(F(x,u)y(G(x,y)H(x,z)))xy(F(x,u)G(x,y)H(x,z)))注意：x与y不能颠倒(换名规则)345.2前束范式（6）),,())(),((321122211xxxHxxGxxxFx)),,())(),(((),,())(),((),,())(),((),,())(),((345241521345524121345522411321122211xxxHxGxxFxxxxxxHxxGxxFxxxxxHxxGxxxFxxxxHxxGxxxFx355.2前束范式例题小结：公式的前束范式不惟一；求公式的前束范式的方法:利用基本等值式、置换规则、换名规则、代替规则进行等值演算。定理：一阶逻辑中的任何公式都存在与之等值的前束范式。365.3一阶逻辑的推理理论推理的形式结构重要的推理定律推理规则构造证明（附加前提证明法）37一、推理的形式结构推理的形式结构有两种：第一种A1A2…AkB(*)第二种前提：A1，A2，…，Ak结论：B其中A1,A2,…,Ak,B为一阶逻辑公式.若(*)为永真式,则称推理正确,否则称推理不正确38一、推理的形式结构判断推理是否正确的方法：等值演算法，应用这种方法时采用第一种形式结构；构造证明法，采用第二种形式结构。39二、重要的推理定律第一组命题逻辑推理定律代换实例如：xF(x)yG(y)xF(x)化简律代换实例.第二组由基本等值式生成的推理定律如：由xA(x)xA(x)生成xA(x)xA(x),xA(x)xA(x),…40二、重要的推理定律第三组xA(x)xB(x)x(A(x)B(x))x(A(x)B(x))xA(x)xB(x))()())()(()()())()((xxBxxAxBxAxxxBxxAxBxAx41三、推理规则(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(5)附加规则(6)化简规则(7)拒取式规则(8)假言三段论规则(9)析取三段论规则(10)构造性二难推理规则(11)合取引入规则42(12)全称量词消去规则（记为UI）)()(2)()(1cAxxAyAxxA）（或）（注意：下面的规则只能用于前束范式。在(1)式中，y应为任意的不在A(x)中约束出现的个体变项。在第二式中，c为任意的未在A(x)中出现过的个体常项。用y或c去取代A(x)中的自由出现的x时，一定要在x自由出现的一切地方进行取代。43(13)全称量词引入规则（记为UG）)()(xxAyA无论A(y)中自由出现的个体变项y取何值，A(y)应该均为真。x不约束出现在A(y)中。),()(yxxFyAyxyxFD:),(：实数域；例：个体域若对A(y)应用UG规则时，用在A(y)中约束出现的x代替y，则得到