离散数学数理逻辑部分考试试题

“离散数学”数理逻辑部分考核试题答案━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━一、命题逻辑基本知识（5分）1、将下列命题符号化(总共4题，完成的题号为学号尾数取4的余，完成1题。

共2分）(0）小刘既不怕吃苦，又爱钻研.解：⌝p∧q，其中,P：小刘怕吃苦；q:小刘爱钻研.(1）只有不怕敌人,才能战胜敌人.解：q→⌝p，其中，P：怕敌人；q：战胜敌人。

（2）只要别人有困难,老张就帮助别人,除非困难已经解决了。

解：⌝r→(p→p），其中，P:别人有困难；q：老张帮助别人;r:困难解决了.（3）小王与小张是亲戚。

解：p，其中，P：小王与小张是亲戚。

2、判断下列公式的类型(总共5题,完成的题号为学号尾数取5的余，完成1题.共1分）（0)A:（⌝（p↔q）→（（p∧⌝q）∨(⌝p∧q））)∨ r(1）B：（p∧⌝(q→p)) ∧（r∧q)（2）C：（p↔⌝r）→（q↔r)（3）E:p→（p∨q∨r)(4）F：⌝（q→r) ∧r解:用真值表判断，A为重言式,B为矛盾式，C为可满足式，E为重言式,F为矛盾式。

3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。

共2分）(0)设y=2｜x|，x为实数。

推理如下:如y在x=0处可导，则y在x=0处连续。

发现y在x=0处连续,所以，y在x=0处可导。

解：设y=2|x｜，x为实数.令P:y在x=0处可导,q：y在x=0处连续。

由此，p为假，q为真。

本题推理符号化为：(p→q）∧q→p。

由p、q的真值，计算推理公式真值为假,由此，本题推理不正确。

（1）若2和3都是素数，则6是奇数。

2是素数,3也是素数.所以，5或6是奇数。

解：令p:2是素数,q：3是素数，r：5是奇数，s：6是奇数。

由此，p=1，q=1,r=1，s=0.本题推理符号化为：((p ∧ q) →s）∧p ∧q) →（r ∨ s)。

计算推理公式真值为真,由此，本题推理正确.二、命题逻辑等值演算(5分)1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。

离散数学试题及答案一、单项选择题（每题2分，共20分）1. 在集合论中，空集的表示符号是（）。

A. {0}B. ∅C. {}D. Ø答案：B2. 如果A和B是两个集合，那么A∩B表示（）。

A. A和B的并集B. A和B的交集C. A和B的差集D. A和B的补集答案：B3. 命题逻辑中，p ∧ q的真值表中，当p和q都为假时，p ∧ q的值为（）。

A. 真B. 假C. 不确定D. 无定义答案：B4. 在图论中，如果一个图中的任意两个顶点都由一条边相连，则称这个图为（）。

A. 连通图B. 无向图C. 完全图D. 有向图答案：C5. 布尔代数中，逻辑或运算符表示为（）。

A. ∧B. ∨C. ¬D. →答案：B6. 一个关系R是从集合A到集合B的二元关系，如果对于A中的每个元素x，B中都存在唯一的元素y与之对应，则称R为（）。

A. 单射B. 满射C. 双射D. 单满射答案：C7. 在命题逻辑中，如果p是假命题，那么¬p的值为（）。

A. 真B. 假C. 不确定D. 无定义答案：A8. 一个有向图是无环的，那么它一定是（）。

A. 有向无环图B. 无向无环图C. 有向有环图D. 无向有环图答案：A9. 在集合论中，如果集合A是集合B的子集，那么A⊆B表示（）。

A. A包含于BB. A是B的真子集C. A是B的超集D. A与B相等答案：A10. 命题逻辑中，p → q的真值表中，当p为真，q为假时，p → q 的值为（）。

A. 真B. 假C. 不确定D. 无定义答案：B二、多项选择题（每题3分，共15分）1. 在集合论中，以下哪些符号表示的是集合的并集（）。

A. ∪B. ∩C. ⊆D. ⊂答案：A2. 在图论中，以下哪些说法是正确的（）。

A. 有向图可以是无环的B. 无向图可以是无环的C. 有向图一定是连通的D. 无向图一定是连通的答案：A B3. 在命题逻辑中，以下哪些符号表示的是逻辑与（）。

页眉内容《离散数学》试题及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2），（3），（4），（5），（6）4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）PP⌝P→⌝↔（4）QQ→⌝（2）QP⌝→（3）Q8、设个体域为整数集，则下列公式的意义是( )。

(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：(1) ∀x∃y (xy=y) ( ) (2) ∃x∀y(x+y=y) ( )(3) ∃x∀y(x+y=x) ( ) (4) ∀x∃y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

《离散数学》题库及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答：（1），（4）2、下列公式中哪些是永真式？()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P答：（2），（3），（4），（5），（6）4、公式某((A(某)B(y，某))zC(y，z))D(某)中，自由变元是(变元是()。

答：某,y,某,z5、判断下列语句是不是命题。

若是，给出命题的真值。

((1)北京是中华人民共和国的首都。

(2)陕西师大是一座工厂。

)，约束)(3)你喜欢唱歌吗？(4)若7+8＞18，则三角形有4条边。

(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为()。

(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：（1）QP（2）PQ（3）PQ（4）PQ8、设个体域为整数集，则下列公式的意义是()。

(1)某y(某+y=0)(2)y某(某+y=0)答：（1）对任一整数某存在整数y满足某+y=0（2）存在整数y对任一整数某满足某+y=09、设全体域D是正整数集合，确定下列命题的真值：(1)某y(某y=y)()(2)某y(某+y=y)()(3)某y(某+y=某)()(4)某y(y=2某)()答：（1）F（2）F（3）F（4）T10、设谓词P(某)：某是奇数，Q(某)：某是偶数，谓词公式某(P(某)Q(某))在哪个个体域中为真()2(1)自然数(2)实数(3)复数(4)(1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

第1章 命题逻辑一、单项选择题1. 下列命题公式等值的是( ) BB A A Q P Q Q P Q B A A B A A QP Q P ),()D (),()C ()(),()B (,)A (∧∨⌝∨∨⌝∨→→→⌝→→∨⌝∧⌝2. 设命题公式G ：)(R Q P ∧→⌝,则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A (3. 命题公式Q Q P →∨)(为 ( ) (A) 矛盾式(B) 仅可满足式 (C) 重言式 (D) 合取范式4 命题公式)(Q P →⌝的主析取范式是( )． (A) Q P ⌝∧ (B) Q P ∧⌝ (C) Q P ∨⌝ (D) Q P ⌝∨ 5. 前提条件P Q P ,⌝→的有效结论是( )． (A) P(B)P(C) Q(D)Q6. 设P ：我将去市里，Q ：我有时间．命题“我将去市里，仅当我有时间时”符号化为( )Q P Q P Q P PQ ⌝∨⌝↔→→)D ()C ()B ()A (二、填空题1. 设命题公式G ：P⌝(Q P )，则使公式G 为假的真值指派是2. 设P ：我们划船，G ：我们跑步，那么命题“我们不能既划船，又跑步”可符号化为3. 含有三个命题变项P ，Q ，R 的命题公式P Q 的主析取范式是4. 若命题变元P ，Q ，R 赋值为(1,0,1)，则命题公式G ＝)())((Q P R Q P ∨⌝↔→∧的真值是5. 命题公式P⌝P Q 的类型是 ．6. 设A ，B 为任意命题公式，C 为重言式，若C B C A ∧⇔∧，那么B A ↔是式(重言式、矛盾式或可满足式)三、解答化简计算题1. 判别下列语句是否命题如果是命题，指出其真值.(1) 中国是一个人口众多的国家. (2) 存在最大的质数.(3) 这座楼可真高啊！ (4) 请你跟我走! (5) 火星上也有人.2.作命题公式))(()(P Q P Q P ∨∧→→的真值表，并判断该公式的类型．3. 试作以下二题：(1) 求命题公式(PQ )(P Q )的成真赋值．(2) 设命题变元P ,Q ,R 的真值指派为(0,1,1),求命题公式))()(()(Q R Q P R P →⌝∨→⌝∧↔的真值．4. 化简下式命题公式))()((P Q P Q P ∧⌝∧⌝∨∧5. 求命题公式))()((Q P P Q P ∧⌝∧→→的主合取范式.6. 求命题公式)()(Q P Q P ⌝→∧→⌝的主析取范式，并求该命题公式的成假赋值．7. 求命题公式)()(Q P Q P ⌝∨⌝∧∧的真值表. 四、证明题1. 证明S S P R R Q Q P ⌝⇒⌝∨∧⌝∧∨⌝∧→)()()(2. 构造推理证明：S R Q P R S Q P →⇒∧→∧→→)())((3. 证明命题公式)()(Q R Q P →∨→与Q R P →∧)(有相同的主析取范式．参考答案一、1. C 2. D 3. B 4. A 5. D 6. B二、1. 1,0；1,1 2. )(Q P ∧⌝或Q P ⌝∨⌝ 3. (P Q R )(P QR )4. 05. 非永真式的可满足式6. 重言 三、1. (1) 是命题，真值为1.(2) 是命题，真值为0. (3), (4)不是命题. (5) 是命题.1. 判别下列语句是否命题如果是命题，指出其真值.(1) 中国是一个人口众多的国家. (2) 存在最大的质数.(3) 这座楼可真高啊！ (4) 请你跟我走! (5) 火星上也有人.2. 命题公式))(()(P Q P Q P ∨∧→→的真值表 P Q P Q Q P ∧P Q P ∨∧)())(()(P Q P Q P ∨∧→→0 0 1 0 0 0 0 1 1 0 0 0 1111 1 1 1 1 1 原式为可满足式.3. (1) (P Q )(P Q )(P Q )(P Q )(P P )Q Q可见(PQ )(P Q )的成真赋值为(0,1)，(1,1)．(2) ))()(()(Q R Q P R P →⌝∨⌝→⌝∧↔0))10()01(()10(⇔→∨→∧↔⇔4.))()((P Q P Q P ∧⌝∧⌝∨∧P Q P Q P ∧⌝∧⌝∨∧⇔)()()()(P P Q P Q P ∧⌝∧⌝∨∧∧⇔0)(∨∧⇔Q PQ P ∧⇔5. ))()((Q P P Q P ∧⌝∧→→ ))()((Q P P Q P ∧⌝∧∨⌝∨⌝⇔)())(Q P P Q P Q P ∧⌝∧∨∧⌝∧⌝∨⌝⇔ )00(∧∨⌝⇔P )(Q Q P ⌝∧∨⌝⇔)()(Q P Q P ⌝∨⌝∧∨⌝⇔6. )()()()(Q P Q P Q P Q P ⌝∨⌝∧⌝∧⇔⌝→∧→⌝ Q P ⌝∧⇔因为成真赋值是（1，0），故成假赋值为（0，0），（0，1），（1，1）7. 作真值表PQ P QPQPQ (P Q )(PQ ) 0 0 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 111四、证明题1. 证明S S P R R Q Q P ⌝⇒⌝∨∧⌝∧∨⌝∧→)()()( ①Q R P②R P③Q T ①，②析取三段论 ④P Q P ⑤P ⌝ T ③，④拒取式 ⑥PS P⑦S ⑤，⑥析取三段论 2. 构造推理证明：S R Q P R S Q P →⇒∧→∧→→)())((.前提：Q P R S Q P ,)),((→→→ 结论：S R → 证明：① R附加前提② RP前提引入 ③ P①，②假言推理④P (Q S ) 前提引入 ⑤ Q S ③,④假言推理 ⑥ Q 前提引入⑦ S⑤,⑥假言推理3. 证明命题公式)()(Q R Q P →∨→与Q R P →∧)(有相同的主析取范式． 证明.方法1．)()(Q R Q P →∨→)()(Q R Q P ∨⌝∨∨⌝⇔∨∧⌝⇔Q R P )(Q R P →∧)(因为两命题公式等值，由主合取范式的惟一性，可知两命题公式的主合取范式是相同． 3 证明命题公式)()(Q R Q P →∨→与Q R P →∧)(有相同的主析取范式．方法2．)()(Q R Q P →∨→)()(Q R Q P ∨⌝∨∨⌝R Q P Q R P ⌝∨∨⌝⇔∨⌝∨⌝⇔ R Q P Q R P Q R P ⌝∨∨⌝⇔∨⌝∨⌝⇔→∧)(因为它们的主合取范式相同，可知它们的主析取范式也相同．第2章谓词逻辑一、 单项选择题1. 谓词公式)())()((x Q y yR x P x →∃∨∀中量词x 的辖域是( ) (A) ))()((y yR x P x ∃∨∀ (B) P (x ) (C) )()(y yR x P ∃∨ (D) )(x Q2. 谓词公式∃xA (x )∧∃xA (x )的类型是（ ）(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 不属于(A ),(B ),(C )任何类型 3 设个体域为整数集，下列公式中其真值为1的是( )(A) )0(=+∃∀y x y x (B) )0(=+∀∃y x x y(C))0(=+∀∀y x y x (D) )0(=+∃⌝∃y x y x4 设L (x )：x 是演员，J (x )：x 是老师，A (x ,y )：x 佩服y. 那么命题“所有演员都佩服某些老师”符号化为( ) (A) ),()(y x A x xL →∀ (B) ))),()(()((y x A y J y x L x ∧∃→∀ (C) )),()()((y x A y J x L y x ∧∧∃∀ (D) )),()()((y x A y J x L y x →∧∃∀5. 设个体域是整数集合，P 代表x y ((x y )(x y 0))，下面4个命题中为真的是( )(A) P 是真命题 (B) P 是逻辑公式，但不是命题 (C) P 是假命题 (D) P 不是逻辑公式6. 表达式))(),(())(),((z zQ y x R y z Q y x P x ∀→∃∧∨∀中x ∀的辖域是( )(A) P (x ,y ) (B)R (x ,y ) (C)P (x ,y )R (x ,y ) (D) P (x ,y )Q (z )二、 填空题1. 设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ∀∨∃消去量词后的等值式为 .2. 设个体域D ＝{a ,b },公式)),()((y x yH x G x ∃→∀消去量词化为3. 设N (x )：x 是自然数，Z (y )；y 是整数，则命题“每个自然数都是整数，而有些整数不是自然数”符号化为参考答案一、1. C ；2.. B ；3 A ；4. B ；5. A 6. D二、1. A (1)A (2)(B (1)B (2)) 2. (G (a )(H (a ,a )H (a ,b ))) (G (b )(H (b ,a )H (b ,b )))3. ))()(())()((x N x Z x x Z x N x ⌝∧∃∧→∀。

离散数学考试题及答案一、选择题（每题5分，共20分）1. 下列哪个选项不是离散数学的研究对象？A. 图论B. 组合数学C. 微积分D. 逻辑学答案：C2. 在逻辑学中，下列哪个命题是真命题？A. 如果今天是周一，那么明天是周二。

B. 如果今天是周一，那么明天是周三。

C. 如果今天是周一，那么明天是周四。

D. 如果今天是周一，那么明天是周五。

答案：A3. 在集合论中，下列哪个符号表示集合的并集？A. ∩B. ∪C. ⊆D. ⊂答案：B4. 在图论中，下列哪个术语描述的是图中的顶点集合？A. 边B. 路径C. 子图D. 顶点答案：D二、填空题（每题5分，共20分）1. 如果一个集合A包含5个元素，那么它的子集个数是______。

答案：322. 在逻辑学中，如果命题P和命题Q都是真命题，那么复合命题“P且Q”的真值是______。

答案：真3. 在图论中，如果一个图的顶点数为n，那么它的最大边数是______。

答案：n(n-1)/24. 如果一个二叉树的深度为3，那么它最多包含______个节点。

答案：7三、简答题（每题10分，共30分）1. 请简述什么是图的连通性，并给出一个例子。

答案：图的连通性是指在图中任意两个顶点之间都存在一条路径。

例如，在一个完全图K3中，任意两个顶点之间都可以通过一条边直接连接，因此它是连通的。

2. 解释什么是逻辑蕴含，并给出一个例子。

答案：逻辑蕴含是指如果一个命题P为真，则另一个命题Q也必须为真。

例如，命题P：“如果今天是周一”，命题Q：“明天是周二”。

如果今天是周一，那么根据逻辑蕴含，明天必须是周二。

3. 请描述什么是二叉搜索树，并给出它的一个性质。

答案：二叉搜索树是一种特殊的二叉树，其中每个节点的左子树只包含小于当前节点的数，右子树只包含大于当前节点的数。

它的一个性质是中序遍历可以得到一个有序序列。

四、计算题（每题15分，共30分）1. 给定一个集合A={1, 2, 3, 4, 5}，请计算它的幂集，并列出所有元素。

数理逻辑测验一．将下列命题符号化（有量词的用谓词符号，没有的用命题符号）1. 没有不犯错误的人。

2. 金子是闪光的，但闪光的不一定是金子。

3．每个人或者喜欢乘汽车，或者喜欢骑自行车。

4．我虽然生病但我仍然去学校。

5．仅当你走，我将留下。

二．令),,(z y x S 表示“x+y=z”,),(y x G 表示“x=y”,),(y x L 表示”x<y”, 其中个体域为自然数集，用以上符号表示命题：（1） 并非对一切x ，都存在y ，使得y x ≤。

（2） （2）对任意的x ，若x+y=x ，当且仅当y=0。

三．简答题1． 写出R Q P →→)(的析取范式，合取范式。

2． 设P ：今天下雨。

Q ：我去上街。

R ：我有空。

用自然语言表达以下命题：)(P R Q ⌝∧↔，)(Q R ∨⌝。

3． 设Q P ,的真值为0，S R ,的真值为1，求以下命题的真值：（1）)()(S R Q P∨⌝∧↔，（2）)()))(((S R P R QP ⌝∨→⌝∧→∨⌝。

4．n 个原子命题变元12,,,n P P P L 可构成多少个互不等值的命题公式？5． 写出谓词公式 )),()()()(()),()()((z y Q z y P y y x Q x P x ∃∧∃→→∀的前束范式。

四．证明题1．)()(R P Q R Q P→→⇔→→。

2．Q P Q Q P∨⇒→→)(。

3．)()())()((y yQ x xP y Q x P y x ∀→∃⇔→∀∀。

五．计算题a) 求公式)()(Q P Q P ⌝↔→⌝∨⌝的主析取范式，主合取范式。

b) 设12:>P ；3:)(≤x x Q ；6:)(≥x x R ；5=a 。

而且论域为{-2，3，6}，求)())()((a R x Q Px ∨→∀的值。

六．用形式推理证明 （1）S Q P S R Q R Q P →⇒→→∨⌝∨⌝),(),(（2）(()(()())),()(()())x P x Q x R x xP x x P x R x ∀→∧∃⇒∃∧七．符号化下列命题，并用推理理论证明其结论是否有效。

离散数学考试题目及答案1. 试述命题逻辑中的等价关系和蕴含关系。

答案：命题逻辑中的等价关系是指两个命题在所有可能的真值赋值下都具有相同的真值。

若命题P和Q等价，则记作P⇔Q。

蕴含关系是指如果命题P为真，则命题Q也为真，但Q为真时P不一定为真。

若命题P蕴含Q，则记作P→Q。

2. 证明：若集合A和B的交集非空，则它们的并集包含A和B。

答案：设x属于A∩B，即x同时属于A和B。

根据并集的定义，若元素属于A或B，则它属于A∪B。

因此，x属于A∪B。

由于x是任意属于A∩B的元素，所以A∩B≠∅意味着A∪B至少包含A∩B中的所有元素，即A∪B包含A和B。

3. 给定一个有向图G，如何判断G中是否存在环？答案：判断有向图G中是否存在环，可以采用深度优先搜索（DFS）算法。

在DFS过程中，记录每个顶点的访问状态，如果遇到一个已访问过的顶点，且该顶点不是当前路径的直接前驱，则表示存在环。

4. 描述有限自动机的组成部分及其功能。

答案：有限自动机由以下几部分组成：输入字母表、状态集合、转移函数、初始状态和接受状态集合。

输入字母表定义了自动机可以接收的符号集合；状态集合包含了自动机所有可能的状态；转移函数定义了在给定输入符号和当前状态的情况下，自动机如何转移到下一个状态；初始状态是自动机开始工作时的状态；接受状态集合包含了所有使自动机接受输入字符串的状态。

5. 什么是图的连通分量？如何确定一个无向图的连通分量？答案：图的连通分量是指图中最大的连通子图。

在一个无向图中，如果两个顶点之间存在路径，则称这两个顶点是连通的。

确定无向图的连通分量可以通过深度优先搜索（DFS）或广度优先搜索（BFS）算法。

从任一顶点开始搜索，搜索过程中访问的所有顶点构成一个连通分量。

重复此过程，直到所有顶点都被访问过，即可确定图中所有连通分量。

离散数学试题及答案解析一、选择题1. 在集合{1,2,3,4}中，含有3个元素的子集有多少个？A. 4B. 8C. 16D. 32答案：B解析：含有3个元素的子集可以通过组合数公式C(n, k) = n! / [k!(n-k)!]来计算，其中n为集合的元素个数，k为子集中的元素个数。

在本题中，n=4，k=3，所以C(4, 3) = 4! / [3!(4-3)!] = 4。

2. 下列哪个命题是真命题？A. 所有偶数都是整数。

B. 所有整数都是偶数。

C. 所有整数都是奇数。

D. 所有奇数都是整数。

答案：A解析：偶数是指能被2整除的整数，因此所有偶数都是整数，选项A是真命题。

选项B、C和D都是错误的，因为并非所有整数都是偶数或奇数。

二、填空题1. 逻辑运算符“非”（NOT）的真值表是：当输入为真时，输出为______；当输入为假时，输出为真。

答案：假解析：逻辑运算符“非”（NOT）是一元运算符，它将输入的真值取反。

如果输入为真，则输出为假；如果输入为假，则输出为真。

2. 命题逻辑中，合取词“与”（AND）的真值表是：当两个命题都为真时，输出为真；否则输出为______。

答案：假解析：合取词“与”（AND）是二元运算符，只有当两个命题都为真时，输出才为真；如果其中一个或两个命题为假，则输出为假。

三、简答题1. 解释什么是等价关系，并给出一个例子。

答案：等价关系是定义在集合上的一个二元关系，它满足自反性、对称性和传递性。

例如，考虑整数集合上的“同余”关系。

对于任意整数a，b，如果a和b除以同一个正整数n后余数相同，则称a和b模n同余。

这个关系是自反的（a同余a），对称的（如果a同余b，则b同余a），并且是传递的（如果a同余b且b同余c，则a同余c）。

2. 什么是图的连通性？一个图是连通的需要满足什么条件？答案：图的连通性是指在无向图中，任意两个顶点之间都存在一条路径。

一个图是连通的需要满足以下条件：图中的任意两个顶点v和w，都可以通过图中的边相互到达。