四川大學離散數(shù)學課后習題2解答提示

1、去找 習題2.11.把下列命題翻譯成謂詞公式： (1) 每個有理數(shù)都是實數(shù)，但是并非每個實數(shù)都是有理數(shù),有些實數(shù)是有理數(shù).解： 設：是實數(shù) ：是有理數(shù)，則有：(2) 直線a和b平行當且僅當a 和b不相交.解： ：是直線，：與平行：與相交，則有：(3) 除非所有的會員都參加,這個活動才有意義解： ：是會員：有意義：參加：這個活動或者（4）任何正整數(shù)不是合數(shù)就是質(zhì)數(shù). 解：是正整數(shù)：是合數(shù)：是質(zhì)數(shù)（5）凡是存錢的人都想有利息,如果沒有利息,人們就不會存錢解：是人B（x）：x存錢a：利息 P:存錢有利息 ：想有2. 設論域D=0,1,2.把下列公式用不含量詞的公式表示出來.(1) (2) （3） 解

2、為：(P(0)P(1)P(2)(Q(0)Q(1)Q(2)3.指出下列公式中的約束變元和自由變元,并確定公式的轄域.（1） . P（x）中的x為約束變元，轄域為：P（x）. Q（x）中的x為自由變元（2） .（x）P(x)Q(x)中，P(x)和Q(x)中的x均為約束變元，轄域為P(x)Q(x)；（x）P(x)Q(x)中，P(x)中的x為約束變元，轄域為P(x)，Q（x）中的x為自由變元。（3）($x)($y)P(x,y)Q(a)中，x,y是約束變元，轄域為P(x,y)Q(a)，Q(a)中的a為自由變元；(z)R(x,z)中，z為約束變元，轄域為R(x,z)，z為自由變元4. 對下列公式中的變元進

3、行代換,以使任何變元不能既是約束變元又是自由變元. (1) . 解： （2）解為：(x)P(x)R(x)Q(u)($x)R(x)($z)S(v,z)習題 2.21.（1）D：數(shù) 永真式(2)是誠實的人講實話a：小林可滿足式 (3) 不便宜是好貨買的a：衣服b：小王可滿足式（4）是作家 懂得人性本質(zhì)是詩人是真正的能刻畫人們內(nèi)心世界很高明創(chuàng)作了a：莎士比亞b：哈姆雷特2.(1) （2）A=P(a,f(b)P(b,f(a)=P(3,f(2)P(2,f(3)=P(3,3)P(2,2)=10=0 B=(x)($y)P(y,x)($y)P(y,2)($y)P(y,3)(P(2,2)P(3,2)(P(2,3

4、)P(3,3)=(01)(01)=1 C=($y)(x)P(y,x)(x)P(2,x)(x)P(3,x)(P(2,2)P(2,3)(P(3,2)P(3,3)=(00)(11)=1 E=(x)(y)P(x,y)P(f(x),f(y)(y)P(2,y)P(f(2),f(y)(y)P(3,y)P(f(3),f(y)(P(2,2)P(f(2),f(2)(P(2,3)P(f(2),f(3)(P(3,2)P(f(3),f(2)( P(3,3)P(f(3),f(3) =(01)(01)(10)(10)=03.(1) (2) （3）T4. 習題 2.31.（1） （2）($x)($y)P(x)Q(y)(x)P

5、(x)($y)Q(y)證明: ($x)P(x)($y)Q(y) (x)P(x)($y)Q(y) （3）($y)(x)P(x,y)(y)($x)P(x,y)證明: (y)(x)P(x,y) (y)($x)P(x,y) (y)($x)P(x,y)2. 不成立 解:因為($x)P(x)Q(x) ($x)P(x)($x)Q(x) (x)P(x)($x)Q(x),故原式不成立.D=0,1,2 3.(1) skolem范式(2) 前束范式 skolem范式（3）(x)(y)($z)P(x,y,z)($u)Q(x,u)($v)Q(y,v)(4) (x)P(x,0)($y)P(y,f(x)(z)Q(x,z)4

6、、 解：習題 2.41. （1）證：在某個解釋下，取值1，必有,，取值1，因此， 取值1。取值1，由定義，蘊含關系成立。（2）(2) 證: 在某個解釋下，取值1即取值0，分二種情況：i)，則無論為何值，取值1。ii) ，則取值1由定義，蘊含關系成立。（3）(x)P(x)Q(x)(x)Q(x)P(x) (x)P(x)Q(x)(x)Q(x) (x)(P(x)Q(x)Q(x) (x)(P(x)Q(x) (x)P(x)(x) Q(x)(x)P(x)P(y) P(x)(4)(x)P(x)Q(x)(x)P(x)(x)Q(x)證明:(x)(P(x)Q(x)(P(x) (x)Q(x)P(x) (x)Q(x)(

7、x)P(x)(x) Q(x) (簡化法則)(5)($x)P(x)Q(x)(x)P(x)(x)Q(x)證明: ($x)P(x)($x)Q(x)(x)P(x) (x)P(x)(x)Q(x)(x)P(x) (x)Q(x)(x)P(x)(x)Q(x) (簡化法則)2、(1)P(x)(x)Q(x)($x)P(x)Q(x) 答: 該蘊涵關系成立判別方法一:當左取1時,必有P(t)=1,(x)Q(x)=1,從而Q(t)=1,即P(t)Q(t)=1,即右取1.判別方法二:P(x)(x)Q(x) (x)P(y)Q(x) ($y)P(y)Q(y)(2)($x)P(x)(x)Q(x)(x)P(x)Q(x)答：該蘊含

8、關系成立 右=($x)P(x)(x)Q(x) ($x)P(x)(x)Q(x) (x)P(x)(x)Q(x) (x)P(x)Q(x) （3）(x)P(x)Q(x)($x)P(x)(x)Q(x)答:該蘊涵關系不成立判別方法一:構造解釋D=a,bP(a)P(b)Q(a)Q(b)0101左=(x)P(x)Q(x)=1,而右=($x)P(x)(x)Q(x)=0.判別方法二:右=($x)P(x)(x)Q(x) ($x)P(x)(x)Q(x) (x)P(x)(x)Q(x) (x)P(x)Q(x)此為單向蘊涵關系, 故原式不成立.3、這個證明不正確 證明：當（x）P(x)Q(x)取值1的時候，P(x)、Q(x

9、)中至少有一個對于任意的x取值都為1，則右邊式子中，（x）P(x)、（x）Q(x)至少有一個也為1，故原式子成立。習題 2.51（2）（反證法）PT,ET,IT,IUST,IUGPT,IT,I USTI2. (1) 錯誤，應換元，即， （2） 正確 （3） 錯誤，a、b應是同一個常元 （4） 錯誤，因為在 中x并不是自由出現(xiàn)(5) 錯誤，因為在中，前件是命題，而后件不是命題（6） 錯誤，因為a、b并不是同一個常量（7） 錯誤，和的順序不對應先使用ES，再使用US3(1)解：設F(x,y):xy; G(z):z0 ; f(x,y)=x-y前提： (x)(y)（F(x,y)G(f(x,y) (x)(y)（F(x,y)G(f(x,y) (x)(y)(G(f(x,y) G(f(y,x)結論： (x)(y)（G(f(x,y)G(f(y,x)）證明（反證法）： (x)(y)（G(f(x,y)G(f(y,x)） （$）（$）（G(f(x,y)G(f(y,x)） G(f(a,b) G(f(b,a) (x)(y)（F(x,y)G(f(x,y) F(a,b)G(f(a,b) G(f(a,b)F(a,b) (x)(y)(G(f(x,y) G(f(