离散数学2009年7月考试真题（02324）

设H是G的有限子集，则是群的子群当且仅当是 群的子代数。

符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。

证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点一次。

，，证明R是等价关系。

用矩阵的方法求右图中结点u₂，u₅之间长为2的路径的数目。

用推理方法证明：

求右图所示格的所有5元子格。

设A={a，b，c，d}，求R的传递闭包。

设A={2，3，6，12，24，36}，请画出A上整除关系的哈斯图，并给出子集{6，12， 24，36}的下界、下确界、极大元、最大元。

用等值演算求的主合取范式。

列出的真值表。

若图中存在________，它经过图中所有的边恰好________次，则称该图为欧拉图。

偶图记为K_n,m那么当________时，K_n,m是平面图，当________时，K_n,m是非平面图。

若回路中，除________外________各不相同，则此回路称为圈(或初级回路)。

代数系统是整环，则是________，是________，且无零因子。

在实数集R上定义运算=a+b+ab，则幺元为________，元素2的逆元为________。

请用联结词﹁，∧表示联结词∨和联结词：________，________。

一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。

设A={1，2，3，4}，A上的二元关系R={<1，2>，<3，4>，<4，3>}，S={<1， 3="">，<3，4>，<4，1>}，则R ∩ ~S=________，=________。

设命题变元为P，Q，R，则小项m₁₀₀=________，大项M₀₁₀=________。

置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以________，记为________规则。

右图的最小入度是( )

• A.0
• B.1
• C.2
• D.3

下面既是汉密尔顿图又是欧拉图的图形是( )

• A.
• B.
• C.
• D.

一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是( )

• A.17
• B.18
• C.19
• D.20

下面不满足结合律的运算是( )

• A.a*b=min(a，b)
• B.a*b=max(a，b)
• C.a*b=2(a+b)
• D.a*b=2ab

设A是奇数集合，×为乘法运算，则是( )

• A.半群
• B.群
• C.循环群
• D.交换群

设R₁和R₂是集合A上的相容关系，下列关系哪个可能不是相容关系( )

• A.
• B.
• C.
• D.

在整数集上，下面哪个运算不是二元运算( )

• A.加法
• B.减法
• C.乘法
• D.除法

下列哪个关系矩阵所对应的关系具有自反性( )

• A.
• B.
• C.
• D.

设论域为{1，2}，与公式等价的是( )

• A.
• B.
• C.
• D.

设是正整数集

• A.仅是入射
• B.仅是满射
• C.是双射
• D.不是函数

设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为x＜y下列公式真值为真的是( )

• A.
• B.
• C.
• D.

对于公式，下列说法正确的是( )

• A.
• B.
• C.
• D.

下列句子为命题的是( )

• A.走，看电影去
• B.x+y>0
• C.空集是任意集合的真子集
• D.你明天能来吗?

下列式子为重言式的是( )

• A.
• B.
• C.
• D.

下列式子不是谓词合式公式的是( )

• A.
• B.
• C.
• D.