离散数学之命题逻辑考试参考答案2

华南理工大学网络教育学院《离散数学》练习题参考答案第一章命题逻辑一填空题（1)设：p：派小王去开会。

q：派小李去开会.则命题：“派小王或小李中的一人去开会" 可符号化为：（p q) (p q）。

（2）设A,B都是命题公式，A B，则A B的真值是T。

（3）设:p：刘平聪明。

q：刘平用功。

在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：p q .（4）设A , B 代表任意的命题公式，则蕴涵等值式为A B A B。

（5）设，p：径一事;q：长一智。

在命题逻辑中,命题:“不径一事，不长一智。

" 可符号化为： p q 。

（6）设A , B 代表任意的命题公式，则德摩根律为（A B）Û A B）。

（7）设，p：选小王当班长;q：选小李当班长.则命题：“选小王或小李中的一人当班长。

”可符号化为: （p q）（p q） .（8）设，P：他聪明；Q：他用功。

在命题逻辑中，命题:“他既聪明又用功。

" 可符号化为：P Q .（9）对于命题公式A,B,当且仅当 A B 是重言式时，称“A蕴含B”，并记为A B。

（10)设:P：我们划船.Q:我们跑步.在命题逻辑中，命题:“我们不能既划船又跑步.”可符号化为：（P Q) 。

（11）设P，Q是命题公式,德·摩根律为：（P Q）P Q) 。

（12）设P:你努力.Q：你失败。

在命题逻辑中，命题：“除非你努力，否则你将失败。

”可符号化为：P Q .（13）设p：小王是100米赛跑冠军。

q:小王是400米赛跑冠军。

在命题逻辑中，命题：“小王是100米或400米赛跑冠军.”可符号化为：p q。

（14）设A，C为两个命题公式，当且仅当A C为一重言式时,称C可由A逻辑地推出。

二．判断题1.设A，B是命题公式，则蕴涵等值式为A B A B。

（）2.命题公式p q r是析取范式。

( √ )3.陈述句“x + y > 5”是命题。

《离散数学》试题及答案 2《离散数学》试题及答案2一、填空题1设子集a,b，其中a＝{1,2,3},b={1,2},则a-b＝____________________;?(b)＝__________________________.2.设有限集合a,|a|=n,则|?(a×a)|=__________________________.3.设子集a={a,b},b={1,2},则从a至b的所有态射就是_______________________________________,其中双射的就是__________________________.4.已知命题公式g＝?(p?q)∧r，则g的主析取范式是_________________________________________________________________________________________.5.设g就是全然二叉树，g存有7个点，其中4个叶点，则g的总度数为__________，分枝点数为________________.6设a、b为两个集合,a={1,2,4},b={3,4},则从a?b＝_________________________;a?b＝_________________________;a－b＝_____________________.7.设r就是子集a上的等价关系，则r所具备的关系的三个特性就是______________________,________________________,______________________________ _.8.设命题公式g＝?(p?(q?r))，则使公式g为真的解释有__________________________，_____________________________,__________________________.9.设子集a＝{1,2,3,4},a上的关系r1={(1,4),(2,3),(3,2)},r1={(2,1),(3,2),(4,3)},则r1?r2=________________________,r2?r1=____________________________,r12=________________________.(a)-10.设有限集a,b，|a|=m,|b|=n,则||?(a?b)|=_____________________________.11设a,b,r是三个集合，其中r是实数集，a={x|-1≤x≤1,x?r},b={x|0≤x<2,x?r},则a-b=__________________________,b-a=__________________________,a∩b=__________________________,.13.设子集a＝{2,3,4,5,6}，r就是a上的相乘，则r以子集形式(列出法)记作__________________________________________________________________.14.设一阶逻辑公式g=?xp(x)??xq(x)，则g的前束范式是_______________________________.15.设g就是具备8个顶点的树，则g中减少_________条边就可以把g变为全然图。

