1 离散数学 习题 参考答案
第一章 命题逻辑
习题一
1、构造公式(p∧q)∨ (¬p∧¬q)、p↔q 的真值表。
2、构造公式¬(p∨q)与¬p∧¬q 的真值表。
3、构造公式 p、p∧p、p∨p 的真值表。
4、构造公式 p∨(q∧r)、(p∨q)∧(p∨r)的真值表。
5、构造公式 p∨(p∧r)、p 的真值表。
6、构造公式 p∧(p∨r)、p 的真值表。
7、构造公式 p↔q、¬q↔¬p 的真值表。
8、构造公式(p→q)∧(p→¬q)、¬p 的真值表。
9、构造公式 p、¬¬p 的真值表。
10、构造公式 p∨¬p、p∧¬p 的真值表
略
习题二
一、分别用等算演算与真值表法，判断下列公式是否存在主析取范式或主合取范式，若有，请写出来。
(1)(¬p→q)→(¬q∨p)
(2)(¬p→q)→(q∧r)
(3)(p∨(q∧r))→(p∨q∨r)
(4) ¬(q→¬p)∧¬p
(5)(p∧q)∨(¬p∨r)
(6)(p→(p∨q))∨r
(7)(p∧q)∨r
(8) (p→q)∧(q→r)
(9) (p∧q)→q
(10) ¬(r↔p)∧p∧q
解：(1)
p q ¬p (¬p→q) ¬q (¬q∨p) (¬p→q)→(¬q∨p)
0 0 1 0 1 1 1
0 1 1 1 0 0 0
1 0 0 1 1 1 1
1 1 0 1 0 1 1
存在主析取范式=成真赋值对应的小项的析取
=m00∨m10∨m11=(¬p∧¬q)∨(p∧¬q)∨(p∧q)
主析取范式=成假赋值对应的大项的合取
=M01=p∨¬q
等值演算：
(¬p→q)→(¬q∨p)
⇔¬ (¬¬p∨q)∨(p∨¬q)
⇔¬ (p∨q)∨(p∨¬q)
⇔ (¬p∧¬q)∨(p∨¬q)
⇔ (¬p∨(p∨¬q))∧(¬q∨(p∨¬q))
离散数学课后答案
1.2
1.分析下列语句哪些是命题，哪些不是命题；如果是命题，指出其真值：
a) 北京是中国的⾸都。b) 上海是全国⼈⼝最多的城市。c) 今天天⽓多么好啊d) 11+1=100.e) 雪是⿊⾊的，当且仅当5>0.
f) 全体起⽴！g) 不存在最⼤素数。h) x+6≥16.i) ⽩⾊加红⾊可以调成粉红⾊。j) 明天你去看电影吗?k) ⽕星上有⽣物。
答：a)的真值为T;b)的真值为T；c)不是命题；d)的真值为F；e)F；f)不是命题；g)F；h)不是命题；i)T；j)不是命题；k)F。3.将下列命题符号化。
a) ⼩李不但聪明⽽且⽤功。b) 昨天晚⾃习时⼩赵做了⼆三⼗道数学题。c) 如果天下⼤⾬，他就在体育馆内锻炼。d)
:
:
:
:
:
4.将下列复合命题分成若⼲原⼦命题。
a) 今天天⽓炎热，且有雷阵⾬。b) 如果你不去⽐赛，那么我也不去⽐赛。c) 我既不看电视，也不去看电影，我准备做作业。
d) 四边形ABCD是平⾏四边形，当且仅当它的对边平⾏。
答：a)原⼦命题为：今天天⽓炎热；今天有雷阵⾬b)原⼦命题为：你去⽐赛；我去⽐赛；c)原⼦命题为：我看电视；我看电影；我做作业；d)原⼦命题为：四边形ABCD是平⾏四边形；四边形的对边平⾏；
1.3
1.判别下列公式哪些是合式公式，哪些不是合式公式。
a) (Q→R∧S)；b) (P←→(R→S))；c) ((|P→Q)→(Q→P))；d) (RS→K)；e) ((P→(Q→R))→((P→Q)→(P→R)))；
答: a) 不是合式公式。b) 是合式公式。c) 是合式公式。d) 不是合式公式。e) 是合式公式2.根据定义，说明下列公式如何形成合式公式。
a) (A→(A∨B))；b) ((|A∧B)∧A)；c) ((|A→B)∨(B→A))；
答：a) 由合式公式的定义中的规定(1)A、B本⾝是⼀个合式公式；由规定(3)(A∨B)是⼀个合式公式；由规定(4)再次应⽤(3)可得式(A→(A∨B)；b) 由合式公式定义规定(1)A、B本⾝各是⼀合式公式；由规定(2)|A是⼀合式公式；由规定(4)应⽤(3)得(|A∧B)是⼀合式公式；再应⽤(3)得原式是⼀个合式公式。c) 由合式公式定义规定(1)A、B本⾝各是⼀合式公式；由规定(2)|A是⼀合式公式；由规定(3)(|A→B)、(B→A)各是合式公式；由规定(4)应⽤(3)得到的式⼦为合式公式。3.设P、Q的真值为0；R、S的真值为1；求下列各命题公式的真值。
1离散数学课后习题答案_(左孝凌版)
（1）解：a)是命题，真值为T。b)不是命题。c)是命题，真值要根据具体情况确定。d)不是命题。e)是命题，真值为T。f)是命题，真值为T。g)是命题，真值为F。h)不是命题。i)不是命题。（2）解：原子命题：我爱北京天安门。复合命题：如果不是练健美操，我就出外旅游拉。（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→┓M
2g)P:我不看电视。Q:我不外出。R:我在睡觉。P∧Q∧Rh)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q
习题解答
（1）解：
a)不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b)是合式公式c)不是合式公式（括弧不配对）d)不是合式公式（R和S之间缺少联结词）e)是合式公式。
（2）解：
a）A是合式公式，(A∨B)是合式公式，(A→(A∨B))是合式公式。这个过程可以简记为：A；(A∨B)；(A→(A∨B))同理可记b）A；┓A；(┓A∧B)；((┓A∧B)∧A)c）A；┓A；B；(┓A→B)；(B→A)；((┓A→B)→(B→A))d）A；B；(A→B)；(B→A)；((A→B)∨(B→A))
（完整版）洪帆《离散数学基础》（第三版）课后习题答
案
第1章 集合1、列举下列集合的元素 (1) ⼩于20的素数的集合 (2) ⼩于5的⾮负整数的集合 (3) 2{|,10240515}i i I i i i ∈--<≤≤且 答：(1){1,3,5,7,11,13,17,19}
(2) {0,1,2,3,4} (3) {5,6,7,8,9,10,11}
2、⽤描述法表⽰下列集合 (1) 12345{,,,,}a a a a a 答：{|,15}i a i I i ∈≤≤ (2) {2,4,8,}L 答：{2|}i i N ∈ (3) {0,2,4,100}L
答：{2|,050}i i Z i ∈≤≤3、下⾯哪些式⼦是错误的？ (1) {}{{}}a a ∈ 答：正确 (2) {}{{}}a a ? 答：错误 (3) {}{{},}a a a ∈ 答：正确 (4) {}{{},}a a a ? 答：正确
4、已给{2,,{3},4}S a =和{{},3,4,1}R a =，指出下⾯哪些论断是正确的？哪些是错误的？ (1) {}a S ∈ 错误
(2) {}a R ∈ 正确 (3) {,4,{3}}a S ? 正确 (4) {{},1,3,4}a R ? 正确 (5)R S = 错误 (6) {}a S ? 正确 (7) {}a R ?错误 (8) R φ?正确 (9) {{}}aR φ?? 正确 (10) {}S φ?错误 (11) R φ∈错误 (12) {{3},4}φ?正确
5、 列举出集合,,A B C 的例⼦，使其满⾜A B ∈，B C ∈且A C ?
答：{}A a =，{{}}B a =，显然A B ∈，{{{}}}C a =，显然B C ∈，但是A C ?。6、 给出下列集合的幂集 (1) {,{}}a b
答：幂集{,{},{{}},{,{}}a b a b φ (2) {,,{}}a a φ
