Question

离散数学作业求大家帮忙

三、构造下面推理的证明：如果小张和小王去看电影, 则小李也去看电影. 小赵不去看电影或小张去看电影. 小王去看电影. 所以, 当小赵去看电影时, 小李也去.
四、设R是集合A上自反和传递的关系，试证明：RR=R.
五、已知A ={{Æ}, {Æ, 1}}, B = {{Æ, 1}, {1}}, 计算A∪B, A+B，A的幂集P(A).
六、今有n个人, 已知他们中任何2人的朋友合起来一定包含其余n -2人. 试证明：
(1) 当n≥3时，这n个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边(或右边)的人的朋友.
(2) 当n≥4时，这n个人能排成一圆圈，使得每个人是其两旁的人的朋友.

Answer 1

三、

A：小张看电影
B：小王看电影
C：小李看电影
D：小赵看电影
前提条件：
A∧B→C
¬D∨(A∧B)

下面来证明：D→C
¬D∨(A∧B)
⇔D→A∧B 蕴含等价
A∧B→C 前提
D→C 蕴含传递性

四、
只需证明RR⊆R ∧ R⊆RR
∀<x,y>,<y,z>∈R，由复合关系的定义，显然<x,z>∈RR
而根据R的传递性，显然<x,z>∈R
由x,z的任意性，得知RR⊆R

∀<x,y>∈R，由R的自反性，得知<x,x>∈R
从而根据R的传递性，得到<x,y>∈RR
由x,y的任意性，得知R⊆RR

综合得知，RR=R

五、

A ={{Æ}, {Æ, 1}}
B = {{Æ, 1}, {1}}
A∪B={{Æ}, {1},{Æ, 1}}
A∩B={{Æ, 1}}
A-B={{Æ}}
A的幂集P(A)={∅,{{Æ}},{{Æ, 1}},{{Æ}, {Æ, 1}}}

六、

用图论方法证明。
证明：
将这n个人作为n个结点,如果某两个人认识,则这两个人对应的结点之间存在一条边,这样就得到一个具有n个结点的无向图,此时需证明的是,当n>=3时该图存在一个哈密顿路,n>=4时,该图存在一个哈密顿回路,即该图是哈密顿图,下面给出证明.

首先证明当n>=3时该图存在一个哈密顿路.
设u,v是任意两个结点,由本题题意(任何2个人合起来认识其余的n-2个人)可知,deg(u)+deg(v)>=n-2,下面需证明deg(u)+deg(v)>=n-1,否则如果deg(u)+deg(v)=n-2,分下面两种情况讨论：
1）如果u,v邻接,此时deg(u)+deg(v)>=(n-2)+2=n> n-1;
2) 如果u,v不邻接,则其余的n-2个结点仅能与u,v中的一个结点相邻接,设w是这其余的任一结点（由n>=3可知结点w存在的）,由于结点w仅能u,v其中之一邻接,不妨设w与u邻接,与v不邻接,此时结点u和w均不与v邻接,这与题意矛盾；
故deg(u)+deg(v)>=n-1,则该图存在一个哈密顿路（参看任意一本离散数学书,如西北工业大学出版社出版刘长安编著《离散数学教程》P267）.

再证明当n>=4时,该图存在一个哈密顿回路.
下面需证明对任意两个结点u,v有deg(u)+deg(v)>=n,仍分下面两种情况讨论：
1）如果u,v邻接,此时deg(u)+deg(v)>=(n-2)+2=n;
2) 如果u,v不邻接,如果deg(u)+deg(v)=n-1,此时除u,v外其余的结点中存在一个结点s与u,v均邻接,另一个结点w仅与u,v其中之一邻接,（由n>=4可知结点s与w是存在的）,不妨设w与u邻接,与v不邻接,此时结点u和w均不与v邻接,这又与题意矛盾；
故deg(u)+deg(v)>=n,则该图存在一个哈密顿路（参看任意一本离散数学书,同上书P268）.