離散數(shù)學(xué)課后習(xí)題答案

第第頁離散數(shù)學(xué)課后習(xí)題答案第一章命題規(guī)律

習(xí)題1.11．解⑴不是陳述句，所以不是命題。

⑵*取值不確定，所以不是命題。

⑶問句，不是陳述句，所以不是命題。

⑷贊嘆句，不是陳述句，所以不是命題。

⑸是命題，真值由詳細(xì)狀況確定。

⑹是命題，真值由詳細(xì)狀況確定。

⑺是真命題。

⑻是悖論，所以不是命題。

⑼是假命題。

2．解⑴是復(fù)合命題。設(shè)p：他們明天去百貨公司；q：他們后

p∨。

天去百貨公司。命題符號化為q

⑵是疑問句，所以不是命題。

⑶是悖論，所以不是命題。

⑷是原子命題。

⑸是復(fù)合命題。設(shè)p：王海在學(xué)習(xí)；q：李春在學(xué)習(xí)。命題符號化為p∧q。

⑹是復(fù)合命題。設(shè)p：你努力學(xué)習(xí)；q：你肯定能取得優(yōu)異成果。p→q。

⑺不是命題。

⑻不是命題

⑼。是復(fù)合命題。設(shè)p：王海是女孩子。命題符號化為：?p。

1

3．解⑴假如李春遲到了，那么他錯過考試。

⑵要么李春遲到了，要么李春錯過了考試，要么李春通過了考試。

⑶李春錯過考試當(dāng)且僅當(dāng)他遲到了。

⑷假如李春遲到了并且錯過了考試，那么他沒有通過考試。

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

習(xí)題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

