离散参考答案(全)

离散数学浙江工业大学计算机学院浙江工业大学软件学院第一章命题逻辑题解2020/1/28离散数学3(1)指出下列语句哪些是命题，哪些不是命题，如果是命题，指出它的真值。a)离散数学是计算机科学系的一门必修课。b)计算机有空吗？c)明天我去看电影。d)请勿随地吐痰！习题1-1(1)答：a)是命题。是真命题。答：b)不是。答：c)是命题，但真值需根据具体情况确定。答：d)不是命题。2020/1/28离散数学4e)不存在最大质数。f)如果我掌握了英语、法语，那么学习其它欧洲语言就容易得多。g)９＋５≤１２。h)x＝3。i)我们要努力学习。答：e)是命题。是真命题。答：f)是命题。是真命题。答：g)是命题，是假命题。答：i)不是命题。答：h)不是命题。习题1-1(3)(3)设Ｐ表示命题“天下雪。”Ｑ表示命题“我将去镇上。”Ｒ表示命题“我有时间。”以符号形式写出下列命题。a)如果天不下雪和我有时间，那么我将去镇上。b)我将去镇上，仅当我有时间时。c)天不下雪。d)天下雪，那么我不去镇上。2020/1/28离散数学5题解：1-1(3)Ｐ:天下雪。Ｑ:我将去镇上。Ｒ:我有时间。a)如果天不下雪和我有时间，那么我将去镇上。b)我将去镇上，仅当我有时间时。c)天不下雪。d)天下雪，那么我不去镇上。2020/1/28离散数学6答：(P∧R)→Q答：Q→R答：P。答：P→R习题1-1(5)(5)将下列命题符号化。a)王强身体很好，成绩也很好。b)小李一边看书，一边听音乐。c)气候很好或很热。d)如果a和b是偶数，则a+b是偶数。e)四边形ABCD是平行四边形，当且仅当它的对边平行。f)停机的原因在于语法错误或程序错误。2020/1/28离散数学7题解：1-1(5)(5)将下列命题符号化。a)王强身体很好，成绩也很好。b)小李一边看书，一边听音乐。c)气候很好或很热。2020/1/28离散数学8答：原子命题：P:王强身体好;Q:王强成绩好。P∧Q答：原子命题P:小李看书;Q:小李听音乐。P∧Q答：原子命题P:气候好;Q:气候热。(P∧Q)∨(P∧Q)题解：1-1(5)d)如果a和b是偶数，则a+b是偶数。e)四边形ABCD是平行四边形，当且仅当它的对边平行。f)停机的原因在于语法错误或程序错误。2020/1/28离散数学9答：原子命题P:a是偶数;Q:b是偶数;R:a+b是偶数。P∧Q→R答：原子命题P:ABCD是平行四边形;Q:ABCD的对边平行。PQ答：原子命题：P:停机的原因是语法错误;Q:停机的原因是有程序错误。P∨Q题解：1-2(1)(1)判别下列公式哪些是合式公式，哪些不是合式公式。a)(Q→Ｒ∧Ｓ)。b)(P(R→S))。c)((P→Q)→(Q→P))。d)((RS→T)。e)((P→(Q→R))→((P→Q)→(P→R)))。2020/1/28离散数学10a)是。b)是。c)不是;多个闭括号。d)不;缺联结词。e)是。习题1-3(7)(7)用符号形式写出下列命题。a)假如上午不下雨，我去看电影，否则就在家里读书或者看报。b)我今天进城，除非下雨。c)仅当你走我将留下。2020/1/28离散数学14题解：1-3(7)a)假如上午不下雨，我去看电影，否则就在家里读书或者看报。2020/1/28离散数学15答：a)原子命题：设P:下雨;Q:我看电影;R:我读书;S:我看报。()(())PQPRSb)我今天进城，除非下雨。答：b)原子命题：设P:我进城;Q:下雨。Q→P。不是：P→Q，不是用进城来判定下雨，命题没有这个意思。如：指南针指向南或北，除非旁边有磁铁。意为：如果旁边没有磁铁，指南针指向南或北。题解：1-3(7)c)仅当你走我将留下。2020/1/28离散数学17答：c)原子命题：设P:你走;Q:我留下。Q→P不可符合化为：P→Q如果你走了，我则留下。原句没有这个意思，原句是：你走了，我不一定留下，但我留下了，则你一定走了。题解1-4(1)(1)求下列各复合命题的真值表。b)(P∧R)∨(P→Q)。2020/1/28离散数学18PQRP∧RP→Q(P∧R)∨(P→Q)TTTTTTTTFFTTTFTTFTTFFFFFFTTFTFFTFFTTFFTFTTFFFFTT题解1-4(1)e）(P→(Q→R))→((P→Q)→(P→R))2020/1/28离散数学19PQRQ→RP→(Q→R)P→QP→R(P→Q)→(P→R)eTTTTTTTTTTTFFFTFFTTFTTTFTTTTFFTTFFTTFTTTTTTTTFTFFTTTTTFFTTTTTTTFFFTTTTTT习题1-4(7)(7)证明下列等价式：a)A→(B→A)A→(A→B)。d)(AB)(A∧B)∨(A∧B)。f)A→(B∨C)(A∧B)→C。g)(A→D)∧(B→D)(A∨B)→D。2020/1/28离散数学20题解1-4(7)a)A→(B→A)A→(A→B)。2020/1/28离散数学21证明：A→(B→A)A∨(B∨A)A∨(A∨B)A∨(A→B)A→(A→B)题解1-4(7)d)(AB)(A∧B)∨(A∧B)。2020/1/28离散数学22证明：(AB)((A→B)∧(B→A))((A∨B)∧(B∨A))(A∧B)∨(A∧B)题解1-4(7)f)A→(B∨C)(A∧B)→C2020/1/28离散数学23证明：A→(B∨C)A∨(B∨C)(A∨B)∨C(A∧B)∨C(A∧B)→C题解1-4(7)g)(A→D)∧(B→D)(A∨B)→D2020/1/28离散数学24证明：(A→D)∧(B→D)(A∨D)∧(B∨D)(A∧B)∨D(A∨B)∨D(A∨B)→D习题1-5(1)(1)试证下列各式为重言式。a)(P∧(P→Q))→Q。c)((P→Q)∧(Q→R))→(P→R)。2020/1/28离散数学25题解1-5(1)a)(P∧(P→Q))→Q2020/1/28离散数学26[证法1]设P(P∧Q)为假,则P真而(P∧Q)假。进而得出Q假,因此PQ必假。[证法2]P(P∧Q)P∨(P∧Q)P∨QPQ。由定理1-5.4,原命题得证。题解1-5(1)c)((P→Q)∧(Q→R))→(P→R)2020/1/28离散数学27c)证明：因为((P→Q)∧(Q→R))(P→R)所以((P→Q)∧(Q→R))→(P→R)为重言式P39（按顺序写变元）把下列各式化为析取范式：2-(a)(P∧Q)RP∨Q∨R2-(c)(P∨Q)∧(ST)(P∧Q∧S)∨(P∧Q∧T)2-(e)(P∧Q)∨(P∨Q)…(P∧Q)∨(P∧Q)把下列各式化为合取范式：3-(a)P∨(P∧Q∧R)…(P∨Q)∧(P∨R)3-(c)(PQ)…P∧Q…(P∨Q)∧(P∨Q)∧(P∨Q)这两个答案都可以3-(e)(P∧Q)∨(P∧Q)…(P∨Q)∧(P∨Q)求下列各式的主合取范式和主析取范式：4-(a)(P∨Q)(PQ)(P∨Q)∨(PQ)(P∧Q)∨(P∧Q)∨(P∧Q)=∑1,2,3主析取范式∏0=P∨Q主合取范式4-(c)P∨(P(Q∨(QR)))P∨(P∨(Q∨(Q∨R)))P∨Q∨R主合取范式=∏0∑1,2,3,4,5,6,7=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主析取范式4-(e)P(P∧(QP))P∨(P∧(Q∨P))(P∨P)∧(P∨Q∨P)T∑0,1,2,3主析取范式=(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)主合取范式不存在。7.A,B,C,D四个人中要派两个人出差，有三个派遣前提：（1）若A去则C和D中要去一人；（2）B和C不能都去；（3）C去则D要留下。能有几种派遣方法？解：设A：A出差，B：B出差，C：C出差，D：D出差，则三个前提可以符号化为：（1）A((CD))（2）(B∧C)（3）CD按照题目要求，三个前提必须同时成立，即A((CD))∧(B∧C)∧(CD)(A((C∧D)∨(C∧D)))∧(B∨C)∧(C∨D)(A∨((C∧D)∨(C∧D)))∧((B∧C)∨(B∧D)∨C∨(C∧D))(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)在上述的析取范式中，有些项明显不符合题意：如(A∧B∧D)表示三个人都不出差，这是不满足题意的；另外如(C∧D∧C∧D)属于矛盾式，应在式中删除。故可以得到原式为：(A∧C)∨(C∧D∧B)∨(C∧D)∨(C∧D∧B)表示存在三种派法：A和C，A和D，B和D。注意：式中C∧D可以表示派A和D，或派B和D，与其他三项合并，总共三种派法。P47(2_abd,3_abd,4_1,5_ac)2、仅用规则P和T，推证以下各式。3、用CP规则证明2中各题。(a)A∨B，CBAC证法一（仅用规则P和T）：(1)A∨BP(2)ABT(1)E条件等值式(3)CBP(4)BCT(3)E假言易位(5)ACT(2)(4)I假言三段论(a)A∨B，CBAC证法二（CP规则）：(1)AP(附加前提)(2)A∨BP(3)BT(1)(2)I析取三段论(4)CBP(5)CT(3)(4)I拒取式(6)ACCP规则(b)A(BC)，(C∧D)E，F(D∧E)A(BF)证法一（仅用规则P和T）(1)A(BC)P(2)(A∧B)CT(1)E输出律(3)(C∧D)EP(4)C(DE)T(4)E输出律(5)(A∧B)(DE)T(3)(4)I假言三段论(6)F(D∧E)P(7)F(D∨E)T(7)E德摩根(8)F(DE)T(8)E条件等值式(9)(DE)FT(9)E假言易位(10)(A∧B)FT(6)(10)I假言三段(11)A(BF)T(11)E输出律(b)A(BC)，(C∧D)E，F(D∧E)A(BF)(CP规则)(1)AP(附加前提)(2)A(BC)P(3)BCT(2)(4)I假言推理(4)(C∧D)EP(5)C(DE)T(4)E输出律(6)B(DE)T(3)(4)I假言三段论(7)F(D∧E)P(8)F(D∨E)T(7)E德摩根(9)F(DE)T(8)E条件等值式(10)(DE)FT(9)E假言易位(11)BFT(6)(10)I假言三段(12)A(BF)CP规则(d)A(B∧C)，B∨D，(EF)D，B(A∧E)BE证法一（仅用规则P和T）:红色条件有错，去掉！(1)(BE)P(附加前提)(2)(B∨E)T(1)E条件等值式(3)B∧ET(2)E德摩根律(4)BT(3)I化简(5)ET(3)I化简(6)B∨DP(7)DT(4)(6)I析取三段论(8)(EF)DP(9)(EF)T(7)(8)I拒取式(10)(E∨F)T(9)E条件等值式(11)E∧FT(10)E德摩根律(12)ET(11)I化简(13)E∧E(矛盾)T(5)(12)I合取引入(d)B∨D，(EF)DBE证法二（CP规则）：(1)BP(附加前提)(2)B∨DT(1)E条件等值式(3)DT(1)(2)E析取三