第一篇：離散數(shù)學(xué)習(xí)題三 含答案

離散數(shù)學(xué)習(xí)題三

11、填充下面推理證明中沒(méi)有寫(xiě)出的推理規(guī)則。前提：?p?q,?q?r,r?s,p 結(jié)論：s 證明：①

p

前提引入 ②?p?q

前提引入

③

q

（①②析取三段論）④?q?r

前提引入

⑤

r

（③④析取三段論）⑥r(nóng)?s

前提引入

⑦

s

（⑤⑥假言推理）

12、填充下面推理證明中沒(méi)有寫(xiě)出的推理規(guī)則。前提：p?(q?r),q?(r?s)結(jié)論：(p?q)?s

證明：①(p?q)

（附加前提）②

p

（①化簡(jiǎn)規(guī)則）③

q

（①化簡(jiǎn)規(guī)則）④p?(q?r)

前提引入 ⑤q?r

（②④假言推理）⑥

r

（③⑤假言推理）⑦q?(r?s)

前提引入 ⑧(r?s)

（③⑦假言推理）⑨

s

（⑥⑧假言推理）

13、前提：?(p?q)?q,p?q,r?s

結(jié)論1：r 結(jié)論2：s 結(jié)論3：r?s

（1）證明從此前提出發(fā)，推出結(jié)論1，結(jié)論2，結(jié)論3的推理都是正確的。（2）證明從此前提出發(fā)，推任何結(jié)論的推理都是正確的。證明：（1）①((?(p?q)?q)?(p?q)?(r?s))?r

?((?p?q)??q)?(?p??q)?(r??s))?r?1 ②((?(p?q)?q)?(p?q)?(r?s))?s

?((?p?q)??q)?(?p??q)?(r??s))?s?1

③((?(p?q)?q)?(p?q)?(r?s))?(r?s)

?((?p?q)??q)?(?p??q)?(r??s))?r?s?1

即結(jié)論1，結(jié)論2，結(jié)論3的推理都是正確的。

（2）(?(p?q)?q)?(p?q)?(r?s)

?(?(?p?q)?q)?(p?q)?(?r?s)?(p??q?q)?(p?q)?(?r?s)?0?(p?q)?(?r?s)?0

即推任何結(jié)論的推理都是正確的。

14、在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：（1）前提：p?(q?r)，p,q 結(jié)論：r?s

證明：①p?(q?r)

前提引入 ②

p

前提引入 ③

(q?r)

① ②假言推理

④

q

前提引入 ⑤

r

③ ④假言推理 ⑥

r?s

⑤ 附加律

15、在自然推理系統(tǒng)P中用附加前提法證明下面的推理： 前提：p?(q?r)，s?p,q

結(jié)論：s?r 證明：

①

s

附加前提引入 ②

s?p

前提引入 ③

p

① ②假言推理 ④

p?(q?r)

前提引入 ⑤

q?r

③ ④假言推理 ⑥

q

前提引入

⑦

r

⑤

⑥假言推理 即根據(jù)附加前提證明法，推理正確。

16、在自然推理系統(tǒng)P中用歸謬法證明下面的推理： 前提：p?q，q?r,q?s 結(jié)論：r?s 證明：

①

?(r?s)

結(jié)論否定引入 ②

p?q

前提引入 ③

q?r

前提引入 ④

q?s

前提引入

⑤

r?s

② ③ ④構(gòu)造性二難 ⑥

?(r?s)?(r?s)

① ⑤

合取

因?yàn)棰逓槊苁郊赐评碚_

17、在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：

只要A曾到過(guò)受害者房間并且11點(diǎn)以前沒(méi)離開(kāi)，A就是謀殺嫌犯。A曾到過(guò)受害者房間，如果A在11點(diǎn)以前離開(kāi)，看門(mén)人會(huì)看見(jiàn)他?？撮T(mén)人沒(méi)有看見(jiàn)他。所以，A是謀殺嫌犯。

答：令p: A到過(guò)受害者房間

q: A在11點(diǎn)以前離開(kāi)

r: A是謀殺嫌犯

s: 看門(mén)人看見(jiàn)過(guò)A 前提：(p??q)?r,p,q?s,?s 結(jié)論：r 證明：① q?s

前提引入 ②

?s

前提引入 ③

?q

① ②拒取式 ④

p

前提引入 ⑤

p??q

③ ④合取 ⑥(p??q)?r

前提引入 ⑦

r

⑤

⑥假言推理

1114490009

張夢(mèng)婷

第二篇：離散數(shù)學(xué)習(xí)題

集合論

