离散数学同步练习

《离散数学》试题及答案一、选择题（每题5分，共25分）1. 下列关系中，哪个是等价关系？（）A. 小于等于（≤）B. 大于等于（≥）C. 整除（|）D. 模2同余（≡）答案：D2. 下列哪个图是完全图？（）A. 无向图B. 有向图C. 简单图D. n阶完全图答案：D3. 设A和B为集合，若A∪B=A，则下列哪个结论成立？（）A. A⊆BB. B⊆AC. A=BD. A∩B=∅答案：B4. 下列哪个命题是永真命题？（）A. (p→q)∧(q→p)B. (p∧q)→(p∨q)C. (p→q)∧(p→¬q)D. (p∧¬q)→(p→q)答案：B5. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的最小生成树的边数是（）。

A. 4B. 5C. 6D. 7答案：B二、填空题（每题5分，共25分）6. 设A={1,2,3,4,5}，B={3,4,5,6,7}，则A∩B=_________。

答案：{3,4,5}7. 设图G的顶点集V={a,b,c,d}，边集E={e1,e2,e3,e4,e5}，其中e1=(a,b)，e2=(a,c)，e3=(b,d)，e4=(c,d)，e5=(d,a)，则G的邻接矩阵为_________。

答案：[0 1 1 0 0; 1 0 0 1 0; 1 0 0 1 0; 0 1 1 0 1;0 0 0 1 0]8. 设p为真命题，q为假命题，则(p∧q)∨(¬p∧¬q)的值为_________。

答案：真9. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的度数序列为（3,3,3,3,3,3），则G的边数是_________。

答案：1510. 下列命题中，与“若p，则q”互为逆否命题的是_________。

《离散数学》练习题和参考答案《离散数学》练习题和参考答案⼀、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）3、设有下列公式，请问哪⼏个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2），（3），（4），（5），（6）4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，⾃由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )北京是中华⼈民共和国的⾸都。

(2) 陕西师⼤是⼀座⼯⼚。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三⾓形有4条边。

(5) 前进！(6) 给我⼀杯⽔吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在⼀些⼈是⼤学⽣”的否定是( )，⽽命题“所有的⼈都是要死的”的否定是( )。

答：所有⼈都不是⼤学⽣，有些⼈不会死7、设P：我⽣病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在⽣病时，我才不去学校 (2) 若我⽣病，则我不去学校(3) 当且仅当我⽣病时，我才不去学校(4) 若我不⽣病，则我⼀定去学校答：（1）PQ→（2）QP?→（3）QP?（4）QP→8、设个体域为整数集，则下列公式的意义是( )。

(1) ?x?y(x+y=0) (2) ?y?x(x+y=0)答：（1）对任⼀整数x存在整数 y满⾜x+y=0（2）存在整数y对任⼀整数x满⾜x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( )(3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) ⾃然数(2) 实数 (3) 复数(4) (1)--(3)均成⽴答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（1)设：p：派小王去开会。

q：派小李去开会.则命题：“派小王或小李中的一人去开会" 可符号化为：（p q) (p q）。

（2）设A,B都是命题公式，A B，则A B的真值是T。

（3）设:p：刘平聪明。

q：刘平用功。

在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：p q .（4）设A , B 代表任意的命题公式，则蕴涵等值式为A B A B。

（5）设，p：径一事;q：长一智。

在命题逻辑中,命题:“不径一事，不长一智。

" 可符号化为： p q 。

（6）设A , B 代表任意的命题公式，则德摩根律为（A B）Û A B）。

（7）设，p：选小王当班长;q：选小李当班长.则命题：“选小王或小李中的一人当班长。

”可符号化为: （p q）（p q） .（8）设，P：他聪明；Q：他用功。

在命题逻辑中，命题:“他既聪明又用功。

" 可符号化为：P Q .（9）对于命题公式A,B,当且仅当 A B 是重言式时，称“A蕴含B”，并记为A B。

（10)设:P：我们划船.Q:我们跑步.在命题逻辑中，命题:“我们不能既划船又跑步.”可符号化为：（P Q) 。

