离散数学期末复习题 2012-6-16
1.“太阳系以外的星球上有生命。”是命题。 （ T ）
2．ρ（A⋃B）=ρ（A ）⋃ ρ（B ） （ F ）
ρ（A∩B）=ρ（A ）∩ρ（B ） （ T ）
3．一个命题的合取范式不是唯一的。 （ T ）
4．等价式⌝（∃x ）A （x ）⇔（∀x ）⌝A （x ）成立。 ( T )
5．（∀x ）（P （x ）∨Q （x ））∧ R（x ）是命题。 （ F ）
8．对于一个谓词公式，指定不同的个体域，则其真值不一定相同.T
9. 若命题公式A 的主析取范式包含全部的极小项，则A 为永真式T
10．命题“他在教室看书或在宿舍看书。”可以符号化为P ∨ S。F
11．当个体域S=｛a,b,c ｝消去公式(∀x) P(x)∨(∃x)Q(x)中量词为(P(a)∨Q(a)) ∧ (P(b)) ∨Q(b)) ∧ (P(c)∨Q(c)) F
12. 设P 、Q 是两个命题，当且仅当P 、Q 的真值均相同时，P Q 的值为T. T
13. 命题公式(P∧(P→ Q)) → Q是永真式. T
14． 命题联结词集｛∨、∧ ｝是极小功能完备的联结词集. F
15．(A ≠ Φ) ∧ (B ≠ Φ) ⇒ (A ⋂ B ≠Φ ) F
16. （P Q）→ ┐（ P ∨Q ） 是矛盾式。 F
17. ∃xA(x) ∨ ∃x B(x) ⇒ ∃x ( A(x) ∨ B(x)) T
19. 若关系R 不具有对称性则R 一定具有反对称性 F
22. 设A 、B 、C 是任意集合，且C-B = C-A，则A=B 。 F
23. 设A 、B 和C 为任意集合，且A ∪B=A∪C ，则B=C. F
24．若R 和S 是X 上具有对称性的关系，则R º S也具有对称性。F
25．若R 和S 是X 上的具有对称性的关系，则R ∩S 具有对称性。 T
26．∃xA(x)∨∃x B(x)⇒ ∃x ( A(x) ∨ B(x)) （F ）
27． （P Q）→ ┐（ P ∨Q ） 是可满足式。 （ F）
28． ｛ ｝=｛φ｝ （ F ）
二、填空题
1．已知B={ {a，b}，c}，
则B 的幂集ρ（B ）= { B , Φ,{{a，b}}，{c} }
2．已知A={1，2，3，4，5，6，7}，B={2，4，6，8，10}，则
A-B= {1,3,5,7,} ,A + B= {1,3,5,7, 8,10} 。
3．设A 、B 是有穷集合，#A=n，#B=m，那么#ρ（A ）= 2n ，
#（A ×B ），#ρ（A ×B ）n*n ，
4．R 是集合X 上的关系。如果R 满足 自反 ， 对称 ， 传递 ，
则R 是X 上的等价关系。
5．如果关系矩阵中主对角线上的元素都是1，则此关系一定具有__自反_性。
6. 两个重言式的析取是 重言式 ,一个重言式与一个矛盾式的析取是 重言式 .
7. 公式(P∨Q) R的只含联结词｛┐、∧｝的等值式 ，
8. 设谓词Q(x)： x
则(∀x)Q(x)真值为__F____, (∃x)Q(x)真值为__T_____ .
9. 已知 A ⋂（~ B） = { a, b, c, d } A ⋂ B = { e, f }
A = __{ a, b, c, d, e, f }____________
10. 谓词公式 ∀xF(x，y) → ⌝ ∃y G(x,y)的前束范式为
______ .
11．设P(x):x是金子，Q(x):x是闪光的，则命题“金子是闪光的，但闪光的不
一定是金子”符号化的谓词公式 .
12. 设F(x):x是北京人，G(x):x是在北京工作。
则命题“在北京工作的并非是北京人”符号化的谓词公式为_____________
13、设个体为自然数集，N(x):x是自然数，L(x,y):x>y
则命题“不存在最大的自然数”形式化为: .
14. 判断下列公式的类型或真值:(永真式, 矛盾式, 可满足式、T 、F)
1) ⌝ (p∨ q∨ r ) (⌝ p ∧ ⌝q ∧ ⌝r ) （ T ）
2) ∀x A(x) → ∃xA(x) （ T ）
3)(P → Q) → (Q →P) （ 可满足 ）
4) ⌝ (∀x A(x) →∀yB(y)) ∧ ∀y B(y) （ F ）
16. 设A=｛1,2,3，｛1,2｝, ｛3｝｝,B=｛ ｛1｝，2,3，｛2,3｝, ｝
A –(B∩A) = ｛ 1， ｛1，2｝，｛3｝ ｝
B ㊉ A = ｛1，｛1，2｝，｛3｝，｛1｝， ｛2，3｝ ｝
16. 已知A={1，2，3，4，5}，B={a，b ，c ，d}，则
定义在A 到B 的不同关系R 有___220_________种.
定义在A 到B 的不同函数F 有___45_________种.
设A={1，2，3}，B={a，b ，2}，则
求 A⊕B=
P(A)∪P(B)=
P(A⊕B) =
17. 关系R={ ，，, }
关系R 具有哪些性质? ______反对称、__________________.
r(R)= R ∪ { ， }。
s(R) = R ∪{ ， }。
t(R) = R ∪ { }。
21. 给定命题公式(P ∧ Q) ∨ R，该公式在全功能集合｛⌝，→｝中的形式
为: ___________________________.
27. 命题公式((p ∧ q) → r ) ∧( p → ⌝( q ∧ r ) )
该公式的主析取范式为 ____________________
该公式的主合取范式为 __(⌝p ∨⌝ q ∨ r ) ∧_(⌝p ∨⌝ q ∨⌝ r )__
三、选择题（有多选题）
1.选出下列语句中的命题 （ C D ）
A.天气多麽晴朗啊！ B.我正在说谎。
C.雪是黑色的。 D.我做完作业了。
4 . 下列等价式中错误的是 ( C )
A. (∀x)(A(x)∨p) ⇔(∀x)A(x)∨p
B. (∃x)A(x)∧p ⇔(∃x)(A(x)∧p)
C. (∀x)(A(x)∨B(x))⇔(∀x)A(x)∨(∀x)B(x)
D. (∀x)(A(x)∧B(x))⇔(∀x)A(x)∧(∀x)B(x)
5. 下列各式中哪个是不成立的： ( A B C )
A: p → q ⇔ ┐p → ┐q
B: (∀x)(P(x)∨Q(x)) ⇔ (∀x)P(x)∨(∀x)Q(x);
C: (p → q) ∧ ┐q ⇒ ┐p ;
D: (∃x)(P(x)∨Q(x)) ⇔ ( ∃ x)P(x)∨(∃x)Q(x);
7. 下面哪组命题公式是等值的；( A C D )
A: ┐(A →B),A ∧┐B; B: A→ (B∨C), ┐A ∧(B∨C);
C: ┐(A B),(A∧┐B) ∨(┐A ∧B); D: A → (B∨C), (A∧┐B) → C.
8. P ⇒ Q 的等价说法有（ A B D ）。
A) P ∧ ⌝Q 是永假式 B) Q 是 P的有效结论。
C) P是Q 的有效结论 D) P → Q 为永真式
9. 下列推理式是正确的有（ B ）
A) P ∧ ( Q→ P) ⇒ Q
B) (P ∧ Q) ⇒ P→ Q
C) P→ Q ⇒ Q→ P
D) (Q → (P ∧ P)) → (R →(P ∧ P)) ⇒ R → Q
10． 设A=｛｛1,2,3｝, ｛4,5｝, ｛6,7,8｝,3｝，下式哪个式子为真( C D ) A: φ A; B: ｛6,7,8｝⊆ A; C: ｛｛4,5｝｝⊆ A; D: 3 A.
11. 设F （x ）：为有理数，G （x ）：为自然数，
命题“有理数不全是自然数”的符号化形式为（ A B ）
A) ┐ ∀x(F(x) → G(x)) B) ∃x(F(x) ∧┐ G(x))
C) ∃x(F(x) → G(x)) D) ∀x(F(x) ∧ G(x))
12. 设 P：2是素数， Q：5是素数， R: π是有理数。下面复合命题中为假的是（B C ）
A) (P ∧ Q ) ∨ R B) R ∧ (P ∨ Q )
C) （ P ∧ R） Q D) (P ∧ R) → Q
16．设个体域A=｛a,b ｝, 公式(∃x)P(x)∨(∀x)S(x)在A 上消去量词后为( B D )
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)）.
17. 下面哪些命题是真命题( B C D )
A) 如果2是偶数，那么一个命题公式的合取范式唯一；
B) 如果2是偶数，那么一个命题公式的主析取范式唯一；
C) 如果2是奇数，那么一个命题公式的析取范式唯一；
D) 如果2是奇数，那么一个命题公式的主合取范式不唯一。
18 设A=｛1,2,3,4,5,6｝上的关系为R =｛(i,z)|i>z｝，
则R 的逆关系的性质有( C D )
A) 对称的； B) 自反的；
C) 反自反的，可传递的； D) 反对称的.
C) 7; D) 10.
22. 给定下列联结词集合，哪个可构成联结词完备集( B D )
A) ｛ ∨，∧，┐｝ B) ｛↑ ｝
C) ｛┐， →， ↓｝ D) ｛┐，∧｝
四、运算题
（1）求命题公式((P→Q) ( ┐ Q→ ┐P)) ∧S 的最简等值式.
（2）命题公式(p → q) r
该公式的主析取范式为 __________________________________.
该公式的主合取范式为 __________________________________.
(3) 设集合集合X 上的关系R 和S 的关系矩阵为M R MS 给出关系R 和S 的集合表示
画出R ︒S 的关系图
3)求出R ︒S 的逆关系的关系矩阵
(7)求(P∧Q) ∨( ⌝P ∧R) ∨(Q∧R) 的主析取范式。
⇔ (P∧Q ∧R )∨( P∧Q ∧⌝R) ∨( ⌝P ∧ Q ∧R) ∨(⌝P ∧ ⌝Q ∧R)
⇔ m1 ∨ m3 ∨ m6 ∨ m7
主合取范式 =
(9)给定集合Ｘ＝｛a,b,c ｝, 且Ｒ是Ｘ中的二元关系。Ｒ的关系矩阵是
1 1 1
MR = 0 1 1 试求出R , R , R ⋂R 的关系矩阵。 1 0 1
（12）设A=｛0,1,2｝到B =｛0,2,4｝的关系为
R=｛|a,bA ∩B ｝，
则R = { ，，， } 。
（13）设集合A=｛1,2,3｝上的关系R=｛,,,｝， 该关系具有什么性质？
确定该关系的自反闭包、对称闭包、传递闭包
五、证明题
（1）用推理规则证明⌝t →m 是前提条件：p → (q→m), ⌝t →p, q的有效结论
（2）用形式推理规则证明： ~2~
结论 (∀x )( C(x) → ⌝ A(x))是
前提条件： ∀x (A(x) →B (x)), ∀x (C(x) →⌝B(x))的有效结论
（3）证明（∃ x）¬ A （x ）
是前提（∀x ）（A （x ）→¬ B （x ）），（∀ x）（B （x ）∨ C（x ）），
（∃x ）¬ C （x ）的有效结论。
(4) 设 A,B是集合，证明 P(A ∩B ） = P(A) ∩ P(B)
（5）给定集合X ，且R 是X 中的二元关系。试证明， R2 ⊆ R，当且仅当关系R
是可传递的。
（6）给定集合X ，且R 和S 是X 中具有传递性的二元关系。试证明R ∩S 也是可
传递的二元关系。
离散数学期末复习题 2012-6-16
1.“太阳系以外的星球上有生命。”是命题。 （ T ）
2．ρ（A⋃B）=ρ（A ）⋃ ρ（B ） （ F ）
ρ（A∩B）=ρ（A ）∩ρ（B ） （ T ）
3．一个命题的合取范式不是唯一的。 （ T ）
4．等价式⌝（∃x ）A （x ）⇔（∀x ）⌝A （x ）成立。 ( T )
5．（∀x ）（P （x ）∨Q （x ））∧ R（x ）是命题。 （ F ）
8．对于一个谓词公式，指定不同的个体域，则其真值不一定相同.T
9. 若命题公式A 的主析取范式包含全部的极小项，则A 为永真式T
10．命题“他在教室看书或在宿舍看书。”可以符号化为P ∨ S。F
11．当个体域S=｛a,b,c ｝消去公式(∀x) P(x)∨(∃x)Q(x)中量词为(P(a)∨Q(a)) ∧ (P(b)) ∨Q(b)) ∧ (P(c)∨Q(c)) F
12. 设P 、Q 是两个命题，当且仅当P 、Q 的真值均相同时，P Q 的值为T. T
13. 命题公式(P∧(P→ Q)) → Q是永真式. T
14． 命题联结词集｛∨、∧ ｝是极小功能完备的联结词集. F
15．(A ≠ Φ) ∧ (B ≠ Φ) ⇒ (A ⋂ B ≠Φ ) F
16. （P Q）→ ┐（ P ∨Q ） 是矛盾式。 F
17. ∃xA(x) ∨ ∃x B(x) ⇒ ∃x ( A(x) ∨ B(x)) T
19. 若关系R 不具有对称性则R 一定具有反对称性 F
22. 设A 、B 、C 是任意集合，且C-B = C-A，则A=B 。 F
23. 设A 、B 和C 为任意集合，且A ∪B=A∪C ，则B=C. F
24．若R 和S 是X 上具有对称性的关系，则R º S也具有对称性。F
25．若R 和S 是X 上的具有对称性的关系，则R ∩S 具有对称性。 T
26．∃xA(x)∨∃x B(x)⇒ ∃x ( A(x) ∨ B(x)) （F ）
27． （P Q）→ ┐（ P ∨Q ） 是可满足式。 （ F）
28． ｛ ｝=｛φ｝ （ F ）
二、填空题
1．已知B={ {a，b}，c}，
则B 的幂集ρ（B ）= { B , Φ,{{a，b}}，{c} }
2．已知A={1，2，3，4，5，6，7}，B={2，4，6，8，10}，则
A-B= {1,3,5,7,} ,A + B= {1,3,5,7, 8,10} 。
3．设A 、B 是有穷集合，#A=n，#B=m，那么#ρ（A ）= 2n ，
#（A ×B ），#ρ（A ×B ）n*n ，
4．R 是集合X 上的关系。如果R 满足 自反 ， 对称 ， 传递 ，
则R 是X 上的等价关系。
5．如果关系矩阵中主对角线上的元素都是1，则此关系一定具有__自反_性。
6. 两个重言式的析取是 重言式 ,一个重言式与一个矛盾式的析取是 重言式 .
7. 公式(P∨Q) R的只含联结词｛┐、∧｝的等值式 ，
8. 设谓词Q(x)： x
则(∀x)Q(x)真值为__F____, (∃x)Q(x)真值为__T_____ .
9. 已知 A ⋂（~ B） = { a, b, c, d } A ⋂ B = { e, f }
A = __{ a, b, c, d, e, f }____________
10. 谓词公式 ∀xF(x，y) → ⌝ ∃y G(x,y)的前束范式为
______ .
11．设P(x):x是金子，Q(x):x是闪光的，则命题“金子是闪光的，但闪光的不
一定是金子”符号化的谓词公式 .
12. 设F(x):x是北京人，G(x):x是在北京工作。
则命题“在北京工作的并非是北京人”符号化的谓词公式为_____________
13、设个体为自然数集，N(x):x是自然数，L(x,y):x>y
则命题“不存在最大的自然数”形式化为: .
14. 判断下列公式的类型或真值:(永真式, 矛盾式, 可满足式、T 、F)
1) ⌝ (p∨ q∨ r ) (⌝ p ∧ ⌝q ∧ ⌝r ) （ T ）
2) ∀x A(x) → ∃xA(x) （ T ）
3)(P → Q) → (Q →P) （ 可满足 ）
4) ⌝ (∀x A(x) →∀yB(y)) ∧ ∀y B(y) （ F ）
16. 设A=｛1,2,3，｛1,2｝, ｛3｝｝,B=｛ ｛1｝，2,3，｛2,3｝, ｝
A –(B∩A) = ｛ 1， ｛1，2｝，｛3｝ ｝
B ㊉ A = ｛1，｛1，2｝，｛3｝，｛1｝， ｛2，3｝ ｝
16. 已知A={1，2，3，4，5}，B={a，b ，c ，d}，则
定义在A 到B 的不同关系R 有___220_________种.
定义在A 到B 的不同函数F 有___45_________种.
设A={1，2，3}，B={a，b ，2}，则
求 A⊕B=
P(A)∪P(B)=
P(A⊕B) =
17. 关系R={ ，，, }
关系R 具有哪些性质? ______反对称、__________________.
r(R)= R ∪ { ， }。
s(R) = R ∪{ ， }。
t(R) = R ∪ { }。
21. 给定命题公式(P ∧ Q) ∨ R，该公式在全功能集合｛⌝，→｝中的形式
为: ___________________________.
27. 命题公式((p ∧ q) → r ) ∧( p → ⌝( q ∧ r ) )
该公式的主析取范式为 ____________________
该公式的主合取范式为 __(⌝p ∨⌝ q ∨ r ) ∧_(⌝p ∨⌝ q ∨⌝ r )__
三、选择题（有多选题）
1.选出下列语句中的命题 （ C D ）
A.天气多麽晴朗啊！ B.我正在说谎。
C.雪是黑色的。 D.我做完作业了。
4 . 下列等价式中错误的是 ( C )
A. (∀x)(A(x)∨p) ⇔(∀x)A(x)∨p
B. (∃x)A(x)∧p ⇔(∃x)(A(x)∧p)
C. (∀x)(A(x)∨B(x))⇔(∀x)A(x)∨(∀x)B(x)
D. (∀x)(A(x)∧B(x))⇔(∀x)A(x)∧(∀x)B(x)
5. 下列各式中哪个是不成立的： ( A B C )
A: p → q ⇔ ┐p → ┐q
B: (∀x)(P(x)∨Q(x)) ⇔ (∀x)P(x)∨(∀x)Q(x);
C: (p → q) ∧ ┐q ⇒ ┐p ;
D: (∃x)(P(x)∨Q(x)) ⇔ ( ∃ x)P(x)∨(∃x)Q(x);
7. 下面哪组命题公式是等值的；( A C D )
A: ┐(A →B),A ∧┐B; B: A→ (B∨C), ┐A ∧(B∨C);
C: ┐(A B),(A∧┐B) ∨(┐A ∧B); D: A → (B∨C), (A∧┐B) → C.
8. P ⇒ Q 的等价说法有（ A B D ）。
A) P ∧ ⌝Q 是永假式 B) Q 是 P的有效结论。
C) P是Q 的有效结论 D) P → Q 为永真式
9. 下列推理式是正确的有（ B ）
A) P ∧ ( Q→ P) ⇒ Q
B) (P ∧ Q) ⇒ P→ Q
C) P→ Q ⇒ Q→ P
D) (Q → (P ∧ P)) → (R →(P ∧ P)) ⇒ R → Q
10． 设A=｛｛1,2,3｝, ｛4,5｝, ｛6,7,8｝,3｝，下式哪个式子为真( C D ) A: φ A; B: ｛6,7,8｝⊆ A; C: ｛｛4,5｝｝⊆ A; D: 3 A.
11. 设F （x ）：为有理数，G （x ）：为自然数，
命题“有理数不全是自然数”的符号化形式为（ A B ）
A) ┐ ∀x(F(x) → G(x)) B) ∃x(F(x) ∧┐ G(x))
C) ∃x(F(x) → G(x)) D) ∀x(F(x) ∧ G(x))
12. 设 P：2是素数， Q：5是素数， R: π是有理数。下面复合命题中为假的是（B C ）
A) (P ∧ Q ) ∨ R B) R ∧ (P ∨ Q )
C) （ P ∧ R） Q D) (P ∧ R) → Q
16．设个体域A=｛a,b ｝, 公式(∃x)P(x)∨(∀x)S(x)在A 上消去量词后为( B D )
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)）.
17. 下面哪些命题是真命题( B C D )
A) 如果2是偶数，那么一个命题公式的合取范式唯一；
B) 如果2是偶数，那么一个命题公式的主析取范式唯一；
C) 如果2是奇数，那么一个命题公式的析取范式唯一；
D) 如果2是奇数，那么一个命题公式的主合取范式不唯一。
18 设A=｛1,2,3,4,5,6｝上的关系为R =｛(i,z)|i>z｝，
则R 的逆关系的性质有( C D )
A) 对称的； B) 自反的；
C) 反自反的，可传递的； D) 反对称的.
C) 7; D) 10.
22. 给定下列联结词集合，哪个可构成联结词完备集( B D )
A) ｛ ∨，∧，┐｝ B) ｛↑ ｝
C) ｛┐， →， ↓｝ D) ｛┐，∧｝
四、运算题
（1）求命题公式((P→Q) ( ┐ Q→ ┐P)) ∧S 的最简等值式.
（2）命题公式(p → q) r
该公式的主析取范式为 __________________________________.
该公式的主合取范式为 __________________________________.
(3) 设集合集合X 上的关系R 和S 的关系矩阵为M R MS 给出关系R 和S 的集合表示
画出R ︒S 的关系图
3)求出R ︒S 的逆关系的关系矩阵
(7)求(P∧Q) ∨( ⌝P ∧R) ∨(Q∧R) 的主析取范式。
⇔ (P∧Q ∧R )∨( P∧Q ∧⌝R) ∨( ⌝P ∧ Q ∧R) ∨(⌝P ∧ ⌝Q ∧R)
⇔ m1 ∨ m3 ∨ m6 ∨ m7
主合取范式 =
(9)给定集合Ｘ＝｛a,b,c ｝, 且Ｒ是Ｘ中的二元关系。Ｒ的关系矩阵是
1 1 1
MR = 0 1 1 试求出R , R , R ⋂R 的关系矩阵。 1 0 1
（12）设A=｛0,1,2｝到B =｛0,2,4｝的关系为
R=｛|a,bA ∩B ｝，
则R = { ，，， } 。
（13）设集合A=｛1,2,3｝上的关系R=｛,,,｝， 该关系具有什么性质？
确定该关系的自反闭包、对称闭包、传递闭包
五、证明题
（1）用推理规则证明⌝t →m 是前提条件：p → (q→m), ⌝t →p, q的有效结论
（2）用形式推理规则证明： ~2~
结论 (∀x )( C(x) → ⌝ A(x))是
前提条件： ∀x (A(x) →B (x)), ∀x (C(x) →⌝B(x))的有效结论
（3）证明（∃ x）¬ A （x ）
是前提（∀x ）（A （x ）→¬ B （x ）），（∀ x）（B （x ）∨ C（x ）），
（∃x ）¬ C （x ）的有效结论。
(4) 设 A,B是集合，证明 P(A ∩B ） = P(A) ∩ P(B)
（5）给定集合X ，且R 是X 中的二元关系。试证明， R2 ⊆ R，当且仅当关系R
是可传递的。
（6）给定集合X ，且R 和S 是X 中具有传递性的二元关系。试证明R ∩S 也是可
传递的二元关系。