《离散数学》模拟试题3
一、 填空题（每小题2分，共20分）
1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）。
2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B ，
A ∩B __，A －B ，～A ∩～B 。
3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B ，
ρ（A ）－ρ（B ）。
4. 已知命题公式G =(⌝P ∧Q ) →R ，则G 的析取范式为 。
5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。
二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。）
1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）.
A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。
A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。
A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }}
4. 设集合A ＝{1,2,3}，A 上的关系R ＝{(1,1),(2,2),(2,3),(3,3),(3,2)}，
则R 不具备（ ）. 三、计算题（共50分）
1. （6分）设全集E ＝N ，有下列子集：A ＝{1，2，8，10}，B ＝{n |n 2
{n |n 可以被3整除，且n
2. （6分）设集合A ＝{a , b , c }，A 上二元关系R 1，R 2，R 3分别为：R 1＝A ×A ，
R 2 ＝{(a ，a ) ，(b ，b )}，R 3 ＝{(a ，a )}，试分别用
2－
定义和矩阵运算求R 1· R 2 ，R 2，R 1· R 2 · R 3 ， (R 1·R 2 ·R 3 ) 1 。 3. （6分）化简等价式（﹁P ∧（﹁Q ∧R ））∨（Q ∧R ）∨（P ∧R ）.
4. (8分) 设集合A ＝{1,2,3}，R 为A 上的二元关系，且 MR ＝
写出R 的关系表达式，画出R 的关系图并说明R 的性质.
5. （10分） 设公式G 的真值表如下.
试叙述如何根据真值表求G 的
主析取范式和主合取范式，并
写出G 的主析取范式和主合取范式.
0 1 1 1 0
6. (8分) 设解释I 为：
（1） 定义域D ＝{-2,3,6}； （2） F（x ）: x≤3 G（x ）: x＞5
在解释I 下求公式 ∃ x（F(x)∨G(x)）的真值.
7. （6分） 试用克鲁斯卡尔算法求下图所示权图中的最优支撑树. 要求画出
其最优支撑树，并求出权和.
四、证明题（每小题8分，共16分）
1. 设A ，B ，C 为三个任意集合，试证明： ( 8分) （1）（A －B ）－C ＝（A －C ）－(B －C ) （2）A ∪(B ∩C ) ＝A ∪（（B －A ）∩（A ∪C ）） （3）（A ∪（B －A ））－C ＝（A －C ）∪(B －C ) （4）（（A ∪B ∪C ）∩（A ∪B ））－（（A ∪（B －C ））∩A ）＝B －A
2. 证明下面的等价式： ( 8分) （1）（⌝ P ∧（⌝ Q ∧R ））∨（Q ∧R ）∨（P ∧R ）＝R （2）（P ∧（Q ∧S ））∨（⌝ P∧（Q ∧S ））＝（Q ∧S ） （3）P → (Q → R) ＝（P ∧Q ）→ R
（4）⌝( P Q ) ＝（P ∧⌝ Q）∨（⌝P ∧Q ）
《离散数学》模拟试题3参考答案
一、填空题
1. {φ，{φ}，{1}，{φ，1}，{φ，2}，{1，2}，A} 2. {a ，b ，c ，d ，e }；{a }；{b ，c }；φ
3. {3}；{{3}，{1，3}，{2，3}，{1，2，3}} 4 P ∨⌝Q ∨R . 5. P Q ，1
二、单项选择题
1. C 2. B 3. C 4. B
三、计算题
1. （1）A ；（2）{1}；（3）B ；（4）{2，4，8，9，16，32} 2. R 1 ·R 2 =={（a ，a ），（a ，b ），（b ，a ），（b ，b ），（c ，a ），（c ，b ）}；
2
R 2
={( a，a ) ，(a ，b )}；
R 1·R 2 ·R 3 = {( a，a ) ，(b ，a ) ，(c ，a )}；
(R 1·R 2 ·R 3) 1 = {( a，a ) ，(a ，b ) ，(a ，c )}； 3. 解：
（﹁P ∧（﹁Q ∧R ））∨（Q ∧R ）∨（P ∧R ） ＝（﹁P ∧（﹁Q ∧R ））∨（（Q ∨P ）∧R ） ＝（(﹁P ∧﹁Q) ∧R ））∨（（Q ∨P ）∧R ） ＝（(﹁P ∧﹁Q) ∨（Q ∨P ））∧R ＝（﹁(P∨Q) ∨（P ∨Q ））∧R ＝1∧R ＝R 4. 解：
R ＝{(1,1),(2,1),(2,2),(3,1) } 其关系图如下：
－
R 是反对称的和传递的.
5. 解：
将真值表中最后一列的1左侧的二进制数，所对应的极小项写出后，将其析取起来， 就得到G 的主析取范式.
于是，G ＝（﹁P ∧﹁Q ∧﹁R ）∨（﹁P ∧ Q∧﹁R ）∨（﹁P ∧ Q∧R ）∨（P ∧﹁ Q∧R ）. 将真值表中最后一列的0左侧的二进制数，所对应的极大项写出后，将其合取起来，
就得到G 的主合取范式.
于是，G ＝（P ∨Q ∨﹁R ）∧（﹁P ∨ Q∨R ）∧（﹁P ∨ ﹁Q ∨R ）∧（﹁P ∨﹁ Q∨﹁R ）. 6. 解：
∃ x ( F(x) ∨G(x))
⇔ ( F(-2) ∨G(-2)) ∨ ( F(3) ∨G(3)) ∨ ( F(6) ∨G(6))
⇔ (1∨0) ∨(1∨0) ∨(0∨1) ⇔ 1 7. 解：
下图的粗线条为该权图的最优支撑树，5条边.
权和为2+2+3+3+5＝15.
四、证明题
1. （1）
左边＝（A －B ）∩～C ＝A ∩～B ∩～C
右边＝（A ∩～C ）∩～（B ∩～C ）
＝（A ∩～C ）∩（～B ∪C ）
＝（A ∩～C ∩～B ）∪（A ∩～C ∩C ） ＝（A ∩～B ∩～C ）∪0 ＝A ∩～B ∩～C ＝左边 （2）
左边＝（A ∪B ）∩（A ∪C ）
右边＝A ∪（（B ∩～A ）∩（A ∪C ）） ＝A ∪（（B ∩～A ∩A ）∪（B ∩～A ∩C ）） ＝A ∪（B ∩～A ∩C ）
＝（A ∪B ）∩（A ∪～A ）∩（A ∪C ） ＝（A ∪B ）∩（A ∪C ） ＝左边
（3）
左边＝（A ∪（B ∩～A ））∩～C
＝（（A ∪B ）∩（A ∪～A ））∩～C ＝（A ∪B ）∩～C
＝（A ∩～C ）∪（B ∩～C ） ＝(A －C ) ∪（B －C ） ＝右边
（4）
左边＝（A ∪B ）－A
＝（A ∪B ）∩～A
＝（A ∩～A ）∩（B ∩～A ） ＝B －A ＝右边
2. （1） （⌝ P ∧（⌝ Q ∧R ））∨（Q ∧R ）∨（P ∧R ） ＝（⌝ P ∧（⌝ Q ∧R ））∨（（Q ∨P ）∧R ） ＝（（⌝ P ∧⌝ Q ）∧R ）∨（（Q ∨P ）∧R ） ＝（（⌝ P ∧⌝ Q）∨（Q ∨P ））∧R ＝（⌝（P ∨Q ）∨（Q ∨P ））∧R ＝1∧R ＝R
（2） （P ∧（Q ∧S ））∨（⌝ P ∧（Q ∧S ）） ＝（（Q ∧S ）∧P ）∨（（Q ∧S ）∧⌝P ） ＝（Q ∧S ）∧（P ∨⌝P ） ＝（Q ∧S ）∧1 ＝ Q ∧S （3） P → (Q → R )
＝ ⌝ P∨（⌝ Q∨R ） ＝（⌝ P∨⌝ Q）∨R ＝ ⌝（P ∧Q ）∨R ＝（P ∧Q ）→ R （4） ⌝(P Q ) ＝ ⌝（（P → Q）∧（Q →P ）） ＝ ⌝（（⌝ P∨Q ）∧（⌝ Q∨P ）） ＝ ⌝（⌝ P∨Q ）∨⌝（⌝ Q∨P ）
＝（⌝（⌝ P）∧⌝ Q）∨（⌝（⌝ Q）∧⌝P ） ＝（P ∧⌝ Q）∨（Q ∧⌝P ） ＝（P ∧⌝ Q）∨（⌝P ∧Q ）