资源描述：
《离散数学复习题(请参考课件)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学Part1_数理逻辑部分1．将下列命题符号化。P48（1）豆沙包是由面粉和红小豆做成的.（2）苹果树和梨树都是落叶乔木.（3）王小红或李大明是物理组成员.（4）王小红或李大明中的一人是物理组成员.（5）由于交通阻塞，他迟到了.（6）如果交通不阻塞，他就不会迟到.（7）他没迟到，所以交通没阻塞.（8）除非交通阻塞，否则他不会迟到.（9）他迟到当且仅当交通阻塞.分清复合命题与简单命题分清相容或与排斥或分清必要与充分条件及必要充分条件答案：（1）是简单命题（2）是合取式（3）是析取式（相容或）（4）是析取式（排斥或）请分别写出（1）—（4）的符号化形式设p:交通阻塞，
2、q:他迟到（5）p®q,（6）Øp®Øq或q®p（7）Øq®Øp或p®q,（8）q®p或Øp®Øq（9）p«q或Øp«Øq可见（5）与（7），（6）与（8）相同（等值）3．用真值表判断下面公式的类型P51（1）pÙrÙØ(q®p)（2）((p®q)®(Øq®Øp))Úr（3）(p®q)«(p®r)按层次写真值表，由最后一列判类型答案：（1）为矛盾式，（2）为重言式，（3）为可满足式例用等值演算法判断下列公式的类型P59（1）qÙØ(p®q)（2）(p®q)«(Øq®Øp)（3）((pÙq)Ú(pÙØq))Ùr)解（1）qÙØ(p®q)ÛqÙØ(ØpÚq)（蕴涵等值式）Û
3、qÙ(pÙØq)（德摩根律）ÛpÙ(qÙØq)（交换律，结合律）ÛpÙ0（矛盾律）Û0（零律）由最后一步可知，（1）为矛盾式.（2）(p®q)«(Øq®Øp)Û(ØpÚq)«(qÚØp)（蕴涵等值式）Û(ØpÚq)«(ØpÚq)（交换律）Û1由最后一步可知，（2）为重言式.问：最后一步为什么等值于1？说明：（2）的演算步骤可长可短，以上演算最省.（3）((pÙq)Ú(pÙØq))Ùr)Û(pÙ(qÚØq))Ùr（分配律）ÛpÙ1Ùr（排中律）ÛpÙr（同一律）由最后一步可知，（3）不是矛盾式，也不是重言式，它是可满足式，其实101,111是成真赋值，000,010等是成
4、假赋值.总结：从此例可看出A为矛盾式当且仅当AÛ0A为重言式当且仅当AÛ1例求公式A=(p®Øq)®r的主析取范式与主合取范式.P71（1）求主析取范式(p®Øq)®rÛ(pÙq)Úr（析取范式）①(pÙq)Û(pÙq)Ù(ØrÚr)Û(pÙqÙØr)Ú(pÙqÙr)Ûm6Úm7②rÛ(ØpÚp)Ù(ØqÚq)ÙrÛ(ØpÙØqÙr)Ú(ØpÙqÙr)Ú(pÙØqÙr)Ú(pÙqÙr)Ûm1Úm3Úm5Úm7③②,③代入①并排序，得(p®Øq)®rÛm1Úm3Úm5Úm6Úm7（主析取范式）（2）求A的主合取范式(p®Øq)®rÛ(pÚr)Ù(qÚr)（合取范式）①pÚ
5、rÛpÚ(qÙØq)ÚrÛ(pÚqÚr)Ù(pÚØqÚr)ÛM0ÙM2②qÚrÛ(pÙØp)ÚqÚrÛ(pÚqÚr)Ù(ØpÚqÚr)ÛM0ÙM4③②,③代入①并排序，得(p®Øq)®rÛM0ÙM2ÙM4（主合取范式1．设A与B均为含n个命题变项的公式，判断下列命题是否为真？P85（1）AÛB当且仅当A与B有相同的主析取范式（2）若A为重言式，则A的主合取范式为0（3）若A为矛盾式，则A的主析取范式为1（4）任何公式都能等值地化成{Ù,Ú}中的公式（5）任何公式都能等值地化成{Ø,®,Ù}中的公式（1）为真，这是显然的（2）为假.注意,任何公式与它的主范式是等值的，显然
6、重言式不能与0等值。重言式的主合取范式不含极大项，因而主合取范式为1.（3）的分析类似于（2），矛盾式的主合取范式为0.（4）为假，因为{Ù,Ú}不是完备集，比如矛盾式Ø(p®q)Ùq不能化成{Ù,Ú}中的公式.（5）为真，注意{Ø,®,Ù}的子集{Ø,®}为完备集.2．通过求主范式判公式类型P87（1）(p®q)®(Øq®Øp)（2）Ø(p®q)Ùq（3）(p®q)ÙØp（1）重言式，（2）矛盾式，（3）可满足式解用等值演算法求解（1）(p®q)®(Øq®Øp)ÛØ(ØpÚq)Ú(qÚØp)(消去®)①Û(pÙØq)Ú(qÚØp)(Ø内移)②Û(pÙØq)Ú(ØpÙq
7、)Ú(pÙq)Ú(ØpÙØq)③Ûm2Úm1Úm3Úm0④Ûm0Úm1Úm2Úm3⑤Û1⑥问由②如何得③？⑤为主析取范式，⑥为主合取范式结论：（1）为重言式（2）Ø(p®q)ÙqÛØ(ØpÚq)Ùq①ÛpÙØqÙq②Û0③ÛM0ÙM1ÙM2ÙM3④问：由②如何得③？③为主析取范式，④为主合取范式结论：（2）为矛盾式.（3）(p®q)ÙØpÛm0Úm1①ÛM2ÙM3②请自己等值演算得①与②结论：（3）为可满足式请用真值表再解此题3．已知命题公式A中含3个命题变项p,q,r，并知道它的成真赋值为001,010,111,求A的主析取范式和主合取
