离散数学试题与答案试卷一
3、设A={1，2，3}，则A上的二元关系有（ c ）个。
A． 23 ； B． 32 ； C． 23?32?2； D． 3。
5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下
R?{?s,t?|s,t?p(A)?(|s|?|t|}则P（A）/ R=（ d ）
A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D．{{?}，{2}，{2，3}，{{2，3，4}}，{A}}
试卷二试题与答案
1、 设S={a1 ，a2 ，?，a8}，Bi是S的子集，则由B31所表达的子集是 6、设 ?,? 为普通加法和乘法，则（ a ）?S,?,??是域。 A．S?{x|x?a?b3,C．S?{x|x?2n?1,a,b?Q} B．S?{x|x?2n,a,b?Z}
n?Z} D．S?{x|x?Z?x?0}= N 。
1、 设R是A上一个二元关系，
S?{?a,b?|(a,b?A)?(对于某一个c?A,有?a,c??R且?c,b??R)}试证
明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）
一、 证明 46%
1、（9分）
（1） S自反的
?a?A，由R自反，?(?a,a??R)?(?a,a??R)，??a,a??S
（2） S对称的
?a,b?A?a,b??S?(?a,c??R)?(?c,b??R)?(?a,c??R)?(?c,b??R)??b,a??S（3） S传递的
?S定义?R对称?R传递
?a,b,c?A?a,b??S??b,c??S?(?a,d??R)?(?d,b??R)?(?b,e??R)?(?e,c??R)?(?a,b??R)?(?b,c??R)??a,c??S由（1）、（2）、（3）得；S是等价关系。
?R传递?S定义
试卷三试题与答案
一、 选择 20% （每小题 2分）
1、 设
R
和
S
是
P
上的关系，P
是所有人的集合，
R?{?x,y?|x,y?P?x是y的父亲}，S?{?x,y?|x,y?P?x是y的母亲}则S?1?R表示关系 （ a ）。
}； A、{?x,y?|x,y?P?x是y的丈夫}； B、{?x,y?|x,y?P?x是y的孙子或孙女}。 C、 ?； D、{?x,y?|x,y?P?x是y的祖父或祖母试卷四试题与答案
一、 选择 25% （每小题 2.5分）
1、 公式A??x(P(x)?Q(x))的解释I为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A
的真值为（ a ）。
A、1； B、0； C、可满足式； D、无法判定。 2、 下列等价关系正确的是（ b ）。 A、?x(P(x)?Q(x))??xP(x)??xQ(x)； B、?x(P(x)?Q(x))??xP(x)??xQ(x)； C、?x(P(x)?Q)??xP(x)?Q； D、?x(P(x)?Q)??xP(x)?Q。 3、 下列推理步骤错在（ d ）。 ①?x(F(x)?G(x)) ②F(y)?G(y) ③?xF(x) ④F(y) ⑤G(y) ⑥?xG(x)
P US① P ES③ T②④I EG⑤
A、②；B、④；C、⑤；D、⑥ 1、 五、谓词逻辑推理 15%
符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证
其结论。
五、谓词逻辑推理 15%
解：M(x):x是人;F(x):x是花;G(x):x是杂草;H(x,y):x喜欢y
?x(M(x)??y(F(y)?H(x,y))) ?x(M(x)??y(G(y)??H(x,y))) ??x(F(x)??G(x))
证明：
⑴?x(M(x)??y(F(y)?H(x,y))) ⑵M(a)??y(F(y)?H(a,y)) ⑶M(a)
⑷?y(F(y)?H(a,y))
⑸?x(M(x)??y(G(y)??H(x,y))) ⑹M(a)??y(G(y)??H(a,y)) ⑺?y(G(y)??H(a,y)) ⑻?y(H(a,y)??G(y)) ⑼F(z)?H(a,z) ⑽H(a,z)??G(z) ⑾F(z)??G(z) ⑿?x(F(x)??G(x))
P ES⑴ T⑵I T⑵I P US⑸ T⑶⑹I T⑺E US⑷ US⑻ T⑼⑽I UG⑾
试卷五试题与答案 试卷六试题与答案
一、 填空 15% （每小题 3分）
1、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶
点，Nk+1个k+1度顶点，则N k = n(k+1)-2m 。
试卷七试题与答案
一、填空 15% （每小题 3分）
1. 已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,
则T中有 5 个1度顶点。 试卷八试题与答案
试卷九试题与答案
一、 选择 20% （每小题 2分）
1、 设S={N，Q，R}，下列命题正确的是（ c ）。 A、2?N,N?S 则2?S； B、N?Q,Q?S 则N?S； C、N?Q,Q?R 则N?R； D、??N,??S 则??N?S。 2、 下列语句不是命题的有（ ae ）。
A、 x=13； B、离散数学是计算机系的一门必修课； C、鸡有三只脚； D、太阳系以外的星球上有生物； E、你打算考硕士研究生吗？ 3、 下列关系中能构成函数的是（ b ）。
2{?x,y?|(x,y?N)?(x?y?10)}{?x,y?|(x,y?R)?(y?x)}； A、；B、
{?x,y?|(x,y?I)?(x?ymod3)}。{?x,y?|(x,y?R)?(y?x)}；C、 D、
10、N是自然数集，定义f:N?N, f(x)?(x) mod3（即x除以3的余数），
则f是（ d ）。
A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。 试卷十试题与答案
2一、 填空 10% （每小题 2分）
P?Q真值为1，1、 若P，Q为二命题，当且仅当 。
2、 对公式(?yP(x,y)??zQ(x,z))??xR(x,y)中自由变元进行代入的 公
为 。 3、 ?xF(x)??(?xG(x))的
前
束
范
式式
为 。
4、 设x是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y的自由的，
则
被称为全称量词消去规则，记为US。
5、 与非门的逻辑网络为
。
二、 选择 30% （每小题 3分）
1、 下列各符号串，不是合式公式的有（ ）。 A、(P?Q)??R； B、((P?Q)?(R?S)； C、P?Q??R； D、(?(P?Q)?R)?S。 2、 下列语句是命题的有（ ）。
A、2是素数；B、x+5 > 6；C、地球外的星球上也有人；D、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。
A、?(P?Q)；B、(P?Q)?Q；C、?(Q?P)?P；D、(P?Q)?P 4、 下列问题成立的有（ ）。
A、 若A?C?B?C，则A?B； B、若A?C?B?C，则A?B； C、若?A??B，则A?B； D、若A?B，则?A??B。 5、 命题逻辑演绎的CP规则为（ ）。 A、 在推演过程中可随便使用前提；
B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；
C、如果要演绎出的公式为B?C形式，那么将B作为前提，设法演绎出C； D、设?(A)是含公式A的命题公式，B?A，则可用B替换?(A)中的A。 6、 命题“有的人喜欢所有的花”的逻辑符号化为（ ）。 设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y
A、?x(M(x)??y(F(y)?H(x,y)))；B、?x(M(x)??y(F(y)?H(x,y)))； C、?x(M(x)??y(F(y)?H(x,y)))；D、?x(M(x)??y(F(y)?H(x,y)))。 7、 公式?x?y(P(x,y)?Q(y,z))??xP(x,y)换名（ ）。
A、?x?u(P(x,u)?Q(u,z))??xP(x,y)；B、?x?y(P(x,u)?Q(u,z))??xP(x,u)；
?x?y(P(x,y)?Q(y,z))??xP(x,u)；?u?y(P(u,y)?Q(y,z))??uP(u,y)。C、D、
8、 给定公式?xP(x)??xP(x)，当D={a,b}时，解释（ ）使该公式真值
为0。
A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=1 9、 下面蕴涵关系成立的是（ ）。 A、?xP(x)??xQ(x)??x(P(x)?Q(x))； B、?xP(x)??xQ(x)??x(P(x)?Q(x))； C、?xP(x)??xQ(x)??x(P(x)?Q(x))；