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

2024年1月25日发(作者：长春单招考试数学试卷真题)

。

第二章习题一

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-y，x 与y 为实数。

(d) 谓词F(x,y)为x=y，G(x,y)为x

给出下列公式在解释I 下的真值。

(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

当x-y=0为真时x

(2) ∀x∀y(G(f(x,y),a) →F(x,y))

解： 原式=∀x∀y(G(f(x,y),a)→F(x,y))

=∀x∀y(G(x-y,0)→F(x,y)) =∀x∀y ( x-y<0 → x=y )

当x-y<0为真时x=y为假，故此式的真值为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为真时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(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(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)

解： ∀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)=0

6、利用代换实例判断下列公式的类型

(1) (∀xA(x)→∀xA(x))→(¬∃yB(y)∨∃yB(y))

解： 此式可看成 (p→p)→(¬p∨p) 的代换实例，而

(p→p)→(¬p∨p) ⇔1→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)为永假式。

精选资料，欢迎下载

。

Welcome !!!

欢迎您的下载，

资料仅供参考！

精选资料，欢迎下载