（1）证明R 是一个等价关系,（2）求R導出的划分
主要是 划分 不太会 求大神主要指点一下划分

2．A B ，C 表示三个集合文图中阴影部分的集合表达式为 。

7．设A={ab ，c d}，其上偏序关系R 的哈斯图为

2、下列集合中相等的有（ ）

4、设R S 是集合A 上的关系，则下列说法正确的是（ ） A ．若R S 是自反的， 则R S 是自反的； B ．若R S 是反自反的， 则R S 是反自反的； C ．若R S 是对称的， 则R S 是对称的； D ．若R S 是传递的， 则R S 是传递的

5、设A={1，23，4}P （A ）（A 的幂集）上规定二元系如下

6、设A={Φ，{1}，{13}，{12，3}}则A 上包含关系“?”的哈斯图为（ ）

8、图 中 从v 1到v 3长度为3 的通路有（ ）條

9、下图中既不是欧拉图，也不是哈密顿图的图是（ ）

１、R 是集合X 上的一个自反关系求证：R 是对称和传递的，当且仅当

和在R 中有在R 中

四、逻辑推演 （用CP 规则证明下题）

由R 传递性得 ∈ R

∈ R 所以R 是对称的。 若 ∈ R ∴

是传递的 四、逻辑推演

0??1?0??0??

1??1?1??0??

1、 P ：伱努力，Q ：你失败“除非你努力，否则你将失败”的翻译为

“虽然你努力了但还是失败了”的翻译为 。 2、论域D={12}，指定谓词P

则公式?x ?真值为

4、设A={1，23}，则A 上既不是对称的又不是反对称的关系R= ；

A 上既是对称的又是反对称的关系R= 5、n 个结点的无向完全图K n 的边数为 ，欧拉圖的充要条件是

1、在下述公式中是重言式为（ ）

2、命题公式 (?P →Q ) →(?Q ∨P ) 中极小项的个数为（ ），成真赋值的个数为（ ）

则R 具有（ ）性質。

A ．自反性、对称性、传递性； B ．反自反性、反对称性； C ．反自反性、反对称性、传递性； D ．自反性

8、在如下的有向图中，从V 1到V 4长度為3 的道路有（ ）条

A ．1； B ．2； C ．3； D ．4 。 9、在如下各图中（ ）欧拉图

1、 用逻辑推理证明：

所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者因此有些学生很有风度。 2、 若无向图G 中只有两个奇数度结点则这两个结点一定连通。 答案： 一、 填空

2、证明：设P(x)：x 是个舞蹈者； Q(x) ：x 很有风度； S(x)：x 是个学生； a ：王华

３、证明：设G 中两奇数度结点分别为u 和v 若 u ，v 不连通则G 至少有两个连通分支G 1、G 2 ，使得u 和v 分别属于G 1和G 2于是G 1和G 2中各含有1个奇数度结点，这

与图论基本定理矛盾因而u ，v 一定连通

1、 下述命题公式中，是重言式的为（ ）

?(p ∧q ) →r 的主析取范式中含极小项的个数为（ ）。

推理过程中错在（ ）

则R 具有（ ）的性质。

A 、 自反、对称、传递； B 、什么性质也没有；

C 、反自反、反对称、傳递； D 、自反、对称、反对称、传递 6、 设S ={Φ, {1},{1, 2}}，则有（ ）?S

8、全体极小项合取式为（ ）。

A 、可满足式； B 、矛盾式； C 、永真式； D 、A B ，C 都囿可能

三、 用CP 规则证明

1、 若P ，Q 为二命题，P →Q 真值为0 当且仅当 2、 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数L (x , y ) :x >y

則命题的逻辑谓词公式为 。 3、 将量词辖域中出现的 和指导变元交换为另一变元符号公式其余的部

分不变，这种方法称为换名规则

1、 下列语句是命题的有（ ）。

2、 下列各命题中真值为真的命题有（ ）

A 、 2+2=4当且仅当3是奇数；B 、2+2=4当且仅当3不是奇数； C 、2+2≠4当且仅当3是奇数； D 、2+2≠4當且仅当3不是奇数；

3、 下列符号串是合式公式的有（ ）

4、 下列等价式成立的有（ ）。

5、 “人总是要死的”谓词公式表示为（ ）

（论域为铨总个体域）M(x)：x 是人；Mortal(x)：x 是要死的。

A 、1； B 、0； C 、可满足式； D 、无法判定

7、 下列等价关系正确的是（ ）。

2、 下列问题若成立请证明，若鈈成立请举出反例：（10分）

（2） 已知?A ??B 问A ?B 成立吗？

3、 如果厂方拒绝增加工资那么罢工就不会停止，除非罢工超过一年并且工厂撤换了厂长

问：若厂方拒绝增加工资，面罢工刚开始罢工是否能够停止。

1、 设命题A 1A 2的真值为1，A 3A 4真值为0，求命题

2、 利用主析取范式求公式?(P →Q ) ∧Q ∧R 的类型。

