第一章 命题逻辑-additional.ppt

1、命题逻辑,1/22,2/22,启发,离散的思考 对偶的考虑问题,3/22,命题逻辑的应用与练习,命题逻辑也称二值逻辑，它是用数学方法研究判定和推理的一门科学。 所谓判定是指在有限步内，判定一个命题公式是永真的、永假的或是可满足的问题。 推理也称演绎或叫证明它是按照公认的推论规则（P，T，CP，F），从前提集合中推导出一个结论来，这样的一个推导序列称为演绎或形式证明。 因此，命题逻辑的核心任务是判定与推理。我们做练习也是以这样一个核心为主。,4/22,前面我们曾经介绍过等价变换和逻辑联结词最小功能完备集的概念，当一个实际问题用命题逻辑表达出来后我们可以利用等价变换使之仅含逻辑联结词、，然后可以选

2、用逻辑部件组成其逻辑电路。 逻辑联结词和逻辑部件的对应关系如下： ： ： ,命题逻辑的应用与练习,5/22,命题逻辑的应用与练习,练习1、给定命题公式: P (Q R) S给出对应的逻辑电路 解： P (Q R) S ( P (Q R) S P Q R S./*黑板画*/,6/22,命题逻辑的应用与练习,练习2、用命题逻辑设计bus报站系统。 分析：用P表示bus运行的方向， 用Qi表示当前站点， 用Ri表示报站内容，于是bus报站的逻辑表达式就可以设计出来了： P Qi Ri 例如P为0，i为1则表示上行并且当前站为栾金村，R1为语音：下一站海事大学，上车的乘客请往后面走，前门只上不下。 /

3、*请注意若一条线路上有多个站点，是否应设多个按纽？*/,7/22,命题逻辑的应用与练习,练习3、求出下列各式的主析取范式和主合取范式： （1）(pq)(pq) 解：上式(pq)(pq) (pq)(pq)(pq) m11,m10,m01 m1,m2,m3 M00 pq 问题得证。,8/22,命题逻辑的应用与练习,(2)(pq)(pr) 解：上式(pq)(pr) （pq)(pr) (pqr) M010 m000,m001,m011,m100,m101，m110，m111,9/22,命题逻辑的应用与练习,练习4、用将公式化为主范式的方法证明下列等价式 （1）(AB)(AB)(AB)(BA) 解： 左

4、(AB)(AB)(AB)(AB) (AB)(AB) m10,m11 右(AB)(BA) (AB)(BA) M00,M01 m10,m11 问题得证。,10/22,命题逻辑的应用与练习,(2) A(A(AB)(AB)(AB) 解： 左A(A(AB) A(BB)(A(BB)(AB) (AB)(AB)(AB)(AB)(AB) (AB)(AB)(AB)(AB) m00,m01 ,m10,m11,11/22,右(AB)(AB)(AB)(AB) (AB)(AB) (A(BB)B(AA)(AB) (AB)(AB)(AB)(AB)(AB) (AB)(AB)(AB)(AB) m00,m01 ,m10,m11 问

5、题得证。,命题逻辑的应用与练习,12/22,命题逻辑的应用与练习,练习5、一家航空公司为了保证安全，用计算机复核飞行计划。每台计算机能给出飞行计划正确或者有误的回答。由于计算机也有可能发生故障，因此采用3台计算机同时复核。由所给答案，根据“少数服从多数”的原则作出判断。试将结果用公式表示，并加以简化，画出电路图。 解：设C1，C2，C3分别表示3台计算机的答案，S表示判断结果，根据题意可有下面的真值表：,13/22,C1 C2 C3 S 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1,命题逻辑的应用与练习,14/2

6、2,命题逻辑的应用与练习,并且S=(C1 C2 C3) (C1 C2 C3) (C1 C2 C3) (C1 C2 C3) = (C1 C2) (C1 C2 C3) (C1 C2 C3).,15/22,命题逻辑的应用与练习,练习6、有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两扇门，一为自由，一为死亡，你可任意开启一门。为协助你逃脱，加派两名战士负责回答你所提出的问题，唯可虑者，此两名战士一名天性诚实，一名说谎成性，今后生死由你自己选择”。逻辑学家沉思片刻，即向一战士发问，然后开门从容离去，逻辑学家该如何发问？ 解：逻辑学家手指一门问身边的战士说：“这扇门是死亡门，他

7、（指另一名战士）将说是对吗？” 当被问战士回答“对”，则逻辑学家开启所指的门离去。当被问战士回答“否”，他开启另一扇门离去。,16/22,命题逻辑的应用与练习,设P：被问战士是诚实人 Q：被问战士回答对 R：另一名战士的回答为“是” S：这扇门是死亡门 真值表如下： P Q R S 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 0,17/22,命题逻辑的应用与练习,练习5、A、B、C、D 4个人中要派两个人出差，按下述3个条件有几种派法？如何派？并编程验证给出的结论。 (1)若A去，则C和D中要去一人； (2)B和C不能都去； (3)C去则D要留下,18/22,命题逻辑的应用与练

8、习,解：本题的意思是求同时满足上面3个条件的派法。 由组合数学知C42=(4*3)/2=6种 这6种派法是：P1：AB ；P2：AC ；P3：AD P4：BC ；P5：BD ；P6：CD 但是由于P1不满足条件(1), P6不满足条件(3),P4不满足条件(2)所以均被排除。剩下3种派法是P2：AC；P3：AD和 P5：BD,19/22,命题逻辑的应用与练习,练习符号化下列命题并推证其结论的有效性。 、明天是晴天，或者是下雨；如果是晴天，我就去看电影；如果我去看电影，我就不看书。结论：如果我在看书，则天在下雨。 解：首先符号化，并令 ：明天是晴天。 ：明天下雨。 ：明天我去看电影。 ：明天我看书。于是问题可描述成：,20/22,命题逻辑的应用与练习,PQ,PR,RSSQ 1.S P规则(附加前提) 2.RS P规则 3.R T规则及和 4.PR P规则 5.P T规则及3和4 6. PQ P规则 7.Q T规则及5和6 8. SQ CP规则及和,21/22,命题逻辑的应用与练习,.如果今天我没课，则我就去机房上机或去图书馆查资料；若机房没有空机器，那麽我没法上机；今天我没课，机房也没空机器所以今天我去图书馆查资料。 解；首先定义下列符号： ：今天我没课。 ：我去机房上机。 ：我去图书馆查资料