离散数学习题课带的答案

命题逻辑习题课参考答案命题符号化P:天下雪。Q:我将去镇上。R:我有时问。⑴如果天不下雪11我有时间，那么我将去镇上。HPAR)^Q(2)我将去镇上，仅当我有时间。Q-*R(3)天下雪，那么我不去镇上。P-iQ(4)或者你没有给我写信，或者它在途中丢失了。显然这里的“或者”是“不可兼取的或”。令P:你给我写信。Q:信在途中丢失了。@Q或(PAQ)VHPA^Q)(5)我们不能既划船乂跑步。令P:我们划船。Q:我们跑步。-(PAQ)(6)如果你来了，那么他唱不唱歌将看你是否为他伴奏而定。令P:你來了。Q:你为他伴奏。R:他唱歌。P^((Q->R)AHQ—R))或：P—*(QgR)(7)假如上午不下雨，我去看电影，否则就在家里读书或看报。令P:上午下雨。Q:我去看电影。R:我在家里读节。S:我在家里看报。(^P^Q)A(P^(RVS))(8)我今天进城，除非卜雨。令P:我今天进城。Q:今天下雨。表达式为:(9)仅当你走我将留下。令P:你走。Q:我留下。表达式为：Q^P或者二.重言式的证明方法方法1:列真值表。方法2:公式的等价变换，化简成“T"。方法3:用公式的主析取范式。(1＞证明(P-Q)-(P-(PAQ))是重言式。方法1:PQP-Qp-*(paq)(P^Q)^(P^(PAQ))FFTTTFTTTTTFFFTTTTTT方法2:(P^QWP^(PAQ))o+PVQ)V(，PV(P八Q))«(PA^Q)V((^PVP)A(^PVQ))^(PA^Q)V(TAHPVQ))o(PA-iQ)V(]PVQ)o(PV(，PVQ))A(^QV(^PVQ)«((PV，P)VQ))AHQV(QV-iP)^(TVQ))A((HQVQ)V^P)^TA(TV^P)«tat方法3(P^QWP^(PAQ))o+PVQ)V(]PV(P八Q))<^(PA-Q)V-PV(PAQ)o(PA]Q)V(”PA(QV]Q))V(PAQ)o(PA]Q)V(]PAQ)V(，PA]Q)V(PAQ)<^>(PAQ)V(PA^Q)V(]PAQ)V卜PA^Q)可见，该公式的主析取范式含有全部(四个)小项，这表明(P—Q)一(P一(PAQ))是永真式三，重言蕴涵式的证明方法方法1.列真值表。(即列永真式的真值表)(略)方法2.假设前件为真，推出后件也为真。方法3.假设后件为假，推出前件也为假。证明HA^(BVC))A(DVE)A((DVE)^-1A)^BVC方法2证明：设前件(-nA-^(BVC))A(DVE)A((DVE)^A)为真，则^A^(BVC)，DVE,(DVE)^A均为真。由DVE,(DVE)^A均为真，得->A为真，又由—iA—>(BVC)为具，得BVC为真。所以(-iA^(BVC))A(DVE)A((DVE)^A)BVCHA->(BVC))A(DVE)A((DVE)^™iA)^BVC方法3证明：设后件BVC为E则B与C均为F，1.如果DVE为T.贝ij1)+若A为T，则，A为F，则(DVE)^A为F,于是前件HA^(BVC))A(DVE)A((DVE)^A)为F。2).若A为Ft

