离散数学第二章练习题答案

一、选择题

1．下列四个公式正确的是

①∀x (A (x ) ∧B (x )) ⇒∀xA (x ) ∧∀xB (x ) ②∀x (A (x ) ∨B (x )) ⇒∀xA (x ) ∨∀xB (x )

③∃x (A (x ) ∨B (x )) ⇒∃xA (x ) ∨∃xB (x ) ④∃xA (x ) ∧∃xB (x ) ⇒∃x (A (x ) ∧B (x ))

A. ①③ B. ①④ C. ③④ D. ②④

2. 谓词公式∀x (P (x ) ∨∃yR (y )) →Q (x ) 中量词∀x 的辖域是( )

(A) ∀x (P (x ) ∨∃yR (y )) (B) P (x ) (C ) P (x ) ∨∃yR (y ) (D) Q (x )

3. 谓词公式∀xP (x ) →(∀x ⌝Q (x ) →⌝∃xQ (x )) 的类型是（）

(A ) 永真式 (B) 矛盾式

4. 设个体域为整数集，下列公式中其真值为1的是( )

(A ) ∀x ∃y (x +y =0) (B) ∃y ∀x (x +y =0)

(C)∀x ∀y (x +y =0) (D) ⌝∃x ∃y (x +y =0)

5. 设个体域A ={a , b }，公式∀xP (x ) ∧∃xS (x ) 在中消去量词后应为 ( )

(A) P (x ) ∧S (x ) (B ) P (a ) ∧P (b ) ∧(S (a ) ∨S (b ))

6. 在谓词演算中，下列各式正确的是( )

(A) ∃x ∀yA (x , y ) ⇔∀y ∃xA (x , y ) (B ) ∃x ∃yA (x , y ) ⇔∃y ∃xA (x , y )

7. 下列各式不正确的是( )

(A ) ∀x (P (x ) ∨Q (x )) ⇔∀xP (x ) ∨∀xQ (x )

(B) ∀x (P (x ) ∧Q (x )) ⇔∀xP (x ) ∧∀xQ (x )

(D) ∀x (P (x ) ∧Q ) ⇔∀xP (x ) ∧Q

8. 设I 是如下一个解释：D ＝{a,b}, P (a , a ) P(a,b) P(b,a) P(b,b) 1 0 1 0

则在解释I 下取真值为1的公式是( ).

(A) ∃x ∀yP(x,y) (B)∀x ∀yP(x,y) (C)∀xP(x,x) (D ) ∀x ∃yP(x,y).

9. 设个体变元x , y , z 的论域都为自然数集合，P (x , y , z ) :x +y =z ,

Q (x , y , z ) ：x ⋅y =z , R (x , y ) :x

A ．∀xP (x , 0, x ) B ．∃x ∀yP (x , y , y )

C ．∀x ∃yQ (y , x , x ) D ．∀xR (x , 0)

10. 下面不是命题的是（）

A ．∀xP (x ) B ．(∃x ) P (x )

C ．(∀x ) P (x ) ∨P (y ) D ．(∃x )(∃y )(P (x ) →R (y ))

11公式(∀x ) P (x ) →(∀x ) Q (x ) 的前束范式为（）

A ．(∀x )(∀y )(P (x ) →Q (y )) B ．(∀x )(∃y )(P (x ) →Q (y ))

C ．(∃x )(∀y )(P (x ) →Q (y )) D ．(∃x )(∃y )(P (x ) →Q (y ))

12. 公式(∀x )(P (x ) Q ) ⇔（）

A ．((∀x ) P (x ) →Q ) ∧(Q →(∀x ) P (x )) B ．((∀x ) P (x ) →Q ) ∧(Q →(∃x ) P (x ))

C ((∃x ) P (x ) →Q ) ∧(Q →(∀x ) P (x )) D ．((∃x ) P (x ) →Q ) ∧(Q →(∃x ) P (x ))

13. (∀x )(∃y ) P (x , y ) 的否定是（）

A ．(∀x )(∀y ) ⌝P (x , y ) B ．(∃x )(∀y ) ⌝P (x , y )

C ．(∀x )(∃y ) ⌝P (x , y ) D ．(∃x )(∃y ) ⌝P (x , y )

14. 下列谓词公式与(∀x )(A (x ) ↓B (x )) 等价的是（）

A ．(∀x ) A (x ) ↓(∀x ) B (x ) B ．(∀x ) A (x ) ↑(∀x ) B (x )

C ．(∃x ) A (x ) ↓(∃x ) B (x ) D ．(∃x ) A (x ) ↑(∃x ) B (x )

15. 在谓词演算中，P (a ) 是∀xP (x ) 的有效结论，其理论依据是（）

A ．US B ．UG C ．ES D ．EG

