数理逻辑总结

1、1总结总结第第一一章章 命题逻辑命题逻辑命题；命题；命题联结词：否定命题联结词：否定( )( )，合取，合取( )( )，析取，析取( )( )，异或，异或( )( )，蕴含，蕴含( )( )，等值，等值( )( )； 原子命题和复合命题；原子命题和复合命题； 命题符号化命题符号化。 1. 1. 命题命题 命题常元，命题变元，命题公式命题常元，命题变元，命题公式( (或称公式或称公式) )； 命题公式命题公式F(PF(P1 1,P,P2 2, ,P,Pn n) )的真值指派，公式的真值表；的真值指派，公式的真值表； 命题公式的分类：重言式命题公式的分类：重言式( (或永真式或永真式) )、矛盾

2、式、矛盾式( (或永假或永假式式) )和可满足公式；和可满足公式； 2. 2. 命题公式命题公式 2总结总结第第一一章章 命题逻辑命题逻辑3. 3. 命题公式间的关系命题公式间的关系 命题公式间的等价关系命题公式间的等价关系( )( )命题公式间的蕴含关系命题公式间的蕴含关系( ) ( ) 基本的等价式；基本的等价式； 基本的蕴含式基本的蕴含式；判断公式类型的方法判断公式类型的方法( (真值表、等价公式变换、主范式真值表、等价公式变换、主范式) )； 判定两公式是否具有等价和蕴含关系的方法判定两公式是否具有等价和蕴含关系的方法。ABAB3总结总结第第一一章章 命题逻辑命题逻辑推理的概念：推理的

3、概念：推理规则：四个规则推理规则：四个规则；4. 4. 命题逻辑的推理理论命题逻辑的推理理论 12nHHHC4练习练习9-1 1. 判断下列语句哪些是命题，若是命题，则指出其真值。判断下列语句哪些是命题，若是命题，则指出其真值。 （1） 只有小孩才爱哭。只有小孩才爱哭。 （2） X+6=Y （3） 银是白的。银是白的。 （4） 起来吧，我的朋友。起来吧，我的朋友。( 是是 假假 ) ( 不是不是 )( 是是 真真 ) ( 不是不是 ) 2 将下列命题符号化将下列命题符号化 （1 1）我看见的既不是小张也不是老李。）我看见的既不是小张也不是老李。 解解 令令P：我看见的是小张；：我看见的是小张；

4、Q：我看见的是老李。：我看见的是老李。 则该命题可表示为则该命题可表示为PQ （2）如果晚上做完了作业并且没有其它的事，他就会如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。看电视或听音乐。 解解 令令 P：他晚上做完了作业；：他晚上做完了作业；Q：他晚上有其它的事；：他晚上有其它的事； R：他看电视；：他看电视； S：他听音乐。：他听音乐。 则该命题可表示为则该命题可表示为（PQ）（RS）5“如果嫦娥是虚构的，而如果圣诞老人也是虚构的，那如果嫦娥是虚构的，而如果圣诞老人也是虚构的，那么许多孩子受骗了。么许多孩子受骗了。”解：解：令令P：嫦娥是虚构的；：嫦娥是虚构的；Q：圣诞老人是虚

