左孝凌離散數(shù)學(xué)課后題答案

1-1，1-2PQ（1）解：f)P：語法錯誤。Q：程序錯誤。R：（P∨Q）→Ra)是命題，真值為T。(6)解：b)不是命題。a)P:天氣炎熱。Q:正在下雨。 P∧Qc)是命題，真值要根據(jù)具體情況確定。b)P:天氣炎熱。R:濕度較低。 P∧Rd)不是命題。c)R:天正在下雨。S:濕度很高。R∨Se)是命題，真值為T。d)A:劉英上ft。B:李進上ft。 A∧Bf)是命題，真值為T。e)M:老王是革新者。N:小李是革新者。M∨Ng)是命題，真值為F。f)L:你看電影。M:我看電影。┓L→┓Mh)不是命題。g)P:我不看電視。Q:我不外出。R:我在睡覺。 P∧Q∧Ri)不是命題。h) P:Q:P∧Q解：原子命題：我愛北京天安門。復(fù)合命題：如果不是練健美操，我就出外旅游拉。解：(┓P∧R)→QQ→R┓PP→┓Q解：Q:我將去參加舞會。R:我有時間。P:天下雨。Q(R∧┓P):b)R:我在看電視。Q:我在吃蘋果。R∧Q:我在看電視邊吃蘋果。c)設(shè)Q:一個數(shù)是奇數(shù)。R:一個數(shù)不能被2除。（Q→R）∧(R→Q):22解：P：王強身體很好。Q：王強成績很好。P∧QP：小李看書。Q：小李聽音樂。P∧QP：氣候很好。Q：氣候很熱。P∨QP：abQ：a+bP→QABCDQABCD

1-3解：（作為合式公式）是合式公式不是合式公式（括弧不配對）不是合式公式（RS）是合式公式。解：a）A，(A∨B)是合式公式，(A→(A∨B))這個過程可以簡記為：A；(A∨B)；(A→(A∨B))同理可記b）A；┓A；(┓A∧B)；((┓A∧B)∧A)c）A；┓A；B；(┓A→B)；(B→A)；((┓A→B)→(B→A))d）A；B；(A→B)；(B→A)；((A→B)∨(B→A))解：a）((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C))b）((B→A)∨(A→B))。解：c)c)QP,(P→P)Q.a)a)中用P→(Q→P)Q.b)RP,SQ,QR,P代換S.解：P:你沒有給我寫信。R:信在途中丟失了。P QP:Q:李四不去。R:他就去。(P∧Q)→RP:Q:P∧Q)P:Q:他唱歌。R:你伴奏。P→(QR)解：P:它占據(jù)空間。Q:它有質(zhì)量。R:它不斷變化。S:這個人起初主張：(P∧Q∧R)S后來主張：(P∧QS)∧(S→R)這個人開頭主張與后來主張的不同點在于：后來認(rèn)為有P∧Q必同時有R，開頭時沒有這樣的主張。解：P:Q:我去看電影。R:我在家里讀書。S:看報。(┓P→Q)∧(P→(R∨S))P:Q:天下雨。┓Q→PP:Q:我留下。Q→P1-4（4）解：a)PQRQ∧RP∧(Q∧R)P∧Q(P∧Q)∧RTTTTTTTTTFFFTFTFTFFFFTFFFFFFFTTTFFFFTFFFFFFFTFFFFFFFFFFF所以，P∧(Q∧R)(P∧Q)∧Rb)

TTTＴＴＴＴTTFＴＴＴＴTFTＴＴＴＴTFFＦＴＴＴFTTＴＴＴＴFTFＴＴＴＴFFTＴＴＦＴFFFＦＦＦＦ所以，P∨(Q∨R)(P∨Q)∨Rｃ）PQRQ∨RP∨(Q∨R)P∨Q(P∨Q)∨RＰＱＱ∨ＲＰ（Ｑ∨ＲＰ∧ＱＰ∧ＲPQRQ∨RP∨(Q∨R)P∨Q(P∨Q)∨RＴＴＴＦＴＦ Ｔ Ｔ Ｔ Ｔ ＴＴＴＴＴＦＴＴＦＴＴＦＴＴＦＦＦＦＦＦＦＴＴＦＦＦＦＴＴＦＦＦＦＦＴＴＦＦＦＦＦＦＦＦＦＦＦＦＴＦＦＦPTQ┓P┓Q┓P∨┓Q┓(P∧Q)┓P∧┓Q┓(P∨Q)PTQ┓P┓Q┓P∨┓Q┓(P∧Q)┓P∧┓Q┓(P∨Q)TFFFFFFTFFTFFTTTFFa)A→(B→A)┐A∨(┐B∨FTTFTTFFA∨(┐A∨┐B)FFTTTTTTA∨(A→┐B)所以，┓(P∧Q)┓P∨┓Q, ┓(P∨Q)┓P∧┓Q16（5）F～F16PQRF1F2F3F4F5F6TTTTFTTFFTTFFFTFFFTFTTFFTTFTFFFTFTTFFTTTFFTTFFTFTFFFTFFFTTFTTTFFFFFTFTTTF1:(Q→P)→RF2:(P∧┓Q∧┓R)∨(┓P∧┓Q∧┓R)F3:(P←→Q)∧(Q∨R)F4:(┓P∨┓Q∨R)∧(P∨┓Q∨R)F5:(┓P∨┓Q∨R)∧(┓P∨┓Q∨┓R)F6:┓(P∨Q∨R)PQPQ123456789 10111213141516FFFTFTFTFTFTFTFTFTFTFFTTFFTTFFTTFFTTTFFFFFTTTTFFFFTTTTTTFFFFFFFFTTTTTTTT解：由上表可得有關(guān)公式為1.F 2.┓(P∨Q) 3.┓(Q→P) 4.┓P5.┓(P→Q) 6.┓Q 7.┓(PQ) 8.┓(P∧Q)9.P∧Q 10.PQ 11.Q 12.P→Q13.P 14.Q→P 15.P∨Q 16.T證明：

┐A→(A→┐B)b)┐(AB)┐((A∧B)∨(┐A∧┐B))┐((A∧B)∨┐(A∨B))(A∨B)∧┐(A∧B)或┐(AB)┐((A→B)∧(B→A))┐((┐A∨B)∧(┐B∨A))┐((┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A))┐((┐A∧┐B)∨(B∧A))┐(┐(A∨B))∨(A∧B)(A∨B)∧┐(A∧B)c)┐(A→B)┐(┐A∨B) A∧┐Bd)┐(AB)┐((A→B)∧(B→A))┐((┐A∨B)∧(┐B∨A))(A∧┐B)∨(┐A∧B)e)(((A∧B∧C)→D)∧(C→(A∨B∨D)))(┐(A∧B∧C)∨D)∧(┐C∨(A∨B∨D))(┐(A∧B∧C)∨D)∧(┐(┐A∧┐B∧C)∨D)(┐(A∧B∧C)∧┐(┐A∧┐B∧C))∨D((A∧B∧C)∨(┐A∧┐B∧C))→D(((A∧B)∨(┐A∧┐B))∧C)→D((C∧(AB))→D)f)A→(B∨C) ┐A∨(B∨C)(┐A∨B)∨C┐(A∧┐B)∨C (A∧┐B)→Cg)(A→D)∧(B→D)(┐A∨D)∧(┐B∨D)(┐A∧┐B)∨D┐(A∨B)∨D(A∨B)→Dh)((A∧B)→C)∧(B→(D∨C))(┐(A∧B)∨C)∧(┐B∨(D∨C))(┐(A∧B)∧(┐B∨D))∨C(┐(A∧B)∧┐(┐D∧B))∨C┐((A∧B)∨(┐D∧B))∨C((A∨┐D)∧B)→C(B∧(D→A))→Cc)P∨(┐P∨Q)(P∨┐P)∨QT∨QT((P→Q)∧(Q→R))→(P→R)因為(P→Q)∧(Q→R)(P→R)（8）解：所以(P→Q)∧(Q→R)為重言式。a)((A→B)(┐B→┐A))∧C((┐A∨B)(B∨┐A))∧C((┐A∨B)(┐A∨B))∧CT∧CCb)A∨(┐A∨(B∧┐B))(A∨┐A)∨(B∧┐B)c)(A∧B∧C)∨(┐A∧B∧C)(A∨┐A)∧(B∧C)T∧(B∧C)T∨FTd)（2）((a∧b)∨(b∧c)∨(c∧a))(a∨b)∧(b∨c)∧(c∨a)因為((a∧b)∨(b∧c)∨(c∧a))((a∨c)∧b)∨(c∧a)((a∨c)∨(c∧a))∧(b∨(c∧a))(a∨c)∧(b∨c)∧(b∨a)所以((a∧b)∨(b∧c)∨(c∧a))(a∨b)∧(b∨c)∧(c∨a)為重言式。證明：B∧C解：1）CT，AT，BF，A∨CB∨C，AB不成立。設(shè)CF，則滿足A∧CB∧C，但AB成立。由題意知┐A┐BAB習(xí)題1-5證明：a)(P∧(P→Q))→Q(P∧(┐P∨Q))→Q(P∧┐P)∨(P∧Q)→Q(P∧Q)→Q┐(P∧Q)∨Q┐P∨┐Q∨Q┐P∨TTb) ┐P→(P→Q)

