离散数学2016年10月考试真题(02324)

符号化下列命题，并构造推理证明。任何人如果他是素食者，他就不喜欢吃肉;每一个人或者喜欢吃肉或者喜欢吃蔬菜;有的人不爱吃蔬菜。因而不是所有的人都是素食者。

今有a、b、c、d、e、f、g共7个球类运动爱好者，已知下列事实：a喜欢篮球运动;b喜欢篮球运动和足球运动;c喜欢篮球、排球和乒乓球运动;d喜欢网球和足球运动;e喜欢羽毛球和排球运动;f喜欢棒球、网球和乒乓球运动;g喜欢棒球和羽毛球运动。试问：这7个人应如何围圆桌排座位，才能使每个人和他身边的人有共同球类爱好话题。须写出所有可能方案。

设解释I如下：D={2，3}，已知f(2)=3，f(3)=2，F(2)=0，F(3)=1，G(2，2)=G(3，3)=0，G(2，3)=G(3，2)=1。

设图G如题29图所示。

(1)写出图G的邻接矩阵;

(2)G中长度为4的通路有几条?

(3)上问中有几条回路?

设无向图G有7个顶点，每个顶点的度数不是4就是5。证明：G中至少有5个度数为4的顶点或至少有4个度数为5的顶点。

含有n个命题变元的命题公式，共有_________组指派。

设论域是全体人类，F(x)：x能呼吸，要求只能使用存在量词，命题“所有人都能呼吸”可符号化为_________。

设A={2，4，8，16}，a*b=lcm(a，b)，即a、b的最小公倍数。代数系统的幺元是_________，零元是_________。

若A={1，4，3}，B={a，3，c}，则A-B=_________，A⊕B=_________。

若连通平面图G有8条边，3个面，则G有_________个结点。

设集合A={a，b，c，d}以及A上的一个二元关系R={，}，则对称闭包s（R）= _________，传递闭包t（R）= _________。

设G是一个有11个顶点的简单无向图。如果G恰有一个回路，则G的边数最大是_______。

设A={1，2，3，4}，B={1，3，4，5}，A到B的关系R={<3，1>，<1，1>，<4，3>}，B到A的关系S={<4，1 >， <3，2>， <2，3>}，则R。S=_________。

设R={<3，c>，<1，a>，<4，c>，<4，d>}是集合A={1，2，3，4}到集合B={a，b，c，d}的关系，则dom R=_________，ran R=_________。

• A.每列火车都比所有汽车快
• B.每列火车都比某些汽车快
• C.某些火车比某些汽车快
• D.某些火车比所有汽车快

设G为连通的无向简单图。若G恰有2个奇度结点，则G一定具有()

• A.欧拉回路
• B.欧拉通路
• C.哈密尔顿回路
• D.哈密尔顿通路

在整数集Z上，下列运算满足结合律的是()

• A.a*b=ab一1
• B.a*b=|a-b|
• C.a*b=2a+b
• D.a*b=a+b-1

设p：他怕困难;q：他获得成功。命题“除非他不怕困难，否则他不会获得成功”可符号化为()

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

下列图对应的格是有补格的为()

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

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

设Z为整数集合，则下列集合关于数的加法运算不能构成独异点的是()

• A.{3m+5n|m，n∈Z}
• B.{2k|k∈Z}
• C.{2k+1|k∈Z}
• D.Z

下列语句是原子命题的为()

• A.x+y>xy
• B.请给我来点掌声吧
• C.小明既爱唱歌又爱跳舞
• D.火星上有生物

下列命题公式是永真式的为()

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

4个结点的非同构的无向树的数目是()

• A.5
• B.4
• C.3
• D.2

设论域为整数集，下列命题中真值为假的是()

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

下列关系不可能是相容关系的是()

• A.恒等关系
• B.全域关系
• C.等价关系
• D.拟序关系

设集合A有3个元素，则A中的划分有()

• A.3个
• B.5个
• C.6个
• D.9个

设无向树T有3个度数为4的结点，其余结点都为树叶，则T的结点数为()

• A.10
• B.11
• C.12
• D.13

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