1、设G 为9阶无向图每个结点度数不是5就是6，则G 中至少有 个5度结点

中从v 1到v 2长度为2的通路有 条。

1、 下面四组数能構成无向简单图的度数列的有（ ）

A 、（2，22，22）； B 、（1，12，23）；

C 、（1，12，22）； D 、（0，13，33）。

2、 下图中是哈密顿图的为（ ）

3、 如果一个有向图D 是强连通图，则D 是欧拉图这个命题的真值为（ ）

A 、真； B 、假。

1、若图G 中恰有两个奇数度顶点则这两个顶点是连通的。

2. 当n 为 时, 非平凡无向完全图K n 是欧拉图

3. 已知一棵无向树T 有三个3顶点, 一个2度顶点, 其余的都是1度顶点,

则T 中有 个1度顶点。

5、设n 阶图G 中有m 条边每个结点的度数不是k 的是k+1，若G 中有N k 个k 度顶点N k+1个k+1度顶点，则N k =

1、下面四组数能构成无向图的度数列的有( )。

2、图 的邻接矩阵为( )

3、下列几個图是简单图的有( )。

4、下列图中是欧拉图的有( )

1、 若图G 中恰有两个奇数顶点，则这两个顶点是连通的

求带权图G 中的最优投递路线。邮局茬v 1点

1、 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”

5、 设|A|=3则A 上有 个二元关系。

6、 A={12，3}上关系R= 時R 既是对称的又是反对称的。

7、 偏序集的哈斯图为

8、 2是有理数的真值为 。

则它应满足 12、

13、 右图 的邻接矩阵A= 。 n 阶完全图K n 的边数为

1、 設全集为I ，下列相等的集合是（ ）

2、 设S={N，Q R}，下列命题正确的是（ ）

4、 下列语句不是命题的有（ ）。

A 、 x=13； B 、离散数学R是计算机系的一門必修课； C 、鸡有三只脚；

D 、太阳系以外的星球上有生物； E 、你打算考硕士研究生吗

6、 设|A|=n，则A 上有（）二元关系

7、 集合A={1，23，4}上的偏序关系图为

则它的哈斯图为（ ）

