離散數(shù)學(xué)答案(尹寶林版)第二章習題解答

1、習題與解答1. 將下列命題符號化：(1)所有的火車都比某些汽車快。(2)任何金屬都可以溶解在某種液體中。(3)至少有一種金屬可以溶解在所有液體中。(4)每個人都有自己喜歡的職業(yè)。(5)有些職業(yè)是所有的人都喜歡的。解(1)取論域為所有交通工具的集合。令是火車，是汽車，比y跑得快?！八械幕疖嚩急饶承┢嚳臁笨梢苑柣癁?。(2)取論域為所有物質(zhì)的集合。令是金屬，是液體，可以溶解在y中。“任何金屬都可以溶解在某種液體中”可以符號化為。(3)論域和謂詞與(2)同?！爸辽儆幸环N金屬可以溶解在所有液體中”可以符號化為。(4)取論域為所有事物的集合。令是人，是職業(yè)，喜歡y。“每個人都有自己喜歡的職業(yè)”可以符

2、號化為(5)論域和謂詞與(4)同?！坝行┞殬I(yè)是所有的人都喜歡的”可以符號化為。2.取論域為正整數(shù)集，用函數(shù)（加法），（乘法）和謂詞，將下列命題符號化：(1)沒有既是奇數(shù)，又是偶數(shù)的正整數(shù)。(2)任何兩個正整數(shù)都有最小公倍數(shù)。(3)沒有最大的素數(shù)。(4)并非所有的素數(shù)都不是偶數(shù)。解先引進一些謂詞如下：能被y整除，可表示為。是奇數(shù)，可表示為。是偶數(shù)，可表示為。是素數(shù)，可表示為。(1)“沒有既是奇數(shù)，又是偶數(shù)的正整數(shù)”可表示為，并可進一步符號化為。(2)“任何兩個正整數(shù)都有最小公倍數(shù)”可表示為，并可進一步符號化為(3)“沒有最大的素數(shù)”可表示為，并可進一步符號化為(4)“并非所有的素數(shù)都不是偶數(shù)”可

