【离散数学作业求大家帮忙三、构造下面推理的证明：如果小张和小王去看电影,则小李也去看电影.小赵不去看电影或小张去看电影.小王去看电影.所以,当小赵去看电影时,小李也去.四、设】-025773查询网问答

【离散数学作业求大家帮忙三、构造下面推理的证明：如果小张和小王去看电影,则小李也去看电影.小赵不去看电影或小张去看电影.小王去看电影.所以,当小赵去看电影时,小李也去.四、设】

更新时间：2024-04-26 21:57:51

1人问答

问题描述：

离散数学作业求大家帮忙

三、构造下面推理的证明：如果小张和小王去看电影,则小李也去看电影.小赵不去看电影或小张去看电影.小王去看电影.所以,当小赵去看电影时,小李也去.

四、设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个人能排成一圆圈，使得每个人是其两旁的人的朋友.

刘治军回答：

网友采纳

　　三、　　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 　　∀,∈R，由复合关系的定义，显然∈RR 　　而根据R的传递性，显然∈R 　　由x,z的任意性，得知RR⊆R 　　∀∈R，由R的自反性，得知∈R 　　从而根据R的传递性，得到∈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）.