则^AAT，于是^A^(BVC)为F,故前件(^A^(BVC))A(DVE)A((DVE)^A)为F。2.如果DVE为F,贝ij前件(^A^(BVC))A(DVE)A((DVE)^A)力F。A(^A^(BVC))A(DVE)A((DVE)^A)=>BVC(2)化简(AABAC)V(”AABAC)上式o(AV-A)A(BAC)<^TA(BAC)<^>BAC五.范式的写法及应用(1)写出(P^(QAR))AHA^R))W主析取范式和主合取范式方法1，用扛俏:表令A(P，Q，R)o(P->(QAR))A(iP->(iQA^R))A(P，Q，R)<=>mGVm7AA^R)V(PAQAR)«E(OJ)A(P，Q，R)oMiAM2AM3AM4AM5AM6<^(PVQV^R)A(PV^QVR)A(PV^QV-iR)A(^PVQVR)A(-iPVQV^R)A(^PV^QVR)c>n(l,2,3・4,5,6)PQRP-XQAR）a（^q，r）0FFFTTT1FFTrFF2FTFTFF3FTTTFF4TFFFTF5TFTFTF6TTFFTF7TTTTTT方法2.等价变换(P^(QAR))A(，P斗QA^R))(门PV(QAR))A(PV(，QA^R))口(^PAP)V(PAQAR))V(^PA^QA^R))V((QAR)A(，QA，R))«FV(PAQAR))V(-iPA-)QA^R)VF«(PAQAR))VHPA^QA^R)(P^(QAR))八(]P^(，QA]R))o(，PV(QAR))八(PVHQA^R))o(]PVQ)八(，PVR))A(PViQ)八(PViR)口(”PVQV(RA]R))A(”PV(QA]Q)VR))A(PV-!QV(RA^R))A(PV(QA^Q)V-iR)«(^PVQVR)A(，PVQV^R))A(，PVQVR)AhPV^QVR)八(PV^QVR)A(PV^QV-nR)A(PVQV]R)A(PV^QV^R)(^PVQVR)A(^PVQV-iR))A(^PViQVR)A(PV^QVR)A(PV^QV^R)A(PVQV-^R)(2)九B,C，D四个人中要派两个人出差，按下述三个条件有儿种派法？①若A去则C和D中耍去一个人。②B和C不能都去。③C去则D要留下。解.设A,B，C，D分別表示A去，B去，C去，D去。①

A—((CA~iD)V(―iC/\d))o^aV(cA^d)V(-1cAd)③

C-—CV~D总的条件为：HAV(CA^D)V(-iCAD))八(”BV-iC)A(iCV-iD)令此式为M。将(，AV(CA^D)V(^CAD))A(^BV^C)AHCV^D)化成析取范式。上式<^(，AV(CA—iD)V(™iCAD))A(^iCV(^>BA-iD))

A~iC)V(CA^>DA^iC)V(—iCADA-i'C)A(^AA^BA^D)V(CA^DA^BA^D)VHCADA-BA^D)<=>(^1AA~iC)VFV(—iC八D)V(^iAAA^iD)V(C八八，B)VF可以取-AA^C为T，得B和Di。取^CAD为T，得A和D去，或者B和D去。取CA-DA-B为T，得A和C去。得三种派法：A和C去、A和D去、B和D去。改锥扳手钳子锤子A有有B有r有I有C有有D有有(3)有工具箱A、B、C、D,各个箱内装的工具如下表所示。试M如何携带数量最少工具箱，而所包含的工具种类齐全。解：设A、B、C、D分别表示带A、B、C、D箱。则总的条件为：(AVC)A(AVBVD)A(BVC)A(BVD)为真。改锥扳手钳子锤子将(AVC)A(AVBVD)A(BVC)A(BVD)写成析取范式，上式o((AVC)八(BVC))八((AV(BVD))A(BVD))«((AAB)VC))A(BVD)^(AABAB)V(CAB)V(AABAD)V(CAD)<^(AAB)V(CAB)V(AABAD)V(CAD)分别可以取(AAB)、(CAB)、(CAD)为真。于是可以得到三种携带方法：带A和B箱，带6和(2箱，带C和D箱。六+逻辑推理熟练掌握三种推理方法。（1）（AVBK（C八D），（DVE）^P=>A^PL直接推理(D(AVBWCAD)P⑵-^(AVB)V(CAD)T(1)E⑶(^AA-iB)V(CAD)T(2)E⑷(^AVC)A(^BVC)A(-iAVD)A(-BVD)T(3)E⑸，AVDT(4)I(6)A->DT(5)E(7)(DVE)^PP⑻，(DVE)VPT(7)E⑼(^DA-E)VPT⑻E⑽(门DVP)A(^EVP)T(9)E(11)，DVPT⑽I(12)D^PT(IDE03)A^PT(6)(12)I2.附加前提⑴A⑵AVB⑶(AVB)-»(CAD)⑷CAD⑸D⑹DVE(7)(DVE)^P⑻P⑼A^PP(附加前提)T(1)IPT(2)(3)IT⑷

IT(5)1PT⑹⑺ICP3.反证法⑴-(A^P)⑵+AVP)⑶AA-^P⑷A⑸AVB⑹(AVB)->(CAD)⑺CAD⑻D(9)DVE⑽(DVE)->P(11)P(1Z)-nP(13)PA^PP(假设前提)T(1)ET⑵ET(3)IT(1)ITT(2)(3)IT(4)IT(5)IPT(6)(7)IT(3)IT01)(12)I(2)请根据下面事实，找出凶手:1.清洁工或者秘书谋害了经理。2.如果清洁工谋害了经理，则谋害小会发生在午夜前。3.如果秘书的证词足正确的，则谋害发生在午夜前。4.如果秘书的证词不正确，则午夜时屋甩灯光未火。5/如果清洁工富裕，则他不会谋害经理。6.经理冇钱且清洁工不富裕。7.午夜时屋甩灯火了。令A:清洁工谋害了经理。秘书谋害了经理。C:谋害发生在亇夜前。D:秘书的证词是正确的.E:午夜吋屋里灯光灭了。H:清洁工富裕.G:经理有钱.命题符号为：AVBA^C,D^C,^D^E,H^A,GA-iH,E^>?AVB,A->-C,B-C,I)—C⑴EP(2)-nD^EP(3)nD丁⑴⑵！⑷D(5)D^C⑹C(7)

