优质解答
三、
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）.
三、
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）.