16. 设个体域是整数集合，P 代表∀x ∀y ((x

(A) P 是真命题 (B ) P 是假命题

二、填空题

1. 设全体域D 是正整数集合，确定下列命题的真值：

(1) ∀x ∃y (xy =y ) ( 0 ) (2) ∃x ∀y (x +y =y ) ( 0 )

(3) ∃x ∀y (x +y =x ) ( 0 ) (4) ∀x ∃y (y =2x ) ( 1 )

2. 谓词公式(∀x )(P (x , y ) ∨Q (z )) ∧(∃y )(R (x , y ) →(∀z ) Q (z )) 中量词∀x 的辖域是

3. 公式(∀x )(P (x ) →Q (x , y ) ∨(∃z ) R (y , z )) →S (x ) 中量的自由变量为约束

变量为 x,z

4. 设个体域D ＝{1,2},那么谓词公式∃xA (x ) ∨∀yB (y ) 消去量词后的等值式为.

A (1)∨A (2)∨(B (1)∧B (2)) 5. 设个体域D ＝{a , b },公式∀x (G (x ) →∃yH (x , y )) 消去量词化为. (G (a ) →(H (a , a ) ∨H (a , b ))) ∧ (G (b ) →(H (b , a ) ∨H (b , b )))

6. 设N (x ) ：x 是自然数，Z (y ) ；y 是整数，则命题“每个自然数都是整数，而有些整数不是自

然数”符号化为 ∀x (N (x ) →Z (x )) ∧∃x (Z (x ) ∧⌝N (x ))

7. 谓词公式∀x (F (x )→G (x ))∧⌝∀y (F (y )→G (y )) 的类型是

8. 设个体域{1,2},谓词P (1)=1,P(2)=0，Q(1)=0，Q (2)=1，则∀x (P (x ) ∨Q (x )) 的真值是

9. 只用联结词⌝, ∀, →表示以下公式

(∃x )(P (x ) ∧Q (x )) =⌝(∀x ) (P (x ) →⌝Q (x )

(∃x )(P (x ) (∀y ) Q (y )) =⌝(∀x ) (P (x (→) ∀(y Q ) y (→) ) ⌝∀(y (Q ) y →() P x (∀y )((∀x ) P (x ) ∨⌝Q (y )) =(∀y )(Q (y ) →(∀x ) P (x ))

三、计算及证明

1. 求谓词公式∀x (P →Q (x )) ∧R (f (a )) 的真值．

其中P ：4>3，Q （x ）：x >1，R （x ）：x ≤2．

f （-3）=1，f （1）=5，f （5）= -3．a ：5．

个体域D =（-3，1，5）．

解：∀x (P →Q (x )) ∧R (f (a ))

=(P →Q (-3)) ∧(P →Q (1)) ∧(P →Q (5)) ∧R (f (5))

=(1→0) ∧(1→0) ∧(1→1) ∧R (-3)

=0∧0∧1∧1=0

2. 说明公式∀xP (x ) →(∃yG (x , y ) →∀xP (x )) 是逻辑有效式(永真式) ．

解：因为∀xP (x ) →(∃yG (x , y ) →∀xP (x )) 是P →(Q →P ) 的代换实例，

可知 ∀xP (x ) →(∃yG (x , y ) →∀xP (x )) 是逻辑有效式．

或 ⌝∀xP (x ) ∨(⌝∃yG (x , y ) ∨∀xP (x ))

⇔⌝∀xP (x ) ∨⌝∃yG (x , y ) ∨P (x ) ⇔1

3. 通过等值演算说明下列等值式成立： ∃x (P (x ) →Q (x )) ⇔∀xP (x ) →∃xQ (x )

证：∃x (P (x ) →Q (x )) ⇔∃x (⌝P (x ) ∨Q (x )

⇔∃x ⌝P (x ) ∨∃xQ (x ))

⇔⌝∀xP (x ) ∨∃xQ (x )

⇔∀xP (x ) →∃xQ (x )

4. 求谓词公式(∀xF (x , y ) →∀yG (x , y )) ∧∃zH (x , y , z ) 的前束范式

解：(∀xF (x , y ) →∀yG (x , y )) ∧∃zH (x , y , z )

⇔(⌝∀xF (x , y ) ∨∀yG (x , y )) ∧∃zH (x , y , z )

⇔(∃u ⌝F (u , y ) ∨∀vG (x , v )) ∧∃zH (x , y , z )

⇔∃u (⌝F (u , y ) ∨∀vG (x , v )) ∧∃zH (x , y , z ))

⇔∃u ∀v ∃z ((⌝F (u , y ) ∨G (x , v )) ∧H (x , y , z ))

(或⇔∃u ∀v ∃z ((F (u , y ) →G (x , v )) ∧H (x , y , z )) )

5. 前提：∃xF (x ), ∀x (F (x ) →G (x ) ∧H (x ))

结论：∃x (F (x ) ∧H (x ))

6. 构造推理证明∃xP (x ) →∀xQ (x ) ⇒∀x (P (x ) →Q (x )) ．（提示：∀xA (x ) ∨∀xB (x ) ⇒∀x (A (x ) ∨B (x )) .) 证 ① ∃xP (x ) →∀xQ (x ) 前提引入

② ⌝∃xP (x ) ∨∀xQ (x ) T ①, 蕴含等值式

③ ∀x ⌝P (x ) ∨∀xQ (x ) T ②, 量词否定 ④ ∀x (⌝P (x ) ∨Q (x ))

⑤ ∀x (P (x ) →Q (x )) T ④, 蕴含等值式法2：（反证法）

① ⌝∀x (P (x ) →Q (x )) 前提引入

② ∃x (P (x ) ∧⌝Q (x )) T E①,

③ P (c ) ∧⌝Q (c ) ES ②, ④ ⌝Q (c ) T ③ , ⑤ P (c ) T ③,

⑥∃xP (x ) EG ⑤ ⑦∃xP (x ) →∀xQ (x ) P

⑧∀xQ (x ) T ⑦

⑨Q (c ) UG ⑧ ⑩⌝Q (c ) ∧Q (c ) T ④