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

在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。

构造下面推理的证明。只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。

简单图G有n个结点，m条边，设m>(n-1)(n-2)/2，证明：G是连通的。

设H是形如的2×2阶矩阵的集合，H中定义通常的矩阵乘法运算。验证H是群，。

设R为N×N上的二元关系证明R为等价关系。

设A={a，b，c}，P(A)是A的幂集，R为A上的包含关系，试给出的哈斯图，并给出子集{{a，b}，{a，c}，{c}}的极大元、极小元、最大元、最小元。

设X={1，2，3，4}，R是X上的二元关系，R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。

(1)画出R的关系图;

(2)写出R的关系矩阵;

(3)说明R是否具有自反、反自反、对称、传递性质。

求下列公式的主析取范式和主合取范式：。

构造命题公式的真值表。

若集合A={1，{2，3}}的幂集为P(A)，集合B={{，2}，{2}}的幂集为P(B)，求P(A)∩ P(B)。

如下图的有补格中，c的补元是__________，b的补元是__________。

在根树中，若每一个结点的出度__________m，则称这棵树为m叉树。如果每一个结点的出度__________m或0，则称这棵树为完全m叉树。

设A={<1,2>,<2,4>,<3,3>}，B={<1,3>,<2,4>,<4,2>}，那么dom(A∪B)=_______，ran(A ∩ B)= __________。

有理数集Q中的 * 运算定义如下：a*b=a+b-ab，则 * 运算的单位元是__________，设a有逆元，则其逆元a^-1=__________。

设f：R→R，f(x)=x²-2，g：R→R，g(x)=x-1，那么复合函数

命题公式的成真指派为__________，成假指派为__________。

公式中的自由变元为_________，约束 变元为__________。

设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R的自反闭包r(R)= _________，对称闭包S(R)=__________。

设A={1，2}，B={2，3}，则A⊕A=__________，A⊕B=__________。

欧拉回路是(　　　)

下列不一定是树的是(　　　)

下面关于关系R的传递闭包t(R)的描述最确切的是(　　　)

设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A到B的入射函数的是(　　　)

设简单图G所有结点的度数之和为12，则G一定有(　　　)

设H，K是群的子群，下面代数系统是的子群的是(　　　)

设集合A={1，2，3，…，10}，下列定义的运算关于集合A是不封闭的是(　　　)

A，B是集合，P(A)，P(B)为其幂集，且A ∩ B=，则P(A)∩ P(B)为(　)

设A-B=，则有(　　　)

设M={x|f₁(x)=0}，N={x|f₂(x)=0}，则方程f₁(x)·f₂(x)=0的解为(　　　)

下列等价式不正确的是(　　　)

设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为(　　)

下面联结词运算不可交换的是(　　　)

设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是(　　　)

下列命题公式不是重言式的是(　　　)