当前位置：文档库 › 数理逻辑期末考试抢先版

数理逻辑期末考试抢先版

数理逻辑期末考试试卷抢先版

1、求公式?(?(p→q)) ∨(?q→?p)的合取范式。10分

解：?(?(p→q)) ∨ (?q→?p)?(p→q) ∨ (p→q) ? (p→q)

??p∨q

2、前提：p→(q→r)，p∧q 结论：?r→s 10分

证明：①p→(q→r)

②?p∨ (?q∨r) ? p∧q→r

③p∧q

④r

⑤r ∨s

⑥?? r∨s

⑦?r→s

3、前提：?x(F(x) →?G(x))，?x(G(x) ∨H(x))，?x?H(x) 结论：?x?F(x) 10分

证明：①?x(F(x) →?G(x))

②F(y) →?G(y)

③?x(G(x) ∨H(x))

④G(y) ∨H(y)

⑤?G(y) →H(y)

⑥F(y) →H (y)

⑦?H(y) →?F (y)

⑧?H(y) →?x ?F (x)

⑨?x?H(x) →?x ?F (x)

⑩?x?H(x)

⑾?x ?F (x)

4、单调不动点的概念及证明10分

设S是有n+1个原书的集合{S0，S1，…,Sn}。若F：P（S）→P（S）是单调函数，则F n+1(@)是F的最小不动点，而F n+1(S)是F的最大不动点。

证明：见书本159页。

5、直接判断EG,EU,AF,AG等算子的

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

离散数学形成性考核作业（四）数理逻辑部分本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第6章命题逻辑 1．判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题．（1）8能被4整除．（2）今天温度高吗？（3）今天天气真好呀！（4）6是整数当且仅当四边形有4条边．（5）地球是行星．（6）小王是学生，但小李是工人．（7）除非下雨，否则他不会去．（8）如果他不来，那么会议就不能准时开始．解：此题即是教材P.184习题6（A）1 （1）、（4）、（5）、（6）、（7）、（8）是命题，（2）、（3）不是命题。其中（1）、（5）是简单命题，（4）、（6）、（7）、（8）是复合命题。 2．翻译成命题公式（1）他不会做此事．（2）他去旅游，仅当他有时间．（3）小王或小李都会解这个题．（4）如果你来，他就不回去．（5）没有人去看展览．（6）他们都是学生．（7）他没有去看电影，而是去观看了体育比赛．（8）如果下雨，那么他就会带伞．解：此题即是教材P.184习题6（A）2

