一、单项选择题（每小题3分，本题共15分）Page2~4→若集合A＝{{a}}，则下列表述正确的是(B)．A．{a}⊆A B．{a}∈A C．a∈A D．∅∈A→若集合A＝{a, b}，则下列表述正确的是(D)．A．∅∈A B．{a}∈A C. {a,b}∈A D. {a}⊆A→若集合A＝{a, {1}}，则下列表述正确的是(A)．A．{1}∈A B．{1}⊆A C．{a}∈A D．∅∈A→若集合A={1, {1}, {2}, {1, 2}}，则下列表述正确的是(A)．A．{2}∈A B．{1，2}⊂A C．1∉A D．2 ⊂ A→若集合A＝{a, {a}, {1, 2}}，则下列表述正确的是(C)．A．{a，{a}}∈A B．{2}⊆A C．{a}⊆A D．∅∈A→若集合A＝{a, {a}}，则下列表述正确的是(A)．//注意是第几个a A．{a}⊆A B．{{{a}}}⊆A C．{a，{a}}∈A D．∅∈A→若集合A＝{2, a, {a}, 4}，则下列表述正确的是(D)A．{a，{a }}∈A B．Ø∈A C．{2}∈A D．{a }⊆A →若集合A={1, {2}, {1, 2}}，则下列表述正确的是(B)．A．2⊂A B．{1}⊂A C．1∉A D．2∈A→设A、B是两个任意集合，侧A-B = Ø ⇔(B)A．A=B B．A⊆B C．A⊇B D．B=Ø→若集合A={a, b}，B={a, {a, b}}，则(D)．A．A∉B B．A⊆B C．A⊂B D．A∈B→若集合A={a, b}，B={a, b, { a, b}}，则(A)．A．A⊂B，且A∈B B．A∈B，但A⊄BC．A⊂B，但A∉B D．A⊄B，且A∉B→若集合A={1, 2}，B={1, 2, {1, 2}}，则下列表述正确的是(A)．A. A⊂B，且A∈B B. B⊂A，且A∈BC. A⊂B，且A∉BD. A⊄B，且A∈BPage30→设集合A={1,2,3,4},R是A上的二元关系，其关系矩阵为则R的关系表达式是( A )．A. {<1, 1>, <1, 4>, <2, 1>, <3, 4>, <4,1>}B. {<1, 1>, <1, 2>, <1, 4>, <4, 1>, <4, 3>}C. {<1, 1>, <2, 1>, <4, 1>, <4, 3>, <1, 4>}D. {<1, 1>, <1, 2>, <2, 4>, <4, 1>, <4, 3>}Page 38~41→集合A={x|x为小于10的自然数}/ A={1, 2, 3, 4, 5, 6, 7, 8}，集合A上的关系R={<x，y>|x+y=10且x, y∈A},则R的性质为(B) A自反的B对称的C传递且对称的D反自反且传递的→集合A={1, 2, 3, 4}上的关系R={<x, y>|x=y且x, y∈A}，则R的性质为(C)．A.不是自反的B不是对称的C传递的D反自反→设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>,<2, 2>,<2, 3>，<4, 4>}，S={<1, 1>,<2, 2>,<2, 3>,<3, 2>,<4, 4>}，则S是R的(C)闭包．Page42A. 自反B. 传递C. 对称D. 自反和传递Page54→设集合A={1, 2, 3, 4, 5}，偏序关系≤是A上的整除关系，则偏序集<A，≤>上的元素5是集合A的(B)．A．最大元B．极大元C．最小元D．极小元→设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为(D)．A. 8、2、8、2B. 8、1、6、1C. 6、2、6、2D. 无、2、无、2→设集合A= {1, 2, 3, 4, 5}上的偏序关系的哈斯图如右图所示，若A 的子集B= {3, 4, 5}，则元素3为B的(B)．A. 下界B. 最小上界C. 最大下界D. 最小元Page 58→设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={<a，2>, <b，2>}，R2={<a，1>, <a，2>, <b，1>}，R3={<a，1>, <b，2>}，则（C ）是从A到B的函数．A. R1B. R2C. R3D. R1和R3→设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={<a，2>, <b，2>}，R2={<a，1>, <a，2>, <b，1>}，R3={<a，1>, <b，2>}，则（B ）不是从A到B的函数．A. R1B. R2C. R3D. R1和R3→设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>, <2, 1>, <3, 3>}，g= {<1, 3>, <2, 2>, <3, 2>}，h= {<1, 3>, <2, 1>, <3, 1>}，则h =(A)．A. f◦gB. g◦fC. f◦fD. g◦g→设函数f：N→N，f(n)=n+1，下列表述正确的是(D)．Page57 A. f存在反函数 B. f是双射的 C. f是满射的 D. f是单射函数→已知图G的邻接矩阵为: 则G有(D)．A．6点，8边B．6点，6边C．5点，8边D．5点，6边→已知图G的邻接矩阵为: 则G有(D)．A．5点，8边B．6点，7边C．6点，8边D．5点，7边→设图G的邻接矩阵为: 则G的边数为( A)．A．5B．6C．7D．8→设无向图G的邻接矩阵为: 则G的边数为( B )．A．1B．7C．6D．14⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1111111111⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡11111111111111→若G是一个汉密尔顿图/ 欧拉图，则G一定是(D)．A．平面图B．对偶图C．欧拉图D．连通图→无向完全图K4是(B)．A．欧拉图B．汉密尔顿图C．非平面图D．树→设G为无向图，则下列结论成立的是(C) ．A．无向图G的结点的度数等于边数的两倍．B．无向图G的结点的度数等于边数．C．无向图G的结点的度数之和等于边数的两倍.D．无向图G的结点的度数之和等于边数．→若完全图G / K n中有n个结点(n≥2)，m条边，则当(A)时，图G / Kn中存在欧拉回路．A．n为奇数B．n为偶数C．m为奇数D．m为偶数→设G是连通平面图，有v个结点，e条边，r个面，则r= (A)．A. e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 →设G是有n个结点，m条边的连通图，必须删去G的(A)条边，才能确定G的一棵生成树．A. m-n+1B. m-nC. m+n+1D. n-m+1→n阶无向完全图K n的边数及每个结点的度数分别是(A)A. n(n-1)/2,n-1B. n-1,nC. n(n-1),n-1D. n(n-1),n→无向简单图G是棵树，当且仅当(A)．A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路．→已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为(D)．A．6 B．4 C．3 D．5→无向树T有8个结点，则T的边数为(B)．A．6 B．7 C．8 D．9→无向树T有5条边，则T的结点为(C)．A．4 B．5 C．6 D．7→设图G＝<V, E>，v∈V，则下列结论成立的是(D)．A．deg(v)=2∣E∣B．deg(v)=∣E∣C．EvVv=∑∈)deg(D．EvVv2)deg(=∑∈→若A是G图的割点，则以下说法正确的是(D).A. {a}不是割点集B. 删除a点，G仍连通C. {a,b} 可以是割点集D. 删除a点，G仍连不通→设个体域D={a, b, c}，那么谓词公式∃xA(x)∨∀yB(y)消去量词后的等值式为(A)．A. (A(a)∨A(b)∨A(c))∨(B(a)∧B(b)∧B(b))B. (A(a)∧A(b)∧A(c))∨(B(a)∨B(b)∨B(b))C. (A(a)∨A(b)∨A(c))∨(B(a)∨B(b)∨B(b))D. (A(a)∧A(b)∧A(c))∨(B(a)∧B(b)∧B(b))→设个体域为整数集，则公式∀x∃y(x+y=0)的解释可为（B）A．存在一整数x有整数y满足x+y=0B．对任一整数x存在整数y满足x+y=0C．存在一整数x有任意整数y满足x+y=0D．任一整数x对存在整数y满足x+y=0→设命题公式G：，则使公式⌝P→(Q∧R)G取真值为1的P，Q，R赋值分别是(D)．A. 0, 0, 0B. 0, 0, 1C. 0, 1, 0D. 1, 0, 0→命题公式(P∨Q)→Q为(B)A. 矛盾式B. 可满足式C. 重言式D. 合取范式→命题公式⌝(P→Q)的析取范式是(A )．A. P∧⌝QB. ⌝P∧QC. ⌝P∨QD. P∨⌝Q→命题公式(P∨Q)→R的析取范式是(D)A．⌝(P∨Q)∨R B．(P∧Q)∨R C．(P∨Q)∨R D．(⌝P∧⌝Q)∨R →命题公式P的合取范式是(A) ．A．P B．(P∧Q)∨(P∨Q) C．P∧P D．⌝ (⌝P∨Q) →命题公式(P∨Q)的合取范式是(D) ．A．(P∧Q) B．(P∧Q)∨(P∨Q) C．(P∨P) D．(P∨Q) →前提条件P→Q,P的有效结论是(D)．A. PB. ⌝PC. QD. ⌝Q→下列公式(B)为永真式．A．⌝P∧⌝Q↔P∨Q B．(P→(⌝Q→P))↔(⌝P→(P→Q)) C．(Q→(P∨Q)) ↔(⌝Q∧(P∨Q)) D．(⌝P∨(P∧Q)) ↔Q→下列公式中(B)为永真式．A．⌝A∧⌝B ↔⌝A∨⌝B B．⌝A∧⌝B ↔⌝(A∨B)C．⌝A∧⌝B ↔ A∨B D．⌝A∧⌝B ↔⌝(A∧B)→下列公式成立的为(D)．A．⌝P∧⌝Q ⇔ P∨Q B．P→⌝Q ⇔⌝P→QC．Q→P ⇒ P D．⌝P∧ (P∨Q)⇒Q→下列公式成立的为(C)．A．⌝P∧⌝Q ⇔⌝ P∨⌝Q B．P→⌝Q ⇔⌝P→QC．P ⇒ P D．⌝P∧ (P∨Q)⇒⌝Q→下列等价公式成立的为(C)．A．P∧Q⇔P∨Q B．⌝Q→P⇔P→QC．⌝P∧P ⇔⌝Q∧Q D．⌝P∨P ⇔Q→下列等价公式成立的为( B)．A．⌝P∧⌝Q⇔P∨Q B．P→(⌝Q→P) ⇔⌝P→(P→Q) C．Q→(P∨Q) ⇔⌝Q∧(P∨Q) D．⌝P∨(P∧Q) ⇔Q→下列公式(C)为重言式．A．⌝P∧⌝Q↔P∨Q B．(Q→(P∨Q)) ↔(⌝Q∧(P∨Q)) C．(P→(⌝Q→P))↔(⌝P→(P→Q)) D．(⌝P∨(P∧Q)) ↔Q→在谓词公式(∀x)(A(x)→B(x)∨C(x，y))中（C）．A. x，y都是约束变元B. x，y都是自由变元C. x是约束变元，y都是自由变元D. x是自由变元，y都是约束变元→表达式∀x(P(x,y)∨Q(z))∧∃ y(R(x,y)→∀zQ(z))中∀x的辖域是(B) A. P(x, y) B. P(x, y)∨Q(z) C. R(x, y) D. P(x, y)∧R(x, y)→命题公式(P∨Q)→Q为(B)A.矛盾式B.可满足式C.重言式D.合取范式→谓词公式xA(x) ∧⌝∃xA(x)是(A)．A.不可满足式B.可满足式C.有效的D.蕴含式→设有向图（a ）、（b ）、（c ）与（d ）如图一所示，则下列结论成立的是(C), (H)A ．（a ）仅为弱连通的B ．（b ）仅为弱连通的C ．（c ）仅为弱连通的D ．（d ）仅为弱连通的E ．（a ）是强连通的F ．（b ）是强连通的G ．（c ）是强连通的H ．（d ）是强连通的→ 图G 如图一所示，以下说法正确的是( C ) ．A ．{(a, b)}是边割集B ．{a, c}是点割集C ．{d}是点割集D ．{(c ，d)}是边割集→ 图G 如图一所示，以下说法正确的是 (B)．A ．a 是割点B ．{b, c}是点割集C ．{b, d}是点割集D ．{c}是点割集→ 图G 如图一所示，以下说法正确的是 ( C) ． A ．{(a, d)}是割边 B ．{(a, d)}是边割集 C ．{(a, d), (b, d)}是边割集 D ．{(b, d)}是边割集→ 如图一所示，以下说法正确的是 ( D) ． A ．{(a, e)}是割边 B ．{(a, e)}是边割集C ．{(a, e) ,(b, c)}是边割集D ．{(d, e)}是边割集→ 如图一所示，以下说法正确的是 ( A)． A ．e 是割点 B ．{a, e}是点割集C ．{b, e}是点割集D ．{d}是点割集→ 如图一所示，以下说法正确的是 ( D)． A ．e 是割点 B ．{a, e}是点割集 C ．{b, e}是点割集 D ．{f}是点割集二、填空题（每小题3分，本题共15分） Page6→设集合A ＝{1,2,3}，那么集合A 的幂集是 Page5~7 Page25→若集合A={1，3，5，7}，B={2，4，6，8}，则A ∩B= 空集or ∅． →设集合A={1,2,3,4},B={3,4,5,6},C={5,6,7,8},→设集合A ＝{1, 2, 3} B={1,2}，Page28~29→设集合A={2, 3, 4}，B={1, 2, 3, 4}，R 是A 到B 的二元关系，R={<x,y>|x ∈A 且y ∈B 且x ≤y} 则R 的有序对集合为{<2, 2>，<2, 3>，<2, 4>，<3, 3>，<3, 4>，<4, 4>}． →设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R 是A 到B 的二元关系，R={<x,y>|x ∈A 且y ∈B 且x,y ∈A ∩B}则R 的有序对集合为 {<2, 2>，<2, 3>，<3, 2>}，<3, 3> ．→设集合A={0, 1, 2}，B={1,2, 3, 4,}，R 是A 到B 的二元关系， R={<x,y>|x ∈A 且y ∈B 且x,y ∈A ∩B 则R 的有序对集合为 {<1, 1>，<1, 2>，<2, 1>，<2, 2>}．→设集合A={1, 2, 3}，B={2, 3, 4, 5, 6}，R 是A 到B 的二元关系， R={<x,y>|x ∈A 且y ∈B 且x=y}则R 的有序对集合为 {<2, 2>，<3, 3>}→设集合A={1, 2, 3, 4,5,6}, B={1, 2, 3}, R 是A 到B 的二元关系， R ＝{<x,y>|x ∈A,y ∈B, x=y 2}则R= {<1,1>, <4,2>} →设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A 到B 的二元关系Page38~41→设集合A={1，2}上的关系R ＝{<2,2>,<1,2>}，则在R 中仅需加入一个元素 <1, 1> ，就可使新得到的关系为自反的．→设集合A={1，2}上的关系R ＝{<1, 1>,<1, 2>}，则在R 中仅需 一个元素 <2, 1> ，就可使新得到的关系为对称的．→设集合A=｛a, b, c, d ｝A 上的二元关系,R={<a, a >, <b, b>, <b, c>, <c, d>}，若在R 中再增加两个元素{<c,b>,<d,c>}，则新得到的关系就具有对称性．→若R 1和R 2是A 上的对称关系，则R 1∪R 2，R 1∩R 2，R 1-R 2，R 2-R 1 中对称关系有 4 个．→如果R 1和R 2是A 上的自反关系，则R 1∪R 2，R 1∩R 2，R 1-R 2 中自反关系有 2个．→设集合A=｛a, b, c, d ｝，A 上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R 具有的性质是 没有任何性质 ．οο ο ο οο a b cdePage42→若A={1,2}，R={<x, y>|x∈A, y∈A, x+y=10}，则R的自反闭包为→若A={1,2}，R={<x, y>|x∈A, y∈A, x+y<4}，则R的自反闭包为Page45→如果R是非空集合A上的等价关系，a ∈A，b∈A，则可推知R中→设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中→如果R是非空集合A上的等价关系，a ∈A，b∈A，<a,b>∈R，等元素．Page 58→设集合A={1，2，3}上的函数分别为：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，则复合函数:g︒f = {<1, 2>, <2, 3>, <3, 2>,}．→设集合A={a,b},B={1,2},C={4,5},从A到B的函数f={<a,1>,<b,2>},从B到C的函数g={<1,5>,<2,4>} 则g︒f = {<a, 5>, <b, 4>}．→设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为8 →设A={a，b}，B={1，2}，作f：A→B，则不同的函数个数为4 ．→设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是{<1, a >, <2, b >}或{<1, b >, <2, a >} ．Page 59→给定一个序列集合{000，001，01，10，0}，若去掉其中的元素0 ，则该序列集合构成前缀码．?→设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”）．→无向图G存在欧拉回路，充分必要条件是/ 当且仅当G所有结点的度数全为偶数且连通．→已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15 ．→若无向树T有5个结点，则T的边数为4 ．→设正则5叉树的树叶数为17，则分支数为i = 5 ．→设连通平面图G的结点数为5，边数为6，则面数为3 ．→设正则m叉树的树叶数为t，分支数为i，则(m-1)i=t-1 ．→结点数v与边数e满足e=v-1 关系的无向连通图就是树．→无向连通图在结点数v与边数e满足e=v-1 关系时是树．→无向连通图G的结点数为v，边数为e，则G当v与e满足e=v-1关系时是树．→若无向图T是连通的，则T的结点数v与边数e满足关系v= e+1 时，T是树．→设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2 ．→设G是具有n个结点m条边k个面的连通平面图，则m等于n+k-2 ，那n+k-m=2→设图G是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4 条边后使之变成树．→设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去 1 条边后使之变成树．→设G＝<V, E>是有6个结点，9条边的无向连通图，则可从G中删去 4 条边，可以确定图G的一棵生成树．→设G＝<V, E>是有4个结点，8条边的无向连通图，则可从G中删去 5 条边，可以确定图G的一棵生成树．→设G＝<V, E>是有20个结点，25条边的连通图，则可从G中删去 6 条边，可以确定图G的一棵生成树．→设G＝<V, E>是有6个结点，8条边的连通图，则可从G中删去 3 条边，可以确定图G的一棵生成树．→设G=<V, E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于n-1 ，则在G中存在一条汉密尔顿路．→若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W≤|S| ．→设个体域D＝{1,2}，则谓词公式(∀x)A(x)消去量词后的等值式为A(1) ∧A(2) ．→设个体域D＝{1,2}，则谓词公式(∃x)A(x)消去量词后的等值式为A(1)∨A(2) ．→设个体域D＝{a, b, c}，则谓词公式(∀x)A(x)消去量词后的等值式为A(a)∧A (b)∧(Ac）．→设个体域D＝{a, b}，则谓词公式(∀x)A(x)∧(∃x)B(x)消去量词后的等值式为(A(a)∧A (b))∧(B(a)∨B(b)) ．→设个体域D＝{a, b}，则谓词公式(∀x)(A(x)∧B(x))消去量词后的等值式为(A (a)∧B (b)) ∧ (A(a)∧B(b)) ．→设个体域D＝{a, b},那么谓词公式∃xA(x)∨∀yB(y)消去量词后的等值式为(A(a)∨A(b))∨((B(a) ∧B(b)) ．→设个体域D＝{1, 2, 3}，P(x)为“x小于2”，则谓词公式(∀x)P(x) 的真值为假（或F, 或0）．→设个体域D＝{1, 2}，A(x)为“x大于1”，则谓词公式(∃x)A(x) 的真值为真（或T, 或1）．→设个体域D＝{1, 2}，A(x)为“x大于2”，则谓词公式(∃x)A(x) 的真值为假（或F, 或0）．→设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(∃x)A(x) 的真值为假（或F, 或0）．→设个体域D＝{1, 2, 3,4}，A(x)为“x等于3”，则谓词公式(∃x)A(x) 的真值为真（或T, 或1）．→命题公式P∨⌝P的真值是真（或T, 或1）．→命题公式P∧⌝ P的真值是假（或F, 或0）．→命题公式P→(Q∨P)的真值是真（或T, 或1）．→ (∀x)(A(x)→B(x))∨C(x, y)中的自由变元为C(x, y )中的x与y ．→ (∀x)(A(x) →B(x, z)∨C(y))中的自由变元有z，y ．→ (∀x)(P(x) →Q(x)∨R(x, y))中的自由变元为R(x, y )中的y．→ (∀x)(P(x) →R(y)∨S(z)) 中的约束变元有x ．→ (∀x)(P(x) →Q(x)∨R(x, y))中的约束变元为x ．→ (∀x)((A(x)∧B(x))∨C(y))中的自由变元为y ．→含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式(P∧Q∧R)∨(P∧Q∧⌝R) ．三、逻辑公式翻译（每小题6分，本题共12分）→将语句“雪是黑色的”翻译成命题公式．设P：雪是黑色的，则命题公式为：P．→将语句“今天上课”翻译成命题公式．设P：今天上课，则命题公式为：P．→将语句“他是学生”翻译成命题公式．设P：他是学生，则命题公式为：P．→请将语句“今天是天晴”翻译成命题公式．设P：今天是晴天。
