当前位置:文档之家› 离散数学课后习题答案(左孝凌版)

离散数学课后习题答案(左孝凌版)

离散数学课后习题答案(左孝凌版)
离散数学课后习题答案(左孝凌版)

离散数学课后习题答案(左孝凌版)

1-1,1-2解:

a)是命题,真值为T。

b)不是命题。

c)是命题,真值要根据具体情况确定。

d)不是命题。

e)是命题,真值为T。

f)是命题,真值为T。

g)是命题,真值为F。

h)不是命题。

i)不是命题。

(2)解:

原子命题:我爱北京天安门。

复合命题:如果不是练健美操,我就出外旅游拉。

(3)解:

a)(┓P ∧R)→Q

b)Q→R

c)┓P

d)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∧Q

b)设P:小李看书。Q:小李听音乐。P∧Q

c)设P:气候很好。Q:气候很热。P∨Q

d)设P: a和b是偶数。Q:a+b是偶数。P→Q

e)设P:四边形ABCD是平行四边形。Q :四边形ABCD的对边平行。P Q

f)设P:语法错误。Q:程序错误。R:停机。(P∨ Q)→ R

(6) 解:

a)P:天气炎热。Q:正在下雨。 P∧Q

b)P:天气炎热。R:湿度较低。 P∧R

c)R:天正在下雨。S:湿度很高。 R∨S

d)A:刘英上山。B:李进上山。 A∧B

e)M:老王是革新者。N:小李是革新者。 M∨N

f)L:你看电影。M:我看电影。┓L→┓M

g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R

h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q

1-3

(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))

(3)解:

a)((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C))

b)((B→A)∨(A→B))。

(4)解:

a) 是由c) 式进行代换得到,在c) 中用Q代换P, (P→P)代换Q.

d) 是由a) 式进行代换得到,在a) 中用P→(Q→P)代换Q.

e) 是由b) 式进行代换得到,用R代换P, S代换Q, Q代换R, P代换S.

(5)解:

a) P: 你没有给我写信。 R: 信在途中丢失了。 P Q

b) P: 张三不去。Q: 李四不去。R: 他就去。(P∧Q)→R

c) P: 我们能划船。 Q: 我们能跑步。┓(P∧Q)

d) P: 你来了。Q: 他唱歌。R: 你伴奏。P→(Q?R)

(6)解:

P:它占据空间。 Q:它有质量。 R:它不断变化。 S:它是物质。

这个人起初主张:(P∧Q∧R) ? S

后来主张:(P∧Q?S)∧(S→R)

这个人开头主张与后来主张的不同点在于:后来认为有P∧Q必同时有R,开头时没有这样的主张。

(7)解:

a) P: 上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。

(┓P→Q)∧(P→(R∨S))

b) P: 我今天进城。Q:天下雨。┓Q→P

c) P: 你走了。 Q:我留下。Q→P

1-4

(4)解:a)

P Q R Q∧R P∧(Q∧R)P∧Q(P∧Q)∧R

T T T T T F T F T T F F F T T F T F T

F

F

F

T

F

T

F

F

F

F

F

T

T

F

F

F

F

T

F

F

F

F

F

F F T F F F F

F

F

F

F

F

F

F

所以,P∧(Q∧R)?(P∧Q)∧R

b)

P Q R Q∨R P∨(Q∨R)P∨Q(P∨Q)∨R

T T T

T T F

T F T

T F F

F T T

F T F

F F T

F F F T

所以,P∨(Q∨R)?(P∨Q)∨R c)

PQRQ∨

P∧(Q∨

R)

P∧

P∧

(P∧Q)∨(P

∧R)

TTTTTF

TFTTFFFTTFTFFFTFFFT

所以,P∧(Q∨R) (P∧Q)∨(P∧R)

d)

P Q┓P┓Q┓P∨┓Q┓(P∧Q)┓P∧┓Q┓(P∨Q)

T T T F F T F F F

F

T

T

F

T

F

T

F

T

T

T

F

T

T

T

F

F

F

T

F

F

F

T

所以,┓(P∧Q)?┓P∨┓Q, ┓(P∨Q)?┓P∧┓Q

(5)解:如表,对问好所填的地方,可得公式F1~F6,可表达为

P Q R F1 F2 F3 F4 F5 F6

T T T T F T T F F

T T F F F T F F F

T F T T F F T T F

T F F F T F T T F

F T T T F F T T F

F T F T F F F T F

F F T T F T T T F

F F F F T F T T T

F1:(Q→P)→R

F2:(P∧┓Q∧┓R)∨(┓P∧┓Q∧┓R)

F3:(P←→Q)∧(Q∨R)

F4:(┓P∨┓Q∨R)∧(P∨┓Q∨R)

F5:(┓P∨┓Q∨R)∧(┓P∨┓Q∨┓R)

F6:┓(P∨Q∨R)

(6)

Q 1 23 4 5678910111213141516

F F T F T F T F T F T F T F T F T

T F F T T F F T T F F T T F F T T

F F F F F T T T T F F F F T T T T

T F F F F F F F F T T T T T T T T 解:由上表可得有关公式为

1.F

2.┓(P∨Q)

3.┓(Q→P)

4.┓P

5.┓(P→Q)

6.┓Q

7.┓(P?Q)

8.┓(P∧Q)

9.P∧Q 10.P?Q 11.Q 12.P→Q

13.P 14.Q→P 15.P∨Q 16.T

(7) 证明:

a)A→(B→A)?┐A∨(┐B∨A)

? A∨(┐A∨┐B)

? A∨(A→┐B)

?┐A→(A→┐B)

b)┐(A?B) ?┐((A∧B)∨(┐A∧┐B))

?┐((A∧B)∨┐(A∨B))

?(A∨B)∧┐(A∧B)

或┐(A?B) ?┐((A→B)∧(B→A))

?┐((┐A∨B)∧(┐B∨A))

?┐((┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A))

?┐((┐A∧┐B)∨(B∧A))

?┐(┐(A∨B))∨(A∧B)

?(A∨B)∧┐(A∧B)

c)┐(A→B) ?┐(┐A∨B) ?A∧┐B

d)┐(A?B)?┐((A→B)∧(B→A))

?┐((┐A∨B)∧(┐B∨A))