5、构的；：圣诞老人是虚构的；R：许多孩子受骗了。：许多孩子受骗了。则一上语句可表示为：则一上语句可表示为： 或或RQP)()(RQP3判断下面一段论述是否为真：判断下面一段论述是否为真：“ 是是 无理数，并且，如果无理数，并且，如果3是无理数，则是无理数，则 也是无理数，也是无理数，另外，只有另外，只有6能被能被2整除时，整除时，6才能被才能被4整除整除”2解：解：令令P： 是无理数；是无理数； S：6能被能被2整除整除 Q：3是无理数：是无理数： H：6能被能被4整除整除 R： 是无理数是无理数语句符号化为：语句符号化为： 1 0 1 0 1命题的真值为真。命题的真值为真。)()(SHRQP2

6、64. 证明下列命题公式的等值关系证明下列命题公式的等值关系（1） （P Q） （PQ） （PQ）（2）（）（P （Q R） （P Q）（P R）解解 (1) （P Q） （PQ）（ P Q） E12 （PQ）（PQ） E10，E6 （P Q） （PQ） （PQ）（2）（P Q）（P R） （ P Q）（ PR） E11 （ P P）（ QR） E1，E2 P（ QR） E7 P （Q R） （P P （Q Q R R） （P P Q Q）（P P R R）75、求出下式的主析取范式、求出下式的主析取范式1） （PQ） （RP）2）（）（PQ）（R P）解：解：1） （PQ） （RP）= （

7、P Q） （ R P）=（PQ） （ R P）=（PQR） （PQ）=（PQR） （PQ R） （PQ R）2）（）（PQ）（R P）=（ P Q）（R P）= （ P Q） （R P）=（PQ） （R P）=（P R） （PQ R）=（P Q R） （PQ R）=M0M2= m1,m3,m4,m5,m6,m7=( PQ R) ( P Q R) (PQR) (PQ R) (P QR) (P Q R)86. 用主范式方法证明下列命题公式的等值关系用主范式方法证明下列命题公式的等值关系（1 1）( ( A A B)B)(A(A B)B)(A(A B)B) (B(BA)A)解：解： 左左( ( A

8、A B)B)(A(A B)B)( A A B)B) (A(A B)B) (A (AB)B) (A(A B)B) m m1010,m,m1111 右右(A(A B)B) (B(BA)A) (A (A B)B) ( ( B B A)A) M M0000,M,M0101 m m1010,m,m11 11 问题得证。问题得证。99/22(2) A(2) A ( ( A A (A(A B)B)( ( A AB)B)(A(AB)B)解：解： 左左A A ( ( A A (A(A B)B) A A (B(BB)B) ( ( A A (B(BB)B) (A(A B)B) (A(A B)B) (A(AB)B)

9、( ( A A B)B) ( ( A AB)B) (A(A B)B) ( ( A AB)B) ( ( A A B)B) (A(AB)B) (A(A B)B) m m0000,m,m01 01 ,m,m1010,m,m1111右右( ( A AB)B)(A(AB)B)( ( A AB)B)( ( A AB)B) ( ( A AB)B) (A(A B) B) ( ( A A (B(BB)B)B B (A(AA)A) (A(A B)B) ( ( A A B)B) ( ( A AB)B) (A(AB)B) ( ( A AB)B) (A(A B)B) ( ( A AB)B) ( ( A A B)B) (

10、A(AB)B) (A(A B)B) m m0000,m,m01 01 ,m,m1010,m,m1111 问题得证。问题得证。1010/227.7.符号化下列命题并推证其结论的有效性。符号化下列命题并推证其结论的有效性。、明天是晴天，或者是下雨；如果是晴天，、明天是晴天，或者是下雨；如果是晴天，我就去看电影；如果我去看电影，我就不看我就去看电影；如果我去看电影，我就不看书。结论：如果我在看书，则天在下雨。书。结论：如果我在看书，则天在下雨。解：首先符号化，并令解：首先符号化，并令：明天是晴天。：明天是晴天。：明天下雨。：明天下雨。：明天我去看电影。：明天我去看电影。：明天我看书。于是问题可描述成

11、：明天我看书。于是问题可描述成：1111/22P P Q,PQ,PR,RR,RS SS SQ Q1.S P1.S P规则规则( (附加前提附加前提) )2.R2.RS PS P规则规则3.3. R TR T规则及和规则及和4.P4.PR PR P规则规则5.5. P TP T规则及规则及3 3和和4 46. P6. P Q PQ P规则规则7.Q T7.Q T规则及规则及5 5和和6 68. S8. SQ CPQ CP规则及和规则及和1212/22. .如果今天我没课，则我就去机房上机或去如果今天我没课，则我就去机房上机或去图书馆查资料；若机房没有空机器，那麽图书馆查资料；若机房没有空机器，那

12、麽我没法上机；今天我没课，机房也没空机我没法上机；今天我没课，机房也没空机器所以今天我去图书馆查资料。器所以今天我去图书馆查资料。解；首先定义下列符号：解；首先定义下列符号：今天我没课。：今天我没课。：我去机房上机。：我去机房上机。：我去图书馆查资料。：我去图书馆查资料。：机房没有空机器。：机房没有空机器。于是问题可描述为：于是问题可描述为：1313/22P P(Q(Q R),SR),SQ,PQ,P S S R R P P S S 规则规则2. P T2. P T规则和规则和1 13. S3. S T T规则和规则和1 14. S4. SQ Q 规则规则5. 5. Q TQ T规则规则3 3和

13、和4 46. P6. P(Q(Q R) R) 规则规则7. Q7. Q R TR T规则规则2 2和和6 68. R T8. R T规则规则5 5和和7 71414/22 前面我们曾经介绍过等价变换和逻辑联结词最小功能前面我们曾经介绍过等价变换和逻辑联结词最小功能完备集的概念，当一个实际问题用命题逻辑表达出来完备集的概念，当一个实际问题用命题逻辑表达出来后我们可以利用等价变换使之仅含逻辑联结词后我们可以利用等价变换使之仅含逻辑联结词 、 、 ，然后可以选用逻辑部件组成其逻辑电路。，然后可以选用逻辑部件组成其逻辑电路。 逻辑联结词和逻辑部件的对应关系如下：逻辑联结词和逻辑部件的对应关系如下： ：

14、 ： 1515/22 8、给定命题公式、给定命题公式: P (Q R) S给出对应的逻辑电路给出对应的逻辑电路 解：解： P (Q R) S ( P (Q R) S P Q R S./*黑板画黑板画*/169.设计一盏灯的开关电路时，要求三个开关设计一盏灯的开关电路时，要求三个开关A，B，C的控制：的控制：当且仅当当且仅当AC同时关闭或者同时关闭或者BC同时关闭时灯亮。用同时关闭时灯亮。用F表示灯表示灯亮，亮，p,q,r分别表示开关分别表示开关A，B，C关闭，求关闭，求F=F(p,q,r)的逻辑的逻辑表达式以及表达式以及F的主范式。的主范式。解：解：F=F(p,q,r)=(p r) (q r)

15、F的主析取范式为：的主析取范式为：F=(p (q q) r) (p p) q r) =(p q r) (p q r) (p q r) ( p q r) =(p q r) (p q r) ( p q r) =m111 m101 m011 = m3,5,7= M0,1,2,4,51710.某电路中有某电路中有1只灯泡和只灯泡和3个开关个开关A，B，C。已知当且仅当。已知当且仅当在下述在下述4种情况之一灯亮。种情况之一灯亮。（1）C的搬键向上，的搬键向上，A和和B的搬键向下。的搬键向下。（2）A的搬键向上，的搬键向上，B和和C的搬键向下。的搬键向下。（3）B和和C的搬键都向上，的搬键都向上，A的搬键

16、向下。的搬键向下。（4）A和和B的搬键都向上，的搬键都向上，C的搬键向下。的搬键向下。求灯亮的逻辑表达式以及主范式。求灯亮的逻辑表达式以及主范式。解：另解：另F表示灯亮，表示灯亮，p,q,r分别表示分别表示A,B,C的搬键向上，则的搬键向上，则F=F(p,q,r) =( p qr)(p q r)( pqr) (pq r) =m001 m100 m011 m110 = m1,3,4,6 = M0,2,5,7 =(pqr)(p qr)( pq r)( p q r) 1818/2211、一家航空公司为了保证安全，用计算机复核、一家航空公司为了保证安全，用计算机复核飞行计划。每台计算机能给出飞行计划正

17、确或飞行计划。每台计算机能给出飞行计划正确或者有误的回答。由于计算机也有可能发生故障，者有误的回答。由于计算机也有可能发生故障，因此采用因此采用3台计算机同时复核。由所给答案，根台计算机同时复核。由所给答案，根据据“少数服从多数少数服从多数”的原则作出判断。试将结的原则作出判断。试将结果用公式表示，并加以简化，画出电路图。果用公式表示，并加以简化，画出电路图。 解：设解：设C1，C2，C3分别表示分别表示3台计算机的答案，台计算机的答案，S表示判断结果，根据题意可有下面的真值表：表示判断结果，根据题意可有下面的真值表：1919/22 C1 C2 C3 S 0 0 0 0 0 0 1 0 0 1

18、 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 12020/22 并且并且S=( C1 C2 C3) (C1 C2 C3) (C1 C2 C3) (C1 C2 C3) = (C1 C2) ( C1 C2 C3) (C1 C2 C3).2111.在一次研讨会上，在一次研讨会上，3名与会者根据王教授的口音分别进行名与会者根据王教授的口音分别进行下述判断：下述判断：甲说：甲说：“王教授不是苏州人，是上海人王教授不是苏州人，是上海人”乙说：乙说：“王教授不是上海人，是苏州人王教授不是上海人，是苏州人”丙说：丙说：“王教授不是杭州人，也不是上海人王教授不是杭州人，也

19、不是上海人”王教授听后笑道：王教授听后笑道：“你们你们3人中有人中有1人全说对了，有一人全说人全说对了，有一人全说错了，有错了，有1人对错各半人对错各半”。请问王教授是哪里人？请问王教授是哪里人？2222/2212、有一逻辑学家误入某部落，被拘于牢狱，酋长意欲、有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：放行，他对逻辑学家说：“今有两扇门，一为自由，今有两扇门，一为自由，一为死亡，你可任意开启一门。为协助你逃脱，加派一为死亡，你可任意开启一门。为协助你逃脱，加派两名战士负责回答你所提出的问题，唯可虑者，此两两名战士负责回答你所提出的问题，唯可虑者，此两名战士一名天性诚实，

20、一名说谎成性，今后生死由你名战士一名天性诚实，一名说谎成性，今后生死由你自己选择自己选择”。逻辑学家沉思片刻，即向一战士发问，。逻辑学家沉思片刻，即向一战士发问，然后开门从容离去，逻辑学家该如何发问？然后开门从容离去，逻辑学家该如何发问？ 解：逻辑学家手指一门问身边的战士说：解：逻辑学家手指一门问身边的战士说：“这扇门是这扇门是死亡门，他（指另一名战士）将说是对吗？死亡门，他（指另一名战士）将说是对吗？” 当被问战士回答当被问战士回答“对对”，则逻辑学家开启所指的门离，则逻辑学家开启所指的门离去。当被问战士回答去。当被问战士回答“否否”，他开启另一扇门离去。，他开启另一扇门离去。2323/22

21、 设设P：被问战士是诚实人：被问战士是诚实人 Q：被问战士回答对：被问战士回答对 R：另一名战士的回答为：另一名战士的回答为“是是” S：这扇门是死亡门：这扇门是死亡门 真值表如下：真值表如下： P Q R S 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 02424/221313、A A、B B、C C、D 4D 4个人中要派两个人出差，个人中要派两个人出差，按下述按下述3 3个条件有几种派法？如何派？并编个条件有几种派法？如何派？并编程验证给出的结论。程验证给出的结论。(1)(1)若若A A去，则去，则C C和和D D中要去一人；中要去一人；(2)B(2)B和和C C不能都去

22、；不能都去；(3)C(3)C去则去则D D要留下要留下2525/22解：本题的意思是求同时满足上面解：本题的意思是求同时满足上面3 3个条件的派法。个条件的派法。由组合数学知由组合数学知C C4 42 2=(4=(4* *3)/2=63)/2=6种种这这6 6种派法是：种派法是：P1P1：AB AB ；P2P2：AC AC ；P3P3：ADAD P4 P4：BC BC ；P5P5：BD BD ；P6P6：CDCD但是由于但是由于P1P1不满足条件不满足条件(1), P6(1), P6不满足条件不满足条件(3),P4(3),P4不满足条件不满足条件(2)(2)所以均被排除。剩下所以均被排除。剩下

23、3 3种派法是种派法是P2P2：ACAC；P3P3：ADAD和和 P5P5：BDBD2614.符号化下列命题，并用推理方法证明谁是做案者：符号化下列命题，并用推理方法证明谁是做案者：（1）A或或B盗窃了金项链盗窃了金项链（2）若）若A作案，则作案时间不在营业时间作案，则作案时间不在营业时间（3）若）若B提供的证据正确，则货柜不上锁提供的证据正确，则货柜不上锁（4）若）若B提供的证据不正确，则作案时间在营业时间提供的证据不正确，则作案时间在营业时间（5）货柜上锁）货柜上锁另另 P：A盗窃了金项链盗窃了金项链 Q：B盗窃的金项链盗窃的金项链 R：作案时间在营业时间：作案时间在营业时间 S：B提供的

24、证据正确提供的证据正确 G：货柜上锁：货柜上锁27总结总结第二章第二章 谓词逻辑谓词逻辑个体词、谓词和量词：个体词、谓词和量词：个体常元、个体变元、约束变元、自由变元个体常元、个体变元、约束变元、自由变元；命题函数，个体域，全总个体域。命题函数，个体域，全总个体域。1. 1. 基本概念基本概念 原子公式，谓词公式：原子公式，谓词公式：谓词公式的解释谓词公式的解释；谓词公式的分类：永真公式，永假公式，可满足公式。谓词公式的分类：永真公式，永假公式，可满足公式。 2. 2. 谓词公式谓词公式 28总结总结第第二二章章 谓词逻辑谓词逻辑3. 3. 谓词公式间的关系谓词公式间的关系 谓词公式间的等价关

25、系谓词公式间的等价关系( )( )谓词公式间的蕴含关系谓词公式间的蕴含关系( ) ( ) 基本的等价式；基本的等价式； 基本的蕴含式基本的蕴含式；判定两公式是否具有等价和蕴含关系的方法判定两公式是否具有等价和蕴含关系的方法 。ABAB4. 4. 谓词逻辑的推理理论谓词逻辑的推理理论 (1)(1)含有量词的推理规则：全称特指规则含有量词的推理规则：全称特指规则(US)(US)、存在特指规则、存在特指规则(ES)(ES)； (2) P(2) P，T T，CPCP，F F。全称推广规则全称推广规则(UG)(UG)、存在推广规则、存在推广规则(EG)(EG)。29 习习 题题1 1 将下列命题符号化将

26、下列命题符号化. . （1 1）在上海高校学习的学生，未必都是上海籍的学生。）在上海高校学习的学生，未必都是上海籍的学生。 解解 令令 H(x)：x是在上海高校学习的学生是在上海高校学习的学生 S(y)：y是上海籍的学生是上海籍的学生 或者或者)()(xSxHx)()(xSxHx（2 2）没有一位女同志既是国家选手又是家庭妇女。）没有一位女同志既是国家选手又是家庭妇女。 解解 令令W(x):x是一位女同志；是一位女同志； C(x):x是国家选手；是国家选手； H(x):x是家庭妇女是家庭妇女 x(W(x(W(x)C(x)H(x) 30（3 3）对于每一个实数对于每一个实数x x，存在一个更大的

27、实数，存在一个更大的实数y y。 解解 令令R(x)：x是实数；是实数； G(x,y):x比比y大。大。 x(R(x) y y( (R(y)GR(y)G(y,x) （4 4）某些汽车比所有的火车都慢，但至少有一列火车比每）某些汽车比所有的火车都慢，但至少有一列火车比每辆汽车快。辆汽车快。 解解 令令C(x)：x是汽车；是汽车；H(x)：x是火车；是火车； S(x,y): x比比y慢。慢。 ),()()(yxSyHyxCx),()()(zySyCyzHz31 2将下一命题符号化。分析到个体词、谓词和量词，将下一命题符号化。分析到个体词、谓词和量词，使用全总个体域。使用全总个体域。“有些大学生不钦

28、佩任何运动员有些大学生不钦佩任何运动员”解：解： 令令P(x): x 是大学生是大学生Q(y): y 是运动员是运动员 H(x, y): x 钦佩钦佩 y( ( )( ( )( , )x P xy Q yH x y命题符号化为323.将下列各公式翻译成自然语言，个体域为整数集将下列各公式翻译成自然语言，个体域为整数集I，并判，并判断各命题的真值。断各命题的真值。(1)(2)(3)(zyxZyx) 1(yxyx)(ZyxZyx解解: (1)对任意整数对任意整数 任意整数任意整数 ，存在整数，存在整数 ，使得使得 。（真命题）。（真命题）(2)对任意整数对任意整数 ，存在整数，存在整数 ，使得，使

29、得 （假命题）（假命题）(3)存在整数存在整数 ，使得对于任意整数，使得对于任意整数 和任意整数和任意整数 ，有有 （假命题）（假命题）ZZyxxy1 yxZyxxyxyZ334试判断下列公式是否永真公式试判断下列公式是否永真公式)()()()(xxQxxPxQxPx(1) 解：解：原式原式)()()()(xxQxxPxQxPx)()()()(xxQxxPxQxPx)()()()(xxQxxPxQxPx)()()()(xxPxxQxQxPx)()()()(xxPxQxQxPx)()()(xxPxQxPx)()()(xxPxxQxPx)()()(xxQxxPxxP( )TxQ xT因此，（因此，

30、（1）式是永真公式。）式是永真公式。 34（2）)()()()(yQxxPyQxPx 解：原式解：原式)()()()(yQxxPyQxxP)()()()(yQxxPyQxxP)()()()(yQxPxyQxxP)()()()()()(yQxPxyQyQxPxxxP)()()(yQxPxxxP此公式不是永真公式此公式不是永真公式设设Q(y) F，个体域，个体域E = a,b,P(a)=T,P(b)=F，则，则 但但因此因此不是永真公式。不是永真公式。( ( )( )x P xQ yT( )( )xP xQ yF)()()()(yQxxPyQxPx355 5 用等价公式变换法证明下一等值式用等价公

31、式变换法证明下一等值式)()()()()()(x,yHyGxFyxx,yHyGxFyx证明证明( ( )( )() )x y F xG yH x,y y( ( )()()( )xF xG yH x,y ( )( )()() )x yF xG yH x,y ( ( )( )()()x y F xG yH x,y (1)36(2)( ( )( )( )( )x A xB xxA xxB x 证明证明( ( )( )x A xB x( )( )xA xxB x ( )( )xA xxB x ( )( )xA xxB x ( )( )xA xB x 376 6 证明下一蕴含式证明下一蕴含式证法一：证法

32、一：此题等价于证明( )( )( ( )( )1()xP xxQ xx P xQ x (PQ)RP(QR)根据此题又等价于证明( )( )()( ( )( )1xP xxQ xx P xQ x )()()()(xQxPxxxQxxP38( )( )()( ( )( )xP xxQ xx P xQ x ( )( )( ( ) ) )(xP xx Q xP xQ x ( )( )( )( )() )(xP xxQ xP xQ x ( )( )( )xP xxQ xP x ( )( )( )xP xx Q xxP x 1396 6 证明下一蕴含式证明下一蕴含式)()()()(xQxPxxxQxxP证

33、法二：证法二：为真假设)()(xxQxxP为真为真，且则)()(xxQxxP因此，必存在个体因此，必存在个体c，使，使P(c) 为真，为真， Q(c) 为真。为真。为真，于是)()(cQcP为真故)()(xQxPx40 7. 7. 用构造推理过程的方法证明用构造推理过程的方法证明)()()()()1(aQxxPaQxPx证明证明(1)( ( )( )x P xQ aP(2)( ( ( )( )(1)xP xQ aT ，(3)( )( )(2)xP xQ aT ，(4)( )( )(3)xP xQ aT ，(5)( )( )(4)xP xQ aT，(6)( )( )(5)xP xQ aT，41(2)( )( ( )( ),( )( )( ( )( )( )xF xy G yH yxM xyG yx F xM xyH y证明证明(1)( )( ( )( )xF xy G yH yP(6)( ( )( )(1),(5)y G yH yT，(4)( )( )(3)xF xxM xT，(3)( ( )M( )x F xxP（附加前提）(2)( )( )xM xyG yP(7)( )(4)xM xT，(5)( )(4)xF xT，(9)( );(8)G cES(8)( )(2),(7)yG yT，(10)( )( );(6)G cH cUS(11)( )(9),(10)H cT，EG