离散数学 习题答案

《离散数学 习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学习题参考答案⇔(p∧(q∨¬q))∨((p∨¬p)∧¬q)第一章命题逻辑⇔(p∧q)∨(p∧¬q)∨(p∧¬q)∨(¬p∧¬q)⇔(p∧q)∨(p∧¬q)∨(¬p∧¬q)因为一个公式的值不是真，就是假，因此当我们得到一个公习题一的取值为真的情况时，剩下的组合是取值为假，因此当得到小项的析取组成的主析取范式后，可以针对剩下的组合写出1、构造公式(p∧q)∨(¬p∧¬q)、p↔q的真值表。主合取范式。2、构造公式¬(p∨q)与¬p∧¬q的真值表。如当我们得到(¬p→q)→(¬q∨p)的大项之合取(p∨¬q)后，使3、构造公式p

2、、p∧p、p∨p的真值表。(p∨¬q)为假时(p,q)的值为(0,1)，故其标记为M，剩余的取值4、构造公式p∨(q∧r)、(p∨q)∧(p∨r)的真值表。015、构造公式p∨(p∧r)、p的真值表。为(0,0),(1,0),(1,1)，故小项之析取为m∨m∨m。0010116、构造公式p∧(p∨r)、p的真值表。反之，若先得到其小项的析取，也可得到其大项的合取。反7、构造公式p↔q、¬q↔¬p的真值表。正这两者将其所有组合瓜分完毕。8、构造公式(p→q)∧(p→¬q)、¬p的真值表。9、构造公式p、¬¬p的真值表。(2)(¬p→

3、q)→(q∧r)10、构造公式p∨¬p、p∧¬p的真值表pqr¬p¬p→q(q∧r)结果0001001略001100101011000111111习题二10001001010100一、分别用等算演算与真值表法，判断下列公式是否存在主1100100析取范式或主合取范式，若有，请写出来。1110111(1)(¬p→q)→(¬q∨p)(2)(¬p→q)→(q∧r)主析取范式=m∨m∨m∨m=(¬p∧¬q∧¬r)∨(¬p∧(3)(p∨(q∧r))→(p∨q∨r)000001011111¬q∧r)∨(¬p∧q∧r)∨(p∧q∧r)(4)¬(

4、q→¬p)∧¬p主合取范式=M∧M∧M∧M=(p∨¬q∨r)∧(¬p∨q(5)(p∧q)∨(¬p∨r)010100101110(6)(p→(p∨q))∨r∨r)∧(¬p∨q∨¬r)∧(¬p∨¬q∨r)(7)(p∧q)∨r(8)(p→q)∧(q→r)(3)(p∨(q∧r))→(p∨q∨r)(9)(p∧q)→q(p∨(q(p∨q(p∨(q∧r))pqr(q∧r)(10)¬(r↔p)∧p∧q∧r))∨r)→(p∨q∨r)解：(1)0000001pq¬p(¬p→q)¬q(¬q∨p)(¬p→q)→(¬q∨p)0010001010001100

5、1011101100110111000100011110011111010111110101111011111111111存在主析取范式=成真赋值对应的小项的析取永真式，所有小项的析取得到其主析取范式=m∨m∨m=(¬p∧¬q)∨(p∧¬q)∨(p∧q)=(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(¬p∧q∧¬r)∨(¬p∧q∧r)∨001011(p∧¬q∧¬r)∨(p∧¬q∧r)∨(p∧q∧¬r)∨(p∧q∧r)主析取范式=成假赋值对应的大项的合取由于没为假的指派，所以没有为假赋值，所对应的大项合取=M=p∨¬q01构成的合取，

6、即没有主合取范式。等值演算：¬(p∨(q∧r))∨(p∨q∨r)=(¬p∧¬(q∧r))∨(p∨q∨r)=((¬p∧(¬p→q)→(¬q∨p)¬q)∨(¬p∧¬r))∨(p∨q∨r)=⇔¬(¬¬p∨q)∨(p∨¬q)(¬p∧¬q)∨(¬p∧¬r)∨p∨q∨r=¬(p∨q)∨(¬p∧¬r)∨p∨q∨⇔¬(p∨q)∨(p∨¬q)r=1永真⇔(¬p∧¬q)∨(p∨¬q)⇔(¬p∨(p∨¬q))∧(¬q∨(p∨¬q))(4)¬(q→¬p)∧¬p⇔(¬p∨p∨¬q)∧(¬q∨p∨¬q)pq¬p(q→¬p)¬(q→¬p)结果⇔(1∨¬q)∧(

7、p∨¬q)001100⇔(p∨¬q)011100这是大项，故为大项的合取，称为主合取范式100100(¬p→q)→(¬q∨p)110010⇔(p∨¬q)⇔(p)∨(¬q)没有成真的赋值，从而没有对应的小项，因此没有小项构成⇔(p∧1)∨(1∧¬q)的主析取范式永假式即矛盾式，为假指派对应的大项合取=(p∨q)∧(p∨¬q)1∧(¬p∨q)∧(¬p∨¬q)=(p∨r)∧(q∨r)原式=¬(¬q∨¬p)∧¬p=(q∧p)∧¬p=0=(p∨0∨r)∧(0∨q∨r)=(p∨(¬q∧q)∨r)∧((¬p∧p)∨q∨r)(5)(p∧q)∨(¬

8、p∨r)=(p∨¬q∨r)∧(p∨q∨r)∧(¬p∨q∨r)∧(p∨q∨r)pqr(p∧q)¬p(¬p∨r)(p∧q)∨(¬p∨r)=(p∨¬q∨r)∧(p∨q∨r)∧(¬p∨q∨r)00001110010111(8)(p→q)∧(q→r)0100