1.A={?,1}，B={{a}}求A的冪集、A×B、A∪B、A+B。2.A={1,2,3,4,5}, R={(x,y)|x

4.A={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b關(guān)于R的等價(jià)類(lèi)。

5.R是A上的等價(jià)關(guān)系，A/R={{1,2}，{3}},求A，R。6.請(qǐng)分別判斷以下結(jié)論是否一定成立，如果一定成立請(qǐng)證明，否則請(qǐng)舉出反例。

①如果A∪B?C，則A?C或者B?C。②如果A×B=A×C且A??，則B=C。

27.如果R是A上的等價(jià)關(guān)系，R,r(R)是否一定是A上的等價(jià)關(guān)系？證明或舉例。

8.已知A∩C?B∩C,A-C?B-C,證明：A?B。9.證明：AX(B∩C)=(AXB)∩(AXC)10.證明：P(A)∪P(B)?P(A∪B)-111.證明：R[sym] iff R=R

-1212.證明：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...13.證明：s(R∪S)=s(R)∪s(S)14.R是A上的關(guān)系，證明：如果R是對(duì)稱(chēng)的，則r(R)也是對(duì)稱(chēng)的。

15.I是整數(shù)集，R={(x,y)|x-y是3的倍數(shù)}，證明：R是I上的等價(jià)關(guān)系。

16.如果R是A上的等價(jià)關(guān)系，則A/R一定是A的劃分。17.R是集合A上的自反關(guān)系，S是A上的自反和對(duì)稱(chēng)關(guān)系，證明t(R∪S)是A上的等價(jià)關(guān)系。18.I是正整數(shù)集合，R是I×I上的二元關(guān)系，R={<,>|xv=yu},證明：R是等價(jià)關(guān)系。

19.f:A?B，R是B上的等價(jià)關(guān)系，令S={|x?A且y?A且?R}，證明：S是A上的等價(jià)關(guān)系。

20.R是集合A上的自反關(guān)系，S是A上的自反和對(duì)稱(chēng)關(guān)系，證明t(R∪S)是A上的等價(jià)關(guān)系。

21.P和Q都是集合A上的劃分，請(qǐng)問(wèn)P∪Q，P-Q是否是A上的劃分，22.R?AXA,R[irref]且R[tra],證明：r(R)是A上的偏序關(guān)系。

23.畫(huà)出{1,2,3,4,6}上整除關(guān)系的哈斯圖，求{2,3,6}的4種元素。

24.A={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),畫(huà)出S的哈斯圖并求{b,c,d,f}的極大元等8種元素。

25.f:A→B,g:B→C都是單（滿(mǎn)）射，證明：復(fù)合映射gof一定是單（滿(mǎn)）射。

26.f:A→B,g:B→C，gof是單射，請(qǐng)問(wèn)f和g是否一定是單射？請(qǐng)證明或舉出反例。27.R是實(shí)數(shù)集，f:R×R?R×R,f()=,請(qǐng)問(wèn)f是否為單射？是否為滿(mǎn)射？分別證明或舉反例。28.已知B∩C=?,令f：P(B∪C)?P(B)×P(C)，對(duì)X?P(B∪C),令f(X)=(B∩X,C∩X),證明：f是雙射。

代數(shù)系統(tǒng)

1.是模8加群，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的單位元、每個(gè)元素的逆元、所有的生成元和所有的子群。

2.求的單位元，零元，每個(gè)元素的逆元，每個(gè)元素的階，它是循環(huán)群?jiǎn)?？求出它所有的子群?/p>

3.R是實(shí)數(shù)集，在R上定義運(yùn)算*為x*y=x+y+xy,問(wèn)：是代數(shù)系統(tǒng)嗎？有單位元嗎？每個(gè)元素都有逆元嗎？ ***4.R是非零實(shí)數(shù)集合，是代數(shù)系統(tǒng)，對(duì)于R中元素*x,y，令xoy=2x+2y-2。請(qǐng)問(wèn)中是否存在單位元、零元、哪些元素有逆元？運(yùn)算o是否滿(mǎn)足交換律和結(jié)合律。分別說(shuō)明理由。

5.R是實(shí)數(shù)集，R上的6運(yùn)算定義如下：對(duì)R中元素x,y，f1()=x+y；f2()=x-y；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|x-y|。問(wèn)：哪些滿(mǎn)足交換律、結(jié)合律、有單位元、有零元？說(shuō)明理由。

6.是一個(gè)群，證明：G是交換群當(dāng)且僅當(dāng)對(duì)任意G中222元素x,y,都有等式(xy)=xy成立。

7.證明：如果群G中每個(gè)元素的逆元素都是它自已，則G是交換群。

8.循環(huán)群一定是交換群。

9.證明：階為素?cái)?shù)的群一定是循環(huán)群。

-110.是一個(gè)群，u?G,定義運(yùn)算*：x*y=xouoy, 證明：是一個(gè)群。

11.整數(shù)集Z上定義運(yùn)算*：對(duì)任意整數(shù)x和y,x*y=x+y-4,其中+，-為普通加減法。證明：是一個(gè)群。

12.證明：如果群G中至少有兩個(gè)元素，則群中沒(méi)有零元。13.S是G的子群，證明：{x|x是S的左陪集}是G的一個(gè)劃分

14.是一個(gè)群,a?G,n是a的階(周期)，證明：k<{a|k=0,2,…,n-1},o>是的一個(gè)子群。

15.H，K都是群G的子群，請(qǐng)問(wèn)H∩K,H∪K,H-K是否一定是G的子群？ 16.H，K是G的兩個(gè)子群，a?G, 試證：aH?aK當(dāng)且僅當(dāng)H?K。17.G={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，請(qǐng)問(wèn)(G,*)是否構(gòu)成群？

n18.是群，e是單位元，a?G,a的階為k,證明：a=e當(dāng)且僅當(dāng) n是k的倍數(shù)。

19.S是G的子群，證明：{x|x是S的左陪集}是G的一個(gè)劃分

20.G是群，證明：S={a?G|?x?G(ax=xa)},則S是G的子群。21.是偶數(shù)階群，則G中必存在2階元素。22.證明：6個(gè)元素的群在同構(gòu)意義下只有兩個(gè)。

++23.R為實(shí)數(shù)集，R為正實(shí)數(shù)集，與是否同構(gòu)？ 24.是有限群，證明：G不可能表示成兩個(gè)真子群的并。25.圖論

1.如何判斷二部圖？完全圖、完全二部圖的邊數(shù)。2.如何求E回路？

3.Petersen圖是否為E圖或H圖。

4.哪些完全圖是H圖？哪些完全圖是E圖？ 5.n為何值時(shí)輪圖為H圖？ 6.如何求最小生成樹(shù)。

7.證明：奇數(shù)個(gè)頂點(diǎn)的二部圖（兩步圖）不是哈密爾頓圖。8.證明：如果G是歐拉圖，則其邊圖L(G)也是歐拉圖。9.證明：奇數(shù)個(gè)頂點(diǎn)的二部圖（兩步圖）不是哈密爾頓圖。10.G是平面圖，G有m條邊，n個(gè)頂點(diǎn)，證明：m?3n-6。并由此證明K5不是平面圖。

11.證明：有6個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖G和它的補(bǔ)圖中至少有一個(gè)三角形。

12.證明：在至少有兩個(gè)頂點(diǎn)的無(wú)向樹(shù)中，至少有2個(gè)一度頂點(diǎn)。

13.G是無(wú)向簡(jiǎn)單連通圖，G有n個(gè)頂點(diǎn)，則G最少有幾條邊，最多有幾條邊？

14.證明：簡(jiǎn)單無(wú)向圖G和它的補(bǔ)圖中至少有一個(gè)是連通圖。15.證明：無(wú)向圖中奇度點(diǎn)（度數(shù)為奇數(shù)的點(diǎn)）有偶數(shù)個(gè)。16.證明：n個(gè)頂點(diǎn)的無(wú)向連通圖至少有n-1條邊。17.G是H圖，V是G的頂點(diǎn)集，證明：對(duì)任意頂點(diǎn)集S，??S?V，都有ω（G-S）≤|S|。其中ω（G-S）表示G-S的分圖數(shù)目。18.一棵無(wú)向樹(shù)有3個(gè)3次點(diǎn)，1個(gè)頂點(diǎn)次數(shù)為2，其余頂點(diǎn)次數(shù)為1，問(wèn)它有幾個(gè)次數(shù)為1的頂點(diǎn)？寫(xiě)出求解過(guò)程。19.證明：每個(gè)簡(jiǎn)單平面圖都包含一個(gè)次至多為5的頂點(diǎn)。20.連通平面圖G有n個(gè)頂點(diǎn)，m條邊和f個(gè)面，證明：n-m+f=2。21.如果圖G的最大頂點(diǎn)次數(shù)≤ρ，證明：G是ρ+1可點(diǎn)著色的。

22.G是無(wú)向簡(jiǎn)單連通圖，G有n個(gè)頂點(diǎn)，則G最少有幾條邊，最多有幾條邊？

23.如果一個(gè)簡(jiǎn)單圖G和它的補(bǔ)圖同構(gòu)，則稱(chēng)G是自補(bǔ)圖，求所有4個(gè)頂點(diǎn)自補(bǔ)圖。

24.G是平面圖，G有m條邊，n個(gè)頂點(diǎn)，證明：m?3n-6。如果G中無(wú)三角形，則m?2n-4。數(shù)理邏輯

1.如果今天是星期一，則要進(jìn)行英語(yǔ)或數(shù)理邏輯考試。

沒(méi)有不犯錯(cuò)誤的人。整數(shù)都是有理數(shù)。有的有理數(shù)不是整數(shù)。

不存在最大的整數(shù)。有且只有一個(gè)偶數(shù)是素?cái)?shù)。2.求真值表及范式：P?(┓Q(chēng)?R)、(┓Q(chēng)?R)?(P?R)3.推理：

