第一讲 命题逻辑(一)

测验-命题逻辑(一)

1、令P:今天晚上我在家看书,Q:今天晚上我去电影院看电影。则命题“今天晚上我在家看书或去电影院看电影。”可以符号化为:( )
    A、
    B、
    C、
    D、

2、下列命题公式不是永真式的是( )
    A、
    B、
    C、
    D、

3、
    A、
    B、
    C、
    D、

4、若p:今天天气好;q:他去爬山;则“如果今天天气不好,他不去爬山”,可符号化为( )
    A、
    B、
    C、
    D、

5、下列各命题中真值为假的命题有( )
    A、2+2=4当且仅当3是奇数
    B、2+2=4当且仅当3不是奇数
    C、2+2≠4当且仅当3是奇数
    D、2+2≠4当且仅当3不是奇数

6、命题公式的成真赋值为( )
    A、00
    B、01
    C、10
    D、11

作业-命题逻辑(一)

1、1、判断公式:的类型,请写出过程。 2、用等值演算证明等值式

第二讲 命题逻辑(二)

测验-命题逻辑(二)

1、下面哪一个命题是假命题?
    A、如果2是偶数,那么一个公式的析取范式唯一
    B、如果2是偶数,那么一个公式的析取范式不唯一
    C、如果2是奇数,那么一个公式的析取范式唯一
    D、如果2是奇数,那么一个公式的析取范式不唯一

2、命题公式的主析取范式中的极小项的个数为?
    A、0
    B、1
    C、2
    D、3

3、称由前提 推出结论的推理正确,则应为下列4个中哪一个?
    A、重言式或可满足式
    B、矛盾式
    C、可满足式
    D、重言式

4、的合取范式为?
    A、
    B、
    C、
    D、

5、下列哪些公式为永真蕴含式?
    A、
    B、
    C、
    D、

6、对于前提:,其有效结论为?
    A、
    B、
    C、
    D、

作业-命题逻辑(二)

1、1、构造下面推理的证明: 如果今天是星期六,我们就去公园或去爬山; 如果公园人太多,我们就不去公园; 今天是星期六,公园人太多,所以我们去爬山.

第三讲 谓词逻辑(一)

测验-谓词逻辑(一)

1、命题“有的学生不踢足球”的逻辑符号化表示为? 设D:全总个体域,F(x):x是足球,M(x) :x是学生,H(x,y):x不踢y
    A、
    B、
    C、
    D、

2、“不是每一个实数都是有理数”的逻辑符号化为? 设R(x):x是实数,Q(x):x是有理数。
    A、
    B、
    C、
    D、

3、公式可换名为( ),使其无既是约束出现又是自由出现的变量,且变量不同时被不同量词约束。
    A、
    B、
    C、
    D、

4、取个体域为整数集,下列公式为真的有?
    A、
    B、
    C、
    D、

5、给定公式 ,当 时,解释()使该公式真值为0.
    A、
    B、
    C、
    D、

6、下列谓词公式中,为重言式的有?
    A、
    B、
    C、
    D、

作业-谓词逻辑(一)

1、1、令L(x,y)表示“x喜欢y”,个体域为所有人的集合,用谓词和量词表示命题: (1)每个人都喜欢一些人 (2)有些人被所有人喜欢 2、给定解释I如下: (1)个体域为D={-2,3,6} (2)D上特性谓词: 在解释I下,求的真值。 3、判断公式的类型。

第四讲 谓词逻辑(二)

测验-谓词逻辑(二)

1、下列谓词公式中,为重言式的有?
    A、
    B、
    C、
    D、

2、给定推理
    A、
    B、
    C、
    D、

3、下列推理步骤错在?
    A、
    B、
    C、
    D、

4、下列公式中等值的是?
    A、
    B、
    C、
    D、

5、下面蕴涵关系式成立的是?
    A、
    B、
    C、
    D、

6、给定公式的前束范式是?
    A、
    B、
    C、
    D、

作业-谓词逻辑(二)

1、符号化命题,并推证其结论: 所有的好书定价都高,没有一本书定价高。所以没有一本书是好书。