a)(P→Q)P→(P∧Q)解法1：P→QTPT，QT，P∧QT，P→(P∧Q)TPF，QF，P∧QF，P→(P∧Q)T命題得證解法2：P→(P∧Q)FPT，(P∧Q)FPT，QFP→QF3：(P→Q)→(P→(P∧Q))┐(┐P∨Q)∨(┐P∨(P∧Q))┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q))T所以(P→Q)P→(P∧Q)b)(P→Q)→QP∨QP∨QF，PF，QP→QT，(P→Q)→QF，所以(P→Q)→QP∨Q。c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→QR→QF，RT，QF，P∧┐PF所以Q→(P∧┐P)為T，R→(P∧┐P)為FR→(R→(P∧┐P))F，所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))為F即(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q成立。解：P→Q8a)Q→P8a)的反換式┐P→┐Q8a)的逆反式┐Q→┐P8解：如果天下雨，我不去。設(shè)P：天下雨。Q：我不去。P→QQ→P僅當(dāng)你走我將留下。S：你走了。R：我將留下。R→S逆換式S→R表示命題：如果你走了則我將留下。逆反式┐S→┐R表示命題：如果你不走，則我不留下。如果我不能獲得更多幫助，我不能完成個任務(wù)。設(shè)E：我不能獲得更多幫助。H：我不能完成這個任務(wù)。E→HH→E助。逆反式┐H→┐E表示命題：我完成這個任務(wù)，則我能獲得更多幫助PQ，QP1：本題要求證明(PQ)∧QP,設(shè)(PQ)∧QT，則(PQ)T，QT，故由P為T。

所以(PQ)∧QP解法2：由體題可知，即證((PQ)∧Q)→P是永真式。((PQ)∧Q)→P(((P∧Q)∨(┐P∧┐Q))∧Q)→P(((┐P∨┐Q)∧(P∨Q))∨┐Q)∨P((┐Q∨┐P∨┐Q)∧(┐Q∨P∨Q))∨P((┐Q∨┐P)∧T)∨P┐Q∨┐P∨P┐Q∨TT解：P：我學(xué)習(xí) Q：我數(shù)學(xué)不及格 R：我熱衷于玩撲克如果我學(xué)習(xí)，那么我數(shù)學(xué)不會不及格： P→┐Q如果我不熱衷于玩撲克，那么我將學(xué)習(xí): 但我數(shù)學(xué)不及格: Q因此我熱衷于玩撲克。 R號化為：(P→┐Q)∧(┐R→P)∧QR證：證法1：((P→┐Q)∧(┐R→P)∧Q)→R┐((┐P∨┐Q)∧(R∨P)∧Q)∨R(P∧Q)∨(┐R∧┐P)∨┐Q∨R((┐Q∨P)∧(┐Q∨Q))∨((R∨┐R)∧(R∨┐P))┐Q∨P∨R∨┐PT所以，論證有效。2：設(shè)(P→┐Q)∧(┐R→P)∧QT，QT，(P→┐Q)T，P由(┐R→P)T，RT。故本題論證有效。解：P：6是偶數(shù) Q：7被2除盡 R：5是素數(shù)672P→┐Qf)(A∧B)→C，┐D，┐C∨D┐A∨┐B572┐R∨Q設(shè)(A∧B)→C，┐D，┐C∨DT，則┐DT，┐C∨DT，C5是素數(shù)所以6是奇數(shù)R┐P為F又(A∧B)→CT，A∧BF，所以┐A∨┐BT。命題得證。（P→┐Q）∧（┐R∨Q）∧R證：證法1：((P→┐Q)∧(┐R∨Q)∧R)→┐P┐((┐P∨┐Q)∧(┐R∨Q)∧R)∨┐P((P∧Q)∨(R∧┐Q)∨┐R)∨┐P((┐P∨P)∧(┐P∨Q))∨((┐R∨R)∧(┐R∨┐Q))(┐P∨Q)∨(┐R∨┐Q)T2：(P→┐Q)∧(┐R∨Q)∧RT，RT，且┐R∨QT，QP→┐QT，得到┐PT。證明：P(┐P→Q)PT，則┐PF，故┐P→QT┐A∧B∧CC假定┐A∧B∧CT，CT。CA∨B∨┐B因為A∨B∨┐B為永真，所以CA∨B∨┐B成立。d)┐(A∧B)┐A∨┐B設(shè)┐(A∧B)T，A∧BF。AT，BF，則┐AF，┐BT，故┐A∨┐BTAF，BT，則┐AT，┐BF，故┐A∨┐BTAF，BF，則┐AT，┐BT，故┐A∨┐BT命題得證。e)┐A→(B∨C)，D∨E，(D∨E)→┐AB∨C設(shè)┐A→(B∨C)，D∨E，(D∨E)→┐A為T，D∨ET，(D∨E)→┐AT，所以┐A又┐A→(B∨C)T，B∨CT。命題得證。

解：如果他有勇氣，他將得勝。P：他有勇氣 Q：他將得勝原命題：P→Q 逆反式：┐Q→┐P表示：如果他失敗了說明他沒勇氣。僅當(dāng)他不累他將得勝。P：他不累 Q：他得勝原命題：Q→P 逆反式：┐P→┐Q表示：如果他累，他失敗。習(xí)題1-6(1)解：a)(P∧Q)∧┐P(P∧┐P)∧Q┐(T∨Q)b)(P→(Q∨┐R))∧┐P∧Q(┐P∨(Q∨┐R))∧┐P∧Q(┐P∧┓P∧Q)∨(Q∧┓P∧Q)∨(┓R∧┓P∧Q)(┓P∧Q)∨(┓P∧Q)∨(┓P∧┓R∧Q)┓P∧Q┐(P∨┐Q)c)┐P∧┐Q∧(┐R→P)┐P∧┐Q∧(R∨P)(┐P∧┐Q∧R)∨(┐P∧┐Q∧P)(┐P∧┐Q∧R)∨F┐P∧┐Q∧R┐(P∨Q∨┐R)解：┐PP↓Pb)P∨Q┐(P↓Q)(P↓Q)↓(P↓Q)c)P∧Q┐P↓┐Q(P↓P)↓(Q↓Q)解：P→(┐P→Q)┐P∨(P∨Q)T┐P∨P(┐P↑┐P)↑(P↑P)P↑(P↑P)P→(┐P→Q)┐P∨(P∨Q)T┐P∨P┐(┐P↓P)┐((P↓P)↓P)((P↓P)↓P)↓((P↓P)↓P)(4)解：P↑Q┐(┐P↓┐Q)┐((P↓P)↓(Q↓Q))((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q))證明：┐(B↑C)┐(┐B∨┐C)┐B↓┐C┐(B↓C)┐(┐B∧┐C)┐B↑┐C解：聯(lián)結(jié)詞“↑”和“↓”不滿足結(jié)合律。舉例如下：F，P↑Q)↑RR)F故(P↑Q)↑R P↑(Q↑R).給出一組指派：PT，QF，RF，則(P↓Q)↓RT，P↓(Q↓R)為F

