离散数学 答案 左孝凌 上海科学技术文献出版社
更新时间:2023-10-24 06:25:01 阅读量: 综合文库 文档下载
- 离散数学推荐度:
- 相关推荐
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 T T T T F F F T F T F T F F F F T F F F F F F F T 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 T T T T F T T T T T F T T T T T T F F F T T T F T T T T T T F T F T T T T F F T T T F T F F F F F F F 所以,P∨(Q∨R) ? (P∨Q)∨R c) P Q R Q∨R P∧(Q∨R) P∧Q P∧R (P∧Q)∨(P∧R) T T T T T F T F T T T T T T T T T F T T F T T F T T F F F F F F F T T F F F F T T F F F F F T T F F F F F F F F F 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 F F F F F F T F F T T T F F F T T F T T F F F F T T T T T 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) P Q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 F F F T F T F T F T F T F T F T F T F T F F T T F F T T F F T T F F T T T F F F F F T T T T F F F F T 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) 1 ?┐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) 解:
(1) ┐R P (2) ┐Q∨R P
(3) ┐Q (1)(2)T,I (4) ┐(P∧┐Q) P (5) ┐P∨Q (4)T,E (6) ┐P (3)(5)T,I
b)J→(M∨N),(H∨G)→J,H∨G?M∨N (1) (H∨G) →J P (2) (H∨G) P
(3) J (1)(2)T,I (4) J→(M∨N) P (5) M∨N (3)(4)T,I c)B∧C,(B?C)→(H∨G)?G∨H (1) B∧C P (2) B (1)T,I (3) C (1)T,I (4) B∨┐C (2)T,I (5) C∨┐B (3)T,I (6) C→B (4)T,E (7) B→C (5)T,E (8) B?C (6)(7)T,E (9) (B?C) →(H∨G) P (10) H∨G (8)(9)T,I
d)P→Q,(┐Q∨R)∧┐R,┐(┐P∧S)?┐S (1) (┐Q∨R) ∧┐R (2) ┐Q∨R (1)T,I (3) ┐R (1)T,I (4) ┐Q (2)(3)T,I (5) P→Q P
(6) ┐P (4)(5)T,I (7) ┐(┐P∧┐S) P (8) P∨┐S (7)T,E (9) ┐S (6)(8)T,I (2) 证明:
a)┐A∨B,C→┐B?A→┐C
(1) ┐(A→┐C) P (2) A (1)T,I (3) C (1)T,I (4) ┐A∨B P
(5) B (2)(4)T,I (6) C→┐B P
(7) ┐B (3)(6)T,I (8) B∧┐B 矛盾。(5),(7)
b)A→(B→C),(C∧D)→E,┐F→(D∧┐E)?A→(B→F) (1) ┐(A→(B→F)) P (2) A (1)T,I (3) ┐(B→F) (1)T,I (4) B (3)T,I (5) ┐F (3)T, (6) A→(B→C) P
(7) B→C (2)(6)T,I (8) C (4)(7)T,I (9) ┐F→(D∧┐E) P
(10) D∧┐E (5)(9)T,I (11) D (10)T,I (12) C∧D (8)(11)T,I (13) (C∧D) →E P
(14) E (12)(13)T,I (15) ┐E (10)T,I
(16) E∧┐E 矛盾。(14),(15) c)A∨B→C∧D,D∨E→F?A→F
(1) ┐(A→F) P (2) A (1)T,I (3) ┐F (1)T,I (4) A∨B (2)T,I (5) (A∨B) →C∧D P
(6) C∧D (4)(5)T,I (7) C (6)T,I (8) D (6)T,I (9) D∨E (8)T,I (10) D∨E→F P
(11) F (9)(10)T,I (12) F∧┐F 矛盾。(3),(11)
d)A→(B∧C),┐B∨D,(E→┐F)→┐D,B→(A∧┐E)?B→E (1) ┐(B→E) P (2) B (1)T,I (3) ┐E (1)T,I (4) ┐B∨D P
(5) D (2)(4)T,I (6) (E→┐F) →┐D P
(7) ┐(E→┐F) (5)(6)T,I (8) E (7)T,I (9) E∧┐E 矛盾
e)(A→B)∧(C→D),(B→E)∧(D→F),┐(E∧F),A→C?┐A (1) (A→B) ∧(C→D) P (2) A→B (1)T,I (3) (B→E) ∧(D→F) P (4) B→E (3)T,I (5) A→E (2)(4)T,I (6) ┐(E∧F) P (7) ┐E∨┐F (6)T,E (8) E→┐F (7)T,E (9) A→┐F (5)(8)T,I (10) C→D (1)T,I (11) D→F (3)T,I
(12) C→F (10)(10)T,I (13) A→C P
(14) A→F (13)(12)T,I (15) ┐F→┐A (14)T,E (16) A→┐A (9)(15)T,I (17) ┐A∨┐A (16)T,E (18) ┐A (17) T,E (3) 证明:
a)┐A∨B,C→┐B?A→┐C
(1) A P (2) ┐A∨B P
(3) B (1)(2)T,I (4) C→┐B P
(5) ┐C (3)(4)T,I (6) A→┐C CP
b)A→(B→C),(C∧D)→E,┐F→(D∧┐E)?A→(B→F)
(1) A P (2) A→(B→C) P
(3) B→C (1)(2)T,I (4) B P
(5) C (3)(4)T,I (6) (C∧D) →E P (7) C→(D→E) (6)T,E (8) D→E (5)(7)T,I (9) ┐D∨E (8)T,E (10) ┐(D∧┐E) (9)T,E (11) ┐F→(D∧┐E) P
(12) F (10)(11)T,I (13) B→F CP (14) A→(B→F) CP c)A∨B→C∧D,D∨E→F?A→F
(1) A P
(2) A∨B (1)T,I (3) A∨B→C∨D P
(4) C∧D (2)(3)T,I (5) D (4)T,I (6) D∨E (5)T,I
(7) D∨E→F P
(8) F (6)(7)T,I (9) A→F CP
d)A→(B∧C),┐B∨D,(E→┐F)→┐D,B→(A∧┐E)?B→E
(1) B P(附加前提) (2) ┐B∨D P
(3) D (1)(2)T,I (4) (E→┐F)→┐D P
(5) ┐(E→┐F) (3)(4)T,I (6) E (5)T,I (7) B→E CP (4)证明:
a) R→┐Q,R∨S,S→┐Q,P→Q?┐P (1) R→┐Q P (2) R∨S P (3) S→┐Q P
(4) ┐Q (1)(2)(3)T,I (5) P→Q P
(6) ┐P (4)(5)T,I b) S→┐Q,S∨R,┐R,┐P?Q?P 证法一:
(1) S∨R P (2) ┐R P
(3) S (1)(2)T,I (4) S→┐Q P (5) ┐Q (3)(4)T,I (6) ┐P?Q P (7)(┐P→Q)∧(Q→┐P) (6)T,E (8) ┐P→Q (7)T,I (9) P (5)(8)T,I 证法二:(反证法)
(1) ┐P P(附加前提) (2) ┐P?Q P
(3)(┐P→Q)∧( Q→┐P) (2)T,E (4) ┐P→Q (3)T,I (5) Q (1)(4)T,I (6) S→┐Q P
(7) ┐S (5)(6)T,I (8) S∨R P
(9) R (7)(8)T,I (10) ┐R P
(11) ┐R∧R 矛盾(9)(10)T,I c)┐(P→Q)→┐(R∨S),((Q→P)∨┐R),R?P?Q (1) R P (2) (Q→P) ∨┐R P
(3) Q→P (1)(2)T,I (4)┐(P→Q) →┐(R∨S) P (5) (R∨S) →(P→Q) (4)T,E (6) R∨S (1)T,I (7) P→Q (5)(6) (8) (P→Q) ∧(Q→P) (3)(7)T,I (9) P?Q (8)T,E (5) 解:
a) 设P:我跑步。Q:我很疲劳。 前提为:P→Q,┐Q
(1) P→Q P (2) ┐Q P (3) ┐P (1)(2)T,I 结论为:┐P,我没有跑步。
b) 设S:他犯了错误。 R:他神色慌张。 前提为:S→R,R
因为(S→R)∧R?(┐S∨R)∧R?R。故本题没有确定的结论。 实际上,若S →R为真,R为真,则S可为真,S也可为假,故无有效结论。
c) 设P:我的程序通过。 Q:我很快乐。
R:阳光很好。 S:天很暖和。(把晚上十一点理解为阳光不
好)
前提为:P→Q,Q→R,┐R∧S
(1) P→Q P (2) Q→R P
(3) P→R (1)(2)T,I (4) ┐R∨S P
(5) ┐R (4)T,I (6) ┐P (3)(5)T,I
结论为: ┐P,我的程序没有通过
习题2-1,2-2 (1) 解:
a) 设W(x):x是工人。c:小张。 则有 ?W(c) b) 设S(x):x是田径运动员。B(x):x是球类运动员。h:他则有 S(h)?B(h) c) 设C(x):x是聪明的。B(x):x是美丽的。l:小莉。 则有 C(l)? B(l) d)设O(x):x是奇数。 则有 O(m)?? O(2m)。 e)设R(x):x是实数。Q(x):x是有理数。 则有 (?x)(Q(x)?R(x)) f) 设R(x):x是实数。Q(x):x是有理数。 则有 (?x)(R(x)?Q(x)) g) 设R(x):x是实数。Q(x):x是有理数。 则有 ?(?x)(R(x)?Q(x)) h)设P(x,y):直线x平行于直线y G(x,y):直线x相交于直线y。 则有 P(A,B)??G(A,B) (2) 解:
a) 设J(x):x是教练员。L(x):x是运动员。 则有 (?x)(J(x)?L(x))
b) 设S(x):x是大学生。L(x):x是运动员。 则有 (?x)(L(x)?S(x))
c) 设J(x):x是教练员。O(x):x是年老的。V(x):x是健壮的。 则有 (?x)(J(x)?O(x)?V(x)) d) 设O(x):x是年老的。V(x):x是健壮的。j:金教练 则有 ? O(j)??V(j)
e) 设L(x):x是运动员。J(x):x是教练员。 则 ?(?x)(L(x)?J(x))
本题亦可理解为:某些运动员不是教练。 故 (?x)(L(x)??J(x)) f) 设S(x):x是大学生。L(x):x是运动员。C(x):x是国家选手。 则有 (?x)(S(x)?L(x)?C(x)) g) 设C(x):x是国家选手。V(x):x是健壮的。 则有 (?x)(C(x)?V(x))或?(?x)(C(x)??V(x)) h) 设C(x):x是国家选手。O(x):x是老的。L(x):x 是运动员。 则有 (?x)(O(x)?C(x)?L(x)) i) 设W(x):x是女同志。H(x):x是家庭妇女。C(x):x是国家选手。
则有 ?(?x)(W(x)?C(x)?H(x)) j)W(x):x是女同志。J(x):x是教练。C(x):x是国家选手。 则有(?x)(W(x)?J(x)?C(x)) k)L(x):x 是运动员。J(y):y是教练。A(x,y):x钦佩y。 则有 (?x)(L(x)? (?y)(J(y)?A(x,y))) l)设S(x):x是大学生。L(x):x 是运动员。A(x,y):x钦佩y。 则(?x)(S(x)?(?y)(L(y)?? A(x,y)))
习题2-3 (1)解:
a)5是质数。
b)2是偶数且2是质数。
c)对所有的x,若x能被2除尽,则x是偶数。 d)存在x,x是偶数,且x能除尽6。(即某些偶数能除尽6) e)对所有的x,若x不是偶数,则x不能被2除尽。
f)对所有的x,若x是偶数,则对所有的y,若x能除尽y,则y也是偶数。
g)对所有的x,若x是质数,则存在y,y是偶数且x能除尽y(即所有质数能除尽某些偶数)。
h)对所有的x,若x是奇数,则对所有y,y是质数,则x不能除尽y(即任何奇数不能除尽任何质数)。 (2)解:(?x)(?y)((P(x)∧P(y)∧┐E(x,y)→(?!z)(L(z)∧R(x,y,z))) 或 (?x)(?y)((P(x)∧P(y)∧┐E(x,y)→(?z)(L(z)∧R(x,y,z) ∧┐(?u)(┐E(z,u) ∧L(u)∧R(x,y,u)))) (3)解:
a) 设N(x):x是有限个数的乘积。 z(y):y为0。
P(x):x的乘积为零。 F(y):y是乘积中的一个因子。
则有 (?x)((N(x)∧P(x)→(?y)(F(y)∧z(y)))
b) 设R(x):x是实数。Q(x,y):y大于x。 故 (?x)(R(x)→(?y)(Q(x,y)∧R(y)))
c) R(x):x是实数。G(x,y):x大于y。 则 (?x)(?y)(?z)(R(x)∧R(y)∧R(z)∧G(x+y,x·z)
(4)解:设G(x,y):x大于y。则有 (?x)(?y)(?z)(G(y,x) ∧G(0,z)→G(x·z,y·z))
(5)解:设N(x):x是一个数。 S(x,y):y是x的后继数。E(x,y):x=y.则
a) (?x)(N(x)→(?!y)(N(y)∧S(x,y)))
或(?x)(N(x)→(?y)(N(y)∧S(x,y) ∧┐(?z)(┐E(y,z) ∧N(z)∧S(x,z))))
b) ┐(?x)(N(x)∧S(x,1))
c) (?x)(N(x)∧┐S(x,2)→(?!y)(N(y) ∧S(y,x)))
或(?x)(N(x)∧┐S(x,2)→(?y)(N(y) ∧S(y,x) ∧┐(?z)(┐E(y,z) ∧N(z)∧S(z,x))))
(6)解:设S(x):x是大学生。 E(x):x是戴眼睛的。
F(x):x是用功的。 R(x,y):x在看y。
G(y):y是大的。 K(y):y是厚的。 J(y):y是巨著。 a:这
本。 b:那位。
则有 E(b)∧F(b)∧S(b)∧R(b,a)∧G(a)∧K(a)∧J(a)
(7)解:设P(x,y):x在y连续。 Q(x,y):x>y。则
P(f,a)?((?ε)(?δ)(?x)(Q(ε,0)→(Q(δ,0)∧Q(δ,|x-a|)→Q(ε,|f(x)-f(a)|))))
习题2-4
(1) 解:a) x是约束变元,y是自由变元。 b) x是约束变元,P(x)∧Q(x)中的x受全称量词?的约束,S(x)中的x受存在量词?的约束。
c) x,y都是约束变元,P(x)中的x受?的约束,R(x)中的x受?的约束。 d) x,y是约束变元,z是自由变元。 (2) 解:a) P(a)∧P(b)∧P(c) b) R(a)∧R(b)∧R(c)∧S(a)∧S(b)∧S(c) c) (P(a)→Q(a))∧(P(b)→Q(b))∧(P(c)→Q(c) d) (┐P(a)∧┐P(b)∧┐P(c))∨(P(z)∧P(b)∧P(c)) e) (R(a)∧R(b)∧R(c))∧(S(a)∨S(b)∨S(c)) (3) 解: a) (?x)(P(x)∨Q(x))?(P(1)∨Q(1))∧(P(2)∨Q(2)), 但P(1)为T,Q(1)为F,P(2)为F,Q(2)为T,所以 (?x)(P(x)∨Q(x))?(T∨F)∧(F∨T)??T。 b) (?x)(P→Q(x))∨R(a)? ((P→Q(?2))∧(P→Q(3))∧(P→Q(6)))∨R(a) 因为P 为T,Q(?2)为T,Q(3)为T,Q(6)为F,R(5)为F,所以 (?x)(P→Q(x))∨R(a)? ((T→T)∧(T→T)∧(T→F))∨F? F (4) 解:a) (?u)(?v)(P(u,z)→Q(v))?S(x,y) b) (?u)(P(u)→ (R(u)∨Q(u))∧(?v)R(v))→(?z)S(x,z) (5) 解:a) ((?y)A(u,y)→(?x)B(x,v))∧(?x)(?z)C(x,t,z) b) ((?y)P(u,y)∧(?z)Q(u,z))∨(?x)R(x,t)
习题2-5 (1)解: a) P(a,f(a))∧P(b,f(b))?P(1,f(1))∧P(2,f(2))?P(1,2)∧P(2,1)??T∧F?F
b) (?x)(?y)P(y,x)? (?x) (P(1,x)∨P(2,x))? (P(1,1)∨P(2,1))∧(P(1,2)∨P(2,2))
? (T∨F)∧(T∨F)?? T
c) (?x)( ?y)(P(x,y)→P(f(x),f(y)))??? (?x) ((P(x,1)→P(f(x),f(1)))∧(P(x,2) →P(f(x)f(2))))
? (P(1,1)→P(f(1),f(1)))∧(P(1,2)→P(f(1),f(2))) ∧(P(2,1)→P(f(2),f(1)))∧(P(2,2) →P(f(2),f(2)))
? 前提:对论域中所有x,如果x不是研究生则x是大学生。
对论域中所有x, x不是大学生。
结论:对论域中所有x都是研究生。
(P(1,1)→P(2,2))∧(P(1,2)→P(2,1))∧(P(2,1)→P(1,2))∧(P(2,2)→P(1,1)) ? (T→F∧(T→F)∧(F→T)∧(F→T)?F∧F∧T∧T?F (2)解:a) (?x)(P(x)→Q(f(x),a))??
?(P(1)→Q(f(1),1))∧(P(2)→Q(f(2),1)) ? (F→Q(2,1))∧(T→Q(1,1))??? (F→F)∧(T→T)??T b) (?x)(P(f(x))∧Q(x,f(a))??? (P(f(1))∧Q(1,f(1)))∨(P(f(2))∧Q(2,f(1)) ? (T∧T)(F∧F)??T
c) (?x)(P(x)∧Q(x,a)) ? (P(1)∧Q(1,a))∨(P(2)∧Q(2,a)) ? (P(1)∧Q(1,1))∨(P(2)∧Q(2,1))??? (F∧T)∨(T∧F)??F d) (?x)( ?y)(P(x)∧Q(x,y))??? (?x) (P(x)∧(?y)Q(x,y))??? (?x) (P(x)∧(Q(x,1)∨Q(x,2))) ? (P(1)∧(Q(1,1)∨Q(1,2)))∧(P(2)∧(Q(2,1)∨Q(2,2))) ? (F∧(T∨T))∧(T∧(F∨F))??F
(3) 举例说明下列各蕴含式。
a) ?((?x)(P(x)∧Q(a))? (?x)P(x)??Q(a) b) (?x) (? P(x) ?Q(x)), (?x) ?Q(x)?P(a)
c) (?x) (P(x) ?Q(x)), (?x) (Q(x) ?R(x))? (?x) (P(x) ?R(x)) d) (?x) (P(x) ?Q(x)), (?x) ?P(x)? (?x)Q (x) e) (?x) (P(x) ?Q(x)), (?x) ?P(x)? (?x)Q (x) 解:a)因为?((?x)(P(x)∧Q(a)) ??(?x)P(x)∨?Q(a) 故原式为?(?x)P(x)∨?Q(a) ? (?x)P(x)??Q(a) 设P(x):x是大学生。Q(x):x是运动员
前提 或者不存在x,x是大学生,或者a是运动员 结论 如果存在x是大学生,则必有a是运动员。 b)设P(x):x是研究生。Q(x):x是大学生。a:论域中的某人。 故,对论域中某个a,必有结论a是研究生,即P(a)成立。 c)设P(x):x是研究生。Q(x):x曾读过大学。R(x):x曾读过中学。
前提 对所有x,如果x是研究生,则x曾读过大学。
对所有x,如果x曾读过大学,则x曾读过中学。
结论:对所有x,如果x是研究生,则x曾读过中学。 d)设P(x):x是研究生。Q(x):x是运动员。
前提 对所有x,或者x是研究生,或者x是运动员。
对所有x,x不是研究生
结论 必存在x,x是运动员。 e)设P(x):x是研究生。Q(x):x是运动员。
前提 对所有x,或者x是研究生,或者x是运动员。
对所有x,x不是研究生
结论 对所有x,x是运动员。 (4)证明:(?x)(A(x)→B(x))? (?x) (┐A(x)∨B(x)) ? (?x)┐A(x)∨ (?x) B(x)
? ┐(?x)A(x)∨(?x) B(x) ? (?x)A(x)→(?x) B(x)
(5) 设论域D={a,b,c},求证(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x)) 证明:因为论域D={a,b,c},所以
(?x)A(x)∨(?x)B(x) ?(A(a) ∧A(b) ∧A(c)) ∨(B(a) ∧B(b) ∧B(c)) ?(A(a) ∨B(a)) ∧(A(a) ∨B(b)) ∧(A(a) ∨B(c)) ∧(A(b) ∨B(a)) ∧
(A(b) ∨B(b)) ∧(A(b)∨B(c)) ∧(A(c) ∨B(a)) ∧(A(c) ∨B(b)) ∧(A(c) ∨B(c))
?(A(a) ∨B(a)) ∧(A(b) ∨B(b))∧(A(c) ∨B(c)) ?( ?x)(A(x)∨B(x))
所以(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x)) (6)解:推证不正确,因为
┐(?x)(A(x)∧┐B(x))?┐((?x)A(x)∧(?x)┐B(x)) (7)求证(?x)( ?y)(P(x)→Q(y)) ? ( ?x)P(x)→(?y)Q(y) 证明:(?x)( ?y)(P(x)→Q(y))
∨
?(?x)( ?y)( ┐P(x) ∨Q(y)) ?(?x) ┐P(x) ∨( ?y)Q(y) ?┐(?x)P(x) ∨( ?y)Q(y) ? ( ?x)P(x)→(?y)Q(y)
习题2-6
(1)解:a) (?x)(P(x)→(?y)Q(x,y))
?(?x)( ┐P(x) ∨(?y)Q(x,y)) ?(?x) (?y) (┐P(x) ∨Q(x,y))
b) (?x)(┐((?y)P(x,y))→((?z)Q(z)→R(x))) ?(?x)((?y)P(x,y)∨((?z)Q(z)→R(x)))
?(?x)((?y)P(x,y) ∨(┐(?z)Q(z) ∨R(x))) ?(?x)((?y)P(x,y) ∨((?z)┐Q(z) ∨R(x))) ?(?x) (?y) (?z) ( P(x,y) ∨┐Q(z) ∨R(x))
c)(?x)( ?y)(((?zP(x,y,z)∧(?u)Q(x,u))→(?v)Q(y,v))
?(?x)( ?y)( ┐((?z)P(x,y,z)∧(?u)Q(x,u))∨(?v)Q(y,v)) ?(?x)( ?y)( (?z)┐P(x,y,z) ∨(?u)┐Q(x,u)∨(?v)Q(y,v)) ?(?x)( ?y)( (?z)┐P(x,y,z) ∨(?u)┐Q(x,u)∨(?v)Q(y,v)) ?(?x)( ?y) (?z) (?u) (?v) (┐P(x,y,z) ∨┐Q(x,u)∨Q(y,v)) (2)解:a) ((?x)P(x)∨(?x)Q(x))→(?x)(P(x)∨Q(x))
?┐((?x)P(x)∨(?x)Q(x)) ∨(?x)(P(x)∨Q(x)) ?┐(?x) (P(x)∨Q(x)) ∨(?x)(P(x)∨Q(x)) ?T b) (?x)(P(x)→(?y)((?z)Q(x,y)→┐(?z)R(y,x))) ?(?x)( ┐P(x) ∨(?y)( Q(x,y)→┐R(y,x))) ?(?x) (?y) ( ┐P(x) ∨┐Q(x,y) ∨┐R(y,x)) 前束合取范式
?(?x) (?y)( (P(x) ∧Q(x,y) ∧R(y,x)) ∨(P(x) ∧Q(x,y) ∧┐R(y,x)) ∨ (P(x) ∧┐Q(x,y) ∧R(y,x)) ∨(┐P(x) ∧Q(x,y) ∧R(y,x)) ∨(┐P(x) ∧┐Q(x,y) ∧R(y,x)) ∨( (P(x) ∧┐Q(x,y) ∧┐R(y,x)) ∨(┐P(x) ∧Q(x,y) ∧┐R(y,x))) 前束析取范式
c) (?x)P(x)→(?x)((?z)Q(x,z)∨(?z)R(x,y,z)) ?┐(?x)P(x) ∨(?x)((?z)Q(x,z)∨(?z)R(x,y,z)) ?(?x)┐P(x) ∨(?x)((?z)Q(x,z)∨(?u)R(x,y,u)) ?(?x)(┐P(x) ∨(?z)Q(x,z)∨(?u)R(x,y,u)) ?(?x) (?z) (?u)(┐P(x) ∨Q(x,z)∨R(x,y,u)) 前束合取范式
?(?x) (?z) (?u)(( P(x) ∧Q(x,z) ∧R(x,y,u)) ∨(P(x) ∧Q(x,z) ∧┐R(x,y,u)) ∨(P(x) ∧┐Q(x,z) ∧R(x,y,u)) ∨(P(x) ∧┐Q(x,z) ∧┐R(x,y,u)) ∨(┐P(x) ∧Q(x,z) ∧┐R(x,y,u)) ∨(┐P(x) ∧┐Q(x,z) ∧R(x,y,u)) ∨(┐P(x) ∧┐Q(x,z) ∧┐R(x,y,u))) 前束析取范式
d)(?x)(P(x)→Q(x,y))→((?y)P(y)∧(?z)Q(y,z))
?┐(?x)( ┐P(x) ∨Q(x,y)) ∨((?y)P(y)∧(?z)Q(y,z)) ?(?x)( P(x) ∧┐Q(x,y)) ∨((?u)P(u)∧(?z)Q(y,z)) ?(?x) (?u) (?z) (( P(x) ∧┐Q(x,y)) ∨(P(u)∧Q(y,z))) 前束析取范式
?(?x) (?u) (?z) (( P(x)∨P(u)) ∧ (P(x)∨Q(y,z)) ∧(┐Q(x,y)∨P(u)) ∧ (┐Q(x,y)∨Q(y,z))) 前束合取范式
习题2-7 (1) 证明:
(2) a) ①(?x)(┐A(x)→B(x)) P
②┐A(u)→B(u) US① ③( ?x)┐B(x) P ④┐B(u) US③ ⑤A(u)∨B(u) T②E ⑥A(u) T④⑤I ⑦ ( ?x)A(x) EG⑥
b) ①┐( ?x)(A(x)→B(x)) P(附加前提) ②( ?x)┐(A(x)→B(x)) T①E ③┐(A(c)→B(c)) ES② ④A(c) T③I ⑤┐B(c) T③I ⑥( ?x)A(x) EG④ ⑦ (?x)A(x)→(?x)B(x) P
⑧(?x)B(x) T⑥⑦I ⑨B(c) US⑧ ⑩B(c)∧ ┐B(c) T⑤⑨矛盾 c)①(?x)(A(x)→B(x)) P ②A(u)→B(u) US① ③( ?x)(C(x)→┐B(x)) P ④C(u)→┐B(u) US③ ⑤┐B(u) →┐A(u) T②E ⑥C(u)→┐A(u) T④⑤I ⑦(?x)(C(x)→┐A(x)) UG⑥
d) (?x)(A(x)∨B(x)),( ?x)(B(x)→┐C(x)),( ?x)C(x)? (?x)A(x) ①( ?x)(B(x)→┐C(x)) P
②B(u)→┐C(u) US① ③( ?x)C(x) P
④C(u) US③ ⑤┐B(u) T②④I ⑥ (?x)(A(x)∨B(x)) P ⑦A(u)∨B(u) US
⑧A(u) T⑤⑦I ⑨(?x)A(x) UG⑧ (2) 证明:
a)①( ?x)P(x) P(附加前提)②P(u) US① ③(?x)(P(x)→Q(x)) P ④P(u)→Q(u) US③ ⑤Q(u) T②④I ⑥(?x)Q(x) UG⑤ ⑦( ?x)P(x)→(?x)Q(x) CP b)因为(?x)P(x)∨(?x)Q(x)?┐(?x)P(x) →(?x)Q(x)
故本题就是推证(?x)(P(x)∨Q(x))?? ┐(?x)P(x) →(?x)Q(x) ①┐(?x)P(x) P(附加前提) ②( ?x)┐P(x) T①E ③┐P(c) ES② ④(?x)(P(x)∨Q(x)) P ⑤P(c)∨Q(c) ES④ ⑥Q(c) T③⑤I ⑦( ?x) Q(x) EG⑥ ⑧┐(?x)P(x) →(?x)Q(x) CP (3)
解:a)设R(x):x是实数。Q(x):x是有理数。I(x):x是整数。 本题符号化为:
(?x)(Q(x) →R(x)) ∧(?x)(Q(x) ∧I(x))?? (?x)(R(x) ∧I(x)) ①(?x)(Q(x) ∧I(x)) P ②Q(c) ∧I(c) ES① ③(?x)(Q(x) →R(x)) P
④Q(c) →R(c) US③ ⑤Q(c) T②I ⑥ R(c) T④⑤I ⑦I(c) T②I ⑧R(c)∧I(c) T⑥⑦I ⑨(?x)(R(x) ∧I(x)) EG⑧ b)设P(x):x喜欢步行。Q(x):x喜欢乘汽车。R(x):x喜欢骑自行车
本题符号化为:
(?x)(P(x) →┐Q(x)), (?x)(Q(x) ∨R(x)) , (?x) ┐R(x)?? (?x) ┐P(x) ①(?x) ┐R(x) P ②┐R (c) ES① ③(?x)(Q(x) ∨R(x)) P ④Q(c) ∨R(c) US③
⑤Q(c) T②④I ⑥ (?x)(P(x) →┐Q(x)) P ⑦P(c) →┐Q(c) US⑥ ⑧┐P (c) T⑤⑦I ⑨(?x) ┐P(x) EG⑧
c) 每个大学生不是文科学生就是理工科学生,有的大学生是优等生,小张不是理工科学生,但他是优等生,因而如果小张是大学生,他就是文科学生。 设G(x):x是大学生。L(x):x是文科学生。P(x):x是理工科学生。S(x):x是优秀生。c:小张。 本题符号化为:
(?x)(G(x) →L(x)∨P(x)), (?x)(G(x) ∧ S(x)), ┐P (c) , S(c) ? G(c) →L(c)
①G(c) P(附加前提) ②(?x)(G(x) →L(x)∨P(x)) P ③G(c) →L(c)∨P(c) US② ④L(c)∨P(c) T①③I ⑤┐P (c) P
⑥ L(c) T④⑤I ⑦G(c) →L(c) CP 注意:本题推证过程中未用到前提(?x)(G(x) ∧ S(x))以及S(c)。主要是S(x):x是优秀生,这个条件与其他前提的联系对证明结论没有影响,因S(x)与其他前提不矛盾,故本题的推证仍是有效的。
3-5.1 列出所有从X={a,b,c}到Y={s}的关系。 解:Z1={} Z2={} Z3={
3-8.1 根据图3-8.1中的有向图,写出邻接矩阵和关系R,并求出R的自反闭包和对称闭包。 解 a M1 1 0 R= 0 0 1 b c 0 1 0 图3-8.1 R={<a,a>,<a,b>,<b,c>,<c,b>= r(R)= R∪IX ={<a,a>,<b,b>,<c,c>,<a,b>,<b,c>,<c,b>= s(R)= R∪RC={<a,a>,<a,b>,<b,a>,<b,c>,<c,b>} 3-8.2 设集合A={a,b,c,d}A上的关系 R={<a,b>,<b,a>,<b,c>,<c,d>} a) 用矩阵运算和作图方法求出R的自反、对称、传递闭包; b) 用Warshall算法,求出R的传递闭包。 解 a) 0 1 0 0 MR= 1 0 1 0 0 0 0 1 0 0 0 0 R的关系图如图所示。 a b d c M0 1 0 0 1 0 0 0 1 1 0 0 R+MIA= 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 + 0 0 1 0 = 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 r(R)= R∪IA ={<a,a>,<a,b>,<b,a>,<b,b>,<b,c>,<c,c>,<c,d>,<d,d>}(图(a)) a b d c 图(a) 0 1 0 0 0 1 0 0 0 1 0 0 MR+MRc= 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 + 0 1 0 0 = 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 3-9.1 4个元素的集合共有多少不同的划分。 解 整数4可划分为:4,1+3,1+1+2,2+2,1+1+1+1。 1+C12+14+C4 C224+1=15(种) 3-9.2 设{A1,A2,?,Ak}是集合A的一个划分,我们定义A上的一个二元关系R,使<a,b>∈R当且仅当a和b在这个划分的同一块中。证明R是自反的,对称的,和传递的。 证明 设对任意a∈A,则必存在Ai,使a∈Ai,因a与a必可看作在同一块中,故有<a,a>∈R。即R是自反的。 设a,b∈A,若有<a,b>∈R,则a与b必在同一块,故b与a亦在同一块,<b, a>∈R,即R是对称的。 对任意a,b,c∈A, <a,b>∈R∧<b,c>∈R ?(?i)(a∈Ai∧b∈Ai)∧(?j)(b∈Aj∧c∈Aj) ?(?i)(?j)(a∈Ai∧c∈Aj∧b∈Ai∩Aj) ?(?i)(?j)(a∈Ai∧c∈Aj∧Ai∩Aj≠?) ?(?i)(?j)(a∈Ai∧c∈Aj∧i=j)(∵i≠j?Ai∩Aj= ?) ?a,c在同一块 ?<a,c>∈R ∴R传递 3-10.1 设R和R′是集合A上的等价关系,用例子说明:R∪R′不一定是等价关系。 证明 设 A={1,2,3},S=R∪R′ R={<1,1>,<2,2>,<3,3>,<3,1>,<1,3>} R′={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>} 则R∪R′={<1,1>,<2,2>,<3,3>,<3,1>,<1,3>,<3,2>,<2,3>} 因为如<2,3>∈S∧<3,1>∈S,但<2,1>?S,故R∪R′不是传递的,即R∪R′不是A上的等价关系。 3-10.2 试问由4个元素组成的有限集上所有等价关系的个数为多少? 解 因为集合X上的等价关系与X的划分是一一对应的,所以4个元素的有限集上等价关系证明 设A上定义的二元关系R为:
xu
<<x,y>, <u,v>>∈R? =
yvxx
① 对任意<x,y>∈A,因为 = ,所以
yy的数目,与4个元素集合进行划分的数目是相同的,由习题3-9.1可知共有15个不同的等价关系。 3-10.3 给定集合S={1,2,3,4,5},找出S上的等价关系R,此关系R能产生划分{{1,2},{3},{4,5}},并画出关系图。 解 我们可用如下方法产生一个等价关系: R1={1,2}×{1,2}={<1,1>,<1,2>,<2,1>,<2,2>} R2={3}×{3}={<3,3>} R3={4,5}×{4,5}={<4,4>,<4,5>,<5,4>,<5,5>} R= R1∪R2∪R3={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>} 关系图如图。 3-10.4 设R是一个二元关系,S={<a,b>∣对于某一c,有<a,c>∈R∧<c,b>∈R},证明若R是一个等价关系,则S也是一个等价关系。 证明 设R是A上的等价关系: (1) 对任一x∈A,因为R在A上自反,所以<x,x>∈R。由S定义,<x,x>∈S,所以S是自反的。 (2) 对任意x,y∈A,若<x,y>∈S,则存在某个c,使得<x,c>∈R∧<c,y>∈R,因为R是对称,故有:<y,c>∈R∧<c,x>∈R,由S的定义,可知<y,x>∈S,所以S是对称的。 (3) 对任意x,y,z∈A,若<x,y>∈S,及<y,z>∈S,则必存在某个c1,使<x,c1>∈R,<c1,y>∈R。由R的传递性,可知<x,y>∈R,同理存在c2,使<y,c2>∈R∧<c2,z>∈R,由R传递,可知<y,z>∈R。再由S定义,得<x,z>∈S。故S是传递的。 3-10.5 设正整数的序偶集合A,在A上定义二元关系R如下:<<x,y>, <u,v>>∈R,当且仅当xv=yu,证明R是一个等价关系。
<<x,y>, <x,y>>∈R 即R是自反的。
② 设<x,y>∈A,<u,v>∈A,若
<<x,y>, <u,v>>∈R?xuux
y =v ?v =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
?(xuuwxwy =v )∧(v =s )?y =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)R21;
d) r(R1-R2)(即R1-R2的自反闭包)。 解 a)(A×A)-R1不是A上等价关系。例如:
A={a,b},R1={<a,a>,<b,b>}
A×A={<a,a>,<a,b>,<b,a>,<b,b>} (A×A)-R1={<a,b>,<b,a>} 所以(A×A)-R1不是A上等价关系。 b)设 A={a,b,c}
R1={<a,b>,<b,a>,<b,c>,<c,b>,<a,c>,<c,a>,
<a,a>,<b,b>,<c,c>}
R2={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>} R1-R2={<a,b>,<b,a>,<a,c>,<c,a>}
所以R1和R2是A上等价关系,但R1-R2不是A上等价关系。 c)若R1是A上等价关系,则
<a,a>∈R1?<a,a>∈R1○R1
所以R21是A上自反的。
若<a,b>∈R21则存在c,使得<a, c>∈R1∧<c,b>∈R1。因R1
对称,故有
<b, c>∈R21∧<c,a>∈R1?<b, a>∈R1
即R2
1是对称的。
若<a,b>∈R21∧<b, c>∈R21,则有 <a,b>∈R1○R1∧<b, c>∈R1○R1 ?(?e1)(<a, e1>∈R1∧<e1, b>∈R1) ∧(?e2)(<b, e2>∈
R1∧<e2, c>∈R1)
?<a,b>∈R1∧<b, c>∈R1(∵R1传递)
?<a,c>∈R2
1
即R2
1是传递的。
故R21是A上的等价关系。
d)如b)所设,R1和R2是A上的等价关系,但 r(R1-R2)=(R1-R2)∪IA
={<a,b>, <b,a>, <a,c>,<c,a>,<a,a>,<b,b>, <c,c>} 不是A上的等价关系。
3-10.8 设C*是实数部分非零的全体复数组成的集合,C*上的关系R定义为:(a+bi)R(c+di)?ac>0,证明R是等价关系,并给出关系R的等价类的几何说明。
证明:(1)对任意非零实数a,有a2>0?(a+bi)R(a+bi) 故R在C*上是自反的。
(2) 对任意(a+bi)R(c+di)?ac>0, 因ca=ac>0?(c+di)R(a+bi), 所以R在C*上是对称的。
(3)设(a+bi)R(c+di) ,(c+di)R(u+vi),则有ac>0?cu>0 若c>0,则a>0?u>0? au>0 若c<0,则a<0?u<0? au>0
所以(a+bi)R(u+vi),即R在C*上是传递的。
关系R的等价类,就是复数平面上第一、四象限上的点,或第二、三象限上的点,因为在这两种情况下,任意两个点(a,b),(c,d),其横坐标乘积ac>0。
3-10.9 设Π和Π?是非空集合A上的划分,并设R和R?分别为由Π和Π?诱导的等价关系,那么Π?细分Π的充要条件是R? ? R。
证明:若Π?细分Π。由假设aR?b,则在Π?中有某个块S?,使得a,b∈S?,因Π?细分Π,故在Π中,必有某个块S,使S?? S,即a,b∈S,于是有aRb,即R? ? R。
反之,若R? ? R,令S?为H?的一个分块,且a∈S?,则S?=[a]R?={x|xR?a} 但对每一个x,若xR?a,因R? ? R,故xRa,因此{x|xR?a} ?{x|xRa}即[a]R? ?[a]R
设S=[a]R,则S?? S
这就证明了Π?细分Π。
3-10.10 设Rj是表示I上的模j等价关系,Rk是表示I上的模k等价关系,证明I/Rk细分I/Rj当且仅当k是j的整数倍。
证明:由题设Rj={
Rk={
故
b)若对于某个r∈I,有k=rj则:
因此,Rk ? Rj,于是I/Rk细分I/Rj
------------------------------------
5-1代数系统的引入 5.1.1设集合A={1,2,3,?,10},问下面定义的二元运算*关于集合A是否封闭? a) x*y=max(x,y); b) x*y=min(x,y); c) x*y=GCD(x,y);(最大公约数) d) x*y=LCM(x,y);(最小公倍数) e) x*y=质数p的个数,其中x?p?y。 解:a)封闭。b)封闭。c)封闭。d)不封闭。e)不封闭。 5.1.2在下表所列出的集合和运算中,请根据运算是否在相应集合上封闭,在相应位置上填写“是”或“否”,其中I表示整数集,N表示自然数集合。 是否封闭 运算 集合 + - ∣x-y∣ max min ∣x∣ I N {x∣0?x?10} {x∣-10?x?10} {2x∣x?I} 解: 是否封闭 运算 集合 + - ∣x-y∣ max min ∣x∣ I 是 是 是 是 是 是 N 是 否 是 是 是 是 {x∣0?x?10} 否 否 是 是 是 是 {x∣-10?x?10} 否 否 否 是 是 是 {2x∣x?I} 是 是 是 是 是 是 5-2运算及其性质 5.2.1对于实数集合R,下表所列的二元运算是否具有左边一列中那些性质,请在相应位置上填写“是”或“否”。 + - × max min ∣x-y∣ 结合律 交换律 有单位元 有零元 解: + - × max min ∣x-y∣ 结合律 是 否 是 是 是 否 交换律 是 否 是 是 是 是 有单位元 是 否 是 否 否 否 有零元 否 否 是 否 否 否
正在阅读:
畜牧有限公司年出栏2万头生猪零排放猪场建设项目可行性研究报告06-01
英语教师招聘真题,不看后悔版409-18
PS2接口协议解析及应用06-02
伯利克里演讲读后感10-19
小学品德与社会浙教版四年级下册第二单元第1课《城乡巨变》公开03-10
火炬之光法术卷轴资料05-10
第十二章++沟通03-10
2015最新苏教版六年级下册第七单元总复习完整版教案12-27
员工培训计划12-11
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 离散
- 上海
- 科学技术
- 文献
- 答案
- 出版社
- 数学
- 左孝
- 华中区智能变电站调试手册和规范(初稿) - 图文
- 澳洲西悉尼大学均分怎么计算及均分详细要求
- 灾害性天气预警和预防机制
- 播音创作基础重点-张颂
- 第四章 神经系统疾病的病史采集和体格检查
- 线性回归分析练习题
- 八年级上册音乐教案(全册)
- 电大专科答案个人与团队管理机考 - (已排序、题目全)
- 酶技术
- POS机返回码及解释
- ETERM销售指令
- 中心借调工作人员管理办法
- 牛顿第二定律教案
- 江苏省扬州中学2018届高三下学期开学考试(2月)历史 Word版含答案
- 土石坝毕业设计
- 供电局脱贫攻坚先进事迹材料
- 居家养老服务机构岗位职责
- 2019年上海高考数学第一轮复习 第42讲 排列组合
- 基于RFID技术的实验室学生考勤系统设计 中期报告 - 图文
- 税费改革后的农民负担问题的调查