湖南大学离散数学第二章习题一解答

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

1、第二章习题一1、指出下列公式∀x∃y(F(x,y)∧G(y,z))∨∃xH(x,y,z)中的指导变元，量词的辖域，各个体变项的自由出现和约束出现。解：全称量词的指导变元为x，第一个存在量词的指导变元为y，第二个存在量词的指导变元为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-

2、y，x与y为实数。(d)谓词F(x,y)为x=y，G(x,y)为x

3、假，故此式的真值为0。3、给定解释I如下：(a)个体域D=自然数N；(b)特定元素a=2；(c)函数f(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))解：∀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为真时

4、y+2=x为假，故此式的真值为0。(2)∃x(F(f(x,x),g(x,x)))=∃x(F(x+x,x*x)=∃x(x+x=x*x)=∃x(2x=x*x)，当x=0,2时等式成立，故原式为真。4、设个体域D={a,b,c}，在D上展开下列公式中的量词。(1)∀x∀y(F(x)∨G(y))解：∀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(

5、a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c)))另解：反复应用德摩根律，有∀x∀y(F(x)∨G(y))=(F(a)∨G(a))∧(F(a)∨G(b))∧(F(a)∨G(c))∧(F(b)∨G(a))∧(F(b)∨G(b))∧(F(b)∨G(c))∧(F(c)∨G(a))∧(F(c)∨G(b))∧(F(c)∨G(c))=(F(a)∨(G(a)∧G(b))∧G(c))∧(F(b)∨(G(a)∧G(b)∧G(c))∧(F(c)∨(G(a)∧G(b)∧G(c))=(F(a)∧F(b)∧F(c))∨(G(

6、a)∧G(b)∧G(c)))(2)∀x(F(x,y)→∃yG(y))解：∀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

7、)解：∀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∀yF(x,y)解：∃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))解：此式可看成(p→p)→(¬p∨p)的代换实例，而(p→p)→(¬p∨p)⇔1

8、→1⇔1为永真式，所以(1)为永真式。(2)¬(∀xF(x)→∃xB(x))∧∃xB(x)解：此式可看成¬(p→q)∧q的代换实例，而¬(p→q)∧q⇔¬(¬p∨q)∧q⇔(p∧¬q)∧q⇔p∧(¬q∧q)⇔0，所以(2)为永假式。