2014-2015学年第一学期期末《离散数学》大作业
一、简要回答下列问题：（每小题3分，共30分）
1．请给出集合的结合率。

2．请给出一个集合A，并给出A上既不具有自反性，又不具有反自反性的关系。

3．设A={1，2}，问A上共有多少个不同的对称关系？
4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={2,3}，求M的上界，下界。

5．关于P，Q，R请给出使极小项m0，m4为真的解释。

6．什么是图中的简单路？请举一例。

7．什么是交换群，请举一例。

8．什么是群中右模H合同关系？
9．什么是有壹环？请举一例。

10．什么是极大理想？请举一例。

二、（12分）R，S是集合A上的两个关系。

试证明下列等式：
（1）(R•S)-1= S-1•R-1
（2）(R-1)-1= R
三、（20分）指出下列公式哪些是恒真的哪些是恒假的：
(1)P∧（P→ Q）→Q
(2)（P→ Q）→（⌝P∨Q）
(3)（P→ Q）∧（Q→R）→（P→ R ）
(4)（P↔ Q）↔（P∧ Q∨⌝P∧⌝ Q）
四、（18分）指出下列表达式中的自由变量和约束变量，并指明量词的作用域：
（1）(∀xP(x)∧∃xQ(x))∨(∀xP(x)→Q(y))
（2）∃x∀y((P(x)∧Q(y))→∀zR(z))
（3）A(z)→(⌝∀x∀yB(x，y，a))
（4）∀x A(x)→∀yB(x，y)
（5）(∃xF(x)∧∀yG(x，y，z))→∃zH(x，y，z)
五、（20分）一公司在六个城市c1，c2，…，c6中的每一个都有分公司。

从c i到c j的班机旅费由下列矩阵中的第i行第j列元素给出(∞表示没有直接班机)：
0 50 ∞40 25 10
50 0 15 20 ∞25
∞15 0 10 20 ∞
40 20 10 0 10 25
25 ∞20 10 0 55
10 25 ∞25 55 0
公司所关心的是计算两城市间的最便宜路线的表格。

请准备一张这样的表格。