p?(q?r)，┓s∨p，q ├ s?r p?r，q?s，p∨q ├ r∨s p∨q，p?┓r，s?t，┓s?r，┓t ├ q p?(┓(r∧s)?┓q),p,┓s ├ ┓q 4.如果小王是理科學(xué)生，他一定會(huì)學(xué)好數(shù)學(xué)。如果小王不是文科學(xué)生，他一定是理科學(xué)生。小王沒(méi)學(xué)好數(shù)學(xué)。所以小王是文科學(xué)生。

5.判斷各公式在給定解釋時(shí)的真假值，并且改變論域使該公式在新的解釋下取值相反。論域：D={-2,3,6}, F(x):x≤3, G(x):x>5, R(x,y):x+y<4 ①?x(F(x)∨G(x))②?y?yR(x,y)

第三篇：離散數(shù)學(xué)習(xí)題及答案

離散數(shù)學(xué)考試試題（A卷及答案）

一、（10分）某項(xiàng)工作需要派A、B、C和D 4個(gè)人中的2個(gè)人去完成，按下面3個(gè)條件，有幾種派法？如何派？

(1)若A去，則C和D中要去1個(gè)人；

(2)B和C不能都去；

(3)若C去，則D留下。

解設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A?C?D，?(B∧C)，C??D必須同時(shí)成立。因此

(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)

?F∨F∨(?A∧?C)∨F∨F∨(C∧? D∧?B)∨F∨F∨(?C∧D∧?B)∨F∨(?C∧D)∨F ?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D∧?B)∨(?C∧D)

?(?A∧?C)∨(?B∧C∧? D)∨(?C∧D)

?T

故有三種派法：B∧D，A∧C，A∧D。

二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會(huì)議的每個(gè)成員都是專(zhuān)家并且是工人，有些成員是青年人，所以，有些成員是青年專(zhuān)家。

解：論域：所有人的集合。S(x)：x是專(zhuān)家；W(x)：x是工人；Y(x)：x是青年人；則推理化形式為：

?x(S(x)∧W(x))，?xY(x)?x(S(x)∧Y(x))

下面給出證明：

(1)?xY(x)P

(2)Y(c)T(1)，ES

(3)?x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)?x(S(x)∧Y(x))T(6)，EG

三、（10分）設(shè)A、B和C是三個(gè)集合，則A?B??(B?A)。

證明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)

???x(x∈A∧x?B)∧??x(x?B∨x∈A)???x(x∈A∧x?B)∨??x(x∈A∨x?B)

??(?x(x∈A∧x?B)∧?x(x∈A∨x?B))??(?x(x∈A∧x?B)∧?x(x∈B→x∈A))

??(B?A)。

四、（15分）設(shè)A＝{1，2，3，4，5}，R是A上的二元關(guān)系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝?Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i?1?4232－

15>}。

五、（10分）R是非空集合A上的二元關(guān)系，若R是對(duì)稱(chēng)的，則r(R)和t(R)是對(duì)稱(chēng)的。

證明對(duì)任意的x、y∈A，若xr(R)y，則由r(R)＝R∪IA得，xRy或xIAy。因R與IA對(duì)稱(chēng)，所以有yRx或yIAx，于是yr(R)x。所以r(R)是對(duì)稱(chēng)的。

下證對(duì)任意正整數(shù)n，R對(duì)稱(chēng)。

因R對(duì)稱(chēng)，則有xRy??z(xRz∧zRy)??z(zRx∧yRz)?yRx，所以R對(duì)稱(chēng)。若Rn對(duì)稱(chēng)，則xRn?1y??z(xRnz∧zRy)??z(zRnx∧yRz)?yRn?1x，所以Rn?1對(duì)稱(chēng)。因此，對(duì)任意正整數(shù)n，Rn對(duì)稱(chēng)。對(duì)任意的x、y∈A，若xt(R)y，則存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是對(duì)稱(chēng)的。

六、（10分）若f：A→B是雙射，則f：B→A是雙射。

證明因?yàn)閒：A→B是雙射，則f是B到A的函數(shù)。下證f是雙射。

對(duì)任意x∈A，必存在y∈B使f(x)＝y(tǒng)，從而f(y)＝x，所以f是滿(mǎn)射。

對(duì)任意的y1、y2∈B，若f(y1)＝f(y2)＝x，則f(x)＝y(tǒng)1，f(x)＝y(tǒng)2。因?yàn)閒：A→B是函數(shù)，則y1＝y(tǒng)2。所以f是單射。

綜上可得，f：B→A是雙射。

七、（10分）設(shè)是一個(gè)半群，如果S是有限集，則必存在a∈S，使得a*a＝a。

證明因?yàn)?S，*>是一個(gè)半群，對(duì)任意的b∈S，由*的封閉性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因?yàn)镾是有限集，所以必存在j＞i，使得bi＝bj。令p＝j(luò)－i，則bj＝bp*bj。所以對(duì)q≥i，有bq＝bp*bq。

因?yàn)閜≥1，所以總可找到k≥1，使得kp≥i。對(duì)于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，則a∈S且a*a＝a。

八、（20分）（1）若G是連通的平面圖，且G的每個(gè)面的次數(shù)至少為l(l≥3)，則G的邊數(shù)m與結(jié)點(diǎn)數(shù)n有如下關(guān)系：

m≤

