《离散数学基础》期中考试题
（附参考答案）
学 期：20XX－20XX 学年第X 学期 学生班级：XX 专业 XXXX-XXXX 班 考试时间：20XX.XX.XX XX:XX-XX:XX am 考试地点：
学号：
姓名：
班级：
□必修 □选修
一、填空题（共10分，每空1分）
1. 我们称 能够表达判断，并且具有确定真值 的陈述句为命题。 2. 在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是 唯一的 。 3. 把命题公式在其所有解释下所取真值列成一个表，称为G 的 真值表 。
4. 命题公式G=（P ∧Q ）→R ，则G 共有 8 个不同的解释；解释（F ，T ，F ）使G 的
真值为 T 。
5. 在推理理论中，前提在推导过程中的任何时候都可以引入使用，这一推理规则叫做 （ P 规则 ）。
6. 设集合}}{,{φφ=A ，A 的幂集
ρ(A )=φ,{φ},{{φ}},{φ,{φ}}{}
。
7. 设R 是集合A 上的二元关系，如果R 是自反的，则它的关系矩阵的主对角线元素（ 全是1 ）。 8. 设R 是集合A 上的二元关系，R -1是R 的逆关系，则R 的关系矩阵与R -1的关系矩阵具 有的关系是（ 互为转置矩阵 ）。
9. 设R 是集合A 上的二元关系，如果关系R 同时具有自反性、 反对称性 和传递性，
则称R 是A 上的一个偏序关系。
二、选择一个正确答案的代号，填入括号中。（共20分，每小题2分）
A ．地球外的星球上也有人；
B ．小王是我的同学，也是我的好朋友；
C ．11+1=100；
D ．我正在说慌。
2. 下列谓词公式中（ C ）不是命题。 A ．(∀x)P(x)； B ．(∃x)P(x)；
C ．(∀x)(P(x)∨P(y))；
D ．(∃x)(∃y)(P(x) →R(y))
3. 个体域为整数集合，下列公式中（ C ）不是命题。
A ．(∀x)(∀y)(x *y=y)；
B ．(∀x)(∃y)(x *y=1)；
C ．(∀x)(x *y=x)；
D ．(∃x)(∃y)(x *y=2)
4.下列谓词公式中（A）不正确。
A．(∃x)(A(x) →B) ⇔ (∃x) A(x) →B；B．(∃x)(B →A(x)) ⇔ B →(∃x) A(x)；
C．(∀x)(B →A(x)) ⇔ B →(∀x) A(x)；D．(∀x)(A(x)∨B) ⇔(∀x)A(x)∨B；
5.下列命题中正确的是（B）。
A．φ∪{φ}=φ；B．{φ,{φ}}-{{φ}}={φ}；
C．{φ,{φ}}-{φ}={φ，{φ}}；D．{φ,{φ}}-φ={{φ}}；
6.由集合运算定义，下列各式正确的有（A）。
A．X⊆X∪Y B.X⊇X∪Y C.X⊆X∩Y D.Y⊆X∩Y
7.设A,B,C为任意三个集合，下列各命题中正确的是（A）。仙魔经纪人
A．若A∈B且B⊆C，则A∈C；B．若A∈B且B⊆C，则A⊆C；
C．若A⊆B且B∈C，则A∈C；D．若A⊆B且B∈C，则A⊆C。
狼和小羊教学设计
8.设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），（b，b），（b，c），
（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，则R2是R1的（B）闭包。
A．自反B．对称C．传递D．以上都不是
9.设偏序关系R是集合A={1，2，3，4，5，6}中数的“整除”关系，则A的极大元、极
小元的个数分别是（ C ）。
A．2，1 B．2，2 C．3，1 D．3，2
10.设有函数
2,3
:,()
2,3
x x
f R R f x
寡头垄断x
⎧≥
→=⎨
−<
⎩
, :,()2
g R R g x x
→=+，则
()():
f g x R R
→
o是。
(A) 单射非满射; (B) 满射非单射;
(C) 不是单射也非满射; (D) 双射.
三、计算题（共40分，每小题10分）
1.求命题公式S=(P→(Q→R) )→ ((P→Q)→ (P→R))的真值表。
【解答】
P Q R Q→R P→(Q→R) P→Q P→R (P→Q)→
(P→R)
S
T T T T T F T F T T F F F T T F T F F F T F F F T
F
T
T
T
F
T
T
T
德国钢铁
F
T
T
T
T
T
T
T
T
F
F
T
T
T
T
T
F
T
F
T
T
T
T
T
F
T
T
晋中学院学报T
T
T
T
T
T
T
T
T
T
T
T
2.通过求主析取范式判断下列命题公式是否等值。
（1）（P∧Q）∨（¬P∧Q∧R）；
（2）（P∨（Q∧R））∧（Q∨（¬P∧R））；
【解答】
（P∧Q）∨（¬P∧Q∧R）
⇔（P∧Q∧（¬R∨R））∨（¬P∧Q∧R）
⇔（P∧Q∧¬R）∨（P∧Q∧R）∨（¬P∧Q∧R）
⇔m6∨m7∨m3
⇔m3∨m6∨m7
（P∨（Q∧R））∧（Q∨（¬P∧R））
⇔（P∧Q）∨（Q∧R）∨（P∧¬P∧R）∨（¬P∧ Q ∧R）（分配律）
⇔（P∧Q∧（¬R∨R））∨（（¬P∨P）∧Q∧R）∨（¬P∧ Q ∧R）
⇔（P∧Q∧¬R）∨（P∧Q∧R）∨（¬P∧Q∧R）∨（P∧Q∧R）∨（¬P∧ Q ∧R）
⇔m6∨m7∨m3∨m7∨m3
⇔m3∨m6∨m7
由此可见（P∧Q）∨（¬P∧Q∧R）⇔（P∨（Q∧R））∧（Q∨（¬P∧R））
3.某学校有597名学生，有299人选修数学，259人选修计算机，227人选修英语；其中
99人同时选修数学与计算机，68人同时选修数学与英语，33人同时选修计算机与英语。
画出文氏图，问该统计数字是否可能，并说明理由。若总人数是581呢？
【解答】（略）
4.设已知集合A={1,2,3,4,5,6}上的等价关系
R={(1,1),(1,5),(2,2),(2,3),(2,6),(3,2),(3,3),(3,6),(4,4),(5,1),(5,5),(6,2),(6,3)(6,6)} 求A的由R诱导出的划分。
【解答】
[1]={1,5}
[2]={2,3,6}
[4]={4}
A/R={[1],[2],[4]}={ {1,5},{2,3,6},{4}}
四、证明题（共30分）
1.用归纳法证明(A1→B)∧(A2→B)∧…∧(A n→B)∧(A1∨A2∨…∨A n)⇒B是一个正确的推理形式。【证明】
往证(A1→B)∧(A2→B)∧…∧(A n→B)∧(A1∨A2∨…∨A n)→B是一个永真式。用归纳法。
当n=1时，
(A1→B)∧A1→B⇔(¬A1∨B)∧A1→B
⇔¬((¬A1∨B)∧A1)∨B
巴山舞⇔¬((¬A1∧A1)∨(B∧A1)∨B
⇔¬(B∧A1∨B
⇔¬B∨¬A1∨B
⇔T
设当n=k-1时推理表达式为真，即设
(A1→B)∧(A2→B)∧…∧(A k-1→B)∧(A1∨A2∨…∨A k-1)→B是一个永真式。
令 C⇔(A1∨A2∨…∨A可－1)
D⇔(A1→B)∧(A2→B)∧…∧(A k-1→B)
即设C∧D→B为T。
当n=k时，
(A1→B)∧(A2→B)∧…∧(A k-1→B)∧(A k→B)∧(A1∨A2∨…∨A k-1∨A k)→B
⇔(D∧(A k→B)∧(C∨A k))→B
⇔¬(D∧(¬A k∨B)∧(C∨A k))∨B
⇔¬((D∧(¬A k∨B)∧C)∨((D∧(¬A k∨B)∧A k)))∨B
⇔……
⇔(C∧D→B)∨A k
⇔T∨A k
⇔T
所以原式是一个正确的推理形式。
2.设R是集合A上的二元关系，证明
（1）R是反自反的⇔I A∩R = ∅；
（2）R是反对称的⇔R∩R-1⊆ I A
【证明】
（1）R是反自反的
⇔(∀a)(a∈A→(a,a)∉A)，但(∀a)(a,a)∈I A
⇔(∀a)((a,a)∉A)∧(a,a)∈I A)⇔I A∩R = ∅。
（2）设R是反对称的，任取a∈A，b∈A，如果(a,b)∈R∩R-1，则有(a,b)∈R且(a,b)∈R-1，也即(a,b)∈R且(b,a)∈R ，由R的反对称性，a=b，所以(a,b)=(a,a)∈ I A，从而得，R ∩R-1⊆I A。
反之，若R∩R-1⊆I A，设(a,b)∈R，(b,a)∈R，则有，(a,b)∈R且(a,b)∈R-1，也即(a,b)∈R ∩R-1， 再由R∩R-1⊆ I A，得到(a,b)∈ I A，从而a=b。
3.设R是一个关系，用R-1表示R的逆关系，s(R)表示S的对称闭包，证明s(R)=R∪R-1。【证明】
①任取(x,y)∈ R∪R-1，则(x,y)∈ R或(x,y)∈ R-1，若(x,y)∈ R，则有(y,x)∈R-1，所
以(y,x)∈ R∪R-1；若(x,y)∈ R-1 ，则有(y,x)∈R，所以(y,x)∈ R∪R-1 ，R∪R-1具有对称性；
②显然，R ⊆ R∪R-1
③对A上任意关系R′′， 若R⊆ R′′，且R′′是对称的，往证R∪R-1⊆R′′。 任取(x,y)∈R
∪R-1，则(x,y)∈R或(x,y)∈R-1，若(x,y)∈R，因为R⊆R′′，则(x,y)∈R′′；若(x,y)∈R-1，则有(y,x)∈R，则(y,x)∈R′′，因为R′′是对称的，所以(x,y)∈R′′ ， 因此，R∪R-1⊆R′′。
综上，根据闭包的定义可知，s(R)=R∪R-1。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议