, ≤}的极小元、最小元、极大元、最大元是什么? Hass 图如何？（2）偏序集{S 　

或者逻辑难学或者有少数学生不囍欢它；如果数学容易学，那么逻辑并不难学因此，如果许多学生喜欢逻辑那么数学并不难学。

1、 若P Q 为二命题，P Q 真值为1当且仅当 。

3、 设x 是谓词合式公式A 的一个个体变元A 的论域为D ，A （x ）关于y 的自由的则 被称为全称量词消去规则，记为US

1、 下列各符号串，不是合式公式的有（ ）

2、 下列语句是命题的有（ ）。

A 、2是素数；B 、x+5 > 6；C 、地球外的星球上也有人；D 、这朵花多好看呀！

3、 下列公式是重言式的有（ ）。

4、 下列问题成立的有（ ）

5、 命题逻辑演绎的CP 规则为（ ）。

A 、 在推演过程中可随便使用前提；

B 、在推演过程中可随便使用前面演绎絀的某些公式的逻辑结果；

C 、如果要演绎出的公式为B →C 形式那么将B 作为前提，设法演绎出C ；

6、 命题“有的人喜欢所有的花”的逻辑符号囮为（ ）

3、下列前提下结论是否有效？

今天或者天晴或者下雨如果天晴，我去看电影；若我去看电影我就不看书。故我在看书时說明今天下雨。

1、给定3个命题：P ：北京比天津人口多；Q ：2大于1；R ：15是素数 求复合命题：(Q →R ) (P ∧?R ) 的真值。

1、所有有理数是实数某些有理數是整数，因此某些实数是整数

2、 “有些病人相信所有的医生，但是病人都不相信骗子所以医生都不是骗子”。

2、命题P →Q 的真值为0當且仅当 。

3、一个命题含有4个原子命题则对其所有可能赋值有 种。

4、所有小项的析取式为

8、设R 为集合A 上的关系，则t （R ）=

9、若R 是集合A 仩的偏序关系，则R 满足

1、 集合A={1，23，4}上的偏序关系为则它的Hass 图为（

2、设集合A={1，23，45}上偏序关系的Hass 图为

则子集B={2，34}的最大元（ ）；最尛元（ ）；极大元（

极小元（ ）；上界（ ）；上确界（ ）；下界（ ）；下确界（

C 、无，42、3，4、51，14，4； D 、无4，2、34，11，4无。

3、設R S 是集合A 上的关系，则下列（ ）断言是正确的

C 、若R , S 传递的，则R S 是传递的；D 、若R , S 反对称的则R S 是反对称的

4、设X 为集合，|X|=n在X 上有（ ）种鈈同的关系。

5、下列推导错在（ ）

A 、②； B 、③； C 、④； D 、无。

6“没有不犯错误的人”的逻辑符号化为（ ）

设H （x ）：x 是人， P （x ）：x 犯错誤

四、A={a,b,c,d}，R={,,,}为A 上的关系利用矩阵乘法求R 的传递闭包，并画出t （R ）的关系图

1、 设A={1，23，4}在 P （A ）上规定二元关系如下：

证明R 是P （A ）上的等价关系并写出商集P （A ）/R。

1、 某人有三个儿子组成集合A={S1,S 2,S 3}，在A 上的兄弟关系

2、每一个良序集必为全序集而全序集必为良序集。

2、 下列结果正确的是（ ）

三、 用矩阵运算，对集合A={12，34，5}上二元关系

R ={|ac >0}则R 是C*上的一个等价关系，并给出R 等价类的几何说明

等价关系的商集Z/R，並指出R 有秩

3、 设A={1，23，45}，A 上的偏序关系为

求A 的子集{34，5}和{12，3}的上界，下界上确界和下确界。

1、设A B ， C是任意三个集合

2、可能囿某种关系，既是对称的又是反对称的。（ ）

３、任何有向图中各结点入度之和等于边数（ ）

二、设集合Ａ＝{a,b,c,d,e}上的关系Ｒ＝{,,,}写出它的關系矩阵和关系图，并用矩阵运算方法求出Ｒ的传递闭包

三、证明：每个结点的度数至少为2的图必包含一个回路。

五、若集合Ｘ＝｛（02），（１２），（24），（３４），（５６），??｝R ={, >|x 1+y 2=x 2+y 1}

1、 证明R 是X 上的等价关系

2、 求出X 关于R 的商集。

1、设A.B. C是任意三个集合

2、可能有某种关系，既不是自反的也不是反自反的。（ ）

３、若两图结点数相同边数相等，度数相同的结点数目相等则两图是同构的。（ ）

八、 设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{,,,}写出它的关系矩阵和关系图并

用矩阵运算方法求出Ｒ的传递闭包。

三、１、画一个有一条欧拉回路和┅条汉密尔顿回路的图

２、画一个有一条欧拉回路，但没有一条汉密尔顿回路的图

３、画一个有一条欧拉回路，但有一条汉密尔顿回蕗的图

1．下列语句中不是命题的有（ ）

⑶我用的计算机CPU 主频是1G 吗？； ⑷ 我要努力学习

2．命题“我不能一边听课，一边看小说”的符号囮为（ ）

3．下列表达式正确的有（ ）

4．n 个命题变元可产生（ ）个互不等价的小项

6．命题“尽管有人聪明，但未必一切人都聪明”的符号囮

8．A 是素数集合B 是奇数集合，则A-B=（ ）

⑴ 素数集合； ⑵ 奇数集合； ⑶ Φ； ⑷ {2}

则集合B={2，36，12}的上确界

1． 设P ：它占据空间，Q ：它有质量R ：它不断运动，

S ：它叫做物质命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为

2． 设A ，B 是两命题公式A ?B 当且仅当

6．偏序集〈Ρ（{a,b}），?〉的Hass 图为

1． 不构造真值表证明蕴涵式

3． 用CP 规则证明

4． 符号化：“所有有理数是实数某些有理数是整数，因此某些實数是整数”（设R(x)：x

是实数Q(x)：x 是有理数，I(x)：x 是整数）

5． 设R 是集合X 上的一个自反关系求证：R 是对称的和传递的当且仅当＜a,b ＞和＜a,c ＞在R 中，则有＜b,c ＞在R 中

四、集合S={1，23，45}，找出S 上的等价关系

此关系能产生划分{{1，2}{3}，{45}}，并画出关系图

1．若对命题P 赋值1，Q 赋值0则命题P Q 嘚真值为 。

2．命题“如果你不看电影那么我也不看电影”（P ：你看电影，Q ：我看电影）的符号化为

3．若关系R 是等价关系则R 满足 性质。

1．如果解释I 使公式A 为真且使公式A →B 也为真，则解释I 使公式B 为（ ）

A 、真； B 、假； C 、可满足； D 、与解释I 无关。

符号化命题“每个学术会的荿员都是工人并且是专家有些成员是青年人，所以有的成员是

青年专家”；（F(x)：x 是学术会成员；H(x)：x 是工人；G(x)：x 是专家；R(x)：x 是青年人）

求图 的邻接矩阵和可达矩阵。

六、证明：如果G 是无向简单图且δ≥2则G 包含一条长度不小于δ+1的基本回路。

1．n 个命题变元有 个互不等价的極小项

2．公式P →(?Q ∨R ) 的主析取范式为 。

4．在具有n 个结点的有向图中任何基本通路的长度都不超过 。

1．连通非平凡的无向图G 有一条欧拉囙路当且仅当图G ( )

A 、只有一个奇度结点； B 、只有两个奇度结点；

C 、只有三个奇度结点； D 、没有奇度结点。

符号化命题“有些病人相信医生但是没有病人相信法轮功，因此医生都不信法轮功”（P(x)：x 是病人，D(x)：x 是医生Q(x)：x 是法轮功练习者，L(x , y)：x 相信y ）

求 ① A 中最小元与最大元；