谓词逻辑总结

1、数理逻辑部分数理逻辑部分小结小结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)命题命题联结词联结词命题公式命题公式真值表真值表命题符号命题符号谓词和个体谓词和个体量词量词一阶逻辑公式一阶逻辑公式置换规则置换规则一阶逻

2、辑前束范式一阶逻辑前束范式命题逻辑命题逻辑一阶谓词逻辑一阶谓词逻辑公式解释公式解释符号化符号化等值式与等值演算等值式与等值演算等值式等值式主析主析( (合合) )取范式取范式命题逻辑推理理论命题逻辑推理理论一阶谓词逻辑一阶谓词逻辑推理理论推理理论重要题型重要题型1.求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值()pqr 真值表法真值表法最简单、最最简单、最直观的方法直观的方法表 1 ()pqr 的真值表 p q r p r pq (pq) r 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1

3、0 1 0 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 重要题型重要题型1.求公式的成真赋值与成假赋值求公式的成真赋值与成假赋值/判断公式类型判断公式类型()pqr 真值表法真值表法最简单、最最简单、最直观的方法直观的方法主析取范式法主析取范式法 m0m1m2m4m5 m6m7 2.判断两个命题公式是否等值判断两个命题公式是否等值()pqpq 真值表法真值表法最简单、最最简单、最直观的方法直观的方法表 2 pq 和和(pq)的的真真值值表表 p q q pq (pq) pq 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0 1 1

4、2.判断两个命题公式是否等值判断两个命题公式是否等值()pqpq 真值表法真值表法最简单、最最简单、最直观的方法直观的方法等值演算法等值演算法 pq (p q)最基本最基本的方法的方法2.判断两个命题公式是否等值判断两个命题公式是否等值()pqpq 真值表法真值表法最简单、最最简单、最直观的方法直观的方法等值演算法等值演算法右边 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

5、 中挑选12名出国进修。由于工作需要，选派时要满足以下条件：(1) 若A去，则C 同去。(2) 若B去，则C 不能去。(3) 若C 不去，则A 与B 可以去。()()()prqrrpq 125mmm由于m1= p qr, m2= pq r, m5= p qr可知选派方案有三种：(1) C去，而A,B 都不去。(2) B去，而A,C都不去。(3) A,C同去去，而B 不去。简单命题符号化简单命题符号化复合命题符号化复合命题符号化命题公式等值演算命题公式等值演算求命题公式的主求命题公式的主析取范式析取范式极小项的定义极小项的定义命题公式的成真命题公式的成真赋值与成假赋值赋值与成假赋值24个重要等值

6、式4.应用题应用题解：(1) 设 p：天气凉快；q：小王去游泳。前提：pq，p结论：q推理的形式结构为：pqpq()例题：判断下面各推理是否正确。例题：判断下面各推理是否正确。(1) 如果天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。如果天气凉快，小王就不去游泳。天气凉快，所以小王没去游泳。(2) 如果我上街，我一定去新华书店。我没上街。所以我没去新华书如果我上街，我一定去新华书店。我没上街。所以我没去新华书店。店。(*)()1pqpq 0123()pqpqmmmm 说明(*)式为重言式，所以推理正确将简单命题符号化简单命题符号化写出前提、结论和写出前提、结论和推理的形式结构推理的形式

7、结构命题公式等命题公式等值演算值演算重言式的重言式的判断判断主析取范式主析取范式的求取的求取推理的正确推理的正确性判断性判断5.在一阶逻辑中命题符号化问题在一阶逻辑中命题符号化问题例例: 用量词、谓词来表述命题。用量词、谓词来表述命题。 (1)凡是人都是要死的。凡是人都是要死的。设命题函数：设命题函数： ():是要死的；是要死的；设特性谓词：设特性谓词： ():是人；是人； ( ( ()( () (2) 兔子比乌龟跑得快。兔子比乌龟跑得快。令令F(x):x是兔子，是兔子，G(y):y是乌龟，是乌龟，H(x,y):x比比y跑得快跑得快 x y(F(x)G(y)H(x,y)个体词个体词谓词谓词个体

8、变项个体变项谓词函数谓词函数一元一元二元二元量词量词指导变元指导变元辖域辖域全称量词全称量词存在量词存在量词6.判断一阶逻辑公式的类型判断一阶逻辑公式的类型 (1) ( ( )( )( )( , )( )( )( )( )x F xG xxF xx yG x yxF xxF xyG yyG y 例例题题： 判断下列公式中，哪些是永真式，哪些是矛盾式？(2)(3)解解 为方便起见，用为方便起见，用A，B，C分别记分别记(1)，(2)，(3)中的公式。中的公式。 (1)取解释取解释I1:个体域为实数集合个体域为实数集合R，F(x):x是整数，是整数，G(x):x是是有理数。在有理数。在I1下下A为

9、真，因而为真，因而A不是矛盾式。取解释不是矛盾式。取解释I2:个体域仍个体域仍然为然为R，F(x):x是无理数，是无理数，G(x):x能表示成分数。在能表示成分数。在I2下下A为假，为假，所以所以A不是永真式。故不是永真式。故A是非永真式的可满足式。是非永真式的可满足式。 (2)易知易知B是命题公式是命题公式p(qp)的代换实例，而该命题公式的代换实例，而该命题公式是重言式，所以是重言式，所以B是永真式。是永真式。 (3)C是命题公式是命题公式(pq)q的代换实例，而该命题公式是的代换实例，而该命题公式是矛盾式，所以矛盾式，所以C是矛盾式。是矛盾式。 7.判断一阶逻辑公式是否等值判断一阶逻辑公

10、式是否等值 ( )( )( )( )x M xF xx M xF x ( )( )( )( ) ( )( )( )( )x M xF xxM xF xxM xF xx M xF x 证： 左边（量词否定等值式）（置换规则）（置换规则）五组重要等值式五组重要等值式三组基本规则三组基本规则自由出现和约束自由出现和约束出现变项出现变项8.求公式的前束范式求公式的前束范式五组重要等值式五组重要等值式三组基本规则三组基本规则自由出现和约束自由出现和约束出现变项出现变项例题：求公式的前束范式例题：求公式的前束范式( x1F(x1,x2) x2G(x2) x1H(x1,x2,x3) 解：解： ( x1F(x

11、1,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.构造推理的证明构造推理的证明将简单命题符号化简单