2、>也是半群，反之不真。5.×有割点的连通图肯定不是汉密尔顿图。四、简答题（共40分）1.答案要点（8分）a)P：天下雨：他在室内运动﹁PÆ﹁Qb)P:你走Q:我留下﹁PÆ﹁Q或QÆPc)M(x)：x是人C(x)：x是聪明的(∃x)(M(x)∧C(x))∧¬(∀x)(M(x)→C(x))d)M(x)：x是人F(x)：x是聪明的(∀x)(M(x)→F(x))2.答案要点（8分）(P∨Q)Æ(┐Q∧R)⇔┐(P∨Q)∨(┐Q∧R)⇔(┐P∧┐Q)∨(┐Q∧R)⇔(┐P∧┐Q∧(R∨┐R))∨((P∨┐P)∧┐Q∧R)⇔(┐P∧┐Q∧R)∨(┐P
3、∧┐Q∧┐R)∨(P∧┐Q∧R)∨(┐P∧┐Q∧R)⇔m001∨m000∨m101⇔M010∧M011∧M100∧M110∧M111⇔(P∨┐Q∨R)∧(P∨┐Q∨┐R)∧(┐P∨Q∨R)∧(┐P∨┐Q∨R)∧(┐P∨┐Q∨┐R)3.答案要点（5分）f1={<1,x>,<2,x>,<3,x>}f2={<1,x>,<2,x>,<3,y>}f3={<1,x>,<2,y>,<3,x>}f4={<1,x>,<2,y>,<3,y>}f5={<1,y>,<2,x>,<3,x>}f6={<1,y>,<2,x>,<3,y>}f7={<1,y>,<2,y>
4、,<3,x>}f8={<1,y>,<2,y>,<3,y>}这8个函数中没有双射，f2~f7是满射4.答案要点（6分）1⎡11100⎤⎢⎥2511111⎢⎥M=⎢11110⎥⎢⎥⎢01110⎥34⎢⎣01001⎥⎦R的极大相容类为{1,2,3},{2,3,4},{2,5}5.答案要点（8分）⊕Φ{a}{b}{c}{a,b}{a,c}{b,c}{a,b,c}ΦΦ{a}{b}{c}{a,b}{a,c}{b,c}{a,b,c}{a}{a}Φ{a,b}{a,c}{b}{c}{a,b,c}{b,c}{b}{b}{a,b}Φ{b,c}{a}{a,b,c
5、}{c}{a,c}{c}{c}{a,c}{b,c}Φ{a,b,c}{a}{b}{a,b}{a,b}{a,b}{b}{a}{a,b,c}Φ{b,c}{a,c}{c}{a,c}{a,c}{c}{a,b,c}{a}{b,c}Φ{a,b}{b}{b,c}{b,c}{a,b,c}{c}{b}{a,c}{a,b}Φ{a}{a,b,c}{a,b,c}{b,c}{a,c}{a,b}{c}{b}{a}Φ幺元为Φ，每个元素的逆元都是其自身求式{a}⊕x={b}中的x，查运算表可知，x={a,b}6.答案要点（5分）⎡1100⎤⎡2110⎤⎢⎥⎢⎥101021
6、11M=⎢⎥M2=⎢⎥⎢1011⎥⎢2121⎥⎢⎥⎢⎥⎣0010⎦⎣1011⎦长度为2的路的总数为18条长度为2的回路总数为6条五、证明题（共25分）1.答案要点（8分）(∀x)(P(x)→Q(x))⇒(∀x)P(x)→(∀x)Q(x)①(∀x)P(x)P(附加前提)②P(a)US①③(∀x)(P(x)→Q(x))P④P(a)→Q(a)US③⑤Q(a)T②④I⑥(∀x)Q(x)UG⑤⑦(∀x)P(x)→(∀x)Q(x)CP2.答案要点（10分）⊆①关系满足自反性⊆②关系满足反对称性⊆③关系满足传递性⊆⊆④说明：任取X，Y∈P，都有XY或Y
7、X也可以画出哈斯图说明3.答案要点（7分）r∵∑deg(ri)=2e而deg(ri)≥k(1≤i≤r)i=1∴2e≥kr,即r≤2e/k又∵v-e+r=2k(v−2)e≤∴v-e+2e/k≥2,即k−2