故(P↓Q)↓R (7)證明：PP，QQ，QP。但PQQP，PPQQ，故實際有：P，Q，┐P，┐Q，PQ，PP（T） （A）用┐作用于（A）類，得到擴大的公式類（包括原公式類：P，Q，┐P，┐Q，┐（PQ，T，F(xiàn)， PQ （B）用作用于（A）類，得到：PQP┐PFP┐Q┐PQP（PQQP（P）P，Q┐P┐（PQ，Q┐QF，Q（PQ）P，QTQ,┐P┐QPQ，┐P（PQ）┐Q，┐PT┐P,┐Q（PQ）┐P，┐QT┐Q,（PQ）（PQ）PQ.（A）類使用運算后，仍在（B）對（B）類使用┐運算得：┐P，┐Q，P，Q， PQ，F(xiàn)，T，┐（PQ，仍在（B）類中。對（B）類使用運算得：PQP┐PFP┐QPQP（PQ┐QPTP，PF┐P，P（PQ）Q，Q┐P（PQQ┐QFQ（PQ┐PQTQ,QF┐Q，Q（PQ）P，┐P┐QPQ，┐P┐（PQ）Q，┐PT┐P,┐PFP,┐P（PQ）┐Q，┐Q┐（PQ）P，┐QT┐Q,┐QT┐Q,┐Q（PQ）┐P，（PQT（PQ（PQFPQ（PQ（PQ）FTFF，T（PQ）F（PQ）┐（PQ）（P（PQ）（PQ）PQ.故由（B）類使用運算后，結(jié)果仍在（B）中。由上證明：用,┐兩個連結(jié)詞，反復(fù)作用在兩個變元的公式中，結(jié)果只(2)a)解：(┐P∧Q)→R┐(┐P∧Q)∨R能產(chǎn)生（B）類中的公式，總共僅八個不同的公式，故{,┐}不是功能P∨┐Q∨R完備的，更不能是最小聯(lián)結(jié)詞組∨(P∧Q)∨(P∧┐Q)∨(┐Q∧R)∨(┐Q∧┐R)∨(R∧P)∨(R∧┐P已證{,┐不是最小聯(lián)結(jié)詞組，又因為P Q┐PQ，故任何)命題式中的聯(lián)結(jié)詞如僅用{ ,┐}表達必可用{,┐}表達，b)P→((Q∧R)→S)其逆亦真。故{ ,┐}也必不是最小聯(lián)結(jié)詞組。┐P∨(┐(Q∧R)∨S)(8)證明{∨}，{∧}和{→}不是最小聯(lián)結(jié)詞組。┐P∨┐Q∨┐R∨S證明：若{∨}，{∧}和{→}是最小聯(lián)結(jié)詞，則(┐P∧Q)∨(┐P∧┐Q)∨(┐Q∧R)∨(┐Q∧┐R)∨(┐R∧S)∨(┐P（P∨P∨??）┐R∧┐S)∨(S∧P)∨(S∧┐P)┐P（P∧P∧??）c)┐(P∨┐Q)∧(S→T)┐PP→(P→(P→??)(┐P∧Q)∧(┐S∨T)對所有命題變元指派T，則等價式左邊為F，右邊為T，與等價表達式矛(┐P∧Q∧┐S)∨(┐P∧Q∧T)盾。d)(P→Q)→R所以{∨}，{∧}和{→}不是最小聯(lián)結(jié)詞。┐(┐P∨Q)∨R(9)證明{┐,→}}是最小聯(lián)結(jié)詞組。(P∧┐Q)∨R證明：因為{┐,∨}為最小聯(lián)結(jié)詞組，且P∨Q┐P→Q(P∨R)∧(┐Q∨R)所以{┐,→}是功能完備的聯(lián)結(jié)詞組，又{┐},{→}都不是功能完備的聯(lián)e)┐(P∧Q)∧(P∨Q)結(jié)詞組。(┐P∨┐Q)∧(P∨Q)所以{┐,→}是最小聯(lián)結(jié)詞組。(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q)又因為P→┐(P Q)c所以{┐, }是功能完備聯(lián)結(jié)詞組，又(┐P∧Q)∨(┐Q∧P){┐},{ }不是功能完備的聯(lián)結(jié)詞組，(3)解：所以}是最小聯(lián)結(jié)詞組。a)P∨(┐P∧Q∧R)(P∨┐P)∧(P∨Q)∧(P∨R)習(xí)題1-7(P∨Q)∧(P∨R)(1)解：b)┐(P→Q)∨(P∨Q)P∧(P→Q)┐(┐P∨Q)∨(P∨Q)P∧(┐P∨Q)(P∧┐Q)∨(P∨Q)(P∧┐P)∨(P∧Q)(P∨P∨Q)∧(┐Q∨P∨Q)P∧(P→Q)c)┐(P→Q)(P∨(┐Q∧Q))∧(┐P∨Q)┐(┐P∨Q)(P∨┐Q)∧(P∨Q)∧(┐P∨Q)P∧┐Q→→ → →→(P∨Q)∧(P∨┐Q)∧(┐Q∨┐P)(P→Q)→R┐(┐P∨Q)∨R(P∧┐Q)∨R

P→(P∧(Q→P)┐P∨(P∧(┐Q∨P)(┐P∨P)∧(┐P∨┐Q∨P)T∨(T∧┐Q)T(P∨R)∧(┐Q∨R)e)(┐P∧Q)∨(P∧┐Q)(┐P∨P)∧(┐P∨┐Q)∧(Q∨P)∧(Q∨┐Q)(┐P∨┐Q)∧(Q∨P)

=(┐P∧┐Q)∨(┐P∧Q)∨(P∧┐Q)∨(P∧Q)0,1,2,3f) (Q→P)∧(┐P∧Q)(┐Q∨P)∧┐P∧Q(┐Q∨P)∧┐(P∨┐Q)F(4)

解：a)(┐P∨┐Q)→(P┐Q)┐(┐P∨┐Q)∨(P┐Q)

(5)

證明：a)

=(P∨Q)∧(P∨┐Q)∧(┐P∨Q)∧(┐P∨┐Q)0,1，2，3(P∧Q)∨(P∧┐Q)∨(┐P∧Q) P∨Q=0b)Q∧(P∨┐Q)(P∧Q)∨(Q∧┐Q)3P∧Q=30，1，2(P∨Q)∧(P∨┐Q)∧(┐P∨Q)c) P∨(┐P→(Q∨(┐Q→R))P∨(P∨(Q∨(Q∨R))0P∨Q∨R=01，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)d) (P→(Q∧R))∧(┐P→(┐Q∧┐R))(┐P∨(Q∧R))∧(P∨(┐Q∧┐R))(P∧┐P)∨(P∧(Q∧R))∨((┐Q∧┐R)∧┐P)∨((┐Q∧┐R)∧(Q∧R))(P∧Q∧R)∨(┐P∧┐Q∧┐R)=0,71，2，3,4,5,6(P∨Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R)∧(┐P∨Q∨R)∧(┐P∨Q∨┐R)∧(┐P∨┐Q∨R)