A十CT⑶EPT(4)(5)IP(8)nA丁(6)(7)1(9)AVBP⑽BT⑻⑼I结果是秘谋害了经理。D十E,H十=>?1.将下列命题符号化(1)在湖南高校学习的学生，未必都是湖南籍的学生X是在湖南高校学习的学生；SU)：

X是湖南籍的学生(2)对于毎一个实数*，存在一个更人的实数yR(x)t

是实数；G(x，y):x比y大(3)存在实数_r，y和：使得与y之和人于*与z之积/(x，y)=x+y;g(x.y)=xXy3x3y3z(R(x)

AR(y)

A/?⑵

AG(/(A\y),片(x，z)))(4)某些汽车比所有的火车都慢，fri至少有一列火车比每辆汽车快C(x)：J是汽车；//(X)：

x是火车；乳r，y):x比y慢3x(C«AVy(H(y^S(x,y)))

AA^y(C(y)-SM))(5)对任何幣数0卟，且足的充耍条件/(%)：*足整数；E(x,y):x=y*G(x，y):x>yVxVy(/(x)

A/(7)—►(-<G(xty)八，G(y^)^E(xj)))(6)若m是奇数，则2m不是奇数O(x)：x足奇数；y(x，y)=xXy0(/n)0(/(2,/n)(7)那位戴眼镜的用功的大学生在看这本火而厚的巨著A(x):x是戴眼镜的是用功的9C(x):x是大学生是大的，£(水¥足厚的，FGryx是巨著，G(A\y)LT在看y，a:那位，ft:这本A{a)

AB{a)

AC(a)

AD{b)AE(h)AF(b)'G(a，b)(8)毎个自然数都有唯一的后继数/V(x)：

jc是自然数;恥):x是y的后继数Vx(N(x)^(By(N(y)AL(y^)AVz(JV(z)AL(Zrx)^E(yfz)))))(9)没有一个H然数使数］是它的后继数^3x(離)A£(1a))(10)毎个不等于I的自然数都冇唯一的一个数坫它的直接先行酋S(x.y):J是y的先行者Vx(^u)A-£Ul)^3!y(/V(y)A56^)勵

AS(y,z)

AS(^))))2.变元的约束(1)

对下列谓同公式屮的约束变元换名Vx(Pa)->(/?(x)V2U)))A训加32取z)Vv(P(v)^(/?Cv)V0(y)))A3uS(x,u)(2)对下列诮词公式中的自由变元代入(彐)，4(i，y卜VxB(xj))ABx^zC(x.y9z)(3v/4(^j)^VaB(av))

A3x\/zC(x,w\z)3.讨论在给定解释下谓词公式的真值(1)

