第一篇数理逻辑

1、1.1 1.1 命题及联结词命题及联结词例例1.1 1.1 下列句子中那些是命题？下列句子中那些是命题？ （1 1）雪是白的。）雪是白的。（2 2）2 2是奇数。是奇数。（3 3）（4 4）22002200年的元旦是晴天。年的元旦是晴天。（5 5）火星上有生物。）火星上有生物。（6 6）请安静！）请安静！（7 7）现在是几点钟）现在是几点钟? ?（8 8）我正在撒谎。）我正在撒谎。5xy例例 求命题公式求命题公式P PQ Q和和 (P (P Q) Q)的真值表。的真值表。()()()PQPQPQ 试证试证:()()()()P QPPQ QQP ()PQ() ()PQQP()()PQQP()()

2、P QQP ()()PQQP() ()P QPQ 证明：证明：（1）A不去，不去，B不去，不去，C去；（去；（2）A不去，不去，B去，去，C不去。不去。如果只安排一个人参加，则有两种情况：如果只安排一个人参加，则有两种情况：因此，符合条件的只有一种情况：因此，符合条件的只有一种情况：A去，去，B不去，不去，C去。去。()()()PRQRRPQ ()()()PQRPQRPQR 化为主析取范式为：化为主析取范式为：()()()PRQRRPQ 条件符号化为：条件符号化为：010101110AMMM解：因为解：因为其它赋值都是其它赋值都是A A的成真赋值：的成真赋值：000000，001001，011

3、011，100100，111111。所以所以A A的成假赋值为（按照字母顺序）：的成假赋值为（按照字母顺序）：010，101，110；(1)PQ前提引入前提引入证明：证明：(2) PQ （2）（）（4）假言三段论假言三段论(3) QS(4)QS （3）置换）置换(6) SP（1）置换）置换(5)PS前提引入前提引入 （5）置换（假言异位）置换（假言异位）(7)PR(8)()()PRRP(9)PR(10) SR(11)SR 前提引入前提引入 （7 7）置换）置换 （8 8）化简）化简 （6 6）（）（9 9）假言三段论）假言三段论 （1010）置换）置换所以，结论有效所以，结论有效注：课本中注：

4、课本中 P.23-26 P.23-26 例例 1.31(6),1.31(6),例例 1.34(2),1.34(2),例例 1.36(2),(7),1.36(2),(7),例例 1.38(2) 1.38(2) 实属多余，应删除实属多余，应删除欲证明欲证明(A(A1 1 A A2 2 A An n ) ) (A (A B ) B ) ，只需证明只需证明 (A(A1 1 A A2 2 A An n A )A ) B B 即可。即可。例例 如果小张和小王去看电影，则小李也去如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，

5、当小赵去看电影时小小王去看电影。所以，当小赵去看电影时小李也去。判断上述推理是否有效？李也去。判断上述推理是否有效？ 命题是具有真假意义的陈述句。从语法上命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。分析，一个陈述句由主语和谓语两部分组成。 为揭示命题内部结构及其不同命题的内部结为揭示命题内部结构及其不同命题的内部结构关系，就按照这两部分对命题进行分析，并且构关系，就按照这两部分对命题进行分析，并且把主语称为个体或客体，把谓语称为谓词。把主语称为个体或客体，把谓语称为谓词。第第2 2章章 一阶逻辑一阶逻辑 在命题在命题“杭州位于北京和广州之间杭州位于北京和广州之间

6、”中，杭州、北京中，杭州、北京和广州是三个个体，和广州是三个个体， 而而“位于位于和和之间之间”是谓词，是谓词，它刻划了杭州、北京和广州之间的关系。它刻划了杭州、北京和广州之间的关系。 设设 P P（x,y,z)x,y,z)：x x位于位于y y和和z z之间，之间， a a：杭州，：杭州，b b：北京，：北京，c c：广州，：广州， 则则 P(aP(a，b b，c)c)：杭州位于北京和广州之间。：杭州位于北京和广州之间。注意：命题的谓词形式中的个体出现的次序影响命题的注意：命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。真值，不是随意变动，否则真值会有变化。如

