离散数学古天龙-1-4章答案 下载本文

是命题,真值不确定 5今天天气真舒服啊 ○

不是命题 6X+Y<0 ○

不是命题 7我们要努力学习 ○

不是命题 8雪是白的 ○

是命题,真值为真 9有三只脚的鸟 ○

是命题,真值为假 10请安静 ○

不是命题

2.判断下列语句,哪些是简单命题,哪些是复合命题 1我和他即是兄弟又是同学 复合命题 ○

3我明天或后天去苏州 复合命题 ○

5只要他出门,他必买书,不管他余款多不多 复合命题 ○

9不存在最大的质数 复合命题 ○

10除非你陪伴我或代我雇辆车子,否则我不去 复合命题 ○

4.给出下列命题的符号化表示 2不管你和他去不去,我都会去 ○

P:你去 q:他去 r:我去

(p∧q∧r)∨(┒p∧q∧r)∨(p∧┒q∧r)∨(┒p∧┒q∧r) 5小张不但聪明而且勤奋,所以他一直学习成绩优秀 ○

P:小张聪明 q:小张勤奋 r:小张一直学习成绩优秀 P∧q→r

9要选修离散数学课程,必须已经选修微积分课程和计算机导论课程 ○

P:选修离散数学 q:已经选修微积分 r:已经选修计算机科学道导论 P→q∧r

8.给出下列命题的真值表 3(p∨┒q)→q ○

P q ┒q p∨┒q (p∨┒q)→q 0 0 1 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 4(p∨q)→(p∧q) ○

P q p∨q p∧q (p∨q)→(p∧q)

0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 1 1 6(p→q)←→(q→p) ○

P q p→q q→p (p→q)←→(q→p) 0 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1

3、○4、○6命题公式的成真赋值和成假赋值 11.求题8中○

3成真赋值 p=1 q=1;p=0 q=1 ○

成假赋值 p=1 q=0;p=0 q=0 4成真赋值 p=1 q=1;p=0 q=0 ○

成假赋值 p=1 q=1;p=0 q=0 6成真赋值 p=1 q=1;p=0 q=0 ○

成假赋值 p=1 q=0;p=0 q=1

15.给出下列命题公式的真值表并指出各命题公式的类型 2(○(p→q)∧(q→r))→(p→r) 永真公式 5(p→q)←→(┒q→p) 永真公式 ○

16.判断下列命题公式是否为等值式 1p←→q和(p∧q)∨(┒q∨┒p) ○

真值表法 为等值式

5(p→q)∧(p→┒q)和┒p ○

真值表法 为等值式

17.用等值验算证明下列命题公式的等值式 2┒(p←→q)?(p∨q)∧(┒q∨┒p) ○

证明:左边?┒((p→q)∧(q→p)) ?┒((┒p∨q)∧(┒q∨p))

?┒(┒p∨q)∨┒(┒q∨p) ?(p∧┒q)∨(q∧┒p)

?((p∧┒q)∨q)∧((p∧┒q)∨┒p) ?(p∨q)∧(┒p∧┒q)

4p→(q→p) ?┒p→(p→┒q) ○

证明:左边?(┒p∨(┒q∨p)) ?p∨(┒p∨┒q)