?(A∧┐B)∨(┐A∧B)

e)(((A∧B∧C)→D)∧(C→(A∨B∨D)))

?(┐(A∧B∧C)∨D)∧(┐C∨(A∨B∨D))

?(┐(A∧B∧C)∨D)∧(┐(┐A∧┐B∧C)∨D) ? (┐(A∧B∧C)∧┐(┐A∧┐B∧C))∨D

?((A∧B∧C)∨(┐A∧┐B∧C))→D

? (((A∧B)∨(┐A∧┐B))∧C)→D

? ((C∧(A?B))→D)

f)A→(B∨C) ?┐A∨(B∨C)

? (┐A∨B)∨C

?┐(A∧┐B)∨C

? (A∧┐B)→C

g)(A→D)∧(B→D)?(┐A∨D)∧(┐B∨D)

?(┐A∧┐B)∨D

?┐(A∨B)∨D

? (A∨B)→D

h)((A∧B)→C)∧(B→(D∨C))

?(┐(A∧B)∨C)∧(┐B∨(D∨C))

? (┐(A∧B)∧(┐B∨D))∨C

?(┐(A∧B) ∧┐(┐D∧B))∨C

?┐((A∧B)∨(┐D∧B))∨C

? ((A∨┐D)∧B)→C

? (B∧(D→A))→C

(8)解:

a)((A→B) ? (┐B→┐A))∧C

? ((┐A∨B) ? (B∨┐A))∧C

? ((┐A∨B) ? (┐A∨B))∧C

?T∧C?C

b)A∨(┐A∨(B∧┐B)) ? (A∨┐A)∨(B∧┐B) ?T∨F ?T

c)(A∧B∧C)∨(┐A∧B∧C)

? (A∨┐A) ∧(B∧C)

?T∧(B∧C)

?B∧C

(9)解:1)设C为T,A为T,B为F,则满足A∨C?B∨C,但A?B不成立。 2)设C为F,A为T,B为F,则满足A∧C?B∧C,但A?B不成立。

3)由题意知┐A和┐B的真值相同,所以A和B的真值也相同。

习题 1-5

(1)证明:

a)(P∧(P→Q))→Q

?(P∧(┐P∨Q))→Q

?(P∧┐P)∨(P∧Q)→Q

?(P∧Q)→Q

?┐(P∧Q)∨Q

?┐P∨┐Q∨Q

?┐P∨T

?T

b)┐P→(P→Q)

?P∨(┐P∨Q)

? (P∨┐P)∨Q

?T∨Q

?T

c)((P→Q)∧(Q→R))→(P→R)

因为(P→Q)∧(Q→R)?(P→R)

所以(P→Q)∧(Q→R)为重言式。

d)((a∧b)∨(b∧c) ∨(c∧a))?(a∨b)∧(b∨c)∧(c∨a)

因为((a∧b)∨(b∧c)∨(c∧a))

?((a∨c)∧b)∨(c∧a)

?((a∨c)∨(c∧a))∧(b∨(c∧a))

?(a∨c)∧(b∨c)∧(b∨a)

所以((a∧b)∨(b∧c) ∨(c∧a))?(a∨b)∧(b∨c)∧(c∨a)为重言式。(2)证明:

a)(P→Q)?P→(P∧Q)

解法1:

设P→Q为T

(1)若P为T,则Q为T,所以P∧Q为T,故P→(P∧Q)为T

(2)若P为F,则Q为F,所以P∧Q为F,P→(P∧Q)为T

命题得证

解法2:

设P→(P∧Q)为F,则P为T,(P∧Q)为F,故必有P为T,Q为F,所以P→Q为F。

解法3:

(P→Q) →(P→(P∧Q))

?┐(┐P∨Q)∨(┐P∨(P∧Q))

?┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q))

?T

所以(P→Q)?P→(P∧Q)

b)(P→Q)→Q?P∨Q

设P∨Q为F,则P为F,且Q为F,

故P→Q为T,(P→Q)→Q为F,

所以(P→Q)→Q?P∨Q。

c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))?R→Q

设R→Q为F,则R为T,且Q为F,又P∧┐P为F

所以Q→(P∧┐P)为T,R→(P∧┐P)为F

所以R→(R→(P∧┐P))为F,所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))为F

即(Q→(P∧┐P))→(R→(R→(P∧┐P)))?R→Q成立。

(3)解:

a) P→Q表示命题“如果8是偶数,那么糖果是甜的”。

b)a)的逆换式Q→P表示命题“如果糖果是甜的,那么8是偶数”。

c)a)的反换式┐P→┐Q表示命题“如果8不是偶数,那么糖果不是甜的”。

d)a)的逆反式┐Q→┐P表示命题“如果糖果不是甜的,那么8不是偶数”。

(4)解:

a)如果天下雨,我不去。

设P:天下雨。Q:我不去。P→Q

逆换式Q→P表示命题:如果我不去,则天下雨。

逆反式┐Q→┐P表示命题:如果我去,则天不下雨

b)仅当你走我将留下。

设S:你走了。R:我将留下。R→S

逆换式S→R表示命题:如果你走了则我将留下。

逆反式┐S→┐R表示命题:如果你不走,则我不留下。

c)如果我不能获得更多帮助,我不能完成个任务。

设E:我不能获得更多帮助。H:我不能完成这个任务。E→H

逆换式H→E表示命题:我不能完成这个任务,则我不能获得更多帮助。

逆反式┐H→┐E表示命题:我完成这个任务,则我能获得更多帮助(5)试证明P?Q,Q逻辑蕴含P。

证明:解法1:

本题要求证明(P?Q) ∧Q?P,

设(P?Q) ∧Q为T,则(P?Q)为T,Q为T,故由?的定义,必有P为T。所以(P?Q) ∧Q?P

解法2:

由体题可知,即证((P?Q)∧Q)→P是永真式。

((P?Q)∧Q)→P

? (((P∧Q) ∨(┐P∧┐Q)) ∧Q)→P

?(┐((P∧Q) ∨(┐P∧┐Q)) ∨┐Q) ∨P

?(((┐P∨┐Q) ∧(P∨Q)) ∨┐Q) ∨P

?((┐Q∨┐P∨┐Q) ∧(┐Q∨P∨Q)) ∨P

