离散数学2009年4月考试真题（02324）
-
今有n个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明：
(1)当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边(或右边)的人的朋友。
(2)当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友。
-
构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。
-
证明：边e是图G的一条割边，当且仅当图G中不存在包含边e的简单回路。
-
R是集合A上自反和传递的关系，试证明：
-
在整数集Z上定义：
是一个群。 -
设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画的哈斯图，并求A中的最大元、最小元、极大元、极小元。
-
求下列公式的主合取范式和主析取范式：
。 -
已知A={{
}，{?，1}}，B={{
，1}，{1}}，计算A∪B，A⊕B，A的幂集P(A)。 -
下图给出了一个有向图。
(1)求出它的邻接矩阵A;(2)求出A2，A3，A4及可达矩阵P。
-
构造命题公式
的真值表。 -
在下图中，结点v2的度数是________。
-
设图D=，V={v1，v2，v3，v4}，若D的邻接矩阵
，则deg-(v1)=________，从v2到v4长度为2的路有________条。 -
在
中，2的阶是________。 -
设S是非空有限集，代数系统中，其中P(S)为集合S的幂集，则P(S)对∪运算的单位元是________，零元是________。
-
设是格，其中A={1，2，3，4，6，8，12，24}，≤为整除关系，则3的补元是________。
-
设A={1，2}，B={2，3}，则A-A=________，A-B=________。
-
设复合函数
是从A到C的函数，如果
是满射，那么________必是满射，如果
是入射，那么________必是入射。 -
两个重言式的析取式是________，一个重言式与一个矛盾式的析取式是________。
-
设N是自然数集合，f和g是N到N的函数，且f(n)=2n+1，g(n)=n2，那么复合函数
-
辖域为________，
的辖域为________。 -
具有4个结点的非同构的无向树的数目是( )
- A.2
- B.3
- C.4
- D.5
-
设G为有n个结点的简单图，则有( )
- A.Δ(G)＜n
- B.Δ(G)≤n
- C.Δ(G)>n
- D.Δ(G)≥n
-
下列所示的哈斯图所对应的偏序集中能构成格的是( )
- A.
- B.
- C.
- D.
-
在代数系统中，整环和域的关系是( )
- A.整环一定是域
- B.域不一定是整环
- C.域一定是整环
- D.域一定不是整环
-
设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是( )
- A.
- B.
- C.
- D.
-
在自然数集N上，下列运算是可结合的是( )
- A.a*b=a-2b
- B.a*b=min{a，b}
- C.a*b=-a-b
- D.a*b=|a-b|
-
R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是t(R)中元素的是( )
- A.<1，1>
- B.<1，2>
- C.<1，3>
- D.<1，4>
-
集合A={1，2，…，10}上的关系R={|x+y=10，x∈A，y∈A}，则R的性质是( )
- A.自反的
- B.对称的
- C.传递的、对称的
- D.反自反的、传递的
-
若R和S是集合A上的两个关系，则下述结论正确的是( )
- A.若R和S是自反的，则R ∩ S是自反的
- B.若R和S是对称的，则
是对称的 - C.若R和S是反对称的，则
是反对称的 - D.若R和S是传递的，则R∪S是传递的
-
在公式
中变元x是( )- A.自由变元
- B.约束变元
- C.既是自由变元，又是约束变元
- D.既不是自由变元，又不是约束变元
-
命题公式
是( )- A.矛盾式
- B.蕴含式
- C.重言式
- D.等价式
-
命题公式
的成真指派是( )- A.000，001，110，
- B.001，011，101，110，111
- C.全体指派
- D.无
-
设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )
- A.￢P ∧ ￢Q
- B.￢P ∨ ￢Q
- C.￢(P ? Q)
- D.￢(￢P ∨ ￢Q)
-
下列语句中是真命题的是( )
- A.我正在说谎
- B.严禁吸烟
- C.如果1+2=3，那么雪是黑的
- D.如果1+2=5，那么雪是黑的
-
下列为两个命题变元P，Q的小项是( )
- A.P ∧ Q ∧￢P
- B.￢P ∨ Q
- C.￢P ∧ Q
- D.￢P ∨ P ∨ Q
是一个群。
。
}，{?，1}}，B={{
，1}，{1}}，计算A∪B，A⊕B，A的幂集P(A)。
的真值表。
，则deg-(v1)=________，从v2到v4长度为2的路有________条。
中，2的阶是________。
是从A到C的函数，如果
是满射，那么________必是满射，如果
是入射，那么________必是入射。
辖域为________，
的辖域为________。
是对称的
是反对称的
中变元x是( )
是( )
的成真指派是( )