第五讲 集合

测验-集合

1、下列关于集合的表示中正确的是?
    A、
    B、
    C、
    D、

2、设集合,则A的幂集
    A、
    B、
    C、
    D、

3、设为集合,当,有() ?
    A、
    B、
    C、
    D、

4、判断下列每组的两个集合是否相等?
    A、
    B、
    C、x | x是有理数并且是无理数
    D、

5、下列命题中真值为真的有?
    A、
    B、
    C、
    D、

6、下列命题中真值为假的有?
    A、
    B、
    C、
    D、

作业-集合

1、1、设A,B,C是任意集合,证明: 2、设A={1,3,5,7,9,11},B={1,2,5,7,11},C={2,3,6,9,12},计算,,

第六讲 关系和函数(一)

测验-关系和函数(一)

1、设为集合,,在上有( )种不同的关系?
    A、
    B、
    C、
    D、

2、设上的关系,是所有人的集合, 的父亲的母亲表示关系 ()?
    A、的丈夫
    B、的孙子或孙女
    C、
    D、的祖父或祖母

3、集合上的关系具有下列哪些性质?
    A、自反性
    B、反自反性
    C、对称性
    D、反对称性

4、设集合上的二元关系 则S是R的()闭包.
    A、自反
    B、对称
    C、传递
    D、以上都不对

5、设集合上的关系,则R的传递闭包t(R) 具备下列哪些性质?
    A、反自反性
    B、对称性
    C、反对称性
    D、传递性

6、设R,S是集合A上的关系,则下列说法不正确的是?
    A、若R,S 是自反的, 则是自反的
    B、若R,S 是反自反的, 则是反自反的
    C、若R,S 是对称的, 则是对称的
    D、若R,S 是传递的, 则是传递的

作业-关系和函数(一)

1、1、设是集合 中的二元关系。证明如果有,那么: (1) (2) 2、如果关系都是自反的,关系是反自反的吗?请给出证明。

第七讲 关系和函数(二)

测验-关系和函数(二)

1、设S={1,2,3},S上的不同的等价关系有()个?
    A、1
    B、3
    C、5
    D、不确定

2、设, R是A上的整除关系, ,则集合B的最大元,最小元,上界,下界依次为?
    A、8、2、8、2
    B、无、2、无、2
    C、6、2、6、2
    D、8、1、6、1

3、下列函数,哪一个是双射?
    A、
    B、
    C、
    D、

4、设集合A ={1, 2, 3}, 下列关系R中哪些是等价关系?
    A、{<1, 1>, <2, 2>, <3, 3>}
    B、{<1, 1>, <2, 2>, <3, 3>, <3, 2>, <2, 3>}
    C、{<1, 1>, <2, 2>, <3, 3>, <1, 3>}
    D、{<1, 1>, <2, 2>, <1, 2>, <2, 1>, <1, 3>, <3, 1>, <3, 3>, <2, 3>, <3, 2>}

5、设集合A = {1, 2, 3}, 下列关系R中哪些是偏序关系?
    A、{<1, 1>, <2, 2>, <3, 3>}
    B、{<1, 1>, <2, 2>, <3, 3>, <3, 2>, <2, 3>}
    C、{<1, 1>, <2, 2>, <3, 3>, <1, 3>}
    D、{<1, 1>, <2, 2>, <1, 2>, <2, 1>, <1, 3>, <3, 1>, <3, 3>, <2, 3>, <3, 2>}

6、设X= {1, 2, 3}, Y ={a, b, c},确定下列关系是否为从X到Y的函数。
    A、{<1, a>, <2, a>, <3, c>}
    B、{<1, c>, <2, a>, <3, b>}
    C、{<1, c>, <1, b>, <3, a>}
    D、{<1, b>, <2, b>, <3, b>}

作业-关系和函数(二)

1、1、A={1,2,3,4},AxA上关系R定义为:(x,y)R(u,v),当且仅当 x+ v = u+ y ,证明R是等价关系,并确定由R对集合AxA的划分。 2、设A和B都是无限集,B⊆A,问A−B 是否一定无限,是否一定有限,为什么? 3、给出三个不同的自然数集合N的真子集,使得它们都与N等势。