?((┐Q∨┐P) ∧T) ∨P

?┐Q∨┐P∨P

?┐Q∨T

?T

(6)解:

P:我学习 Q:我数学不及格 R:我热衷于玩扑克。

如果我学习,那么我数学不会不及格:P→┐Q

如果我不热衷于玩扑克,那么我将学习: ┐R→P

但我数学不及格: Q

因此我热衷于玩扑克。 R

即本题符号化为:(P→┐Q)∧(┐R→P)∧Q?R

证:

证法1:((P→┐Q)∧(┐R→P)∧Q)→R

?┐((┐P∨┐Q)∧(R∨P)∧Q) ∨R

?(P∧Q)∨(┐R∧┐P)∨┐Q∨R

?((┐Q∨P)∧(┐Q∨Q))∨((R∨┐R)∧(R∨┐P))?┐Q∨P∨R∨┐P

? T

所以,论证有效。

证法2:设(P→┐Q)∧(┐R→P)∧Q为T,

则因Q为T,(P→┐Q)为T,可得P为F,

由(┐R→P)为T,得到R为T。

故本题论证有效。

(7)解:

P:6是偶数 Q:7被2除尽 R:5是素数

如果6是偶数,则7被2除不尽P→┐Q

或5不是素数,或7被2除尽┐R∨Q

5是素数 R

所以6是奇数┐P

即本题符号化为:(P→┐Q)∧(┐R∨Q)∧R ?┐P

证:

证法1:((P→┐Q)∧(┐R∨Q)∧R)→┐P

?┐((┐P∨┐Q) ∧(┐R∨Q) ∧R) ∨┐P

?((P∧Q) ∨(R∧┐Q) ∨┐R) ∨┐P

?((┐P∨P) ∧(┐P∨Q)) ∨((┐R∨R) ∧(┐R∨┐Q))?(┐P∨Q) ∨(┐R∨┐Q)

?T

所以,论证有效,但实际上他不符合实际意义。

证法2:(P→┐Q)∧(┐R∨Q)∧R为T,

则有R为T,且┐R∨Q为T,故Q为T,

再由P→┐Q为T,得到┐P为T。

(8)证明:

a)P?(┐P→Q)

设P为T,则┐P为F,故┐P→Q为T

b)┐A∧B∧C?C

假定┐A∧B∧C为T,则C为T。

c)C?A∨B∨┐B

因为A∨B∨┐B为永真,所以C?A∨B∨┐B成立。

d)┐(A∧B) ?┐A∨┐B

设┐(A∧B)为T,则A∧B为F。

若A为T,B为F,则┐A为F,┐B为T,故┐A∨┐B为T。

若A为F,B为T,则┐A为T,┐B为F,故┐A∨┐B为T。

若A为F,B为F,则┐A为T,┐B为T,故┐A∨┐B为T。

命题得证。

e)┐A→(B∨C),D∨E,(D∨E)→┐A?B∨C

设┐A→(B∨C),D∨E,(D∨E)→┐A为T,

则D∨E为T,(D∨E)→┐A为T,所以┐A为T

又┐A→(B∨C)为T,所以B∨C为T。命题得证。

f)(A∧B)→C,┐D,┐C∨D?┐A∨┐B

设(A∧B)→C,┐D,┐C∨D为T,则┐D为T,┐C∨D为T,所以C为F 又(A∧B)→C为T,所以A∧B为F,所以┐A∨┐B为T。命题得证。(9)解:

a)如果他有勇气,他将得胜。

P:他有勇气 Q:他将得胜

原命题:P→Q 逆反式:┐Q→┐P 表示:如果他失败了,说明他没勇气。

b)仅当他不累他将得胜。

P:他不累 Q:他得胜

原命题:Q→P 逆反式:┐P→┐Q 表示:如果他累,他将失败。

习题 1-6

(1)解:

a)(P∧Q)∧┐P?(P∧┐P)∧Q?┐(T∨Q)

b)(P→(Q∨┐R)) ∧┐P∧Q

? (┐P∨(Q∨┐R))∧┐P∧Q

?(┐P∧┓P∧Q)∨(Q∧┓P∧Q)∨(┓R∧┓P∧Q)

?(┓P∧Q)∨(┓P∧Q)∨(┓P∧┓R∧Q)

?┓P∧Q

?┐(P∨┐Q)

c)┐P∧┐Q∧(┐R→P)

?┐P∧┐Q∧(R∨P)

?(┐P∧┐Q∧R)∨(┐P∧┐Q∧P)

?(┐P∧┐Q∧R)∨F

?┐P∧┐Q∧R

?┐(P∨Q∨┐R)

(2) 解:

a)┐P? P↓P

b)P∨Q?┐(P↓Q) ? (P↓Q)↓(P↓Q)

c)P∧Q?┐P↓┐Q? (P↓P)↓(Q↓Q)

(3)解:

P→(┐P→Q)

?┐P∨(P∨Q)

?T

?┐P∨P

?(┐P↑┐P)↑(P↑P)

?P↑(P↑P)

P→(┐P→Q)

?┐P∨(P∨Q)

?T

?┐P∨P

?┐(┐P↓P)

?┐((P↓P)↓P)

?((P↓P)↓P)↓((P↓P)↓P)

(4)解:

P↑Q

?┐(┐P↓┐Q)

?┐((P↓P)↓(Q↓Q))

? ((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q)) (5)证明:

┐(B↑C)

?┐(┐B∨┐C)

?┐B↓┐C

┐(B↓C)

?┐(┐B∧┐C)

?┐B↑┐C

(6)解:联结词“↑”和“↓”不满足结合律。举例如下:

a)给出一组指派:P 为T ,Q 为F ,R 为F ,则(P ↑Q)↑R 为T ,P ↑(Q ↑R)为F 故 (P ↑Q)↑R P ↑(Q ↑R).

b)给出一组指派:P 为T ,Q 为F ,R 为F ,则(P ↓Q) ↓R 为T ,P ↓(Q ↓R)为F 故(P ↓Q)↓R P ↓(Q ↓R). (7)证明:

设变元P ,Q ,用连结词?,┐作用于P ,Q 得到:P ,Q ,┐P ,┐Q ,P ?Q ,P ?P ,Q ?Q ,Q ?P 。

