一、填空题
二、选择题
1．下列语句中不是命题的只有( ) ．．A．鸡毛也能飞上天？ C．不经一事，不长一智。 2．下列是真命题的有（ ）
A． {a}{{a}}；
B．{{}}{,{}}；
B．或重于泰山，或轻于鸿毛。 D．牙好，胃口就好。
C． {{},}； D． {}{{}}。 3．下列集合中相等的有（ ）
A．{4，3}；B．{，3，4}；C．{4，，3，3}；D． {3，4}。
S
4．设S{,{1},{1,2}}，则 2 有（ ）个元素。
A．3； B．6； C．7； D．8 。
5．令p：张三做这件事，q：李四做这件事，则命题“这件事由张三和李四中的一人去做”可符号化为( ) ．．．．．A．p ∨ q
B．(p∧q)∨(p∧q)
C．(p∨q)∧(p∨q) D．(p∧q)∧(p∧q)
6．从真值角度看，命题公式的全部类型是( ) ．．．．．．．．．．A．永真式 C．永真式，永假式
B．永假式
D．永真式，永假式，可满足式
7．下述命题公式中，是重言式的为（ ）。
A、(pq)(pq) ； B、(pq)((pq))(qp)) ； C、(pq)q ； D、(pp)q 。
8．设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”可符号化为( ) ．．．．A．(x)(A(x)B(x))
B．(x)(A(x)B(x))
C．(x)(A(x)B(x)) D．(x)(A(x)B(x))
9．关于谓词公式(x)(y)(P(x, y)∧Q(y, z))∧(x)p(x, y),下面的描述中错误的是．．( )
A．(x)的辖域是(y)(P(x, y)∧Q(y, z)) B．z是该谓词公式的约束变元 C．(x)的辖域是P(x, y)
D．x是该谓词公式的约束变元
10．A，B是集合，P(A)，P(B)为其幂集，且A∩B=，则P(A)∩P(B)为( ) A． B．{} C．{{}} D．{，{}} 11．设S{,{1},{1,2}}，则有（ ）S。
A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。
12．设A={a, b, c}， A上二元关系R={ B．反对称的 D．不可传递的 13．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}， S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1R-1的运算结果是( ) A．{〈4，1〉，〈2，3〉，〈4，2〉} C．{〈4，1〉，〈2，3〉，〈2，4〉} B．{〈2，4〉，〈2，3〉，〈4，2〉} D．{〈2，2〉，〈3，1〉，〈4，4〉} 14．下面关于关系R的传递闭包t(R)的描述最确切的是( ) ．．．A．t(R)是包含R的二元关系 C．t(R)是包含R的一个传递关系 B．t(R)是包含R的最小传递关系 D．t(R)是任何包含R的传递关系 15．设S{ 1, 2, 3 }，S上关系R的关系图为 则R具有（ ）性质。 A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 1016．关系R的关系矩阵为MR00( ) 0100101001，则关系R所具有的性质是 ．．01A.自反、对称、传递 B.自反、反对称、传递 C.反自反、对称、传递 D.自反、反对称 17．设S={1，2，3}，R为S上的关系，其关系图为 则R具有（ ）的性质。 A、自反、对称、传递； B、什么性质也没有； C、反自反、反对称、传递； D、自反、对称、反对称、传递。 18．设集合X为人的全体，在X上定义关系R、S为R={ R 和 S是 P B． RS-1 D． R-1S 上的关系，P 是所有人的集合， R{x,y|x,yPx是y的父亲}，S{x,y|x,yPx是y的母亲} 则 S1R表示关系 （ ）。 }； A、{x,y|x,yPx是y的丈夫}； B、{x,y|x,yPx是y的孙子或孙女C、 ； }。 D、{x,y|x,yPx是y的祖父或祖母20．设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（ ） 21. 函数的复合运算满足( ) ．． A．交换律 B．分配律 C．结合律 D．等幂律 22．设简单图G所有结点的度数之和为12，则G一定有( ) ．．．A．3条边 B．4条边 C．5条边 23．下列各有向图是强连通图的是( ) D．6条边 24．设无向图G的边数为m，结点数为n，则G是树等价于( ) ．．．A．G连通且m=n+1 C．G连通且m=2n B．G连通且n=m+1 D．每对结点之间至少有一条通路 25．设G为简单图，若图中存在一条经过每边一次且仅一次的回路，则此图为：( ) A、欧拉图 B、哈密顿图 C、平面图 D、树 26．下列语句中不是命题的只有( ) ．．A．这个语句是假的。 C．飞碟来自地球外的星球。 B．1+1=2.0 D．凡石头都可练成金。 27．下列语句是命题的有（ ）。 A、明年中秋节的晚上是晴天； B、xy0； C、xy0当且仅当x和y都大于0； D、我正在说谎。 28．设p：天下大雨，q：他在室内运动，命题“除非天下大雨，否则他不在室． 内运动”可符合化为( ) A. ┐p∧q C. ┐p→┐q 29．下列各命题中真值为真的命题有（ ）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当3不是奇数； C、2+2≠4当且仅当3是奇数； D、2+2≠4当且仅当3不是奇数； 30．下列命题公式为重言式的是( ) ．A．q→（p∧q） C．（p∧q）→p 31．下列等价式成立的有（ ）。 A、PQQP ； B、P(PR)R ； C、 P(PQ)Q； D、P(QR)(PQ)R。 32．设个体域D是正整数集合，下列命题为真命题的是( ) ．．．． A． xy (xy=y) B．xy(x+y=y) C．xy(x+y=x) D．xy(y=2x) 33．公式Ax(P(x)Q(x))的解释I为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A的真值为（ ）。 A、1； B、0； C、可满足式； D、无法判定。 34．下列符号串是合式公式的有（ ） A、PQ ；B、PPQ ；C、(PQ)(PQ)；D、(PQ)。 35．A，B为二合式公式，且AB，则（ ）。 **A、AB为重言式； B、AB； **C、AB； D、AB； E、AB为重言式。 B. ┐p→q D. p→┐q B．p→（p∧q） D．（p∨q）→q 36．在公式(x)(y)(P(x,y)Q(z))(y)P(y,z)中变元y是( ) A．自由变元 B．约束变元 C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元 37．给定公式xP(x)xP(x)，当D={a,b}时，解释（ ）使该公式真值为0。 A、P(a)=0、P(b)=0； B、P(a)=0、P(b)=1； C、P(a)=1、P(b)=0； D、P(a)=1、P(b)=1 38．命题“有的人喜欢所有的花”的逻辑符号化为（ ）。 设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y A、x(M(x)y(F(y)H(x,y)))；B、x(M(x)y(F(y)H(x,y)))； C、x(M(x)y(F(y)H(x,y)))；D、x(M(x)y(F(y)H(x,y))) 39．若A－B=Ф，则下列哪个结论不可能正确？( ) ．．．．． A．A=Ф B. B=Ф C. AB D. BA 40．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}， 则S是( ) A．自反关系 B．反自反关系 C．对称关系 D．传递关系 1041．关系R的关系矩阵为MR00( ) 0100101001，则关系R所具有的性质是 ．．01A.自反、对称、传递 B.自反、反对称、传递 C.反自反、对称、传递 D.自反、反对称 42．下列等价关系正确的是（ ）。 x(P(x)Q(x))xP(x)xQ(x)；x(P(x)Q(x))xP(x)xQ(x)；A、B、 C、x(P(x)Q)xP(x)Q； D、x(P(x)Q)xP(x)Q。 43．设A={1，2，3，4}，A上的等价关系R={<1, 2>，<2, 1>，<3, 4>,，<4, 3>}∪IA，则对应于R的A的划分是( ) A．{{1}，{2, 3}，{4}} B．{{1, 2}，{3}，{4}} C．{{1}，{2}，{3}，{4}} 射函数的是( ) A ． f D．{{1, 2}, {3,4}} 44．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A到B的单 ={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B ． f ={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C．f ={<1,6>,<2,7>,<4,9>,<3,8>} D．f ={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} 45．设有集合X和Y，且|X|=m，|Y|=n，则从X到Y有( )个不同的双射．．函数。 A．nm B． m! C．m+n D．mn 50．设G是一个哈密尔顿图，则G一定是( ) A．连通图 B．树 C．平面图 D．欧拉图 51．下列各图是无向完全图的是( ) 52．一棵无向树的顶点数n与边数m关系是( ) A．m＝n＋2 B．m＝n－2 C． n＝m＋1 D． n＝m－1 53．下列语句中不是命题的有（ ） ⑴ 9+512 ； ⑵ x+3=5； ⑶我用的计算机CPU主频是1G吗？； ⑷ 我要努力学习。 54．下列语句中是真命题的只有( ) ．．．．A．宇宙间只有地球上有生命。 C．大偶数都是两个素数之和。 B．我正在说谎。 D．17只能被1和它本身整除。 55．命题“我不能一边听课，一边看小说”的符号化为（ ） ⑴ PQ ； ⑵ PQ； ⑶ QP ； ⑷ (PQ)。 56．设p：我想睡，q：我去学习，命题：“除非我想睡，否则我就去学习”的符 号化正确的是( ) ．．A．┐p∧q C．┐p→┐q 57．若公式(PQ)(PR)的主析取范式为 B．┐p→q D．p→┐q m001m011m110m111则它的主合取范式为（ ） ⑴ m001m011m110m111 ； ⑵ M000M010M100M101 ； ⑶M001M011M110M111； ⑷ m000m010m100m101 。 58．命题“尽管有人聪明，但未必一切人都聪明”的符号化 （P(x)：x是聪明的，M(x)：x是人） （ ） ⑴ x(M(x)P(x))(x(M(x)P(x))) ⑵ x(M(x)P(x))(x(M(x)P(x))) ⑶ x(M(x)P(x))(x(M(x)P(x))) ⑷x(M(x)P(x))(x(M(x)P(x))) 59．下列命题公式中不是重言式的是( ) ．．A．p→(q→r) B．p→(q→p) C． ┐p→(┐p→┐p) D．(p→(q→r)) (q→(p→r)) 60．设个体域是整数集，则下列命题的真值为真的是( ) ．．A．yx(x·y=1) C．xy (x·y=y2) 61．下列表达式正确的有（ ） ⑴ (PQ)Q； ⑵ PQP ； ⑶ (PQ)(PQ)P； ⑷ P(PQ)T。 62．下列等价式正确的是( ) ．． B．xy (x·y≠0) D．yx(x·y=x2) A．┐(x)A(x)┐A B．(x)(y)A(x)(y)A C．┐(x)A(x)┐A D．(x)(A(x)B(x))(x)A(x)(x)B(x) 4．n个命题变元可产生（ ）个互不等价的小项。 ⑴ n ； ⑵ n2 ； ⑶ 2n ； ⑷ 2n。 63．下列公式是前束范式．．．．． 的是( ) A．((x)F(x)(y)G(y))H(z) B． (x)(y)(F(z,x)G(y)) C．(x)F(x,y)(y)G(y) D．(x)(F(x,y)(y)G(x,y)) 64．A是素数集合，B是奇数集合，则A-B=（ ） ⑴ 素数集合； ⑵ 奇数集合； ⑶ ； ⑷ {2}。 65．下列选项中错误．．的是( ) A．ØØ B．Ø∈Ø C．Ø{Ø} D．Ø∈{Ø} 66．设A={} ，B=Р(Р(A)) 下列（ ）表达式成立。 ⑴ B ； ⑵ B； ⑶ B； ⑷ B。 67．在{1，2，3，4，5}上定义的关系R＝{ 68．集合A={a，b，c}上的下列关系矩阵中符合等价关系．．．．．． 条件的是( 101100A．010 B．01110 0111110101C．011 D．01010 1011 ) ) 70．设A={a，b，c，d}，A上的等价关系R={ B．{{a, b}，{c}，{d}} D．{{a, b}, {c, d}} 71．集合A={2，3，6，12，24，36}上偏序关系R的Hass图为 则集合B={2，3，6，12}的上确界 。 B={2，3，6，12}的下界 B={6，12，24，36}的下确界 B={6，12，24，36}的上界 ⑴ 2； ⑵ 3； ⑶ 6； ⑷ 12； ⑸ 无。 72．设R为实数集，函数f：R→R，f(x)=2x，则f是( ) ．A．单射函数 B．满射函数 C．双射函数 D．非单射非满射 73. 设f：A→B的函数，当f是( )时，f才有反函数。 ． A．单射 B．满射 C．双射 D．函数 74．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是( ) A．3 C．5 B．4 D．6 75．下列各图中既是欧拉图，又是哈密尔顿图的是( ) A． B． C． D． 76．设G是一棵树，n，m分别表示顶点数和边数，则( ) A． n=m B．m=n+1 C．n=m+1 D．不能确定 77．设G为简单图，若图可以以边不交叉的方式画在一张纸上，则此图为( ) A、欧拉图 B、哈密顿图 C、平面图 D、树 三、综合题 24、N台计算机，用k条网线连接，证明，人们总能通过网线，从一台计算机到达另一台计算机。 25、某市的街道是互通的，一个警察要去巡逻一次，他要以正反方向巡逻街的两边，并且巡逻每条街的每一边仅一次。证明，他从警局出发，总是能回到警局。 26．设6个字母在通讯中出现频率如下： A：35% B：20% C：25% D：10% E：5% F：5% (1) 以频率乘100为权，求最优2元树。（2）利用所求最优2元树找出每个字母的前缀码。 27、判断下面推理是否正确，并证明你的结论。 如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。 28、公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下： （1）营业员A或B盗窃了钻石项链 （2）若B作案，则作案时间不在营业时间 （3）若A提供的证词正确，则货柜未上锁 （4）若A提供的证词不正确，则作案发生在营业时间 （5）货柜上了锁 试问：作案者是谁？要求写出推理过程。 29、有6个村庄Vi，i=l，2，„，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低？要求写出求解过程，画出符合要求的最低费用的道路网络图并计算其费用。 30、设R是集合A上的自反、传递的二元关系，又设T也是A上的二元关系，且满足： x,yTx,yRy,xR。求证：T是A上的等价关系。 31、设R是集合X上的二元关系，证明R是X上传递关系当且仅当RRR。 32、在自然推理系统P中，利用附加前提法证明下面推理： 前提：(PQ),(QR),R,(PS) 结论： S 因篇幅问题不能全部显示，请点此查看更多更全内容