离散数学课后习题答案_(邱学绍)

第一章命题逻辑

习题1.11．解⑴不是陈述句，所以不是命题。

⑵x取值不确定，所以不是命题。

⑶问句，不是陈述句，所以不是命题。

⑷惊叹句，不是陈述句，所以不是命题。

⑸是命题，真值由具体情况确定。

⑹是命题，真值由具体情况确定。

⑺是真命题。

⑻是悖论，所以不是命题。

⑼是假命题。

2．解⑴是复合命题。设p：他们明天去百货公司；q：他们后

p∨。

天去百货公司。命题符号化为q

⑵是疑问句，所以不是命题。

⑶是悖论，所以不是命题。

⑷是原子命题。

⑸是复合命题。设p：王海在学习；q：李春在学习。命题符号化为p∧q。

⑹是复合命题。设p：你努力学习；q：你一定能取得优异成绩。p→q。

⑺不是命题。

⑻不是命题

⑼。是复合命题。设p：王海是女孩子。命题符号化为：?p。

1

3．解⑴如果李春迟到了，那么他错过考试。

⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。

⑶李春错过考试当且仅当他迟到了。

⑷如果李春迟到了并且错过了考试，那么他没有通过考试。

4．解⑴?p→(q∨r)。⑵p→q。⑶q→p。⑷q → p。

习题1.2

1．解⑴是1层公式。

⑵不是公式。

⑶一层：p∨q，?p

二层：?p?q

所以，)

p?

?

∨是3层公式。

→

p

(

q

)