（11）设P，Q是命题公式,德·摩根律为：（P Q）P Q) 。

（12）设P:你努力.Q：你失败。

在命题逻辑中，命题：“除非你努力，否则你将失败。

”可符号化为：P Q .（13）设p：小王是100米赛跑冠军。

q:小王是400米赛跑冠军。

在命题逻辑中，命题：“小王是100米或400米赛跑冠军.”可符号化为：p q。

（14）设A，C为两个命题公式，当且仅当A C为一重言式时,称C可由A逻辑地推出。

二．判断题1.设A，B是命题公式，则蕴涵等值式为A B A B。

（）2.命题公式p q r是析取范式。

( √ )3.陈述句“x + y > 5”是命题。

《 离散数学 》同步测试1、命题逻辑一．填空：1．公式)()(s r q p ∨→∧的真值表中共有 16 种真值指派。

2．命题公式（⌝P →Q ）→（⌝ Q ∨ P ）的主析取范式为001011m m m ∨∨或（P ∧Q ）∨（P ∧⌝ Q ）∨（⌝P ∧⌝Q ） ，主合取范式为：01M 或P ∨⌝ Q 。

3．设A 、B 、C 和D 四个人中派两个人出差，需要满足下列条件：（1）若A 去，则C 和D 中要去一人；（2）B 和C 不能都去；（3）C 去则D 要留下。

则有3 种派法，分别为 AC,AD,BD 。

4．给定命题公式：P ∨（⌝P →（Q ∨(⌝ Q →R )）则它的成真指派为001，010，011，100，101，110，111，成假指派为000。

二．判断下列命题的对错。

正确的在括号内填√,错误的在括号内填×。

1、设A 、B 、C 为任意命题公式，若A ∨B ⇔ B ∨ C ，则A ⇔ B 。

（ × ）2、设A 、B 为任意命题公式，若⌝ A ⇔⌝ B ，则A ⇔ B 。

（ √ ）3、公式)()(q p q p ∨→∧是重言式。

（ √ ）4、公式P ∧Q 是合取范式，不是析取范式。

（ × ）5、所有极大项的析取为永真式。

（√ ）6、一个命题公式可以有多个与之等价的析取范式。

（√ ）7、任一命题的主合取范式是唯一的。

（√）8、下面推理是正确的： （ × ）（1）P →Q P（2）⌝P P（3）⌝Q T(1)(2)9、公式（P ∧Q ）→（R ∨ ⌝S ）的对偶式为（P ∨Q ）→（R ∧ ⌝S ）。

（ × ）10、公式（⌝P ∨Q ）∧（P →R ）与P →（Q ∧ R ）。

（ √ ）三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内(多选不给分)。

1、给定命题公式如下：A ．（P ↔Q ）↔（P →Q ）∧（Q → P ）B ．（P ∧⌝P ）↔ QC ．（P ∨⌝P ）→（（Q ∧⌝ Q ）∧R ）则重言式为：( A ) ，矛盾式为：( C )，可满足式为：( B )2．给定命题公式如下：（⌝P →Q ）→（⌝ P ∧Q ）该命题公式的成真赋值个数是（D），成假赋值个数是（B），与它等价的主析取范式中极小项个数为（D），主合取范式中极大项个数为（B）A．0 B．1 C．2 D．3 E. 43．给定命题公式：P∨（Q∧R）则它的成真赋值为（A），成假赋值为（C）A．111，011，100，101，110 B．111，011C．000，010，001 D．0004．给定真值表：则F等价于（ D ）A．P ∧Q B．P∨Q C．P→Q D．⌝P∨⌝Q5．给定命题公式：（⌝P∨Q）∧（P→ R），与之等价的是(C )A．P→（⌝ Q∧R）B．P→（Q∨R）C．P→（Q∧R）D．⌝P→（Q∧R）6．前提条件：P→（Q →S），Q, P∨⌝R,则它的有效推论为(B )A．S B．R→S C．P D．R→Q同步测试2、谓词逻辑一．填空：1．对谓词公式（（∀x）P（x）∨（∃y）Q（y））→（∀x）R（x）中约束变元应用变换规则所得到的前束范式是（∃x）（∀ y）（∀z）（P（x）∨Q（y））→R（z））2．谓词公式（∀x）（P（x）→Q（x））∧（∃z）（R（x）∧S（z））中，量词（∀x）的辖域为（P（x）→Q（x））。

离散数学练习题(含答案)题目1. 对于集合 $A={1,2,3,...,10}$ 和 $B={n|n是偶数，2<n<8}$，求 $A \cap B$ 的元素。

2. 存在三个可识别的状态A,B,C。

置换群 $S_3$ 作用在状态集上。

定义四个动作：$α: A → C, β: A → B, γ: C→ A, δ: B→ C$。

确定式子，描述 $\{α,β,γ,δ\}$ 的乘法表。

3. 证明 $\forall n \in \mathbb{N}$，合数的个数不小于$n$。

4. 给定一个无向带权图，图中每个节点编号分别是$1,2,...,n$，证明下列结论：a. 如果从节点$i$到$j$只有一条权值最小的路径，则这条路径的任意子路径都是最短路径。

b. 如果从节点$i$到$j$有两条或两条以上权值相等的路径，则从$i$到$j$的最短路径可能不唯一。

答案1. $A \cap B = \{2,4,6\}$。

2. 乘法表：3. 对于任意$n$，我们可以选择$n+1$个连续的自然数$k+1,k+2,...,k+n,k+n+1$中的$n$个数，其中$k \in \mathbb{Z}$。

这$n$个数构成的$n$个正整数均为合数，因为它们都至少有一个小于它自身的因子，所以不是质数。

所以合数的个数不小于任意$n$。

4.a. 根据题意，从$i$到$j$只有一条权值最小的路径，即这条最短路径已被确定。

如果从这条路径中任意取出一段子路径，假设这段子路径不是这个节点到$j$的最短路径，那么存在其他从$i$到$j$的路径比这段子路径更优，又因为这条路径是最短路径，所以这段子路径也一定不优于最短路径，矛盾。

所以从这条路径中任意取出的子路径都是最短路径。

b. 如果从节点$i$到$j$有多条权值相等的路径，则这些路径权值都是最短路径的权值。

因为所有最短路径的权值相等，所以这些路径的权值就是最短路径的权值。

所以从$i$到$j$的最短路径可能不唯一。

离散数学-习题集《离散数学》习题集第⼀部分判断题⼀、第⼀章—集合1、（）已知集合A的元素个数为10，则集合A的幂集的基=102。

2、（）已知两个集合A、B，若A中的元素都是B中的元素，则记为A∈B。

2、（）已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。

3、( ) 已知两个集合A={Ф，{Ф}}，B={Ф}，则A∩B={Ф}。

4、（）已知两个集合A={Ф，{Ф}}，B={Ф}，则A∩B=Ф。

5、（）已知两个集合A、B，若A中的元素都是B中的元素，则记为A∈B。

6、（）已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。

7、（）已知集合A的元素个数为n，则A×A的幂集的元素个数为n2。

8、（）已知两个集合A、B，则A-B是由属于B但不属于A的元素构成的集合。

⼆、第⼆章—⼆元关系1、（）若R是A上的⼆元关系，I A是A上的恒等关系，则当且仅当I A∈R时，R是A上的⾃反关系。

2、（√）若R是集合A上的⼆元关系，且当（a，b）∈R且（a，c）∈R时，就有（b，c）∈R，则R是A 上的可传递关系。

3、（）设A是集合，A1、A2、．．．A n都是A的⾮空⼦集，令S={A1，A2，．．．,A n}，则如果S是集合A的⼀个划分，那么S⼀定是集合A的⼀个完全覆盖；反之亦然。

5、（）R是⾮空集合A上的等价⼆元关系，则A关于R的商集A/R是集合A的⼀个划分，但不是A的⼀个完全覆盖。

6、（）已知集合A有4元素，易知集合A共有24个互不相同的⼦集合，所以在集合A上⼀共可定义24个互不相同的⼆元关系。

7、（）若R1和R2都是集合A上的可传递⼆元关系，则R1∪R2也是A上的传递关系。

8、（）设R是有限的⾮空集合A上的偏序关系，则A必有极⼤（⼩）元和最⼤（⼩）元。

9、（）若R1和R2都是集合A上的相容关系，则R1∩R2也是A上的相容关系。

10、（）若R1和R2都是集合A的可传递⼆元关系，则R1∩R2也是A上的传递关系。

《离散数学》练习题和参考答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P 答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P 答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PQ→⌝（2）QP⌝→（3）QP⌝↔（4）QP→⌝8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

离散数学-题库1、将下列命题推理符号化并给出形式证明：已知张三或李四的彩票中奖了；如果张三的彩票中奖了，那么你是知道的；如果李四的彩票中奖了，那么王五的彩票也中奖了；现在你不知道张三的彩票中奖。

所以李四和王五的彩票都中奖了。

答案：解：设：p:张三的彩票中奖了。

q：李四的彩票中奖了。

r：你知道张三的彩票中奖。

s：王五的彩票中奖了。

符号化:前提：p∨q,p→r,q→s,￢r结论：q∧s证明：（1）￢r 前提（2）p→r 前提（3）￢p (1)(2)拒取式（4）p∨q 前提（5）q (3)(4)析取三段论（6）q→s 前提（7）s （5）（6）假言推理（8）q∧s （5）（7）合取引入2、用推导法求下列公式的主合取范式和主析取范式：（(￢P∨Q）→R)答：（(￢P∨Q）→R)⇔(￢(￢P∨Q)∨R)⇔((P∧￢Q)∨R)⇔((P∨R)∧(￢Q∨R))⇔((P∨(Q∧￢Q)∨R)∧((P∧￢P)∨￢Q∨R))⇔((P∨Q∨R)∧(P∨￢Q∨R)∧(￢P∨￢Q∨R))⇔((P∧Q∧R)∨(P∧￢Q∧R)∨(P∧￢Q∧￢R)∨(￢P∧Q∧R)∨(￢P∧￢Q∧R))3、设集合 A ={1,2,3,4},A上二元关系R ={<1,2>,<2,2>,<,2,4〉,<3,4>}. 求其自反闭包，对称闭包和传递闭包。

答案： r(R)={<1,1>,<1,2>,<2,1>,<2,3>,<3,4>,<2,2>,<3,3>,<4,4>} s(R)={<1,1>,<1,2>,<2,1>,<2,3>,<3,4>,<3,2>,<4,3>}t(R)={<1,1>,<1,2>,<2,1>,<2,3>,<3,4>,<1,3>,<2,2>,<2,4>,<1,4>}4、设A,B,C是三个集合，证明（A∩B）-C=(A-C)∩B答案：答：（A∩B）-C=(A∩B)∩C=(A∩C)∩B=(A-C)∩B5、证明等价式：(∃χ)(A(χ)→B(χ))⇔(∀χ)A(χ)→(∃χ)B(χ)答案：(∃χ)(A(χ)→B(χ))⇔(∃χ)￢(A(χ)∨B(χ))⇔(∃χ)￢A(χ)∨(∃x)B(χ) ⇔￢(∀χ)A(χ)∨(∃χ)B(χ)⇔￢(∀χ)A(χ)→(∃χ)B(χ)6、设复数集合C={a+bi|a,b∈R,a≠0},定义C上二元关系R：<a+bi,c+di>∈R当且仅当ac>0,证明：R为等价关系。

《离散数学》练习题库（加粗红色字体为2013下新增题目）一、选择题1、G是一棵根树，贝ij （）oA、G—定是连通的C、G只有一个顶点的出度为02、下而哪个语句不是命题（）。

A、中国将成功举办2008年奥运会C、我说的不是真话B、G —定是强连通的D、G只有一个顶点的入度为1B、一亿年前地球发生了大灾难D、哈密顿图是连通的3、设R是实数集合，在上定义二元运算佗a, bWR, a*b=a+b-ab,则F面的论断屮正确的是（）。

A、（）是*的零元B、1是*的幺元C、0是*的幺元D、*没有等幕元4、下面说法中正确的是（）。

C、有些无限集合没有可数子集D、有理数集合是不可数集合5、无向完全图心的不同构的生成了图有（）个。

A. 6B.5C.4D. 36、下I何哪一种图彳、一定是无向树？A、无回路的连通图有n个顶点n-1条边的连通图C、每对顶点间都有通路的图D、连通但删去一条边则不连通的图7、设集合A ={{1,2,3}, {4,5}, {6,7,8}},则下列各式为真的是（）。

A. I E A B・{{4,5}}uAC. (1,2, 3}cAD. 0G A8、在有界格屮，若一个元素有补元，则补元（）。

A、必惟一B、不惟一c、不一定惟一D、可能惟一9、设集合A={l,2,3,・・・,10},下面定义的哪种运算关于集合A是不封闭的？（）A、x*y=max{x,y}B、x*y=min{x,y}C^ x*y=GCD(x,y),即x,y的最大公约数D、x*y=LCM(x,y),即x,y的最小公倍数_i o r10.集合X中的关系R,其矩阵是110,则关于R的论述中正确的是()o1 I 1A、R是对称的B、R是反对称的C、R是反自反的D、R中有7个元素11.下列各组数中，哪个可以构成无向图的度数列()。

A.1, 1, 1, 2, 2B.2, 2, 2, 2, 3C.1, 2, 2, 4, 6D.2, 3, 3, 312.*是定义在Z上的二元运算，Vx,yeZ,x^y = xy + x-y,则*的幺元和零元分别是()。

离散数学试题及答案解析一、选择题1. 在集合{1,2,3,4}中，含有3个元素的子集有多少个？A. 4B. 8C. 16D. 32答案：B解析：含有3个元素的子集可以通过组合数公式C(n, k) = n! / [k!(n-k)!]来计算，其中n为集合的元素个数，k为子集中的元素个数。

在本题中，n=4，k=3，所以C(4, 3) = 4! / [3!(4-3)!] = 4。

2. 下列哪个命题是真命题？A. 所有偶数都是整数。

B. 所有整数都是偶数。

C. 所有整数都是奇数。

D. 所有奇数都是整数。

答案：A解析：偶数是指能被2整除的整数，因此所有偶数都是整数，选项A是真命题。

选项B、C和D都是错误的，因为并非所有整数都是偶数或奇数。

二、填空题1. 逻辑运算符“非”（NOT）的真值表是：当输入为真时，输出为______；当输入为假时，输出为真。

答案：假解析：逻辑运算符“非”（NOT）是一元运算符，它将输入的真值取反。

如果输入为真，则输出为假；如果输入为假，则输出为真。

2. 命题逻辑中，合取词“与”（AND）的真值表是：当两个命题都为真时，输出为真；否则输出为______。

答案：假解析：合取词“与”（AND）是二元运算符，只有当两个命题都为真时，输出才为真；如果其中一个或两个命题为假，则输出为假。

三、简答题1. 解释什么是等价关系，并给出一个例子。

答案：等价关系是定义在集合上的一个二元关系，它满足自反性、对称性和传递性。

例如，考虑整数集合上的“同余”关系。

对于任意整数a，b，如果a和b除以同一个正整数n后余数相同，则称a和b模n同余。

这个关系是自反的（a同余a），对称的（如果a同余b，则b同余a），并且是传递的（如果a同余b且b同余c，则a同余c）。

2. 什么是图的连通性？一个图是连通的需要满足什么条件？答案：图的连通性是指在无向图中，任意两个顶点之间都存在一条路径。

一个图是连通的需要满足以下条件：图中的任意两个顶点v和w，都可以通过图中的边相互到达。