(A→B)∧(A→C)(┐A∨B)∧(┐A∨C)A→(B∧C)┐A∨(B∧C)(┐A∨B)∧(┐A∨C)b)(A→B)→(A∧B)┐(┐A∨B)∨(A∧B)(A∧┐B)∨(A∧B)A∧(B∨┐B)A∧TA(┐A→B)∧(B→A)(A∨B)∧(┐B∨A)A∨(B∧┐B)A∨FAc)A∧B∧(┐A∨┐B)((A∧┐A)∨(A∧┐B))∧BA∧B∧┐BF┐A∧┐B∧(A∨B)((┐A∧A)∨(┐A∧B))∧┐B┐A∧┐B∧BFd)A∨(A→(A∧B)A∨┐A∨(A∧B)T┐A∨┐B∨(A∧B)┐(A∧B)∨(A∧B)T(6)解：AR↑(Q∧┐(R↓P)),A*R↓(Q∨┐(R↑P))AR↑(Q∧┐(R↓P))┐(R∧(Q∧(R∨P)))┐R∨┐Q∨┐(R∨P)┐(R∧Q)∨┐(R∨P)A*R↓(Q∨┐(R↑P))┐(R∨(Q∨(R∧P))┐R∧┐Q∧┐(R∧P)┐(R∨Q)∧┐(R∧P)解：設(shè)A：A去出差。B：B去出差。C：C去出差。D：D去出差若A去則C和D中要去一個。 A→(CVD)B和C不能都去。 ┐(B∧C)C去則D要留下。 C→┐D按題意應(yīng)有：A→(CVD)，┐(B∧C)，C→┐DCVD(C∧┐D)∨(D∧┐C)故(A→(CVD))∧┐(B∧C)∧(C→┐D)(┐A∨(C∧┐D)∨(D∧┐C))∧┐(B∧C)∧(┐C∨┐D)(┐A∨(C∧┐D)∨(D∧┐C))∧(┐B∨┐C)∧(┐C∨┐D)

(┐A∨(C∧┐D)∨(D∧┐C))∧((┐B∧┐C)∨(┐B∧┐D)∨(┐C∧┐D)∨┐C)(┐A∧┐B∧┐C)∨(┐A∧┐B∧┐D)∨(┐A∧┐C∧┐D)∨(┐A∧┐C)∨(┐B∧┐C∧D)∨(┐C∧D∧┐B∧┐D)∨(┐C∧D∧┐C∧┐D)∨(┐C∧D∧┐C)∨(┐D∧C∧┐B∧┐C)∨(┐D∧C∧┐B∧┐D)∨(┐D∧C∧┐C∧┐D)∨(┐D∧C∧┐C)在上述的析取范式中，有些（畫線的）不符合題意，舍棄，得(┐A∧┐C)∨(┐B∧┐C∧D)∨（┐C∧D）∨(┐D∧C∧┐B)故分派的方法為：B∧D,或D∧A,或C∧A。P：AQ：BR：CS：DE：A是第二。由題意得(PVQ)∧(RVS)∧(EVS)((P∧┐Q)∨(┐P∧Q))∧((R∧┐S)∨(┐R∧S))∧((E∧┐S)∨(┐E∧S))((P∧┐Q∧R∧┐S)∨(P∧┐Q∧┐R∧S)∨(┐P∧Q∧R∧┐S)∨(┐P∧Q∧┐R∧S))∧((E∧┐S)∨(┐E∧S))因為 (P∧┐Q∧┐R∧S)與(┐P∧Q∧R∧┐S)不合題意，所以原可化為((P∧┐Q∧R∧┐S)∨(┐P∧Q∧┐R∧S))∧((E∧┐S)∨(┐E∧S))(P∧┐Q∧R∧┐S∧E∧┐S)∨(P∧┐Q∧R∧┐S∧┐E∧S)∨(┐P∧Q∧┐R∧S∧E∧┐S)∨(┐P∧Q∧┐R∧S∧┐E∧S)(P∧┐Q∧R∧┐S∧E)RE┐P∧Q∧┐R∧S∧┐E即A不是第一，B是第二，C不是第二，D為第四，A不是第二于是得：A是第三 B是第二 C是第一 D是第四。習(xí)題1-8(1)證明：a)┐(P∧┐Q)，┐Q∨R，┐R┐P┐R P┐Q∨R P(3)┐Q (1)(2)T,I(4)┐(P∧┐Q) P(5)┐P∨Q (4)T,E(6)┐P (3)(5)T,Ib)J→(M∨N)，(H∨G)→J，H∨GM∨N(H∨G)→J P(H∨G) P(3)J (1)(2)T,I(4)J→(M∨N) P(5)M∨N (3)(4)T,Ic)B∧C，(BC)→(H∨G) G∨HB∧C P(2)B (1)T,I(3)C (1)T,I(4)B∨┐C (2)T,I(5)C∨┐B (3)T,I(6)C→B (4)T,E(7)B→C (5)T,E(8)BC (6)(7)T,E(9)(BC)→(H∨G) P(10)H∨G (8)(9)T,I

┐A∨B，C→┐BA→┐C(1)┐(A→┐C)P(2)A(1)T,I(3)C(1)T,I(4)┐A∨BP(5)B(2)(4)T,I(6)C→┐BP(7)┐B(3)(6)T,I(8)B∧┐B矛盾。(5),(7)b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E) (1)┐(A→(B→F)) P(2)A (1)T,I(3)┐(B→F) (1)T,I(4)B (3)T,I(5)┐F (3)T,(6)A→(B→C) P(7)B→C (2)(6)T,I(8)C (4)(7)T,I(9)┐F→(D∧┐E) P(10)D∧┐E (5)(9)T,I(11)D (10)T,I(12)C∧D (8)(11)T,I)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S) ┐S (13)(C∧D)→E P)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S) ┐S (13)(C∧D)→E P(1)(┐Q∨R)∧┐R(14)E(12)(13)T,I(2)┐Q∨R(1)T,I(15)┐E(10)T,I(3)┐R(1)T,I(16)E∧┐E矛盾。(14),(15)(4)┐Q(2)(3)T,Ic)A∨B→C∧D，D∨E→FA→F(5)P→QP(1)┐(A→F)P(6)┐P(4)(5)T,I(2)A(1)T,I(7)┐(┐P∧┐S)P(3)┐F(1)T,I(8)P∨┐S(7)T,E(4)A∨B(2)T,I(9)┐S(6)(8)T,I(5)(A∨B)→C∧DP(2)證明：(6)C∧D(4)(5)T,I(7)C (6)T,I(8)D (6)T,I(9)D∨E (8)T,I(10)D∨E→F P(11)F (9)(10)T,I(12)F∧┐F 矛盾。(3),(11)d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E) B→E(1)┐(B→E) P(2)B (1)T,I(3)┐E (1)T,I(4)┐B∨D P

(17)┐A∨┐A (16)T,E(18)┐A (17)T,E證明：┐A∨B，C→┐BA→┐CA P┐A∨B P(3)B (1)(2)T,I(4)C→┐B P(5)┐C (3)(4)T,I(6)A→┐C CPb)A→(B→C)，(C∧D)→E，┐F→(D∧┐E) A→(B→F)(5)D(2)(4)T,I(1)AP(6)(E→┐F)→┐DP(2)A→(B→C)P(7)┐(E→┐F) (5)(6)T,I(8)E (7)T,I(9)E∧┐E 矛盾e)(A→B)∧(C→D)，(B→E)∧(D→F)，┐(E∧F)，A→C┐A

(3)B→C (1)(2)T,IB P(5)C (3)(4)T,I(6)(C∧D)→E P(1)(A→B)∧(C→D)P(7)C→(D→E)(6)T,E(2)A→B(1)T,I(8)D→E(5)(7)T,I(3)(B→E)∧(D→F)P(9)┐D∨E(8)T,E(4)B→E(3)T,I(10)┐(D∧┐E)(9)T,E(5)A→E(2)(4)T,I(11)┐F→(D∧┐E)P(6)┐(E∧F)P(12)F(10)(11)T,I(7)┐E∨┐F(6)T,E(13)B→FCP(8)E→┐F(7)T,E(14)A→(B→F)CP(9)A→┐F (5)(8)T,I c)A∨B→C∧D，D∨E→FA→F(10)C→D(1)T,I(1)AP(11)D→F(3)T,I(2)A∨B(1)T,I(12)C→F(10)(10)T,I(3)A∨B→C∨DP(13)A→CP(4)C∧D(2)(3)T,I(14)A→F(13)(12)T,I(5)D(4)T,I(15)┐F→┐A(14)T,E(6)D∨E(5)T,I(16)A→┐A(9)(15)T,I(7)D∨E→FP(8)F (6)(7)T,I(4)┐P→Q (3)T,I(9)A→F CPd)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)B→E(5)Q (1)(4)T,I(6)S→┐Q P(1)B P(附加前提)(7)┐S (5)(6)T,I(2)┐B∨D P(8)S∨R P(3)D (1)(2)T,I(9)R (7)(8)T,I(4)(E→┐F)→┐D P(10)┐R P(5)┐(E→┐F) (3)(4)T,I(6)E (5)T,I(11)┐R∧R 矛盾（9（10）T，Ic)┐(P→Q)→┐(R∨S)，((Q→P)∨┐R)，RPQ(7)B→E CP(1)R P證明：R→┐Q，R∨S，S→┐Q，P→Q┐P(2)(Q→P)∨┐R P(3)Q→P (1)(2)T,I(1)R→┐Q P(4)┐(P→Q)→┐(R∨S) P(2)R∨SP(5)(R∨S)→(P→Q)(4)T,E(3)S→┐QP(6)R∨S(1)T,I(4)┐Q(1)(2)(3)T,I(7)P→Q(5)(6)(5)P→QP(8)(P→Q)∧(Q→P)(3)(7)T,I(6)┐P(4)(5)T,I(9)PQ(8)T,ES→┐Q，S∨R，┐R，┐PQP證法一：S∨R P┐R P(3)S (1)(2)T,IS→┐Q P(5)┐Q (3)(4)T,I(6)┐PQ P(7)(┐P→Q)∧(Q→┐P) (8)┐P→Q (7)T,I(9)P (5)(8)T,I（反證法）┐P P（附加前提）┐PQ P(3)（┐P→Q）∧（Q→┐P）(2)T，E