rl(n－2)。l?2l證明設(shè)G有r個(gè)面，則2m＝

2)。?d(f)≥lr。由歐拉公式得，n－m＋r＝2。于是，m≤l?2(n－ii?

1（2）設(shè)平面圖G＝是自對(duì)偶圖，則| E|＝2(|V|－1)。

證明設(shè)G＝是連通平面圖G＝的對(duì)偶圖，則G? G，于是|F|＝|V*|＝|V|，將其代入歐拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

離散數(shù)學(xué)考試試題（B卷及答案）

一、（10分）證明(P∨Q)∧(P?R)∧(Q?S)S∨R

證明因?yàn)镾∨R??R?S，所以，即要證(P∨Q)∧(P?R)∧(Q?S)?R?S。

(1)?R附加前提

(2)P?RP

(3)?PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)Q?SP

(7)ST(5)(6)，I

(8)?R?SCP

(9)S∨RT(8)，E

二、（15分）根據(jù)推理理論證明：每個(gè)考生或者勤奮或者聰明，所有勤奮的人都將有所作為，但并非所有考生都將有所作為，所以，一定有些考生是聰明的。

設(shè)P(e)：e是考生，Q(e)：e將有所作為，A(e)：e是勤奮的，B(e)：e是聰明的，個(gè)體域：人的集合，則命題可符號(hào)化為：?x(P(x)?(A(x)∨B(x)))，?x(A(x)?Q(x))，??x(P(x)?Q(x))?x(P(x)∧B(x))。

(1)??x(P(x)?Q(x))P

(2)??x(?P(x)∨Q(x))T(1)，E

(3)?x(P(x)∧?Q(x))T(2)，E

(4)P(a)∧?Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)?Q(a)T(4)，I

(7)?x(P(x)?(A(x)∨B(x))P

(8)P(a)?(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)?x(A(x)?Q(x))P

(11)A(a)?Q(a)T(10)，US

(12)?A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)?x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另外一種球，求不會(huì)打這三種球的人數(shù)。

解設(shè)A、B、C分別表示會(huì)打排球、網(wǎng)球和籃球的學(xué)生集合。則：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|A?B?C|＝25－20＝5。故，不會(huì)打這三種球的共5人。

四、（10分）設(shè)A1、A2和A3是全集U的子集，則形如?Ai?(Ai?為Ai或Ai)的集合稱(chēng)為由A1、A2和

i?1

3A3產(chǎn)生的小項(xiàng)。試證由A1、A2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個(gè)劃分。

證明小項(xiàng)共8個(gè)，設(shè)有r個(gè)非空小項(xiàng)s1、s2、…、sr(r≤8)。

對(duì)任意的a∈U，則a∈Ai或a∈Ai，兩者必有一個(gè)成立，取Ai?為包含元素a的Ai或Ai，則a∈?Ai?，i?13即有a∈?si，于是U??si。又顯然有?si?U，所以U＝?si。

i?1i?1i?1i?1rrrr

任取兩個(gè)非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個(gè)Ai和Ai分別出現(xiàn)在sp和sq中，于是sp∩sq＝?。綜上可知，{s1，s2，…，sr}是U的一個(gè)劃分。

五、（15分）設(shè)R是A上的二元關(guān)系，則：R是傳遞的?R*R?R。

證明(5)若R是傳遞的，則∈R*R??z(xRz∧zSy)?xRc∧cSy，由R是傳遞的得xRy，即有∈R，所以R*R?R。

反之，若R*R?R，則對(duì)任意的x、y、z∈A，如果xRz且zRy，則∈R*R，于是有∈R，即有xRy，所以R是傳遞的。

六、（15分）若G為連通平面圖，則n－m＋r＝2，其中，n、m、r分別為G的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)。證明對(duì)G的邊數(shù)m作歸納法。

當(dāng)m＝0時(shí)，由于G是連通圖，所以G為平凡圖，此時(shí)n＝1，r＝1，結(jié)論自然成立。

假設(shè)對(duì)邊數(shù)小于m的連通平面圖結(jié)論成立。下面考慮連通平面圖G的邊數(shù)為m的情況。

設(shè)e是G的一條邊，從G中刪去e后得到的圖記為G?，并設(shè)其結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為n?、m?和r?。對(duì)e分為下列情況來(lái)討論：

若e為割邊，則G?有兩個(gè)連通分支G1和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為ni、mi和ri。顯然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由歸納假設(shè)有n1－m1＋r1＝2，n2－m2＋r2＝2，從而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不為割邊，則n?＝n，m?＝m－1，r?＝r－1，由歸納假設(shè)有n?－m?＋r?＝2，從而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由數(shù)學(xué)歸納法知，結(jié)論成立。

七、（10分）設(shè)函數(shù)g：A→B，f：B→C，則：

(1)f?g是A到C的函數(shù)；

(2)對(duì)任意的x∈A，有f?g(x)＝f(g(x))。

證明(1)對(duì)任意的x∈A，因?yàn)間：A→B是函數(shù)，則存在y∈B使∈g。對(duì)于y∈B，因f：B→C是函數(shù)，則存在z∈C使∈f。根據(jù)復(fù)合關(guān)系的定義，由∈g和∈f得∈g*f，即∈f?g。所以Df?g＝A。

對(duì)任意的x∈A，若存在y1、y2∈C，使得、∈f?g＝g*f，則存在t1使得∈g且∈f，存在t2使得∈g且∈f。因?yàn)間：A→B是函數(shù)，則t1＝t2。又因f：B→C是函數(shù)，則y1＝y(tǒng)2。所以A中的每個(gè)元素對(duì)應(yīng)C中惟一的元素。

綜上可知，f?g是A到C的函數(shù)。

(2)對(duì)任意的x∈A，由g：A→B是函數(shù)，有∈g且g(x)∈B，又由f：B→C是函數(shù)，得∈f，于是∈g*f＝f?g。又因f?g是A到C的函數(shù)，則可寫(xiě)為f?g(x)＝f(g(x))。

八、（15分）設(shè)是的子群，定義R＝{|a、b∈G且a1*b∈H}，則R是G中的－

一個(gè)等價(jià)關(guān)系，且[a]R＝aH。

證明對(duì)于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－

若∈R，則a1*b∈H。因?yàn)镠是G的子群，故(a1*b)1＝b1*a∈H。所以∈R。－－－－

若∈R，∈R，則a1*b∈H，b1*c∈H。因?yàn)镠是G的子群，所以(a1*b)*(b1*c)＝a－－－－

－1*c∈H，故∈R。

綜上可得，R是G中的一個(gè)等價(jià)關(guān)系。