但P ?Q ?Q ?P ,P ?P ?Q ?Q ,故实际有:

P ,Q ,┐P ,┐Q ,P ?Q ,P ?P (T ) (A ) 用┐作用于(A )类,得到扩大的公式类(包括原公式类):

P ,Q ,┐P ,┐Q ,┐(P ?Q ), T ,F , P ?Q (B ) 用?作用于(A )类,得到:

P ?Q ,P ?┐P ?F ,P ?┐Q ?┐(P ?Q ),P ?(P ?Q )?Q ,P ?(P ?P )?P , Q ?┐P ?┐(P ?Q ),Q ?┐Q ?F ,Q ?(P ?Q )?P ,Q ?T ?Q, ┐P ?┐Q ?P ?Q ,┐P ?(P ?Q )?┐Q ,┐P ?T ?┐P, ┐Q ?(P ?Q )?┐P ,┐Q ?T ?┐Q, (P ?Q )?(P ?Q )?P ?Q.

因此,(A )类使用运算后,仍在(B )类中。 对(B )类使用┐运算得:

┐P ,┐Q ,P ,Q , P ?Q , F ,T , ┐(P ?Q ), 仍在(B )类中。

? ?

对(B )类使用?运算得:

P ?Q ,P ?┐P ?F ,P ?┐Q ?┐(P ?Q ),P ?┐(P ?Q )?┐Q ,P ?T ?P ,P ?F ?┐P ,P ?(P ?Q )?Q ,

Q ?┐P ?┐(P ?Q ),Q ?┐Q ?F ,Q ?┐(P ?Q )?┐P ,Q ?T ?Q, Q ?F ?┐Q , Q ?(P ?Q )?P ,

┐P ?┐Q ?P ?Q ,┐P ?┐(P ?Q )?Q ,┐P ?T ?┐P, ┐P ?F ?P,┐P ?(P ?Q )?┐Q ,

┐Q ?┐(P ?Q )?P ,┐Q ?T ?┐Q, ┐Q ?T ?┐Q,┐Q ?(P ?Q )?┐P , ┐(P ?Q )?T ?┐(P ?Q ),┐(P ?Q )?F ?P ?Q ,┐(P ?Q )?(P ?Q )?F T ?F ?F ,T ?(P ?Q )? P ?Q F ?(P ?Q )? ┐(P ?Q ) (P ?Q )?(P ?Q )?P ?Q.

故由(B )类使用?运算后,结果仍在(B )中。

由上证明:用?,┐两个连结词,反复作用在两个变元的公式中,结果只能产生(B )类中的公式,总共仅八个不同的公式,故{?,┐}不是功能完备的,更不能是最小联结词组。

已证{?,┐}不是最小联结词组,又因为P Q ? ┐(P ?Q ),故任何命题公式中的

联结词,如仅用{ , ┐}表达,则必可用{?,┐}表达,其逆亦真。故{ , ┐}也必不是最小联结词组。

(8)证明{∨},{∧}和{→}不是最小联结词组。 证明:若{∨},{∧}和{→}是最小联结词,则 ┐P ?(P ∨P ∨……) ┐P ?(P ∧P ∧……)

屈婉玲版离散数学课后习题答案【3】

第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解: F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) ?,在(a)中为假命题,在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) xG ?,在(a)(b)中均为真命题。 (x 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ ?? x ? ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) F ?? x x→ (x ( H ) ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F y x G ? y ? ∧ x→ , ( )) ( H ) x ((y ( (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快

命题符号化为: ))),()(()((y x H x F x y G y →?∧?? 9.给定解释I 如下: (a) 个体域D 为实数集合R. (b) D 中特定元素=0. (c) 特定函数(x,y)=xy,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x

离散数学第三版课后习题答案

离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论

离散数学习题解答 习题一(第一章集合) 1. 列出下述集合的全部元素: 1)A={x | x ∈N∧x是偶数∧x<15} 2)B={x|x∈N∧4+x=3} 3)C={x|x是十进制的数字} [解] 1)A={2,4,6,8,10,12,14} 2)B= 3)C={0,1,2,3,4,5,6,7,8,9} 2. 用谓词法表示下列集合: 1){奇整数集合} 2){小于7的非负整数集合} 3){3,5,7,11,13,17,19,23,29} [解] 1){n n∈I∧(?m∈I)(n=2m+1)}; 2){n n∈I∧n≥0∧n<7}; 3){p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性: 1) 2)∈ 3){} 4)∈{} 5){a,b}{a,b,c,{a,b,c}} 6){a,b}∈(a,b,c,{a,b,c}) 7){a,b}{a,b,{{a,b,}}} 8){a,b}∈{a,b,{{a,b,}}} [解]1)真。因为空集是任意集合的子集; 2)假。因为空集不含任何元素; 3)真。因为空集是任意集合的子集; 4)真。因为是集合{}的元素; 5)真。因为{a,b}是集合{a,b,c,{a,b,c}}的子集; 6)假。因为{a,b}不是集合{a,b,c,{a,b,c}}的元素;

7)真。因为{a,b}是集合{a,b,{{a,b}}}的子集; 8)假。因为{a,b}不是集合{a,b,{{a,b}}}的元素。 4. 对任意集合A,B,C,确定下列命题的真假性: 1)如果A∈B∧B∈C,则A∈C。 2)如果A∈B∧B∈C,则A∈C。 3)如果A B∧B∈C,则A∈C。 [解] 1)假。例如A={a},B={a,b},C={{a},{b}},从而A∈B∧B∈C但A∈C。 2)假。例如A={a},B={a,{a}},C={{a},{{a}}},从而A∈B∧B∈C,但、A ∈C。 3)假。例如A={a},B={a,b},C={{a},a,b},从而ACB∧B∈.C,但A∈C。5.对任意集合A,B,C,确定下列命题的真假性: 1)如果A∈B∧B C,则A∈C。 2)如果A∈B∧B C,则A C。 3)如果A B∧B∈C,则A∈C。 3)如果A B∧B∈C,则A C。 [解] 1)真。因为B C x(x∈B x∈C),因此A∈B A∈C。 2)假。例如A={a},B={{a},{b}},C={{a},{b},{c}}从而A∈B∧B C,但A C。 3)假。例如A={a},B={{a,b}},C={{a,{a,b}},从而A B∧B∈C,但A C。 4)假。例如A={a},B={{a,b}},C={{a,b},b},从而A B∧B∈C,但A C。 6.求下列集合的幂集: 1){a,b,c} 2){a,{b,c}} 3){} 4){,{}} 5){{a,b},{a,a,b},{a,b,a,b}} [解] 1){,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 2){,{a},{{b,c}},{a,{a,b}}} 3){,{}} 4){,{},{{}},{,{}}}

