2004级本科《离散数学i》考试试题（b卷）
注：考试结束后请将此题签与答题纸一并交回，否则后果自负！（2005-07-08）】
一、简答题【本大题共20小题，每小题2分，共40分】
1) 设集合a=，b=,求a－b和b－a。
2) 存在既具有对称性又具有反对称性的关系吗？若有，请举例说明。
3) 令a=，关系r=，试给出r所满足的两条性质（自反性、反自反性、对称性、反对称性、传递性）。
4) 设c=是集合a的一个划分，试求c所对应的等价关系rc（用m1, m2, m3来表示）。
5) 对于任意的部分序集(a,r)，极大元一定存在吗？最大元一定存在吗？
6) 设集合a、b，|a|=m，|b|=n，求a到b映射的个数。
7) 有理数集合是可数集合吗？其与整数集合等浓吗？
8) 请给出命题公式(pq)r的真值表。
9) 写出关于p、q的所有极大项。
10) 假设公式pq的真值为假，求(pq)q的真值。
11) 从命题公式的集合能演绎出公式s吗？
12) 设谓词公式g＝xp(x)xyq(x,y)，i是g的一个解释：
d=, p(a) p(b) q(a,a) q(a,b) q(b,a) q(b,b)
试确定公式g在i下的真值。
13) 设谓词公式g＝xp(x)xq(x)，h＝x(p(x)q(x))，则g与h等价吗？
14) hamilton图一定是连通图吗？其每个点的度数一定是偶数吗？
15) 一个有100个点的树，其所有点的度数之和是多少？
16) 设有n个点的连通图g，则c(g)是否一定是kn？
17) 请给出右侧权图中最优树中各边的权值之和。
18) 合同式18x6(mod 36)有解吗？若有，有几个？
19) 方程19x+37y =1在整数范围内一定有解吗？ 为什么？
20) a与b互质，a|bc，则是否一定有a|c。若没有，请举出反例。
1) 是否存在集合a满足a a×a？
2) 如果(a,r)为部分序集，则(a,r-1)是否也是部分序集？
3) 无限集是否一定是不可数集？
4) 命题公式g＝(pq)(pq)是否是恒真公式？
5) 谓词公式g的skolem范式s与g是否等价？
6) 任意图是否都有支撑树？
7) 有向图g是euler图，则g是否一定强连通？
8) 有根的有向图是否一定强连通？
9) p为质数，a为整数，且p不整除a，则p与a是否一定互质？
10) 设m≠0，c≠0，acbc(mod mc)，则是否一定有ab(mod m)?
1) 求命题公式g＝p(p→(q(q→r)))的主析取范式和主合取范式。
2) 设r是a上的等价关系，定义a上的关系s如下：
s=证明：s是a上的等价关系。
3) 用形式演绎法证明：共同蕴涵s。
4) 设g是由6个点v1, v2, …v6所构成的权图，g中任意两个不同点vi和vj之间恰有一条边，且边的权wij规定如下：
试求出v5到v6的最短路径和距离（要求写出求解算法具体步骤）。
5) 用辗转相除法解合同式67x 29（mod 1000）。
2019离散数学试题B
计算机应用专业。2005年3月。一 填空题 每小题3分，本题共15分 1 设r是集合a上的等价关系，则r所具有的关系的三个特性是。2.设命题公式，则公式g的合取范式是。3.设a是集合，且a 则a上的全关系a2 4.有限图g是树的一个等价定义是。5.设k5 是有5个点的完全图，则k5有条边。二 选择题...
离散数学B 2019离散数学A卷 郑州轻工业学院
c 既是自由变元，又是约束变元 d 既不是自由变元，又不是约束变。5 由huffman算法求出的带权为 的最优树的权为。a 75 b 80 c 83 d 87。二 判断题，对的写 t 错的写 f 每小题2分，共10分 1 群中仅有惟一的单位元。2 命题公式是可满足式。3 不是命题。4 无向图是二部图...
离散数学试题B卷
一 单项选择题 本大题共10小题，每小题2分，共20分 1 下列语句中为命题的是 a 这朵花是谁的？b 这朵花真美丽啊！c 这朵花是你的吗？d 这朵花是他的。2 设论域d 与公式xa x 等价的命题公式是 a a a a b b a a a b c a a a b d a b a a 3 下列各图中...