對(duì)于任意的b∈[a]R，有∈R，a1*b∈H，則存在h∈H使得a1*b＝h，b＝a*h，于是b∈aH，－－

[a]R?aH。對(duì)任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H，∈R，故aH?[a]R。所以，[a]R－

＝aH。

第四篇：離散數(shù)學(xué)習(xí)題五

習(xí)題五

1.設(shè)個(gè)體域D={a,b,c}，在D中消去公式?x(F(x)??yG(y))的量詞。甲乙用了不同的演算過(guò)程：

甲的演算過(guò)程如下： ?x(F(x)??yG(y))??x(F(x)?(G(a)?G(b)?G(c)))?(F(a)?(G(a)?G(b)?G(c)))

?(F(b)?(G(a)?G(b)?G(c)))?(F(c)?(G(a)?G(b)?G(c)))?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))乙的演算過(guò)程如下：

?x(F(x)??yG(y))??xF(x)??yG(y)?(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))

顯然，乙的演算過(guò)程簡(jiǎn)單，試指出乙在演算過(guò)程中的關(guān)鍵步驟。

解：乙在演算中的關(guān)鍵步驟是，在演算開(kāi)始就利用量詞轄域收縮與擴(kuò)張等值式，將量詞的轄域縮小，因而演算簡(jiǎn)單。

2.設(shè)個(gè)體域D={a,b,c}，消去下列各式的量詞：

(1)?x?y(F(x)?G(y))(2)?x?y(F(x)?G(y))(3)?xF(x)??yG(y)(4)?（xF(x,y)??yG(y))

解：

（1）(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))（2）(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))（3）(F(a)?F(b)?F(c))?(G(a)?G(b)?G(c))（4）(F(a,y)?F(b,y)?F(c,y))?(G(a)?G(b)?G(c))在（1）（2）（4）中均將量詞的轄域縮小，所以演算結(jié)果都比較簡(jiǎn)單

3.設(shè)個(gè)體域D={1,2}，請(qǐng)給出兩種不同的解釋I1和I2，使得下面公式在I1下都是真命題，而在I2下都是假命題。（1）?x(F(x)?G(x))（2）?x(F(x)?G(x))解：

解釋I1為：個(gè)體為實(shí)數(shù)集合R，F(xiàn)(x)：x為自然數(shù)，G(x)：x為整數(shù)。在I1下，（1）為自然數(shù)都是整數(shù)，（2）為存在整數(shù)為自然數(shù)。他們都是真命題

解釋I2為：個(gè)體域仍為實(shí)數(shù)集R，F(xiàn)(x)：x是無(wú)理數(shù)，G(x)：x能表示成分?jǐn)?shù)，在I2下，（1）為無(wú)理數(shù)都能表示成分?jǐn)?shù)，（2）為存在能表示成分?jǐn)?shù)的無(wú)理數(shù)，他們都是假命題

4.給定公式A??xF(x)??xF(x)

（1）在解釋I1中，個(gè)體域D1={a}，證明公式A在I1下的真值為1.（2）在解釋I2中，個(gè)體域D2={a1,a2,?,an}，n?2,A在I2下的真值還一定是1嗎？為什么？ 解：

（1）在I1下，?xF(x)??xF(x)?F(a)?F(a)??F(a)?F(a)?1（2）在I2下

?xF(x)??xF(x)?(F(a1)?F(a2)???F(an))?(F(a1)?F(a2)???F(an))

為可滿(mǎn)足式，設(shè)F(x)：x為奇數(shù)，ai?i,i?1,2,?n,n?2，此時(shí)，蘊(yùn)涵式前件為真，后件為假，故蘊(yùn)含式為假，若令F(x)；x為整數(shù)，則蘊(yùn)含式前后件均為真，所以（2）中公式在I2下為可滿(mǎn)足式

5.給定解釋I如下：（a）個(gè)體域D={3,4}；（b）f(x)為f(3)?4,f(4)?3;

（c）F(x,y)為F(3,3)?F(4,4)?0,F(3,4)?F(4,3)?1.試求下列公式在I下的真值。

(1)?x?yF(x,y)(2)?x?yF(x,y)(3)?x?yF(x,y)?F(f(x),f(y)))

解：

（1）

?x?yF(x,y)??x(F(x,3)?F(x,4))?(F(3,3)?F(3,4))?(F(4,3)?F(4,4))?1?1?1（2）

??x(F(x,3)?F(x,4))?(F(3,3)?F(3,4))?(F(4,3)?F(4,4)?0（3）

??x((F(x,3)?F(f(x),f(3)))?(F(x,4)?F(f(x),f(4))))?(((F(3,3)?F(f(3),f(3)))?(F(3,4)?F(f(3),f(4))))?(((F(4,3)?F(f(4),f(3)))?(F(4,4)?F(f(4),f(4))))?1

6.甲使用量詞轄域收縮與擴(kuò)張等值式進(jìn)行如下演算

?x(F(x)?G(x,y))??xF(x)?G(x,y)

乙說(shuō)甲錯(cuò)了，乙說(shuō)的對(duì)嗎？為什么？

解：乙說(shuō)的對(duì)，甲錯(cuò)了，全稱(chēng)量詞?的指導(dǎo)變?cè)獂，轄域?yàn)?F(x)?G(x,y))，其中F(x)與G(x,y)都是x的約束變?cè)?，因而不能講量詞的轄域變小

7.請(qǐng)指出下面等值運(yùn)算的兩處錯(cuò)誤