离散数学课后习题答案

习题参考解答 习题 1、(3)P:银行利率降低 Q:股价没有上升 P∧Q (5)P:他今天乘火车去了北京 Q:他随旅行团去了九寨沟 Q P? (7)P:不识庐山真面目 Q:身在此山中 Q→P,或~P→~Q (9)P:一个整数能被6整除 Q:一个整数能被3整除 R:一个整数能被2整除 T:一个整数的各位数字之和能被3整除 P→Q∧R ,Q→T 2、(1)T (2)F (3)F (4)T (5)F (6)T (7)F (8)悖论 习题 1(3) ) ( ) ( ) ( ) ( ) ( ) ( R P Q P R P Q P R Q P R Q P → ∨ → ? ∨ ? ∨ ∨ ? ? ∨ ∨ ? ? ∨ →

(4) ()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右 2、不, 不, 能 习题 1(3) (())~((~)) (~)()~(~(~))(~~)(~) P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、 主合取范式 ) ()()()()()()()()()()()()()())(())(()()(()) ()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧?∧∨?∧?∧∨∧?∧?∨?∧∧?∨?∧?∧?=∧∧∨?∧∧∨∧?∧∨?∧?∧∨∧?∧?∨∧?∧?∨?∧∧?∨?∧?∧?=∨?∧∧∨∨?∧?∧∨∨?∧∨?∧?=∧∨?∧∨?=∨?∧∨?=→∧→ ————主析取范式 (2) ()()(~)(~) (~(~))(~(~))(~~)(~)(~~) P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨Q 2、 ()~() (~)(~) (~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价 3、解:根据给定的条件有下述命题公式: (A →(CD ))∧~(B ∧C )∧~(C ∧D ) (~A ∨(C ∧~D )∨(~C ∧D ))∧(~B ∨~C )∧(~C ∨~D ) ((~A ∧~B )∨(C ∧~D ∧~B )∨(~C ∧D ∧~B )∨ (~A ∧~C )∨(C ∧~D ∧~C )∨(~C ∧D ∧~C ))∧(~C ∨~D )

离散数学习题解答

习题一 1.下列句子中,哪些是命题?在是命题的句子中,哪些是简单命题?哪些是真命题?哪些命题的真值现在还不知道? (1)中国有四大发明. 答:此命题是简单命题,其真值为1. (2)5是无理数. 答:此命题是简单命题,其真值为1. (3)3是素数或4是素数. 答:是命题,但不是简单命题,其真值为1. x+< (4)235 答:不是命题. (5)你去图书馆吗? 答:不是命题. (6)2与3是偶数. 答:是命题,但不是简单命题,其真值为0. (7)刘红与魏新是同学. 答:此命题是简单命题,其真值还不知道. (8)这朵玫瑰花多美丽呀! 答:不是命题. (9)吸烟请到吸烟室去! 答:不是命题. (10)圆的面积等于半径的平方乘以π. 答:此命题是简单命题,其真值为1. (11)只有6是偶数,3才能是2的倍数. 答:是命题,但不是简单命题,其真值为0. (12)8是偶数的充分必要条件是8能被3整除. 答:是命题,但不是简单命题,其真值为0. (13)2008年元旦下大雪. 答:此命题是简单命题,其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:(1)p:中国有四大发明. (2)p:是无理数. (7)p:刘红与魏新是同学. (10)p:圆的面积等于半径的平方乘以π. (13)p:2008年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. (1)5是有理数. 答:否定式:5是无理数.p:5是有理数.q:5是无理数.其否定式q的真值为1.

(2)25不是无理数. 答:否定式:25是有理数. p :25不是无理数. q :25是有理数. 其否定式q 的真值为1. (3)2.5是自然数. 答:否定式:2.5不是自然数. p :2.5是自然数. q :2.5不是自然数. 其否定式q 的真值为1. (4)ln1是整数. 答:否定式:ln1不是整数. p :ln1是整数. q :ln1不是整数. 其否定式q 的真值为1. 4.将下列命题符号化,并指出真值. (1)2与5都是素数 答:p :2是素数,q :5是素数,符号化为p q ∧,其真值为1. (2)不但π是无理数,而且自然对数的底e 也是无理数. 答:p :π是无理数,q :自然对数的底e 是无理数,符号化为p q ∧,其真值为1. (3)虽然2是最小的素数,但2不是最小的自然数. 答:p :2是最小的素数,q :2是最小的自然数,符号化为p q ∧?,其真值为1. (4)3是偶素数. 答:p :3是素数,q :3是偶数,符号化为p q ∧,其真值为0. (5)4既不是素数,也不是偶数. 答:p :4是素数,q :4是偶数,符号化为p q ?∧?,其真值为0. 5.将下列命题符号化,并指出真值. (1)2或3是偶数. (2)2或4是偶数. (3)3或5是偶数. (4)3不是偶数或4不是偶数. (5)3不是素数或4不是偶数. 答: p :2是偶数,q :3是偶数,r :3是素数,s :4是偶数, t :5是偶数 (1) 符号化: p q ∨,其真值为1. (2) 符号化:p r ∨,其真值为1. (3) 符号化:r t ∨,其真值为0. (4) 符号化:q s ?∨?,其真值为1. (5) 符号化:r s ?∨?,其真值为0. 6.将下列命题符号化. (1)小丽只能从筐里拿一个苹果或一个梨. 答:p :小丽从筐里拿一个苹果,q :小丽从筐里拿一个梨,符号化为: p q ∨. (2)这学期,刘晓月只能选学英语或日语中的一门外语课. 答:p :刘晓月选学英语,q :刘晓月选学日语,符号化为: ()()p q p q ?∧∨∧?. 7.设p :王冬生于1971年,q :王冬生于1972年,说明命题“王冬生于1971年或1972年”既可以化 答:列出两种符号化的真值表:

屈婉玲版离散数学课后习题答案【1】

第一章部分课后习题参考答案 16 设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。 (1)p∨(q∧r)?0∨(0∧1) ?0 (2)(p?r)∧(﹁q∨s) ?(0?1)∧(1∨1) ?0∧1?0. (3)(?p∧?q∧r)?(p∧q∧﹁r) ?(1∧1∧1)? (0∧0∧0)?0 (4)(?r∧s)→(p∧?q) ?(0∧1)→(1∧0) ?0→0?1 17.判断下面一段论述是否为真:“π是无理数。并且,如果3是无理数,则2也是无理数。另外6能被2整除,6才能被4整除。” 答:p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为:p∧(q→r)∧(t→s)的真值为1,所以这一段的论述为真。19.用真值表判断下列公式的类型: (4)(p→q) →(?q→?p) (5)(p∧r) ?(?p∧?q) (6)((p→q) ∧(q→r)) →(p→r) 答:(4) p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式//最后一列全为1 (5)公式类型为可满足式(方法如上例)//最后一列至少有一个1 (6)公式类型为永真式(方法如上例)// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值.

(1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答:(2)(p→(p∨q))∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r (p∨q)→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式: (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明(2)(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) (4)(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式,并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r) 解: (1)主析取范式 (?p→q)→(?q∨p)

吉林大学离散数学课后习题答案

第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法: 方法一.真值表方法。即列出公式的真值表,若表中对应公式所在列的每一取值全为1,这说明该公式在它的所有解释下都是真,因此是恒真的;若表中对应公式所在列的每

一取值全为0,这说明该公式在它的所有解释下都为假,因此是恒假的。 真值表法比较烦琐,但只要认真仔细,不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解:该公式的真值表如下: 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1,故

G恒真。 方法二.以基本等价式为基础,通过反复对一个公式的等价代换,使之最后转化为一个恒真式或恒假式,从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解:由(P→R) ∨? R=?P∨ R∨? R=1,以及 ? (Q→P) ∧ P= ?(?Q∨ P)∧ P = Q∧? P∧ P=0 知,((P→R) ∨? R)→ (? (Q→P) ∧ P)=0,故G恒假。 方法三.设命题公式G含n个原子,若求得G的主析取范式包含所有2n个极小项,则G是恒真的;若求得G的主合取范式包含所有2n个极大项,则G是恒假的。 方法四. 对任给要判定的命题公式G,设其中有原子P1,P2,…,P n,令P1取1值,求G的真值,或为1,或为0,或成为新公式G1且其中只有原子P2,…,P n,再令P1取0值,求G真值,如此继续,到最终只含0或1为止,若最终结果全为1,则公式G恒真,若最终结果全为0,则公式G

离散数学课后习题答案(左孝凌版)

离散数学课后习题答案(左孝凌版) 1-1,1-2解: a)是命题,真值为T。 b)不是命题。 c)是命题,真值要根据具体情况确定。 d)不是命题。 e)是命题,真值为T。 f)是命题,真值为T。 g)是命题,真值为F。 h)不是命题。 i)不是命题。 (2)解: 原子命题:我爱北京天安门。 复合命题:如果不是练健美操,我就出外旅游拉。 (3)解: a)(┓P ∧R)→Q b)Q→R c)┓P d)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∧Q b)设P:小李看书。Q:小李听音乐。P∧Q c)设P:气候很好。Q:气候很热。P∨Q d)设P: a和b是偶数。Q:a+b是偶数。P→Q e)设P:四边形ABCD是平行四边形。Q :四边形ABCD的对边平行。P Q f)设P:语法错误。Q:程序错误。R:停机。(P∨ Q)→ R (6) 解: a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 (1)解:

离散数学课后习题答案左孝凌版

a)是命题,真值为T。 b)不是命题。 c)是命题,真值要根据具体情况确定。 d)不是命题。 e)是命题,真值为T。 f)是命题,真值为T。 g)是命题,真值为F。 h)不是命题。 i)不是命题。 (2)解: 原子命题:我爱北京天安门。 复合命题:如果不是练健美操,我就出外旅游拉。 (3)解:、- a)(┓P ∧R)→Q b)Q→R c)┓P d)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∧Q b)设P:小李看书。Q:小李听音乐。P∧Q c)设P:气候很好。Q:气候很热。P∨Q d)设P: a和b是偶数。Q:a+b是偶数。P→Q e)设P:四边形ABCD是平行四边形。Q :四边形ABCD的对边平行。 P Q f)设P:语法错误。Q:程序错误。R:停机。(P∨ Q)→ R (6) 解: a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 (1)解: a)不是合式公式,没有规定运算符次序(若规定运算符次序后亦可 作为合式公式) b)是合式公式 c)不是合式公式( d)) e)不是合式公式(R和S之间缺少联结词) f)是合式公式。 (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)) (3)解: a)((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b)((B→A)∨(A→B))。 (4)解: a) 是由c) 式进行代换得到,在c) 中用Q代换P, (P→P)代换Q. d) 是由a) 式进行代换得到,在a) 中用P→(Q→P)代换Q.

离散数学课后答案

离散数学课后答案 习题一 6.将下列命题符号化。 (1)小丽只能从框里那一个苹果或一个梨. (2)这学期,刘晓月只能选学英语或日语中的一门外语课. 答: (1)(p Λ?q )ν(?pΛq)其中p:小丽拿一个苹果,q:小丽拿一个梨(2)(p Λ?q )ν(?pΛq)其中p:刘晓月选学英语,q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答: (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q

离散数学第四版课后标准答案

离散数学第四版课后答案 第1章习题解答 1.1 除(3),(4),(5),(11)外全是命题,其中,(1),(2),(8),(9), (10),(14),(15)是简单命题,(6),(7),(12),(13)是复合命题。 分析首先应注意到,命题是陈述句,因而不是陈述句的句子都不是命题。 本题中,(3)为疑问句,(5)为感叹句,(11)为祈使句,它们都不是陈述句,所以它们都不是命题。 其次,4)这个句子是陈述句,但它表示的判断结果是不确定。又因为(1),(2),(8),(9),(10),(14),(15)都是简单的陈述句,因而作为命题,它们都是简单命题。(6)和(7)各为由联结词“当且仅当”联结起来的复合命题,(12)是由联结词“或”联结的复合命题,而(13)是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中,合取联结词有许多表述法,例如,“虽然……,但是……”、“不仅……,而且……”、“一面……,一面……”、“……和……”、“……与……”等。但要注意,有时“和”或“与” 联结的是主语,构成简单命题。例如,(14)、(15)中的“与”与“和”是联结的主语,这两个命题均为简单命题,而不是复合命题,希望读者在遇到“和”或“与”出现的命题时,要根据命题所陈述的含义加以区分。 1.2 (1)p: 2是无理数,p为真命题。 (2)p:5能被2整除,p为假命题。 (6)p→q。其中,p:2是素数,q:三角形有三条边。由于p与q都是真 命题,因而p→q为假命题。 (7)p→q,其中,p:雪是黑色的,q:太阳从东方升起。由于p为假命