7、上述例子中，如上述例子中，P(b,a,c)P(b,a,c)是假。是假。 例如：令例如：令S(x)S(x)：x x是大学生。是大学生。 若若x x的论域为福建师大福清分校的全体同学，则的论域为福建师大福清分校的全体同学，则S(x) S(x) 是真的；是真的； 若若x x的论域是福州一中的全体学生，则的论域是福州一中的全体学生，则S(x)S(x)是假的；是假的； 若若x x的论域是福清市街心公园的全体人员，则的论域是福清市街心公园的全体人员，则S(x)S(x)的真值是不确定的。的真值是不确定的。例例 将下列命题符号化：将下列命题符号化：(1) (1) 张华和李明都是学生；张华和李明都是学生；(2)

8、 2(2) 2既是偶数又是素数；既是偶数又是素数；(3) (3) 如果张三比李四高，并且李四比王五高，则张如果张三比李四高，并且李四比王五高，则张三比王五高。三比王五高。解解 (1) (1) 设个体域是人的集合。设个体域是人的集合。 P(x)P(x)：:x:x是学生。是学生。a a：张华：张华 b b：李明：李明该命题符号化为该命题符号化为P(a)P(a) P(b)P(b)(2) (2) 设个体域为正整数集合设个体域为正整数集合Z Z P(x)P(x)：x x是偶数，是偶数，Q(x)Q(x)：x x是素数，是素数， a a：2 2该命题符号化为该命题符号化为 P(a)P(a) Q(a)Q(a)

9、(3)(3) 设个体域是人的集合设个体域是人的集合 H(x,y)H(x,y)：x x比比y y高，高， a a：张三，：张三， b b：李四，：李四， c c：王五：王五该命题符号化为该命题符号化为H(a,b)H(a,b) H H(b,c)(b,c)H H(a,c)(a,c)4 4、封闭公式（闭式）、封闭公式（闭式）5 5、公式的解、公式的解释释公式的解释通常由以下四个部分构成公式的解释通常由以下四个部分构成（1 1）个体）个体域域（3 3）特定的运算符）特定的运算符（4 4）特定的谓词）特定的谓词P.38 P.38 例例 2.8 (2.8 (自己看）自己看）6 6、有限个体域的量词消去公式、

10、有限个体域的量词消去公式若解释若解释I I的个体域是有限集合的个体域是有限集合 D= eD= e1 1,e,e2 2, , , e en n 则在则在I I中，公式中，公式 xA(x)xA(x)的意义为的意义为A(A(e e1 1) )A(A(e e2 2) )A(A(e en n) )公式公式 xA(x) xA(x)的意义为的意义为A(A(e e1 1) )A(A(e e2 2) )A(A(e en n) )P .39 P .39 例例 2.92.9( )F x( ( )( )x F xG x( )G xxxx( )F x( )G xx( ( )( )x F xG x( ( )( )x F

11、xG x( )( , )( )xF xx yG x yxF x ()PQP()PQQ( )( )( )xF xyG yyG y ()PQQPQQF()()PQPPQPT 已经得证的重要等值式：已经得证的重要等值式： 全称量词只对合取运算满足分配律，存在量词全称量词只对合取运算满足分配律，存在量词只对析取满足分配律。但有：只对析取满足分配律。但有：( ( )( )x F xG x()( )() ( )x F xy G y ( )() ( )x F xy G y ( , )x yF x y ( ( )( )( ( )( )( ( )( )( ( )( )x F xG xF aG aF bG bF

12、cG c解:(1)( ( )( )( )( )( ( )( )( ) ( ( )( )( )x F xyG yxF xyG yF aF bF cG aG bG c()() ( , )() ( , ) () ( , ) () ( , )( ( , )( , )( , )xy F x yy F a yy F b yy F c yF a aF a bF a c ( , )( , )( , )( , )( ( , )( , )( , )x y F x yyF a yyF b yyF c yF a aF a bF a c ( ( , )( , )( , )( ( , )( , )( , )F b aF

13、b bF b cF c aF c bF c cP.46 P.46 例例 2 .17 (1)2 .17 (1)、（、（4 4）( ( )( )x F xG x( ( )( )xF xG x ( )( )xF xG x ( ( )( )x F xG x ( ( )( )x F xG x( ( )( )xF xG x ( )( )xF xG x ( )( )x F xG x 证明：（证明：（1 1）左式）左式= =证明：（证明：（2 2）左式）左式= =注意：一个谓词公式的前束范式不一定惟一。注意：一个谓词公式的前束范式不一定惟一。( , )( , )( , )( , )( , )( , )xP x xx yP x yxP x xx yP x yx yP x yxP x x 讨论公式与公式之间是否有逻辑推论关系即或是否成立