解：P：我跑步。Q：前提為：P→Q，┐QP→Q P┐Q P(3)┐P (1)(2)T,I結(jié)論為：┐P，我沒有跑步。S：他犯了錯誤。R：前提為：S→R，R因為（S→R）∧R（┐S∨R）∧RRS→R，RS，S有效結(jié)論。P：我的程序通過。Q：我很快樂。R：陽光很好。 S：天很暖和（把晚上十一點理解為陽光好）前提為：P→Q，Q→R，┐R∧S c)設(shè)J(x)：x是教練員。O(x)：x是年老的。V（x：x是健壯的。(1)P→QP則有 （x（J（x）O（x）V（x）(2)Q→RPd)O(x)：xV（x：xj：金教練(3)P→R(1)(2)T,I則有 ?O（j）?V（j）(4)┐R∨SPe)設(shè)L(x)：x是運動員。J(x)：x是教練員。(5)┐R(4)T,I則 ?（x（L（x）J（x）(6)┐P(3)(5)T,I本題亦可理解為：某些運動員不是教練。結(jié)論為：┐P，我的程序沒有通過習(xí)題2-1,2-2解：Wx：xc：則有?W（c）設(shè)Sx：x是田徑運動員。B（x：x是球類運動員。h：則有 S（h）B（h）Cx：xB（x：xl：C（l）B（l）d）設(shè)Ox：x是奇數(shù)。則有 Om）?O（2mRx：xQ（x：x則有x（Q（x）R（x）Rx：xQ（x：x則有x（R（x）Q（x）Rx：xQ（x：x則有?x（R（x）Q（x）設(shè)Px，y：直線x平行于直線G（x，：直線x相交于直線y。則有 P（A，B）?G（A，B）解：J(x)：xL(x)：x則有（x（J（x）L（x）S(x)：xL(x)：x則有（x（L（x）S（x）