第八讲 图论

测验-图论的基本概念

1、设G=(V,E)为无环的无向图,|V|=6,|E|=16,则G是?
    A、完全图
    B、零图
    C、简单图
    D、多重图

2、图的结点和边分别存在一一对应关系是同构的?
    A、充分条件
    B、必要条件
    C、充分必要条件
    D、既不充分也不必要条件

3、设|V|>1,D=(V,E)是强连通图,当且仅当?
    A、D中至少有一条通路
    B、D中至少有一条回路
    C、D中有通过每个结点至少一次的通路
    D、D中有通过每个结点至少一次的回路

4、图的邻接矩阵为
    A、
    B、
    C、
    D、

5、设图G是简单有向图,可达矩阵P(G)刻画下列关系中的?
    A、点与边
    B、边与点
    C、点与点
    D、边与边

6、在二分图中有长度为()的回路?
    A、3
    B、4
    C、5
    D、6

作业-图论

1、1、画出以(1,2,2,3)为度数列的简单图和非简单图各一个。 2、设G是n阶k-正则图,证明G的补图也是正则图。 3、有向图D如图1所示,回答下列问题: (1)D是哪类连通图? (2)D中长度为1、2、3、4的通路各有多少条?其中有多少条回路? (3)D中长度小于或等于4的通路有多少条?其中有多少条回路?

第九讲 特殊图 (一)

测验-特殊图(一)

1、若完全图G中有n个结点(),m条边,则当()时,图G是欧拉图。
    A、n为奇数
    B、n为偶数
    C、m为奇数
    D、m为偶数

2、下列关于哈密顿图的判断正确的是?
    A、A为哈密顿图
    B、B为哈密顿图
    C、C为哈密顿图
    D、D为哈密顿图

3、在下列关于图论的命题中,为真的命题是( )
    A、哈密顿图一定是欧拉图
    B、欧拉图一定是哈密顿图
    C、无向完全图都是欧拉图
    D、无向完全图都是哈密顿图

4、当n为( )时,必为欧拉图
    A、偶数
    B、奇数
    C、大于2的整数
    D、任意数

5、当n为( )时,必为哈密顿图
    A、偶数
    B、奇数
    C、大于2的整数
    D、任意数

6、结点a到结点z的最短路径距离是

作业-特殊图(一)

1、1、在哥尼斯堡七桥问题中,至少再架几座桥,游人就可以从陆地的某一点出发经过每座桥一次且仅一次,最后回到出发地点? 2、设G是n()阶无向简单哈密顿图,则对于任意不相邻的结点vi,vj,均有。这个结论成立吗?为什么?

第十讲 特殊图 (二)

测验-特殊图(二)

1、n为大于2的任意值,下面的图哪个是二分图?
    A、
    B、
    C、
    D、

2、完全二分(部)图的关联矩阵有多少行?
    A、m
    B、n
    C、m+n
    D、mn

3、一个连通平面图共有9个结点,它们的度数分别为:2,2,2,3,3,3,4,5,6,这个图共有()个面?
    A、6
    B、7
    C、8
    D、9

4、对图的结点着色,最少用几种颜色?
    A、m
    B、m+n
    C、n
    D、2

5、如图所示的带权图中经过每天边至少一次的回路(中国邮路)长度为( )。
    A、31
    B、35
    C、40
    D、36

6、下面哪个图不存在完美匹配?
    A、(1)
    B、(2)
    C、(3)
    D、都不存在

作业-特殊图(二)

1、1、求如图所示的带权图的经过图中每条边至少一次的回路(中国邮路)?写出过程。 2、证明:如果简单图G是二分图,有n个结点m条边,则

第十一讲 树

测验-树

1、下面哪一种图不是树?
    A、无回路的连通图
    B、有n个结点,n-1条边的连通图;
    C、每对结点间都有路的图;
    D、连通但删去一条边则不连通的图。

