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

..资料.习题一解答或提示1.(1)设「:他是本片的编剧，Q:他是本片的导演。PaQ(2)设P:银行利率降低，。:股价上扬。PfQ(3)设P:银行利率降低，。:股价上升。〜(PfQ)(4)设「:这个对象是占据空间的,。：这个对象是有质量的水：这个对象是不断变化的5这个对象称为物质。PaQaRfS(5)设「:他今天乘火车去了，Q:他今天随旅行团去了九寨沟。PVQ(6)设P:小身体单薄，设Q:小极少生病，设R:小头脑好使。PaQaR(7)设「:这个人不识庐山真面目，设。:这个人身在庐山中。QfR(8)设「:两个三角形相似，设。:两个三角形的对应角相等或者对应边成比例。「仆。(9)设「：一个整数能被6整除，设。:这个整数能被2和3整除。PfQ设R:一个整数能被3整除，设S:这个整数的各位数字之和也能被3整除。RfS2、(1)命题T命题T/F不是命题，因为真值无法确定。命题T不是命题。命题T命题T/F不是命题，是悖论。5、(1)证：〜((〜PAQ)V(〜P八〜Q))VCPAQ)O(〜(〜PAQ)A〜(〜pa〜Q))V(PAQ)o((PV〜Q)A(PVQ))V(PAQ)o(PV(〜QVQ))V(PAQ)oPV(PAQ)oP(3)证：P-(QVR)o〜PV(QVR)o〜pvqv〜pvro(〜PVQ)V(〜PVR)o(P-Q)V(P-R)6、解：如果PVQoQVR,不能断定「0%因为当Q=T时，PVQoQVR恒成立。如果PAQoQAR,不能断定「0%因为当Q=F时，PAQoQAR恒成立。如果〜Po〜R,则PoR。8、把下列各式用T等价表示出来：＜：(PAQ)V〜pO((PTQ)MPTQ)」V(PTP)o(((PTQ)T(PTQ))T((PTQ)T(PTQ)))T((PTP)T(PTP))(3)解：(P-(QV〜R))八〜Po(〜PV(QV〜R))八〜Po((PfP)V(QV(RfR)))八(PfP)；o((PfP)v((QTQ)T((RfR)T(RfR))))A(PfP)o(((PfP)f(PfP))f(((QfQ)f((RfR)f(RfR)))t((QfQ)f((RfR)f(RfR)))))A(PfP)o((((PtP)t(PtP))t(((QtQ)t((RtR)t(RtR)))t((QtQ)t((RtR)t(RtR)))))t(PtP))t((((PtP)t(PtP))t(((QtQ)t((RtR)t(RtR)))t((QtQ)t((RtR)t(RtR)))))t(PtP))9、证：:PVQo〜〜PVQo(〜P)fQPAQo〜(〜PV〜Q)o〜(Pf〜Q)而｛〜，▽,八｝是功能完备集，，｛〜，f｝是功能完备集，〜，f不能互相表示，故｛〜，f｝是最小功能完备集。0 C又「P-Qo〜(PfQ),「.｛〜，一｝也是最小功能完备集。10、证：由书上的表1.16可知，“〜”对应的真值表含2个1和2个0,而“▽”对应的真值表也含2个1和2个0,V对应的真值表含3个1和1个0,八对应的真值表含1个1和3个0,所以，“V”无法用“〜”和“。来表示，同样“八”也无法用“〜”和“▽”来表示，因此，｛〜，V｝不是功能完备集。12.解：（1）a）真值表法PQRSQARQARfS(P-(QARfS))0000011000101100100110011011010001101010110110101011111110000111001011101001110110111100011110101111101001111111由表中看出，i)使公式仆—(QAR-S))取值1时的解释所对应的全部极小项为：(〜P八〜Q八〜R八〜S),(〜P八〜Q八〜RAS),(〜P八〜QAR八〜S),(〜P八〜QARASJ,(〜PAQ八〜R八〜S),(〜PAQ八〜RAS),(〜PAQAR八〜S),(〜PAQ八RAS),(〜QAP八〜R八〜S),(〜QAP八〜RAS),(〜QAPAR八〜S),(〜QAPARAS),(〜RAQAPA〜S),(〜RAQAPAS),(SAQARAP)，由定理1.8,其主析取式为：(〜PA〜QA〜RA〜S)V(〜PA〜QA〜RAS)V(〜PA〜QARA〜S)V(〜PA〜QARASJV(〜PAQA〜RA〜S)V(〜PAQA〜RAS)V(〜PAQARA〜S)V(〜PAQARASJV(〜QAPA〜RA〜S)V(〜QAPA〜RAS)V(〜QAPARA〜S)V(〜QAPARASJV(〜RAQAPA〜S)V(〜RAQAPAS)V(SAQARAP)。ii)使公式仆-(QAR-S))取值0时的解释所对应的全部极大项为：〜PV〜QV〜RVS由定理1.7,其主合取式为：〜PV〜QV〜RVS。■b)等价变换法P—((QfS)o〜PV(〜(QAR)VS)o〜PV〜QV〜RVS---主合取式o(〜PA(〜QVQJA(〜RVRJA(〜SVS))(〜QA(〜PVPJA(〜RVRJA(〜SVS))(〜RA(〜PVPJA(〜QVQJA(〜SVS))(SA(〜PVPJA(〜QVQJA(〜RVR))一—添加永真式o(〜PA〜QA〜RA〜S)V(〜PA〜QA〜RASJV(〜PA〜QARA〜S)V(〜PA〜QARASJV(〜PAQA〜RA〜S)V(〜PAQA〜RASJV(〜PAQARA〜s)v(〜PAQARASJV(〜QA〜PA〜RA〜S)V(〜QA〜PA〜RAS)V(〜QA〜PARA〜S)V(〜QA〜PARAS)V(〜QAPA〜RA〜S)V(〜QAPA〜RAS)V(〜QAPARA〜S)V(〜QAPARAS)V(〜RA〜QA〜PA〜S)V(〜RA〜QA〜PAS)V(〜RA〜QAPA〜S)V(〜RA〜QAPAS)V(〜RAQA〜PA〜S)V(〜RAQA〜PAS)V(〜RAQAPA〜S)V(〜RAQAPAS)V(SA〜QA〜RA〜P)V(SA〜QA〜RAP)V(SA〜QARA〜P)V(SA〜QARAP)V(SAQA〜RA〜P)V(SAQA〜RAP)V(SAQARA〜P)V(SAQARAP)……合并相同的项o(〜PA〜QA〜RA〜S)V(〜PA〜QA〜RAS)V(〜PA〜QARA〜S)V(〜PA〜QARAS)V(〜PAQA〜RA〜S)V(〜PAQA〜RAS)V(〜PAQARA〜S)V(〜PAQARAS)V(〜QAPA〜RA〜S)V(〜QAPA〜RAS)V(〜QAPARA〜S)V(〜QAPARAS)V(〜RAQAPA〜S)V(〜RAQAPAS)V(SAQARAP) 主析取式(3)等价变换法Pt0人(QtP))07Pv(RAQvP)3 ((Ra-®v(RaP))0；二PA(--QVQ)A(»RVR}) QA(~PVP))V(RAPA(^QvuP〃a~H)vPa(JavPafQaR)vPaQaR)v(Ha-^Qav(RaaP)v(RaPav(RaPaQ)UPA»QA—R)UPaQAjR)"(pPAjQAR)VPA(JAR)V(ftAAP；

V(RV(RAPAQ)主折取式Pt(R/.(Q一力)"PV(RA(-QVP))oPVR)V(T)=-puR主合取式uPVRV-^Q)A(--PVRvQ)主合取式.解：⑴二一二一二.二二・・、二二--；=I' -；='--二SP1—+Q〕n(Q-+P)oP)u①a(2QuP)(PvQ)a("~QvP)=- '<=- 不等价o)-- ---=1-2「二.等价P1—>(QaR]=“PV(Q八艮)等价.解：由题设A：A去，B：B去，C：C去，D：D去则满足条件的选派应是如下式：二一二二'"二,：'"「：构造和以上式等价的主析取式(AT(CVDJ)A-(BAC)A-(CA0)口gAv(CgD)vCAD))ABC)_ASCD；03AagB"C)ACSD1))V((C八丑D)AB8C)丸SCWD))"…久"…久2E八〜CAD)MOA吊fEA2cA2D)U(AaE人“C小D)..资料.VV(eCAD)ABUmC)ASC5D))..资料.u且2BzC)VAzezD)VhzcgC)V c2D)v(CzD2EMC)v(C2DzBgD)v(C2D2CzC)V(CZDZC2D)VCADA、EZC)u(~C7\DEA—d)M(2CAD2C2GHI"CADZ£zD]u(»且2BzC)V(fAzezD)V(»hzcgC)V(—c2D)V(CgDZ D)"(jCAD2BgC)VCADZCA--C)㈡(》A2g八fc)VgAa~B冉~D)V A小〜C)V(〜42C人2D]V(CA^-B0)VCEAD)VCA□)gDA(CC))口(。AAmB CA(DVmD；)v(0AgDA(CC))；皿A.a>Ca(FueB)a(Due口))v{=a八皿c八皿Da(B7mB))A>)v(--CBADa(Av^-A})v(wCaDa(AueA)a(B7mB))0(2AZegC八D)UAMEA-c«D)V(^AA--EACgd〕M卜AZBJ\2c2D)vAABZCA2D)V°ABC2d)v(Aa-^BaCD)vAa-^EaC D)v(Aa^BCaD)m(»A八fBy\^-CaD)v AaBa^CaD)vAaBCD)v(Aa^-BCaD)v AaBa^CaD)v(-^Aa--Ea”Ca0)0(fA2EgC△D)u5A凡》B2C2D)u(-^AA--BAC2D)70SzCzD)V[AzEAC小》D)V(Aa^BCAD)V(~A/lBCAD)V(AaBCA0)共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：(AA-^EACD);(ABA^-CAD]sAaEA--CAD]即有三种方案：A和C去或者A和口去或者8和口去。15.证：(1)由定理1.11，需证二一二一二一二,二为永真式V(P-^Q)->(p->(PaQ))=FsFUQ)U卜PV(PAQ))=zcPVQ)"(sFUP)A3FU①)=【(〜Pv①u(~PvQ)=T■■■”0=伊7弘⑪(3)由定理1.11，需证二‘.•口’二一1'为永真式PZPaR—35=F/\R―，帛0F—5=T..资料.16.证：(1)性质1由定理1.11和“一”的定义，一二是永真式，所以二=二。(2)性质2由定理1.11,二=三，三=.：，二一三和E一二是永真式，即----E是永真式，由定理1.3,二二三成立。(3)性质3由定理1.11, •、一三是永真式，又二是永真式，根据“一”的定义，B必是永真式。.证：“=” =三，二一三是永真式，A―K=vAVE=p(%B)sA=mB—nA=T"En2A“=”因为上述等价式是可逆的，当',三=',二，必有二=三。.解：设「：珍宝藏在东厢房。：藏宝的房子靠近池塘入房子的前院栽有大柏树5：珍宝藏在花园正中地下「后院栽有香樟树乂：珍宝藏在附近(后院)对语句符号化以后得到以下蕴涵式：二一一‘,二，R――二，-- ：，，T—；=?(QP)/V(R-P)AQA(RVS)A(TM)=QA(Q P)A(RvS)A(T-M)（附加前提规则）（附加前提规则）PT®②PT@E2ST@⑤CP规则①⑥="PA(RTP]八(RV£)A(TTM)[P八(pP―>2R)A(艮VS)A仃一>="Ra(RvS)a(T一M)—M)所以5为真，即珍宝藏在花园正中地下。19．解：(1)不成立(P=0，Q=1)不成立(P=1，Q=R=0)不成立(P=0，Q=1)不成立(P=0，Q=1，R=0)不成立(P=1，