离散数学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=__________。

欧拉回路是(　　　)

• A.路径
• B.迹
• C.既是初级回路也是迹
• D.既非初级回路也非迹

下列不一定是树的是(　　　)

• A.无回路的连通图
• B.有n个结点，n-1条边的连通图
• C.每对结点之间都有通路的图
• D.连通但删去一条边则不连通的图

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

• A.t(R)是包含R的二元关系
• B.t(R)是包含R的最小传递关系
• C.t(R)是包含R的一个传递关系
• D.t(R)是任何包含R的传递关系

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

• A.f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>}
• B.f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>}
• C.f={<1,6>,<2,7>,<4,9>,<3,8>}
• D.f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>}

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

• A.3条边
• B.4条边
• C.5条边
• D.6条边

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

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

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

• A.x*y=max{x，y}
• B.x*y=min{x，y}
• C.x*y=GCD{x，y}，即x，y的最大公约数
• D.x*y=LCM{x，y}，即x，y的最小公倍数

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

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

设A-B=，则有(　　　)

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

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

• A.M ∩ N
• B.M∪N
• C.M⊕N
• D.M-N

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

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

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

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

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

• A.∧
• B.→
• C.∨
• D.

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

• A.￢ P∧Q
• B.P∧￢ Q
• C.P→￢ Q
• D.P∨￢ Q

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

• A.Q→(P∨Q)
• B.(P∧Q)→P
• C.￢(P∧￢ Q)∧(￢ P∨Q)
• D.(P→Q)　　　　(￢ P∨Q)