2005-2006《离散数学》试卷。
一．单项选择题。
1．设命题公式 (p (q p))，记作g，使g的真值指派为0的p，q的真值是(c)
a)(0,0) (b)(0,1) (c)(1,0) (d)(1,1)
2．与命题公式p （q r）等值的公式是(b)
a)(p q) r (b)(p q) r (c)(p q) r (d)p (q r)
3.不满**换律的是(a)
a)单条件 (b)析取 (c)合取 (d)双条件
4．设个体域为整数集，下列公式中其真值为1的是(a)
a))0( yxyx (b))0( yxxy
c))0( yxyx (d))0( yxyx
5．在谓词演算中，p(a)是( x)p(x)的有效结论，根据是(c)
a)us规则(b)ug规则(c)es规则(d)eg规则。
6.设s1＝ ，s2＝,s3＝p(),s4＝p( )以下命题为假的是(a)
a)s2 s4(b)s1 s3，(c)s4 s2(d)s4 s3
7.设集合a＝,a上的空关系不具备(d)性质。
a)传递性(b)反对称性(c)对称性(d)自反性。
8．设a＝,b=,则a b的恒等关系是(a)
a)(b)c)(d)
9.设集合a＝,在集合a上定义的运算 ，不是封闭的为(a)
a) a,b a,a b=lcm(最小公倍数)
b) a,b a,a b=gcd(最大公约数)
c) a,b a,a b=max
d) a,b a,a b=min
10.在自然数n上定义的二元运算 ，满足结合律的是(c)
a)a b=a－b(b)a b=a+2b(c)a b=max(d)a b= a－b
11.下列代数系统(g,*)中，其中*是加法运算。(d)不是群。
a)g为整数集合 (b)g为偶数集合。
c)g为有理数集合(d)g为自然数集合。
12．在图g＝中，结点总度数与边数的关系是(c)
a)deg(vi)=2 e
b)deg(vi)= e
c）vev2)deg(
d) vvev)deg(
二．填空题。
1．设f(x)：x是素数，e(x)：x是偶数，命题“不是所有的素数都不是偶数”符号化为：x(f(x) e(x))或 x（f（x） e（x）
3．设r是集合a＝上的二元关系，其中r＝
则r。r＝；
4.设集合a=,r是a上的二元关系，且r=
则r的自反闭包；
r的对称闭包；
r的传递闭。
8．设g是n个结点的无向完全图，则图g的边数为n(n-1)/2,其点连通度为n-1；
9.有限布尔格中有n个原子，则此布尔格中元素个数为2n；
10．4个元素的集合共有15个不同的划分；
三．（8分）符号化下列命题，并用推理规则推证其结论；
所有有理数是实数，某些有理数是整数，因此某些实数是整数。
解：q(x):x是有理数，r(x):x是实数，i(x):x是整数，五．（8分）设a＝,r是a上的二元关系r＝证明r是a上的偏序关系，并画出哈斯图，并判断此偏序集是否为格；
七．（8分）设t是图，证明以下关于树的定义是等价的。
1）无回路的连通图。
2）每一对结点间有且仅有一条路。
证明（1）->2）
因为t是连通图，故每一对结点间至少有一条路；但t中又没有回路，因此每一对结点间的路只有一条；
t中每一对结点间有一条路，t是连通图；
t中每一对结点间的路只有一条，因此t中没有回路。
8．（8分）求(p∧q)∨(p∧r)的主合取范式和主析取范式；
解：主析取范式为：7,6,3,1
主合取范式为： 5,4,2,0
离散试题练习
1.求下列各公式的主析取范式和主合取范式 p q r pr qr p 2.证明 p q，qr，r，sp s a b c c de f de a b fpq，p r,q s rs 3.设a 下列哪个是a的划分？若是划分，则它们诱导的等价关系是什么？1 b 2 c 3 d 是a 上的等价关系，r ia求...
2019离散试题A
河北科技大学2013 2014 学年第1学期。离散数学 考试试卷。考场号座位号学院。班级姓名学号。一 单项选择题 本题共10小题，每小题2分，共20分 1 下列偏序集中哪个是格。2 下列蕴含式错误的是。a p pqb.ppq c pp q d.pqp 3 若一条路中所有的结点v0,v1,vn均不相同...
离散复习试题
一 选择题。1 下面命题公式不是重言式。ab cd 2 命题 没有不犯错误的人 符号化为。设是人，犯错误。ab c d 3 设a 下列各式中 是错的。ab a c ad a 4 给定下列序列可以构成无向简单图的结点次数序列。a 1，1，2，2，3 b 1，1，2，2，2 c 0，1，3，3，3 d ...