2、下面给出的各符号串集合,哪个不是前缀码?
    A、{11,00,10,01}
    B、{a,b,c,ac,abc,bc}
    C、{11,101,010,0001,0011}
    D、{a,b,cb, cde}

3、设T是如下的二元树T,下面()是对T先根遍历访问所有结点的结果?
    A、hdnibeajfkclgom
    B、abdhinecfjkglmo
    C、hnidebjkflomgca
    D、abcdefghijklmo

4、设G是由5个顶点构成的完全图,则从G中删去( )边可以得到树。
    A、6
    B、5
    C、8
    D、4

5、设G是一棵无向树,则G一定是()?
    A、平面图
    B、半欧拉图
    C、二分图
    D、连通图

6、设G是一棵根树,则G一定是?
    A、强连通图
    B、单向连通图
    C、弱连通图
    D、有向连通图

作业-树

1、1、设一棵树中度为k的结点数是nk(2≤k),求它的树叶的数目? 2、证明: 简单连通无向图G的任何一条边,都是G的某一棵生成树的边。 3、画出产生前缀码{11,01,001,1001,1010}的二元树。

期末考试

期末考试

1、在下面语句中,是命题的只有()。
    A、在实数范围内,
    B、在实数范围内,x+y<3
    C、请回答这个问题!
    D、大家想做什么,就做什么,行吗?

2、下列各命题中真值为假的命题有()。
    A、如果太阳从西边出来,那么地球自转
    B、如果地球自转,那么太阳从西边出来
    C、如果太阳从东边出来,那么地球自转
    D、如果地球自转,那么太阳从东边出来

3、下面哪一个命题是命题“2是偶数或-3是负数”的否定( )
    A、2是偶数或-3不是负数;
    B、2是奇数或-3不是负数;
    C、2不是偶数且-3不是负数;
    D、2是奇数且-3不是负数.

4、设:P:他去游泳。Q:他休假。则命题“如果他休假,他就去游泳。”可符号化为()?
    A、
    B、
    C、
    D、

5、设F(x):x是学生,G(x):x是体育运动,H(x,y):x喜欢y。命题“所有学生都喜欢某种体育运动”的符号化公式是?
    A、
    B、
    C、
    D、

6、命题公式A与B是等价的,是指
    A、A与B有相同的命题变元
    B、A与B都是可满足的
    C、当A的真值为真时,B的真值也为真
    D、A和B有相同的真值表

7、设个体域为整数集,下列真值为真的公式是
    A、
    B、
    C、
    D、

8、下列公式中等值的是?
    A、
    B、
    C、
    D、

9、下面的四个谓词逻辑推理,其中正确的是:
    A、前提: 结论:
    B、前提:结论:
    C、前提: 结论:
    D、前提: 结论:

10、命题公式是( )?
    A、矛盾式;
    B、可满足式;
    C、重言式;
    D、以上都不是

11、设论域,与公式等价的命题公式是( )?
    A、
    B、
    C、
    D、

12、在谓词演算中,P(a)是的有效结论,其理论依据是( )?
    A、全称量词消去规则(UI)
    B、全称量词推广规则(UG)
    C、存在量词消去规则(EI)
    D、存在量词推广规则(EG)

13、下列可称为集合的是:
    A、某本书中第a页上汉字的全体
    B、很大数的全体
    C、全体高个子的人
    D、全部接近于0的数

14、,则有____既是S的元素,又是S的子集。
    A、
    B、
    C、
    D、

15、设R为A上的关系,则下列说法错误的是?
    A、R在A上自反当且仅当
    B、R在A上反自反当且仅当
    C、R在A上对称当且仅当
    D、R在A上反对称当且仅当

16、设R是非空集合A上的关系,则下列说法错误的是?
    A、R是自反的当且仅当r(R)=R
    B、R是对称的当且仅当s(R)=R
    C、R是传递的当且仅当t(R)=R
    D、以上说法都不对

17、设A={a,b,c,d},A上的等价关系,则对应于R的A的划分是()?
    A、{{a},{b, c},{d}}
    B、{{a, b},{c}, {d}}
    C、{{a},{b},{c},{d}}
    D、{{a, b}, {c,d}}