w(p一e(x))v則D={-2,3,6},P:2>l,0(x):x<3,尺U):x>5，a:5Vx(P^Q(x))V/?(t7)«(P^Vjte(x))V/?(tz)<X^-(Q(-2)AQ(3)AQ(6)))V/f(5)ATAF))VF<z>(r-^F)VF<=>FVF<=>F(2)Vx3X/V)A0Cr，y))D:{1，2}，P(1)P(2)Q(1，1)Q(1,2)Q(2，1)Q(2,2)FTTTFF真值为F4.判断下列公式是不是永真式，并加以说明(1)(3鼎)W(尸(x)解：不是永真式，取解释如下D={1，2}尸⑴P⑵(2(1)⑽~FTFT~在该解释下3#(幻为7；

为尸，所以3W)^xQ(x)为F;而(P(l)—2(1))为八(P(2)—g(2))为r，所以W(P(-r)-QW)为门综上该公式不是永真式(2)VxVy(P(x)^Q(y))~^(3xP(x)

VyQ(y))解：是永真式。证明：法1，形式证明法2,量词作用域的收缩与扩张公式5.用形式推理证明：(1)VxP(x)VVx0(x)^Vx(P(x)V0(x))⑴]Vx(P(x)V(?W)P（假设）(2)3^(PU)V(?(x))T(1)E(3)^(P(c)VG(c))ES(2)⑷身）A，0（c）T(3)E(5卜P(c)T(4)I(6)3x^P(x)EG(5)(7)]VxP(x)T(6)E(S)VxPCr)VVxC(x)P(9)^xQ(x)T(7)(8)I(10)(2(c)US(9)(ii)-ewT(4)I(12)G(c)A-C(c)T(10)(11)1(2)Vy(G()，)—/7(y))，3xM(x)^3yG(y)=^>3x(F(x)AA/(a))^3j//0)(l)3_r(F(x)AW))P（附加）(2)3xF(x^y(G(y)^H(y))P(3)3xM(x卜3yG(y)P(4)3xF(x)A3xMWT(1)I(5)3xF(x)T(4)I(6)Vy(G(^)-W)T(2)(5)l(7)3xM(x)T(4)I(8)3>'G(y)T⑶

P)1(9)G(c)ES(8)(10)G(c)^H(c)US(6)(H)H(c)T(9)(10)I(12)3焉)EG(ll)(13)3x(FWAM(x)Wy/7WCP(3)任何人如果他喜欢步行，他就不喜欢乘汽车;每个人或者喜欢乘汽车或者喜欢骑ft行车。有的人不爱骑自行车，因此有的人不爱步行设A(x):x是人，B(x):x是喜欢步行，C(x):x喜欢乘汽车，D(x):x喜欢骑自行车Vx(A(x)一

(B(x)-^-iC(x)))，Vx(A(x)一(C(x)VD(x)))，3x(A(x)A-iD(x))=>3x(A(x)A-iB(x))⑴彐x(A(x)A-iD(x))P⑵A(a)A—iD(a))ES(1)⑶A(a)T(2)T⑷—iD(a))T(2)I⑸Vx(A(x)-(B(x)-iC(x)))P⑹A(a)(B(a)iC(a))US(5)(7)B(a)一］C(a))T(3)(6)T⑻Vx(A(x)一(C(x)VD(x)))P(9)A(a)—(C(a)VD(a)))US⑻⑽C(a)VD(a)T(3)(9)I(11)C(a)T(4)(10)I⑽—iB(a)T(7)(11)I(13)A(a)A，B(a))丁⑶⑽I(14)彐x(A(x)A-iB(x))EG(13)(4)每个大学虫不是文科生就是理工科生，存的大学生是优等生，小张不是理工科生，但他是优等生，因此如果小张是大学生，他就是文科生设A(x):x是大学生，B(x):x是文科生，C(x):x是理工科生，D(x):x是优等生，a:小张Vx(A(x)_(-iB(x)—C(x)))，彐x(A(x)AD(x))-nC(a)AD(a)A(a)-►B(a)_Vx(A(x)(，B(x)-►C(x)))，3x(A(x)AD(x))-nC(a)AD(a)=>A(a)~*B(A)(1)