故（x（L（x）?J（x）（xx（xx（xx手。則有（x（S（x）L（x）C（x）C（x：xV（x：x則有 （x（C（x）V（x）或?（xC（x）?V（x）（xx（xx（xx則有（x（O（x）C（x）L（x）（xx（xx（xx選手。則有?（x（W（x）C（x）H（x）j）W（x：xJ（x：xC（x：x則有（x（W（x）J（x）C（x）k）L（x：x是運動員。J（y：y是教練。A(x,y)：x欽佩y則有 （x（L（x）（y（J（y）A（x，y））l）（xx（xx是運動員。A(x,y)xy則（x（S（x）（y（L（y）?A(x,y)）習(xí)題2-3（1）解：a）5是質(zhì)數(shù)。b）2是偶數(shù)且2是質(zhì)數(shù)。x，若x2x是偶數(shù)。x，x是偶數(shù)，且x6（e）x，若x不是偶數(shù)，則x2除盡。對所有的x，若x是偶數(shù)，則對所有的，若x，則y也是偶數(shù)。對所有的x，若x是質(zhì)數(shù)，則存在x所有質(zhì)數(shù)能除盡某些偶數(shù)。對所有的x，若x是奇數(shù)，則對所有是質(zhì)數(shù)，則x不能除盡即任何奇數(shù)不能除盡任何質(zhì)數(shù)。（2）（x）y)((P(x∧P(y∧┐E(x,y→!z)(L(z∧R(x,y,z)))或∧┐(u)(┐E(z,u)∧L(u)∧R(x,y,u))))解：N(x):x是有限個數(shù)的乘積。z(y):y0。P(x):x的乘積為零。F(y):y是乘積中的一個因子則有 (x)((N(x)∧P(x)→(y)(F(y)∧z(y)))R(x):xQ(x,y):yx(x)(R(x)→(y)(Q(x,y)∧R(y)))R(x):x是實數(shù)。G(x,y):x。則(x)(y)(z)(R(x)∧R(y)∧R(z)∧G(x+y,x·z)（4）解：設(shè)G(x,y):x大于y。則有(x)(y)(z)(G(y,x)∧G(0,z)→G(x·z,y·z))N(x):xS(x,y):yx的后繼數(shù)。則a) (x)(N(x)→(!y)(N(y)∧S(x,y)))或(x)(N(x)→(y)(N(y)∧S(x,y) ∧┐(z)(┐E(y,z) ∧N(z)S(x,z))))b)┐(x)(N(x)∧S(x,1))c) (x)(N(x)∧┐S(x,2)→(!y)(N(y)∧S(y,x)))或(x)(N(x)∧┐S(x,2)→(y)(N(y)∧S(y,x)∧┐(z)(┐E(y,z)∧N(z)∧S(z,x))))S(x):xE(x):x是戴眼睛的。F(x):x是用功的。 R(x,y):x在看。G(y):y是大的。 K(y):y是厚的。 J(y):y是巨著。 a:本。 b:那位。則有E(b)∧F(b)∧S(b)∧R(b,a)∧G(a)∧K(a)∧J(a)解：設(shè)P(x,y):x在y連續(xù)。 Q(x,y):x>y。則

習(xí)題2-4解：a)x是約束變元，y是自由變元。xx的約束，S(x)x受存在量詞的約束。x，y都是約束變元,P(x)中的x受的約束，R(x)中的x受的約束。x，y是約束變元，z是自由變元。(2) 解：a)b)R(a)∧R(b)∧R(c)∧S(a)∧S(b)∧S(c)c)(P(a)→Q(a))∧(P(b)→Q(b))∧(P(c)→Q(c)d)(┐P(a)∧┐P(b)∧┐P(c))∨(P(z)∧P(b)∧P(c))e)(R(a)∧R(b)∧R(c))∧(S(a)∨S(b)∨S(c))(3) 解：a)(x)(P(x)∨Q(x))(P(1)∨Q(1))∧(P(2)∨Q(2))，但P(1)為T，Q(1)為F，P(2)為F，Q(2)為所T。b)(x)(P→Q(x))∨R(a)((P→Q(2))∧(P→Q(3))∧(P→Q(6)))∨R(a)PT，Q(2)T，Q(3)T，Q(6)F，R(5)F，所以F(4) 解：a)u)(v)(P(u，z)→Q(v))S(x，y)b)(u)(P(u)→(R(u)∨Q(u))∧(v)R(v))→(z)S(x,z)(5) 解：a)b)((y)P(u，y)∧(z)Q(u，z))∨(x)R(x，t)習(xí)題2-5（ 1 ） 解 ：a) b)(x)(y)P(y,x)(x) (P(1,x) ∨P(2,x)) (P(1,1) ∨P(2,1))∧(P(1,2)∨P(2,2))Tc)(x)(y)(P(x,y)→P(f(x),f(y)))(x)((P(x,1)→P(f(x),f(1)))∧(P(x,2)→P(f(x)f(2))))(P(1,1)→P(f(1),f(1)))∧(P(1,2)→P(f(1),f(2)))∧(P(2,1)→P(f(2),f(1)))∧(P(2,2)→P(f(2),f(2)))對論域中所有x，x不是大學(xué)生。結(jié)論：對論域中所有x都是研究生。(P(1,1)→P(2,2))∧(P(1,2)→P(2,1))∧(P(2,1)→P(1,2))∧(P(2,2)→P(1,1))故，對論域中某個a，必有結(jié)論a是研究生，即P（a）成立。(T→F∧(T→F)∧(F→T)∧(F→T)F∧F∧T∧TF（2）解：a)(x)(P(x)→Q(f(x),a))）P（xx（xxR（xx學(xué)。(P(1)→Q(f(1),1))∧(P(2)→Q(f(2),1))前提對所有x，如果x是研究生，則x曾讀過大學(xué)。(F→Q(2,1))∧(T→Q(1,1))對所有x，如果x曾讀過大學(xué)，則x曾讀過中學(xué)。b)(x)(P(f(x))∧Q(x,f(a))結(jié)論：對所有x，如果x是研究生，則x曾讀過中學(xué)。d）P（xx（xx是運動員。 ∨ ∨前提對所有x，或者x是研究生，或者x是運動員。Tc) (x)(P(x)∧Q(x,a))x，x結(jié)論必存在x，x(P(1)∧Q(1,a))∨(P(2)∧Q(2,a))）P（xx（xx是運動員。(P(1)∧Q(1,1))∨(P(2)∧Q(2,1))前提對所有x，或者x是研究生，或者x是運動員。F對所有x，x不是研究生d)(x)(y)(P(x)∧Q(x,y))結(jié)論對所有x，x是運動員。(x)(P(x)∧(y)Q(x,y))(x)(P(x)∧(Q(x,1)∨Q(x,2)))(x)(┐A(x)∨B(x))(x)┐A(x)∨(x)B(x)(P(1)∧(Q(1,1)∨Q(1,2)))∧(P(2)∧(Q(2,1)∨Q(2,2)))┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x)F（5）(x)A(x)∨(x)B(x)x)(A(x)∨B(x))(3)舉例說明下列各蘊含式。證明：因為論域D={a，b，c}，所以a) ((x)(P(x)∧Q(a))(x)P(x)Q(a)(x)A(x)∨(x)B(x)(A(a)∧A(b)∧A(c))∨(B(a)∧B(b)∧B(c))b) (x)(P(x)Q(x)),(x)Q(x)P(a)(A(a)∨B(a))∧(A(a)∨B(b))∧(A(a)∨B(c))∧(A(b)∨B(a))∧c) (x)(P(x)Q(x)),(x)(Q(x)R(x))(x)(P(x)R(x))(A(b)∨B(b))∧(A(b)∨B(c))∧(A(c)∨B(a))∧(A(c)∨B(b))d) (x)(P(x)Q(x)),(x)P(x)(x)Q(x)e) (x)(P(x)Q(x)),(x)P(x)(x)Q(x)解：a）因為((x)(P(x)∧Q(a))(x)P(x)∨Q(a)∧(A(c)∨B(c))(A(a)∨B(a))∧(A(b)∨B(b))∧(A(c)∨B(c))(x)(A(x)∨B(x))故原式為(x)P(x)∨Q(a)(x)P(x)Q(a)所以(x)A(x)∨(x)B(x)(x)(A(x)∨B(x))P（xx（xx是運動員（6）解：推證不正確，因為前提 或者不存在x，x是大學(xué)生，或者a是運動員┐(x)(A(x)∧┐B(x))┐((x)A(x)∧(x)┐B(x))結(jié)論如果存在x是大學(xué)生，則必有a是運動員。（7）求證(x)(y)(P(x)→Q(y))(x)P(x)→(y)Q(y)bP（xx（xx：論域中的某人。證明：(x)(y)(P(x)→Q(y))前提：對論域中所有x，如果x不是研究生則x是大學(xué)生。(x)(y)(┐P(x)∨Q(y))(x)┐P(x)∨(y)Q(y)┐(x)P(x)∨(y)Q(y)(x)P(x)→(y)Q(y)習(xí)題2-6（1）解：a) (x)(P(x)→(y)Q(x,y))(x)(┐P(x)∨(y)Q(x,y))(x)(y)(┐P(x)∨Q(x,y))b) (x)(┐((y)P(x,y))→((z)Q(z)→R(x)))(x)((y)P(x,y)∨((z)Q(z)→R(x)))(x)((y)P(x,y)∨(┐(z)Q(z)∨R(x)))(x)((y)P(x,y)∨((z)┐Q(z)∨R(x)))(x)(y)(z)(P(x,y)∨┐Q(z)∨R(x))c)(x)(y)(((zP(x,y,z)∧(u)Q(x,u))→(v)Q(y,v))(x)(y)(┐((z)P(x,y,z)∧(u)Q(x,u))∨(v)Q(y,v))(x)(y)((z)┐P(x,y,z)∨(u)┐Q(x,u)∨(v)Q(y,v))(x)(y)((z)┐P(x,y,z)∨(u)┐Q(x,u)∨(v)Q(y,v))(x)(y)(z)(u)(v)(┐P(x,y,z)∨┐Q(x,u)∨Q(y,v))（2）解：a) ((x)P(x)∨(x)Q(x))→(x)(P(x)∨Q(x))┐((x)P(x)∨(x)Q(x))∨(x)(P(x)∨Q(x))┐(x)(P(x)∨Q(x))∨(x)(P(x)∨Q(x))Tb) (x)(P(x)→(y)((z)Q(x,y)→┐(z)R(y,x)))(x)(┐P(x)∨(y)(Q(x,y)→┐R(y,x)))(x)(y)(┐P(x)∨┐Q(x,y)∨┐R(y,x))前束合取范式(x)(y)((P(x)∧Q(x,y)∧R(y,x))∨(P(x)∧Q(x,y)∧┐R(y,x))∨(P(x)∧┐Q(x,y)∧R(y,x))∨(┐P(x)∧Q(x,y)∧R(y,x))∨(┐P(x)∧┐Q(x,y)∧R(y,x))∨((P(x)∧┐Q(x,y)∧┐R(y,x))∨(┐P(x)∧Q(x,y)∧┐R(y,x)))前束析取范式

c) (x)P(x)→(x)((z)Q(x,z)∨(z)R(x,y,z))┐(x)P(x)∨(x)((z)Q(x,z)∨(z)R(x,y,z))(x)┐P(x)∨(x)((z)Q(x,z)∨(u)R(x,y,u))(x)(┐P(x)∨(z)Q(x,z)∨(u)R(x,y,u))(x)(z)(u)(┐P(x)∨Q(x,z)∨R(x,y,u))前束合取范式(x)(z)(u)((P(x)∧Q(x,z)∧R(x,y,u))∨(P(x)∧Q(x,z)∧┐R(x,y,u))∨(P(x)∧┐Q(x,z)∧R(x,y,u))∨(P(x)∧┐Q(x,z)∧┐R(x,y,u))∨(┐P(x)∧Q(x,z)∧┐R(x,y,u))∨(┐P(x)∧┐Q(x,z)∧R(x,y,u))∨(┐P(x)∧┐Q(x,z)∧┐R(x,y,u)))前束析取范式d)(x)(P(x)→Q(x,y))→((y)P(y)∧(z)Q(y,z))┐(x)(┐P(x)∨Q(x,y))∨((y)P(y)∧(z)Q(y,z))(x)(P(x)∧┐Q(x,y))∨((u)P(u)∧(z)Q(y,z))(x)(u)(z)((P(x)∧┐Q(x,y))∨(P(u)∧Q(y,z)))前束析取范式(x)(u)(z)((P(x)∨P(u))∧(P(x)∨Q(y,z))∧(┐Q(x,y)∨P(u))∧(┐Q(x,y)∨Q(y,z)))前束合取范式習(xí)題2-7證明：(2)a)①(x)(┐A(x)→B(x)) P②┐A(u)→B(u) US①③(x)┐B(x) P④┐B(u) US③⑤A(u)∨B(u) T②E⑥A(u) T④⑤I⑦(x)A(x) EG⑥b)①┐x)(A(x)→B(x)) P（附加前提）②(x)┐(A(x)→B(x))T①E⑦(x)P(x)→(x)Q(x) CP③┐(A(c)→B(c))ES②b)因為(x)P(x)∨(x)Q(x)┐(x)P(x)→(x)Q(x)④A(c)T③I故本題就是推證(x)(P(x)∨Q(x)) ┐(x)P(x)→(x)Q(x)⑤┐B(c)T③I①┐(x)P(x) P（附加前提）⑥(x)A(x)EG④②(x)┐P(x) T①E⑦(x)A(x)→(x)B(x)P③┐P(c) ES②⑧(x)B(x)T⑥⑦I④(x)(P(x)∨Q(x)) P⑨B(c)US⑧⑤P(c)∨Q(c) ES④⑩B(c)∧┐B(c)T⑤⑨矛盾⑥Q(c) T③⑤Ic）①(x)(A(x)→B(x))P⑦(x)Q(x) EG⑥②A(u)→B(u)US①⑧┐(x)P(x)→(x)Q(x) CP③(x)(C(x)→┐B(x))P(3)④C(u)→┐B(u)US③解：aR（xx（xx是有理數(shù)。（x：x是整數(shù)。⑤┐B(u)→┐A(u)T②E本題符號化為：⑥C(u)→┐A(u)T④⑤I(x)(Q(x)→R(x))∧(x)(Q(x)∧I(x)) (x)(R(x)∧I(x))⑦(x)(C(x)→┐A(x))UG⑥①(x)(Q(x)∧I(x)) Pd)(x)(A(x)∨B(x)),(x)(B(x)→┐C(x)),(x)C(x)(x)A(x)②Q(c)∧I(c)ES①①(x)(B(x)→┐C(x)) P③(x)(Q(x)→R(x))P②B(u)→┐C(u)US①④Q(c)→R(c)US③③(x)C(x)P⑤Q(c)T②I④C(u)US③⑥R(c)T④⑤I⑤┐B(u)T②④I⑦I(c)T②I⑥(x)(A(x)∨B(x))P⑧R(c)∧I(c)T⑥⑦I⑦A(u)∨B(u)US⑨(x)(R(x)∧I(x))EG⑧⑧A(u)T⑤⑦Ib（xx（xx（xx喜歡騎自行⑨(x)A(x)UG⑧車(2) 證明：本題符號化為：a)①(x)P(x)P（附加前提）(x)(P(x)→┐Q(x)),(x)(Q(x)∨R(x)),(x)┐R(x) (x)┐P(x)②P(u)US①①(x)┐R(x) P③(x)(P(x)→Q(x))P②┐R(c) ES①④P(u)→Q(u)US③③(x)(Q(x)∨R(x)) P⑤Q(u)T②④I④Q(c)∨R(c) US③⑥(x)Q(x)UG⑤⑤Q(c) T②④I⑥(x)(P(x)→┐Q(x)) P⑦P(c)→┐Q(c) US⑥⑧┐P(c) T⑤⑦I⑨(x)┐P(x) EG⑧張不是理工科學(xué)生，但他是優(yōu)等生，因而如果小張是大學(xué)生，他就是文科學(xué)生。（xx（xx（xx是理工科學(xué)生。S（xx是優(yōu)秀生。本題符號化為：(x)(G(x)→L(x)∨P(x)),(x)(G(x)∧S(x)),┐P(c),S(c) G(c)→L(c)①G(c) P（附加前提）②(x)(G(x)→L(x)∨P(x)) P③G(c)→L(c)∨P(c) US②④L(c)∨P(c) T①③I⑤┐P(c) P⑥L(c) T④⑤I⑦G(c)→L(c) CP注意：本題推證過程中未用到前提(x)(G(x)∧S(x))以及S(c)。主要是S（xxS（x）與其他前提不矛盾，故本題的推證仍是有效的。

