离散数学习题答案..docxVIP

离散数学 习题 参考答案第一章 命题逻辑习题一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)0000111001011