一、 选择题
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) 矛盾式
(C) 非永真式的可满足式 (D) 蕴涵式
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 ))
(C) P (a ) ∧S (b ) (D) 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 )
(C) ∃x ∀yA (x , y ) ⇔∀x ∃yA (x , y ) (D) ∀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 )
(C) ∃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 是假命题
(C) P 是一阶逻辑公式，但不是命题 (D) 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 ④