四川大学离散数学课后习题2解答提示.doc

去找 习题2.11.把下列命题翻译成谓词公式： (1) 每个有理数都是实数，但是并非每个实数都是有理数,有些实数是有理数.解： 设：是实数 ：是有理数，则有：(2) 直线a和b平行当且仅当a 和b不相交.解： ：是直线，：与平行：与相交，则有：(3) 除非所有的会员都参加,这个活动才有意义解： ：是会员：有意义：参加：这个活动或者（4）任何正整数不是合数就是质数. 解：是正整数：是合数：是质数（5）凡是存钱的人都想有利息,如果没有利息,人们就不会存钱解：是人B（x）：x存钱a：利息 P:存钱有利息 ：想有2. 设论域D=0,1,2.把下列公式用不含量词的公式表示出来.(1) (2) （3） 解为：(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. 对下列公式中的变元进行代换,以使任何变元不能既是约束变元又是自由变元. (1) . 解： （2）解为：(x)P(x)R(x)Q(u)($x)R(x)($z)S(v,z)习题 2.21.（1）D：数 永真式(2)是诚实的人讲实话a：小林可满足式 (3) 不便宜是好货买的a：衣服b：小王可满足式（4）是作家 懂得人性本质是诗人是真正的能刻画人们内心世界很高明创作了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)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(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、 解：习题 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)(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)答：该蕴含关系成立 右=($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)中至少有一个对于任意的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并不是自由出现(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