⑵pqpqA→→∧=)(是3層公式。真值表如表2-2所示：

表2-2

⑶)()(qprqpA∨→∧∧=是3層公式。真值表如表2-3所示：

表2-3

⑷)()()(rqrpqpA∨∧∨?∧∨=是4層公式。真值表如表2-4所示：3．解⑴pqpA∨?∧?=)(真值表如表2-5所示：

4

表2-5

所以其成真賦值為：00，10，11；其成假賦值為01。⑵)(qprA∧→=真值表如表2-6所示：

表2-6

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

⑶)()(qpqpA?∨?→=真值表如表2-7所示，所以其成真賦值為：

5

00，11；成假賦值為：01，10，。

4．解⑴設(shè))(qppA∧?∨=，其真值表如表2-8所示：

表2-8

故)(qppA∧?∨=為重言式。

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

表2-9

故A=(p∧q)∧?(p∨q)為沖突式。

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

表2-10

6

故A=(p→q)?(?p?q)為可滿意式。

⑷設(shè))())()((rprqqpA→→→∧→=，其真值表如表2-11所示：

表2-11

故)())()((rprqqpA→→→∧→=為重言式。習(xí)題1.3

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

表2-12

7

由真值表可以看出)(qp∨?和qp?∧?所在的列相應(yīng)填入值相同，故等值。

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

表2-13

由真值表可以看出p和)()(qpqp?∧∨∧所在的列相應(yīng)填入值相同，故等值。

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

表2-14

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

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

8

表

2-15由真值表可以看

出p→(q→r)和(p∧q)→r所在的列相應(yīng)填入值相同，故等值。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)。⑸)()(rqprqp∨∨??∨→

rqp∨∨??)(rqp∨?∧??)(

9

rqp→?∧?)(

⑹)()()()(qrqpqrqp∨?∧∨??→∧→

qrp∨?∧??)(qrp→∨?)(

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．解⑴與習(xí)題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．解⑴設(shè)p：他努力學(xué)習(xí)；q：他會通過考試。那么命題符號化p→q。

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

所以語句的否定：他學(xué)習(xí)很努力但沒有通過考試。

⑵設(shè)p：水暖和；q：他游泳。那么命題符號化p?q。

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

所以語句的否定：當(dāng)且僅當(dāng)水不暖和時(shí)他游泳。

⑶設(shè)p：天冷；q：他穿外套；r：他穿襯衫。那么命題符號化p→(q∧?r)其否定?(p→(q∧?r))??(?p∨(q∧?r))

11

12

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

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

⑷設(shè)p：他學(xué)習(xí)；q：他將上清華高校；r：他將上北京高校。那么命題符號化)(rqp∨→

其否定))((rqp∨→?))((rqp∨∨???rqp?∧?∧?

所以語句的否定：他努力學(xué)習(xí)，但是沒有上清華高校，也沒有上北京高校。

6．解設(shè)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．解設(shè)p：甲得冠軍；q：乙得亞軍；r：丙得亞軍；s：丁得亞軍。

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

結(jié)論：?s

證明p→(q∨r)為真，其前件p為真，所以q∨r為真，

又q→?p為真，其后件?p為假，所以要求q為假，所以r為真。又s→?r為真，其后件?r為假，所以要求s為假，故?s為真。習(xí)題1.4

1．解⑴設(shè)p：明天下雨；q：后天下雨。命題符號化qp∨。⑵設(shè)p：明天我將去北京；q：明天我將去上海。命題符號化qp∨。

13

2．解⑴pqp∨→)(

))(())((pqppqp∧→?∨?∧→?

))(())((pqppqp∧∨??∨?∧∨??

)(pqpp∧?∧∨??qp?∨??

⑵)(pqp∨↓))((pqp∨∨??

))()((pqpqp∧?∨?∧∨??

))((pqp?∧∨??

)(qp∨??qp?∧??

⑶rqp↓↑)(

))((rqp∨↑??))((rqp∨∧???

rqp?∧∧?

3．證明由于，{?→∧∨?,,,,}是功能完備聯(lián)結(jié)詞集，所以，含有{?→∧∨?,,,,}外的其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含{?→∧∨?,,,,}中的聯(lián)結(jié)詞的公式。

又由于qpqp∨??→

)()()()(pqqppqqpqp∨?∧∨??→∧→??

即含有?→,的公式均可以轉(zhuǎn)換為僅含{∧∨?,,}中的聯(lián)結(jié)詞的公式。因此，含{∧∨?,,}外其他聯(lián)結(jié)詞的公式均可以轉(zhuǎn)換為僅含{∧∨?,,}中的聯(lián)結(jié)詞的公式。

故{∧∨?,,}是功能完備聯(lián)結(jié)詞集。

4．證明},{∧?是微小功能完備集，因而只需證明},{∧?中的每個聯(lián)結(jié)詞都可以用↑表示，就說明}{↑是功能完備集。只有一個聯(lián)結(jié)詞，自然是微小功能完備集。事實(shí)上，

14

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

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

對于證明}{↓是微小功能完備集，可類似證明。

習(xí)題1.5

1．解⑴)()(qpqp∧?∨?∧?；

⑵prprqp?∨?∧∨∨?∧))()(((

2．解⑴)()(srqp→→→?)()(srqp∨?∨∨??

?srqp∨?∨?∧)(即為其析取范式。

)()(srqp→→→?srqp∨?∨?∧)(

?)()(srqsrp∨?∨?∧∨?∨即為其合取范式。

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

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

⑶rqp?∧∨)(即為其合取范式。

rqp?∧∨)(?)()(rqrp?∧∨?∧為其析取范式。

⑷)(rqp→→?rqp∨?∨?即為其析取范式和合取范式。

3．解⑴)(qpp∨?∧)())((qpqqp∨?∧∧?∨?

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

⑵)()(qpqp?∧?∨→?1)()(?∨?∨∨?qpqp。

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

15

prqp∨?∧∨?))(()()(rpqp?∨∧∨?

))()(())()((qqrprrqp?∧∨?∨∧?∧∨∨?

)()()()(rqprqprqprqp?∨?∨∧?∨∨∧?∨∨∧∨∨?

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

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

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

⑷)()(srqp→→→)()(srqp∨?∨∨???

)()()()(srqsrpsrqp∨?∨?∧∨?∨?∨?∨?∧?

)()()()(srqpsrqpsrqpsrqp∨?∨?∨?∧∨?∨?∨∧∨?∨?∨∧∨?∨∨?∏?)14,6,2(即為其主合取范式。

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

4．解⑴真值表如表2-21所示,所以其微小項(xiàng)是p∧?q，極大項(xiàng)為p∨q，p∨?q，?p∨?q。

表2-21

其主析取范式是：p∧?q，主合取范式為：(p∨q)∧(p∨?q)∧(?p∨?q)。⑵真值表如表2-222所示,所以其微小項(xiàng)是?p∧q,p∧?q,p∧q,極大項(xiàng)為p∨q。

表2-22

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

⑶真值表如表2-23所示，所以其微小項(xiàng)是?p∧q∧r,p∧?q∧?r,p∧?q∧r,p∧q∧?r,p∧q∧r,

表2-23

極大項(xiàng)為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所示,所以其微小項(xiàng)為

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

而極大項(xiàng)分為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

(()())()pqqrpr???∨∧?∨∨?∨

()()()pqqrpr?∧?∨∧?∨?∨

()()()()pqrpqrpqrpqr?∧?∧∨∧?∧?∨∧∧?∨?∧∧?()()()()pqrpqrpqrpqr∨?∧∧∨?∧∧?∨?∧?∧∨?∧?∧?()()()()pqrpqrpqrpqr∨∧∧∨∧?∧∨?∧∧∨?∧?∧(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。

故⑶為沖突式。

⑷(()())(()())pqrsprqs→∨→→∨→∨

(()())()pqrsprqs???∨∧??∨∨?∧?∨∨

(()())()pqrsprqs?∧?∧∧?∨?∧?∨∨

()()()pqrspqrspqrs?∧?∧∧?∨?∧∧?∧∨?∧∧?∧?()()()pqrspqrspqrs∨?∧?∧?∧∨?∧?∧?∧?∨∧∧∧()()()pqrspqrspqrs∨∧∧∧?∨∧∧?∧∨∧∧?∧?()()()pqrspqrspqrs∨?∧∧∧∨?∧∧∧?∨?∧∧?∧()()()pqrspqrspqrs∨?∧∧?∧?∨∧∧∧∨∧∧?∨()()()pqrspqrspqrs∨∧?∧∧∨∧?∧?∧∨?∧∧∧

()()()

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

pqrspqrspqrs

?∑

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

故僅為可滿意式。

6．證明⑴右邊已經(jīng)是主合取范式。而左邊主合取范式已是

?p∧?q，因此，

?(p∨q)??p∧?q，證畢。

⑵右邊(p∨q)∧(p∨?q)已經(jīng)是主合取范式。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

習(xí)題1.6

1．解設(shè)p：這里有演出；q：這里通行是困難的；r：他們根據(jù)指定時(shí)間到達(dá)。

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

結(jié)論：?p

證明

①rP

②r→?qP

③?qT①②假言推理

④p→qP

⑤?pT③④拒取式

19

2．⑴證明

①sP

②s→pP

③pT①②假言推理

④p→qP

⑤qT③④假言推理

⑵證明

①rP附加前提引入

②r→qP

③qT①②假言推理

④p→?qP

⑤?pT③④拒取式

⑥?p→sP

⑦sT⑤⑥假言推理

⑧r→sT①⑦CP

⑶證明

20

①pP否定結(jié)論引入

②p→qP

③qT①②假言推理

④q→rP

⑤rT③④假言推理

⑥?r∧sP

⑦?rT⑥化簡

⑧r∧?rT⑤⑦合取

⑷證明

①pP附加前提引入

②?p∨qP

③q①②析取三段論

④r→?qP

⑤?r③④拒取式

⑥p→?r①⑥CP

21

第一章命題規(guī)律

習(xí)題1.11．解⑴不是陳述句，所以不是命題。

⑵*取值不確定，所以不是命題。

⑶問句，不是陳述句，所以不是命題。

⑷贊嘆句，不是陳述句，所以不是命題。

⑸是命題，真值由詳細(xì)狀況確定。

⑹是命題，真值由詳細(xì)狀況確定。

⑺是真命題。

⑻是悖論，所以不是命題。

⑼是假命題。

2．解⑴是復(fù)合命題。設(shè)p：他們明天去百貨公司；q：他們后

p∨。

天去百貨公司。命題符號化為q

⑵是疑問句，所以不是命題。

⑶是悖論，所以不是命題。

⑷是原子命題。

⑸是復(fù)合命題。設(shè)p：王海在學(xué)習(xí)；q：李春在學(xué)習(xí)。命題符號化為p∧q。

⑹是復(fù)合命題。設(shè)p：你努力學(xué)習(xí)；q：你肯定能取得優(yōu)異成果。p→q。

⑺不是命題。

⑻不是命題

⑼。是復(fù)合命題。設(shè)p：王海是女孩子。命題符號化為：?p。

1

3．解⑴假如李春遲到了，那么他錯過考試。

⑵要么李春遲到了，要么李春錯過了考試，要么李春通過了考試。

⑶李春錯過考試當(dāng)且僅當(dāng)他遲到了。

⑷假如李春遲到了并且錯過了考試，那么他沒有通過考試。

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

習(xí)題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

⑵pqpqA→→∧=)(是3層公式。真值表如表2-2所示：

表2-2

⑶)()(qprqpA∨→∧∧=是3層公式。真值表如表2-3所示：

表2-3

⑷)()()(rqrpqpA∨∧∨?∧∨=是4層公式。真值表如表2-4所示：3．解⑴pqpA∨?∧?=)(真值表如表2-5所示：

4

表2-5

所以其成真賦值為：00，10，11；其成假賦值為01。⑵)(qprA∧→=真值表如表2-6所示：

表2-6

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

⑶)()(qpqpA?∨?→=真值表如表2-7所示，所以其成真賦值為：

5

00，11；成假賦值為：01，10，。

4．解⑴設(shè))(qppA∧?∨=，其真值表如表2-8所示：

表2-8

故)(qppA∧?∨=為重言式。

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

表2-9

故A=(p∧q)∧?(p∨q)為沖突式。

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

表2-10

6

故A=(p→q)?(?p?q)為可滿意式。

⑷設(shè))())()((rprqqpA→→→∧→=，其真值表如表2-11所示：

表2-11

故)())()((rprqqpA→→→∧→=為重言式。習(xí)題1.3

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

表2-12

7

由真值表可以看出)(qp∨?和qp?∧?所在的列相應(yīng)填入值相同，故等值。

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

表2-13

由真值表可以看出p和)()(qpqp?∧∨∧所在的列相應(yīng)填入值相同，故等值。

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

表2-14

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

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

8

表

2-15由真值表可以看

出p→(q→r)和(p∧q)→r所在的列相應(yīng)填入值相同，故等值。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)?(