离散数学 习题 参考答案第一章 命题逻辑习题一1、构造公式(p∧q)∨ (¬p∧¬q)、p↔q 的真值表 2、构造公式¬(p∨q)与¬p∧¬q 的真值表 3、构造公式 p、p∧p、p∨p 的真值表 4、构造公式 p∨(q∧r)、(p∨q)∧(p∨r)的真值表 5、构造公式 p∨(p∧r)、p 的真值表 6、构造公式 p∧(p∨r)、p 的真值表 7、构造公式 p↔q、¬q↔¬p 的真值表 8、构造公式(p→q)∧(p→¬q)、¬p 的真值表 9、构造公式 p、¬¬p 的真值表 10、构造公式 p∨¬p、p∧¬p 的真值表略习题二一、分别用等算演算与真值表法，判断下列公式是否存在主析取范式或主合取范式，若有，请写出来1)(¬p→q)→(¬q∨p) (2)(¬p→q)→(q∧r) (3)(p∨(q∧r))→(p∨q∨r) (4) ¬(q→¬p)∧¬p (5)(p∧q)∨(¬p∨r) (6)(p→(p∨q))∨r (7)(p∧q)∨r (8) (p→q)∧(q→r) (9) (p∧q)→q (10) ¬(r↔p)∧p∧q解：(1)pq ¬p (¬p→q)¬q(¬q∨p)(¬p→q)→(¬q∨p)00 1 0 1 1 1 01 1 1 0 0 0 10 0 1 1 1 1 11 0 1 0 1 1 存在主析取范式=成真赋值对应的小项的析取=m00∨m10∨m11=(¬p∧¬q)∨(p∧¬q)∨(p∧q) 主析取范式=成假赋值对应的大项的合取=M01=p∨¬q 等值演算： (¬p→q)→(¬q∨p) ⇔¬ (¬¬p∨q)∨(p∨¬q) ⇔¬ (p∨q)∨(p∨¬q) ⇔ (¬p∧¬q)∨(p∨¬q) ⇔ (¬p∨(p∨¬q))∧(¬q∨(p∨¬q)) ⇔ (¬p∨p∨¬q)∧(¬q∨p∨¬q) ⇔ (1∨¬q)∧(p∨¬q) ⇔ (p∨¬q) 这是大项，故为大项的合取，称为主合取范式 (¬p→q)→(¬q∨p) ⇔ (p∨¬q) ⇔ (p)∨(¬q) ⇔ (p∧1)∨( 1∧¬q) ⇔ (p∧(q∨¬q))∨( (p∨¬p)∧¬q) ⇔ (p∧q)∨ (p∧¬q)∨(p∧¬q)∨(¬p∧¬q)⇔ (p∧q)∨ (p∧¬q)∨(¬p∧¬q) 因为一个公式的值不是真，就是假，因此当我们得到一个公的取值为真的情况时，剩下的组合是取值为假， 因此当得到小项的析取组成的主析取范式后，可以针对剩下的组合写出主合取范式。
如当我们得到(¬p→q)→(¬q∨p)的大项之合取(p∨¬q)后，使(p∨¬q)为假时(p,q)的值为(0,1)，故其标记为M01，剩余的取值为(0,0),(1,0),(1,1)，故小项之析取为m00∨m10∨m11反之，若先得到其小项的析取，也可得到其大项的合取反正这两者将其所有组合瓜分完毕2)(¬p→q)→(q∧r)pqr¬p¬p→q(q∧r)结果00010010011001010110001111111000100101010011001001110111主析取范式=m000∨m001∨m011∨m111=(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧q∧r) 主合取范式=M010∧M100∧M101∧M110=(p∨¬q∨r)∧(¬p∨q∨r)∧(¬p∨q∨¬r)∧(¬p∨¬q∨r)(3)(p∨(q∧r))→(p∨q∨r)pqr(q∧r)(p∨(q∧r))(p∨q∨r)(p∨(q∧r))→(p∨q∨r)00000010010001010001101100111000111101011111011111111111永真式，所有小项的析取得到其主析取范式=(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(¬p∧q∧r)∨(p∧¬q∧¬r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r) 由于没为假的指派，所以没有为假赋值，所对应的大项合取构成的合取，即没有主合取范式。
¬(p∨(q∧r))∨(p∨q∨r)=(¬p∧¬(q∧r))∨(p∨q∨r)=((¬p∧¬q)∨ (¬p∧¬r))∨(p∨q∨r) = (¬p∧¬q)∨ (¬p∧¬r)∨p∨q∨r=¬(p∨q)∨(¬p∧¬r)∨p∨q∨r=1永真(4) ¬(q→¬p)∧¬ppq¬p(q→¬p)¬(q→¬p)结果0011000 1 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 没有成真的赋值，从而没有对应的小项，因此没有小项构成的主析取范式永假式即矛盾式，为假指派对应的大项合取=(p∨q)∧(p∨¬q)∧(¬p∨q)∧(¬p∨¬q) 原式=¬(¬q∨¬p)∧¬p=(q∧p) ∧¬p=0 (5) (p∧q)∨(¬p∨r)pqr(p∧q)¬p(¬p∨r)(p∧q)∨(¬p∨r)00001110010111010011101101111000000101001111010011111011主析取范式(¬p∧¬q∧¬r)∨( ¬p∧¬q∧r)∨( ¬p∧q∧¬r)∨( ¬p∧q∧r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r) 主合取范式M100=¬p∨q∨r 原式=((p∧q)∨¬p)∨r=((p∨¬p)∧(¬p∨q))∨r=(1∧(¬p∨q))∨r=¬p∨q∨r 这就是大项也剩下的赋值对应的就是小项 (6)(p→(p∨q))∨rpqr(p∨q)(p→(p∨q))(p→(p∨q))∨r000011001011010111011111100111101111110111111111永真式，只有小项组成的主析取范式。
没有为假的赋值，所以没有成假赋值对应的大项的合取，即没有主合取范式 原式=(¬p∨ (p∨q))∨r=(1∨q)∨r=1 (7)(p∧q)∨rpqr(p∧q)(p∧q)∨r0000000101010000 110 1 1 000 0 1 010 1 1 101 1 1 111 1 主析取范式=m001∨m011∨m101∨m110∨m111= (¬p∧¬q∧r)∨( ¬p∧q∧r)∨( p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r) 主合取范式=M000∧M010∧M100=(p∨q∨r)∧ (p∨¬q∨r)∧ (¬p∨q∨r) (p∧q)∨r =(p∧q∧1)∨(1∧1∧r) =(p∧q∧(¬r∨r))∨( (¬p∨p)∧ (¬q∨q)∧r) =(p∧q∧¬r)∨ (p∧q∧r)∨ (¬p∧¬q∧r)∨( ¬p∧q∧r) ∨ (p∧¬q∧r) (p∧q)∨r =(p∨r) ∧(q∨r) =(p∨0∨r) ∧(0∨q∨r) =(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)(8) (p→q)∧(q→r)pqr(p→q)(q→r)(p→q)∧(q→r)000111001111010100011111100010101010110100111111主析取范式=m000∨m001∨m011∨m111=(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧q∧r) 主合取范式=M010∧M100∧M101∧M110= =(p∨¬q∨r)∧(¬p∨q∨r)∧(¬p∨q∨¬r)∧(¬p∨¬q∨r) (p→q)∧(q→r)=(¬p∨q)∧(¬q∨r) =(¬p∨q∨0)∧(0∨¬q∨r) =(¬p∨q∨(¬r∧r))∧( (¬p∧p)∨¬q∨r) =(¬p∨q∨¬r)∧ (¬p∨q∨r) ∧(¬p∨¬q∨r)∧( p∨¬q∨r) (p→q)∧(q→r)=(¬p∨q)∧(¬q∨r)=(¬p∧¬q)∨ (¬p∧r)∨ (q∧¬q)∨ (q∧r) =(¬p∧¬q∧1)∨ (¬p∧1∧r)∨(1∧q∧r) =(¬p∧¬q∧(¬r∨r))∨ (¬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)∨ (¬p∧¬q∧r)∨ (¬p∧q∧r)∨( p∧q∧r) (9) (p∧q)→qpq(p∧q)(p∧q)→q0001010110011111永真式，只有小项的析取构成的主析取范式=(¬p∧¬q)∨( ¬p∧q)∨(p∧¬q)∨(p∧q) 没有为假的指派，所以没有由大项的合取构成的主合取范式(p∧q)→q =¬(p∧q)∨q =(¬p∨¬q)∨q =¬p∨¬q∨q =1 (10) ¬(r↔p)∧p∧qpqrr↔p¬(r↔p)¬(r↔p)∧p∧q000100001010010100011010100010101100110011111100主析取范式=m110=p∧q∧¬r 主合取范式=M000∧ M001∧ M010∧ M011∧ M100∧ M101∧ M111 = (p∨q∨r)∧(p∨q∨¬r)∧(p∨¬q∨r)∧(p∨¬q∨¬r)∧( ¬p∨q∨r)∧( ¬p∨q∨¬r)∧( ¬p∨¬q∨¬r) ¬(r↔p)∧p∧q =¬((¬p∨r)∧ (p∨¬r))∧p∧q =((p∧¬r) ∨ (¬p∧r))∧p∧q =(p∧¬r∧p∧q) ∨(¬p∧r∧p∧q) =(p∧q ∧¬r) ¬(r↔p)∧p∧q=¬((p∧r)∨ (¬p∧¬r))∧p∧q = ((¬p∨¬r)∧(p∨r))∧p∧q = (¬p∨¬r)∧(p∨r)∧p∧q = (¬p∨¬r)∧((p∨r)∧p)∧q = (¬p∨¬r)∧p∧q = (¬p∨(¬q∧q)∨¬r)∧(p∨(¬q∧q)∨ (¬r∧r))∧( (¬p∧p)∨q∨(¬r∧r)) =(¬p∨¬q∨¬r)∧ (¬p∨q∨¬r)∧ (p∨¬q∨¬r)∧(p∨¬q∨r)∧(p∨q∨¬r)∧ (p∨q∨r) ∧ ∧( ¬p∨q∨¬r) ∧( ¬p∨q∨ r) ∧( p∨q∨¬r) ∧( p∨q∨r)= (p∨q∨r) ∧(p∨q∨¬r)∧ (p∨¬q∨r)∧ (p∨¬q∨¬r)∧ ( ¬p∨q∨ r) ∧(¬p∨q∨¬r)∧ (¬p∨¬q∨¬r) =M000 ∧M001∧M010∧M011∧ M100 ∧M101∧M111二、应用题 1、某次课间休息时，1位同学作为主持人与另外3位同学进行猜数游戏，主持人说这个数是30、50、70中的某一个，你们三位同学各猜一次，然后主持人分析每人猜数的结果，从而最终确定是哪个数。
同学1说：这个数是30，不是50 同学2说：这个数是50，不是70 同学3说：这个数既不是30，也不是50 主持人听后说道：你们3人中，有一人全对，有二人对了一半，请问到底是哪个数解：令S表示“这个数是30”，W表示“这个数是50”，Q表示“这个数是70” 同学1的话：S∧¬W 同学2的话：W∧¬Q 同学3的话：¬S∧¬W 对于每个人来说，只有二个选择：全对、对一半，对一半又分成：第一句对第二句错、第一句错第二句对，因此每个同学的对错情况为：√√、√×、×√，因此3个人共有3*3*3=27种可能的情况，其中有些情况不符合“有一人全对，有二人对了一半”而剔除我们按“√√、√×、×√”顺序，构造“类真值表”来分析其组合情况同学1同学2同学3命题公式分析√√√√√√不必写不可能全对√√√√√×不必写不可能有2个对√√√√√×不必写不可能有2个对√√√×√√不必写不可能有2个对√√√×√×S∧¬W∧W∧Q∧¬S∧W=0真值为0不对√√√×√×S∧¬W∧W∧Q∧S∧¬W=0真值为0不对√√√×√√不必写不可能有2个对√√√×√×S∧¬W∧¬W∧Q∧¬S∧W=0真值为0不对√√√×√×S∧¬W∧¬W∧¬Q∧S∧¬W= S∧¬W∧¬Q可能对的，是30不是50，不是70√×√√√×S∧W∧ W∧¬Q∧¬S∧ W=0不可能√×√√√×S∧W∧ W∧¬Q∧S∧ ¬W=0不可能√×√×√√S∧W∧ W∧Q∧¬S∧¬W=0不可能√×√×√√S∧W∧ ¬W∧¬Q∧¬S∧¬W=0不可能√×√√√×× S, ¬W,W, ¬Q,S,W=0不可能×√√√×√¬S, ¬W,W, ¬Q,S, ¬W=0不可能×√√×√√¬S, ¬W,W,Q, ¬S, ¬W=0不可能×√×√√√¬S，¬W，¬W，¬Q，¬S，¬W=3个数都不是，不可能答案是：是30，不是50，不是70 同学1说：这个数是30，不是50 全对同学2说：这个数是50，不是70 第一句错第二句对同学3说：这个数既不是30，也不是50 第一句错第二句对2、设计一个如下的电路图：它有三个输入p1、p2、p3，当其中有2个及以上的值为1时输出的结果为1，其他情况下输出0。
请给出其真值表，同时针对此真值表给出主析取范式、主合取范式，并给出其最简单的表达式答：与课堂例题一样 在真实的教材将其换成了如下习题2、设计一个如下的电路图：它有三个输入p1、p2、p3，当其中任意二个的值为0时输出的结果为1，其他情况下输出0请给出其真值表，同时针对此真值表给出主析取范式、主合取范式，并给出其最简单的表达式p1p2p3表达式的值00010011010101101001101011001110其主析取范式=m000∨m001∨m010∨m100 =(¬p1∧¬p2∧¬p3)∨(¬p1∧¬p2∧p3)∨(¬p1∧p2∧¬p3)∨(p1∧¬p2∧¬p3) =((¬p1∧¬p2)∧(¬p3∨∧p3))∨(( (¬p1∧p2)∨ (p1∧¬p2))∧¬p3) =(¬p1∧¬p2) ∨(((¬p1∧p2)∨ (p1∧¬p2))∧¬p3) 其主合取范式=M011∧M101∧M110∧M111=(p1∨¬p2∨¬p3)∧(¬p∨p2∨¬p3)∧(¬p1∨¬p2∨p3)∧(¬pq∨¬p2∨¬p3) =(((p1∨¬p2)∧(¬p1∨p2))∨¬p3)∧ (¬p1∨¬p2) 3、某年级要从1班、2班、3班、4班、5班中选出一名才子主持元旦晚会，每班最多一人，也可能没有，这些人满足如下条件，请确定最终选择哪些班级的学生： (1)如果1班有人选中，则2班有人选中。
2)若5班有人选上则1班与2班均有人选上3)5班与4班必有一班有被选中4)3班与4班同时有人选上或同时没人选上解：用One表示1班选了人，Two表示2班选了人，Three表示3班选了人，Four表示4班选了人，Five表示5班选了人则这4个条件依次为One→Two，Five→(One∧Two)，Four∨Five，Three↔Four 满足这4个条件，即这4个条件的值均为真即为1，所以其合取为1 (One→Two) ∧(Five→(One∧Two)) ∧(Four∨Five) ∧(Three↔Four)=1， 将以上合取范式转换为主析取范式，因此双条件应转换为析取式的合取式 原式= (¬One∨Two) ∧(¬Five∨(One∧Two)) ∧(Four∨Five) ∧((¬Three∨Four)∧ (Three∨¬Four)) =[(¬One∨Two) ∧(¬Five∨(One∧Two))] ∧(Four∨Five) ∧(¬Three∨Four)∧ (Three∨¬Four) =[(¬One∧¬Five)∨(¬One∧(One∧Two)∨(Two∧¬Five)∨(Two∧(One∧Two)]∧(Four∨Five) ∧(¬Three∨Four)∧ (Three∨¬Four) ={[(¬One∧¬Five)∨(Two∧¬Five)∨(Two∧One)]∧(Four∨Five)} ∧(¬Three∨Four)∧ (Three∨¬Four) ={[(¬One∧¬Five∧Four) ∨( Two∧¬Five∧Four) ∨(Two∧One∧Four) ∨(Two∧One∧Five)] ∧(¬Three∨Four)}∧ (Three∨¬Four) ={(¬One∧¬Five∧Four∧¬Three) ∨ (¬One∧¬Five∧Four) ∨ (Two∧¬Five∧Four ∧¬Three) ∨ (Two∧¬Five∧Four) ∨ (Two∧One∧Four ∧¬Three) ∨ (Two∧One∧Four) ∨ (Two∧One∧Five ∧¬Three) ∨ (Two∧One∧Five ∧Four)} ∧ (Three∨¬Four) =(¬One∧¬Five∧Four∧ Three) ∨ ( Two∧¬Five∧Four ∧ Three) ∨ (Two∧One∧Four∧ Three) ∨ (Two∧One∧Five ∧¬Three ∧ ¬Four) ∨ (Two∧One∧Five ∧Four ∧ Three) = (¬One∧ Three ∧Four ∧¬Five) ∨ ( Two ∧ Three ∧Four ∧¬Five) ∨ (One∧Two∧ Three ∧ Four) ∨ (One∧Two∧¬Three∧ ¬Four∧ Five) ∨ (One∧Two∧ Three ∧Four ∧ Five)一班二班三班四班五班条件1条件2条件3条件4方案一无不限有有无满足满足满足满足方案二不限有有有无满足满足满足满足方案三有有有有不限满足满足满足满足方案四有有无无有满足满足满足满足方案五有有有有有满足满足满足满足(1)如果1班有人选中，则2班有人选中。
2)若5班有人选上则1班与2班均有人选上3)5班与4班必有一班有被选中4)3班与4班同时有人选上或同时没人选上按照某位帅哥的质疑，经仔细思考，应该将其转换为主析取范式，所以最终结果为：= (¬One∧1∧ Three ∧Four ∧¬Five) ∨ (1∧ Two ∧ Three ∧Four ∧¬Five) ∨ (One∧Two∧ Three ∧ Four∧1) ∨ (One∧Two∧¬Three∧ ¬Four∧ Five) ∨ (One∧Two∧ Three ∧Four ∧ Five) = (¬One∧¬Two∧ Three ∧Four ∧¬Five) ∨(¬One∧Two∧ Three ∧Four ∧¬Five) ∨ (¬One ∧ Two ∧ Three ∧Four ∧¬Five) ∨(One∧ Two ∧ Three ∧Four ∧¬Five) ∨ (One∧Two∧ Three ∧ Four∧¬Five) ∨(One∧Two∧ Three ∧ Four∧Five) ∨ (One∧Two∧¬Three∧ ¬Four∧ Five) ∨(One∧Two∧ Three ∧Four ∧ Five)=(¬One∧¬Two∧ Three ∧Four ∧¬Five) ∨(¬One∧Two∧ Three ∧Four ∧¬Five) ∨ (One∧ Two ∧ Three ∧Four ∧¬Five) ∨(One∧Two∧ Three ∧ Four∧Five) ∨ (One∧Two∧¬Three∧ ¬Four∧ Five)一班二班三班四班五班条件1条件2条件3条件4方案一无无有有无满足满足满足满足方案二无有有有无满足满足满足满足方案三有有有有无满足满足满足满足方案四有有有有有满足满足满足满足方案五有有无无有满足满足满足满足(1)如果1班有人选中，则2班有人选中。
2)若5班有人选上则1班与2班均有人选上3)5班与4班必有一班有被选中4)3班与4班同时有人选上或同时没人选上4、某公司要从A、B、C、D、E选派一些人去参观世博会，必须满足如下条件： (1)若A去则B肯定不能去； (2)若A与C只能去一个； (3)C与D两人同去或同不去； (4)若B去则C肯定去(5)若E去则B，C，D肯定有一人陪同证明：是否存在满足以上条件的人选？若存在则请给出全部方案 解：这句知表示为： (A→¬B) ∧((A∧¬C)∨(¬A∧C)) ∧(C↔D) ∧ (B→C) ∧(E→(B∨C∨D)) 满足5个条件，则每个条件的值为真，故其合取为真，将其转换为主析取范式，则可以判断是否有可能的方案A→¬B) ∧((A∧¬C)∨(¬A∧C)) ∧(C↔D) ∧ (B→C) ∧(E→(B∨C∨D)) ={(¬A∨¬B)∧((A∧¬C)∨(¬A∧C))}∧((C∧D)∨(¬C∧¬D))∧(¬E∨ B∨C∨D) ={[(¬A∧C) ∨ (A∧¬C∧¬B) ∨(¬A∧C∧¬B)]∧((C∧D)∨(¬C∧¬D))}∧(¬E∨ B∨C∨D) ={(¬A∧C∧D) ∨ (A∧¬B ∧¬C ∧¬D) ∨(¬A∧¬B ∧C ∧D)}∧ (¬E∨B∨C∨D) =(¬A∧C∧D∧¬E) ∨(¬A∧C∧D∧B) ∨(¬A∧C∧D) ∨ (A∧¬B ∧¬C ∧¬D∧¬E) ∨ (¬A∧¬B ∧C ∧D∧¬E) ∨(¬A∧¬B ∧C ∧D)=(A∧¬B ∧¬C ∧¬D∧¬E) ∨(¬A∧¬B ∧C ∧D∧¬E) ∨(¬A∧¬B ∧C ∧D) ∨ (¬A∧B ∧C∧D) ∨(¬A∧C∧D∧¬E) ∨(¬A∧C∧D) =(A∧¬B ∧¬C ∧¬D∧¬E) ∨ (¬A∧¬B ∧C ∧D∧¬E) ∨ ∨(¬A∧¬B ∧C ∧D∧¬E) ∨ (¬A∧¬B ∧C ∧D∧E) ∨ (¬A∧B ∧C∧D∧¬E) ∨ (¬A∧B ∧C∧D∧¬E)∨ (¬A∧¬B ∧C∧D∧¬E) ∨ (¬A∧B ∧C∧D∧¬E) ∨ (¬A∧¬B ∧C∧D∧¬E) ∨ (¬A∧¬B ∧C∧D∧E) ∨ (¬A∧B ∧C∧D∧¬E) ∨ (¬A∧B ∧C∧D∧E)=(A∧¬B∧¬C∧¬D∧¬E) ∨ (¬A∧¬B ∧C ∧D∧¬E) ∨ (¬A∧¬B ∧C ∧D∧E) ∨ (¬A∧B ∧C∧D∧¬E) ∨ (¬A∧B ∧C∧D∧E)条件1条件2条件3条件4条件5(A∧¬B ∧¬C ∧¬D∧¬E)A去B不C不D不E不满足满足满足满足满足(¬A∧¬B ∧C ∧D∧¬E)A不B不C去D去E不满足满足满足满足满足(¬A∧¬B ∧C ∧D∧E)A不B不C去D去E去满足满足满足满足满足(¬A∧B ∧C∧D∧¬E)A不B去C去D去E不去满足满足满足满足满足(¬A∧B ∧C∧D∧E)A不B去C去D去E去满足满足满足满足满足习题三 1、利用定义1.6.1，并利用等值演算或真值表，证明如下各推理式，要注明每步的理由。
1、(A→B)∧ ¬B⇒¬A (1) ¬B为真 前提条件(2) A→B为真 前提条件(3) ¬B→¬A为真因为¬B→¬A⇔A→B为真(4) ¬A为真 (¬B→¬A)∧ ¬B⇒¬A假言推理2、 (A∨B)∧ ¬B⇒A (1) ¬B为真 前提条件(2) (A∨B)为真前提条件 (3) ¬B→A为真因为¬B→A⇔ A∨B为真(4)A为真 (¬B→A)∧ ¬B⇒A假言推理3、 (A↔B)∧(B↔C)⇒ (A↔C) (1) (A↔B)为真 前提条件(2)(A→B)∧(B→A)为真因(A↔B) ⇔(A→B)∧(B→A) (3) (A→B)为真 由(2)及合取的定义(4) (B→A)为真 由(2)及合取的定义(5) (B↔C)为真 前提条件(6)(B→C)∧(C→B)为真因(B↔C) ⇔(B→C)∧(C→B) (7) (B→C)为真 由(6)及合取的定义(8) (C→B)为真 由(6)及合取的定义(9) (C→A)为真 由(8)(4)及传递律(10) (A→C)为真 由(3)(7)及传递律(11) (A↔C)为真 由(9)(10)及双条件的定义(4) (A→B)∧( ¬A→B)⇒B ((A→B)∧( ¬A→B))→B ⇔¬((¬A∨B) ∧( ¬¬A∨B )) ∨B ⇔¬((¬A∨B) ∧(A∨B )) ∨B ⇔((A∧¬B) ∨ (¬A∧¬B )) ∨B ⇔((A ∨ ¬A ) ∧¬B)) ∨B ⇔(1 ∧¬B)) ∨B ⇔¬B∨B ⇔1 故为永真式(A→B)∧( ¬A→B)⇒B 2、采用定义1.6.2方法证明如下推理式，并注明每步理由，可采用CP规则、反证法。
1、¬p∨q，¬q∨r，r→s，p⇒s (1) p (2) ¬p∨q (3) q (1)(2) ∨的定义，或(1)(2)分离原则(4) ¬q∨r (5) r (4)(5) ∨的定义，或(4)(5)分离原则(6) r→s (7) s (5)(6)分离原则2、 p→(q→r)，q→(r→s) ⇒ (p∧q) →s (1) (p∧q) 附加条件(2) p (1)与∧的定义附加条件(3) q (2)与∧的定义附加条件(4) p→(q→r) (5) q→r (2)与(4)分离原则(6) r (3)与(5)分离原则(7) q→(r→s) (8) r→s (3)与(7)分离原则(9) s (6)与(8)分离原则3、p→(q→r)，p，q⇒ r∨s (1) p为真前提条件 (2) p→(q→r)为真前提条件 (3) (q→r)为真 (1)(2)假言推理(4)q为真 前提条件(5)r为真 (4)(3)假言推理(6)r∨s为真 (5)与析取的定义4、p→q，¬(p∧r) ，r⇒¬p (1) ¬(p∧r)为真前提条件 (2) ¬p∨¬r为真 (1)与德摩律(3)r→¬p为真 与(2)等值(4) r为真前提条件 (5) ¬p为真 (4)(3)假言推理反证法 (1) ¬¬p为真反证法即假设结论为真 (2)p为真 否定的否定为真(3)¬(p∧r)为真前提条件 (4)¬p∨¬r为真 (3)与德摩律(5) p→¬r为真与(4)等值(6) ¬r为真 (2)(5)假言推理(7)r为真 前提条件显然(6)(7)矛盾，故假设错了，即“¬¬p为真”错了，所以¬p为真5、p→q⇒ p→(p∧q) (1)p为真 附加前提(2) p→q为真前提条件 (3)q为真 (1)(2)假言推理(4) (p∧q)为真 (1)(3)及合取的性质6、q→p，q↔s，s↔t，t↔r,r⇒p∧q (1) t↔r为真 前提条件(2) (t→r) ∧(r→t)为真与(1)等值(3) (r→t)为真 (2)及合取的定义(4)r为真 前提条件(5)t为真 (3)(4)假言推理(6) s↔t为真 前提条件(7) (s→t) ∧(t→s)为真与(6)等值(8) (t→s)为真 (7)及合取的定义(9)s为真 (5)(8)与假言推理(10) q↔s为真 前提条件(11) (q→s) ∧(s→q)为真与(10)等值(12) (s→q)为真 (11)与合取的定义(13)q为真 (9)(12)与假言推理(14) q→p为真 前提条件(15)p为真 (13)(14)假言推理(16)p∧q为真 (13)(15)及合取的定义7、p→r， q→s ，p∧q ⇒r∧s (1) p∧q为真 前提条件(2)p为真 (1)与合取的性质(3)q为真 (1)与合取的性制(4) p→r为真 前提条件(5)r为真 (2)(4)假言推理(6) q→s为真 前提条件(7)s为真 (3)(6)及假言推理(8) r∧s为真 (5)(7)及合取的性质8、¬p∨r，¬q∨s，p∧q⇒t→ r∧s (1)t为真 附件前提(2) p∧q为真前提条件 (3)p为真 (2)与合取的定义(4)q为真 (2)与合取的定义(5) ¬p∨r为真前提条件 (6)p→r为真与(5)等值(7)r为真 (6)(3)与假言推理(8) ¬q∨s为真前提条件 (9) q→s为真与(8)等值(10)s为真 (9)(4)与假言推理(11) r∧s为真 (7)(10)与合取的性质9、p→ (q→r)，s→p，q⇒ s→r (1)s为真 附加前提(2) s→p为真前提条件 (3)p为真 (1)(2)假言推理(4) p→ (q→r)为真前提条件 (5) (q→r)为真 (3)(4)假言推理(6)q为真 前提条件(7)r为真 (5)(6)假言推理10、(p∨q) → (r∧s)，(s∨t) →u⇒p→u (1)p为真 附加前提(2)p∨q为真 (1)及析取的性质(3) (p∨q) → (r∧s)为真前提条件 (4) (r∧s)为真 (2)(3)与假言推理(5)s为真 (4)与合取的定义(6) (s∨t)为真 (5)与析取的定义(7) (s∨t) →u为真前提条件 (8)u为真 (6)(7)假言推理11、p→¬q，¬r∨q，r∧¬s ⇒¬p 反证法(1) ¬¬p为真 结论的否定(2)p为真 (1)的否定之否定(3) p→¬q为真前提条件 (4) ¬q为真 (2)(3)假言推理(5) ¬r∨q为真 前提条件(6) ¬q→¬r为真与(5)等值(7) ¬r为真 (4)(6)假言推理(8) r∧¬s为真 前提条件(9) r为真 (8)及合取的定义故(7)(9)矛盾，从而假设“¬¬p为真”是错的，只能“¬¬p为假”，所以¬p为真12、p∨q，p→r，q→s⇒ r∨s 结论为r∨s⇔¬r→s，所以上式等价于证明p∨q，p→r，q→s⇒¬r→s (1) ¬r为真附加条件 (2) p→r为真前提条件 (3) ¬r→¬p为真与(2)等值(4) ¬p为真 (1)(3)假言推理(5) p∨q为真前提条件 (6) ¬p→q为真与(5)等值(7)q为真 (4)(6)与假言推理(8) q→s为真前提条件(9)s为真 (7)(8)与假言推理3、将下面各段话用命题逻辑公式表示，并构造其自然逻辑的证明过程。
1)只要A曾到过受害者的房间，并且11点以前没有离开，A就是谋杀嫌犯A曾到过受害者房间如果A在11点前离开，看门人会看见他看门人没看见他所以A是谋杀嫌犯解：P1表示“A曾到过受害者的房间” P2表示“A人11点以前离开” P3表示“A是谋杀嫌犯” P4表示“看门人看见A” 则以上语句表示：(P1∧¬P2)→P3，P1，P2→P4，¬P4⇒P3 (1) ¬P4为真 前提条件(2) P2→P4为真 前提条件(3) ¬P4→¬P2为真与(2)等值(4) ¬P2为真 (1)(3)进行假言推理(5)P1为真 前提条件(6) (P1∧¬P2)为真 (4)(5)与合取的定义(7) (P1∧¬P2)→P3为真前提条件 (8)P3为真 (6)(7)进行假言推理(2)如果今天是星期六，我们就要橘州公园看烟火晚会或者步行街去逛街如果步行街人太多，我们就不去步行街今天是星期六，步行街由于搞活动人太多了所以我们去橘州公园看烟火晚会解：P1：今天星期六 P2：我们到橘州公园看烟火晚会 P3：我们到步行街去逛街 P4：步行街人太多则以上语句可表示为：P1→( P2∨P3)，P4→¬P3，P1，P4⇒P2 (1) P1为真 前提条件(2) P1→( P2∨P3)为真前提条件 (3) ( P2∨P3)为真 (1)(2)进行假言推理(4)P4为真 前提条件(5) P4→¬P3为真 前提条件(6) ¬P3为真 (4)(5)进行假言推理(7) ¬P3→ P2为真 与(3)等值(8) P2为真 (6)(7)进行假言推理(3)如果肖寒是理科生，那么他的逻辑思维能力应该不差。
如果肖寒不是文科生，一定是理科生肖寒的逻辑思维能力很差，所以肖寒一定是文科生解：P1：肖寒是理科生 P2：肖寒逻辑思维能力差 P3：肖寒是文科生则以上推理过程可写成：P1→¬P2，¬P3→P1，P2⇒P3 (1)P2为真 前提条件(2) P1→¬P2为真前提条件 (3) P2→¬ P1为真与(2)等值(4) ¬ P1为真 (1)(3)进行假言推理(5) ¬P3→P1为真前提条件 (6) ¬ P1→ P3为真与(5)等值(7) P3为真 (4)(6)进行假言推理习题四采用定义1.6.2方法、消解法证明如下推理式1、¬p∨q，¬q∨r，r→s，p⇒s 证明： (1) ¬p∨q为真 前提条件(2)p为真 前提条件(3)q为真 因为(1)(2)为真，故其消解式为真(4) ¬q∨r为真 前提条件(5)r为真 因为(3)(4)为真，故其消解式为真(6) r→s为真 前提条件(7) ¬r∨s为真 与(6)等值(8)s为真 因为(5)(7)为真，故其消解式为真2、 p→(q→r)，q→(r→s) ⇒ (p∧q) →s (1) p→(q→r)为真 前提条件(2) ¬p∨ (¬q∨r)为真与(1)等值，条件式的等值(3) ¬p∨ ¬q∨r为真 与(2)等值，结合律(4) q→(r→s)为真 前提条件(5) ¬q∨(¬r∨s)为真 与(4)等值(6) ¬q∨¬r∨s为真 与(5)等值，结合律(7) ¬p∨ ¬q∨s为真 因为(3)(6)为真，故其消解式为真(8) ¬(p∧q) ∨s为真 与(7)等值，德摩律(9) (p∧q) →s为真 与(8)等值，因为条件式的等值式3、p→(q→r)，p，q⇒ r∨s (1) p→(q→r)为真 前提条件(2) ¬p∨ (¬q∨r)为真与(1)等值，条件式的等值(3) ¬p∨ ¬q∨r为真 与(2)等值，结合律(4)p为真 前提条件(5) ¬q∨r为真 因为(3)(4)为真，故其消解式为真(6)q为真 前提条件(7) r为真因为(5)(6)为真，故其消解式为真(8) r∨s为真 由(7)与析取的定义可知4、p→q，¬(p∧r) ，r⇒¬p (1) ¬(p∧r)为真 前提条件(2) ¬p∨¬r为真 与(1)等值，德摩律(3) r为真前提条件 (4) ¬p为真 因为(2)(3)为真，故其消解式为真5、p→q⇒ p→(p∧q)(1)p为真 附加前提(2) p→q为真前提条件 (3) ¬p∨q为真与(2)等值(4)q为真 (1)(3)为真，故其消解式为真(5) (p∧q)为真 (1)(4)与合取的定义5、q→p，q↔s，s↔t，t↔r，r⇒p∧q (1) t↔r为真 前提条件(2)(¬t∨r) ∧(t∨¬r)为真与(1)等值(3) (t∨¬r)为真 (2)与合取的定义(4)r为真 前提条件(5)t为真 因为(3)(4)为真，故其消解式为真(6) s↔t为真 前提条件(7)(¬s∨t) ∧(s∨¬t)为真与(6)等值(8) (s∨¬t)为真 (7)与合取的定义(9)s为真 因为(5)(8)为真，故其消解式为真(10) q↔s为真 前提条件(11)(¬q∨s) ∧(q∨¬s)为真与(10)等值(12) (q∨¬s)为真 (11)与合取的定义(13)q为真 (9)(12)为真，故消解式为真(14)q→p为真 前提条件(15)¬q∨p为真 与(14)等值(16)p为真 (13)(15)为真，故消解式为真(17) p∧q为真 (13)(16)为真及合取的性质7、p→r， q→s ，p∧q ⇒r∧s (1) p∧q为真 前提条件(2)p为真 (1)与合取的定义(3)q为真 (2)与合取的定义(4) p→r为真 前提条件(5) ¬p∨r为真 与(4)等值(6)r为真 (2)(5)为真，故其消解式为真(7) q→s为真 前提条件(8) ¬q∨s为真 与(7)等值(9)s为真 (3)(8)为真，故其消解式为真(10) r∧s为真 (6)(9)为真及合取的性质8、¬p∨r，¬q∨s，p∧q⇒t→ r∧s (1) p∧q为真 前提条件(2)p为真 (1)与合取的定义(3)q为真 (2)与合取的定义(4) ¬p∨r为真 前提条件(5)r为真 (2)(4)为真，故其消解式为真(6) ¬q∨s为真 前提条件(7) s为真 (3)(6)为真，故其消解式为真(8) r∧s为真 (5)(7)为真及合取的性质(9) ¬t∨( r∧s) 为真 (8)与析取的定义(10) t→ r∧s为真与(9)等值9、p→ (q→r)，s→p，q⇒ s→r (1) p→ (q→r)为真 前提条件(2) ¬p∨(¬q∨r)为真与(1)等值(3) ¬p∨¬q∨r为真 与(2)等值(4)q为真 前提(5) ¬p∨r为真 因为(3)(4)为真，故其消解式为真(6) s→p为真 前提条件(7) ¬s∨p为真 与(6)等值(8) ¬s∨r为真 (5)(7)为真，故其消解式为真(9) s→r为真 与(8)等值10、(p∨q) → (r∧s)，(s∨t) →u⇒p→u (1) (p∨q) → (r∧s)为真 前提条件(2) ¬(p∨q) ∨(r∧s)为真 与(1)等值(3) (¬p∧¬q) ∨(r∧s)为真 与(2)等值，德摩律(4)( ¬p ∨r) ∧(¬p∨s) ∧(¬q∨r) ∧(¬q∨s) 为真与(3)等值(5) (s∨t) →u为真 前提条件(6) ¬(s∨t) ∨u为真 与(5)等值(7) (¬s∧¬t) ∨u为真 与(6)等值(8) ( ¬s ∨u) ∧(¬t∨u)为真 与(7)等值(9) ( ¬s ∨u)为真 (8)与合取的定义(10) (¬p∨s)为真 (4)与合取的定义(11) ¬p ∨u为真 (9)(10)为真，故其消解式为真(12) p→u为真 与(11)等值11、p→¬q，¬r∨q，r∧¬s ⇒¬p (1) r∧¬s为真 前提条件(2)r为真 (1)与合取的定义(3) ¬r∨q为真 前提条件(4)q为真 (2)(3)消解式(5) p→¬q为真 前提条件(6) ¬p∨¬q为真 与(5)等值(6) ¬p为真 (4)(6)消解式12、p∨q，p→r，q→s⇒ r∨s (1) p∨q为真 前提条件(2) p→r为真 前提条件(3) ¬p∨r为真 与(2)等值(4) q∨r为真 (1)(3)消解式(5) q→s为真 前提条件(6) ¬q∨s为真 与(5)等值(7) r∨s为真 (4)(6)消解式为真第二章 谓词逻辑习题一1、指出下列公式∀x∃y(F(x,y)∧G(y,z)) ∨∃xH(x,y,z)中的指导变元，量词的辖域，各个体变项的自由出现和约束出现。
解：全称量词的指导变元为 x，第一个存在量词的指导变元为y，第2 个存在量词的指导变元为x在∀x∃y(F(x,y) ∧G(y,z))中约束变元为x 与y，自由变元为z在∃xH(x,y,z)中的约束变元为x，自由变元为y,z2、给定解释I 如下： (a)个体域为实数集R； (b)特定元素a=0； (c)函数f(x,y)=x-y，x 与y 为实数d)谓词F(x,y)为x=y，G(x,y)为x
3、给定解释I 如下： (a)个体域D=自然数N； (b)特定元素a=2； (c)函数f(x,y)=x+y，g(x,y)=x*y； (d)谓词F(x,y)为x=y； 给出下列各式在 I 下的解释，并讨论它们的真值： (1) ∀x∀y(F(f(x,a),y) →F(f(y,a),x)) (2) ∃x(F(f(x,x),g(x,x))) (1) ∀x∀y(F(f(x,a),y) →F(f(y,a),x)) =∀x∀y(F(f(x,2),y) →F(f(y,2),x)) =∀x∀y(F(x+2,y) →F(y+2,x)) =∀x∀y((x+2=y) →(y+2=x)) 当x+2=y 时即x-y=-2 即前件为1 时，后件y+2=x 即x-y=2 是不可能的，也即后件为0， 故此式的值为 02) ∃x(F(f(x,x),g(x,x))) = ∃x(F(x+x,x*x) = ∃x(x+x=x*x) = ∃x(2x=x*x) = ∃x(2=x) 当x为任意值，x=2时上式为真故原式为真 4、设个体域D={a,b,c}，在D上展开下列公式中的量词1) ∀x∀y(F(x) ∨G(y)) (2) ∀x(F(x,y) →∃yG(y)) (1) ∀x∀y(F(x) ∨G(y)) =∀x((F(x)∨G(a))∧(F(x)∨G(b))∧(F(x)∨G(c))) =∀x(F(x)∨(G(a) ∧G(b) ∧G(c))) =∀x(F(x))∨(G(a) ∧G(b) ∧G(c))) =(F(a) ∧F(b) ∧F(c))∨(G(a) ∧G(b) ∧G(c))) (2) ∀x(F(x,y) →∃yG(y)) = ∀x(F(x,y)→(G(a)∨G(b)∨G(c))) =(F(a,y)→(G(a)∨G(b)∨G(c))) ∧(F(b,y)→(G(a)∨G(b)∨G(c))) ∧(F(c,y)→(G(a)∨G(b)∨G(c))) 5、在给定解释I如下： (a)个体域D={3,4} (b)f(3)=4,f(4)=3 (c)F(3,3)=F(4,4)=0,F(3,4)=F(4,3)=1 试求下列公式在I下的真值： (1) ∀x∃yF(x,y) (2) ∃x∀yF(x,y) (1) ∀x∃yF(x,y) =∀x(F(x,3)∨F(x,4。