题,q为真命题,因而p→q为假命题。 (8)p:2000年10月1日天气晴好,今日(1999年2月13日)我们还不 知道p的真假,但p的真值是确定的(客观存在的),只是现在不知道而已。(9)p:太阳系外的星球上的生物。它的真值情况而定,是确定的。 1 (10)p:小李在宿舍里. p的真值则具体情况而定,是确定的。 (12)p∨q,其中,p:4是偶数,q:4是奇数。由于q是假命题,所以,q 为假命题,p∨q为真命题。 (13)p∨q,其中,p:4是偶数,q:4是奇数,由于q是假命题,所以,p∨q 为假命题。 (14)p:李明与王华是同学,真值由具体情况而定(是确定的)。 (15)p:蓝色和黄色可以调配成绿色。这是真命题。 分析命题的真值是唯一确定的,有些命题的真值我们立即可知,有些则不能马上知道,但它们的真值不会变化,是客观存在的。 1.3 令p:2+2=4,q:3+3=6,则以下命题分别符号化为 (1)p→q (2)p→?q (3)?p→q (4)?p→?q

最新离散数学习题答案

离散数学习题答案 习题一及答案:(P14-15) 14、将下列命题符号化: (5)李辛与李末是兄弟 解:设p :李辛与李末是兄弟,则命题符号化的结果是p (6)王强与刘威都学过法语 解:设p :王强学过法语;q :刘威学过法语;则命题符号化的结果是 p q ∧ (9)只有天下大雨,他才乘班车上班 解:设p :天下大雨;q :他乘班车上班;则命题符号化的结果是q p → (11)下雪路滑,他迟到了 解:设p :下雪;q :路滑;r :他迟到了;则命题符号化的结果是()p q r ∧→ 15、设p :2+3=5. q :大熊猫产在中国. r :太阳从西方升起. 求下列复合命题的真值: (4)()(())p q r p q r ∧∧???∨?→ 解:p=1,q=1,r=0, ()(110)1p q r ∧∧??∧∧??, (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型: (2)()p p q →?→? 解:列出公式的真值表,如下所示: 20、求下列公式的成真赋值:

(4)()p q q ?∨→ 解:因为该公式是一个蕴含式,所以首先分析它的成假赋值,成假赋值的条件是: ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有:01,10,11。 习题二及答案:(P38) 5、求下列公式的主析取范式,并求成真赋值: (2)()()p q q r ?→∧∧ 解:原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨,此即公式的主析取范式, 所以成真赋值为011,111。 6、求下列公式的主合取范式,并求成假赋值: (2)()()p q p r ∧∨?∨ 解:原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?,此即公式的主合取范式, 所以成假赋值为100。 7、求下列公式的主析取范式,再用主析取范式求主合取范式: (1)()p q r ∧∨ 解:原式()(()())p q r r p p q 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 ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨,此即主析取范式。 主析取范式中没出现的极小项为0m ,2m ,4m ,所以主合取范式中含有三个极大项0M ,2M ,4M ,故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式:

离散数学课后习题答案_(左孝凌版)

1-1,1-2 (1)解: a)是命题,真值为T。 b)不是命题。 c)是命题,真值要根据具体情况确定。 d)不是命题。 e)是命题,真值为T。 f)是命题,真值为T。 g)是命题,真值为F。 h)不是命题。 i)不是命题。 (2)解: 原子命题:我爱北京天安门。 复合命题:如果不是练健美操,我就出外旅游拉。 (3)解: a)(┓P ∧R)→Q b)Q→R c)┓P d)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∧Q b)设P:小李看书。Q:小李听音乐。P∧Q c)设P:气候很好。Q:气候很热。P∨Q d)设P:a和b是偶数。Q:a+b是偶数。P→Q

e)设P:四边形ABCD是平行四边形。Q :四边形ABCD的对边平行。P Q f)设P:语法错误。Q:程序错误。R:停机。(P∨Q)→R (6) 解: a)P:天气炎热。Q:正在下雨。P∧Q b)P:天气炎热。R:湿度较低。P∧R c)R:天正在下雨。S:湿度很高。R∨S d)A:刘英上山。B:李进上山。A∧B e)M:老王是革新者。N:小李是革新者。M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。R:我在睡觉。P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 (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)) (3)解: a)((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b)((B→A)∨(A→B))。 (4)解: a) 是由c) 式进行代换得到,在c) 中用Q代换P, (P→P)代换Q.

离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案

离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0;r、s的真值为1,求下列各命题公式的真值。 (1)p∨(q∧r)?0∨(0∧1) ?0 (2)(p?r)∧(﹁q∨s) ?(0?1)∧(1∨1) ?0∧1?0. (3)(?p∧?q∧r)?(p∧q∧﹁r) ?(1∧1∧1)? (0∧0∧0)?0 (4)(?r∧s)→(p∧?q) ?(0∧1)→(1∧0) ?0→0?1 17.判断下面一段论述是否为真:“π是无理数。并且,如果3是无理数,则2也是无理数。另外6能被2整除,6才能被4整除。” 答:p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为:p∧(q→r)∧(t→s)的真值为1,所以这一段的论述为真。19.用真值表判断下列公式的类型: (4)(p→q) →(?q→?p) (5)(p∧r) ?(?p∧?q) (6)((p→q) ∧(q→r)) →(p→r) 答:(4) p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 (5)公式类型为可满足式(方法如上例) (6)公式类型为永真式(方法如上例) 第二章部分课后习题参考答案

