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.
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
F F
T
T
F
F
F
T
F
F
F
T
F
F
F
F
F
F
F
T
T
F
F
F
F
F
F
T
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 T
T
T
F
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
T
F
T
T
F
F
F
T
T
F
T
F
F
F
T
F
F
FFT
T
T
F
F
T
T
T
T
F
F
所以,P∨(Q∨R)(P∨Q)∨R c)
PQRQ
∨
R
P∧
(Q∨
R)
P
∧
Q
P
∧
R
(P∧Q)∨
(P∧R)
T
TTTTFTFTTT
T
T
F
T
T
T
F
T
T
T
F
F
F
F
F
T
T
F
F
F
F
F
F
T
F
T
F
F
F
F
F
T
T
T
F
F
F
F
F
F
F
F
T
T
F
T
F
F
F
T
F
F
F
所以,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 F1F2F3F4F5F6
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
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)
解:由上表可得有关公式为
2.┓(P∨Q) 3 .┓(Q→P) 4.┓P
5.┓(P→Q)
6.┓Q
7.┓(P Q) 8.┓(P∧Q)
∧Q Q
→Q
→P
∨Q
(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 ∧……) ┐P
P →(P →(P →……)
对所有命题变元指派T ,则等价式左边为F ,右边为T ,与等价表达式矛盾。
所以{∨},{∧}和{→}不是最小联结词。 (9)证明{┐,→}和{┐, }是最小联结词组。 证明:因为{┐,∨}为最小联结词组,且P ∨Q ┐P →Q
所以{┐,→}是功能完备的联结词组,又→ c ∨
离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论
离散数学习题解答 习题一(第一章集合) 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年”既可以化 答:列出两种符号化的真值表:
第一章部分课后习题参考答案 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)
离散数学课后习题答案(左孝凌版) 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)解:
离散数学课后答案 习题一 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、用真值表法求下面公式的主析取范式:
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 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>}
习题3.7 1. 列出关系}6|{=???∈><+ d c b a d c b a d c b a 且,,,,,,Z 中所有有序4元组。 解 }6|{=???∈><+ d c b a d c b a d c b a 且,,,,,,Z ,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><= ><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3,1,1,3,2,1,2,3,1,1,3,2,1 2. 列出二维表 3.18所表示的多元关系中所有5元组。假设不增加新的5元组,找出二维表3.18所有的主键码。 表3.18 航班信息 航空公司 航班 登机口 目的地 起飞时间 Nadir 112 34 底特律 08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛 09:10 Nadir 322 34 底特律 09:44 解 略 3. 当施用投影运算5,3,2π到有序5元组> 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)解: 习题 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 第四章部分课后习题参考答案 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)在两个个体域中都解释为)(x ?,在(a)中为假命题, xF 在(b)中为真命题。 (2)在两个个体域中都解释为)(x ?,在(a)(b)中均为真命 xG 题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ x ?? ? ) ( H ( (x (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→ ((y ( )) ( H ) x , ( (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y 快 命题符号化为: ))) x F x y y→ ?? ∧ ? H G ) ( , x ( ( ( (y ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 离散数学~ 习题1.1 1.下列句子中,哪些是命题?哪些不是命题?如果是命题,指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗? ⑶不存在最大素数。 ⑷21+3<5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以 。 ⑾只有6是偶数,3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨,他就乘班车上班。 解:⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题,其中⑴⑶⑽⑾是真命题,⑷⑹⑿是假命题,⑸⑺⒀的真值目前无法确定;⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷,所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影,那么我也不看电影。 ⑺我既不看电视也不外出,我在睡觉。 ⑻除非天下大雨,否则他不乘班车上班。 解:⑴本命题为原子命题; ⑵p:天气冷;q:我穿羽绒服; ⑶p:天在下雨;q:湿度很高; ⑷p:刘英上山;q:李进上山; ⑸p:王强学过法语;q:刘威学过法语; ⑹p:你看电影;q:我看电影; ⑺p:我看电视;q:我外出;r:我睡觉; ⑻p:天下大雨;q:他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭,一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木,则人类不能生存。 ⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数,则a+b是偶数。 解:⑴p:他吃饭;q:他听音乐;原命题符号化为:p∧q ⑵p:3是素数;q:2是素数;原命题符号化为:p∨q ⑶p:地球上有树木;q:人类能生存;原命题符号化为:?p→?q ⑷p:8是偶数;q:8能被3整除;原命题符号化为:p?q ⑸p:停机;q:语法错误;r:程序错误;原命题符号化为:q∨r→p ⑹p:四边形ABCD是平行四边形;q:四边形ABCD的对边平行;原命题符号化为:p?q。 ⑺p:a是偶数;q:b是偶数;r:a+b是偶数;原命题符号化为:p∧q→r 4. 将下列命题符号化,并指出各复合命题的真值。 ⑴如果3+3=6,则雪是白的。 ⑵如果3+3≠6,则雪是白的。 ⑶如果3+3=6,则雪不是白的。 ⑷如果3+3≠6,则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1,O2的面积相等,则它们的半径相等,反之亦然。 ⑻当王小红心情愉快时,她就唱歌,反之,当她唱歌时,一定心情愉快。 解:设p:3+3=6。q:雪是白的。 ⑴原命题符号化为:p→q;该命题是真命题。 ⑵原命题符号化为:?p→q;该命题是真命题。 ⑶原命题符号化为:p→?q;该命题是假命题。 ⑷原命题符号化为:?p→?q;该命题是真命题。 ⑸p:3是无理数;q:加拿大位于亚洲;原命题符号化为:p?q;该命题是假命题。 ⑹p:2+3=5;q:3是无理数;原命题符号化为:p?q;该命题是真命题。 ⑺p:两圆O1,O2的面积相等;q:两圆O1,O2的半径相等;原命题符号化为:p?q;该命题是真命题。 ⑻p:王小红心情愉快;q:王小红唱歌;原命题符号化为:p?q;该命题是真命题。离散数学课后习题答案
离散数学课后习题答案_(左孝凌版)
屈婉玲版离散数学课后习题答案
离散数学(左孝凌)课后习题解答(详细)