四川大学离散数学课后习题一解答或提示

-.z.习题一解答或提示1.(1)设P:他是本片的编剧，Q:他是本片的导演。PQ(2)设P:银行利率降低，Q:股价上扬。PQ(3)设P:银行利率降低，Q:股价上升。～(PQ)(4)设P:这个对象是占据空间的,Q:这个对象是有质量的,R:这个对象是不断变化的,S:这个对象称为物质。PQRS(5)设P:他今天乘火车去了，Q:他今天随旅行团去了九寨沟。PQ(6)设P:小身体薄弱，设Q:小极少生病,设R:小头脑好使。PQR(7)设P:这个人不识庐山真面目，设Q:这个人身在庐山中。QR(8)设P:两个三角形相似,设Q:两个三角形的对应角相等或者对应边成比例。PQ(9)设P:一个整数能被6整除，设Q:这个整数能被2和3整除。PQ设R:一个整数能被3整除，设S:这个整数的各位数字之和也能被3整除。RS2、(1)命题T(2)命题T/F(3)不是命题，因为真值无法确定。(4)命题T(5)不是命题。(6)命题T(7)命题T/F(8)不是命题，是悖论。5、〔1〕证：～〔〔～P∧Q〕∨〔～P∧～Q〕〕∨〔P∧Q〕〔～〔～P∧Q〕∧～〔～P∧～Q〕〕∨〔P∧Q〕〔〔P∨～Q〕∧〔P∨Q〕〕∨〔P∧Q〕〔P∨〔～Q∨Q〕〕∨〔P∧Q〕P∨〔P∧Q〕P〔3〕证：P→(Q∨R)～P∨(Q∨R)～P∨Q∨～P∨R〔～P∨Q〕∨〔～P∨R〕(P→Q〕∨〔P→R〕6、解：如果P∨QQ∨R，不能断定PR。因为当Q=T时，P∨QQ∨R恒成立。如果P∧QQ∧R，不能断定PR。因为当Q=F时，P∧QQ∧R恒成立。如果～P～R，则PR。8、把以下各式用↑等价表示出来：解：〔P∧Q〕∨～P〔(P↑Q)↑(P↑Q)〕∨〔P↑P〕〔〔(P↑Q)↑(P↑Q)〕↑〔(P↑Q)↑(P↑Q)〕〕↑〔〔P↑P〕↑〔P↑P〕〕〔3〕解：〔P→〔Q∨～R〕〕∧～P〔～P∨〔Q∨～R〕〕∧～P〔〔P↑P〕∨〔Q∨〔R↑R〕〕〕∧〔P↑P〕；〔〔P↑P〕∨〔〔Q↑Q〕↑〔〔R↑R〕↑〔R↑R〕〕〕〕∧〔P↑P〕〔〔〔P↑P〕↑〔P↑P〕〕↑〔〔〔Q↑Q〕↑〔〔R↑R〕↑〔R↑R〕〕〕↑〔〔Q↑Q〕↑〔〔R↑R〕↑〔R↑R〕〕〕〕〕∧〔P↑P〕〔〔〔〔P↑P〕↑〔P↑P〕〕↑〔〔〔Q↑Q〕↑〔〔R↑R〕↑〔R↑R〕〕〕↑〔〔Q↑Q〕↑〔〔R↑R〕↑〔R↑R〕〕〕〕〕↑〔P↑P〕〕↑〔〔〔〔P↑P〕↑〔P↑P〕〕↑〔〔〔Q↑Q〕↑〔〔R↑R〕↑〔R↑R〕〕〕↑〔〔Q↑Q〕↑〔〔R↑R〕↑〔R↑R〕〕〕〕〕↑〔P↑P〕〕9、证：∵P∨Q～～P∨Q〔～P〕→QP∧Q～〔～P∨～Q〕～〔P→～Q〕而{～，∨，∧}是功能完备集，∴{～，→}是功能完备集，～，→不能互相表示，故{～，→}是最小功能完备集。又∵PQUOTEQ～(P→Q)，∴{～，QUOTE}也是最小功能完备集。10、证：由书上的表1.16可知，“～〞对应的真值表含2个1和2个0，而“〞对应的真值表也含2个1和2个0，∨对应的真值表含3个1和1个0，∧对应的真值表含1个1和3个0，所以，“∨〞无法用“～〞和“〞来表示，同样“∧〞也无法用“～〞和“〞来表示，因此，{～，}不是功能完备集。12.解：〔1〕a)真值表法PQRSQ∧RQ∧RS〔P→〔Q∧RS〕〕0000000100100011010001010110011110001001101010111100110111101111010101010101101101010101010110111111111111111101由表中看出，i)使公式〔P→〔Q∧RS〕〕取值1时的解释所对应的全部极小项为：〔～P∧～Q∧～R∧～S〕，〔～P∧～Q∧～R∧S〕，〔～P∧～Q∧R∧～S〕，〔～P∧～Q∧R∧S〕，〔～P∧Q∧～R∧～S〕，〔～P∧Q∧～R∧S〕，〔～P∧Q∧R∧～S〕，〔～P∧Q∧R∧S〕，〔～Q∧P∧～R∧～S〕，〔～Q∧P∧～R∧S〕，〔～Q∧P∧R∧～S〕，〔～Q∧P∧R∧S〕，〔～R∧Q∧P∧～S〕，〔～R∧Q∧P∧S〕，〔S∧Q∧R∧P〕，由定理1.8，其主析取式为：〔～P∧～Q∧～R∧～S〕∨〔～P∧～Q∧～R∧S〕∨〔～P∧～Q∧R∧～S〕∨〔～P∧～Q∧R∧S〕∨〔～P∧Q∧～R∧～S〕∨〔～P∧Q∧～R∧S〕∨〔～P∧Q∧R∧～S〕∨〔～P∧Q∧R∧S〕∨〔～Q∧P∧～R∧～S〕∨〔～Q∧P∧～R∧S〕∨〔～Q∧P∧R∧～S〕∨〔～Q∧P∧R∧S〕∨〔～R∧Q∧P∧～S〕∨〔～R∧Q∧P∧S〕∨〔S∧Q∧R∧P〕。ii〕使公式〔P→〔Q∧RS〕〕取值0时的解释所对应的全部极大项为：～P∨～Q∨～R∨S由定理1.7，其主合取式为：～P∨～Q∨～R∨S。■b)等价变换法P((Q∧R)S)～P∨(～(Q∧R)∨S)～P∨～Q∨～R∨S-----主合取式〔～P∧〔～Q∨Q〕∧〔～R∨R〕∧〔～S∨S〕〕∨〔～Q∧〔～P∨P〕∧〔～R∨R〕∧〔～S∨S〕〕∨〔～R∧〔～P∨P〕∧〔～Q∨Q〕∧〔～S∨S〕〕∨〔S∧〔～P∨P〕∧〔～Q∨Q〕∧〔～R∨R〕〕------添加永真式〔～P∧～Q∧～R∧～S〕∨〔～P∧～Q∧～R∧S〕∨〔～P∧～Q∧R∧～S〕∨〔～P∧～Q∧R∧S〕∨〔～P∧Q∧～R∧～S〕∨〔～P∧Q∧～R∧S〕∨〔～P∧Q∧R∧～S〕∨〔～P∧Q∧R∧S〕∨〔～Q∧～P∧～R∧～S〕∨〔～Q∧～P∧～R∧S〕∨〔～Q∧～P∧R∧～S〕∨〔～Q∧～P∧R∧S〕∨〔～Q∧P∧～R∧～S〕∨〔～Q∧P∧～R∧S〕∨〔～Q∧P∧R∧～S〕∨〔～Q∧P∧R∧S〕∨〔～R∧～Q∧～P∧～S〕∨〔～R∧～Q∧～P∧S〕∨〔～R∧～Q∧P∧～S〕∨〔～R∧～Q∧P∧S〕∨〔～R∧Q∧～P∧～S〕∨〔～R∧Q∧～P∧S〕∨〔～R∧Q∧P∧～S〕∨〔～R∧Q∧P∧S〕∨〔S∧～Q∧～R∧～P〕∨〔S∧～Q∧～R∧P〕∨〔S∧～Q∧R∧～P〕∨〔S∧～Q∧R∧P〕∨〔S∧Q∧～R∧～P〕∨〔S∧Q∧～R∧P〕∨〔S∧Q∧R∧～P〕∨〔S∧Q∧R∧P〕------合并一样的项〔～P∧～Q∧～R∧～S〕∨〔～P∧～Q∧～R∧S〕∨〔～P∧～Q∧R∧～S〕∨〔～P∧～Q∧R∧S〕∨〔～P∧Q∧～R∧～S〕∨〔～P∧Q∧～R∧S〕∨〔～P∧Q∧R∧～S〕∨〔～P∧Q∧R∧S〕∨〔～Q∧P∧～R∧～S〕∨〔～Q∧P∧～R∧S〕∨〔～Q∧P∧R∧～S〕∨〔～Q∧P∧R∧S〕∨〔～R∧Q∧P∧～S〕∨〔～R∧Q∧P∧S〕∨〔S∧Q∧R∧P〕------主析取式〔3〕等价变换法QUOTEQUOTEQUOTEQUOTEQUOTEQUOTE------------主析取式QUOTEQUOTEQUOTEQUOTE-----------主合取式13.解：〔1〕QUOTEQUOTEQUOTE---------不等价〔2〕QUOTEQUOTE------------等价14.解：由题设A：A去，B：B去，C：C去，D：D去则满足条件的选派应是如下式：QUOTE构造和以上式等价的主析取式QUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTE共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：QUOTE即有三种方案：A和C去或者A和D去或者B和D去。15．证：〔1〕由定理1.11，需证QUOTE为永真式QUOTEQUOTEQUOTEQUOTEQUOTE〔3〕由定理1.11，需证QUOTE为永真式QUOTEQUOTE16．证：〔1〕性质1由定理1.11和“QUOTE〞的定义，QUOTE是永真式，所以QUOTE。〔2〕性质2由定理1.11，QUOTE是永真式，即QUOTE是永真式，由定理1.3，QUOTE成立。〔3〕性质3由定理1.11，QUOTE是永真式，又QUOTE是永真式，根据“QUOTE〞的定义，B必是永真式。17．证：“QUOTE〞QUOTE是永真式，QUOTEQUOTE“QUOTE〞因为上述等价式是可逆的，当QUOTE，必有QUOTE。18．解：设 P：珍宝藏在东厢房 Q：藏宝的房子靠近池塘 R：房子的前院栽有大柏树 S：珍宝藏在花园正中地下 T：后院栽有香樟树 M：珍宝藏在附近〔后院〕对语句符号化以后得到以下蕴涵式：QUOTEQUOTEQUOTEQUOTEQUOTEQUOTEQUOTE所以S为真，即珍宝藏在花园正中地下。19．解：(1)不成立(P=0，Q=1)(2)不成立(P=1，Q=R=0)(3)不成立(P=0，Q=1)(4)不成立(P=0，Q=1，R=0)(5)不成立(P=1，Q=1，R=0)20．证：〔1〕利用CP规则①QUOTE(附加前提规则)②QUOTE③QUOTE④QUOTE⑤QUOTE⑥QUOTE⑦QUOTECP规则①⑥〔2〕利用CP规则①QUOTE(附加前提规则)②QUOTE③QUOTE④QUOTE⑤QUOTE⑥QUOTE⑦QUOTE⑧QUOTE⑨QUOTECP规则①⑧〔4〕〔反证法〕①QUOTE(附加前提规则)②QUOTE③QUOTE④QUOTE⑤QUOTE⑥QUOTE⑦QUOTE⑧QUOTE⑨QUOTEeq\o\ac(○,10)QUOTEeq\o\ac(○,11)QUOTEQUOTEeq\o\ac(○,12)QUOTEQUOTEeq\o\ac(○,13)EQUOTEeq\o\ac(○,14)BQUOTEeq\o\ac(○,15)QUOTEQUOTEeq\o\ac(○,16)QUOTEeq\o\ac(○,17)FTeq\o\ac(○,15)eq\o\ac(○,16)21．(2)解：对原子命题符号化P：无任何痕迹Q：失窃时，小花在OK厅R：失窃时，小英在OK厅S：失窃时，小胖在附近T：金刚是偷窃者M：瘦子是偷窃者前提：QUOTE结论：？推导：①QUOTEQUOTE②QUOTEQUOTE③QUOTE T①②EI④QUOTEQ