3-5.1 列出所有從 X={a,b,c} 到Y(jié)={s}的關(guān)系。解：Z1={<a,s>}Z2={<b,s>}Z3={<c,s>}Z4={<a,s>,<b,s>}Z5={<a,s>,<c,s>}Z6={<b,s>,<c,s>}Z7={<a,s>,<b,s>,<c,s>}3-5.2 在一個有 n個元素的集合上， 以有多少種不同的關(guān)系。解因為在X中的任何二元關(guān)系都是 X×X的子集，而 X×X=X2中共有n2個元素，取 0個到n2個元素，共可組成2個子集，即 |(XX)|23-5.3 A＝{600630,730,9：30,10：30}表示在晚上每隔半小時的九個時刻的集合， 設(shè)B={3,12,15,17}表示本地四個電視頻道的集合 ,設(shè)R1和R2是從A到B的兩個二元關(guān)系， 對于二無關(guān)系 R1，R2，R1∪R2，R1∩R2，R1R2和R1-R2可分別得出怎樣的解釋。AB電視頻道所組成的電視節(jié)目表。R1和R2分別是A×B的兩個子集，例如R1表示音樂節(jié)目播出的時間表，R2是戲曲節(jié)日的播出時間表，則 R1∪R2表示音樂或戲曲節(jié)目的播出時間表，R1∩R2表示音樂和戲曲一起播出的時間表， R1R2表示音樂節(jié)目表及戲曲節(jié)目表，但不是音樂和戲曲一起的節(jié)日表， R1-R2表示不是戲曲時的音樂節(jié)目時間麥。3-5.4 設(shè)L表示關(guān)系“小于或等于” 表示‘整除”關(guān)系 ,L和D刀均定義于{1,2,3,6} ，分別寫出 L和D的所有素并求出 L∩D.

解：L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>}D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>}L∩D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>}3-5.5 對下列每一式， 給出A上的二關(guān)系，試給出關(guān)系圖：a){<x,y>|0 xy3}，這里A={1,2,3,4} ；{<x,y>|2 ?x,y?7且xy,里A＝{n|nNn10}c){<x,y>|0 x-y<3}，這里A={0,1,2,3,4} ；d){<x,y>|x,y 是互質(zhì)的A={2,3,4,5,6}解：a)R={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<1,3>,<2,0>,<2,1>,<2,2>,<2,3>,<3,0>,<3,1>,<3,2>,<3,3>,}其關(guān)系圖b)R={<2,0>,<2,2>,<2,4>,<2,6>,<3,0>,<3,3>,<3,6>,<4,0>,<4,4>,<5,0>,<5,5>,<6,0>,<6,6>,<7,0>,<7,7>}3-6.1分析集合A={1，2，3}上的下述五個關(guān)系：

R是可傳遞的的和反對稱的； 但不是反的和對稱的。

3-7.1設(shè)R和R是A上的任意關(guān)系，1 2說明以下命題的真假并予以證明。

S，且＜yzS。若S是傳遞的，＜xz＞∈S（S○S）（1）R={＜1，1＞，＜1，2＞，＜1，

若R1

和R是自反的，則 R○R也是2 1 2

S。3＞，＜3，3＞}；

3-6.3 舉出A={123}上關(guān)系R

自反的；（2）S={＜1，1＞，＜1，2＞，＜2，

例子，使其具有下述性質(zhì)：

若R1

和R是反自反的，則 R○R也2 1 2

反之，設(shè)（S○S）S，假定＜xy＞1＞，＜2，2＞，＜3，3＞}；

既是對稱的，又是反對稱的；

是反自反的；

SS○S。（3）T={＜1，1＞，＜1，2＞，＜2，

R既不是對稱的，又不是反對稱的；

若R1

和R是對稱的，則 R○R也是2 1 2

因為（S○S）S，故＜xzS，得2＞，＜2，3＞}；

R

對稱的；

到S是傳遞的。（4）?

若R1

和R是傳遞的，則 R○R也是2 1 2（5）AA=

解 傳遞的。

b）設(shè)S是自反的，令＜xyIX判斷A中的上述關(guān)系是否為 a自反的b）對稱的，c）可傳遞的，d）反對稱

a）R={＜1，1＞，＜2，2＞，＜3，3＞}

證明a）對任意aA，設(shè)R1

和R是自2

則x=yxxS，因此＜xyxxS，得IS。X的。 b）R={＜1，2＞，＜2，1＞，＜2，3

反的，則＜aa

，＜a，a＞∈R1 2 所以，＜aaR○RR○R

反之，令I(lǐng)

S，設(shè)任意xXxx解（1）R

c)R={＜1，2＞，＜2，1＞，＜1，1

自反的。

1 2 1 2

＞∈

XxxS，因此SX（2）S（3）T

＞，＜2，2＞，＜3，3＞}