《离散数学》试题带答案试卷九试题与答案一、 填空 30% （每空 3分）1、 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 。

2、 集合A={Φ,{Φ}}的幂集P (A) = 。

3、 设A={1，2，3，4}，A 上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图。

4、 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},则B A ⋃= 。

B A = 。

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

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

7、 偏序集><≤R A ,的哈斯图为，则≤R = 。

8、 设|X|=n ，|Y|=m 则（1）从X 到Y 有 个不同的函数。

（2）当n , m 满足 时，存在双射有 个不同的双射。

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

10、Q ：我将去上海，R ：我有时间，公式)()(Q R R Q →∧→的自然语言为 。

11、公式)()(Q P P Q ∧⌝∧→的 主合取范式是 。

12、 若} ,, , {21m S S S S =是集合A 的一个分划，则它应满足 。

二、 选择 20% （每小题 2分）1、 设全集为I ，下列相等的集合是（ ）。

A 、} |{是偶数或奇数x x A =；B 、)}2( |{y x I y y x B =∧∈∃=；C 、)}12( |{+=∧∈∃=y x I y y x C ；D 、},4,4,3,3,2,2,1,1,0|{ ----=x D 。

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

A 、S S N N ∈∈∈2 ,2则； B 、S N S Q Q N ⊂∈⊂则 ,； C 、R N R Q Q N ⊂⊂⊂则 ,； D 、S N S N ⋂⊂Φ⊂Φ⊂Φ则 ,。

“离散数学”数理逻辑部分考核试题答案━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━一、命题逻辑基本知识（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题。

第一章命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.7.因为p与q不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0(4)（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。

并且，如果3是无理数，则2也是无理数。

另外6能被2整除，6才能被4整除。

第二章作业 评分要求：1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分2. 给出每小题得分(注意: 写出扣分理由)3. 总得分在采分点1处正确设置.一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):说明证1. p ⇔(p ∧q)∨(p ∧¬q)解逻辑方程法设 p ↔((p ∧q)∨(p ∧¬q)) =0, 分两种情况讨论:⎩⎨⎧=⌝∧∨∧=0)()(1)1(q p q p p 或者 ⎩⎨⎧=⌝∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ↔(p ∧q)∨(p ∧¬q)无成假赋值, 为永真式.等值演算法(p ∧q)∨(p ∧¬q)⇔ p ∧(q ∨¬q)∧对∨的分配率⇔ p ∧1 排中律⇔ p 同一律真值表法用真值表法和解逻辑方程法证明相当于证明为永真式1. (¬p→q)→(¬q∨p)解(¬p→q)→(¬q∨p)⇔(p∨q)→(¬q∨p)蕴含等值式⇔(¬p∧¬q)∨(¬q∨p)蕴含等值式, 德摩根律⇔(¬p∧¬q)∨¬q ∨p结合律⇔p∨¬q吸收律, 交换律⇔M1因此, 该式的主析取范式为m0∨m2∨m32. (¬p→q)∧(q∧r)解逻辑方程法设(¬p→q)∧(q∧r) =1, 则¬p→q=1且q∧r=1,解得q=1, r=1, p=0 或者q=1, r=1, p=1, 从而所求主析取范式为m3∨m7, 主合取范式为M0∧M1∧M2∧M4∧M5∧M6等值演算法(¬p→q)∧(q∧r)⇔ (p∨q)∧(q∧r) 蕴含等值式⇔ (p∧q∧r)∨(q∧r) ∧对∨分配律, 幂等律⇔ (p∧q∧r) ∨ (p∧q∧r)∨(⌝p∧q∧r) 同一律, 矛盾律, ∧对∨分配律⇔m7∨ m3主合取范式为M0∧M1∧M2∧M4∧M5∧M63. (p↔q)→r解逻辑方程法设(p↔q)→r =0, 解得p=q=1, r=0 或者p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析取范式为m1∨m2∨m3∨m4∨m5∨m7等值演算法(p↔q)→r⇔ ((p→q)∧(q→p))→r 等价等值式⇔⌝((p→q)∧(q→p))∨r 蕴含等值式⇔ (p∧⌝q)∨(q∧⌝p)∨r 德摩根律, 蕴含等值式的否定(参见PPT)⇔ (p∨q∨r)∧(⌝q∨⌝p∨r) ∨对∧分配律, 矛盾律, 同一律⇔M0∧ M6主析取范式为m1∨m2∨m3∨m4∨m5∨m74. (p→q)∧(q→r)解等值演算法(p→q)∧(q→r)⇔ (⌝p∨q)∧(⌝q∨r) 蕴含等值式⇔ (⌝p∧⌝q)∨(⌝p∧r)∨(q∧r) ∧对∨分配律, 矛盾律, 同一律⇔ (⌝p∧⌝q∧r)∨(⌝p∧⌝q∧⌝r) ∨ (⌝p∧q∧r)∨(⌝p∧⌝q∧r) ∨ (p∧q∧r)∨(⌝p∧q∧r)⇔m1∨ m0∨ m3∨ m7主合取范式为M2∧ M4∧ M5∧ M6.解逻辑方程法设(p → q) ∧ (q → r) = 1, 则p → q =1 且q → r =1.前者解得: p=0, q=0; 或者p=0, q=1; 或者p=1, q=1.后者解得: q=0, r=0; 或者q=0, r=1; 或者q=1, r=1.综上可得成真赋值为000, 001, 011, 111, 从而主析取范式为m0∨ m1∨ m3∨ m7, 主合取范式为M2∧ M4∧ M5∧ M6.真值表法公式(p → q) ∧ (q从而主析取范式为m0∨ m1∨ m3∨ m7, 主合取范式为M2∧ M4∧ M5∧ M6.。

离散数学考试题目及答案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）算法。

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

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

Page 49 第17题解：（1）令①P：李明学习努力；②Q：李明成绩好；③R：李明不热衷于玩扑克；（2）已知条件符号化，即①P→Q：如果李明学习努力，那么他成绩好；②R→P：如果李明不热衷于玩扑克，那么他就努力学习；（3）所求结论符号化，即①¬Q→¬R：李明成绩不好，所以李明热衷于玩扑克；（4）证明：原命题符号化为P→Q，R→P ¬Q→¬R；①P→Q P规则；②R→P P规则；③R→Q T规则①②；④Q∨¬R T规则③；⑤¬Q→¬R T规则④；（5）得证。

Page 50 第32题（2）解： P∨(¬P→(Q∨(¬Q→R)))；⇔ P∨(P∨(Q∨(Q∨R)))；⇔P∨Q∨R；①主合取范式为：P∨Q∨R；因为 P∨Q∨R ⇔∏M0 ⇔∑m1,2,3,4,5,6,7；②主析取范式为：∨(¬P∧¬Q∧R)∨(¬P∧Q∧¬R)∨(¬P∧Q∧R)∨(P∧¬Q∧¬R)∨(P∧¬Q∧R)∨(P∧Q∧¬R)∨(P∧Q∧R)；Page 50 第32题（4）解： (P∧¬Q∧R)∨(¬P∧Q∧¬S)；⇔ ((P∧¬Q∧R)∧(S∨¬S))∨((¬P∧Q∧¬S)∧(R∨¬R))；⇔(P∧¬Q∧R∧S)∨(P∧¬Q∧R∧¬S)∨(¬P∧Q∧R∧¬S)∨(¬P∧Q∧¬R∧¬S)；①主析取范式为：(¬P∧Q∧¬R∧¬S)∨(¬P∧Q∧R∧¬S)∨(P∧¬Q∧R∧¬S)∨(P∧¬Q∧R∧S) ⇔∑m4,6,10,11⇔∏M0,1,2,3,5,7,8,9,12,13,14,15；②主合取范式为：(¬P∨¬Q∨¬R∨¬S)∧(¬P∨¬Q∨¬R∨S)∧(¬P∨¬Q∨R∨¬S) ∧(¬P∨¬Q∨R∨S)∧(¬P∨Q∨¬R∨S)∧(¬P∨Q∨R∨S)∧(P∨¬Q∨¬R∨¬S) ∧(P∨¬Q∨¬R∨S)∧(P∨Q∨¬R∨¬S)∧(P∨Q∨¬R∨S)∧(P∨Q∨R∨¬S)∧(P∨Q∨R∨S)；Page 50 第32题（6）解： (P→Q)→(P∨R)；⇔¬(¬P∨Q)∨(P∨R)；⇔(P∧¬Q)∨(P∨R)；⇔(P∨R)∧(P∨¬Q∨R)；⇔ ((P∨R)∨(¬Q∧Q))∧(P∨¬Q∨R)；⇔(P∨¬Q∨R)∧(P∨Q∨R)∧(P∨¬Q∨R)；⇔(P∨¬Q∨R)∧(P∨Q∨R)；①主合取范式为：(P∨¬Q∨R)∧(P∨Q∨R)；⇔∏M0,2；⇔∑m1,3,4,5,6,7；①主合取范式为：(¬P∨¬Q∨R)∧(¬P∨Q∨R)∧(P∨¬Q∨¬R)∧(P∨¬Q∨R)∧(P∨Q∨¬R)∧(P∨Q∨R)；Page 51 第37题（2）解： P→Q P→(P∧Q)①P P规则（附加前提）；②P→Q P规则；③Q T规则①，②，I；④P∧Q T规则①，③，I；⑤P→(P∧Q) CP规则；Page 51 第37题（4）解： (P∨Q)→R ⇒ (P∧Q)→R①P∧Q P规则（附加前提）；②P T规则①，I；③P∨Q T规则②，I；④(P∨Q)→R P规则；⑤R T规则③，④，I；⑥(P∧Q)→R CP规则；Page 51 第38题（3）解：﹁(P→Q)→﹁(R∨S),((Q→P)∨﹁R),R ⇒ P↔Q①﹁(P↔Q) P规则（假设前提）；②﹁((P→Q)∧(Q→P)) T规则①，I；③R P规则；④((Q→P)∨﹁R) P规则；⑤R→(Q→P) T规则④，I；⑥(Q→P) T规则③⑤，I；⑦R∨S T规则③，I；⑧﹁(P→Q)→﹁(R∨S) P规则；⑨(R∨S)→(P→Q) T规则⑧，I；⑩(P→Q) T规则⑦⑨，I；⑪(P→Q)∧(Q→P) T规则⑥⑩，I；⑫得证间接证明法②⑪；Page 51 第39题（1）解：（1）符号化已知命题①P：明天是晴天；②Q：明天下雨；③R：我去看电影；④S：我不看书；条件符号化：P∨Q，P→R，R→S；结论符号化：①﹁S→Q（2）证明：P∨Q，P→R，R→S ⇒﹁S→Q①P→R P规则；②R→S P规则；③P→S T规则①②；④﹁S→﹁P T规则③，I；⑤P∨Q P规则；⑥﹁P→Q T规则⑤，I；⑦﹁S→Q T规则④⑥，I；Page 51 第39题（2）解：（1）符号化已知命题①P：明天不下雨；②Q：能够买到车票；③R：我去参观计算机展览会；条件符号化：P∧Q→R；结论符号化：①﹁R→﹁P（2）证明：P∨Q，P→R，R→S ⇒﹁S→Q①P∧Q→R P规则；②﹁R P规则（附加前提）；③﹁(P∧Q) T规则①②；④﹁P∨﹁Q T规则③，I；⑤也就是说或者明天下雨或者买不到票，所以原命题说不能参加计算机展览的原因只是明天下雨是不完全的，故原命题无效。