离散数学作业标准答案

离散数学作业一、选择题1、下列语句中哪个就是真命题(C )。

A.我正在说谎。

B.如果1+2=3,那么雪就是黑色的。

C.如果1+2=5,那么雪就是白色的。

D.严禁吸烟！2、设命题公式))((r q p p G →∧→=,则G 就是( C )。

A 、 恒假的B 、 恒真的C 、 可满足的D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ∃∀→中的变元x ( C )。

A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>}B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>}C.R={<1,1>,<2,2>,<3,3>,<1,4>}D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>,<3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。

A.单射而非满射B.满射而非单射C.双射D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D )b b b a a a b a * a b b b a a b a *8( A )A B C D 9、下列各组数中,能构成无向图的度数列就是( D ) A.1,1,1,2,4 B.1,2,3,4,5 C.0,1,0,2,4 D.1,2,3,3,510、一棵树有2个4度顶点,3个3度顶点,其余都就是树叶,则该树中树叶的个数就是( B )A 、8B 、9C 、 10D 、 11 11、“所有的人都就是要死的。

数理逻辑习题判断题1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →⌝→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧⌝∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →∃=→∀ （ √ ）6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ）8．))()((x G x F x →∀是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ∃→∀是永真式（ √ ）11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ）13．))()((x G x F x →∀是永假式 （ × ）14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨⌝ （ × ） 18．命题公式 )(r q p →∨⌝的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →∀是闭式（ × ）单项选择题1． 下述不是命题的是（ A ）A．花儿真美啊! B．明天是阴天。

C．2是偶数。

D．铅球是方的。

2．谓词公式（∀y）（∀x）（P（x）→R（x,y））∧∃yQ（x,y）中变元y （B）A．是自由变元但不是约束变元B．是约束变元但不是自由变元C．既是自由变元又是约束变元D．既不是自由变元又不是约束变元3．下列命题公式为重言式的是（ A ）A．p→ （p∨q）B．（p∨┐p）→qC．q∧┐q D．p→┐q4．下列语句中不是．．命题的只有（A ）A．花儿为什么这样红？B．2+2=0C．飞碟来自地球外的星球。

《离散数学》题库及标准答案《离散数学》题库及答案————————————————————————————————作者：————————————————————————————————日期：《离散数学》题库与答案一、选择或填空（数理逻辑部分）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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。

在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。

若是，给出命题的真值。

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

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

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

1-1，1-2（1） 解：a) 是命题，真值为T。

b) 不是命题。

c) 是命题，真值要根据具体情况确定。

d) 不是命题。

e) 是命题，真值为T。

f) 是命题，真值为T。

g) 是命题，真值为F。

h) 不是命题。

i) 不是命题。

（2） 解：原子命题：我爱北京天安门。

A（3） 解：a) (┓P ∧R)→Qb) Q→Rc) ┓Pd) P→┓Q（4） 解：a)设Q:我将去参加舞会。

R:我有时间。

P:天下雨。

Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。

b)设R:我在看电视。

Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。

c) 设Q:一个数是奇数。

R:一个数不能被2除。

（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。

(5) 解：a) 设P：王强身体很好。

Q：王强成绩很好。

P∧Qb) 设P：小李看书。

Q：小李听音乐。

P∧Qc) 设P：气候很好。

Q：气候很热。

P∨Qd) 设P： a和b是偶数。

Q：a+b是偶数。

P→Qe) 设P：四边形ABCD是平行四边形。

Q ：四边形ABCD的对边平行。

PQf) 设P：语法错误。

Q：程序错误。

R：停机。

（P∨ Q）→ R(6) 解：a) P:天气炎热。

Q:正在下雨。

P∧Qb) P:天气炎热。

R:湿度较低。

P∧Rc) R:天正在下雨。

S:湿度很高。

R∨Sd) A:刘英上山。

B:李进上山。

A∧Be) M:老王是革新者。

N:小李是革新者。

M∨Nf) L:你看电影。

M:我看电影。

┓L→┓Mg) P:我不看电视。

Q:我不外出。

R:我在睡觉。

P∧Q∧Rh) P:控制台打字机作输入设备。

Q:控制台打字机作输出设备。