??x?y(F(x)?(G(y)?H(x,y))??x?y(F(x)?(G(y)?H(x,y))??x?y((F(x)?G(y))?H(x,y))

解：

演算的第一步，應(yīng)用量詞轄域收縮與擴(kuò)張算值式時(shí)丟掉了否定連接詞?，演算的第二步，在原錯(cuò)的基礎(chǔ)上又用錯(cuò)了等值式

(F(x)?G(y)?H(x,y))和(F(x)?G(y)?H(x,y))不等值

8.在一階邏輯中將下列命題符號(hào)化，要求用兩種不同的等值形式（1）沒(méi)有小于負(fù)數(shù)的正數(shù)

（2）相等的兩個(gè)角未必都是對(duì)頂角 解：

（1）??x(F(x)?G(x))??x(G(x)??F(x))

其中F(x)：x小于負(fù)數(shù)，G(x)：x是正數(shù)

（2）??x?y(F(x)?F(y)?H(x,y)?L(x,y)??x?y(F(x)?F(y)?H(x,y)??L(x,y))其中F(x)：x是角，H(x,y)：x=y，L(x,y)：x和y是對(duì)頂角

9.設(shè)個(gè)體域D為實(shí)數(shù)集合，命題“有的實(shí)數(shù)既是有理數(shù)又是無(wú)理數(shù)”，這顯然是個(gè)假命題?？墒悄橙藚s說(shuō)這是真命題，其理由如下

設(shè)F(x)：x是有理數(shù)，G(x）：x是無(wú)理數(shù)。?xF(x),?xG(x)都是真命題，于是，?xF(x)??xG(x)??x(F(x)?G(x))由于?xF(x)??xG(x)是真命題，故?x(F(x)?G(x))也是真命題，即有的實(shí)數(shù)是有理數(shù)，也是無(wú)理數(shù)這個(gè)人的結(jié)論對(duì)嗎？為什么？ 解：存在量詞對(duì)?無(wú)分配律

10.在求前束范式時(shí)有人說(shuō)??x(F(x)?G(x,y))已是前束范式，理由是量詞已在公式的前面，他說(shuō)的對(duì)嗎？為什么？

解：在前束范式中，否定聯(lián)結(jié)詞不能在量詞前面出現(xiàn) 11.有人說(shuō)無(wú)法求公式

?x(F(x)?G(x))??xG(x,y)的前束范式，因?yàn)楣街械膬蓚€(gè)量詞的指導(dǎo)變?cè)嗤Ｋ睦碛蓪?duì)嗎？為什么？ 換名規(guī)則可以使兩個(gè)指導(dǎo)變?cè)幌嗤?12.求下列各式的前束范式：(1)?xF(x)??yG(x,y)(2)?x(F(x,y)??yG(x,y,z))(3)?xF(x,y)??xG(x,y)

(4)?x1(F(x1)?G(x1,x2))?(?x2H(x2)??x3L(x2,x3))(5)?x1F(x1,x2)?(F(x1)???x2G(x1,x2))解：

（1）?x?y(F(x)?G(z,y))（2）?x?t(F(x,t)?G(x,t,z))

（3）?x1?x2?x3?x4((F(x1,y)?G(x2,y))?(G(x3,y)?F(x4,y)))（4）?y1?y2?y3((F(y1)?G(y1,x2))?(H(y2)?L(x2,y3)))（5）?y1?y2(F(y1,x2)?(F(x1)??G(x1,y2)))

13.將下列命題符號(hào)化，要求符號(hào)化的公式權(quán)威前束范式：（1）有點(diǎn)火車(chē)比有的汽車(chē)跑的快（2）有的火車(chē)比所有的汽車(chē)跑的快

（3）說(shuō)有的火車(chē)比所有汽車(chē)跑得快是不對(duì)的（4）說(shuō)有的飛機(jī)比有的汽車(chē)慢也是不對(duì)的 解：

（1）?x?y(F(x)?G(y)?H(x,y))其中F(x)：x是汽車(chē) G(y):y是 火車(chē) H(x,y)：x比y跑得快（2）?x?y(F(x)?(G(y)?H(x,y)))其中F(x)：x是火車(chē) G(y):y是 汽車(chē) H(x,y)：x比y跑得快

（3)?x?y(F(x)?G(y)??H(x,y))其中F(x)：x是火車(chē) G(y):y是 汽車(chē)H(x,y)：x比y跑得快

（4）?x?y(F(x)?G(y)??H(x,y))其中F(x)：x是飛機(jī) G(y):y是 汽車(chē) H(x,y)：x比y跑得慢

14.在自然推理系統(tǒng)F中，指出下面各證明序列中的錯(cuò)誤：（1）①F(x)??xG(x)前提引入

②F(c)?G(c)①EI規(guī)則（2）①?xF(x)??yG(y)前提引入

②F(a)?F(b)①EI規(guī)則（3）①F(y)?G(y)前提引入

②?x(F(x)?G(x))①EG規(guī)則（4）①F(a)?F(b)前提引入

②?x(F(x)?G(x))①EG規(guī)則（5）①F(c)?G(c)前提引入

②?x(F(x)?G(x))①UG規(guī)則

解：（1）對(duì)F(x)??xG(x)不能使用EI規(guī)則，它不是前束范式，首先化成前束范式F(x)??xG(x)??x(F(y)?G(x))，因?yàn)榱吭~轄域(F(y)?G(x)中，除了x還有自由出現(xiàn)的y所以不能用EI規(guī)則

（2）對(duì)?xF(x)??yG(y)也應(yīng)該先化成前束范式才能消去量詞，其前束范式為?x?y(F(x)?G(y))，要消去量詞，既要用UI規(guī)則，又要用EI規(guī)則（3）這里A(y)=F(y)?G(y)滿(mǎn)足要求

（4）這里，使F(a)為真的a不一定使G(a)為真，同樣的，使G(b)為真的b不一定使F(b)為真

（5）這里，c為個(gè)體常項(xiàng)，不能對(duì)F(c)?G(c)引入全稱(chēng)量詞 15.在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明：（1）前提：?xF(x)??y((F(y)?G(y))?R(y)),?xF(x)

結(jié)論：?xR(x)

（2）前提：?x(F(x)?(G(a)?R(x))),?xF(x)

結(jié)論：?x(F(x)?R(x))（3）前提：?x(F(x)?G(x)),??xG(x)

結(jié)論：?xF(x)

（4）前提：?x(F(x)?G(x)),?x(?G(x)??R(x)),?xR(x)

結(jié)論：?xF(x)

（1）證明：1 ?xF(x)

前提引入 ?xF(x)??y((F(y)?G(y))?R(y))

前提引入

?y((F(y)?G(y))?R(y)

2假言推理

F(c)EI(F(c)?G(c))?R(c)

UI F(c)?G(c)

附加

R(c)6假言推理

?xR(x)

7EG

（2）證明：1 ?xF(x)

前提引入

?x(?H(x)),?x?F(x)?x(F(a)?G(a))?),G(a)I(y)H(a)????x(F(x)?(G(a)?R(x)))

?x(G(a)?H(a)?I(a))前提引入 F(c)EI F(c)?(G(a)?R(c))

UI G(a)?R(c)4假言推理

R(c)

5化簡(jiǎn)

F(c)?R(c)6合取

?x(F(x)?R(x))

7EG

（3）證明：1 ??xF(x)

前提引入?x?F(x)

1置換?F(c)

2UI

?x(F(x)?G(x))

前提引入F(c)?G(c)

4UI

6F(c)5析取三段論?xF(x)

6EG(4)證明：1 ?x(F(x)?G(x))

前提引入

F(y)?G(y)UI ?x(?G(x)??R(X))

前提引入

?G(y)??R(y)

UI ?xR(x)

前提引入

R(y)

5UI ?G(y)

6析取三段論

8F(y)

27析取三段論

?xF(x)

UG 16.找一個(gè)解釋I，在I下，使得?xF(x)??xG(x)為真，而使得?x(F(x)??G(x))為假，從而說(shuō)明?xF(x)??xG(x)??x(F(x)??G(x))。解：取個(gè)體域?yàn)樽匀粩?shù)集合N，F(xiàn)(x):x為奇數(shù)，G(x):x 為偶數(shù)。顯然在以上解釋下?xF(x)??xG(x)為真而?x(F(x)?G(x))為假。