A(a)P(附加前提)(2)Vx(A(x)(—iB(x)-(x)))P(3)A(a)-►(—iB(a)-►C(a))⑷-nB(a)—C(a))⑸-nC(a)AD(a)⑹-iC(a)(7)^iB(a)⑻

B(a)(9)A(a)-^B(a)US⑵T(1)(3)IPT(5)1T(4)(6)IT⑺ECP1.判断下面命题的真值(真的话证明，假的话举反例)a)如來/1EB，B^C9

则AeC

T办)如果AGS,B[C，则AcC

F举反例?U{1}B={{1}}C={{1},2}c)如果AgB，Bee,则A^C

F举反餓：{1}B={1，2}C={{1,2}}a)如果?IqB，BEC,则AoCF举反纖={1}B={1，2}C={{1,2}}2.集合计算a)0A{0}=<t>b)

{0}A{0}={0}c)-0={少，{0}}J){0,{0}}.{^}={{0}}e){040})4(0}}={0}3.在什么条件下，下面命题为真？a)(A-B)

U(A-Q=A(a-b)

u(a~c)=

(An-s)u(xn〜o=An(〜b

u〜o=An-<BACM-(3CiC)=A所以满足此式的充要条件是：AABnC=0b)(A-B)

U(A-Q=0(A-B)

U(/l-C)=A-(BnC)=^所以满足此式的充要条件是：AcBACc)(A-B)n(A-C)=0(a-b)c\(a-q=(An^BjncAn^q^n^Bn^c)=A门〜(BUO=A-(BU0=0所以满足此式的充要条件足：/laBUCd)(A-B)®(?l-O=0因为当且仅当A=B.才有A㊉所以满足此式的充驭条件是：A-B^A-C4.集合的基数是有限集合，已知L4l=3,|p(B)l=64^(/lUB)|=256,则\B\=(),L4ABI=(),IA-BI=()，L4㊉别二()解：由(p(B)|=64=26,得IBI=6由lp(AUB)l=256=28，得L4UBI=8由容斥原理得\AUB\^\AMB\-\AQB\\AOB\

=L4WB1-IAUBI=3+6-8=l，所以L4PBI=1L4-BI=L4I—14051=3-1=2\A®B\^\AUBI-IAnBI=8-l=75.集合的证明a)证明0nB)UC=An(BUQiffCo4证明；充分性已知CgA(AHB)UC=(AUO门(5UC)=AC}(B

UC)(VCo4...AUC=A)必要性己知打)uc二4n(suc)Vxec,^GC=>xe(Anfi)UC<^>xe/in(BUC)=>xFA所以Cg4幻证明(A^B)-C=(A-C)-BW:xe(A‘S)-C<=>(xE4/\x^C)/\x^B<=>x^(4-Qoxe(A-C)-B所以(/1-B)-C=(A-C)-BC)证明以下各式彼此等价：AUB=U.

-AoB,A

UB—Uo\/x(xE>1UBox

EU)«VXx£AU5)(x^U

为7)<=>Vx(x^y4<^>Vjc(x^i4—>xB)

<=>Vx(xF-A—>x<=>〜AgB同f!AUZJ=t/o・"oVxfxeAVxe/?)A)»Vx(x-B^xA)<=>〜BqA所以>4UB二Uo-AqB«^Bo4.6,幕集设AB足集合，证明以下命题成立a)p(ArB)=p(A)np(B)VS：oSoAAS^B<=>Sep(A)/\Sep(B)«Sep(A)Ap(B)h)p(A)

Up(B)op(A

UB)V5：5ep(A)Up(B)«Sep(A)V5ep(B)»5o4\/ScB=>So4U£?<=>Sep(AUB)证明：必要性：若证明〆>!)op(B)V5:Sep(A

)即5o4?A^B

人S^B

GilSep(B)二p⑷⑻充分性：若fl(A)g⑻证明AqBWx:xgA必3S，S^Af

使得xe5••'p(A)^p(B)

人由SgA即Sep(A)可得到S^p(B)也就足说人xgB人A^B综上所述：A^Biffp(A)Q9(fi)7.笛卡尔积A={O，1}B={1,2}求A2X5A2XB=[＜0,0＞，＜0,1＞，＜1，0＞，＜1，1＞}XB={«0,0〉，1＞，《0,0〉，2＞，《0,1〉，1＞,«0,1〉，2＞，«1,0＞,1＞,«I，0＞，2〉，《1，1＞，1＞,«1，】＞，2〉}注意：A2XB=(AXA)XB^AXAXB:元关系习题课(F)1.设A、B、C和D是四个非空集合，且AXCcBXD，则AcBlLCcD。(F)2.设A、B、C和D是四个集合，则AXC=BXD,iffA=B且C=D。(F)3.传递关系的对称闭包仍足传递的。(F)4.非空集合上的关系小是对称的，则必是反对称的。(T)5.非空集合上的自反关系必不是反自反的。(F)6.若R和S足二个有完令相同的二元组的集合，则称它们是相等的二元关系。(F)7,设A是*个非空巣合，则At的等价关系都不是偏序关系。(T)8,有限集上的全序关系必是良序关系、(F)9.有限集I:的偏序关系必是全序关系。(F)10.<A;R>是偏序集，则A的任何非空子集必冇极小元。(F)IL<A;R>fe偏序集，则A的非空子集B的上确界必是B的最大元。(F)12.<A:R>是伞序集，则A的任何非空子集必有唯一极小元。(F)13.<A:R>足伞序集，则A的非空子集3的F确界必足B的S小元。二、多项选择题(1,2)1.下列说法中正确的有：①任何集合都不是它自身的元素②任何集合的好集都不是空集③若AXB则AB—0)④任意两集合的辿卡尔积都小是空集(4,5)2.｛1,23,4,5｝上的关系R=｛＜1，1＞，＜1，3＞，＜2,3＞｝是①自反的②反自反的③对称的④反对称的⑤传递的(1，2,3)3.设妇｛＜1，2＞｝是A=｛1,2,3｝上的关系，则①rst(R)足等价关系②Rl0—(D③r(R)是偏序④tr(R)是良序(5)4.设R和S分别是A到B和B到C的关系，ARS=O,那么①R是空关系②S是空关系③R和S都是空关系④R和S中至少冇一个是空关系⑤以上答案都不对I2)5.若R和S是集合A上的等价关系，则下列关系屮一定是等价关系的有©RUS②Rns③R-S④R®S(1.2.4)6.若R是集合A上的等价关系，则①

R2

=R②

t(R)=R③

IacR

④

RA=R(1，2,3,4,5)7.空集上的空关系是_关系。①线印②等价③偏什④拟什⑤(2.4)8,{1，2,3,4,5}匕的全序关系一定是_关系。①等价②偏序③拟序④良序(1,4,5)9.{1,2,3A5}上的良序关系一定是①闩反的②反自反的③对称的④反对称的⑤传递的(1,2,34)10.设R和S都是A到B的关系，下列关系式中正确的有:rus-1

②(Rnsy^FHns-1③(R-SyLRi-S-1

④(R®S)4=R-1®S-11.若集合A={1，2,3,4,5}上的等价关系R={＜1，1＞，＜2,2＞，＜3，3＞，＜4,4＞，＜5，5〉，＜1，2＞，＜2,1＞，＜3,4＞，＜4,3＞},求商集A/R解：A/R={{1，2}，{3,4}，{5}}2.R为集合A={1，2,3,4,5}上的等价关系，已知商集A/R={{1，2}，{3}，{4,5}},求R解：R=IA

U{＜1，2〉，＜2，1〉，＜5,4〉，＜4,5〉}3.设A=｛3,6,9，15,54,90，135，180｝，关系。画岀＜A;I＞的Hasse—，

上、下确界。I为自然数的整除并求｛6,15,90｝的｛6,15,90｝的上确界：90下确界：3四、证明题L设R是集合A上的关系iffRdnR=lA且R=rt(R)。2-设R是集合A上的关系iff0＞且R=t(R)。证明：R是偏序关系，证明：R是拟序关系，函数习题课一、多项选择(l,2,3)h函数f:RXR—>RXR，f(<x，y>)=<x+y,x-y>足①入射②满射③双射④以上答案都不对(2)2,函数f:RXR->R，f(<x,y>)=(x+y)/2是①入射②满射③双射④以上答案都不对(1)3,设L={a,b}为字母表，则f:S*一S*