P∧Q1-3（1）解：a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b) 是合式公式c) 不是合式公式（括弧不配对）d) 不是合式公式（R和S之间缺少联结词）e) 是合式公式。

（2）解：a） A是合式公式，(A∨B)是合式公式，(A→(A∨B)) 是合式公式。

离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是p q∧（9）只有天下大雨，他才乘班车上班解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p →（11）下雪路滑，他迟到了解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r∧→15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起.求下列复合命题的真值：（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→解：p=1，q=1，r=0，，()(110)1p q r ∧∧⌝⇔∧∧⌝⇔(())((11)0)(00)1p q r ⌝∨⌝→⇔⌝∨⌝→⇔→⇔()(())111p q r p q r ∴∧∧⌝↔⌝∨⌝→⇔↔⇔19、用真值表判断下列公式的类型：（2）()p p q→⌝→⌝解：列出公式的真值表，如下所示：p qp⌝q⌝()p p →⌝()p p q→⌝→⌝001111011010100101110001由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。

20、求下列公式的成真赋值：（4）()p q q⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒0p q ⇔⎧⎨⇔⎩所以公式的成真赋值有：01，10，11。

习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）()()p q q r ⌝→∧∧解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧，此即公式的主析取范式，()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨所以成真赋值为011，111。

*6、求下列公式的主合取范式，并求成假赋值：（2）()()p q p r ∧∨⌝∨解：原式，此即公式的主合取范式，()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔所以成假赋值为100。

大 连 理 工 大 学课 程 名 称： 离散数学 试 卷： A 授课院 (系)： 软件学院 考试日期： 04 年 1 月 3 日 试卷共 4 页1、 简答下列各问(每小题2分共20分)1） 一个可满足的公式一定是永真式。

一个永真式一定是可满足的。

哪一句为真？ 后一句为真2） 一个偏序一定是一个全序。

一个全序一定是一个偏序。

哪一句为真？ 后一句为真3） 一个划分一定是一个覆盖。

一个覆盖一定是一个划分。

哪一句为假？ 后一句为假4） 同余关系一定是等价关系。

等价关系一定是同余关系，哪一句为真？ 前一句为真5） Y 盖复x ，则一定有x ≤y 。

若x ≤y ，则一定有Y 盖复x 。

哪一句为假？（≤为偏序）后一句为假 6） 一个单射、满射函数一定是一个双射函数。

一个双射函数一定是一个满射函数？哪一句为假？都不为假7） 一个分配格一定是一个布尔代数。

一个布尔代数一定是一个分配格。

哪一句为假？前一句为假8） 设T=<n,m>是一棵具有n 个结点m 条边的树，试给出结点n 和边m 的关系式： m =n-19） 设R 是集合X 中的二元关系，试给出R 的对称闭包:s( R)=R ⋃R10） 数理逻辑中介绍了哪8条推理规则？P 、T 、CP 、F 、UG 、US 、EG 、ES 规则姓名：学号： 院系： 级 班装订线2、 试证在完全二元有向树中，边的总数为2（n t –1）.其中n t 为树叶数。

（6分）证明：因为是完全二元树，所以每个结点的度数为2或0。

设度数为2的结点数为n 2 ,于是边数为m=2 n 2. 在树中边数m 和结点数n 有关系式 m=n-1即2 n 2.= n 2+n t -1而n= n 2+ n t 由上式得：m=n 2+ n t -1=m/2+ n t -1 整理得：m=2（n t –1）.3、 若无向树T 有两个顶点度为2，一个顶点度为3，3个顶点度为4，则T 有几片树叶？（6分）证明：设无向树有n 个结点，于是n=n 2+n 3+n 4+n t （1）其中：n 2，n 3， n 4 ，n t 分别代表度为2，为3，为4及叶结点。

《离散数学》试题及标准答案解析⼀、填空题1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝ __________________________ .2. 设有限集合A, |A| = n, 则 |ρ(A×A)| = __________________________.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.4. 已知命题公式G＝?(P→Q)∧R，则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)}, R2= {(2,1),(3,2),(4,3)}, 则R1?R2 = ________________________,R2? R1 =____________________________, R12 =________________________.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的前束范式是__________________________ _____.16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________.17. 设集合A＝{1, 2, 3, 4}，A上的⼆元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。