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

去找(1)设P:他是本片的编剧，Q:他是本片的导演。PQ(2)设P:银行利率降低，Q:股价上扬。PQ(3)设P:银行利率降低，Q:股价上升。～(PQ)(4)设P:这个对象是占据空间的,Q:这个对象是有质量的,R:这个对象是不断变化的,S:这个对象称为物质。PQRS(5)设P:他今天乘火车去了北京，Q:他今天随旅行团去了九寨沟。PQ(6)设P:小张身体单薄，设Q:小张极少生病,设R:小张头脑好使。PQR(7)设P:这个人不识庐山真面目，设Q:这个人身在庐山中。QR(8)设P:两个三角形相似,设Q:两个三角形的对应角相等或者对应边成比例。PQ(9)设P:一个整数能被6整除，设Q:这个整数能被2和3整除。PQ设R:一个整数能被3整除，设S:这个整数的各位数字之和也能被3整除。RS2、(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∨QQ∨R，不能断定PR。因为当Q=T时，P∨QQ∨R恒成立。如果P∧QQ∧R，不能断定PR。因为当Q=F时，P∧QQ∧R恒成立。如果～P～R，则PR。8、把下列各式用↑等价表示出来：去找(1)解：（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）而{～，∨，∧}是功能完备集，∴{～，→}是功能完备集，～，→不能互相表示，故{～，→}是最小功能完备集。又∵P错误!未找到引用源。Q～(P→Q)，∴{～，错误!未找到引用源。}也是最小功能完备集。10、证：由书上的表1.16可知，“～”对应的真值表含2个1和2个0，而“”对应的真值表也含2个1和2个0，∨对应的真值表含3个1和1个0，∧对应的真值表含1个1和3个0，所以，“∨”无法用“～”和“”来表示，同样“∧”也无法用“～”和“”来表示，因此，{～，}不是功能完备集。12.解：（1）a)真值表法PQRSQ∧RQ∧RS（P→（Q∧RS））00000001001000110100010101010111111去找由表中看出，i)使公式（P→（Q∧RS））取值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∧RS））取值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）等价变换法错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。------------主析取范式错误!未找到引用源。错误!未找到引用源。去找错误!未找到引用源。错误!未找到引用源。-----------主合取范式13.解：（1）错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。---------不等价（2）错误!未找到引用源。错误!未找到引用源。------------等价14.解：由题设A：A去，B：B去，C：C去，D：D去则满足条件的选派应是如下范式：错误!未找到引用源。构造和以上范式等价的主析取范式错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。去找错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：错误!未找到引用源。即有三种方案：A和C去或者A和D去或者B和D去。15．证：（1）由定理1.11，需证错误!未找到引用源。为永真式错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。去找错误!未找到引用源。错误!未找到引用源。（3）由定理1.11，需证错误!未找到引用源。为永真式错误!未找到引用源。错误!未找到引用源。16．证：（1）性质1由定理1.11和“错误!未找到引用源。”的定义，错误!未找到引用源。是永真式，所以错误!未找到引用源。。（2）性质2由定理1.11，错误!未找到引用源。是永真式，即错误!未找到引用源。是永真式，由定理1.3，错误!未找到引用源。成立。（3）性质3由定理1.11，错误!未找到引用源。是永真式，又错误!未找到引用源。是永真式，根据“错误!未找到引用源。”的定义，B必是永真式。17．证：“错误!未找到引用源。”错误!未找到引用源。是永真式，错误!未找到引用源。错误!未找到引用源。“错误!未找到引用源。”因为上述等价式是可逆的，当错误!未找到引用源。，必有错误!未找到引用源。。18．解：设P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园正中地下T：后院栽有香樟树M：珍宝藏在附近（后院）对语句符号化以后得到以下蕴涵式：错误!未找到引用源。错误!未找到引用源。去找错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。错误!未找到引用源。所以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规则①错误!未找到引用源。(附加前提规则)②错误!未找到引用源。③错误!未找到引用源。④错误!未找到引用源。⑤错误!未找到引用源。⑥错误!未找到引用源。⑦错误!未找到引用源。CP规则①⑥（2）利用CP规则①错误!未找到引用源。(附加前提规则)②错误!未找到引用源。③错误!未找到引用源。④错误!未找到引用源。⑤错误!未找到引用源。⑥错误!未找到引用源。⑦错误!未找到引用源。去找⑧错误!未找到引用源。⑨错误!未找到引用源。CP规则①⑧（4）（反证法）①错误!未找到引用源。(附加前提规则)②错误!未找到引用源。③错误!未找到引用源。④错误!未找到引用源。⑤错误!未找到引用源。⑥错误!未找到引用源。⑦错误!未找到引用源。⑧错误!未找到引用源。⑨错误!未找到引用源。○10错误!未找到引用源。○11错误!未找到引用源。错误!未找到引用源。○12错误!未找到引用源。错误!未找到引用源。○13E错误!未找到引用源。○14B错误!未找到引用源。○15错误!未找到引用源。错误!未找到引用源。○16错误!未找到引用源。○17FT○15○1621．(2)解：对原子命题符号化P：无任何痕迹去找：失窃时，小花在OK厅R：失窃时，小英在OK厅S：失窃时，小胖在附近T：金刚是偷窃者M：瘦子是偷窃者前提：错误!未找到引用源。结论：？推导：①错误!未找到引用源。错误!未找到引用源。②错误!未找到引用源。错误!未找到引用源。③错误!未找到引用源。T①②EI④错误!未找到引用源。错误!未找到引用源。⑤错误!未找到引用源。T③④I⑥错误!未找到引用源。错误!未找到引用源。⑦错