[标签:标题]
篇一:离散数学习题答案-2015
离散数学习题答案
习题一
1、利用逻辑联结词把下列命题翻译成符号逻辑形式
(1)他既是本片的编剧,又是导演--- P ∧Q (2)银行利率一降低,股价随之上扬--- P →Q (3)尽管银行利率降低,股价却没有上扬--- P ∧Q (4)占据空间的、有质量而且不断变化的对象称为物质--- M ??(S∧P∧T) (5)他今天不是乘火车去北京,就是随旅行团去了九寨沟--- P ▽Q
(6)小张身体单薄,但是极少生病,并且头脑好使--- P ∧Q ∧R (7)不识庐山真面目,只缘身在此山中--- P →Q
(解释:因为身在此山中,所以不识庐山真面目)
(8)两个三角形相似,当且仅当他们的对应角相等或者对应边成比例
--- S ??(E∨T)
(9)如果一个整数能被6整除,那么它就能被2和3整除。如果一个整数能被3整除,那么它的各位数字之和也能被3整除
解:设P –一个整数能被6整除Q –一个整数能被2整除R –一个整数能被3整除S –一个整数各位数字之和能被3整除翻译为:(P →(Q ∧R))∧(R →S)2、判别下面各语句是否命题,如果是命题,说出它的真值
(1)BASIC语言是最完美的程序设计语言--- Y,T/F (2)这件事大概是小王干的--- N (3)x2 = 64--- N (4)可导的实函数都是连续函数--- Y,T/F (5)我们要发扬连续作战的作风,再接再厉,争取更大的胜利--- N (6)客观规律是不以人们意志为转移的--- Y,T (7)到2020年,中国的国民生产总值将赶上和超过美国--- Y,N/A (8)凡事都有例外--- Y,F
3、构造下列公式的真值表,并由此判别哪些公式是永真式、矛盾式或可满足式
(1)(P ∨(~P ∧Q))→Q 解:
4、利用真值表方法验证下列各式为永真式
(1)~(8)略
5、证明下列各等价式
(3)P→(Q∨R)? (P →Q)∨(P →R)证明:左式? ~P∨Q∨R
? ~P∨Q∨~P∨R
? (~P∨Q)∨(~P∨R)
? (P →Q)∨(P →R)? 右式
(4)(P∧Q)∨(R∧Q)∨(R∧P)? (P∨Q)∧(R∨Q)∧(R∨P)证明:左式? ((P∨R)∧Q)∨(R∧P)
? ((P∨R)∨R) ) ∧((P∨R)∨P) ) ∧(Q∨R)∧(Q∨P)? (P∨Q)∧(R∨Q)∧(R∨P)? 右式
6、如果P∨Q ? Q∨R,能否断定P ? R ?如果P∧Q ? Q∧R,能否断定P ? R?如果~P ? ~R,能否断定P ? R?
解:(1)如果P∨Q ? Q∨R,不能判断P ? R,因为如果Q = P∨R, 那么P∨Q? P∨P ∨R ? Q∨R,但P可以不等价于R.
(2)如果P∧Q ? Q∧R,不能判断P ? R,因为如果Q = P∧R, 那么P∧Q? P∧P∧R ?
Q∧R,但P可以不等价于R.
(3)如果~P ? ~R,那么有P ? R,因为~P ? ~R,则~P <-> ~R为永真式,及有P <-> R为永真式,所以P ? R.
8、把下列各式用↑等价表示出来
(1)(P∧Q) ∨~P
解:原式? ((P↑Q) ↑(P↑Q)) ∨(P↑P)
? (((P↑Q) ↑(P↑Q)) ↑((P↑Q) ↑(P↑Q))) ↑((P↑P) ↑(P↑P))
9、证明:{ ~→}是最小功能完备集合
证明: 因为{~, ∨}是最小功能完备集合,所以,如果{ ~→}能表示出∨,则其是功能完备集合。由于P ∨Q ? (~P) →Q ,所以{ ~→}是功能完备集合。因为~→不能相互表示,所以{ ~→}是最小功能完备集合;同理可证:{非,条件非}也能将或表示出来:P ∨Q ? ~(~P ! →Q)
8、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:
(3) P→(R∧(Q→P)) 解:真值表法
主合取范式为= (~P∨Q∨R) ∧(~P∨~Q∨R) = M4∧M6
主析取范式为= (~P∧~Q∧~R)∨(~P∧~Q∧R)∨(~P∧Q∧~R)∨(~P∧Q∧R)∨(P ∧~Q∧R)∨(P∧Q∧R) = m0∨m1∨m2∨m3∨m5∨m7 等价变换法(略)
(4) (P→(Q∧R)) ∧(~P→(~Q∧~R)) 解:真值表法
主合取范式为= (P∨Q∨~R) ∧( P∨~Q∨R) ∧( P∨~Q∨~R) ∧(~P∨Q∨R) ∧(~P∨Q∨~R) ∧(~P∨~Q∨R) = M1∧M2∧M3∧M4∧M5∧M6 主析取范式为= (~P ∧~Q∧~R)∨(P∧Q∧R) = m0∨m7 等价变换法(略)
14、从A,B,C,D 4个人中派2人出差,要求满足下列条件:如果A去,则必须在C或D中选一人同去;B和C不能同时去;C和D不能同时去。用构造范式的方法决定选派方案。解:由题设A:A去,B:B去,C:C去,D:D去则满足条件的选派应满足如下范式:(A→(C?D))∧~(B∧C)∧~(C∧D)
构造和以上范式等价的主析取范式(A→(C?D))∧~(B∧C)∧~(C∧D)
?(~A∧~B∧~C ∧D )∨(~A∧~B∧~C∧~D)∨(~A∧~B∧C∧~D)∨(~A∧B∧~C∧~D)∨(A∧~B∧C∧~D)∨(A∧~B∧~C∧D)∨(~A∧B∧~C∧D)∨(A∧B∧~C∧D)
共有八个极小项,但根据题意,需派两人出差,所以,只有其中三项满足要求:(A∧~B ∧C∧~D),(A∧~B∧~C∧D),(~A∧B∧~C∧D)即有三种方案:A和C去或者A 和D去或者B和D去。
15、证明下列蕴含试:
(1)P→Q=>P →(P∧Q)
证明:P→Q ? ~P ∨Q ? T∧(~P ∨Q) ? (~P∨P) ∧(~P ∨Q) ? ~P ∨(P∧Q) ? P →(P∧Q)
所以,这是个等价式,因此也是个蕴含式(2)(P→Q) →Q=> (P∨Q)
证明:(P→Q) →Q ? ~(~P∨Q) ∨Q ? (P∧~Q) ∨Q ? (P∨Q) ∧(Q∨~Q) ? (P∨Q) ∧T ? (P∨Q)
所以,这是个等价式,因此也是个蕴含式(3)P∧~P∧R=>S
证明:P∧~P∧R ? F => S (F可蕴含任何命题公式) (4)P=>Q∨R∨~R
证明:P=>T ? Q∨R∨~R (任何公式可蕴含永真式)
18、一个有钱人生前留下了一笔珍宝,藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下:
(1)如果藏宝的房子靠近池塘,那么珍宝不会藏在东厢房。(2)如果房子的前院栽有大柏树,那么珍宝就藏在东厢房。(3)藏宝房子靠近池塘。
(4)要么前院栽有大柏树,要么珍宝埋在花园正中地下。(5)如果后院栽有香樟树,珍宝藏在附近。请利用蕴含关系找出藏宝处
解:根据给定的条件有下述命题:P:珍宝藏在东厢房Q:藏宝的房子靠近池塘R:房子的前院栽有大柏树S:珍宝藏在花园正中地下T:后院栽有香樟树M:珍宝藏在附近根据题意,得出:
(Q→~P)∧(R→P)∧Q∧(R∨S)∧(T→M)??(Q→~P)∧(R→P)∧Q∧(R∨S)∧(T→M)?~P∧(R→P)∧(R∨S)∧(T→M)?~R∧(R∨S)∧(T →M)?S∧(T→M)
?S 即珍宝藏在花园正中地下
20、演绎证明下面各蕴含式:
(4)(R→Q) ∧(R→S),(Q→E) ∧(S→B), ~(E∧B),(P→R) ? ~P 证明:运用反证方法,将结论的非纳入前提,证明步骤如下[1] P p(附加前提) [2] P→Rp
[3] R T [1,2] I [4] (R→Q) ∧(R→S) p
[5] Q∧ST [3,4] I [6] (Q→E) ∧(S→B) p
[7] E∧BT [5,6] I [8] ~(E∧B) p
[9] F(矛盾式) T [7,8] E
(5)P→(Q→R),Q→(R→S) ? P→(Q→S)
证明:运用cp法,将结论条件式的前件作为前提,证明步骤如下[1] P p(附加前提) [2] P →(Q→R) p
[3] Q→RT [1,2] I [4] Q→(R→S) p
[5] R→(Q→S) T [4] E [6] Q→ST [3,5] I [7] P→(Q→S) CP [1,6]
21、把下列句子演绎成逻辑形式,并给出证明
(2)某公司发生了一起盗窃案,经仔细侦察,掌握了如下一些事实:
? 被盗现场没有留下任何痕迹
? 失盗时,小花或则小英正在卡拉ok厅
? 如果失窃时小胖正在附近,他就会习惯性地破门而入偷走东西后扬长而去? 如果失盗时小花正在卡拉ok厅唱歌,那么金刚是最大的嫌疑者? 如果失盗时小胖不在附近,那么他的女友小英会和他一起外出旅游? 如果失盗时小英正在卡拉ok厅唱歌,那么瘦子是最大的嫌疑者根据以上事实,请通过演绎推理找出偷窃者
解:根据给定的条件有下述命题:P:现场无任何痕迹
Q:失窃时,小花在OK厅R:失窃时,小英在OK厅S:失窃时,小胖在附近T:金刚是偷窃者M:瘦子是偷窃者
则根据案情有如下命题公式:
{P,Q∨R,S→~P,Q→T,~S→~R,R→M}
①P P ②S→~PP
篇二:离散数学最全课后答案(屈婉玲版)
1.1.略
1.2.略
1.3.略
1.4.略
1.5.略
1.6.略
1.7.略
1.8.略
1.9.略
1.10.略
1.11.略
1.12.将下列命题符号化,并给出各命题的真值:
(1)2+2=4当且仅当3+3=6.(2)2+2=
4的充要条件是3+3?6.(3)2+2?4与
3+3=6互为充要条件.(4)若2+2?4, 则
3+3?6,反之亦然.
(1)p?q,其中,p: 2+2=4,q: 3+3=6, 真值为
1.(2)p??q,其中,p:2+2=4,q:3+3=6,真值为0.
(3)?p?q,其中,p:2+2=4,q:3+3=6,真值为
0.(4)?p??q,其中,p:2+2=4,q:3+3=6,真值为1.
1.13.将下列命题符号化, 并给出各命题的真
值:(1)若今天是星期一,则明天是星期二.(2)只有
今天是星期一,明天才是星期二.(3)今天是星期
一当且仅当明天是星期二. (4)若今天是星期一,
则明天是星期三.
令p: 今天是星期一;q:明天是星期二;r:明天是星期三.(1)
p?q ??1.
(2) q?p ??1.
(3) p?q??1.
(4)p?r当p ??0时为真; p ??1时为假.
1.14.将下列命题符号化. (1)
刘晓月跑得快,跳得高.(2)
老王是山东人或河北人.
(3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组.
(5)李辛与李末是兄弟.
(6)王强与刘威都学过法语. (7)他一面吃
饭, 一面听音乐. (8)如果天下大雨,他就乘
班车上班.(9)只有天下大雨,他才乘班车上
班.(10)除非天下大雨,他才乘班车上班.(11)
下雪路滑, 他迟到了.
(12)2与4都是素数,这是不对的.
(13)“2或4是素数,这是不对的”是不对的.
(1)p?q,其中, p:刘晓月跑得快, q: 刘晓月跳得
高.(2)p?q,其中, p:老王是山东人, q: 老王是河北
人.(3)p?q, 其中,p:天气冷, q:我穿了羽绒服.
(4)p, 其中,p:王欢与李乐组成一个小组,是简单命题.(5)p,
其中,p:李辛与李末是兄弟.
(6)p?q,其中, p:王强学过法语, q: 刘威学过法语.(7)p?q,
其中, p:他吃饭,q:他听音乐.
(8)p?q, 其中,p:天下大雨, q:他乘班车上班.
(9)p?q, 其中,p:他乘班车上班, q: 天下大雨.(10)p?q, 其中,p: 他乘班车上班,q:天下大雨.(11)p?q, 其中,p: 下雪路滑, q:他迟到了.
12)??(p?q)或?p??q,其中,p:2是素数,q:4是素
数.(13)???(p?q)或p?q,其中,p:2 是素数,q:4是素数.
1.15.设p:2+3=5.
q: 大熊猫产在中
国.r: 复旦大学在广州.
求下列复合命题的真值:
(1)(p?q)?r(2)(r??(
p?q))???p(3)?r??(
?p??q?r)
(4)(p?q??r)??((?p??q)?r)
(1)真值为0.
(2)真值为0.
(3)真值为0.
(4)真值为1.
注意:p, q是真命题,r是假命题.
1.16.
1.17.
1.18.
1.19.略略略用真值表判断下列公式的类型:(1)p??(p?q?r)
(2)(p??q)??q
(3)??(q?r)?r
(4)(p?q)??(?q??p)
(5)(p?r)??(?p??q)(6)((p?q)
??(q?r))??(p?r)(7)(p?q)
??(r?s)
(1), (4),(6)为重言式.
(3)为矛盾式.
(2), (5),(7)为可满足式.
1.20.
1.21.
1.22.
1.23.
1.24.
1.25.
1.26.
1.27.
1.28.
1.29.
1.30.
1.31.略略略略略略略略略略略将下列命题符号化,并给出各命题的真
值:(1)若3+=4,则地球是静止不动的.
(2)若3+2=4,则地球是运动不止的. (3)若地球
上没有树木,则人类不能生存.
(4)若地球上没有水,则3是无理数.
(1)p?q,其中, p: 2+2=4,q:地球静止不动,真值为0.(2)p?q,
其中, p: 2+2=4,q:地球运动不止,真值为1.
(3)?p??q,其中,p:地球上有树木,q:人类能生存,真值为
1.(4)?p?q,其中,p:地球上有水,q: 3 是无理数,真值为1.
2.1.设公式A=p?q,B=p??q,用真值表验证公式A和B适合德摩根律:
?(A?B)???A??B.
因为?(A?B)和?A??B的真值表相同,所以它们等值.
2.2. 略
2.3. 用等值演算法判断下列公式的类型, 对不是重言式的可满足式,再用真值表法求出成真赋
值.(1)??(p?q?q)
(2)(p??(p?q))??(p?r)
(3)(p?q)??(p?r)
(1)??(p?q?q)????(?(p?q)??q)????(?p???q??q)??p?q??q??p?0??0??0.矛盾式.(2)重言式.
(3) (p?q)??(p?r)???(p?q)??(p?r)???p??q??p?r易见,是可满足式,但不是重言式.成真赋值为:000,001, 101, 111
2.4.用等值演算法证明下面等值
式:(1)p??(p?q)??(p??q)
(3)??(p?q)??(p?q)???(p?q)
(4)(p??q)??(?p?q)??(p?q)???(p?q)
(1)
(p?q)??(p??q)??p??(q??q)??p??1??p.(3)??(p
?q)
???((p?q)??(q?p))
???((?p?q)??(?q?p))
??(p??q)??(q??p)
??(p?q)??(p??p)??(?q?q)??(?p??q)
??(p?q) ???(p?q)
(4)(p??q)??(?p?q)
??(p??p)??(p?q)??(?q??p)??(?q?q)
??(p?q) ???(p?q)
2.5.求下列公式的主析取范式,并求成真赋
值:(1)(?p?q)??(?q?p)
(2)??(p?q)?q?r
(3)(p??(q?r)) ??(p?q?r)
(1)(?p?q)??(?q?p)
???(p?q) ??(?q?p)
???p??q???q??p???p??q???q??p(吸收律)??(p??p)??q??p?(q??q) ??p??q??p??q??p?q??p??q ??m10??m00??m11??m10
??m0??m2??m3
???(0, 2,3).
成真赋值为00,10, 11.
(2)主析取范式为0, 无成真赋值,为矛盾式.(3)m0?m1?m2?m3?m4?m5?m6?m7,为重言式.
2.6.求下列公式的主合取范式, 并求成假赋
值:(1)??(q??p)??p
(2)(p?q)??(?p?r)
(3)(p??(p?q))?r
(1) ??(q??p)???p
???(?q??p)???p
??q?p???p
??q?0
??0
??M0?M1?M2?M3
这是矛盾式.成假赋值为00, 01,10,11.
(2)M4,成假赋值为100.
(3)主合取范式为1, 为重言式.
篇三:离散数学习题答案
离散数学习题答案
习题一及答案:(P14-15)14、将下列命题符号化:
(5)李辛与李末是兄弟
解:设p:李辛与李末是兄弟,则命题符号化的结果是p (6)王强与刘威都学过法语解:设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,
p?q
(p?q??r)?(1?1??0)?1,
((?p??q)?r)?((?1??1)?0)?(0?0)?1 ?(p?q??r)?((?p??q)?r)?1?1?1
19、用真值表判断下列公式的类型:(2)(p??p)??q
解:列出公式的真值表,如下所示:
20、求下列公式的成真赋值:
(4)?(p?q)?q
解:因为该公式是一个蕴含式,所以首先分析它的成假赋值,成假赋值的条件是:
??(p?q)?1?p?0
???
q?0q?0??
所以公式的成真赋值有: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)?m3?m7,此即公式的主析取范式,所以成真赋值为011,111。
*6、求下列公式的主合取范式,并求成假赋值:(2)(p?q)?(?p?r)
解:原式?(p??p?r)?(?p?q?r)?(?p?q?r)?M4,此即公式的主合取范式,所以成假赋值为100。
7、求下列公式的主析取范式,再用主析取范式求主合取范式:(1)(p?q)?r
解:原式?p?q?(?r?r)?((?p?p)?(?q?q)?r) ?(p?q??r)?(p?q?)r ?(?p??q?r)
?(p??q
?(?p?q?)?r(?p?q?)r?(?p)?r(?p
?q?)r?(?p
q?
)?r?(
?q?)r?(?p q?r?
?pq?r?
?m1?m3?m5?m6?m,此即主析取范式。7
主析取范式中没出现的极小项为m0,m2,m4,所以主合取范式中含有三个极大项M0,M2,
M4,故原式的主合取范式?M0?M2?M4。
9、用真值表法求下面公式的主析取范式:
(1)(p?q)?(?p?r) 解:公式的真值表如下:
由真值表可以看出成真赋值的情况有7种,此7种成真赋值所对应的极小项的析取即为主析取范式,故主析取范式?m1?m2?m3?m4?m5?m6?m7
习题三及答案:(P52-54)
11、填充下面推理证明中没有写出的推理规则。前提:?p?q,?q?r,r?s,p 结论:s 证明:
①p 前提引入②?p?q前提引入③q ①②析取三段论④?q?r前提引入
⑤r ③④析取三段论⑥r?s前提引入
⑦s ⑤⑥假言推理
15、在自然推理系统P中用附加前提法证明下面推理:(2)前提:(p?q)?(r?s),(s?t)?u结论:p?u
证明:用附加前提证明法。
①p附加前提引入
②p?q ①附加③(p?q)?(r?s) 前提引入④r?s ②③假言推理⑤s ④化简⑥s?t ⑤附加⑦(s?t)?u前提引入
⑧u ⑥⑦假言推理故推理正确。
16、在自然推理系统P中用归谬法证明下面推理:(1)前提:p??q,?r?q,r??s结论:?p
证明:用归谬法
①p结论的否定引入②p??q前提引入③?q ①②假言推理④?r?q 前提引入
⑤?r③④析取三段论⑥r??s 前提引入⑦r ⑥化简⑧r??r ⑤⑦合取
由于r??r?0,所以推理正确。
17、在自然推理系统P中构造下面推理的证明:
只要A曾到过受害者房间并且11点以前没离开,A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开,看门人会看见他。看门人没有看见他。所以,A是谋杀嫌犯。解:设p:A到过受害者房间,q:A在11点以前离开,r:A是谋杀嫌犯,s:看门人看见过A。则前提:(p??q)?r,p,q?s,?s结论:r 证明:
①q?s 前提引入②?s 前提引入③?q ①②拒取式④p 前提引入
⑤p??q ③④合取引入⑥(p??q)?r 前提引入⑦r⑤⑥假言推理
习题四及答案:(P65-67)
5、在一阶逻辑中将下列命题符号化:(2)有的火车比有的汽车快。
解:设F(x):x是火车,G(y):y是汽车,H(x,y):x比y快;则命题符号化的结果是:
?x?y(F(x)?G(y)?H(x,y))
(3)不存在比所有火车都快的汽车。解:方法一:
设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快;则命题符号化的结果是:
??x(F(x)??y(G(y)?H(x,y)))或?x(F(x)??y(G(y)??H(x,y)))
方法二:
设F(x):x是火车,G(y):y是汽车,H(x,y):x比y快;则命题符号化的结果是:
??x(G(x)??y(F(y)?H(x,y)))或??x?y(G(x)?(F(y)?H(x,y)))
9、给定解释I如下:
(a) 个体域为实数集合R。(b) 特定元素a
?
?
?0。
(c) 函数
f(x,y)?x?y,x,y?R。
?
(d) 谓词F(x,y):x?y,G(x,y):x?y,x,y?R。
?
给出以下公式在I下的解释,并指出它们的真值:
(2)?x?y(F(f(x,y),a)?G(x,y))
解:解释是:?x?y(x?
y?0?x?y),含义是:对于任意的实数x,y,若x-y=0则x<y。
该公式在I解释下的真值为假。
14、证明下面公式既不是永真式也不是矛盾式:(1)?x(F(x)??y(G(y)?H(x,y)))
解:取解释I如下:个体域为全总个体域,
F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快,则该公式在解释I下真值是1;取解释I如下:H(x,y):x比y跑得慢,其它同上,则该公式在解释I下真值是0;
'
'
1. 写出命题公式 ﹁(P →(P ∨ Q ))的真值表。 答案: 2.证明 答案: 3. 证明以下蕴涵关系成立: 答案: 4. 写出下列式子的主析取范式: 答案: 5. 构造下列推理的论证:p ∨q, p →r, s →t, s →r, t q 答案: ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨) ()(Q P Q P Q P ?∧?∨∧??Q) P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)() ()(R P Q P ∨∧∧?
①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明:p →((r ∧s)→q), p, s q 7. 请将下列命题符号化: 所有鱼都生活在水中。 答案: 令 F( x ):x 是鱼 W( x ):x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( x ):x 是有理数 R ( x ):x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化: 尽管有人聪明,但并非一切人都聪明。 答案: 令M(x):x 是人 C(x):x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化: 对于所有的正实数x,y ,都有x+y ≥x 。 答案: 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化: 每个人都要参加一些课外活动。 答案: ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不? (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不? B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
一、选择题:(每题2’) 1、下列语句中不是命题的有( )。 A .离散数学是计算机专业的一门必修课。 B .鸡有三只脚。 C .太阳系以外的星球上有生物 。 D .你打算考硕士研究生吗? 2、命题公式A 与B 是等价的,是指( )。 A . A 与B 有相同的原子变元 B . A 与B 都是可满足的 C . 当A 的真值为真时,B 的真值也为真 D . A 与B 有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为( )。 A . 010,100,101,110,111 B . 010,100,101,111 C . 全体赋值 D . 不存在 4、合式公式 (P∧Q)R 的主析取范式中含极小项的个数为( )。 A .2 B .3 C .5 D .0 5、一个公式在等价意义下,下面哪个写法是唯一的( )。 A .析取范式 B .合取范式 C .主析取范式 D .以上答案都不对 6、下述公式中是重言式的有( )。 A .(P ∧Q) (P ∨Q) B .(P Q) (( P Q)∧(Q P)) C .(P Q)∧Q D .P (P ∧Q) 7、命题公式 (P Q) ( Q ∨P) 中极小项的个数为( ),成真赋值的个数为( )。 A .0 B .1 C .2 D .3 8、若公式 (P∧Q)∨(P∧R) 的主析取范式为 m 001∨m 011∨m 110∨m 111 则它的主合取范式为( )。 A .m 001∧m 011∧m 110∧m 111 B .M 000∧M 010∧M 100∧M 101 C .M 001∧M 011∧M 110∧M 111 D .m 000∧m 010∧m 100∧m 101 9、下列公式中正确的等价式是( )。 A .(x)A(x) ( x)A(x) B .(x) (y)A(x, y) (y) (x) A(x, y) C .(x)A(x) (x)A(x) D .(x) (A(x) ∧B(x)) ( x) A(x) ∨(x) B(x) 10、下列等价关系正确的是( )。 A .x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) B .x ( P(x) ∨Q(x) ) x P(x) ∨x Q(x) C .x ( P(x) Q ) x P(x) Q D . x ( P(x) Q ) x P(x) Q 11、设个体域为整数集,下列真值为真的公式是( )。 A .x y (x·y=1) B .x y (x·y=0) C . x y (x·y=y) D .x y (x+y=2y ) 12、设S={,{1},{1,2}},则有( )S 。 A .{{1,2}} B .{1,2 } C .{1} D .{2} 13、下列是真命题的有( )。 A .{a}{{a}} B .{{}}{,{}} C .{,{}} D .{}{,{}}
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈>∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】
一、填空题 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=(PQ)∧R,则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB= _________________________;AB=_________________________;A-B=_____________________. 7.设R是集合A上的等价关系,则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G=(P(QR)),则使公式G为真的解释有 __________________________, _____________________________,__________________________. 9.设集合A={1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则
离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提:p s r r q q ,,,p →∨?∨? 结论:s 证明:① p 前提引入 ②q ∨?p 前提引入 ③ q (①②析取三段论) ④r q ∨? 前提引入 ⑤ r (③④析取三段论) ⑥s r → 前提引入 ⑦ s (⑤⑥假言推理) 12、填充下面推理证明中没有写出的推理规则。 前提:s)(r q r),(q p →→→→ 结论:s q)(p →∧ 证明:①q)(p ∧ (附加前提) ② p (①化简规则) ③ q (①化简规则) ④r)(q p →→ 前提引入 ⑤r q → (②④假言推理) ⑥ r (③⑤假言推理) ⑦s)(r q →→ 前提引入 ⑧s)(r → (③⑦假言推理) ⑨ s (⑥⑧假言推理) 13、前提:s r ,q p q,q)p (→∨∧→? 结论1:r 结论2:s 结论3:s ∨r (1)证明从此前提出发,推出结论1,结论2,结论3的推理都是正确的。 (2)证明从此前提出发,推任何结论的推理都是正确的。 证明:(1)①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??
②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1,结论2,结论3的推理都是正确的。 (2)s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明: (1)前提:q → p, → (q r) p, r→ 结论:s 证明:①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理: 前提:q → , →s p→ (q p, r) s→ 结论:r 证明: ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法,推理正确。
离散数学课后习题答案(左孝凌版) 1-1,1-2解: a)是命题,真值为T。 b)不是命题。 c)是命题,真值要根据具体情况确定。 d)不是命题。 e)是命题,真值为T。 f)是命题,真值为T。 g)是命题,真值为F。 h)不是命题。 i)不是命题。 (2)解: 原子命题:我爱北京天安门。 复合命题:如果不是练健美操,我就出外旅游拉。 (3)解: a)(┓P ∧R)→Q b)Q→R c)┓P d)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∧Q b)设P:小李看书。Q:小李听音乐。P∧Q c)设P:气候很好。Q:气候很热。P∨Q d)设P: a和b是偶数。Q:a+b是偶数。P→Q e)设P:四边形ABCD是平行四边形。Q :四边形ABCD的对边平行。P Q f)设P:语法错误。Q:程序错误。R:停机。(P∨ Q)→ R (6) 解: a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 (1)解:
常熟理工学院20 ~20 学年第学期 《离散数学》考试试卷(试卷库01卷) 试题总分: 100 分考试时限:120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题(每题2分,共20分) 1.下列表达式正确的有( ) (A)(B)(C)(D) 2.设P:2×2=5,Q:雪是黑的,R:2×4=8,S:太阳从东方升起,下列( )命题的真值为 真。 (A)(B)(C)(D) 3.集合A={1,2,…,10}上的关系R={
1.n个命题变元组成的命题公式共有种不同的等价公式。 2.设〈L,≤〉为有界格,a为L中任意元素,如果存在元素b∈L,使,则称b是a 的补元。 3.设*,Δ是定义在集合A上的两个可交换二元运算,如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4.设T是一棵树,则T是一个连通且的图。 5.一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6.量词否定等价式? ("x)P(x) ?,? ($x)P(x) ?。 7.二叉树有5个度为2的结点,则它的叶子结点数为。 8.设中的幺元是,α的逆元是。 10.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>} = 。 = 。 三、判断题(每题1分,共10分) 1.命题公式是一个矛盾式。() 2.,若,则必有。() 3.设S为集合X上的二元关系,则S是传递的当且仅当(S S)S。() 4.任何一棵二叉树的结点可对应一个前缀码。() 5.代数系统中一个元素的左逆元一定等于该元素的右逆元。() 6.一个有限平面图,面的次数之和等于该图的边数。() 7.A′B = B′A () 8.设*定义在集合A上的一个二元运算,如果A中有关于运算*的左零元θl和右零θr,则A中 有零元。() 9.一个循环群的生成元不是唯一的。() 10.任何一个前缀码都对应一棵二叉树。() 四、解答题(5小题,共30分) 1.(5分)什么是欧拉路?如何用欧拉路判定一个图G是否可一笔画出? 2.(8分)求公式 (P∨Q)R 的主析取范式和主合取范式。
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解: F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?,在(a)中为假命题,在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?,在(a)(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R.
离散数学试题及答案 一、填空题 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的主析取范式是_______________________________ __________________________________________________________. 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 =________________________. 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变成完全图。
1. 写出命题公式 ﹁(P →(P ∨ Q))的真值表。 答案: 2.证明 答案: 3. 证明以下蕴涵关系成立: 答案: 4. 写出下列式子的主析取范式: 答案: )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5. 构造下列推理的论证:p ∨q, p→?r , s →t, ?s →r, ?t ? q 答案: ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I 11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明:p→(?(r ∧s )→?q ), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
7. 请将下列命题符号化: 所有鱼都生活在水中。 答案: 令 F ( x ):x是鱼 W( x ):x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( x ):x 是有理数 R ( x ):x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化: 尽管有人聪明,但并非一切人都聪明。 答案: 令M(x):x 是人 C(x):x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化: 对于所有的正实数x,y ,都有x+y ≥x。 答案: 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化: 每个人都要参加一些课外活动。 答案: 令P(x ):x 是人 Q (y): y 是课外活动 S(x,y):x参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
第十四章部分课后习题参考答案 5、设无向图G 有10条边,3度与4度顶点各2个,其余顶点的度数均小于3,问G 至少有多少个顶点?在最少顶点的情况下,写出度数列、)()(G G δ、?。 解:由握手定理图G 的度数之和为:20102=? 3度与4度顶点各2个,这4个顶点的度数之和为14度。 其余顶点的度数共有6度。 其余顶点的度数均小于3,欲使G 的顶点最少,其余顶点的度数应都取2, 所以,G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2,2)(,4)(==?G G δ. 7、设有向图D 的度数列为2,3,2,3,出度列为1,2,1,1,求D 的入度列,并求)(),(D D δ?, )(),(D D ++?δ,)(),(D D --?δ. 解:D 的度数列为2,3,2,3,出度列为1,2,1,1,D 的入度列为1,1,1,2. 2)(,3)(==?D D δ,1)(,2)(==?++D D δ,1)(,2)(==?--D D δ 8、设无向图中有6条边,3度与5度顶点各1个,其余顶点都是2度点,问该图有多少个顶点? 解:由握手定理图G 的度数之和为:1262=? 设2度点x 个,则1221513=+?+?x ,2=x ,该图有4个顶点. 14、下面给出的两个正整数数列中哪个是可图化的?对可图化的数列,试给出3种非同构的无向图,其中至少有两个时简单图。 (1) 2,2,3,3,4,4,5 (2) 2,2,2,2,3,3,4,4 解:(1) 2+2+3+3+4+4+5=23 是奇数,不可图化; (2) 2+2+2+2+3+3+4+4=16, 是偶数,可图化; 18、设有3个4阶4条边的无向简单图G 1、G 2、G 3,证明它们至少有两个是同构的。 证明:4阶4条边的无向简单图的顶点的最大度数为3,度数之和为8,因而度数列为2,2,2,2;3,2,2,1;3,3,1,1。但3,3,1,1对应的图不是简单图。所以
离散数学练习题 第一章 一.填空 1.公式) ∨ ? ∧的成真赋值为 01;10 ? p∧ ( (q ) p q 2.设p, r为真命题,q, s 为假命题,则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01;10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式,B为重言式,则B A∨的类型为重言式 5.设p, q均为命题,在不能同时为真条件下,p与q的排斥也可以写成p与q的相容或。 二.将下列命题符合化 1. 7不是无理数是不对的。 解:) ? ?,其中p: 7是无理数;或p,其中p: 7是无理数。 (p 2.小刘既不怕吃苦,又很爱钻研。 解:其中 ?p: 小刘怕吃苦,q:小刘很爱钻研 p∧ ,q 3.只有不怕困难,才能战胜困难。 解:p →,其中p: 怕困难,q: 战胜困难 q? 或q →,其中p: 怕困难, q: 战胜困难 p? 4.只要别人有困难,老王就帮助别人,除非困难解决了。 解:) → ?,其中p: 别人有困难,q:老王帮助别人,r: 困难解决了 p (q r→ 或:q ?) (,其中p:别人有困难,q: 老王帮助别人,r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解:q p?,其中p: 整数n是偶数,q: 整数n能被2整除 三、求复合命题的真值 P:2能整除5, q:旧金山是美国的首都, r:在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解:p, q 为假命题,r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
. 一、选择题:(每题2’) 1、下列语句中不是命题的有()。 A.离散数学是计算机专业的一门必修课。B.鸡有三只脚。 C.太阳系以外的星球上有生物。D.你打算考硕士研究生吗? 2、命题公式A与B是等价的,是指()。 A.A与B有相同的原子变元B.A与B都是可满足的 C.当A的真值为真时,B的真值也为真D.A与B有相同的真值 3、所有使命题公式P∨(Q∧?R)为真的赋值为()。 A.010,100,101,110,111 B.010,100,101,111 C.全体赋值D.不存在 4、合式公式?(P∧Q)→R的主析取范式中含极小项的个数为()。 A.2 B.3 C.5 D.0 5、一个公式在等价意义下,下面哪个写法是唯一的()。 A.析取范式B.合取范式C.主析取范式D.以上答案都不对 6、下述公式中是重言式的有()。 A.(P∧Q) → (P∨Q) B.(P?Q) ? (( P→Q)∧(Q→P)) C.?(P →Q)∧Q D.P →(P∧Q) 7、命题公式(?P→Q) →(?Q∨P)中极小项的个数为(),成真赋值的个数为()。 A.0 B.1 C.2 D.3 8、若公式(P∧Q)∨(?P∧R) 的主析取范式为m001∨m011∨m110∨m111则它的主合取范式为()。 A.m001∧m011∧m110∧m111B.M000∧M010∧M100∧M101 C.M001∧M011∧M110∧M111D.m000∧m010∧m100∧m101 9、下列公式中正确的等价式是()。 A.?(?x)A(x) ? (?x)?A(x) B.(?x) (?y)A(x, y) ? (?y) (?x) A(x, y) C.?(?x)A(x) ? (?x)?A(x) D.(?x) (A(x) ∧B(x)) ? (?x) A(x) ∨(?x) B(x) 10、下列等价关系正确的是()。 A.?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) B.?x ( P(x) ∨Q(x) ) ??x P(x) ∨?x Q(x) C.?x ( P(x) →Q ) ??x P(x) → Q D.?x ( P(x) →Q ) ??x P(x) → Q 11、设个体域为整数集,下列真值为真的公式是()。 A.?x?y(x·y=1)B.?x?y(x·y=0)C.?x?y(x·y=y)D.?x?y(x+y=2y) 12、设S={?,{1},{1,2}},则有()?S。 A.{{1,2}} B.{1,2 } C.{1} D.{2} 13、下列是真命题的有()。 A.{a}?{{a}} B.{{?}}∈{?,{?}} C.?∈{?,{?}} D.{?}∈{?,{?}} 14、设S={?,{1},{1,2}},则2S有()个元素。 A.3 B.6 C.7 D.8
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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,z 5、判断下列语句是不是命题。若是,给出命题的真值。( ) (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) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义是( )。 (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)T 10、设谓词P(x):x 是奇数,Q(x):x 是偶数,谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2是偶数或-3是负数”的否定是( )。 答:2不是偶数且-3不是负数。 12、永真式的否定是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答:(2) 13、公式(?P ∧Q)∨(?P ∧?Q)化简为( ),公式 Q →(P ∨(P ∧Q))可化简为( )。 答:?P ,Q →P
欢迎共阅 一、填空题 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.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.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)}。则R ?S =_____________________________________________________, R 2=______________________________________________________. 二、选择题
《离散数学》题库与答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式?( A ) (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条边。 (5) 前进! (6) 给我一杯水吧!
离散数学 1.在自然推理系统P 中构造下面推理的证明: 前提:,,p q r q r s ?∨∨?→ 结论:p s →. 3设一阶逻辑公式 ((,)(()()))G x yP x y zQ z R x =???→?→ 试将G 化成与其等价的前束范式。 4.判断下面推理是否正确,并证明你的结论。 如果小王今天家里有事,则他不会来开会。 如果小张今天看到小王,则小王今天来开会了。 小张今天看到小王。所以小王今天家里没事。 5、构造下面推理的证明 前提: ))()(()),()()((x R x F x x H x G x F x ∧?∧→? 结论: ))()()((x G x R x F x ∧∧? 6用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ??→∧→=的类型。 7分别用真值表法和公式法求(P →(Q ∨R ))∧(?P ∨(Q ?R ))的主析取范式 ,并写出其相应的成真赋值和成假赋值。 8用逻辑推理证明: 所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。 9、设A ={?,1,{1}},B ={0,{0}},求P (A )、P (B )-{0}、P (B )⊕B 。 10、设X ={1,2,3,4},R 是X 上的二元关系,R ={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>} (1)画出R 的关系图。 (2)写出R 的关系矩阵。 (3)说明R 是否是自反、反自反、对称、传递的。 11、集合X={<1,2>, <3,4>, <5,6>,… },R={<