(q

⑷不是公式。

⑸(p→q)∧?(?q?( q→?r))是5层公式，这是因为

一层：p→q，?q，?r

二层：q→?r

三层：?q?( q→?r)

四层：?(?q?( q→?r))

2．解⑴A=(p∨q)∧q是2层公式。真值表如表2-1所示：

表2-1

2

3

⑵p q p q A →→∧=)(是3层公式。真值表如表2-2所示：

表2-2

⑶)()(q p r q p A ∨→∧∧=是3层公式。真值表如表2-3所示：

表2-3

⑷)()()(r q r p q p A ∨∧∨?∧∨=是4层公式。真值表如表2-4所示： 3．解 ⑴p q p A ∨?∧?=)(真值表如表2-5所示：

4

表2-5

所以其成真赋值为：00，10，11；其成假赋值为01。 ⑵)(q p r A ∧→=真值表如表2-6所示：

表2-6

所以其成真赋值为：000，010，100，110，111；其成假赋值为001，011，101。

⑶)()(q p q p A ?∨?→=真值表如表2-7所示，所以其成真赋值为：

5

00，11；成假赋值为：01，10，。

4．解 ⑴设)(q p p A ∧?∨=，其真值表如表2-8所示：

表2-8

故)(q p p A ∧?∨=为重言式。

⑵设A =(p ∧q )∧?(p ∨q )，其真值表如表2-9所示：

表2-9

故A =(p ∧q )∧?(p ∨q )为矛盾式。

⑶设A =(p →q )?(?p ?q )，其真值表如表2-10所示：

表2-10

6

故A =(p →q )?(?p ?q )为可满足式。

⑷设)())()((r p r q q p A →→→∧→=，其真值表如表2-11所示：

表2-11

故)())()((r p r q q p A →→→∧→=为重言式。 习题1.3

1．解 ⑴真值表如表2-12所示：

表2-12

7

由真值表可以看出)(q p ∨?和q p ?∧?所在的列相应填入值相同，故等值。

⑵真值表如表2-13所示：

表2-13

由真值表可以看出p 和)()(q p q p ?∧∨∧所在的列相应填入值相同，故等值。

⑶真值表如表2-14所示：

表2-14

由真值表可以看出?p 和(p →q )∧(p →?q )所在的列相应填入值相同，故等值。

⑷真值表如表2-15所示：

8

表

2-15 由真值表可以看

出p →(q →r )和(p ∧q )→r 所在的列相应填入值相同，故等值。 2．证明 ⑴(p ∧q )∨? (?p ∨q )? (p ∧q )∨( p ∧?q ) ? p ∧ (q ∨?q )? p 。

⑵(p →q )∧(q →p )?(?p ∨q ) ∧(?q ∨p ) ?(?p ∧?q )∨(?p ∧ p )∨( q ∧?q )∨(q ∧ p ) ?( p ∧q )∨(?p ∧?q )。

⑶由⑵可得，?(p ?q )??(( p ∧q )∨(?p ∧?q )) ?(? p ∨?q )∧(p ∨q )?(q →?p )∧(?p →q )??p ?q 。 ⑷p →(q →r )?? p ∨(?q ∨ r ) ?? q ∨(?p ∨ r )? q →( p →r )。 ⑸)()(r q p r q p ∨∨??∨→

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

9

r q p →?∧?)(

⑹)()()()(q r q p q r q p ∨?∧∨??→∧→

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

3．解 ⑴?(p →?q )??(?p ∨?q )?p ∧q ⑵?(?p →?q )??( p ∨?q )??p ∧q

⑶?(p ??q )??((p →?q )∧(?q →p ))??(p →?q )∨?(?q →p ) ?(p ∧q ) ∨(?p ∧?q )? p ?q 。 ⑷同理可证?(?p ?q )? p ?q 。 4．解 ⑴与习题2.2第4（4）相同。 ⑵真值表如表2-16所示：

表2-16

所以公式是重言式。

⑶真值表如表2-17所示，所以公式是矛盾式。

表2-17

⑷真值表如表2-18所示，所以公式是重言式。

表2-18

⑸真值表如表2-19所示，所以公式仅为可满足式。

表2-19

10

⑹真值表如表2-20所示，所以公式是重言式。

表2-20

5．解⑴设p：他努力学习；q：他会通过考试。则命题符号化p→q。

其否定?(p→q)? p∧?q。

所以语句的否定：他学习很努力但没有通过考试。

⑵设p：水温暖；q：他游泳。则命题符号化p?q。

其否定?(p?q)? p??q。

所以语句的否定：当且仅当水不温暖时他游泳。

⑶设p：天冷；q：他穿外套；r：他穿衬衫。则命题符号化p→(q∧?r) 其否定?( p→(q∧?r))??(?p∨(q∧?r))

11

12

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

所以语句的否定：天冷并且他不穿外套或者穿衬衫。

⑷设p ：他学习；q ：他将上清华大学；r ：他将上北京大学。则命题符号化)(r q p ∨→

其否定))((r q p ∨→?))((r q p ∨∨???r q p ?∧?∧?

所以语句的否定：他努力学习，但是没有上清华大学，也没有上北京大学。

6．解 设p ：张三说真话；q ：李四说真话；r ：王五说真话。

则：p ??q , q ??r (??q ?r ), r ?(?p ∧?q )为真,

因此p ?(?p ∧?q )?(p ∧?p ∧?q )∨(?p ∧(p ∨q ))??p ∧q 为真。 因此，p 为假，q 为真，所以r 为假。

故张三说谎，李四说真话，王五说谎。

7．解 设p ：甲得冠军；q ：乙得亚军；r ：丙得亚军；s ：丁得亚军。

前提：p →(q ∨r )，q →?p ，s →?r ，p

结论：?s

证明 p →(q ∨r )为真，其前件p 为真，所以q ∨r 为真，

又q →?p 为真，其后件?p 为假，所以要求q 为假，所以r 为真。 又s →?r 为真，其后件?r 为假，所以要求s 为假，故?s 为真。 习题1.4

1．解 ⑴设p ：明天下雨；q ：后天下雨。命题符号化q p ∨。 ⑵设p ：明天我将去北京；q ：明天我将去上海。命题符号化q p ∨。

13

2．解 ⑴p q p ∨→)(

))(())((p q p p q p ∧→?∨?∧→?

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

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

⑵)(p q p ∨↓))((p q p ∨∨??

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

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

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

⑶r q p ↓↑)(

))((r q p ∨↑??))((r q p ∨∧???

r q p ?∧∧?

3．证明 因为，{?→∧∨?,,,,}是功能完备联结词集，所以，含有{?→∧∨?,,,,}外的其他联结词的公式均可以转换为仅含{?→∧∨?,,,,}中的联结词的公式。

又因为q p q p ∨??→

)()()()(p q q p p q q p q p ∨?∧∨??→∧→??

即含有?→,的公式均可以转换为仅含{∧∨?,,}中的联结词的公式。因此，含{∧∨?,,}外其他联结词的公式均可以转换为仅含{∧∨?,,}中的联结词的公式。

故{∧∨?,,}是功能完备联结词集。

4．证明 },{∧?是极小功能完备集，因而只需证明},{∧?中的每个联结词都可以用↑ 表示，就说明}{↑是功能完备集。只有一个联结词，自然是极小功能完备集。事实上，

14

?p ??(p ∧p )?p ↑p ，

p ∧q ???(p ∧q )??(p ↑q )?(p ↑q )↑(p ↑q )。

对于证明}{↓是极小功能完备集，可类似证明。

习题1.5

1．解 ⑴)()(q p q p ∧?∨?∧?；

⑵p r p r q p ?∨?∧∨∨?∧))()(((

2．解 ⑴)()(s r q p →→→?)()(s r q p ∨?∨∨??

?s r q p ∨?∨?∧)(即为其析取范式。

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

?)()(s r q s r p ∨?∨?∧∨?∨即为其合取范式。

⑵)(r q p ?∧??)()(q r r q p ∨?∧∨?∧?即为其合取范式。 ?p ∧(q ?r )??p ∧((q ∧r )∨(?q ∧?r ))

?(?p ∧q ∧r )∨(?p ∧?q ∧?r ) 即为其析取范式。

⑶r q p ?∧∨)(即为其合取范式。

r q p ?∧∨)(?)()(r q r p ?∧∨?∧为其析取范式。

⑷)(r q p →→?r q p ∨?∨?即为其析取范式和合取范式。

3．解 ⑴)(q p p ∨?∧)())((q p q q p ∨?∧∧?∨?

∏?∨?∧∨∧?∨?)2,1,0()()()(q p q p q p 即为其主合取范式。 其主析取范式为∑3?p ∧q 。

⑵)()(q p q p ?∧?∨→?1)()(?∨?∨∨?q p q p 。

故其主析取范式为∑(0,1,2,3)=(?p ∧?q )∨(?p ∧q )∨(p ∧?q )∨(p ∧q )。 ⑶p r q p →→∨))((p r q p ∨∨∨???))((

15

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

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

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

∏?)3,1,0(即为其主合取范式。

其主析取范式为∑(2,4,5,6,7) ?

(?p ∧q ∧?r )∨(p ∧?q ∧?r )∨(p ∧?q ∧r )∨(p ∧q ∧?r )∨(p ∧q ∧r )。

⑷)()(s r q p →→→)()(s r q p ∨?∨∨???

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

)()()()(s r q p s r q p s r q p s r q p ∨?∨?∨?∧∨?∨?∨∧∨?∨?∨∧∨?∨∨?∏?)14,6,2(即为其主合取范式。

其主析取范式为∑)15,13,12,11,10,9,8,7,5,4,3,1,0(。

4．解 ⑴真值表如表2-21所示, 所以其极小项是p ∧?q ，极大项为p ∨q ，p ∨?q ，?p ∨?q 。

表2-21

其主析取范式是：p ∧?q ，主合取范式为：(p ∨q )∧( p ∨?q )∧(?p ∨?q )。 ⑵真值表如表2-222所示, 所以其极小项是?p ∧q , p ∧?q , p ∧q , 极大项为p ∨q 。

表2-22

其主析取范式是：(?p∧q)∨(p∧?q)∨(p∧q)，主合取范式为：p∨q。

⑶真值表如表2-23所示，所以其极小项是?p∧q∧r,p∧?q∧?r, p∧?q∧r, p∧q∧?r,p∧q∧r,

表2-23

极大项为p∨q∨r，p∨q∨?r，p∨?q∨r。其主析取范式是：

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

16

∨(p∧q∧?r)∨(p∧q∧r)，主合取范式为：(p∨q∨r)∧(p∨q∨?r)∧(p∨?q∨r) 。

⑷真值表如表2-24所示,所以其极小项为

?p∧?q∧r,?p∧q∧r,p∧?q∧?r,p∧?q∧r,p∧q∧r,

而极大项分为p∨q∨r，p∨?q∨r，?p∨?q∨r.主合取范式为

(p∨q∨r)∧(p∨?q∨r)∧(?p∨?q∨r),

主析取范式为

(?p∧?q∧r)∨(?p∧q∧r)∨(p∧?q∧?r,)∨(p∧?q∧r)∨(p∧q∧r)。

表2-24

5．解⑴(?p∨q)∧(?(?p∧?q))?(?p∨q)∧(p∨q)

? q? (?p∧q)∨(p∧q)，

故⑴为可满足式。

⑵)

p→

→

q

→

q

∧

→

(

(

))

r

)

((r

p

17

18

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

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

()()()()p q r p q r p q r p q r ?∧?∧∨∧?∧?∨∧∧?∨?∧∧? ()()()()p q r p q r p q r p q r ∨?∧∧∨?∧∧?∨?∧?∧∨?∧?∧? ()()()()p q r p q r p q r p q r ∨∧∧∨∧?∧∨?∧∧∨?∧?∧ (0,1,2,3,4,5,6,7)?∑

故⑵为重言式。

⑶?(p ∨(q ∧r ))?((p ∨q )∧(p ∨r ))??(p ∨(q ∧r ))?(p ∨(q ∧r )) ?(p ∨(q ∧r ))∨(p ∨(q ∧r ))∧?(p ∨(q ∧r ))∨?(p ∨(q ∧r )) ?(p ∨(q ∧r ))∧?(p ∨(q ∧r ))

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

?(?p ∧q ∧r )∧(?q ∨?r )?0。

故⑶为矛盾式。

⑷(()())(()())p q r s p r q s →∨→→∨→∨

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

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

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

()()()

∨?∧∧?∧∨?∧?∧∧∨?∧?∧?∧

p q r s p q r s p q r s

?∑

(0,1,3,4,5,6,7,9,10,11,12,13,14,15)

故仅为可满足式。

6．证明⑴右边已经是主合取范式。而左边主合取范式已是

?p∧?q，因此，

?(p∨ q)??p∧?q，证毕。

⑵右边(p∨ q)∧(p∨?q)已经是主合取范式。p?p∨(q∧?q)? (p∨q)∧(p∨?q)。因此，)

∧

∨

p?

?。

∧

)

(

p

(q

q

p

⑶左边p→(q→r)??p∨(?q∨r)??p∨?q∨r，而右边

∧)

(??(p∧q)∨r

q

p→

r

??p∨?q∨r，因此，)

p→

(。

q

∧)

p→

(r

q

→?r

习题1.6

1．解设p：这里有演出；q：这里通行是困难的；r：他们按照指定时间到达。

前提：p→q, r→?q,r

结论：?p

证明

①r P

②r→?q P

③?q T①②假言推理

④p→q P

⑤?p T③④拒取式

19

2．⑴证明

①s P

②s→p P

③p T①②假言推理

④p→q P

⑤q T③④假言推理

⑵证明

①r P附加前提引入

②r→q P

③q T①②假言推理

④p→?q P

⑤?p T③④拒取式

⑥?p→s P

⑦s T⑤⑥假言推理

⑧r→s T①⑦CP

⑶证明

20

①p P否定结论引入

②p→q P

③q T①②假言推理

④q→r P

⑤r T③④假言推理

⑥?r∧s P

⑦?r T⑥化简

⑧r∧?r T⑤⑦合取

⑷证明

①p P附加前提引入

②?p∨q P

③q①②析取三段论

④r→?q P

⑤?r③④拒取式

⑥p→?r①⑥CP

21

本文来源：https://www.bwwdw.com/article/9sjq.html