17.給定推理如下：

前提：?x(F(x)??G(x)),?x(H(x)?G(x))

結(jié)論：?x(H(x)??F(x))。

有些人給出的證明如下：

證明：

①?xH(x)附加前提引入

②H(y)

③?x(H(x)?G(x))

④H(y)?G(y)

⑤G(y)

⑥?x(F(x)??G(x))

⑦F(y)??G(y)

⑧?F(y)

⑨?x?F(x)

解：根據(jù)16題可知兩公式并不等價(jià)。

①UI 前提引入 ③UI ②⑤假言推理 前提引入 ⑥UI ⑤⑦拒取式 ⑧UG 并且說(shuō)，由附加前提證明法可知，推理正確，請(qǐng)指出以上證明的錯(cuò)誤。18.給出上題（17）推理的正確證明（注意，不能使用附加前提證明法）。

證明：1 ?x(F(x)??G(x))

前提引入

?x(H(x)?G(x))

前提引入

F(y)??G(y)UI H(y)?G(y)

2UI G(y)??F(y)

3置換H(y)??F(y)5假言三段論?x(H(x)??F(x))UG

19.在自然推理系統(tǒng)F中，構(gòu)造下列推理的證明：

前提：?xF(x)??xG(x)

結(jié)論：?x(F(x)?G(x))

證明：1?xF(x)??xG(x)

前提引入 ?yF(y)??xG(x)

換名規(guī)則

?y?x(F(x)?G(x))化簡(jiǎn)

?x(F(x)?G(x))EI

20.在自然推理系統(tǒng)F中，構(gòu)造下列推理的證明（可以使用附加前提證明法）：（1）前提：?x(F(x)?G(x))

結(jié)論：?xF(x)??xG(x)（2）前提：?x(F(x)?G(x))

結(jié)論：??xF(x)??xG(x)

證明：（1）.1?xF(x)

附加前提引入

F(y)UI ?x(F(x)?G(x))

前提引入

F(y)?G(y)

3UI G(y)3假言推理

?xG(x)

（2）1 ??xF(x)

附加前提引入?x?F(x)

置換原則?F(c)

2EI

?x(F(x)?G(x))

前提引入

F(c)?G(c)

UI

G(c)

5析取三段論?xG(x)

EG 21.在自然推理系統(tǒng)中，構(gòu)造下面推理的證明：

沒(méi)有白色的烏鴉，北京鴨都是白色的。因此，北京鴨都不是烏鴉。

設(shè)F(x):x是烏鴉，G(x)：x是北京鴨，H(x):x是白色的。前提 ??x(F(x)?H(x)),?x(G(x)?H(x))結(jié)論 ?x(G(x)??F(x))

證明：1 ??x(F(x)?H(x))

前提引入 2 ?x?(F(x)?H(x))

置換原則 3 ?x(?F(x)??H(x))

置換原則 4 ?x(?H(x)??F(x))

H(y)??F(y)

4UI 6 ?x(G(x)?H(x))

前提引入 7 G(y)?H(y)

5UI 8 G(y)??F(y)

7假言三段論 9 ?x(G(x)??F(x))

8UG 22.在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明：

(1)偶數(shù)都能被2整除。6是偶數(shù)。所以6能被2整除。

(2)凡大學(xué)生都是勤奮的。王曉山不勤奮，所以王曉山不是大學(xué)生。

（1）設(shè)F(x):x為偶數(shù)，G(x)：x能被2整除 前提 ?x(F(x)?G(x)),F(6)結(jié)論 G(6)證明：1 ?x(F(x)?G(x))

前提引入

F(6)?G(6)

1UI F(6)

前提引入 G(6)

3假言推理

(2)設(shè)F(x):x是大學(xué)生，G(x)：x是勤奮的，a 王曉山 前提 ?x(F(x)?G(x)),?G(a)，結(jié)論 ?F(a)

證明：1 ?x(F(x)?G(x))

前提引入

F(a)?G(a)

1UI ?G(a)

前提引入

?F(a)3 據(jù)取式

23.在自然推理系統(tǒng)F中，證明下面推理：

（1）每個(gè)有理數(shù)都是實(shí)數(shù)。有的有理數(shù)是整數(shù)。因此，有的實(shí)數(shù)是整數(shù)9（2）有理數(shù)，無(wú)理數(shù)都是實(shí)數(shù)。虛數(shù)不是實(shí)數(shù)。因此，虛數(shù)既不是有理數(shù)也不是無(wú)理數(shù)。

（1）設(shè)F(x):x是有理數(shù)，G(x)：x實(shí)數(shù)，H(x):x是整數(shù)

前提 ?x(F(x)?G(x))，?x(F(x)?H(x))

結(jié)論 ?x(G(x)?H(x))

(2)設(shè)F(x):x是有理數(shù)，G(x)：x是無(wú)理數(shù)，H(x):x是實(shí)數(shù)，I(x):x是虛數(shù) 前提 ?x((F(x)?G(x))?H(x)),?x(I(x)??H(x))結(jié)論 ?x(I(x)?(?F(x)?G(x)))

證明：1 ?x(I(x)??H(x))

前提引入

I(y)??H(y)

UI ?x((F(x)?G(x))?H(x)), 前提引入

4(F(y)?G(y))?H(y)UI ?H(y)?(?F(y)??G(y))

置換 I(y)?(?F(y)??G(y))

5假言三段論

?x(I(x)?(?F(x)??G(x))

UG 24.在自然推理系統(tǒng)F中，構(gòu)造下面推理的證明：

每個(gè)喜歡不行的人都不喜歡騎自行車(chē)。每個(gè)人或者喜歡騎自行車(chē)或者喜歡乘汽車(chē)。有的人不喜歡乘汽車(chē)，所以有的人不喜歡步行。（個(gè)體域?yàn)槿祟?lèi)集合）