3、表示為，并可進一步符號化為3.取論域為實數(shù)集合，用函數(shù)，（減法）和謂詞，將下列命題符號化：(1)沒有最大的實數(shù)。(2)任何兩個不同的實數(shù)之間必有另一實數(shù)。(3)函數(shù)在點a處連續(xù)。(4)函數(shù)恰有一個根。(5)函數(shù)是嚴格單調(diào)遞增函數(shù)。解(1)“沒有最大的實數(shù)”符號化為。(2)“任何兩個不同的實數(shù)之間必有另一實數(shù)”符號化為。(3)“函數(shù)在點a處連續(xù)”的定義是：任給，總可以找到，使得只要就有?！昂瘮?shù)在點a處連續(xù)”符號化為(4)“函數(shù)恰有一個根”符號化為。(5)“函數(shù)是嚴格單調(diào)遞增函數(shù)”符號化為。4.指出下列公式中變元的約束出現(xiàn)和自由出現(xiàn)，并對量詞的每次出現(xiàn)指出其轄域。(1)(2)(3)(4)(5)解(

4、1)變元x 在中三次出現(xiàn)都是約束出現(xiàn)，x的唯一出現(xiàn)的轄域是 P(y, x) P(x, a)。(2)變元x 在中的頭兩次出現(xiàn)是約束出現(xiàn)，第三次出現(xiàn)是自由出現(xiàn)。變元y 在中的唯一出現(xiàn)是自由出現(xiàn)。變元z 在中的唯一出現(xiàn)是約束出現(xiàn)。x的唯一出現(xiàn)的轄域是 P(x)，z 的唯一出現(xiàn)的轄域是Q(x, y)。(3)變元x 在中的頭五次出現(xiàn)是約束出現(xiàn)，第六次出現(xiàn)是自由出現(xiàn)。x的第一次出現(xiàn)的轄域是P(x) R(x)，第二次出現(xiàn)的轄域是P(x)。(4)變元x 在中的頭兩次出現(xiàn)是自由出現(xiàn)，后兩次出現(xiàn)是約束出現(xiàn)。x的唯一出現(xiàn)的轄域是 P(z, g(x, y)，y的唯一出現(xiàn)的轄域是P(f(x, y), x) xP(z,

5、g(x, y)。(5)變元x 在中的頭五次出現(xiàn)是約束出現(xiàn)，第六次出現(xiàn)是自由出現(xiàn)。x的唯一出現(xiàn)的轄域是P(x) Q(x)$xR(x)，$x的唯一出現(xiàn)的轄域是R(x)。5.歸納證明：若t，是項，則也是項。證明 若t是x，則是，是項。 若t是不同于x的變元y，則仍是y，是項。若t是常元a，則仍是a，是項。若t是，則是，由歸納假設(shè)知都是項，所以是項。6.歸納證明：若t是項，A是公式，則也是公式。證明若A是，則是，由上題知都是項，所以是公式。若A是，則是，由歸納假設(shè)知是公式，所以是公式。若A是，則是，由歸納假設(shè)知和都是公式，所以是公式。若A是，則仍是A，是公式。若A是，其中y是不同于x的變元，則是，由歸

6、納假設(shè)知是公式，所以是公式。7.給定解釋I和I中賦值v如下：，計算下列公式在解釋I和賦值I中v下的真值。(1)(2)(3)解(1)(2)(3)7.給定解釋I如下：， ， 判斷I是不是以下語句的模型。(1)(2)(3)(4)(5)(6)解(1)(2)(3)(4)(5)(6)9.寫出一個語句A，使得A有模型，并且A的每個模型的論域至少有三個元素。解 語句A為。給定解釋如下。為自然數(shù)集合， 當且僅當， ，則是A的模型，A有模型。任取滿足語句A的解釋I，則，又因為，所以，是論域中三個不同元素，論域中至少有三個元素。10.寫出一個語句A，使得A有模型，并且A的每個模型的論域有無窮多個元素。解 語句A為。

7、給定解釋如下。為自然數(shù)集合， 當且僅當則是A的模型，A有模型。任取滿足語句A的解釋I，取，因為，所以有使得，又因為，故。因為，所以有使得，又因為，故。因為，所以，故。因此，是論域中的三個不同元素。這個過程可以不斷進行下去，得到因此，論域DI中必然有無窮多個元素。11.判斷以下公式是不是永真式、永假式、可滿足式，并說明理由。(1)(2)(3)(4)(5)(6)(7)解(1) 是永真式。若解釋I使得，則或。 若，則存在使得，。 若，則存在使得，。因此，。(2) 是非永真的可滿足式。給定解釋I如下。， ， 則。給定解釋如下。，則。(3) 是非永真的可滿足式。給定解釋I如下。， ， 則。給定解釋如下。

8、，則。(4) 是非永真的可滿足式。給定解釋I如下。， 則。給定解釋如下。，則。(5) 是非永真的可滿足式。給定解釋I如下。， ， 則。給定解釋如下。，則。(6) 是永真式。若解釋I使得，則存在使得，因此且，且，。(7) 是永真式。若解釋I使得，則且。存在使得，又因為，所以，。因此，。A,B是任意公式，證明以下公式是永真式。(1) ,其中項t對于A中的x是可代入的。(2) (3) (4) (5) (6) ，其中x不是A的自由變元。解(1) 任取解釋I和I中賦值v，若,則，所以。這表明是永真式。(2) 任取解釋I和I中賦值v，當且僅當 當且僅當 存在使得當且僅當 存在使得當且僅當 這表明是永真式。

9、(3) 任取解釋I和I中賦值v，當且僅當 當且僅當 存在使得當且僅當 存在使得當且僅當 這表明是永真式。(4) 任取解釋I和I中賦值v，若，則存在使得，且，。這表明是永真式。(5) 任取解釋I和I中賦值v，若，則存在使得，。這表明是永真式。(6) 任取解釋I和I中賦值v，若，則對于每個，因為x不是A的自由變元，所以，因此，。這表明是永真式。13.設(shè)是公式A的閉包，是，其中。證明：(1) A是永真式當且僅當是永真式；(2) A是可滿足式當且僅當是可滿足式。證明(1) （）首先證明：若A是永真式，則是永真式。設(shè)A是永真式。任取解釋I和I中賦值v，任取，因為也是I中賦值，所以，。是永真式。若A是永真

10、式，則是永真式， ，是永真式。（）因為是永真式，所以若是永真式，則A是永真式。(2) （）因為是永真式，所以若解釋I和I中賦值v滿足A，則I和v滿足。（）若解釋I和I中賦值v滿足，則有使得，I和I中賦值滿足A。14.判斷以下等值式是否成立，并說明理由。(1) (2) (3) (4) (5) (6) 解 (1) 不成立。取解釋I如下。， ， ， ， 則且。(2) 不成立。取解釋I如下。， ， ， ， 則且。(3) 不成立。取解釋I和I中賦值v下。， ， ， 則且。(4) 成立。任取解釋I和I中賦值v，因為x不是中的自由變元，所以對于每個，。當且僅當對于每個，當且僅當(5) 不成立。取解釋I如下。

11、， ， ， ， 則且。(6) 不成立。取解釋I如下。， ， ， 則且。A,B是任意公式，證明以下等值式。(1) ，其中y在A中不出現(xiàn)。(2) (3) ，其中x不是B的自由變元，y不是A的自由變元。(4) ，其中x不是B的自由變元，y不是A的自由變元。(5) ，其中x不是B的自由變元，y不是A的自由變元。(6) 證明 (1) (2) (3) (4) (5) (6) 任取解釋I和I中賦值v，當且僅當有使得當且僅當有使得當且僅當有使得當且僅當有使得當且僅當16.判斷以下邏輯推論關(guān)系是否成立，并說明理由。(1) (2) (3) (4) (5) (6) 解 (1) 不成立。取解釋I如下。， ， ， ，

12、則且。這表明。(2) 不成立。取解釋I如下。， ， ， ， 則且。這表明。(3) 不成立。取解釋I如下。， ， ， 則且。這表明。(4) 若解釋I使得，則有使得，且，。這表明。(5) 不成立。取解釋I如下。， ， ， 則且，這表明。(6) 不成立。取解釋I如下。， ， 則，但。所以。17.設(shè)A,B是任意公式，證明以下結(jié)論。(1) (2) (3) ，其中x對于A中的y是可代入的。(4) 證明 (1) 若解釋I和I中賦值v使得，則有使得，且，。這表明。(2) 若解釋I和I中賦值v使得，則對于每個，。這表明。(3) 若解釋I和I中賦值v使得，則有使得，因為，所以，。這表明。(4) 若解釋I和I中賦值v使得，則對于每個，且，因此且，。所以。18.設(shè)變元x既不是公式B中的自由變元，也不是公式集中任何公式的自由變元，A是公式。若，則。證明 設(shè)解釋I和I中賦值v滿足，則，有使得。因為x不是公式集中任何公式的自由變元，所以I和也滿足，I和滿足。又因為，所以，因為x不是B中的自由變元，因此。這表明。19. 設(shè)是公式集合，A是公式，則當且僅當不可滿足。證明 設(shè)可滿足，解釋