会带伞。：如果下雨，那么他就：他会带伞。：天下雨。）（。是去观看了体育比赛。：他没有去看电影，而。：他去观看了体育比赛：他去看电影。）（：他们都是学生。）（：没有人去看展览。：有人去看展览。）（去。：如果你来，他就不回：他回去。：你来。）（道题。：小王或小李都会解这：小李会解这道题。：小王会解这道题。）（时间。：他去旅游，仅当他有：他有时间。：他去游泳。）（：他不会做此事。：他会做此事。）（Q P Q P Q P Q P P P P Q P Q P Q P Q P Q P Q P P P →∧???→∧→?87654321 3．设P ，Q 的真值为1；R ，S 的真值为0，求命题公式(P ∨Q )∧R ∨S ∧Q 的真值．解：此题即是教材P.184习题6（A ）4（2） (P ∨Q )真值为1，(P ∨Q )∧R 真值为0，S ∧Q 真值为0，从而(P ∨Q )∧R ∨S ∧Q 真值为0。 4．试证明如下逻辑公式（1） ┐（A ∧┐B ）∧（┐B ∨C ）∧┐C ? ┐（A ∨C ）（2） (P →Q )∧(Q →R )∧┐R ??P （此题即是教材P.185习题6（A ）5（1）、（4）） ) 7() () 8()6)(5()7()4)(2()6()4)(3()5()4()3()1() 2()() 1()(), (),(由由由由由证明：结论：前提：T B A T B A T A T B P C P C B T B A P B A B A C C B B A ∨??∧????∨?∨??∧?∨??∨??∧? ) 4)(3() 5()4()2)(1()3() 2() 1(), (),(由由证明：结论：前提：T P P R T R P P R Q P Q P P R R Q Q P ??→→→??→→

集合论与图论试题A

本试卷满分90分（06级计算机、信息安全专业、实验学院）一、判断对错（本题满分10分，每小题各1分）（正确画“√”，错误画“×”） 1．对每个集合A ，A A 2}{∈。（×） 2．对集合Q P ,，若?==Q P Q Q P ,，则P =?。（√） 3．设,,:X A Y X f ?→若)()(A f x f ∈，则A x ∈。（×） 4．设,,:Y B Y X f ?→则有B B f f ?-))((1。（×） 5．若R 是集合X 上的等价关系，则2R 也是集合X 上的等价关系。（√） 6．若:f X Y →且f 是满射，则只要X 是可数的，那么Y 至多可数的。（√） 7．设G 是有10个顶点的无向图，对于G 中任意两个不邻接的顶点u 和v, 均有9deg deg ≥+v u ，则G 是哈密顿图。（×） 8．设)(ij a A =是 p 个顶点的无向图G 的邻接矩阵，则对于G 的顶点i v , 有∑==p j ij i a v 1deg 成立。（√） 9. 设G 是一个),(q p 图，若1-≥p q ，则]/2[)(q p G ≤χ。（×） 10．图G 和1G 同构当且仅当G 和1G 的顶点和边分别存在一一对应关系。（×）

二.填空(本题40分，每空各2分) 1．设}},{,{φφ=S 则=S 2 }}}{,{}},{{},{,{φφφφφ 。 2．设B A ,是任意集合，若B B A =\，则A 与B 关系为 φ==B A 。 3．设1)(,0)()(,:};3,2{},1,0{},,,{===→===c f b f a f Y X f Z Y c b a X , 3)1(,2)0(,:==→g g Z Y g ,则)()(c f g a f g ，分别为 2，3 。 4．设X 和Y 是集合且X m =，Y n =，若n m ≤，则从X 到Y 的单射的个数为 !m C m n 。 5．设}2,1{},,,2,1{==B n X ，则从X 到Y 的满射的个数为 22-n 。 6．设)}2,4(),1,3(),3,2{()},4,3(),2,2(),2,1{(},4,3,2,1{===S R X ，则 =)(R S R )}2,3(),4,2(),4,1{( 。 7．设???? ??=???? ??=5123454321,415235432121σσ，则???? ??=235411234521σσ 。 8. 设)},(),,(),,{(},,,,{a c c b b a R d c b a X ==，则 )},(),,(),,(),,(),,(),,(),,(),,(),,{(b c a c a b c b c a b a c c b b a a R =+ 。 9. 设X 为集合且X n =，则X 上不同的自反或对称的二元关系的个数为 22222222n n n n n n +--+- 。 10．设}}{},{},,{{},,,,{d c b a A d c b a X ==是X 的一个划分，则由A 确定的 X 上的等价关系为 )},(),,(),,(),,(),,(),,{(d d c c a b b a b b a a 。 11．}10,,2,1{ =S ，在偏序关系“整除”下的极大元为 6，7，8，9，10 。 12．给出一个初等函数)(x f ，使得它是从)1,0(到实数集合R 的一一对应，这个函数为 x ctg π或-x ctg π或)2/(ππ-x tg 。 13. 设G 是),(p p 连通图，则G 的生成树的个数至多为 p 。

离散数学期末测试卷I及答案

离散数学期末测试卷I及答案第一部分、考试形式和时间答题时限：120 分钟考试形式：闭卷笔试第二部分、考试题型和得分构成一、选择题：对每一道小题,从其4个备选答案中选择最适合的一项,每小题2分,共10 道小题,20分。二、填空题：每空1分,共5道小题,10个空白处待填,10分。三、判断题：每一道小题均以陈述语句描述,对的打√,错的打х。每小题1分,共10 道小题,10分。四、综合题：每小题10分,共6道小题,60分。第三部分、考试复习范围一、选择题 1．含n个元素的集合A的幂集的元素个数为多少？答案：2n个。 2．数理逻辑的创始人是谁？

答案：莱布里茨。 3．设(R,+,?)是环,它有哪些特性？答案：1.(R,+)是阿贝尔群。2.(R,?)是半群。3.?对+可分配。 4．排中律满足哪些性质？答案：A ∧ 不成立。（不应同时否认一个命题（A ）及其否定（非A ）） x （F （x ）∨F （x ））对任何个体x 而言,x 有性质F 或没有性质F 。 5．什么是真命题？命题“如果雪是黑的,则1+1=0”是真命题吗？答案：真值为真的命题为真命题。命题“如果雪是黑的,则1+1=0”是真命题！解析：p:雪是黑的；q:1+1=0;如果雪是黑的,则1+1=0:p →q 。由于p 为假,所以无论的真值如何,“p →q ”的真值都为真。 6. 下列哪个等价公式有错？ A ．P Q Q P →?→； B ．P Q P Q →??∨； C ．P Q Q P →??∨；答案：A 7. 设G 为4阶有向图,度数列为（3,4,2,3）,若它的入度列为（1,2,2,1）, 则出度列为哪项？ A ．（1,2,1,2）； B ．（2,2,0,2）； C ．（2,1,1,2）．答案：B 解析：有向图中：度数=出度数+入度数。 8. 设{}{},3,4,S a φ=,则表示空元素属于S 怎样写？答案:?∈S 9. 什么是前束范式？下面哪个是前束范式？ A

形式逻辑-课后习题-答案(含原题)

第四章简单命题及其推理一、下列命题是哪种直言命题？请指出命题的主项、谓项、联项、量项及主谓项的周延情况。 1．共产党员是无产阶级先进分子。答：这是个全称肯定命题（A），全称肯定量项省略；“共产党员”是主项；“是”为联项；“无产阶级先进分子”是谓项。主项周延，谓项不周延。 2．任何困难都不是不可克服的。答：这是个全称否定命题（E）。全称量项“任何”；主项“困难”；联项“不是”；谓项为负概念“不可克服的”。其主项、谓项都周延。 3．有些图书是线装书。答：这是特称肯定命题（I）。量项“有些”；主项“图书”；联项“是”；谓项“线装书”。其主项、谓项均不周延。 4．《女神》是郭沫若的诗集。答：这是个单称肯定命题。《女神》是主项；“是”是联项；“郭沫若的诗集”是谓项。其主项周延，谓项不周延。 5．有些学生不刻苦。答：这个命题一般理解为O命题：有些学生不是刻苦的。“学生”是主项；“刻苦的”是谓项；“不是”是联项；“有些”是量项。其主项不周延，谓项周延。二、下列对当关系推理是否有效？为什么？ 1．由“有的植物不开花”真，推知“所有植物都开花”假。答：正确。因为O与A是矛盾关系，由O真可推知A假。 2．由“凡环境污染都对人身体有害”真，推知“有的环境污染不对人身体有害”假。答：正确。因为A与O是矛盾关系，由A真可推知O假。 3．由“有人生而知之”假，推知“有人不是生而知之”真。答：正确。I与O是下反对关系，由I假可推知O真。 4．由“有的大学生是有理想的”真，推知“所有大学生都是有理想的”假。答：不正确。I与A是从属（差等）关系，由I真推不出A假。 5．由“所有的古代散文都不押韵”假，推知“有的古代散文押韵”真。答：正确。E与I是矛盾关系，由E假可推知I真。 6．由“所有的新诗都不押韵”假，推知“所有新诗都押韵”真。答：不正确。E与A是反对关系，由E假推不出A真。三、根据命题的对当关系，由已知下列命题的真假，断定同素材的其它三种命题的真 1．已知“某单位职工都买了电冰箱”为假。答：这是个A命题。当A假时，同素材的E命题“某单位职工都没买电冰箱”真假不定；I命题“某单位职工有的买了电冰箱”真假不定；O命题“某单位有的职工没买电冰箱”为真。 2．已知“某班同学都不是会打桥牌的”为真。答：这是个E命题。当E真时，A命题“某班同学都是会打桥牌的”为假；I命题“某班同学有的是会打桥牌的”为假；O命题“某班同学有的不是会打桥牌的”为真。 3．已知“有的科学家是自学成才的”为真。答：这是个I命题。当I真时，A命题“所有的科学家是自学成才的”可真可假；E命题“所有的科学家不是自学成才的”为假；O命题“有的科学家不是自学成才的”可真可假。 4．已知“有的教授不是懂外语的”为假。答：这是个O命题。当O假时，A命题“所有的教授都是懂外语的”为真；E命题“所有的教授都不是懂外语的”为假；I命题“有的教授是懂外语的”为真。四、根据命题的对当关系，选择相应的命题来确定下列命题的虚假。 1．所有青年都是积极向上的。答：有的青年不是积极向上的。 2．有的理论是检验真理的标准。答：任何理论都不是检验真理的标准。

数理逻辑考试题及答案

“离散数学”数理逻辑部分考核试题答案 ━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━ 一、命题逻辑基本知识（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分）（0）求公式p→((q∧r) ∧(p∨(q∧r)))的主析取范式。解：p→((q∧r) ∧(p∨(q∧r)))p∨(q∧r∧p) ∨(q∧r∧q∧r) p∨(q∧r∧p) ∨0 (p∧q∧r) ∨ (p∧1∧1) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨m7 (p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨m7 m0∨m1∨m2∨m3∨m7. （1）求公式((p→q)) ∨(q→p)的主合取范式。解：((p→q)) (q→p) (p→q) (p→q) (p→q) p q M2.

北大集合论与图论往年考题.pdf

一、用真值表证明德*摩根律（证明其中一条即可）。二、设A,B,C是集合，试问在什么条件下(A-B)-C=A-(B-C)？给出证明。三、设A={a,b,c}，问A上有多少种不同的：二元关系？自反关系？对称关系？传递关系？等价关系？偏序关系？良序关系？四、用花括号和空集来表示1?2（注意?表示集合的叉乘）. 五、设R是实数集，Q是有理数集，试构造出R-Q与R之间的双射. 1．简单叙述构造的思路； 2．给出双射f：R-Q -> R 或f：R -> R-Q的严格定义。 2008年期末考题：一、在有向图中，如果存在从顶点u到顶点v的有向通路，则说u可达v；如果顶点u和顶点v互相可达，则说u双向可达v。回答下列问题： 1．顶点集上的可达关系是不是等价关系？为什么？ 2．顶点集上的双向可达关系是不是等价关系？为什么？ 3．对于上述两个关系，如果是等价关系，其等价类的导出子图称为什么？二、一棵树有13个顶点，除了3个2度顶点和若干个树叶之外，其余顶点都是5度。 1．求出5度顶点的个数（写出计算过程）； 2．画出所有互不同构的这种树。三、计算出右图中v1到v4长度为4的通路数（要写出计算过程的主要步骤），并写出一个最小支配集、一个最大团、一个最小边覆盖、一个最大匹配。四、如果一个图中所有顶点度数都为k，则称为k正则图。8阶3 正则简单图一定是平面图吗？一定不是平面图吗？为什么？五、证明：如果正则简单图G和补图G都是连通图，则G和G中至少有一个是欧拉图。六、证明：如果n阶（n≥3）简单图G中，对于任何1≤j,<2,3>,<3,2>, <3,4>}. (1) 给出R的矩阵表示, 画出R的关系图; (2) 判断R具有哪些关系性质(自反,反自反,对称,反对称,传递); (3) 求出R的自反闭包r(R), 对称闭包s(R), 传递闭包t(R). (用关系图表示) 三、设X,Y,Z是任意集合, 构造下列集合对之间的双射, 并给出是双射的证明. (1) Z(X?Y)与(Z X)Y ; (2) P(X?Y) 与P(X)?P(Y). (假设X?Y=?) 四、已知对每个自然数n, 都存在唯一后继n+=n?{n}. 证明: 对于每个非零自然数n, 都存在唯一前驱n-, 满足n=(n-)+. 五、设f: A→B是单射, g: B→A是单射, 证明: 存在集合C,D,E,F, 使得A=C?D, C?D=?, B=E?F, E?F=?, 并且f(C)=E, g(F)=D.

暨南大学离散数学周密试卷数理逻辑与集合论—参考试卷

暨南大学考试试卷一、填空题（共10小题，每小题2分，共20分） 1. 设命题 p ：罗素悖论的真值为假，q ：暨南大学的校训是信敏廉毅，r ：离散数学是计算机科学不可分割的一门基础课程，则复合命题: ()()()()() p q r q p r p ?∧?∨∧???→∨的真值为 ; 2. 下列各式中为永真式的有： (1) Q Q P P →→∧))(( (2) Q Q P →→)( (3) )(Q P P ∨→ (3) Q Q P P →∨∧?))(( (5) )(Q P Q ∧→

3. A 是个10元集合，B 是个2元集合，则集合A B 中元素的个数为 4. 设M(x)：x 是人，C(x)：x 很聪明，则命题：“尽管有人很聪明，但未必一切人都聪明。”可符号化为： 5. 设R(x)：x 是实数；L(x, y)：x 小于y ，则谓词公式： (()(()(,)))x R x y R y L x y ?→?∧用自然语言表述就是： 6. 设个体域为A={a, b, c}，消去公式()()xP x xQ x ?→?中的量词得到的与之等值的谓词公式为： 7. P(A)表示集合A 的幂集，则((()))P P P ? = 8. ())(B A B B A ?-??= 9. 设D 为同一平面上直线的集合，并且 // 表示两直线的平行关系，⊥表示两直线间的垂直关系，则 20// ＝，21⊥＝ 10.设 {}c ,b ,a A =，{} ,,,A R a b b a I =<><>?是A 上的等价关系, 设自然映射,R /A A :g →,那么()=a g 二、简答题（共4小题，每小题6分，共24分） 1.(1)求公式()()?∨?→??P Q P Q 的主析取式（要有过程）；（4分） (2)根据主析取式直接写出该公式的主合取式；（2分）

数理逻辑测试题

玛氏食品 ( 中国 ) 有限公司姓名：武英杰性别：男 1-25 题均为选择题，只有一个正确答案。答案写在( ) 内 1-6 题根据下列数字规律，选择( )内应填数字： ( B ) 1、 2，9，16，23，30，（） A.35 B.37 C.39 D.41 ( C ) 2、 5，11，20，32，（） A ．43 B ．45 C ．47 D ．49 ( C )3、 1，2，3，5，（），13 A 9 B 11 C 8 D7 ( A )4、 5，7，（），19，31，50 A 12 B 13 C 10 D11 ( C )5、 8，4，2，2，（） A 、2 B 、3 C 、4 D 、5 ( C)6、 14，20，29，41，( ) A.45 B.49 C.56 D.72 ( A ) 7、. 15.025.053÷?的值是： A ．1 B ．1.5 C ．1.6 D ．2.0 ( C ) 8、 1994年第二季度全国共卖出汽车297600辆，与上年同期相比增长了 24%。上年同期卖出多少辆汽车?

A．714224 B．226176 C．240000 D．369024 ( D ) 9、甲、乙两地相距42公里，A、B两人分别同时从甲乙两地步行出发， A的步行速度为3公里/小时，B的步行速度为4公里/小时，问A、B步行几小时后相遇？ A. 3 B. 4 C. 5 D. 6 ( A)10、一根绳子长40米，将它对折剪断；再对剪断；第三次对折剪断，此时每根绳子长多少米？ A、5 B、10 C、15 D、20 ( B ) 11、如果一米远栽一棵树，则285米远可栽多少棵树？ A、285 B、286 C、287 D、284 (B ) 12、在一本300页的书中，数字“1”在书中出现了多少次？ A、140 B、160 C、180 D、120 ( D ) 13、自然数A、B、 C、 D的和为90，已知A加上2，B减去2，C乘以 2，D除以2之后所得结果相同，则B等于（） A、26 B、24 C、28 D、22 ( B ) 14、某人工作一年的报酬是18000元和一台全自动洗衣机,他干了7个月, 得到9500和一台全自动洗衣机,问这台洗衣机值多少元? A.8500元 B.2400元 C.2000元 D.1700元 ( B ) 15、橱窗：商品；相当于 A 电影：明星 B 书架：书籍 C 宇宙：星球 D 餐馆：厨师

离散数学集合论部分测试题

离散数学集合论部分综合练习本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y∈A}，则R 的性质为（）． A．自反的B．对称的 C．传递且对称的D．反自反且传递的 8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b∈A , 且a +b = 8}，则R具有的性质为（）． A．自反的B．对称的 C．对称和传递的D．反自反和传递的 9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个． A．0 B．2 C．1 D．3 10．设集合A={1 , 2 , 3 , 4}上的二元关系 R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，