谓词逻辑总结.ppt

数理逻辑部分数理逻辑部分小结小结2010年年11月月命题命题谓词和个体谓词和个体量词量词命题逻辑部分命题逻辑部分一阶谓词逻辑部分一阶谓词逻辑部分p:2是偶数是偶数F(x):x是偶数，是偶数，a:2F(2)例题例题:(1)2是偶数是偶数例题例题:(2)x是偶数是偶数不是命题不是命题F(x):x是偶数是偶数例题例题:(3)所有的人都是大学生所有的人都是大学生假命题假命题G(x):x是人是人,H(x):x是大学是大学生生x(G(x)H(x)命题命题联结词联结词命题公式命题公式真值表真值表命题符号命题符号谓词和个体谓词和个体量词量词一阶逻辑公式一阶逻辑公式置换规则置换规则一阶逻辑前束范式一阶逻辑前束范式命题逻辑命题逻辑一阶谓词逻辑一阶谓词逻辑公式解释公式解释符号化符号化等值式与等值演算等值式与等值演算等值式等值式主析主析(合合)取范式取范式命题逻辑推理理论命题逻辑推理理论一阶谓词逻辑一阶谓词逻辑推理理论推理理论重要题型重要题型1.求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值真值表法真值表法最最简单、最简单、最直观的方法直观的方法重要题型重要题型1.求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值/判断公式类判断公式类型型真值表法真值表法最最简单、最简单、最直观的方法直观的方法主主析取范式法析取范式法m0m1m2m4m5m6m72.判断两个命题公式是否等值判断两个命题公式是否等值真值表法真值表法最最简单、最简单、最直观的方法直观的方法2.判断两个命题公式是否等值判断两个命题公式是否等值真值表法真值表法最最简单、最简单、最直观的方法直观的方法等值演算法等值演算法 pq(p q)最最基本基本的方法的方法2.判断两个命题公式是否等值判断两个命题公式是否等值真值表法真值表法最最简单、最简单、最直观的方法直观的方法等值演算法等值演算法右边 pq(p(q q)(p p)q)(pq)(p q)(pq)(pq)(pq)(p q)(pq)m1m2m3主析取范式法主析取范式法左边左边(p q)pq(pq)(p q)(pq)m1m2m33.应用题应用题例题：例题：某科研所要从3名科研骨干A,B,C 中挑选12名出国进修。由于工作需要，选派时要满足以下条件：(1)若A去，则C 同去。(2)若B去，则C 不能去。(3)若C 不去，则A 与B 可以去。由于m1=p qr,m2=pq r,m5=p qr可知选派方案有三种：(1)C去，而A,B 都不去。(2)B去，而A,C都不去。(3)A,C同去去，而B 不去。简单命题符号化简单命题符号化复合命题符号化复合命题符号化命题公式等值演算命题公式等值演算求求命题公式的主命题公式的主析取范式析取范式极小项的定义极小项的定义命题公式的成真命题公式的成真赋值与成假赋值赋值与成假赋值24个重要等值式4.应用题应用题解：(1)设 p：天气凉快；q：小王去游泳。前提：pq，p结论：q推理的形式结构为：例题：判断下面各推理是否正确。例题：判断下面各推理是否正确。(1)如如果果天天气气凉凉快快，小小王王就就不不去去游游泳泳。天天气气凉凉快快，所所以以小小王王没没去去游泳。游泳。(2)如如果果我我上上街街，我我一一定定去去新新华华书书店店。我我没没上上街街。所所以以我我没没去去新新华书店。华书店。(*)说明(*)式为重言式，所以推理正确将简单命题符号化简单命题符号化写出前提、结论和写出前提、结论和推理的形式结构推理的形式结构命题公式等命题公式等值演算值演算重言式的重言式的判断判断主主析取范式析取范式的求取的求取推理的正确推理的正确性判断性判断5.在一阶逻辑中命题符号化问题在一阶逻辑中命题符号化问题例例:用量词、谓词来表述命题。用量词、谓词来表述命题。(1)凡是人都是要死的。凡是人都是要死的。设命题函数：设命题函数：():是要死的；是要死的；设特性谓词：设特性谓词：():是人；是人；()()(2)兔子比乌龟跑得快。兔子比乌龟跑得快。令令F(x):x是兔子，是兔子，G(y):y是乌龟，是乌龟，H(x,y):x比比y跑得快跑得快 x y(F(x)G(y)H(x,y)个体词个体词谓词谓词个体变项个体变项谓词函数谓词函数一元一元二元二元量词量词指导变元指导变元辖域辖域全称量词全称量词存在量词存在量词6.判断一阶逻辑公式的类型判断一阶逻辑公式的类型解解为方便起见，用为方便起见，用A，B，C分别记分别记(1)，(2)，(3)中的公式。中的公式。(1)取解释取解释I1:个体域为实数集合个体域为实数集合R，F(x):x是整数，是整数，G(x):x是有是有理数。在理数。在I1下下A为真，因而为真，因而A不是矛盾式。取解释不是矛盾式。取解释I2:个体域仍然个体域仍然为为R，F(x):x是无理数，是无理数，G(x):x能表示成分数。在能表示成分数。在I2下下A为假，所为假，所以以A不是永真式。故不是永真式。故A是非永真式的可满足式。是非永真式的可满足式。(2)易知易知B是命题公式是命题公式p(qp)的代换实例，而该命题公式是的代换实例，而该命题公式是重言式，所以重言式，所以B是永真式。是永真式。(3)C是命题公式是命题公式(pq)q的代换实例，而该命题公式是矛的代换实例，而该命题公式是矛盾式，所以盾式，所以C是矛盾式。是矛盾式。7.判断一阶逻辑公式是否等值判断一阶逻辑公式是否等值五组重要等值式五组重要等值式三组基本规则三组基本规则自由出现和约束自由出现和约束出现变项出现变项8.求公式的前束范式求公式的前束范式五组重要等值式五组重要等值式三组基本规则三组基本规则自由出现和约束自由出现和约束出现变项出现变项例题：求公式的前束范式例题：求公式的前束范式(x1F(x1,x2)x2G(x2)x1H(x1,x2,x3)解：解：(x1F(x1,x2)x2G(x2)x1H(x1,x2,x3)(x4F(x4,x2)x5G(x5)x1H(x1,x2,x3)x4 x5(F(x4,x2)G(x5)x1H(x1,x2,x3)x4 x5 x1(F(x4,x2)G(x5)H(x1,x2,x3)(换名规则换名规则)(量词辖域收缩与扩量词辖域收缩与扩张等值式张等值式第三式第三式)(量词辖域收缩与扩量词辖域收缩与扩张等值式张等值式第三式第三式)例题例题在自然推理系统在自然推理系统F 中，构造下面推理的证明：中，构造下面推理的证明：任何自然数都是整数，存在着自然数，所以存在着整数，个体任何自然数都是整数，存在着自然数，所以存在着整数，个体域为实数集合域为实数集合R.解解先将原子命题符号化。先将原子命题符号化。设设F(x):x为自然数，为自然数，G(x):x为整数。为整数。前提：前提：x(F(x)G(x),xF(x)结论：结论：xG(x)9.构造推理的证明构造推理的证明将简单命题符号化简单命题符号化写出前提、结论和写出前提、结论和推理的形式结构推理的形式结构命题公式等值演算命题公式等值演算五组重要等值式五组重要等值式三组基本规则三组基本规则推理的证明过程推理的证明过程思考题1.53是命题吗？2.53是命题公式吗？3.5x是命题公式吗？4.5x是命题吗？5.为什么不能机械地检验P=Q的正确性，却可以机械地检验P-Q是否为永真公式？