离散数学习题与解答

《离散数学习题与解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、作业题与解答第一章19(2)、(4)、(6)21(1)、(2)、(3)19、(2)解答:(p→┐p)→┐q真值表如下:pq┐p┐qp→┐p(p→┐p)→┐q00111101101010010111000119、(4)所以公式(p→┐q)→┐q为可满足式解答:(p→q)→(┐q→┐p)真值表如下:pq┐p┐qp→q┐q→┐p(p→q)→(┐q→┐p)0011111011011110010011100111所以公式(p→q)→(┐q→┐p)为永真式19、(6)解答:((p→q)∧(q→r))→(p→r)真值

2、表如下:pqrp→qq→rp→r(p→q)∧(q→r)((p→q)∧(q→r))→(p→r)0001111100111111010101010111111110001001101011011101000111111111所以公式((p→q)∧(q→r))→(p→r)为永真式21、(1)解答:┐(┐p∧q)∨┐r真值表如下:pqr┐p┐r┐p∧q┐(┐p∧q)┐(┐p∧q)∨┐r0001101100110011010111010111010010001011101000111100101111100011所

3、以成假赋值为:01121、(2)解答:(┐q∨r)∧(p→q)真值表如下:pqr┐q┐q∨rp→q(┐q∨r)∧(p→q)00011110011111010001001101111001100101110011000101110111所以成假赋值为:010,100,101,11021、(3)解答:(p→q)∧(┐(p∧r)∨p)真值表如下:pqrp→qp∧r┐(p∧r)┐(p∧r)∨p(p→q)∧(┐(p∧r)∨p)000101110011011101010111011101111000011010101

4、0101101011111111011所以成假赋值为:100,101第二章5、(1)(2)(3)6、(1)(2)(3)7、(1)(2)8、(1)(2)(3)5、求下列公式的主析取范式,并求成真赋值(1)(┐p→q)→(┐q∨p)Û┐(┐p→q)∨(┐q∨p)Û┐(┐(┐p)∨q)∨(┐q∨p)Û(┐p∧┐q)∨(┐q∨p)Û(┐p∧┐q)∨(p∧┐q)∨(p∧q)Ûm0∨m2∨m3，所以00，10，11为成真赋值。(2)(┐p→q)∧(q∧r)Û(┐┐p∨q)∧(q∧r)Û(p∨q)∧(q∧r)Û(p∧q

5、∧r)∨(q∧r)Û(p∧q∧r)∨(p∧q∧r)∨(┐p∧q∧r)Û(p∧q∧r)∨(┐p∧q∧r)Ûm3∨m7，所以011，111为成真赋值。(3)(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∨p∨q∨r)∧(┐r∨p∨q∨r))Û(┐p∧┐q)∨(1∧1)Û(┐p∧┐q)∨1Û1Ûm0∨m1∨m2∨m3∨m

6、4∨m5∨m6∨m7，所以000,001,010,011,100,101,110,111为成真赋值。7、求下列公式的主析取范式，再用主析取范式求主合取范式(1)(p∧q)∨rÛ(p∧q∧r)∨(p∧q∧┐r)∨(p∧r)∨(┐p∧r)Û(p∧q∧r)∨(p∧q∧┐r)∨(p∧r∧q)∨(p∧r∧┐q)∨(┐p∧r∧q)∨(┐p∧r∧┐q)Û(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r)Ûm1∨m3∨m5∨m6∨m7由主析取范式和主合取范式之间的关系，所以公式的主合

7、取范式为：(p∧q)∨rÛM0∧M2∧M4(2)(p→q)∧(q→r)Û(┐p∨q)∧(┐q∨r)Û(┐p∧(┐q∨r))∨(q∧(┐q∨r))Û(┐p∧┐q)∨(┐p∧r)∨(q∧┐q)∨(q∧r)Û(┐p∧┐q)∨(┐p∧r)∨(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)Ûm0∨m1∨m3∨m7由主析取范式和主合取范式之间的关系，所以公式的主合取范

8、式为：(p→q)∧(q→r)ÛM2∧M4∧M5∧M68、求下列公式的主合取范式，再用主合取范式求主析取范式(1)(p∧q)→qÛ┐(p∧q)∨qÛ(┐p∨┐q)∨qÛ┐p∨(┐q∨q)Û┐p∨1Û1该公式无主合取范式，所以公式的主析取范式为：(p∧q)→qÛm0∨m1∨m2∨m3(2)(p«q)→rÛ┐((┐p∨q)∧(p∨┐q))∨rÛ((p∧┐q)∨(┐p∧q))∨rÛ(((p∨(┐p∧q))∧(┐q∨(┐p∧q)))∨r