离散数学 杨圣洪等著 第二章习题一解答

《离散数学 杨圣洪等著 第二章习题一解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章习题一1、指出下列公式∀x∃y(F(x,y)∧G(y,z))∨∃xH(x,y,z)中的指导变元，量词的辖域，各个体变项的自由出现和约束出现。解：全称量词的指导变元为x，第一个存在量词的指导变元为y，第2个存在量词的指导变元为x。在∀x∃y(F(x,y)∧G(y,z))中约束变元为x与y，自由变元为z。在∃xH(x,y,z)中的约束变元为x，自由变元为y,z。2、给定解释I如下：(a)个体域为实数集R；(b)特定元素a=0；(c)函数f(x,y)=x-y，x与y为实数。(d)谓词F(x,y)为x=y，G(x,y)为x

2、∀x∀y(F(f(x,y),a)→G(x,y))(2)∀x∀y(G(f(x,y),a)→F(x,y))(1)∀x∀y(F(f(x,y),a)→G(x,y))解：原式=∀x∀y(F(x-y,0)→G(x,y))=∀x∀y(x-y=0→x

3、(x,y)=x+y，g(x,y)=x*y；(d)谓词F(x,y)为x=y；给出下列各式在I下的解释，并讨论它们的真值：(1)∀x∀y(F(f(x,a),y)→F(f(y,a),x))(2)∃x(F(f(x,x),g(x,x)))(1)∀x∀y(F(f(x,a),y)→F(f(y,a),x))=∀x∀y(F(f(x,2),y)→F(f(y,2),x))=∀x∀y(F(x+2,y)→F(y+2,x))=∀x∀y((x+2=y)→(y+2=x))当x+2=y时即x-y=-2即前件为1时，后件y+2=x即x-y=2是不可能的，也即后件为0，故此式的值为0。(2)∃x(F(f(x,x)

4、,g(x,x)))=∃x(F(x+x,x*x)=∃x(x+x=x*x)=∃x(2x=x*x)=∃x(2=x)当x为任意值，x=2时上式为真。故原式为真。4、设个体域D={a,b,c}，在D上展开下列公式中的量词。(1)∀x∀y(F(x)∨G(y))(2)∀x(F(x,y)→∃yG(y))(1)∀x∀y(F(x)∨G(y))=∀x((F(x)∨G(a))∧(F(x)∨G(b))∧(F(x)∨G(c)))=∀x(F(x)∨(G(a)∧G(b)∧G(c)))=∀x(F(x))∨(G(a)∧G(b)∧G(c)))=(F(a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c)))(

5、2)∀x(F(x,y)→∃yG(y))=∀x(F(x,y)→(G(a)∨G(b)∨G(c)))=(F(a,y)→(G(a)∨G(b)∨G(c)))∧(F(b,y)→(G(a)∨G(b)∨G(c)))∧(F(c,y)→(G(a)∨G(b)∨G(c)))5、在给定解释I如下：(a)个体域D={3,4}(b)f(3)=4,f(4)=3(c)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)(1)∀x∃yF(x,y)=∀x(F(x,3)∨F(x,4))=(F(3,3)∨F(3,4))∧(F(4,

6、3)∨F(4,4))=(0∨1)∧(1∨0)=1(2)∃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)=06、利用代换实例判断下列公式的类型(1)(∀xA(x)→∀xA(x))→(¬∃yB(y)∨∃yB(y))(2)¬(∀xF(x)→∃xB(x))∧∃xB(x)解：(1)∀xA(x)→∀xA(x)可看成p→p的代换实例，而p→p⇔¬p∨p⇔1，所以∀xA(x)→∀xA(x)⇔1(¬∃yB(y)∨∃yB(y))可看成¬p∨p的代换实例，而¬p∨p⇔1，故(¬∃yB(y)∨∃yB(y)

7、)⇔1故(1)⇔1→1⇔1，故(1)为永真式(2)¬(∀xF(x)→∃xB(x))∧∃xB(x)⇔¬(¬∀xF(x)∨∃xB(x))∧∃xB(x)是p→q⇔¬p∨q的代换实例⇔(¬¬∀xF(x)∧¬∃xB(x))∧∃xB(x)是德摩律的代换实例⇔(∀xF(x)∧¬∃xB(x))∧∃xB(x)是否定之否定的代换实例⇔∀xF(x)∧(¬∃xB(x)∧∃xB(x))是结合律的代换实例⇔∀xF(x)∧0是¬p∧p⇔0的代换实例⇔0是p∧0⇔0的代换实例故为永假式以后在所有的证明中，可将“代换实例”这几个省略不写