設(shè)F(x):x喜歡步行，G(x)：x喜歡騎自行車(chē)，H(x):x喜歡乘汽車(chē) 前提 ?x(F(x)?G(x)，?x(G(x)?H(x)),??xH(x)結(jié)論 ??xF(x)

證明：1 ??xH(x)

前提引入

?H(c)

UI x(G(x)?H(x))

前提引入

G(c)?H(c)UI G(c)

4析取三段論

?x(F(x)??G(x))

前提引入

F(c)??G(c)

UI

?F(c)

57拒取式

?x?F(x)

8UG 25.在自然推理系統(tǒng)F中，構(gòu)造下列推理的證明（個(gè)體域?yàn)槿祟?lèi)集合）：

每個(gè)科學(xué)工作者都是刻苦鉆研的，每個(gè)刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。王大海是科學(xué)工作者，并且是聰明的，所以王大海在他的事業(yè)中將獲得成功。

設(shè)F(x):x是科學(xué)工作者，G(x)：x是刻苦鉆研的，H(x):x是聰明的，I(x):x在事業(yè)中獲得成功

前提 ?x(F(x)?G(x))，?x(G(x)?H(x)?I(x))，a:王大海，F(xiàn)(a),H(a)結(jié)論 I(a)證明：1 F(a)

前提引入

?x(F(x)?G(x))

前提引入

F(a)?G(a)

2UI G(a)3假言推論

H(a)

前提引入 ?x(G(x)?H(x)?I(x))

前提引入

G(a)?H(a)?I(a)

6UI G(a)?H(a)5合取

I(a)8假言推論

第五篇：離散數(shù)學(xué)課后習(xí)題答案

第一章部分課后習(xí)題參考答案 設(shè)p、q的真值為0；r、s的真值為1，求下列各命題公式的真值。

（1）p∨(q∧r)? 0∨(0∧1)?0（2）（p?r）∧(﹁q∨s)?（0?1）∧(1∨1)?0∧1?0.（3）（?p∧?q∧r）?(p∧q∧﹁r)?（1∧1∧1）?(0∧0∧0)?0(4)（?r∧s）→(p∧?q)?（0∧1）→(1∧0)?0→0?1 17．判斷下面一段論述是否為真：“?是無(wú)理數(shù)。并且，如果3是無(wú)理數(shù)，則2也是無(wú)理數(shù)。另外，只有6能被2整除，6才能被4整除?！?/p>

答：p: ?是無(wú)理數(shù)

q: 3是無(wú)理數(shù)

0

r: 2是無(wú)理數(shù)

s: 6能被2整除t: 6能被4整除

0

命題符號(hào)化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類(lèi)型：（4）(p→q)→(?q→?p)（5）(p∧r)?(?p∧?q)（6）((p→q)∧(q→r))→(p→r)答：

（4）

p

q

p→q

?q

?p

?q→?p

(p→q)→(?q→?p)

0

0

0

0

0

0

0

0

0

0

所以公式類(lèi)型為永真式

（5）公式類(lèi)型為可滿(mǎn)足式（方法如上例）（6）公式類(lèi)型為永真式（方法如上例）

第二章部分課后習(xí)題參考答案

3.用等值演算法判斷下列公式的類(lèi)型，對(duì)不是重言式的可滿(mǎn)足式，再用真值表法求出成真賦值.1(1)?(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1

所以公式類(lèi)型為永真式

(3)P

q

r

p∨q

p∧r

（p∨q）→(p∧r)0

0

0

0

0

0

0

0

0

0

0

0

0 0

0

0 1

0

0

0

0 1

0

1

0

0

0 1

所以公式類(lèi)型為可滿(mǎn)足式

4.用等值演算法證明下面等值式：(2)(p→q)∧(p→r)?(p→(q∧r))(4)(p∧?q)∨(?p∧q)?(p∨q)∧?(p∧q)證明（2）(p→q)∧(p→r)?(?p∨q)∧(?p∨r)??p∨(q∧r))?p→(q∧r)（4）(p∧?q)∨(?p∧q)?(p∨(?p∧q))∧(?q∨(?p∧q)?(p∨?p)∧(p∨q)∧(?q∨?p)∧(?q∨q)?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q)5.求下列公式的主析取范式與主合取范式，并求成真賦值

(1)(?p→q)→(?q∨p)(2)?(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：

（1）主析取范式

(?p→q)→(?q?p)?????(p?q)?(?q?p)(?p??q)?(?q?p)(?p??q)?(?q?p)?(?q??p)?(p?q)?(p??q)(?p??q)?(p??q)?(p?q)?m0?m2?m3

?∑(0,2,3)主合取范式：

(?p→q)→(?q?p)???(p?q)?(?q?p)(?p??q)?(?q?p)?(?p?(?q?p))?(?q?(?q?p))?1?(p??q)?(p??q)? M1

?∏(1)(2)主合取范式為：

?(p→q)?q?r??(?p?q)?q?r ?(p??q)?q?r?0 所以該式為矛盾式.主合取范式為∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式為 0(3)主合取范式為：

(p?(q?r))→(p?q?r)??(p?(q?r))→(p?q?r)??(?p?(?q??r))?(p?q?r)(?p?(p?q?r))?((?q??r))?(p?q?r))?1?1 ?1 所以該式為永真式.永真式的主合取范式為 1 主析取范式為∑(0,1,2,3,4,5,6,7)第三章部分課后習(xí)題參考答案

14.在自然推理系統(tǒng)P中構(gòu)造下面推理的證明：(2)前提：p?q,?(q?r),r 結(jié)論：?p(4)前提：q?p,q?s,s?t,t?r 結(jié)論：p?q

證明：（2）

①?(q?r)前提引入 ②?q??r ①置換 ③q??r ②蘊(yùn)含等值式 ④r 前提引入 ⑤?q ③④拒取式 ⑥p?q 前提引入 ⑦￢p（3）⑤⑥拒取式

證明（4）：

①t?r 前提引入 ②t ①化簡(jiǎn)律 ③q?s 前提引入 ④s?t 前提引入

⑤q?t ③④等價(jià)三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡(jiǎn) ⑧q ②⑥ 假言推理 ⑨q?p 前提引入 ⑩p ⑧⑨假言推理(11)p?q ⑧⑩合取

15在自然推理系統(tǒng)P中用附加前提法證明下面各推理：

4(1)前提：p?(q?r),s?p,q 結(jié)論：s?r 證明

①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理

16在自然推理系統(tǒng)P中用歸謬法證明下面各推理：

(1)前提：p??q,?r?q,r??s 結(jié)論：?p 證明：

①p 結(jié)論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡(jiǎn)律 ⑥r(nóng)?￢s 前提引入 ⑦r ⑥化簡(jiǎn)律 ⑧r?﹁r ⑤⑦ 合取

由于最后一步r?﹁r 是矛盾式,所以推理正確.