第一章命题逻辑备选

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,1,命题,例,：判断下列语句是否为命题。,陈述句一般为命题,（,1,）十是整数。（）,（,2,）上海是一个村庄。（）,（,3,）今天下雨。,（,4,）加拿大是一个国家。（）,（,5,）是偶数而是奇数。,（,6,）她不是护士。,（,7,）,（,8,）今天是星期天。,1,命题,命令句，感叹句，疑问句均不是命题。,（,1,）把门关上！,（,2,）你到哪里去？,语句既为真，同时又包含假的不是命题，这样的句子称为“,悖论,”。,（,3,）他正在说谎。,（在命题逻辑中不讨论这类问题）,2,命题联结词,例,.,将下列命题符号化：,（,1,）李明是计算机系的学生，他住在,312,室或,313,室。,（,2,）张三和李四是朋友。,（,3,）虽然交通堵塞，但是老王还是准时到达了车站。,（,4,）只有一个角是直角的三角形才是直角三角形。,（,5,）老王或小李中有一个去上海出差。,2,命题联结词,解：,（,1,）首先用字母表示简单命题。,P,：,李明是计算机系的学生。,Q,：,李明住在,312,室。,R,：,李明住在,313,室。,该命题符号化为：,P,（,Q,R,）,（,2,）,张三和李四是朋友。是一个简单句,该命题符号化为：,P,2,命题联结词,（,3,）首先用字母表示简单命题。,P,：,交通堵塞。,Q,：,老王准时到达了车站。,该命题符号化为：,P,Q,（,4,）,首先用字母表示简单命题。,P,：,三角形的一个角是直角。,Q,：,三角形是直角三角形。,该命题符号化为：,P,Q,2,命题联结词,（,5,）首先用字母表示简单命题。,P,：,老王去上海出差。,Q,：,小李去上海出差。,该命题符号化为：,P,Q,也可符号化为：,（,P,Q,）（,PQ,）,或者,（,P,Q,）（,PQ,）,命题公式,P,Q,P Q,（,）,（,）,）,F,F,F,F,T,F,T,T,F,T,T,F,T,T,F,T,T,T,T,F,例构造命题公式,（,）,）的真值表：,命题公式,例写出命题公式,（,）的真值表,P,Q,R,（,),F,F,F,F F,F,F,T,F F,F,T,F,F F,F,T,T,T T,T,F,F,T F,T,F,T,T F,T,T,F,T F,T,T,T,T T,例：证明：（）,（,）,（,）,（,）,例：证明：,（,）,（,（,）,（,）,（,）为一永真式,4,等价式,证明：,原式：（,）,（,（,）,（,）,（,）,（,）,（,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,它是,（永真式）的代换实例，永真式的代换实例仍为永真式！,4,等价式,证明：,原式：（,）,（,（,）,（,）,（,）,（,）,（,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,它是,（永真式）的代换实例，永真式的代换实例仍为永真式！,4,等价式,例：证明：,（）,（,）,（,（,）,（,）,（）（,）,（,（,）,（,）,证明：（）左边,（,）,（,（,）,（,）,（,）,（,）,（,）,（,）,4,等价式,（）左边,（,）,（,）,（,）,（,）,（,）,结论：（）和（）是互为对偶的。,7,范式和判定,例：证明,（,）,证明方法是写出二个命题公式的主析范式，看其是否相同：,（,）,（,）,（,）,（,）,（,）,而,（,（,）,（,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,主析范式相同，,有,（,）,8,推理理论,例,1,：,P,(Q S),R,P,Q,R,S,证,:(1)R,附加前提,(2),R,P P,(3),R,P T(2)E,(4)P T(1)(3)I,(5)P,(Q S)P,(6),Q S T(4)(5)I,8,推理理论,(7)Q P,(8)S T(6)(7)I,(9),R,S CP,例,2:PQ,P,(P,Q),(1)P,附加前提,(2),PQ P,(3)Q T(1)(2)I,(4)P,Q T(1)(3),(5)P,(P,Q)CP,8,推理理论,例：证明,P,Q,(P,Q),证,:(1),(,(P,Q),假设前提,(2),P,Q T(1),(3)P T(2),(4),P,Q P,(5),P T(4),(6)P,P T(3)(5),(7)F,8,推理理论,例,2:,证明,:,RQ,R,S,SQ,PQ,P,(1)(P),假设前提,(2)P T(1),(3)PQ P,(4)Q T(2)(3),(5)SQP,(6)QS T(5),(7)S T(4)(6),(8)R,S P,(9)RT(7)(8),8,推理理论,(10),RQP,(11)QT(9)(10),(12)Q,QT(4)(11),讨论：,由上例可见，间接证明法在结论较为简单的条件下，使用是比较方便的，实际上间接证明法也可以用,CP,规则代替它。,8,推理理论,例：一位计算机工作者协助公安人员审查一起谋杀案，经调查，他认为下列情况均是真的。,（,1,）会计张某或邻居王某谋害了厂长。,（,2,）如果会计张某谋害了厂长，则谋害不可能发生在半夜。,（,3,）如果邻居王某的证词不正确，则在半夜时房里灯光未灭。,（,4,）如果邻居王某的证词是正确的，则谋害发生在半夜。（,5,）在半夜房子里的灯光灭了，且会计张某曾贪污过。,8,推理理论,解：设,P,：,会计张某谋害了厂长,Q,：,邻居王某谋害了厂长,N,：,谋害发生在半夜,O,：,邻居王某的证词是正确的,R,：,半夜时房子的灯光灭了,A,：,会计张某曾贪污过,列出条件公式：,8,推理理论,(1),P,Q,(4)QN,(2),PN (5)RA,(3)O R,推导过程为：,(1)RA P (6)N T,(2)R T (7)PN P,(3)O R P (8)P,T,(4)O T (9),P,Q P,(5),O R P (10)Q T,结论：邻居王某谋害了厂长；,例题选讲,例,1.,符号化下列命题：,（,1,）辱骂和恐吓决不是战斗；,（,2,）除非天气好，否则我是不会去公园的；,（,3,）如果晚上做完作业且没有其它的事，他就会去看电视或听音乐。,解,：（,1,）设,P,：,辱骂不是战斗。,Q,：,恐吓不是战斗。,P,Q,（,2,）设,P,：,今天天气好。,Q,：,我去公园。,Q,P,例题选讲,（,3,）设,P,：,他晚上做完了作业。,Q,：,他晚上没有其它事情。,R,：,他看电视。,S,：,他听音乐。,（,P,Q,）（,RS,）,例,2.,证明,P,（,Q R,）（,P Q,）（,P R,）,给出本题的各种证明：,（,1,）列真值表：设,M P,（,Q R,）,K,（,P Q,）（,P R,）,S P,（,Q R,）（,P Q,）（,P R,）,例题选讲,P Q R,Q,R,M,P,Q,P,R,K,S,T T T,T,T,T,T,T,T,T T F,F,F,T,F,F,T,T F T,T,T,F,T,T,T,T F F,T,T,F,F,T,T,F T T,T,T,T,T,T,T,F T F,F,T,T,T,T,T,F F T,T,T,T,T,T,T,F F F,T,T,T,T,T,T,例题选讲,a),直接证法：,P,（,Q R,）,的真值,为,T,，,其对应指派下,（,P Q,）（,P R,）,的真值均为,T,。,b),反证法：（,P Q,）（,P R,）,的真值为,F,，,其对应指派,下,P,（,Q R,）,的真值为,F,。,c),条件永真式：,（,P,（,Q R,）（,P Q,）（,P R,）,的真值都为,T,，,及为永真式。,（,2,）逻辑推证,a),直接证法：设,P,（,Q R,）为,T,，,则,P,为,T,，,Q R,为,T,，,有三种情况：,P,为,T,，,Q,为,T,，,R,为,T,，,则（,P Q,）（,P R,）为,T,。,例题选讲,P,为,T,，,Q,为,F,，,R,为,T,，,则（,P Q,）（,P R,）为,T,。,P,为,T,，,Q,为,F,，,R,为,F,，,则（,P Q,）（,P R,）为,T,。,P,为,F,，,Q R,为,F,，,则：,P,为,F,，,Q,为,T,，,R,为,F,，,所以,P Q,为,T,，,P R,为,T,，,得（,P Q,）（,P R,）为,T,。,P,为,F,，,Q R,为,T,，,则：,P,为,F,，,Q,为,T,，,R,为,T,，,则（,P Q,）（,P R,）为,T,。,P,为,F,，,Q,为,F,，,R,为,F,，,则（,P Q,）（,P R,）为,T,。,P,为,F,，,Q,为,F,，,R,为,T,，,则（,P Q,）（,P R,）为,T,。,综上各点：当,P,（,Q R,）为,T,时，必有（,P Q,）（,P R,）为,T,。,例题选讲,b),间接证法：,设,（,P Q,）（,P R,）为,F,，,则,必有,P Q,为,T,，,P R,为,F,，,故得,P,为,T,，,Q,为,T,，,R,为,F,。,所以,P,（,Q R,）为,F,。,（,3,）,等价变换,S(P (Q R)(P Q)(P R),(P(Q R)(P Q)(P R),(PQ R)(P Q)(P R),(PQ R)(P Q)(P R),(PQ R)(P R P)(Q P R),(PQ R)(P Q R),(PQ R)(PQ R)T,例题选讲,例,3.,证明,，,不是最小联结词组。,证明：设变元,P,，,Q,，,用联结词,，作用于,P,，,Q,得到：,P,，,Q,，,P,，,Q,，,PQ,，,PP,，,QQ,，,QP,。,但,(PQ)(QP),，,(PP)(QQ),，,故实际有：,P,，,Q,，,P,，,Q,，,PQ,，,PP(T)(A),用作用于,(A),类,得到扩大的公式类,(,包括原公式类,):,P,，,Q,，,P,，,Q,，,PQ,，,(PQ),，,T,，,F (B),用作用于,(A),类得到：,PQ,，,P P(F),，,P Q(PQ),，,P(PQ)Q,，,P(PP)P,Q P (PQ),，,Q Q(F),，,Q (PQ)P,QT Q,，,例题选讲,P Q(PQ),，,P(PQ)Q,，,PT P,，,Q(PQ)P,，,QT Q,，,(PQ)(PP)PQ,。,因此,(A),类使用运算后，仍在,(B),类中。,同样，对,(B),类使用，运算后，结果仍在,(B),中。,由上证明：用，两个联结词，反复作用在两个变元的公式中，结果只能产生,(B),类中的公式，总共仅八个不同公式，而两个变元所形成的公式共有,2,2,2,=16,个彼此不等价的公式，因此,，,不是功能完备的，更不可能是最小联结词组。,例题选讲,例,4.,求,(A,B,C),(,A,(,B,C),的主析取范式与主合取范式。,解,：,(1),列表法：,设,S,(A,B,C),(,A,(,B,C),，,R,A,B,C,，,M,A,(,B,C),，,根据真值表中,S,真值为,T,的指派，所对应的小项析取即为,S,的主析取范式，,S,真值为,F,的指派，所对应的大项合取即为主合取范式。,S,的真值表如下：,例题选讲,A B C,B,C,R,A,B,C,M,S,T T T,T,T,F,F,T,T,T T F,F,F,F,F,T,F,T F T,F,F,F,F,T,F,T F F,F,F,F,T,F,F,F T T,T,T,T,F,F,F,F T F,F,T,T,F,F,F,F F T,F,T,T,F,F,F,F F F,F,T,T,T,T,T,例题选讲,S,(AB C)(A B C),主析取范式,S,(A B C)(A B C)(A B C),(A B C)(A B C)(A B C),主合取范式,(2),公式推导法：,S,(A,B,C),(,A,(,B,C),(,A,(B,C),(,A,(,B,C),(,(,B,C),A),(,A,(B,C),(A,(,B,C),(,