18、对于集合A={1,2,3,4}上的下列关系,是偏序关系的是?
    A、R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)},
    B、R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,1),(2,4),(3,1),(3,4),(4,4)},
    C、R={(1,1),(1,2),(1,3),(1,4),(2,2), (2,1),(3,1),(3,3),(4,1),(4,4)},
    D、R={(2,1),(1,2),(1,3),(1,4),(2,2), (4,3),(2,4),(3,3),(3,4),(4,4)}

19、集合A上的等价关系R的关系矩阵M(R)的对角线元素____?
    A、全是1
    B、全是0
    C、有的是1,有的是0
    D、有的是2

20、设S={1,2,3},S上的不同的等价关系有____个?
    A、1
    B、3
    C、5
    D、不确定

21、集合A={1,2,3,4}上的偏序关系如下图所示,则它的哈斯图为?
    A、[A]
    B、[B]
    C、[C]
    D、[D]

22、下列关系中能构成函数的是?
    A、
    B、
    C、
    D、

23、设R为实数集,映射,则f是()?
    A、单射而非满射
    B、满射而非单射
    C、双射
    D、既不是单射,也不是满射

24、设Z、N、E分别为整数集,自然数集,偶数集,则下列函数是双射的为?
    A、
    B、
    C、
    D、

25、设无向图G有12条边,已知G中3度顶点有6个,其余顶点的度数都小于3,则该图至少有()个结点?
    A、6
    B、8
    C、9
    D、12

26、判断下列各非负整数列是否是无向简单图的结点度数序列?
    A、(5,5,4,4,2,1)
    B、(1,1,2,2,2)
    C、(0,1,3,3,3)
    D、(2,3,4,4,5)

27、在有n个结点的连通图中,其边数( )?
    A、最多有n-1条
    B、至少有n-1条
    C、最多有n条
    D、至少有n条

28、已知图G的邻接矩阵如下图所示,则G有( )?
    A、6个结点,8条边
    B、6个结点,6条边
    C、5个结点,8条边
    D、5个结点,6条边

29、两个图具有相同的顶点数和边数是这两个图同构的?
    A、充分条件
    B、必要条件
    C、充分必要条件
    D、以上说法都不对

30、下列图中, 不是哈密顿图。
    A、(1)
    B、(2)
    C、(3)
    D、(4)

31、若连通平面图G有4个节点,3个面,则G有______条边?
    A、3
    B、4
    C、5
    D、6

32、对7个结点的完全图K7的结点着色,最少用几种颜色?
    A、4
    B、5
    C、6
    D、7

33、在Peterson图中,至少填加()条边才能构成Euler图?
    A、1
    B、2
    C、4
    D、5

34、设图G是有6个顶点的连通图,总度数为20,则从G中删去( )条边后使之变成树。
    A、10
    B、5
    C、3
    D、2

35、已知一棵无向树T有三个3度结点,一个2度结点,其余的都是1度结点, 则T 中有几个1度结点?
    A、3
    B、4
    C、5
    D、6

36、“空气是人生存所必需的”是陈述句,也是命题.

37、若P:每一个自然数都是偶数,则ØP:每一个自然数都不是偶数.

38、如果5<1,则太阳从东边升起.

39、同一谓词公式,指定不同的论域,其真值不一定相同.

40、

41、A×B={(a,b)|a∈A∧b∈B}

42、若集合A上的关系R是对称的,则~R也是对称的.

43、设R和S是集合A上的等价关系,则RÈS一定是等价的.

44、R∘R=R是集合A上的关系R为传递的充分必要条件.

45、{a}⊆{{a}}

46、任一图G=(V,E)的顶点的最大度数必小于G的顶点数.

47、在有向图中,顶点间的互相可达关系是等价关系.

48、若n个顶点的简单无向图G的边数e=n−1,则G一定是树.

49、在n阶图G中,若从结点u到v(u≠v)存在通路,则从u到v存在长度小于或等于n−1的通路.

50、若有n个人,每个人恰恰有5个朋友,则n可能为奇数.