下载文档原格式
《离散数学》习题与解答
第一篇数理逻辑
第一章命题逻辑
1-1（1）指出下列语句哪些是命题，哪些不是命题，如果是命题指出他的真值
a)离散数学是计算机科学系的一门必修棵
b)∏> 2 吗？
c)明天我去看电影
d)请勿随地吐痰
e)不存在最大质数
f)如果我掌握了英语，法语，那么学习其他欧洲的语言就容易多了
g)9+5<12
h)x<3
i)月球上有水
j)我正在说假话
[解]
a)不是命题
b)是命题,真值视具体情况而定
c)不是命题
d)是命题,真值为t
e)是命题,真值为t
f)是命题,真值为f
g)不是命题
h)是命题, 真值视具体情况而定
i)不是命题
1-2(1)用P表示命题“天下雪”,(又表示命题“我将去镇上”,R表示命题“我有时间”.以符号形式写出下列命题:
(a)如果天不下雪和我有时间,那么我将去镇上.
(b)我将去镇上，仅当我有时间.
(c)天不下雪
(d)天下雪,那么我不去镇上
[解]
a)(┐P∧R)→Q
b)Q→R
c)┐P
d)P→┐Q
1-2(2)将下面这段陈述中所出现的原子命题符号化,并指出他们的真值,然后将这段陈述中的每一命题符号化 2 是有理数是不对的.2是偶素数.2或4是素数.如果2是素数则3也是素数.2是素数当且仅当3也是素数.
[解]:陈述中出现5个原子命题，将他们符号化为:
P: 2 是有理数其真值为F
Q:2是素数其真值为T
R:2是偶数其真值为T
S:3是素数其真值为T
U:4是素数其真值为F
陈述中各命题符号化为:
┐P;Q∧R;Q∨U;Q→S;Q＜＝＞S
1-2(3)将下列命题符号化
a)如果3+3=6,则雪是白色的.
b)如果3+3≠6,则雪是白色的
c)如果3+3=6,则雪不是白色的.
d)如果3+3≠6,则雪不是白色的
e)王强身体很好，成绩也很好.
f)四边形ABCD是平行四边形,仅当其对边平行
[解]:设P:3+3=6 Q:雪是白色的
R:王强成绩很好S:王强身体很好
U: 四边形ABCD是平行四边形V: 四边形ABCD的对边是平行的于是:
a)可表示为:P→Q
b)可表示为: ┐P→Q
c)可表示为: P→┐Q
d)可表示为：┐P→┐Q
e)可表示为：S∧R
f)可表示为:U＜＝＞V
1-3(1)判别下列公式中哪些是合式公式,那些不是合式公式
a) (Q→R∧S)
b) (P＜＝＞(R→S))
c) ((┐P→Q)→(Q→P)))
d) (RS→T)
e)((P→(Q→R))→((P→Q)→(P→R)))
[解]:
a)不是合式公式(若规定运算符优先级后也可以作为合式公式)
b)是合式公式
c)不是合式公式(括号不配对)
d)不是合式公式
e)是合式公式
1-3(2)对下列各式用指定的公式进行代换:
a) (((A→B)→B)→A),用（A→C）代换A，用（（B∧C）→A代换B。
b)((A→B)∨(B→A),用B代换A,A代换B.
[解]:a)((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C))
b)((B→A)∨(A→B))
1-3(3)用符号形式写出下列命题
a)假如上午不下雨,我去看电影;否则就在家里读书或看报.
b)我今天进城,除非下雨.
c)仅当你走,我将留下.
[解]a)设P:上午天下雨. Q:我去看电影
R:我在家读书S:我在家看报
原命题可译为:(┐P→Q)∧(P→(R∨S))
b)设:P:我今天进城Q:天下雨
原命题可译为:┐Q→P
c)设:P:你走Q:我留下
原命题可译为:Q→P
１－３(4)称┐P→┐Q为条件命题P→Q的反换式
Q→P为条件命题P→Q的逆换式
┐Q→┐P为条件命题P→Q的逆反式
试写出如下条件命题的反换式，逆换式，逆反式。
（a）如果他有勇气，则他将得胜。
（b）如果天下雨，我不去。
[解]（a）设P：他有勇气，Q：他将得胜
原条件命题可译为：P→Q
反换式：┐P→┐Q，表示：如果他没有勇气，则他将不能获胜。
逆换式：Q→P，表示：如果他将得胜，则他有勇气。
逆反式：┐Q→┐P，表示：如果他不获胜，则他没有勇气。
（b）设P：天下雨，Q：我去
原条件命题可译为：P→┐Q
反换式：┐P→Q，表示：如果如果天不下雨，则我去。
逆换式：Q→P，表示：如果我不去，则天下雨。
逆反式：┐Q→┐P，表示：如果我去，则天不下雨。
1-4（1）试求下列各命题公式的真值表并解释其结果
（a）（P→Q）∧（Q→P）；
（b）（P∧Q）→P；
（c）Q→（P∨Q）；
（d）（P→Q）＜＝＞（┐P∨Q）；
（e）（┐P∨Q）∧（┐（┐P∧┐Q））；
（f）┐（P→Q）∧Q∧R 。
[解] （a）从真值表1-1中可看出：（P→Q）∧（Q→P）＜＝＞（P＜＝＞Q）
(b) 从真值表1-2中可看出：（P∧Q）→P是永真式
(c) 从真值表1-3中可看出：Q→（P∨Q）是永真式
(d) 从真值表1-4中可看出：（P→Q）＜＝＞（┐P∨Q）是永真式
(e) 从真值表1-5中可看出：（┐P∨Q）∧（┐（┐P∧┐Q））
＜＝＞┐P∨Q
＜＝＞P→Q
＜＝＞┐（P∧┐Q）
(f) 从真值表1-6中可看出：┐（P→Q）∧Q∧R是永真式