?(┒p→(┒p∨┒q) ?(┒p→(p→┒q))

18.用等值演算判断下列命题公示的类型 1((p∨q)∧┒p)→q ○

解:原式?┒((p∨q)∨┒p)∨q?(┒(p∨q)∨p)∨q ?┒(p∨q)∨(p∨q) ?1 该式为永真式

5p∨((┒p∨q)∨(┒p∨┒q)) ○

解:原式?p∨(┒p∧(q∨┒q)) ?p∨┒p?1 该式为永真式

9(p∨q∨r)→(┒p→((q∨r)∧┒p)) ○

解:原式?(p∨q∨r)→(p∨((q∨r)∧┒p))

?(p∨q∨r)→(p∨q∨r) ?┒(p∨q∨r)∨(p∨q∨r) ?1 该式为永真式

29.求题25中命题公式的拾取范式 2(┒p∧q)→r ○

解:原式?┒(┒p∧q)∨r?p∨q∨r?M2 4┒(p∧q)∧(p∨q) ○

解:原式?(┒p∨┒q)∧(p∨q) ?M3∧M0 30.求题25中主析取范式

2原式?M0∨M1∨M3∨M4∨M5∨M6∨M7 ○

?(┒p∧┒q∧┒r)∨(┒p∧┒q∧r)∨(┒p∧q∧r)∨(p∧┒q∧┒r) ∨(p∧┒q∧r)∨(p∧q∧┒r)∨(p∧q∧r) 4原式?M1∨M2?(┒p∧q)∨(┒q∧p) ○

34.用主析取范式判断下列命题公式是否为等值式 6(p←→q)∧(q←→r)和p←→r ○

(p←→q)∧(q←→r) : M0 ∨M7 显然不为等值式 p←→r : M0∨M2∨M5∨M7 38.用等值演算证明如下推理

2p∨┒r, q∨s, r→(p∧s) => s→p ○

思路:即证 (p∨┒r)∧(q∨s)∧(r→(p∧s))→(s→p)是否为重言式 证:

(p∨┒r)∧(q∨s)∧(r→(p∧s))→(s→p) ?(p∨┒r)∧(q∨s)∧(┒r∨(p∧s))→(s→p)

?(p∨┒r)∧(q∨s)∧(┒r∨p)∧(┒r∨s)→(s→p)

?┒((p∨┒r)∧(q∨s)∧(┒r∨p)∧(┒r∨s))∨(┒s∨p) ?(┒p∧r)∨(┒q∧┒s)∨(r∧┒p)∨(r∧┒s)∨┒s∨p ?(┒p∧r)∨(r∧┒p)∨┒s∨p ?(┒p∧r)∨┒s∨p

?p∨r∨┒s 非永真

所以,上述推理不是有效推理 39.用真值表证明题38中的推理 真值表

解:将((p∨┒r)∧(q∨s)∧(r→(p∧s)))→(s→p)的真值 表列出,非永真,所以推理不正确 40.用主析取范式证明题38中的推理

证: ((p∨┒r)∧(q∨s)∧(r→(p∧s)))→(s→p)

?M0∨M2∨M3∨M4∨M6∨M7∨M8∨M9∨M10∨M11∨M12∨M13∨M14∨M15

51.符号化下述推理并证明其有效性:如果今天下大雨,则马路上不好行走; 如果马路难走,则我不去逛书店;如果我不去逛书店,则在家学习,所以 如果今天下大雨,则我在家学习。

p:今天下大雨 q:马路上不好走 s:我不去逛书店 r:我在家学习

前提:p→q, q→s, s→r

结论:p→r

1 p→q 前提引入 证明:○

2 q→s 前提引入 ○

3 p→s ○1○2条件三段论 ○

4 s→r 前提引入 ○

5 p→r ○3○4条件三段论 ○

52.符号化下述推理,并证明其有效性:如果马会飞或羊吃草, 则母鸡会是飞鸟,如果母鸡是飞鸟,那么烤鸭子还会跑。 烤熟的鸭子不会跑,所以羊不会吃草。 符号化:

P:马会飞 q:羊吃草 r:烤熟的鸭子会跑 s:母鸡是飞鸟 前提:p∨q→s, s→r, ┒r 结论:┒q

1 p∨q→r 前提引入 证:○

2 s→r 前提引入 ○

3 p∨q→r ○1○2条件三段论 ○

4 ┒r 前提引入 ○

5 ┒(p∨q) ○

6 ┒p∧┒q ○5置换 ○

7 ┒q ○6化简 ○

55.在一个盗窃案中,已知下列事实:甲或乙是窃贼;甲是窃贼,作案时间不会发生在夜间12点以前;若乙的证词正确,则夜间12点时被盗物品所在房间灯光未灭;若乙的证词不正确,则作案时间发生在夜间12点以前;夜间12点被盗房间的灯光灭了。试用构造证明推理判断谁是窃贼。 证明:

P:甲是窃贼 q:乙是窃贼 r:作案时间发生在夜间12点以前 S:乙的证词正确

t:夜间12点时被盗物品所在房间的灯光灭 前提: p∨q, p→┒r, s→┒t

┒s→r, t 结论:

1s→┒t 前提引入 解: ○

2 t 前提引入 ○

3 ┒s ○1○2拒取式 ○

4┒s→r 前提引入 ○

5 r ○3○4假言推论 ○

6p→┒r 前提引入 ○

7┒p ○5○6拒取式 ○

8p∨q 前提引入 ○

9 q ○7○8析取三段论 ○

所以乙是窃贼

60.甲乙丙站成纵列。甲在最后,丙在最前。现从三顶红帽子和两顶黑帽子中,任拿三顶帽子,分别戴在三人的头上,当按甲乙丙的顺序推测自己所戴帽子的颜色时,丙总能正确说出自己头上的帽子颜色,请写出丙的推理过程。

1如果甲能说出自己的帽子的颜色,那么只有一种情况,就是乙丙头上是黑帽子,甲能解:○

说出自己头上是红帽子,这种情况下,丙一定能说出自己头上是黑帽子。

2如果甲不能说出自己头上帽子的颜色,那么,乙丙可以是两红或一红一黑 ○

3如果乙能说出自己是红色, ○那么,一定是丙戴黑色,如果乙不能说出自己帽子的颜色,那么丙头上一定是红色帽子。