3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答:(2)(p→(p∨q))∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r (p∨q)→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式: (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明(2)(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) (4)(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 5.求下列公式的主析取范式与主合取范式,并求成真赋值 (1)(?p→q)→(?q∨p) (2)?(p→q)∧q∧r (3)(p∨(q∧r))→(p∨q∨r)

离散数学最全课后答案(屈婉玲版)

1.1.略 1.2.略 1.3.略 1.4.略 1.5.略 1.6.略 1.7.略 1.8.略 1.9.略 1.10.略 1.11.略 1.12.将下列, 并给出各命题的: (1)2+2=4 当且仅 当3+3=6. (2)2+2=4 的充要 条件是3+3 6. (3)2+2 4 与3+3 =6 互为充要条件. (4)若2+24, 则 3+36, 反之亦然. (1)p q, 其中, p: 2+2=4, q: 3+3=6, 真值为1. (2)p q,

其中, p: 2+2=4, q: 3+3=6, 真值为0. (3) p q, 其中, p: 2+2=4, q: 3+3=6, 真值为0. (4) p q, 其中, p: 2+2=4, q: 3+3=6, 真值为1. 1.13.将下列命题符号化, 并给出各命题的真值:(1)若今天是星期一, 则明天是星期二. (2)只有今天是星期一, 明天才是星期二. (3)今天是星期一当且仅当明天是星期二. (4)若今天是星期一, 则明天是星期三. 令p: 今天是星期一; q: 明天是星期二; r: 明天是星期三. (1) p q 1. (2) q p 1. (3) p q 1.

(4) p r 当p 0 时为真; p 1 时为假. 1.14.将下 列 . (1) 刘 晓月跑得快, 跳得高. (2) 老王是山东 人或河北人. (3)因为天气冷, 所以我穿了羽 绒服. (4)王欢与李乐组成一个 小组. (5)李辛与李末是兄弟. (6)王强与刘威都学 过法语. (7)他一面 吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他 迟到了. (12)2 与4 都是素数, 这是不对的. (13)“2或4 是素数, 这是不对的”是不对的.

离散数学习题详细答案

离散数学习题详细答案

————————————————————————————————作者:————————————————————————————————日期:

离散数学习题答案 习题一及答案:(P14-15) 14、将下列命题符号化: (5)李辛与李末是兄弟 解:设p :李辛与李末是兄弟,则命题符号化的结果是p (6)王强与刘威都学过法语 解:设p :王强学过法语;q :刘威学过法语;则命题符号化的结果是 p q ∧ (9)只有天下大雨,他才乘班车上班 解:设p :天下大雨;q :他乘班车上班;则命题符号化的结果是q p → (11)下雪路滑,他迟到了 解:设p :下雪;q :路滑;r :他迟到了;则命题符号化的结果是()p q r ∧→ 15、设p :2+3=5. q :大熊猫产在中国. r :太阳从西方升起. 求下列复合命题的真值: (4)()(())p q r p q r ∧∧???∨?→ 解:p=1,q=1,r=0, ()(110)1p q r ∧∧??∧∧??, (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型: (2)()p p q →?→? 解:列出公式的真值表,如下所示: p q p ? q ? ()p p →? ()p p q →?→? 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值,故公式是非重言式的可满足式。 20、求下列公式的成真赋值:

离散数学课后习题答案_(左孝

证明 设A 上定义的二元关系R 为: <<x,y >, <u,v >>∈R ?x y =u v ① 对任意<x,y >∈A ,因为x y =x y ,所以 <<x,y >, <x,y >>∈R 即R 是自反的。 ② 设<x,y >∈A ,<u,v >∈A ,若 <<x,y >, <u,v >>∈R ?x y =u v ?u v =x y ?<<u,v >,<x,y >>∈R 即R 是对称的。 ③ 设任意<x,y >∈A ,<u,v >∈A ,<w,s >∈A ,对 <<x,y >, <u,v >>∈R ∧<<u,v >, <w,s >>∈R ?(x y =u v )∧(u v =w s )?x y =w s ?<<x,y >, <w,s >>∈R 故R 是传递的,于是R 是A 上的等价关系。

3-10.6 设R是集合A 上的对称和传递关系,证明如果对于A中的每一个元素a,在A中同时也存在b,使在R之中,则R是一个等价关系。 证明对任意a∈A,必存在一个b∈A,使得<a,b>∈R. 因为R是传递的和对称的,故有: <a,b>∈R∧<b, c>∈R?<a, c>∈R?<c,a>∈R 由<a,c>∈R∧<c, a>∈R?<a,a>∈R 所以R在A上是自反的,即R是A上的等价关系。 3-10.7 设R1和R2是非空集合A上的等价关系,试确定下述各式,哪些是A上的等价关系,对不是的式子,提供反例证明。a)(A×A)-R1; b)R1-R2; c)R12; d) r(R1-R2)(即R1-R2的自反闭包)。 解 a)(A×A)-R1不是A上等价关系。例如: A={a,b},R1={<a,a>,<b,b>}

离散数学课后习题答案左孝凌版

离散数学课后习题答案(左孝凌版) 1-1,1-2解: a)是命题,真值为T。 b)不是命题。 c)是命题,真值要根据具体情况确定。 d)不是命题。 e)是命题,真值为T。 f)是命题,真值为T。 g)是命题,真值为F。 h)不是命题。 i)不是命题。 (2)解: 原子命题:我爱北京天安门。 复合命题:如果不是练健美操,我就出外旅游拉。 (3)解: a)(┓P ∧R)→Q b)Q→R c)┓P d)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∧Q b)设P:小李看书。Q:小李听音乐。P∧Q c)设P:气候很好。Q:气候很热。P∨Q d)设P:a和b是偶数。Q:a+b是偶数。P→Q e)设P:四边形ABCD是平行四边形。Q :四边形ABCD的对边平行。P Q f)设P:语法错误。Q:程序错误。R:停机。(P∨ Q)→ R (6) 解: a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。R:我在睡觉。P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 (1)解:

相关主题
相关文档 最新文档