离散数学模拟题及答案
- 格式:doc
- 大小:81.50 KB
- 文档页数:4
一、证明下列各题1、 (10分)证明蕴涵式:()P P Q Q ∧→⇒2、(10分)证明:,1111f g f g -⇒-I 为函数为函数。
5、 3、(10分)给定代数结构,N ⨯和{}0,1,⨯,其中N 是自然数集合,⨯是数的乘法。
设{}:0,1f N →,定义为:12,,()0k n n k N f n ⎧=∈=⎨⎩否则试证}01N ⨯≅⨯,,,。
4、(10分)给定代数结构,R *,其中R 是实数集合,对R 中任意元a 和b ,*定义如下:a b a b a b *=++⨯ 试证明:,R *是独异点。
二、求下列各题的解:1、试求下列公式的主析取范式和主合取范式(15分):()()P Q P Q ⌝∨⌝→⌝€2、(15分){}010*********R =设,,,,,,,,,,,,试求(1)、R R *,(2)、{}1R ↑,(3)、{}11R -↑,(4)、{}1R ⎡⎤⎣⎦,(5)、{}11R -⎡⎤⎣⎦3、(15分给定无向图,G V E =,如图,试求: F E DCA B(1) 从A 到D 的所有基本链; (2) 从A 到D 的所有简单链;(3) 长度分别是最小和最大的简单圈; (4) 长度分别是最小和最大的基本圈; (5) 从A 到D 的距离。
4、(15分)给定二部图12,,G E V =,如图 9v 8v 7v 6v 1V1v 2v 3v 4v 5v 2V 试求1V 到2V 的最大匹配一、证明下列各题1、 (10分)证明蕴涵式:()P Q P P Q →⇒→∧2、(10分)证明:()()()A B C A B A C ⨯-=⨯-⨯3、(10分)给定群,G ,则,G 为Abel 群⇔222()()(,())∀∀∈→=a b a b G a b a b4、(10分)给定代数结构,S *,其中S 中元为实数有序对,*定义为 ,,,2a b c d a c b d bd *=+++,试证,S *是可交换独异点。
离散数学试题及答案一、选择题1. 在集合论中,下列哪个选项表示两个集合A和B的并集?A. A ∩ BB. A ∪ BC. A - BD. A × B答案:B2. 命题逻辑中,下列哪个符号表示逻辑非?A. ∧B. ∨C. ¬D. →答案:C3. 在有向图中,如果存在一条从顶点u到顶点v的路径,那么称顶点v为顶点u的:A. 祖先B. 后代C. 邻居D. 连接点答案:B二、填空题1. 一个命题函数P(x)表示为“x是偶数”,那么其否定形式为________。
答案:x是奇数2. 在关系R上,如果对于所有的a和b,如果(a, b)∈R且(b, a)∈R,则称R为________。
答案:自反的三、简答题1. 简述什么是等价关系,并给出其三个基本性质。
答案:等价关系是一种特殊的二元关系,它满足自反性、对称性和传递性。
自反性指每个元素都与自身相关;对称性指如果a与b相关,则b也与a相关;传递性指如果a与b相关,b与c相关,则a与c也相关。
2. 解释什么是图的连通分量,并给出如何判断一个图是否是连通图。
答案:连通分量是指图中最大的连通子图,即图中任意两个顶点之间都存在路径。
判断一个图是否是连通图,可以通过深度优先搜索或广度优先搜索算法遍历整个图,如果所有顶点都被访问,则图是连通的。
四、计算题1. 给定命题公式P:((p → q) ∧ (r → ¬p)) → (q ∨ ¬r),证明P是一个重言式。
答案:通过使用命题逻辑的等价规则和真值表,可以证明P在所有可能的p, q, r的真值组合下都为真,因此P是一个重言式。
2. 给定一个有向图G,顶点集合V(G)={1, 2, 3, 4},边集合E(G)={(1, 2), (2, 3), (3, 4), (4, 1), (2, 4)}。
找出所有强连通分量。
答案:通过Kosaraju算法或Tarjan算法,可以找到图G的强连通分量,结果为{1, 4}和{2, 3}。
一、填空1.不能再分解的命题称为____________,至少包含一个联结词的命题称为____________。
2.一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100,则其主析取范式是__________________,其主合取范式是_________________。
3.设A={a,b,c},B={b,c,d,e},C={b,c},则( A ⋃ ⊕=____________。
4.幂集P(P(∅)) =________________。
5.设A为任意集合,请填入适当运算符,使式子A________A=∅;A________A’=∅成立。
6.设A={0,1,2,3,6},R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)},则D(R)=____________,R(R)=____________。
7.称集合S是给定非空集合A的覆盖:若S={S1,S2,…,S n},其中S i⊆A,S i≠Ø,i=1,2,…,n,且______ _____;进一步若_____ _______,则S是集合A的划分。
8.两个重言式的析取是____ ____式,一个重言式和一个永假式的合取式是式。
9.公式┐(P∨Q) ←→(P∧Q)的主析取范式是。
10. 已知Π={{a}{b,c}}是A={a,b,c}的一个划分,由Π决定的A上的一个等价关系是。
二、证明及求解1.求命题公式(P→Q)→(Q∨P)的主析取范式。
2.推理证明题1)⌝P∨Q,⌝Q∨R,R→S⇒P→S。
2) (∀x)(P(x)→Q(y)∧R(x)),(∃x)P(x)⇒Q(y)∧(∃x)(P(x)∧R(x))x)},S={〈x,y〉|x,y∈A∧(x=y+2)}。
3.设A={0,1,2,3},R={〈x,y〉|x,y∈A∧(y=x+1∨y=2试求R S R。
4.证明:R是传递的⇔R*R⊆R。
5.设R是A上的二元关系,S={<a, b>| 存在c∈A,使<a, c>∈R,且<c, b>∈R}。
离散数学试题及答案一、选择题1. 设A、B、C为三个集合,下列哪个式子是成立的?A) \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)B) \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)C) \(A \cup (B \cup C) = (A \cup B) \cup (A \cup C)\)答案:B2. 对于一个有n个元素的集合S,S的幂集中包含多少个元素?A) \(n\)B) \(2^n\)C) \(2 \times n\)答案:B二、判断题1. 对于两个关系R和S,若S是自反的,则R ∩ S也是自反的。
答案:错误2. 若一个关系R是反对称的,则R一定是反自反的。
答案:正确三、填空题1. 有一个集合A,其中包含元素1、2、3、4和5,求集合A的幂集的大小。
答案:322. 设a和b是实数,若a \(\neq\) b,则a和b之间的关系是\(\__\_\)关系。
答案:不等四、解答题1. 证明:如果关系R是自反且传递的,则R一定是反自反的。
解答:假设关系R是自反的且传递的,即对于集合A中的任意元素x,都有(x, x) ∈ R,并且当(x, y) ∈ R和(y, z) ∈ R时,(x, z) ∈ R。
反证法:假设R不是反自反的,即存在一个元素a∈A,使得(a, a) ∉ R。
由于R是自反的,所以(a, a) ∈ R,与假设矛盾。
因此,R一定是反自反的。
答案完整证明了该结论。
2. 已知集合A={1, 2, 3},集合B={2, 3, 4},求集合A和B的笛卡尔积。
解答:集合A和B的笛卡尔积定义为{(a, b) | a∈A,b∈B}。
所以,集合A和B的笛卡尔积为{(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}。
数理逻辑习题判断题1.任何命题公式存在惟一的特异析取范式 ( √ ) 2. 公式)(q p p →⌝→是永真式 ( √ ) 3.命题公式p q p →∧)(是永真式 ( √ ) 4.命题公式r q p ∧⌝∧的成真赋值为010 ( × ) 5.))(()(B x A x B x xA →∃=→∀ ( √ )6.命题“如果1+2=3,则雪是黑的”是真命题 ( × ) 7.p q p p =∧∨)( ( √ )8.))()((x G x F x →∀是永真式 ( × ) 9.“我正在撒谎”是命题 ( × ) 10. )()(x xG x xF ∃→∀是永真式( √ )11.命题“如果1+2=0,则雪是黑的”是假命题 ( × ) 12.p q p p =∨∧)( ( √ )13.))()((x G x F x →∀是永假式 ( × )14.每个命题公式都有唯一的特异(主)合取范式 ( √ ) 15.若雪是黑色的:p ,则q →p 公式是永真式 ( √ ) 16.每个逻辑公式都有唯一的前束范式 ( × ) 17.q →p 公式的特异(主)析取式为q p ∨⌝ ( × ) 18.命题公式 )(r q p →∨⌝的成假赋值是110 ( √ ) 19.一阶逻辑公式)),()((y x G x F x →∀是闭式( × )单项选择题1. 下述不是命题的是( A )A.花儿真美啊! B.明天是阴天。
C.2是偶数。
D.铅球是方的。
2.谓词公式(∀y)(∀x)(P(x)→R(x,y))∧∃yQ(x,y)中变元y (B)A.是自由变元但不是约束变元B.是约束变元但不是自由变元C.既是自由变元又是约束变元D.既不是自由变元又不是约束变元3.下列命题公式为重言式的是( A )A.p→ (p∨q)B.(p∨┐p)→qC.q∧┐q D.p→┐q4.下列语句中不是..命题的只有(A )A.花儿为什么这样红?B.2+2=0C.飞碟来自地球外的星球。
离散数学试题及答案一、单项选择题(每题2分,共20分)1. 在集合论中,空集的表示符号是()。
A. {0}B. ∅C. {}D. Ø答案:B2. 如果A和B是两个集合,那么A∩B表示()。
A. A和B的并集B. A和B的交集C. A和B的差集D. A和B的补集答案:B3. 命题逻辑中,p ∧ q的真值表中,当p和q都为假时,p ∧ q的值为()。
A. 真B. 假C. 不确定D. 无定义答案:B4. 在图论中,如果一个图中的任意两个顶点都由一条边相连,则称这个图为()。
A. 连通图B. 无向图C. 完全图D. 有向图答案:C5. 布尔代数中,逻辑或运算符表示为()。
A. ∧B. ∨C. ¬D. →答案:B6. 一个关系R是从集合A到集合B的二元关系,如果对于A中的每个元素x,B中都存在唯一的元素y与之对应,则称R为()。
A. 单射B. 满射C. 双射D. 单满射答案:C7. 在命题逻辑中,如果p是假命题,那么¬p的值为()。
A. 真B. 假C. 不确定D. 无定义答案:A8. 一个有向图是无环的,那么它一定是()。
A. 有向无环图B. 无向无环图C. 有向有环图D. 无向有环图答案:A9. 在集合论中,如果集合A是集合B的子集,那么A⊆B表示()。
A. A包含于BB. A是B的真子集C. A是B的超集D. A与B相等答案:A10. 命题逻辑中,p → q的真值表中,当p为真,q为假时,p → q 的值为()。
A. 真B. 假C. 不确定D. 无定义答案:B二、多项选择题(每题3分,共15分)1. 在集合论中,以下哪些符号表示的是集合的并集()。
A. ∪B. ∩C. ⊆D. ⊂答案:A2. 在图论中,以下哪些说法是正确的()。
A. 有向图可以是无环的B. 无向图可以是无环的C. 有向图一定是连通的D. 无向图一定是连通的答案:A B3. 在命题逻辑中,以下哪些符号表示的是逻辑与()。
离散数学练习题(含答案)题目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$的最短路径可能不唯一。
离散数学试题与答案试卷一一、填空20% (每小题2分)1.设}7|{)},5()(|{<∈=<∈=+xExxBxNxxA且且(+=⋃BA{0,1,2,3,4,6} 。
2.A,B,C表示三个集合,文图中阴影部分的集合表达式为。
3R,S的真值为1,则)()))(((SRPRQP⌝∨→⌝∧→∨⌝的真值= 1 。
4.公式PRSRP⌝∨∧∨∧)()(的主合取范式为)()(RSPRSP∨⌝∨⌝∧∨∨⌝。
5.若解释I的论域D仅包含一个元素,则)()(xxPxxP∀→∃在I下真值为1 。
6.设A={1,2,3,4},A上关系图为则R2 = {<a.b>,<a,c>,<a,d>,<b,d>,<c,d> 。
7.设A={a,b,c,d},其上偏序关系R的哈斯图为则R= {<a.b>,<a,c>,<a,d>,<b,d>,<c,d>} I A。
8.图的补图为9.设A={a,b,c,d} ,A上二元运算如下:那么代数系统<A,*>的幺元是 a ,有逆元的元素为a , b , c ,d,它们的逆元分别为 a , d , c , d 。
10.下图所示的偏序集中,是格的为 c 。
二、选择20% (每小题2分)1、下列是真命题的有(CD)A.}}{{}{aa⊆;B.}}{,{}}{{ΦΦ∈Φ;C.}},{{ΦΦ∈Φ;D.}}{{}{Φ∈Φ。
2、下列集合中相等的有(BC )A.{4,3}Φ⋃;B.{Φ,3,4};C.{4,Φ,3,3};D.{3,4}。
3、设A={1,2,3},则A上的二元关系有( C )个。
A.23 ;B.32 ;C.332⨯;D.223⨯。
4、设R,S是集合A上的关系,则下列说法正确的是(A )A.若R,S 是自反的,则SR 是自反的;B.若R,S 是反自反的,则SR 是反自反的;C .若R ,S 是对称的, 则S R是对称的;D .若R ,S 是传递的, 则S R 是传递的。
网络学院离散数学模拟试题1 考试时间120 分钟考试方式:开卷专业年级姓名学号一、选择填空题(每个空格3分,共30分)1.设A,B是集合,且φA,则_____必定成立。
D-B=A.A=B B.B⊆A C.A∩B=φD.A⊆B 2.{φ,{φ}}-φ=_____;CA. φ B. {φ} C. {φ,{φ}} D. {{φ}}3.设集合A={{0}},则P(A) =_____。
DA. P(P({0}))B. P({0})∪φC. P({0})∪{{0}}D. {φ,{{0}}}4.设有集合A={1,2,3,4},则从A到{0,1}的不同的函数有____个。
EA.0 B.1 C.4 D.12 E. 16 F. 24 G. 32 5.设G=(a)为12阶循环群,则G没有____阶子群。
EA.1 B.2 C.3 D.4 E. 5 F. 66.凡_____都满足消去律。
DA. 代数系统B. 半群C. 独异点D. 群7.从无向完全图K中至少删除____条边后,所得的图将成为平面图。
B5A.0 B.1 C.2 D.38.若无向图G是有99个结点,9个连通分量,则G中的边数必_____。
C A. ≤90 B. =90 C. ≥90 D. =100 E. ≥1009.下列句子中为命题的是_____。
AA.今天不是星期六。
B.考场内禁用手机!C.今天是周末吗?D.今天真冷呀!10. 任意两个不同极大项的析取式必为______。
AA. 永真公式B. 可满足公式C. 永假公式D. 等值公式二、求出谓词公式(,)(,,)u v F u v w G u v w ∃∃→∀的前束范式。
(10分)解:(,)(,,)u v F u v w G u v w ∃∃→∀ ⇔1111(,)(,,)u u F u v w G u v w ∃∃→∀ ⇔111(,)(,,)u v F u v w G u v w ⌝∃∃∨∀ ⇔1111(,)(,,)u y F u v w G u v w ∀∀⌝∨∀⇔1111(,)(,,)u v wF u vG u v w ∀∀∀⌝∨()三、用形式证明的方法证明下列论证的有效性:“本班有些同学是有经验的C++程序员,任何C++程序员都知道对象的概念。
《离散数学》模拟题北航10秋学期《离散数学》模拟题⼀⼀、单项选择题(本⼤题共15⼩题,每⼩题2分,共30分)1.∑中所有有限长度的串形成的集合记为∑* ,容易证得∑*上的连接运算不满⾜交换律,但满⾜( A ) A .结合律 B .分配律 C .幂等律 D .吸收律 2.Klein 群中元素a,b,c 的阶为( B )。
A .1B .2C .3D .4 3.群G 的元素x 的所有幂的集合为G 的⼦群,称由x ⽣成的⼦群。
记为( A ). A . B .(x) C .x D .[x] 4.交换环是指乘法满⾜( A )。
A .交换律B .结合律C .分配律D .吸收律 5.⾄少有( B )元素的含单位元、⽆零因⼦环称为除环。
A .⼀ B .⼆ C .三 D .四 6.∨,∧满⾜( C )的格称为分配格A .交换律B .结合律C .分配律D .幂等律 7.若L 为有限布尔代数,则( B )正整数n ,L 与含有n 个元素的集合A 的幂集同构。
A .不存在 B .存在 C .有可能存在 8.有向图D 的顶点v 作为边的始点的次数之和称为v 的出度,记为d +(v), v 作为边的终点的次数之和称为v 的⼊度,记为d -(v),v 的度数d(v)= ( A )。
A .d +(v)+d -(v)B .d +(v)C .d -(v)D .d +(v)*d -(v) 9.若通路Г=v 0e 1v 1e 2…e 1v 1 中所有顶点互不相同(所有边⾃然互不相同)时称为( B ) A .初级回路 B .路径 C .复杂通路D .迹 10.在n 阶图中,若⼀顶点存在到⾃⾝的回路,则必存在从该顶点到⾃⾝的长度不超过( B )的回路。
A .n-1 B .n C .n+1 D .2n 11.“⼈总是要死的”谓词公式表⽰为( C )。
(论域为全总个体域)M(x):x 是⼈;Mortal(x):x 是要死的。
A .)()(x Mortal x M →; B .)()(x Mortal x M ∧C .))()((x Mortal x M x →?; D .))()((x Mortal x M x ∧?12. 公式))()((x Q x P x A →?=的解释I 为:个体域D={2},P(x):x>3, Q(x):x=4则A 的真值为( A )。
离散数学试题及答案解析一、选择题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,都可以通过图中的边相互到达。
离散数学考试题目及答案一、单项选择题(每题2分,共20分)1. 集合A={1,2,3},集合B={3,4,5},则A∩B的元素个数为:A. 0B. 1C. 2D. 3答案:B2. 函数f: X→Y是一个双射,当且仅当:A. f是单射且满射B. f是单射C. f是满射D. f是双射答案:A3. 命题p: "x是偶数",命题q: "x是3的倍数",下列逻辑运算中,表示"x是6的倍数"的是:A. p∧qB. p∨qC. ¬p∧¬qD. ¬p∨¬q答案:A4. 有向图G中,若存在从顶点u到顶点v的有向路径,则称顶点u可达顶点v。
若G中任意两个顶点都相互可达,则称G为:A. 强连通图B. 弱连通图C. 无向图D. 有向无环图答案:A5. 在二进制数系统中,下列哪个数的值最大?A. 1010B. 1100C. 1110D. 1101答案:C6. 布尔代数中,逻辑或运算符表示为:A. ∧B. ∨C. ¬D. →答案:B7. 有限自动机中,状态q0是初始状态,状态q1是接受状态。
若存在从q0到q1的ε-转移,则该自动机:A. 仅在输入为空时接受B. 仅在输入非空时接受C. 无论输入为何都接受D. 无法确定是否接受答案:C8. 命题逻辑中,若命题p和q都为真,则p∧q的真值是:A. 真B. 假C. 可能为真,也可能为假D. 无法确定答案:A9. 集合{1,2,3}的子集个数为:A. 4B. 6C. 7D. 8答案:D10. 若关系R在集合A上是自反的,则对于A中的任意元素a,有:A. (a,a)∈RB. (a,a)∉RC. (a,a)是R的自反对D. (a,a)不是R的自反对答案:A二、填空题(每题3分,共15分)1. 集合A={1,2,3}的幂集包含__个元素。
答案:82. 若函数f: X→Y是满射,则对于Y中的任意元素y,至少存在X中的一个元素x,使得f(x)=__。
离散数学试题+答案⼀、单项选择题(本⼤题共15⼩题,每⼩题1分,共15分)在每⼩题列出的四个选项中只有⼀个选项是符合题⽬要求的,请将正确选项前的字母填在题后的括号内。
1.⼀个连通的⽆向图G,如果它的所有结点的度数都是偶数,那么它具有⼀条( )A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路2.设G是连通简单平⾯图,G中有11个顶点5个⾯,则G中的边是( )A.10B.12C.16D.143.在布尔代数L中,表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( )A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数,·是复数乘法运算,则G=<{1,-1,i,-i},·>是群,下列是G的⼦群是( )A.<{1},·>B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉5.设Z为整数集,A为集合,A的幂集为P(A),+、-、/为数的加、减、除运算,∩为集合的交运算,下列系统中是代数系统的有( )A.〈Z,+,/〉B.〈Z,/〉C.〈Z,-,/〉D.〈P(A),∩〉6.下列各代数系统中不含有零元素的是( )A.〈Q,*〉Q是全体有理数集,*是数的乘法运算B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合,*是矩阵乘法运算C.〈Z,ο〉,Z是整数集,ο定义为xοxy=xy,?x,y∈ZR具有的性质是A.⾃反性B.对称性C.传递性D.反⾃反性8.设A={a,b,c},A上⼆元关系R={〈a,a〉,〈b,b〉,〈a,c〉},则关系R的对称闭包S(R)是( )A.R∪I AB.RC.R∪{〈c,a〉}D.R∩I A9.设X={a,b,c},Ix是X上恒等关系,要使Ix∪{〈a,b〉,〈b,c〉,〈c,a〉,〈b,a〉}∪R为X上的等价关系,R应取( )A.{〈c,a〉,〈a,c〉}B.{〈c,b〉,〈b,a〉}C.{〈c,a〉,〈b,a〉}D.{〈a,c〉,〈c,b〉}10.下列式⼦正确的是( )A. ?∈?B.C.{?}??D.{?}∈?11.设解释R如下:论域D为实数集,a=0,f(x,y)=x-y,A(x,y):x( )A.( ?x)( ?y)( ?z)(A(x,y))→A(f(x,z),f(y,z))B.( ?x)A(f(a,x),a)C.(?x)(?y)(A(f(x,y),x))D.(?x)(?y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式,谓词公式(?x)(A(x)→B)等价于( )A.(?x)A(x)→BB.(?x)A(x)→BC.A(x)→BD.(?x)A(x)→(?x)B13.谓词公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中变元x( )A.是⾃由变元但不是约束变元C.既是⾃由变元⼜是约束变元D.是约束变元但不是⾃由变元14.若P:他聪明;Q:他⽤功;则“他虽聪明,但不⽤功”,可符号化为( )A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q15.以下命题公式中,为永假式的是( )A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)⼆、填空题(每空1分,共20分)16.在⼀棵根树中,仅有⼀个结点的⼊度为______,称为树根,其余结点的⼊度均为______。
离散数学试题及答案一、选择题1. 下列哪个是由离散数学的基本概念组成的?A. 集合论和函数论B. 图论和逻辑C. 运算符和关系D. 全数论和数论答案:B2. 下列哪个是离散数学的一个应用领域?A. 数据结构和算法分析B. 微积分和线性代数C. 概率论和统计学D. 数值分析和微分方程答案:A3. 集合A={1, 2, 3},集合B={2, 3, 4},则A交B的结果是:A. {1, 2, 3, 4}B. {2, 3}C. {2}D. {1}答案:B4. 下列哪个是对于集合的补集运算的正确描述?A. A∪A' = ∅B. A∩A' = ∅C. A - A' = AD. A'∩B' = (A∪B)'答案:B5. 若命题p为真,命题q为假,则命题p→q的真值为:A. 真B. 假C. 不确定D. 无法确定答案:B二、填空题1. 对于命题“如果x是偶数,则x能被2整除”,其逆命题为________________。
答案:如果x不能被2整除,则x不是偶数。
2. 在一个完全图中,如果有12条边,则这个图有__________个顶点。
答案:6个顶点。
3. 设集合A={1, 2, 3, 4},则A的幂集的元素个数是__________。
答案:2^4=16个元素。
4. 设关系R={(-1, 0), (0, 1), (1, 0)},则R的逆关系是__________。
答案:R^(-1)={(0, -1), (1, 0), (0, 1)}。
5. 若集合A={1, 2, 3},集合B={2, 3, 4},则A的笛卡尔积B是__________。
答案:A×B={(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}。
三、计算题1. 求集合A={1, 2, 3}和集合B={2, 3, 4}的并集。
离散数学模拟卷2参考答案一、选择题1、请指出下列选项中哪一个是错谋的:(2)(1)0C0 (2) 060 ⑶ 0C{0} (4) 0G {0}2、对任意集合下述论断正确的是:(1)(1)若恥B,B U C,则AY⑵若则AuC(3)若AuSBwC,则A* ⑷若AaB9BeC f WlJ AcC3、假设 A 二{d#,c}上的关系R = {<a y a><a,bxa,cxc,a>}f那么,R是:⑴) (1)反自反的(2)反对称的(3)可传递的(4)不可传递的4、非空集合A上的空关系/?不具备下列哪个性质:(1)(1)白反性(2)反白反性(3)对称性(4)传递性5、若f:ATB,g:BT C是满射函数,则复合函数必是:(3)(1)双射函数(2)单射函数(3)满射函数(4)不单射也不满射6、假设人二{d",c}, B = {1,2]下列哪个关系是4到〃的函数:(3)(])于={v G,1 X a,2 >< Z?,l >< b,2 >< c,l >< c,2 >}⑵ f = {< >< a,b >< b,a >< b,b >< c.a >< c,c >}(3)/ = {v d,l x b,2〉v c,l >}(4)/ = {vl,ax2,bxl,c>}7、一个无向简单图G有加条边,农个顶点,则图中顶点的总度数为:(3)(1)(2) (3) 2m(4) 2nX、一个图是哈密顿图是指:(3)(1)图小包含-•条回路经过图小每条边一次且仅一次;(2)图中包含一条路经过图中每条边一次且仅一次;(3)图中包含一条回路经过图中每个顶点一次H.仅一次;(4)图屮包含一条路经过图中每个顶点一•次且仅一次。
9、一•棵树有2个2度顶点,1个3度顶点,3个4度顶点,则其1度的顶点数为:(2)(1)5 (2) 7 (3) 8 (4) 910、完全加叉树中有/片叶,「个分支点,则有关系式是:(2)(D z = Z -1 (2)(m -1)/ +1 = / (3)(血_“ = !(4)(m -1)/ = z -1二、填空题1、假设A = {{a,b},{c}}, B = {{a}y[h},{c}}试求出:A 的幕集p(A) =2、假设A = {x\x2 <30,xe正整数}, B = (x\x是正奇数,xv20}, C = {1,3,5}(1) (C —A) IJ (3— A) = {7911,13,15,17,19};(2)(BnC)-A=0;3、假设 A = {1,2,3,4}上的关系R = {< 2,3 >}, M:(1)r(R)二{v 1,1 >,<2,2>,v2,3>,v3,3>,v4,4>};(2)s(R) = {v2,3>,v3,2>h(3)”R) = {v2,3>};4、假设A = {1,2,3},仁g、h是A到A 的函数,其中:(a) /⑴=/(2) = /(3) = 1 ;(b) g⑴=1, g⑵=3, g(3) = 2; (c) /?(1) = 3 , /z(2) = /?(3) = 1 ;则:(1)丄是满射;(2)―是双射;5、设无向图G有36条边,冇6个3度的顶点,其余顶点度数均小于3,则G中至少有辽个顶点。
a 离散模拟答案11命题符号化(共6小题,每小题3分,共计18分)1.用命题逻辑把下列命题符号化a)假如上午不下雨,我去看电影,否则就在家里读书或看报。
b)我今天进城,除非下雨。
c)仅当你走,我将留下。
2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x,总存在y使得xy=1。
c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b.一、简答题(共6道题,共32分)1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋值。
(5分)2.设个体域为{1,2,3},求下列命题的真值(4分)a)x y(x+y=4)b)y x (x+y=4)3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。
(4分)4.判断下面命题的真假,并说明原因。
(每小题2分,共4分)a)(A B)-C=(A-B) (A-C)b)若f是从集合A到集合B的入射函数,则|A|≤|B|5.设A是有穷集,|A|=5,问(每小题2分,共4分)a)A上有多少种不同的等价关系?b)从A到A的不同双射函数有多少个?6.设有偏序集<A,≤>,其哈斯图如图1,求子集B={b,d,e}的最小元,最大元、极大元、极小元、上界集合、下界集合、上确界、下确界,(5分)f gd eb c图17.已知有限集S={a1,a2,…,a n},N为自然数集合,R为实数集合,求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N(写出即可)(6分)二、证明题(共3小题,共计40分)1.使用构造性证明,证明下面推理的有效性。
(每小题5分,共10分)a)A→(B∧C),(E→F)→C, B→(A∧S)B→Eb)x(P(x)→Q(x)), x(Q(x)∨R(x)),x R(x) x P(x)2.设R1是A上的等价关系,R2是B上的等价关系,A≠且B≠,关系R满足:<<x1,y1>,<x2,y2>>∈R,当且仅当< x1, x2>∈R1且<y1,y2>∈R2。
一、 填空 15% (每小题 3分)1、 n 阶完全图结点v 的度数d(v) = 。
2、 设n 阶图G 中有m 条边,每个结点的度数不是k 的是k+1,若G 中有N k 个k 度顶点,N k+1个k+1度顶点,则N k = 。
3、 算式 )*()*)*(((f e d c b a ÷+的二叉树表示为。
4、 如图给出格L ,则e 的补元是 。
5、 一组学生,用二二扳腕子比赛法来测定臂力的大小,则幺元是 。
二、选择 15% (每小题 3分)1、设S={0,1,2,3},≤为小于等于关系,则{S ,≤}是( )。
A 、群;B 、环;C 、域;D 、格。
2、设[{a , b , c},*]为代数系统,*运算如下:* a b c a a b c b b a c cccc则零元为( )。
A 、a ;B 、b ;C 、c ;D 、没有。
3、如右图 相对于完全图K 5的补图为( )。
4、一棵无向树T 有7片树叶,3个3度顶点,其余顶点均为4度。
则T 有( )4度结点。
A 、1;B 、2;C 、3;D 、4。
5、设[A ,+,·]是代数系统,其中+,·为普通加法和乘法,则A=( )时,[A ,+,·]是整环。
A 、},2|{Z n n x x ∈= ;B 、},12|{Z n n x x ∈+= ;C 、},0|{Z x x x ∈≥且 ;D 、},,5|{4R b a b a x x ∈+=。
三、证明 50%1、设G 是(n,m )简单二部图,则42n m ≤。
(10分)2、设G 为具有n 个结点的简单图,且)2)(1(21-->n n m ,则G 是连通图。
(10分) 3、记“开”为1,“关”为0,反映电路规律的代数系统[{0,1},+,·]的加法运算和乘法运算。
如下:+ 0 1· 0 1 0 0 1 0 0 0 1111证明它是一个环,并且是一个域。
离散数学考试(试题及答案)一、(10分)某项工作需要派A、B、C和D 4个人中的2个人去完成,按下面3个条件,有几种派法?如何派?(1)若A去,则C和D中要去1个人;(2)B和C不能都去;(3)若C去,则D留下。
解设A:A去工作;B:B去工作;C:C去工作;D:D去工作。
则根据题意应有:A C D,(B∧C),C D必须同时成立。
因此(A C D)∧(B∧C)∧(C D)(A∨(C∧D)∨(C∧D))∧(B∨C)∧(C∨D)(A∨(C∧D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)F∨F∨(A∧C)∨F∨F∨(C∧D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F(A∧C)∨(B∧C∧D)∨(C∧D∧B)∨(C∧D)(A∧C)∨(B∧C∧D)∨(C∧D)T故有三种派法:B∧D,A∧C,A∧D。
二、(15分)在谓词逻辑中构造下面推理的证明:某学术会议的每个成员都是专家并且是工人,有些成员是青年人,所以,有些成员是青年专家。
解:论域:所有人的集合。
S(x):x是专家;W(x):x是工人;Y(x):x是青年人;则推理化形式为:∀x (S(x)∧W(x)),∃x Y(x)∃x(S(x)∧Y(x))下面给出证明:(1)∃x Y(x) P(2)Y(c) T(1),ES(3)∀x(S(x)∧W(x)) P(4)S( c)∧W( c) T(3),US(5)S( c) T(4),I(6)S( c)∧Y(c) T(2)(5),I(7)∃x(S(x)∧Y(x)) T(6) ,EG三、(10分)设A、B和C是三个集合,则A B⌝(B A)。
证明:A B x(x∈A→x∈B)∧x(x∈B∧x A)x(x A∨x∈B)∧x(x∈B∧x A) ⌝x(x∈A∧x B)∧⌝x(x B∨x∈A)⌝x(x∈A∧x B)∨⌝x(x∈A∨x B)⌝(x(x∈A∧x B)∧x(x∈A∨x B))⌝(x(x∈A∧x B)∧x(x∈B→x∈A))⌝(B A)。
一、 填空
1.不能再分解的命题称为,至少包含一个联结词的命题称为。
2.一个命题公式A(P , Q, R)为真的所有真值指派是000, 001, 010, 100,则其主析取范式是,其主合取范式是。
3.设 {},{},{},则( A ⋃ B ) ⊕C = 。
4.幂集 P(P(∅)) = 。
5.设A 为任意集合,请填入适当运算符,使式子∅;’=∅成立。
6.设{0,1,2,3,6},{〈〉≠y ∧(∈A)∧y≡x( 3)},则D(R),R(R)。
7.称集合S 是给定非空集合A 的覆盖:若{S 1,S 2,…,},其中⊆,≠Ø,1,2,…,n ,且 ;进一步若 ,则S 是集合A 的划分。
8.两个重言式的析取是 式,一个重言式和一个永假式的合取式是 式。
9.公式 ┐(P ∨Q) ←→(P ∧Q)的主析取范式是 。
10. 已知Π={{a}{}}是{}的一个划分,由Π决定的A 上的一个等价关系是 。
二、 证明及求解
1.求命题公式(P →Q )→(Q ∨P )的主析取范式。
2.推理证明题
1)⌝P ∨Q ,⌝Q ∨R ,R →S ⇒P →S 。
2) (∀x)(P(x)→Q(y)∧R(x)),(∃x)P(x)⇒Q(y)∧(∃x)(P(x)∧R(x))
3.设{0,1,2,3},{〈〉∈A ∧(1∨2x )},{〈〉∈A ∧(2)}。
试求οο。
4.证明:R 是传递的⇔R *R ⊆R 。
5.设R 是A 上的二元关系,{<a, b>| 存在c ∈A ,使<a, c>∈R ,且<c, b>∈R}。
证明:若R 是等价关系,则S 也是等价关系。
6.若→B 和→C 是双射,则()-1-1 1。
7.符号化下列命题,并证明结论的有效性。
只要今天天气不好,就一定有考生不能提前进入考场,当且仅当所有考生提前进入考场,考试才能准时进行。
所以,如果考试准时进行,那么天气就好。
8.画出集合{1,2,3,4,5,6}在偏序关系“整除”下的哈斯图,并讨论:
1)写出 {1,2,3,4,5,6}的最大(小)元和极大(小)元;
2)分别写出{2,3,6}和{2,3,5}的上(下)界、上(下)确界。
9. 设R 是{1,2,3,4,5}上的二元关系,{<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>},求r(R)、s(R)和t(R),并作出它们及R 的关系图。
参考答案
一、填空
1.原子命题;复合命题
2.0m ∨1m ∨2m ∨4m ;3M ∧5M ∧6M ∧7M
3.{}
4.{∅,{∅}}
5.⊕;∩
6.{0,3,6};{0,3,6}
7.S 1∪S 2∪…∪=S ; ∩=∅,1≤i<j ≤n
8.重言;永假
9.0m ∨1m
10. {<>,<>,<>,<>,<>}
二、证明及求解
1.解:(⌝p →q)→( ⌝q ∨p)⇔⌝(⌝p →q)∨(p ∨⌝q)
⇔⌝(p ∨q)∨(p ∨⌝q)
⇔(⌝p ∧⌝q)∨(p ∨⌝q)
⇔(⌝p ∨p ∨⌝q)∧(⌝q ∨p ∨⌝q)
⇔(p ∨⌝q)
⇔M1
⇔m0∨m2∨m3
2.1)证明:
(1)P 附加前提
(2)⌝P ∨Q P
(3)Q T(1)(2),I
(4)⌝Q ∨R P
(5)R T(3)(4),I
(6)R →S P
(7)S T(5)(6),I
(8)P →S
2) 证明
(1)∃(x)
P (2)P(a) (1)
(3)x(P(x)→Q(y)∧R(x)) P
(4)P(a)→Q(y)∧R(a) (3)
(5)Q(y)∧R(a) T(2)(4)
(6)Q(y) T(5)
(7)R(a) T(5)
(8)P(a)∧R(a) T(2)(7)
(9)∃x(P(x)∧R(x)) (8)
(10)Q(y)∧∃x(P(x)∧R(x)) T(6)(9)
3.解:
{<0,1>,<1,2>,<2,3>,<0,0>,<2,1>}{<2,0>,<3,1>},
ο{<1,0>,<2,1>},
οο{<1,1>,<1,0>,<2,2>}
4.证明若R是传递的,则<x,y>∈R*R z(∧)∧,由R是传递的得,即有<x,y>∈R,所以R*R⊆R。
反之,若R*R⊆R,则对任意的x、y、z∈A,如果且,则<x,y>∈R*R,于是有<x,y>∈R,即有,所以R是传递的。
5.证明由R是A上的等价关系,知<>∈R,故存在a∈A,使<>∈R,且<>∈R,
故<>∈S。
若<a, b>∈S,则存在c∈A,使<>∈R,且<>∈R,由R的对称性,<>∈R,且<>∈R,故<>∈S。
若<a, b>∈S,<>∈S,存在d∈A,使<>∈R,且<>∈R,存在e∈A,使<>∈R,且<>∈R,由R的传递性,故存在e∈A,使<>∈R,且<>∈R,
所以<a, c>∈S。
故S是等价关系。
6.证明:1)因为→B和→C均是双射,故1和1均存在,且1:B→A,1:C→B,所以-1 1:C →A。
由f和g是双射,可知也是双射,故()-1存在且()-1:C→A。
D(-1 1)()-1
2) 对任意c∈C⇒存在唯一b∈B,使得g(b)⇒存在唯一a∈A,使得f(a),故
(-1 1)(c)= (1(1(c))1(b)
但()(a)(f(a))(b)
故()-1(c)
因此对任意c∈C有:()-1(c)= (-1 1)(c)
由1),2)可知-1 1=()-1
7.解设P:今天天气好,Q:考试准时进行,A(e):e提前进入考场,个体域:考生的集合,则命题可符号化为:⌝P→x⌝A(x),(x)↔Q Q→P。
(1)⌝P→x⌝A(x) P
(2)⌝P→⌝(x) T(1),E
(3)(x)→P T(2),E
(4)(x)↔Q P
(5)((x)→Q)∧(Q→(x)) T(4),E
(6)Q→(x) T(5),I
(7)Q→P T(6)(3),I
8.1)最大元:无;最小元:1;极大元:4,5,6;极小元:1
2){2,3,6}的上界:6;下界:1;上确界:6;下确界:1。
{2,3,5}的上界:无;下界:1;上确界:无;下确界:1。
9.解:r(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,
<3,3>,<5,5>}
s(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>}
R25={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}
R3={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>}
R4={<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>}
t(R)={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>} 图请同学自己画出。