假。例如：設(shè)A={ab}R1

反的。（4）空關(guān)系是對稱，可傳遞和反對稱的。

3-6.4如果關(guān)系R和S是自反的，對稱的和可傳遞的，證明R∩S也是自反，

ab

={＜b，a＞}2

設(shè)S是反對稱的。假定＜ x，y＞∈R和R1 2

是反自反的。但 R○R1

={＜a，2

S∩Sc，則（5）全域關(guān)系是自反，對稱和可傳遞的。

對稱和可傳遞的。

R○R1 2

A

＜x，y＞∈S∧＜x，y＞∈Sc＜x，y＞∈S∧＜y，x＞∈S證明設(shè)R和S是X上的自反的，對稱

假。例如：設(shè) A={a，b，c}，

因為S是反對稱的，故 x＝y(tǒng)，3-6.2給定A={123,4}，考慮a的關(guān)系R,R={13＞，＜14＞，＜2，3＞，＜2，4＞，＜3，4＞}

的和可傳遞的關(guān)系。對任意xXx，xRx，x＞?S，所以＜x，x＞?R∩S，

R={＜a，b＞，＜b，a＞，＜c，c＞}，1R={＜b，c＞，＜c，b＞}2

xy＞＝＜xxIS∩ScI。XXX在AA的坐標(biāo)圖上標(biāo)出 R，并繪出

即R∩S在X上是自反的。

R和R1

R={＜a，c＞，1 2＜c，b＞}

反之，若S∩ScI，設(shè)＜x，y＞∈S且它的關(guān)系圖；R是ⅰ)自反的ⅱ）對稱的ⅲ )可傳

對任意的＜x，yRSx，y＞?R∧＜x，y＞?S，因為R和S

R○R1 2

不是對稱的。

XyxS，則遞的，iv)反對稱的嗎？

是對稱的，故必有＜ y，x＞?R∧

假。例如：設(shè) A={a，b，c}，有

＜x，y＞∈S∧＜x，y＞∈Sc＜x，y＞∈S∩Sc解 ＜y，x＞?S。即＜y，x＞?R∩S，a） 所以RSX對任意的＜x，yRSy，z

R={＜a，b＞，＜b，c＞，＜a，c＞}，1R={＜b，c＞，＜c，a＞，＜b，a＞}2

＜x，y＞∈IXx＝y(tǒng)，即S＞?R∩S，則有

RR1

都是傳遞的。但

R={＜a，1 2＜x，y＞?R∧＜x，y＞?S∧＜y，

c＞，＜a，a＞，＜b，a＞}

3-7.3設(shè)S為X上的關(guān)系，證明若 Sz＞?R∧＜y，z＞?S因為R和S是傳遞的，故得＜ x，z＞

R○R1 2

不是傳遞的。

是自反和傳遞的，則S○S=S，其逆為真嗎？RxzS，即＜xzR∩S，所以RSX1233-6.5給定S={1234}S上關(guān)R={12＞，＜43＞，＜2123＞，＜2，1＞，＜3，1＞}4 說明R是不可傳遞的，找出關(guān)系RR，

3-7.2證明若S為集合X上的二元關(guān)系：a）S是傳遞的，當(dāng)且僅當(dāng)（ S○S）S；b）S是自反的，當(dāng)且僅當(dāng) IS；Xc）證明定理3-7.3（b（即S是反對稱的，當(dāng)且僅當(dāng) S∩ScI。X

證明若S是X上傳遞關(guān)系，由習(xí)題3-7.2a）可知（S○S）S，令＜x，y＞∈S，根據(jù)自反性，必有＜x，x＞∈S，因此有＜x，y＞∈S○S，即SS○S。得到 S=S○S.使得R1

1是可傳遞的，還能找出另一個

證明a）設(shè)S為傳遞的，若＜xz＞S○S，則存在某個yX，使得＜x，y

這個定理的逆不真。例如X={1S={＜1，2＞，＜2，2＞，＜1，1＞}，bc圖3-8.1a1100010103-8.1根據(jù)圖3-8.1中的有向圖，bc圖3-8.1a110001010M=

3-9.14個元素的集合共有多少不同的劃分。解整數(shù)41+1+1+2+1+1+1+。1R 1+C1+C2+C2+1=1（種）4 4 243-9.2{AAAR={＜a，a＞，＜a，b＞，＜b，c＞，＜c，b＞＝

1 2 kr（R）=R∪IX

={＜a，a＞，＜b，b＞，＜c，c＞，＜a，b＞，＜b，c＞，＜c，b＞＝

abRs（R）=R∪RC={＜a，a＞，＜a，b＞，＜b，a＞，＜b，c＞，＜c，b＞}3-8.2設(shè)集合A={abcd}A上的關(guān)系R={＜a，b＞，＜b，a＞，＜b，c＞，＜c，d＞}用矩陣運算和作圖方法求出 R的自反、對稱、傳遞閉包；010010100000100101000010000M=

證明A，使A，因a與a＞i i∈R。即R是自反的。設(shè)a,a,，則a與bb與ab,＞，即R＜a,b＞∈R∧＜b,c＞∈RAA）∧AA）R i i j jAAAA）i j i jabdcAAAAabdci j i jR的關(guān)系圖如圖所示。01001000110100100011001010010011100001+0010 = 0011000000010001R IA

AAi=（AA=）i j i ja,c在同一塊r（R）=R∪IA={＜a，a＞，＜a，b＞，＜b，a＞，＜b，b＞，＜b，c＞，＜c，c＞，＜c，d＞，＜d，d＞}（圖（a）a bd c 圖（a）=010001000=010001000100M+M=1010100010100001+010001010000001000103-10.1 設(shè)R和R′是集合A上的等價關(guān)系，用例子說明： R∪R′不一定是等價關(guān)系證明設(shè)A={1，2，3}，S=R∪R′

證明設(shè)A上定義的二元關(guān)系R為：R={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞}R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，2＞，＜2，3＞}則R∪R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞，＜3，2＞，＜2，3＞}因為如＜2，3＞∈S∧＜3，1＞∈S，但＜2，1＞S，故R∪R′不是傳遞的，即 R∪R′不是A上的等價關(guān)系。3-10.2 試問由4解因為集合X上的等價關(guān)系與 X的劃分是一一對應(yīng)的，所以 4個元素的有限集上等價關(guān)系的數(shù)目，與 4個元素集合進行劃分的數(shù)目是相同的，由習(xí)題 3-9.1可知共有15個不同的價關(guān)系。3-10.3 給定集合S={1，2，3，4，5}，找出S上的等價關(guān)系 R，此關(guān)系R能產(chǎn)生劃分{{1，2}{3}{45}}

u＜＜x,y＞,＜u,v＞＞∈R =vx①對任意＜x,y＞∈A，因為 =，所以y＜＜x,y＞,＜x,y＞＞∈R即R是自反的。②設(shè)＜x,y＞∈A，＜u,v＞∈A，若xu ux＜＜x,y＞,＜u,v＞＞∈Ry=vv=y＜＜u,v＞,＜R={1，2}×{1，2}={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞}1R={3}×{3}={＜3，3＞}2R={4，5}×{4，5}={＜4，4＞，＜4，5＞，＜5，4＞，＜5，5＞}3

x,y＞＞∈R即R是對稱的。R=R

∪R∪1 2

={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞，＜3，3＞，＜4，4＞，＜4，53＞，＜5，4＞，＜5，5＞}關(guān)系圖如圖。

③設(shè)任意＜x,y＞∈A，＜u,v＞∈A，＜w,s＞∈A，對＜＜x,y＞,＜u,v＞＞∈R∧＜＜u,v＞,＜w,s＞＞∈R（x u u w x w= ）∧（y v v

= ） =s y s3-10.4 設(shè)R是一個二元關(guān)系， S={＜a，b＞∣對于某一 c，有＜a，c＞∈R∧＜c，b＞∈R}證明若R是一個等價關(guān)系，則 S也是一個等價關(guān)系。證