第一篇：屈婉玲版離散數學課后習題答案【1】
屈婉玲版離散數學課后習題答案
第一章部分課后習題參考答案 設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．判斷下面一段論述是否為真：“?是無理數。并且，如果3是無理數，則2也是無理數。另外6能被2整除，6才能被4整除。”
答：p: ?是無理數
q: 3是無理數
0
r: 2是無理數
s: 6能被2整除t: 6能被4整除
0
命題符號化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類型：（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
所以公式類型為永真式 //最后一列全為1（5）公式類型為可滿足式（方法如上例）//最后一列至少有一個1（6）公式類型為永真式（方法如上例）// 第二章部分課后習題參考答案
3.用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.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
所以公式類型為永真式
(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
所以公式類型為可滿足式
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)屈婉玲版離散數學課后習題答案
第三章部分課后習題參考答案
14.在自然推理系統P中構造下面推理的證明：(2)前提：p?q,?(q?r),r 結論：?p(4)前提：q?p,q?s,s?t,t?r 結論：p?q
證明：（2）
①?(q?r)前提引入 ②?q??r ①置換
③q??r ②蘊含等值式 ④r 前提引入 ⑤?q ③④拒取式 ⑥p?q 前提引入 ⑦￢p ⑤⑥拒取式
證明（4）：
①t?r 前提引入 ②t ①化簡律 ③q?s 前提引入 ④s?t 前提引入
⑤q?t ③④等價三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡 ⑧q ②⑥ 假言推理 ⑨q?p 前提引入 ⑩p ⑧⑨假言推理(11)p?q ⑧⑩合取
15在自然推理系統P中用附加前提法證明下面各推理：
屈婉玲版離散數學課后習題答案
(1)前提：p?(q?r),s?p,q 結論：s?r 證明
①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理
16在自然推理系統P中用歸謬法證明下面各推理：
(1)前提：p??q,?r?q,r??s 結論：?p 證明：
①p 結論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡律 ⑥r?￢s 前提引入 ⑦r ⑥化簡律 ⑧r?﹁r ⑤⑦ 合取
由于最后一步r?﹁r 是矛盾式,所以推理正確.
第二篇：屈婉玲版離散數學課后習題答案【3】
屈婉玲版離散數學課后習題答案 第四章部分課后習題參考答案
3.在一階邏輯中將下面將下面命題符號化,并分別討論個體域限制為(a),(b)條件時命題的真值:(1)對于任意x,均有錯誤！未找到引用源。2=(x+錯誤！未找到引用源。)(x錯誤！未找到引用源。).(2)存在x,使得x+5=9.其中(a)個體域為自然數集合.(b)個體域為實數集合.解：
F(x): 錯誤！未找到引用源。2=(x+錯誤！未找到引用源。)(x錯誤！未找到引用源。).G(x): x+5=9.(1)在兩個個體域中都解釋為?xF(x)，在（a）中為假命題，在(b)中為真命題。
(2)在兩個個體域中都解釋為?xG(x)，在（a）(b)中均為真命題。
4.在一階邏輯中將下列命題符號化:(1)沒有不能表示成分數的有理數.(2)在北京賣菜的人不全是外地人.解:(1)F(x): x能表示成分數 H(x): x是有理數
命題符號化為: ??x(?F(x)?(2)F(x): x是北京賣菜的人 H(x): x是外地人 命題符號化為: ??x(F(x)?H(x))H(x))
5.在一階邏輯將下列命題符號化:(1)火車都比輪船快.(3)不存在比所有火車都快的汽車.解:(1)F(x): x是火車;G(x): x是輪船;H(x,y): x比y快 屈婉玲版離散數學課后習題答案 命題符號化為: ?x?y((F(x)?G(y))?H(x,y))
(2)(1)F(x): x是火車;G(x): x是汽車;H(x,y): x比y快 命題符號化為: ??y(G(y)??x(F(x)9.給定解釋I如下:(a)個體域D為實數集合R.(b)D中特定元素錯誤！未找到引用源。=0.(c)特定函數錯誤！未找到引用源。(x,y)=x錯誤！未找到引用源。y,x,y?未找到引用源。.(d)特定謂詞錯誤！未找到引用源。(x,y):x=y,錯誤！未找到引用源。(x,y):x 錯誤！.說明下列公式在I下的含義,并指出各公式的真值:(1)?x?y(G(x,y)(2)??F(x,y)) ?x?y(F(f(x,y),a)?G(x,y))答:(1)對于任意兩個實數x,y,如果x （a）個體域D=N(N為自然數集合).（b）D中特定元素錯誤！未找到引用源。=2.（c）D上函數錯誤！未找到引用源。=x+y,錯誤！未找到引用源。(x,y)=xy.（d）D上謂詞錯誤！未找到引用源。(x,y):x=y.說明下列各式在I下的含義，并討論其真值.(1)錯誤！未找到引用源。xF(g(x,a),x)(2)錯誤！未找到引用源。x錯誤！未找到引用源。y(F(f(x,a),y)→F(f(y,a),x)答:(1)對于任意自然數x, 都有2x=x, 真值0.(2)對于任意兩個自然數x,y,使得如果x+2=y, 那么y+2=x.真值0.11.判斷下列各式的類型:(1)錯誤！未找到引用源。 (3)錯誤！未找到引用源。yF(x,y).解:(1)因為 p?(q?p)??p?(?q?p)?1 為永真式； 所以 錯誤！未找到引用源。為永真式； 屈婉玲版離散數學課后習題答案(3)取解釋I個體域為全體實數 F(x,y)：x+y=5 所以,前件為任意實數x存在實數y使x+y=5，前件真； 后件為存在實數x對任意實數y都有x+y=5，后件假，] 此時為假命題 再取解釋I個體域為自然數N，F(x,y)：:x+y=5 所以,前件為任意自然數x存在自然數y使x+y=5，前件假。此時為假命題。 此公式為非永真式的可滿足式。13.給定下列各公式一個成真的解釋，一個成假的解釋。 (1)錯誤！未找到引用源。(F(x)錯誤！未找到引用源。 (2)錯誤！未找到引用源。x(F(x)錯誤！未找到引用源。G(x)錯誤！未找到引用源。H(x))解:(1)個體域:本班同學 F(x)：x會吃飯, G(x)：x會睡覺.成真解釋 F(x)：x是泰安人,G(x)：x是濟南人.（2）成假解釋(2)個體域:泰山學院的學生 F(x)：x出生在山東,G(x):x出生在北京,H(x):x出生在江蘇,成假解釋.F(x)：x會吃飯,G(x)：x會睡覺,H(x)：x會呼吸.成真解釋.第五章部分課后習題參考答案 5.給定解釋Ｉ如下:(a)個體域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錯誤！未找到引用源。.試求下列公式在Ｉ下的真值.(1)?x?yF(x,y) ?F(f(x),f(y)))(3)?x?y(F(x,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)) ?(0?1)?(1?0)?1 (2)?x?y(F(x,y)?F(f(x),f(y))) ??x((F(x,3)?F(f(x),f(3)))?(F(x,4)?F(f(x),f(4)))) ??x((F(x,3)?F(f(x),4))?(F(x,4)?F(f(x),3)))?((F(3,3)?F(f(3),4))?(F(3,4)?F(f(3),3))) ?((F(4,3)?F(f(4),4))?(F(4,4)?F(f(4),3)))?((0?F(4,4))?(F(3,4)?F(4,3)))?((1?F(3,4))?(0?F(3,3)))?(0?0)?(1?1)?(1?1)?(0?0)?1 12.求下列各式的前束范式。 (1)?xF(x)??yG(x,y) (5)?x1F(x1,x2)解:(1)?xF?(H(x1)???x2G(x1,x2))(本題課本上有錯誤)(x)??yG(x,y)??xF(x)??yG(t,y)??x?y(F(x)?G(t,y)) (5)?x1F(x1,x2)?(H(x1)???x2G(x1,x2)) ??x1F(x1,x2)?(H(x3)??x2?G(x3,x2))??x1F(x1,x4)??x2(H(x3)??G(x3,x2))??x1?x2(F(x1,x4)?(H(x3)??G(x3,x2)))15.在自然數推理系統F中,構造下面推理的證明:(1)前提: ?xF(x)??y((F(y)?G(y))?R(y)),?xF(x) 結論: ?xR(x)(2)前提: ?x(F(x)→(G(a)∧R(x))), 錯誤！未找到引用源。xF(x)結論:錯誤！未找到引用源。x(F(x)∧R(x))證明(1)①?xF(x)前提引入 ②F(c)①EI ③?xF(x)??y((F(y)?G(y))?R(y))G(y))?R(y))前提引入 ④?y((F(y)? ①③假言推理 ⑤(F(c)∨G(c))→R(c))④UI 屈婉玲版離散數學課后習題答案 ⑥F(c)∨G(c)②附加 ⑦R(c)⑤⑥假言推理 ⑧?xR(x)⑦EG(2)①?xF(x)前提引入 ②F(c)①EI ③?x(F(x)→(G(a)∧R(x)))④F(c)→(G(a)∧R(c))⑤G(a)∧R(c)⑥R(c)⑦F(c)∧R(c)⑧?x(F(x)∧R(x)) 前提引入 ③UI ②④假言推理⑤化簡 ②⑥合取引入 屈婉玲版離散數學課后習題答案 第十章部分課后習題參考答案 4．判斷下列集合對所給的二元運算是否封閉：（1）整數集合Z和普通的減法運算。 封閉,不滿足交換律和結合律，無零元和單位元 （2）非零整數集合錯誤！未找到引用源。普通的除法運算。不封閉 （3）全體n?n實矩陣集合錯誤！未找到引用源。（R）和矩陣加法及乘法運算，其中n錯誤！未找到引用源。2。 封閉 均滿足交換律，結合律，乘法對加法滿足分配律； 加法單位元是零矩陣，無零元； 乘法單位元是單位矩陣，零元是零矩陣； （4）全體n?n實可逆矩陣集合關于矩陣加法及乘法運算，其中n錯誤！未找到引用源。2。不封閉 （5）正實數集合錯誤！未找到引用源。和錯誤！未找到引用源。運算，其中錯誤！未找到引用源。運算定義為： 錯誤！未找到引用源。 不封閉 因為 1?1?1?1?1?1??1?R? （6）n錯誤！未找到引用源。關于普通的加法和乘法運算。封閉，均滿足交換律，結合律，乘法對加法滿足分配律 加法單位元是0，無零元； 乘法無單位元（n?1），零元是 0；n?1單位元是1 （7）A = {a1,a2,?,an} 錯誤！未找到引用源。n錯誤！未找到引用源。運算定義如下： 錯誤！未找到引用源。 封閉 不滿足交換律，滿足結合律，（8）S = 錯誤！未找到引用源。關于普通的加法和乘法運算。封閉 均滿足交換律，結合律，乘法對加法滿足分配律（9）S = {0,1},S是關于普通的加法和乘法運算。 加法不封閉，乘法封閉；乘法滿足交換律，結合律 （10）S = 錯誤！未找到引用源。,S關于普通的加法和乘法運算。屈婉玲版離散數學課后習題答案 加法不封閉，乘法封閉，乘法滿足交換律，結合律 5．對于上題中封閉的二元運算判斷是否適合交換律，結合律，分配律。 見上題 7． 設 * 為Z?錯誤！未找到引用源。上的二元運算?x,y?Z?，X * Y = min(x，y),即x和y之中較小的數.(1)求4 * 6，7 * 3。 4，(2)* 在Z上是否適合交換律，結合律，和冪等律？ 滿足交換律，結合律，和冪等律 (3)求*運算的單位元，零元及Z?中所有可逆元素的逆元。單位元無，零元1, 所有元素無逆元 8．S?Q?Q? Q為有理數集，*為S上的二元運算，錯誤！未找到引用源。 < a，b >* （1）*運算在S上是否可交換，可結合？是否為冪等的？ 不可交換： （2）*運算是否有單位元，零元？ 如果有請指出，并求S中所有可逆元素的逆元。設 屈婉玲版離散數學課后習題答案 設 錯誤！未找到引用源。 10．令S={a，b}，S上有四個運算：*，錯誤！未找到引用源。分別有表10.8確定。 (a) (b) (c) (d) (1)這4個運算中哪些運算滿足交換律，結合律，冪等律？(a)交換律，結合律，冪等律都滿足，零元為a,沒有單位元；(b)滿足交換律和結合律，不滿足冪等律，單位元為a,沒有零元 a?1?a,b?1?b (c)滿足交換律,不滿足冪等律,不滿足結合律 a?(b?b)a?(b?b)?a?a?b,?(a?b)?b(a?b)?b?a?b?a 沒有單位元, 沒有零元 (d)不滿足交換律，滿足結合律和冪等律 沒有單位元, 沒有零元 (2)求每個運算的單位元，零元以及每一個可逆元素的逆元。見上 16．設V=〈 N，+，錯誤！未找到引用源。〉，其中+，錯誤！未找到引用源。分別代表普通加法與乘法，對下面給定的每個集合確定它是否構成V的子代數，為什么？ （1）S1=錯誤！未找到引用源。是 屈婉玲版離散數學課后習題答案 （2）S2=錯誤！未找到引用源。 不是 加法不封閉（3）S3 = {-1，0，1} 不是，加法不封閉 第十一章部分課后習題參考答案 8.設S={0，1，2，3}，為模4乘法，即 y=(xy)mod 4 “?x,y∈S, x問〈S，〉是否構成群？為什么？ y=(xy)mod 4?S解：(1)?x,y∈S, x,是S上的代數運算。 (2)?x,y,z∈S,設xy=4k+r 0(xy)z =((xy)mod 4) ?r?3 z=rz=(rz)mod 4 =(4kz+rz)mod 4=((4k+r)z)mod 4 =(xyz)mod 4 同理x(yz)=(xyz)mod 4 y)z = x1)=(1 (y z)，結合律成立。所以，(x(3)?x∈S,(x(4)1?1?1,3?1x)=x,，所以1是單位元。 ?3, 0和2沒有逆元 所以，〈S，〉不構成群 9.設Z為整數集合，在Z上定義二元運算。如下： ” ?x,y∈Z,xoy= x+y-2 問Z關于o運算能否構成群？為什么？ 解：(1)?x,y∈Z, xoy= x+y-2?(2)?x,y,z∈Z,(xoy)oz =(x+y-2)oz=(x+y-2)+z-2=x+y+z-4 同理(xoy)oz= xo(yoz)，結合律成立。 (3)設e是單位元，?x∈Z, xoe= eox=x,即x+e-2= e+x-2=x, e=2(4)?x∈Z , 設x的逆元是y, xoy= yox=e, 即x+y-2=y+x-2=2, 所以，x?1?y?4?xZ,o是Z上的代數運算。 所以〈Z，o〉構成群 屈婉玲版離散數學課后習題答案 11.設??1G=?????00???,1??1???00???,?1???1???00???,1???1???00??????1??，證明G關于矩陣乘法構成一個群． 解：(1)?x,y∈G, 易知xy∈G,乘法是Z上的代數運算。 (2)矩陣乘法滿足結合律(3)設???1?00???1?是單位元，(4)每個矩陣的逆元都是自己。所以G關于矩陣乘法構成一個群． 14.設G為群，且存在a∈G,使得 G={ak∣k∈Z} 證明：G是交換群。證明:?x,y∈G，設x xy?aa?aklk?l?a,l?kky?a?aall，則 ?yx??ak 所以，G是交換群 17.設G為群，證明e為G中唯一的冪等元。證明:設e0 18.設G為群，a,b,c∈G,證明 ∣abc∣=∣bca∣=∣cab∣ 證明：先證設(abc設(abc)k?G也是冪等元，則e02?e0，即e02?e0e，由消去律知e0?e)k?e?(bca)k?e ?e,則(abc)(abc)(abc)?(abc)?e，a(bc)(abc)(abc)a?(bc)aa?1即 ?e 左邊同乘a?1，右邊同乘a得 (bca)(bca)(bca)?(bca)?(bac)kkk?a?1ea?e 反過來，設(bac)?e,則(abc)?e.由元素階的定義知，∣abc∣=∣bca∣，同理∣bca∣=∣cab∣ 屈婉玲版離散數學課后習題答案 19.證明：偶數階群G必含2階元。 證明：設群G不含2階元，?a?G，當a?e時，a是一階元，當a?e時，a至少是3階元,因為群G時有限階的，所以a是有限階的，設a是k階的,則a?1也是k階的，所以高于3階的元成對出現的，G不含2階元，G含唯一的1階元e,這與群G是偶數階的矛盾。所以，偶數階群G必含2階元 20.設G為非Abel群，證明G中存在非單位元a和b,a≠b,且ab=ba.證明：先證明G含至少含3階元。 若G只含1階元,則G={e},G為Abel群矛盾； 若G除了1階元e外,其余元a均為2階元，則a2?a,b?G,a?1?e?1，a?1?a，?a,b?1?b,(ab)?1?ab,所以ab?a?1b?(ba)?1?ba與G為Abel群矛盾； 所以，G含至少含一個3階元，設為a，則a令b?a2?a2，且a2a?aa2。的證。 21.設G是Mn(R)上的加法群，n≥2，判斷下述子集是否構成子群。（1）全體對稱矩陣 是子群（2）全體對角矩陣 是子群 （3）全體行列式大于等于0的矩陣.不是子群（4）全體上（下）三角矩陣。是子群 22.設G為群，a是G中給定元素，a的正規化子N（a）表示G中與a可交換的元素構成的集合，即 N（a）={x∣x∈G∧xa=ax} 證明N（a）構成G的子群。證明：ea=ae,e??x,y?N(a),N(a)?? ,所以xy?1則ax?xa,ay?ya a(xy)?(ax)y?(xa)y?x(ay)?x(ya)?(xy)a?N(a) 由ax?xa，得x?1axx?1?x?1xax?1,x?1ae?eax，即x?1a?ax?1，所以x?1?N(a) 所以N（a）構成G的子群 31.設?1是群G1到G2的同態，?2是G2到G3的同態，證明?1??2 是G1到G3的同態。 屈婉玲版離散數學課后習題答案 證明：有已知?1是G1到G2的函數，?2是G2到G3的函數，則?1·?2是G1到G3的函數。 ?a,b?G1,(?1??2)(ab)?(?2(?1(a)))(?2(?1(b)))??2(?1(ab))??2(?1(a)?1(b))?(?1??2)(a)(?1??2)(b) 所以:?1·?2是G1到G3的同態。 33.證明循環群一定是阿貝爾群，說明阿貝爾群是否一定為循環群，并證明你的結論。 證明：設G是循環群,令G=,?x,y?G,令xxy?aa?aklk?l?a,y?akl,那么 ?al?k?aalk?yx,G是阿貝爾群 克萊因四元群,G?{e,a,b,c} ?eabceeabcaaecbbbceaccbae 是交換群,但不是循環群,因為e是一階元，a,b,c是二階元。36.設?,?是5元置換，且 ?????2?12134455??1????，??3??32435415??? 2?(1)計算??(2)將??,??,??1?1,??1,??1??； ,?,??1??表示成不交的輪換之積。 (3)將（2）中的置換表示成對換之積，并說明哪些為奇置換，哪些為偶置換。解：(1)??????4??1?125353343425???1? ??????4?1?12324313142435???5?5???2? ??1?1????42531425??? 3??1????2215??? ?4??1??????5?1?1 (2)??(3)?? ??1?(1425)??(14253)????(143)(25) ?(14)(12)(15)奇置換，?(14)(12)(15)(13)偶置換 ?(14)(13)(25)奇置換 ??1?? 第一章部分課后習題參考答案 設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．判斷下面一段論述是否為真：“?是無理數。并且，如果3是無理數，則2也是無理數。另外6能被2整除，6才能被4整除。” 答：p: ?是無理數 q: 3是無理數 0 r: 2是無理數 s: 6能被2整除t: 6能被4整除 0 命題符號化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類型：（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 所以公式類型為永真式 //最后一列全為1（5）公式類型為可滿足式（方法如上例）//最后一列至少有一個1（6）公式類型為永真式（方法如上例）// 第二章部分課后習題參考答案 3.用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.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 所以公式類型為永真式 (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 所以公式類型為可滿足式 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)第三章部分課后習題參考答案 14.在自然推理系統P中構造下面推理的證明：(2)前提：p?q,?(q?r),r 結論：?p(4)前提：q?p,q?s,s?t,t?r 結論：p?q 證明：（2） ①?(q?r)前提引入 ②?q??r ①置換 ③q??r ②蘊含等值式 ④r 前提引入 ⑤?q ③④拒取式 ⑥p?q 前提引入 ⑦￢p ⑤⑥拒取式 證明（4）： ①t?r 前提引入 ②t ①化簡律 ③q?s 前提引入 ④s?t 前提引入 ⑤q?t ③④等價三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡 ⑧q ②⑥ 假言推理 ⑨q?p 前提引入 ⑩p ⑧⑨假言推理(11)p?q ⑧⑩合取 15在自然推理系統P中用附加前提法證明下面各推理： 4(1)前提：p?(q?r),s?p,q 結論：s?r 證明 ①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系統P中用歸謬法證明下面各推理： (1)前提：p??q,?r?q,r??s 結論：?p 證明： ①p 結論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡律 ⑥r?￢s 前提引入 ⑦r ⑥化簡律 ⑧r?﹁r ⑤⑦ 合取 由于最后一步r?﹁r 是矛盾式,所以推理正確.第四章部分課后習題參考答案 3.在一階邏輯中將下面將下面命題符號化,并分別討論個體域限制為(a),(b)條件時命題的真值:(1)對于任意x,均有錯誤！未找到引用源。2=(x+錯誤！未找到引用源。)(x錯誤！未找到引用源。).5(2)存在x,使得x+5=9.其中(a)個體域為自然數集合.(b)個體域為實數集合.解： F(x): 錯誤！未找到引用源。2=(x+錯誤！未找到引用源。)(x錯誤！未找到引用源。).G(x): x+5=9.(1)在兩個個體域中都解釋為?xF(x)，在（a）中為假命題，在(b)中為真命題。(2)在兩個個體域中都解釋為?xG(x)，在（a）(b)中均為真命題。 4.在一階邏輯中將下列命題符號化:(1)沒有不能表示成分數的有理數.(2)在北京賣菜的人不全是外地人.解:(1)F(x): x能表示成分數 H(x): x是有理數 命題符號化為: ??x(?F(x)?H(x))(2)F(x): x是北京賣菜的人 H(x): x是外地人 命題符號化為: ??x(F(x)?H(x))5.在一階邏輯將下列命題符號化:(1)火車都比輪船快.(3)不存在比所有火車都快的汽車.解:(1)F(x): x是火車;G(x): x是輪船;H(x,y): x比y快 命題符號化為: ?x?y((F(x)?G(y))?H(x,y)) (2)(1)F(x): x是火車;G(x): x是汽車;H(x,y): x比y快 命題符號化為: ??y(G(y)??x(F(x)?H(x,y)))9.給定解釋I如下:(a)個體域D為實數集合R.6(b)D中特定元素錯誤！未找到引用源。=0.(c)特定函數錯誤！未找到引用源。(x,y)=x錯誤！未找到引用源。y,x,y?D錯誤！未找到引用源。.(d)特定謂詞錯誤！未找到引用源。(x,y):x=y,錯誤！未找到引用源。(x,y):x 答:(1)對于任意兩個實數x,y,如果x （a）個體域D=N(N為自然數集合).（b）D中特定元素錯誤！未找到引用源。=2.（c）D上函數錯誤！未找到引用源。=x+y,錯誤！未找到引用源。(x,y)=xy.（d）D上謂詞錯誤！未找到引用源。(x,y):x=y.說明下列各式在I下的含義，并討論其真值.(1)錯誤！未找到引用源。xF(g(x,a),x)(2)錯誤！未找到引用源。x錯誤！未找到引用源。y(F(f(x,a),y)→F(f(y,a),x)答:(1)對于任意自然數x, 都有2x=x, 真值0.(2)對于任意兩個自然數x,y,使得如果x+2=y, 那么y+2=x.真值0.11.判斷下列各式的類型:(1)錯誤！未找到引用源。 (3)錯誤！未找到引用源。yF(x,y).解:(1)因為 p?(q?p)??p?(?q?p)?1 為永真式； 所以 錯誤！未找到引用源。為永真式； (3)取解釋I個體域為全體實數 F(x,y)：x+y=5 所以,前件為任意實數x存在實數y使x+y=5，前件真； 后件為存在實數x對任意實數y都有x+y=5，后件假，] 此時為假命題 再取解釋I個體域為自然數N，F(x,y)：:x+y=5 所以,前件為任意自然數x存在自然數y使x+y=5，前件假。此時為假命題。 此公式為非永真式的可滿足式。13.給定下列各公式一個成真的解釋，一個成假的解釋。 (1)錯誤！未找到引用源。(F(x)錯誤！未找到引用源。 (2)錯誤！未找到引用源。x(F(x)錯誤！未找到引用源。G(x)錯誤！未找到引用源。H(x))解:(1)個體域:本班同學 F(x)：x會吃飯, G(x)：x會睡覺.成真解釋 F(x)：x是泰安人,G(x)：x是濟南人.（2）成假解釋(2)個體域:泰山學院的學生 F(x)：x出生在山東,G(x):x出生在北京,H(x):x出生在江蘇,成假解釋.F(x)：x會吃飯,G(x)：x會睡覺,H(x)：x會呼吸.成真解釋.第五章部分課后習題參考答案 5.給定解釋Ｉ如下:(a)個體域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錯誤！未找到引用源。.試求下列公式在Ｉ下的真值.(1)?x?yF(x,y) (3)?x?y(F(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))?(0?1)?(1?0)?1 (2)?x?y(F(x,y)?F(f(x),f(y))) ??x((F(x,3)?F(f(x),f(3)))?(F(x,4)?F(f(x),f(4)))) ??x((F(x,3)?F(f(x),4))?(F(x,4)?F(f(x),3)))?((F(3,3)?F(f(3),4))?(F(3,4)?F(f(3),3))) ?((F(4,3)?F(f(4),4))?(F(4,4)?F(f(4),3))) ?((0?F(4,4))?(F(3,4)?F(4,3)))?((1?F(3,4))?(0?F(3,3))) ?(0?0)?(1?1)?(1?1)?(0?0)?1 12.求下列各式的前束范式。 (1)?xF(x)??yG(x,y) (5)?x1F(x1,x2)?(H(x1)???x2G(x1,x2))(本題課本上有錯誤)解:(1)?xF(x)??yG(x,y)??xF(x)??yG(t,y)??x?y(F(x)?G(t,y))(5)?x1F(x1,x2)?(H(x1)???x2G(x1,x2)) ??x1F(x1,x2)?(H(x3)??x2?G(x3,x2))??x1F(x1,x4)??x2(H(x3)??G(x3,x2))??x1?x2(F(x1,x4)?(H(x3)??G(x3,x2))) 15.在自然數推理系統F中,構造下面推理的證明:(1)前提: ?xF(x)??y((F(y)?G(y))?R(y)),?xF(x) 結論: ?xR(x)(2)前提: ?x(F(x)→(G(a)∧R(x))), 錯誤！未找到引用源。xF(x)結論:錯誤！未找到引用源。x(F(x)∧R(x))證明(1)①?xF(x)前提引入 ②F(c)①EI ③?xF(x)??y((F(y)?G(y))?R(y))前提引入 ④?y((F(y)?G(y))?R(y))①③假言推理 ⑤(F(c)∨G(c))→R(c))④UI ⑥F(c)∨G(c)②附加 ⑦R(c)⑤⑥假言推理 ⑧?xR(x)⑦EG 9(2)①?xF(x)前提引入 ②F(c)①EI ③?x(F(x)→(G(a)∧R(x)))前提引入 ④F(c)→(G(a)∧R(c))③UI ⑤G(a)∧R(c)②④假言推理 ⑥R(c)⑦F(c)∧R(c)⑧?x(F(x)∧R(x)) ⑤化簡 ②⑥合取引入 第一章部分課后習題參考答案 設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．判斷下面一段論述是否為真：“?是無理數。并且，如果3是無理數，則2也是無理數。另外，只有6能被2整除，6才能被4整除。” 答：p: ?是無理數 q: 3是無理數 0 r: 2是無理數 s: 6能被2整除t: 6能被4整除 0 命題符號化為： p∧(q→r)∧(t→s)的真值為1，所以這一段的論述為真。19．用真值表判斷下列公式的類型：（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 所以公式類型為永真式 （5）公式類型為可滿足式（方法如上例）（6）公式類型為永真式（方法如上例） 第二章部分課后習題參考答案 3.用等值演算法判斷下列公式的類型，對不是重言式的可滿足式，再用真值表法求出成真賦值.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 所以公式類型為永真式 (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 所以公式類型為可滿足式 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)第三章部分課后習題參考答案 14.在自然推理系統P中構造下面推理的證明：(2)前提：p?q,?(q?r),r 結論：?p(4)前提：q?p,q?s,s?t,t?r 結論：p?q 證明：（2） ①?(q?r)前提引入 ②?q??r ①置換 ③q??r ②蘊含等值式 ④r 前提引入 ⑤?q ③④拒取式 ⑥p?q 前提引入 ⑦￢p（3）⑤⑥拒取式 證明（4）： ①t?r 前提引入 ②t ①化簡律 ③q?s 前提引入 ④s?t 前提引入 ⑤q?t ③④等價三段論 ⑥（q?t）?(t?q)⑤ 置換 ⑦（q?t）⑥化簡 ⑧q ②⑥ 假言推理 ⑨q?p 前提引入 ⑩p ⑧⑨假言推理(11)p?q ⑧⑩合取 15在自然推理系統P中用附加前提法證明下面各推理： 4(1)前提：p?(q?r),s?p,q 結論：s?r 證明 ①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r)前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 16在自然推理系統P中用歸謬法證明下面各推理： (1)前提：p??q,?r?q,r??s 結論：?p 證明： ①p 結論的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④￢r?q 前提引入 ⑤￢r ④化簡律 ⑥r?￢s 前提引入 ⑦r ⑥化簡律 ⑧r?﹁r ⑤⑦ 合取 由于最后一步r?﹁r 是矛盾式,所以推理正確.第三篇：屈婉玲版離散數學課后習題答案【4】
第四篇：離散數學(屈婉玲)答案_1-5章
第五篇：離散數學課后習題答案
點擊咨詢 