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

dintin@gmailcom 1
离散数学课题答案离散数学课题答案离散数学课题答案离散数学课题答案 ((((左孝凌版左孝凌版左孝凌版左孝凌版))))
1112
（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： ab偶数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∧Rdintin@gmailcom 2
h) P控制台字机作输入设备Q控制台字机作输出设备P∧Q
13
（1）解：
a) 合式公式没规定运算符次序（规定运算符次序作合式公式）
b) 合式公式
c) 合式公式（括弧配）
d) 合式公式（RS间缺少联结词）
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┓AB(┓A→B)(B→A)((┓A→B)→(B→A))
d）AB(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代换 PS代换 QQ代换 RP代换 S
（5）解：
a) P 没写信 R 信途中丢失 PQ
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
14
（4）解：a)
PQRQ∧RP∧(Q∧R)P∧Q(P∧Q)∧R
∨dintin@gmailcom 3
TTT
TTF
TFT
TFF
FTT
FTF
FFT
FFF
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
P∧(Q∧R) ⇔ (P∧Q)∧R
b)
PQRQ∨RP∨(Q∨R)P∨Q(P∨Q)∨R
TTT
TTF
TFT
TFF
FTT
FTF
FFT
FFF
Ｔ
Ｔ
Ｔ
Ｆ
Ｔ
Ｔ
Ｔ
Ｆ
Ｔ
Ｔ
Ｔ
Ｔ
Ｔ
Ｔ
Ｔ
Ｆ
Ｔ
Ｔ
Ｔ
Ｔ
Ｔ
Ｔ
Ｆ
Ｆ
Ｔ
Ｔ
Ｔ
Ｔ
Ｔ
Ｔ
Ｔ
Ｆ
P∨(Q∨R) ⇔ (P∨Q)∨R
ｃ）
ＰＱＲＱ∨ＲＰ∧（Ｑ∨Ｒ）Ｐ∧ＱＰ∧Ｒ（Ｐ∧Ｑ）∨（Ｐ∧Ｒ）
ＴＴＴ
ＴＴＦ
ＴＦＴ
ＴＦＦ
ＦＴＴ
ＦＴＦ
ＦＦＴ
ＦＦＦ
Ｔ
Ｔ
Ｔ
Ｆ
Ｔ
Ｔ
Ｔ
Ｆ
Ｔ
Ｔ
Ｔ
Ｆ
Ｆ
Ｆ
Ｆ
Ｆ
Ｔ
Ｔ
Ｆ
Ｆ
Ｆ
Ｆ
Ｆ
Ｆ
Ｔ
Ｆ
Ｔ
Ｆ
Ｆ
Ｆ
Ｆ
Ｆ
Ｔ
Ｔ
Ｔ
Ｆ
Ｆ
Ｆ
Ｆ
Ｆ
P∧(Q∨R) ⇔ (P∧Q)∨(P∧R)
ｄ）
PQ ┓P ┓Q ┓P∨┓Q ┓(P∧Q) ┓P∧┓Q ┓(P∨Q)
TT
TF
FT
FF
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表达
PQR F1 F2 F3 F4 F5 F6dintin@gmailcom 4
TTTTFTTFF
TTFFFTFFF
TFTTFFTTF
TFFFTFTTF
FTTTFFTTF
FTFTFFFTF
FFTTFTTTF
FFFFTFTTT
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
FFTFTFTFTFTFTFTFT
TFFTTFFTTFFTTFFTT
FFFFFTTTTFFFFTTTT
TFFFFFFFFTTTTTTTT
解：表关公式
1F 2┓(P∨Q) 3┓(Q→P) 4┓P
5┓(P→Q) 6┓Q 7┓(P↔Q) 8┓(P∧Q)
9P∧Q 10P↔Q 11Q 12P→Q
13P 14Q→P 15P∨Q 16T
(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)dintin@gmailcom 5
⇔ (┐(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）设 CTATBF满足 A∨C⇔B∨C A⇔B 成立
2）设 CFATBF满足 A∧C⇔B∧C A⇔B 成立
3）题意知┐A┐B真值相 AB真值相
题 15
（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)∨Qdintin@gmailcom 6
⇔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→QT
（1） PT QT P∧QT P→(P∧Q)T
（2） PF QF P∧QFP→(P∧Q)T
命题证
解法 2：
设P→(P∧Q)F PT(P∧Q)F必 PTQF P→QF
解法 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∨QF PF QF
P→QT(P→Q)→QF
(P→Q)→Q⇒P∨Q
c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))⇒R→Q
设R→QF RT QF P∧┐PF
Q→(P∧┐P)TR→(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) 仅走留dintin@gmailcom 7
设S：走R：留R→S
逆换式 S→R表示命题：果走留
逆反式┐S→┐R表示命题：果走留
c) 果获更帮助完成务
设E：获更帮助H：完成务E→H
逆换式 H→E表示命题：完成务获更帮助
逆反式┐H→┐E表示命题：完成务获更帮助
（5） 试证明 P↔QQ逻辑蕴含 P
证明：解法 1：
题求证明(P↔Q) ∧Q⇒P
设(P↔Q) ∧QT(P↔Q)TQ 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)∧QT
QT(P→┐Q) T PF
(┐R→P)T RT
题证效
（7） 解：
P：6偶数 Q：72 R：5素数
果 6偶数 72 P→┐Q
5素数 72 ┐R∨Qdintin@gmailcom 8
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)∧RT
RT┐R∨Q T QT
P→┐QT┐PT
（8） 证明：
a) P⇒(┐P→Q)
设PT┐PF┐P→QT
b) ┐A∧B∧C⇒C
假定┐A∧B∧CT CT
c) C⇒A∨B∨┐B
A∨B∨┐B永真 C⇒A∨B∨┐B 成立
d) ┐(A∧B) ⇒┐A∨┐B
设┐(A∧B)T A∧BF
ATBF┐AF┐BT┐A∨┐BT
AFBT┐AT┐BF┐A∨┐BT
AFBF┐AT┐BT┐A∨┐BT
命题证
e) ┐A→(B∨C)D∨E(D∨E)→┐A⇒B∨C
设┐A→(B∨C)D∨E(D∨E)→┐AT
D∨ET(D∨E)→┐AT┐AT
┐A→(B∨C)T B∨CT命题证
f) (A∧B)→C┐D┐C∨D⇒┐A∨┐B
设(A∧B)→C┐D┐C∨DT┐DT┐C∨DT CF
(A∧B)→CT A∧BF┐A∨┐BT命题证
（9）解：
a) 果勇气胜
P：勇气 Q：胜
原命题：P→Q 逆反式：┐Q→┐P 表示：果失败说明没勇气
b) 仅累胜
P：累 Q：胜
原命题：Q→P 逆反式：┐P→┐Q 表示：果累失败
题 16
(1)解：
a) (P∧Q)∧┐P⇔(P∧┐P)∧Q⇔┐(T∨Q)
b) (P→(Q∨┐R)) ∧┐P∧Qdintin@gmailcom 9
⇔ (┐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)出组指派：PTQFRF(P↑Q)↑RTP↑(Q↑R)F
(P↑Q)↑RP↑(Q↑R)
b)出组指派：PTQFRF(P↓Q) ↓RTP↓(Q↓R)F
⇔
⇔dintin@gmailcom 10
∨
∨
(P↓Q)↓RP↓(Q↓R)
(7)证明：
设变元 PQ连结词↔┐作 PQ：PQ┐P┐QP↔QP↔PQ↔QQ↔P
P↔Q⇔Q↔PP↔P⇔Q↔Q实际：
PQ┐P┐QP↔QP↔P（T）（A）
┐作（A）类扩公式类（包括原公式类）：
PQ┐P┐Q┐（P↔Q）TFP↔Q（B）
↔作（A）类：
P↔QP↔┐P⇔FP↔┐Q⇔┐（P↔Q）P↔（P↔Q）⇔QP↔（P↔P）⇔P
Q↔┐P⇔┐（P↔Q）Q↔┐Q⇔FQ↔（P↔Q）⇔PQ↔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┐QPQP↔QFT
┐（P↔Q）
（B）类中
（B）类↔运算：
P↔QP↔┐P⇔FP↔┐Q⇔┐（P↔Q）P↔┐（P↔Q）⇔┐QP↔T⇔PP↔F⇔┐PP↔（P↔Q）⇔Q
Q↔┐P⇔┐（P↔Q）Q↔┐Q⇔FQ↔┐（P↔Q）⇔┐PQ↔T⇔QQ↔F⇔┐QQ↔（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⇔FT↔（P↔Q）⇔ P↔Q
F↔（P↔Q）⇔ ┐（P↔Q）
（P↔Q）↔（P↔Q）⇔P↔Q
（B）类↔运算结果（B）中
证明：↔┐两连结词反复作两变元公式中结果产生（B）类中公式总仅八公式{↔┐}
功完备更联结词组
已证{↔┐}联结词组 PQ⇔ ┐（P↔Q）命题公式中联结词仅{ ┐}表达必{↔
┐}表达逆真{ ┐}必联结词组
(8)证明{∨}{∧}{→}联结词组
证明：{∨}{∧}{→}联结词
┐P⇔（P∨P∨……）
┐P⇔（P∧P∧……）
┐P⇔P→(P→(P→……)
命题变元指派 T等价式左边 F右边 T等价表达式矛盾
{∨}{∧}{→}联结词
(9)证明{┐→}{┐}联结词组
证明：{┐∨}联结词组 P∨Q⇔┐P→Q
{┐→}功完备联结词组{┐}{→}功完备联结词组
{┐→}联结词组
P→Q⇔┐(PQ){┐}功完备联结词组{┐}{ }功完备联结词组
{┐}联结词组
→c
∨
→c →c →c
→cdintin@gmailcom 11
题 17
(1) 解：
P∧(P→Q)
⇔P∧(┐P∨Q)
⇔ (P∧┐P)∨(P∧Q)
P∧(P→Q)
⇔ (P∨(┐Q∧Q))∧(┐P∨Q)
⇔ (P∨┐Q)∧(P∨Q)∧(┐P∨Q)
(2) 解：
a) (┐P∧Q)→R
⇔┐(┐P∧Q)∨R
⇔ P∨┐Q∨R
⇔(P∧Q)∨(P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(R∧P)∨(R∧┐P)
b) P→((Q∧R)→S)
⇔┐P∨(┐(Q∧R)∨S)
⇔┐P∨┐Q∨┐R∨S
⇔(┐P∧Q)∨(┐P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(┐R∧S)∨(┐R∧┐S)∨(S∧P)∨(S∧┐P)
c) ┐(P∨┐Q)∧(S→T)
⇔(┐P∧Q)∧(┐S∨T)
⇔(┐P∧Q∧┐S)∨(┐P∧Q∧T)
d) (P→Q)→R
⇔┐(┐P∨Q)∨R
⇔(P∧┐Q)∨R
⇔(P∨R)∧(┐Q∨R)
e) ┐(P∧Q)∧(P∨Q)
⇔(┐P∨┐Q)∧(P∨Q)
⇔(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q)
⇔ (┐P∧Q)∨(┐Q∧P)
(3) 解：
a) P∨(┐P∧Q∧R)
⇔(P∨┐P)∧(P∨Q)∧(P∨R)
⇔(P∨Q)∧(P∨R)
b) ┐(P→Q)∨(P∨Q)
⇔┐(┐P∨Q)∨(P∨Q)
⇔(P∧┐Q)∨(P∨Q)
⇔(P∨P∨Q)∧(┐Q∨P∨Q)
c) ┐(P→Q)
⇔┐(┐P∨Q)
⇔ P∧┐Q
⇔(P∨Q)∧(P∨┐Q)∧(┐Q∨┐P)
d) (P→Q)→R
⇔┐(┐P∨Q)∨R
⇔ (P∧┐Q)∨R
⇔ (P∨R)∧(┐Q∨R)
e) (┐P∧Q)∨(P∧┐Q)
⇔(┐P∨P)∧(┐P∨┐Q)∧(Q∨P)∧(Q∨┐Q)dintin@gmailcom 12
⇔(┐P∨┐Q)∧(Q∨P)
(4) 解：
a) (┐P∨┐Q)→(P↔┐Q)
⇔┐(┐P∨┐Q) ∨(P↔┐Q)
⇔ (P∧Q) ∨(P∧┐Q)∨(┐P∧Q)
⇔∑123
⇔P∨QΠ 0
b) Q∧(P∨┐Q)
⇔ (P∧Q)∨(Q∧┐Q)
⇔ P∧Q ∑3
⇔Π 012
⇔(P∨Q)∧(P∨┐Q) ∧(┐P∨Q)
c) P∨(┐P→(Q∨(┐Q→R))
⇔P∨(P∨(Q∨(Q∨R))
⇔P∨Q∨RΠ 0
⇔∑1234567
(┐P∧┐Q∧R) ∨(┐P∧Q∧┐R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R)
d) (P→(Q∧R))∧(┐P→(┐Q∧┐R))
⇔ (┐P∨(Q∧R)) ∧(P∨(┐Q∧┐R))
⇔ (P∧┐P) ∨(P∧(Q∧R)) ∨ ((┐Q∧┐R) ∧┐P) ∨((┐Q∧┐R) ∧(Q∧R))
⇔ (P∧Q∧R) ∨(┐P∧┐Q∧┐R) ∑07
⇔Π 123456
⇔ (P∨Q∨┐R) ∧(P∨┐Q∨R) ∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R) ∧(┐P∨Q∨┐R) ∧(┐P∨┐Q∨R)
e) P→(P∧(Q→P)
⇔┐P∨(P∧(┐Q∨P)
⇔(┐P∨P)∧(┐P∨┐Q∨P)
⇔T∨(T∧┐Q) ⇔T
⇔∑0123 (┐P∧┐Q) ∨(┐P∧Q) ∨(P∧┐Q) ∨(P∧Q)
f) (Q→P) ∧(┐P∧Q)
⇔ (┐Q∨P) ∧┐P∧Q
⇔ (┐Q∨P) ∧┐(P∨┐Q) ⇔F
⇔Π 0123 (P∨Q) ∧(P∨┐Q) ∧(┐P∨Q) ∧(┐P∨┐Q)
(5) 证明：
a)
(A→B) ∧(A→C)
⇔ (┐A∨B) ∧(┐A∨C)
A→(B∧C)
⇔┐A∨(B∧C)
⇔ (┐A∨B) ∧(┐A∨C)
b)
(A→B) →(A∧B)
⇔┐(┐A∨B) ∨(A∧B)
⇔ (A∧┐B) ∨(A∧B)
⇔A∧(B∨┐B)
⇔A∧T
⇔Adintin@gmailcom 13
(┐A→B) ∧(B→A)
⇔ (A∨B) ∧(┐B∨A)
⇔A∨(B∧┐B)
⇔A∨F
⇔A
c)
A∧B∧(┐A∨┐B)
⇔ ((A∧┐A)∨(A∧┐B))∧B
⇔A∧B∧┐B
⇔F
┐A∧┐B∧(A∨B)
⇔ ((┐A∧A)∨(┐A∧B))∧┐B
⇔┐A∧┐B∧B
⇔F
d)
A∨(A→(A∧B)
⇔A∨┐A∨(A∧B)
⇔T
┐A∨┐B∨(A∧B)
⇔┐(A∧B) ∨(A∧B)
⇔T
(6)解：A⇔R↑(Q∧┐(R↓P))A*⇔ R↓(Q∨┐(R↑P))
A⇔R↑(Q∧┐(R↓P))
⇔┐(R∧(Q∧(R∨P)))
⇔┐R∨┐Q∨┐(R∨P)
⇔┐(R∧Q) ∨┐(R∨P)
A*⇔R↓(Q∨┐(R↑P))
⇔┐(R∨(Q∨(R∧P))
⇔┐R∧┐Q∧┐(R∧P)
⇔┐(R∨Q) ∧┐(R∧P)
(7) 解：设A：A出差B：B出差C：C出差D：D出差
A CD中 A→(CVD)
BC ┐(B∧C)
C D留 C→┐D
题意应：A→(CVD)┐(B∧C)C→┐D必须时成立
CVD ⇔ (C∧┐D) ∨(D∧┐C)
(A→(CV D))∧┐(B∧C) ∧(C→┐D)
⇔ (┐A∨(C∧┐D) ∨(D∧┐C)) ∧┐(B∧C) ∧(┐C∨┐D)
⇔ (┐A∨(C∧┐D) ∨(D∧┐C)) ∧(┐B∨┐C) ∧(┐C∨┐D)
⇔ (┐A∨(C∧┐D) ∨(D∧┐C)) ∧((┐B∧┐C) ∨(┐B∧┐D) ∨(┐C∧┐D) ∨┐C)
⇔ (┐A∧┐B∧┐C) ∨(┐A∧┐B∧┐D) ∨(┐A∧┐C∧┐D) ∨(┐A∧┐C)
∨(┐B∧┐C∧D) ∨(┐C∧D∧┐B∧┐D) ∨(┐C∧D∧┐C∧┐D)dintin@gmailcom 14
∨(┐C∧D∧┐C) ∨(┐D∧C∧┐B∧┐C) ∨(┐D∧C∧┐B∧┐D)
∨(┐D∧C∧┐C∧┐D) ∨(┐D∧C∧┐C)
述析取范式中（画线）符合题意舍弃
(┐A∧┐C) ∨(┐B∧┐C∧D) ∨（┐C∧D）∨(┐D∧C∧┐B)
分派方法：B∧D D∧A C∧A
(8) 解：设P：A 第Q：B 第二R：C 第二S：D 第四E：A 第二
题意 (PVQ) ∧(RVS) ∧(EVS)
⇔ ((P∧┐Q) ∨(┐P∧Q)) ∧((R∧┐S) ∨(┐R∧S)) ∧((E∧┐S) ∨(┐E∧S))
⇔ ((P∧┐Q∧R∧┐S) ∨(P∧┐Q∧┐R∧S) ∨(┐P∧Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S)∨(┐E∧S))
(P∧┐Q∧┐R∧S)(┐P∧Q∧R∧┐S)合题意原式化
((P∧┐Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S) ∨(┐E∧S))
⇔ (P∧┐Q∧R∧┐S∧E∧┐S) ∨(P∧┐Q∧R∧┐S∧┐E∧S) ∨(┐P∧Q∧┐R∧S∧E∧┐S)∨(┐P∧Q∧┐R∧S∧┐E∧S)
⇔ (P∧┐Q∧R∧┐S∧E) ∨(┐P∧Q∧┐R∧S∧┐E)
RE矛盾┐P∧Q∧┐R∧S∧┐E真
A第B第二C第二D第四A第二
： A 第三 B第二 C第 D 第四
题 18
(1)证明：
a)┐(P∧┐Q)┐Q∨R┐R⇒┐P
(1) ┐RP
(2) ┐Q∨RP
(3) ┐Q(1)(2)TI
(4) ┐(P∧┐Q)P
(5) ┐P∨Q(4)TE
(6) ┐P(3)(5)TI
b)J→(M∨N)(H∨G)→JH∨G⇒M∨N
(1) (H∨G) →JP
(2) (H∨G)P
(3) J(1)(2)TI
(4) J→(M∨N)P
(5) M∨N(3)(4)TI
c)B∧C(B↔C)→(H∨G) ⇒G∨H
(1) B∧CP
(2) B(1)TI
(3) C(1)TI
(4) B∨┐C(2)TI
(5) C∨┐B(3)TI
(6) C→B(4)TE
(7) B→C(5)TE
(8) B↔C(6)(7)TE
(9) (B↔C) →(H∨G)P
(10) H∨G(8)(9)TI
d)P→Q(┐Q∨R)∧┐R┐(┐P∧S) ⇒┐S
(1) (┐Q∨R) ∧┐Rdintin@gmailcom 15
(2) ┐Q∨R(1)TI
(3) ┐R(1)TI
(4) ┐Q(2)(3)TI
(5) P→QP
(6) ┐P(4)(5)TI
(7) ┐(┐P∧┐S)P
(8) P∨┐S(7)TE
(9) ┐S(6)(8)TI
(2) 证明：
a)┐A∨BC→┐B⇒A→┐C
(1) ┐(A→┐C)P
(2) A(1)TI
(3) C(1)TI
(4) ┐A∨BP
(5) B(2)(4)TI
(6) C→┐BP
(7) ┐B(3)(6)TI
(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)TI
(3) ┐(B→F)(1)TI
(4) B(3)TI
(5) ┐F(3)T
(6) A→(B→C)P
(7) B→C(2)(6)TI
(8) C(4)(7)TI
(9) ┐F→(D∧┐E)P
(10) D∧┐E(5)(9)TI
(11) D(10)TI
(12) C∧D(8)(11)TI
(13) (C∧D) →EP
(14) E(12)(13)TI
(15) ┐E(10)TI
(16) E∧┐E 矛盾(14)(15)
c)A∨B→C∧DD∨E→F⇒A→F
(1) ┐(A→F)P
(2) A(1)TI
(3) ┐F(1)TI
(4) A∨B(2)TI
(5) (A∨B) →C∧DP
(6) C∧D(4)(5)TI
(7) C(6)TI
(8) D(6)TI
(9) D∨E(8)TI
(10) D∨E→FPdintin@gmailcom 16
(11) F(9)(10)TI
(12) F∧┐F 矛盾(3)(11)
d)A→(B∧C)┐B∨D(E→┐F)→┐DB→(A∧┐E) ⇒B→E
(1) ┐(B→E)P
(2) B(1)TI
(3) ┐E(1)TI
(4) ┐B∨DP
(5) D(2)(4)TI
(6) (E→┐F) →┐DP
(7) ┐(E→┐F)(5)(6)TI
(8) E(7)TI
(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)TI
(3) (B→E) ∧(D→F)P
(4) B→E(3)TI
(5) A→E(2)(4)TI
(6) ┐(E∧F)P
(7) ┐E∨┐F(6)TE
(8) E→┐F(7)TE
(9) A→┐F(5)(8)TI
(10) C→D(1)TI
(11) D→F(3)TI
(12) C→F(10)(10)TI
(13) A→CP
(14) A→F(13)(12)TI
(15) ┐F→┐A(14)TE
(16) A→┐A(9)(15)TI
(17) ┐A∨┐A(16)TE
(18) ┐A(17) TE
(3) 证明：
a)┐A∨BC→┐B⇒A→┐C
(1) AP
(2) ┐A∨BP
(3) B(1)(2)TI
(4) C→┐BP
(5) ┐C(3)(4)TI
(6) A→┐CCP
b)A→(B→C)(C∧D)→E┐F→(D∧┐E) ⇒A→(B→F)
(1) AP
(2) A→(B→C)P
(3) B→C(1)(2)TI
(4) BP
(5) C(3)(4)TI
(6) (C∧D) →EPdintin@gmailcom 17
(7) C→(D→E)(6)TE
(8) D→E(5)(7)TI
(9) ┐D∨E(8)TE
(10) ┐(D∧┐E)(9)TE
(11) ┐F→(D∧┐E)P
(12) F(10)(11)TI
(13) B→FCP
(14) A→(B→F)CP
c)A∨B→C∧DD∨E→F⇒A→F
(1) AP
(2) A∨B(1)TI
(3) A∨B→C∨DP
(4) C∧D(2)(3)TI
(5) D(4)TI
(6) D∨E(5)TI
(7) D∨E→FP
(8) F(6)(7)TI
(9) A→FCP
d)A→(B∧C)┐B∨D(E→┐F)→┐DB→(A∧┐E) ⇒B→E
(1) BP(附加前提)
(2) ┐B∨DP
(3) D(1)(2)TI
(4) (E→┐F)→┐DP
(5) ┐(E→┐F)(3)(4)TI
(6) E(5)TI
(7)B→ECP
(4)证明：
a) R→┐QR∨SS→┐QP→Q⇒┐P
(1) R→┐QP
(2) R∨SP
(3) S→┐QP
(4) ┐Q(1)(2)(3)TI
(5) P→QP
(6) ┐P(4)(5)TI
b) S→┐QS∨R┐R┐P↔Q⇒P
证法：
(1) S∨RP
(2) ┐RP
(3) S(1)(2)TI
(4) S→┐QP
(5) ┐Q(3)(4)TI
(6) ┐P↔QP
(7)(┐P→Q)∧(Q→┐P)(6)TE
(8) ┐P→Q(7)TI
(9) P(5)(8)TI
证法二：（反证法）dintin@gmailcom 18
(1) ┐PP（附加前提）
(2) ┐P↔QP
(3)（┐P→Q）∧（Q→┐P）(2)TE
(4) ┐P→Q(3)TI
(5) Q(1)(4)TI
(6) S→┐QP
(7) ┐S(5)(6)TI
(8) S∨RP
(9) R(7)(8)TI
(10) ┐RP
(11) ┐R∧R 矛盾（9）（10）TI
c)┐(P→Q)→┐(R∨S)((Q→P)∨┐R)R⇒P↔Q
(1) RP
(2) (Q→P) ∨┐RP
(3) Q→P(1)(2)TI
(4)┐(P→Q) →┐(R∨S)P
(5) (R∨S) →(P→Q)(4)TE
(6) R∨S(1)TI
(7) P→Q(5)(6)
(8) (P→Q) ∧(Q→P)(3)(7)TI
(9) P↔Q(8)TE
(5) 解：
a) 设P：跑步Q：疲劳
前提：P→Q┐Q
(1) P→QP
(2) ┐QP
(3) ┐P(1)(2)TI
结：┐P没跑步
b) 设S：犯错误 R：神色慌张
前提：S→RR
（S→R）∧R⇔（┐S∨R）∧R⇔R题没确定结
实际 S →R真R真S真S假效结
c) 设P：程序通 Q：快乐
R：阳光 S：天暖（晚十点理解阳光）
前提：P→QQ→R┐R∧S
(1) P→QP
(2) Q→RP
(3) P→R(1)(2)TI
(4) ┐R∨SP
(5) ┐R(4)TI
(6) ┐P(3)(5)TI
结： ┐P程序没通
题 2122
（1） 解：
a) 设W（x）：x工c：张dintin@gmailcom 19
¬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（xy）：直线 x行直线 y
G（xy）：直线 x相交直线 y
P（AB）�¬G（AB）
（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(xy)：x钦佩 y
（∀x）（L（x）→ （∃y）（J（y）∧A（xy）））
l） 设S（x）：x学生L（x）：x 运动员A(xy)：x钦佩 y
（∃x）（S（x）∧（∀y）（L（y）→¬ A(xy)））
题 23
（1）解：dintin@gmailcom 20
a）5 质数
b）2偶数 2质数
c） x x 2 x 偶数
d）存 xx偶数 x 6（某偶数 6）
e） x x 偶数 x 2
f） x x偶数 y x y y偶数
g） x x 质数存 yy偶数 x y（质数某偶数）
h） x x 奇数 yy 质数 x y（奇数质数）
（2）解：（∀x）(∀y)((P(x)∧P(y)∧┐E(xy)→(∃z)(L(z)∧R(xyz)))
（∀x）(∀y)((P(x)∧P(y)∧┐E(xy)→(∃z)(L(z)∧R(xyz) ∧┐(∃u)(┐E(zu) ∧L(u)∧R(xyu))))
（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(xy)y x (∀x)(R(x)→(∃y)(Q(xy)∧R(y)))
c) R(x)x 实数G(xy)x y
(∃x)(∃y)(∃z)(R(x)∧R(y)∧R(z)∧G(x+yx·z)
（4）解：设 G(xy)x y (∀x)(∀y)(∀z)(G(yx) ∧G(0z)→G(x·zy·z))
（5）解：设 N(x)x 数 S(xy)y x继数E(xy)：xy
a) (∀x)(N(x)→(∃y)(N(y)∧S(xy)))
(∀x)(N(x)→(∃y)(N(y)∧S(xy) ∧┐(∃z)(┐E(yz) ∧N(z)∧S(xz))))
b) ┐(∃x)(N(x)∧S(x1))
c) (∀x)(N(x)∧┐S(x2)→(∃y)(N(y) ∧S(yx)))
(∀x)(N(x)∧┐S(x2)→(∃y)(N(y) ∧S(yx) ∧┐(∃z)(┐E(yz) ∧N(z)∧S(zx))))
（6）解：设 S(x)x 学生 E(x)x 戴眼睛
F(x)x 功 R(xy)x y
G(y)y K(y)y 厚 J(y)y 巨著 a b位
E(b)∧F(b)∧S(b)∧R(ba)∧G(a)∧K(a)∧J(a)
（7）解：设 P(xy)x y连续 Q(xy)x>y
P(fa)�((∀ε)(∃δ)(∀x)(Q(ε0)→(Q(δ0)∧Q(δ|xa|)→Q(ε|f(x)f(a)|))))
题 22224444
(1) 解：a) x 约束变元y 变元
b) x 约束变元P(x)∧Q(x)中 x受全称量词∀约束S(x)中 x 受存量词∃约束
c) xy约束变元P(x)中 x受∃约束R(x)中 x受∀约束
d) xy 约束变元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)TQ(1)FP(2)FQ(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)dintin@gmailcom 21
P TQ(−2)TQ(3)TQ(6)FR(5)F
(∀x)(P→Q(x))∨R(a)⇔ ((T→T)∧(T→T)∧(T→F))∨F⇔ F
(4) 解：a) (∀u)(∃v)(P(uz)→Q(v))�S(x y)
b) (∀u)(P(u)→ (R(u)∨Q(u))∧(∃v)R(v))→(∃z)S(xz)
(5) 解：a) ((∃y)A(uy)→(∀x)B(xv))∧(∃x)(∀z)C(x tz)
b) ((∀y)P(uy)∧(∃z)Q(uz))∨(∀x)R(xt)
题 25252525
（1）解： a) P(af(a))∧P(bf(b))⇔P(1f(1))∧P(2f(2))⇔P(12)∧P(21) ⇔T∧F⇔F
b) (∀x)(∃y)P(yx)⇔ (∀x) (P(1x)∨P(2x))⇔ (P(11)∨P(21))∧(P(12)∨P(22))
⇔ (T∨F)∧(T∨F) ⇔ T
c) (∀x)( ∀y)(P(xy)→P(f(x)f(y)))
⇔ (∀x) ((P(x1)→P(f(x)f(1)))∧(P(x2) →P(f(x)f(2))))
⇔ (P(11)→P(f(1)f(1)))∧(P(12)→P(f(1)f(2)))
∧(P(21)→P(f(2)f(1)))∧(P(22) →P(f(2)f(2)))
⇔ (P(11)→P(22))∧(P(12)→P(21))∧(P(21)→P(12))∧(P(22)→P(11))
⇔ (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(21))∧(T→Q(11))
⇔ (F→F)∧(T→T) ⇔T
b) (∃x)(P(f(x))∧Q(xf(a))
⇔ (P(f(1))∧Q(1f(1)))∨(P(f(2))∧Q(2f(1)) ⇔ (T∧T)∨(F∧F) ⇔T
c) (∃x)(P(x)∧Q(xa))
⇔ (P(1)∧Q(1a))∨(P(2)∧Q(2a))
⇔ (P(1)∧Q(11))∨(P(2)∧Q(21))
⇔ (F∧T)∨(T∧F) ⇔F
d) (∀x)( ∃y)(P(x)∧Q(xy))
⇔ (∀x) (P(x)∧(∃y)Q(xy))
⇔ (∀x) (P(x)∧(Q(x1)∨Q(x2)))
⇔ (P(1)∧(Q(11)∨Q(12)))∧(P(2)∧(Q(21)∨Q(22)))
⇔ (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运动员
前提 者存 xx学生者 a 运动员
结 果存 x学生必 a运动员
b)设P（x）：x研究生Q（x）：x学生a：域中某
前提：域中 x果 x研究生 x 学生
域中 x x学生dintin@gmailcom 22
结：域中 x研究生
域中某 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运动员
xx研究生
结 必存 xx运动员
e）设 P（x）：x研究生Q（x）：x 运动员
前提 x者 x研究生者 x运动员
xx研究生
结 xx运动员
（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{abc}求证(∀x)A(x)∨(∀x)B(x)⇒( ∀x)(A(x)∨B(x))
证明：域 D{abc}
(∀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)
题 26262626
（1）解：a) (∀x)(P(x)→(∃y)Q(xy))
⇔(∀x)( ┐P(x) ∨(∃y)Q(xy))
⇔(∀x) (∃y) (┐P(x) ∨Q(xy))
b) (∃x)(┐((∃y)P(xy))→((∃z)Q(z)→R(x)))
⇔(∃x)((∃y)P(xy)∨((∃z)Q(z)→R(x)))
⇔(∃x)((∃y)P(xy) ∨(┐(∃z)Q(z) ∨R(x)))
⇔(∃x)((∃y)P(xy) ∨((∀z)┐Q(z) ∨R(x)))
⇔(∃x) (∃y) (∀z) ( P(xy) ∨┐Q(z) ∨R(x))
c)(∀x)( ∀y)(((∃zP(xyz)∧(∃u)Q(xu))→(∃v)Q(yv))
⇔(∀x)( ∀y)( ┐((∃z)P(xyz)∧(∃u)Q(xu))∨(∃v)Q(yv))
⇔(∀x)( ∀y)( (∀z)┐P(xyz) ∨(∀u)┐Q(xu)∨(∃v)Q(yv))
⇔(∀x)( ∀y)( (∀z)┐P(xyz) ∨(∀u)┐Q(xu)∨(∃v)Q(yv))dintin@gmailcom 23
⇔(∀x)( ∀y) (∀z)(∀u)(∃v) (┐P(xyz) ∨┐Q(xu)∨Q(yv))
（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(xy)→┐(∀z)R(yx)))
⇔(∀x)( ┐P(x) ∨(∀y)( Q(xy)→┐R(yx)))
⇔(∀x) (∀y) ( ┐P(x) ∨┐Q(xy) ∨┐R(yx))
前束合取范式
⇔(∀x) (∀y)((P(x) ∧Q(xy) ∧R(yx))
∨(P(x) ∧Q(xy) ∧┐R(yx))
∨ (P(x) ∧┐Q(xy) ∧R(yx))
∨(┐P(x) ∧Q(xy) ∧R(yx))
∨(┐P(x) ∧┐Q(xy) ∧R(yx))
∨((P(x) ∧┐Q(xy) ∧┐R(yx))
∨(┐P(x) ∧Q(xy) ∧┐R(yx)))
前束析取范式
c) (∀x)P(x)→(∃x)(( ∀z)Q(xz)∨(∀z)R(xyz))
⇔┐(∀x)P(x) ∨(∃x)(( ∀z)Q(xz)∨(∀z)R(xyz))
⇔(∃x)┐P(x) ∨(∃x)(( ∀z)Q(xz)∨(∀u)R(xyu))
⇔(∃x)(┐P(x) ∨(∀z)Q(xz)∨(∀u)R(xyu))
⇔(∃x) (∀z) (∀u)(┐P(x) ∨Q(xz)∨R(xyu))
前束合取范式
⇔(∃x) (∀z) (∀u)(( P(x) ∧Q(xz) ∧R(xyu))
∨(P(x) ∧Q(xz) ∧┐R(xyu))
∨(P(x) ∧┐Q(xz) ∧R(xyu))
∨(P(x) ∧┐Q(xz) ∧┐R(xyu))
∨(┐P(x) ∧Q(xz) ∧┐R(xyu))
∨(┐P(x) ∧┐Q(xz) ∧R(xyu))
∨(┐P(x) ∧┐Q(xz) ∧┐R(xyu)))
前束析取范式
d)(∀x)(P(x)→Q(xy))→((∃y)P(y)∧(∃z)Q(yz))
⇔┐(∀x)( ┐P(x) ∨Q(xy)) ∨((∃y)P(y)∧(∃z)Q(yz))
⇔(∃x)( P(x) ∧┐Q(xy)) ∨((∃u)P(u)∧(∃z)Q(yz))
⇔(∃x) (∃u) (∃z) (( P(x) ∧┐Q(xy)) ∨(P(u)∧Q(yz)))
前束析取范式
⇔(∃x) (∃u) (∃z) (( P(x)∨P(u)) ∧ (P(x)∨Q(yz)) ∧(┐Q(xy)∨P(u)) ∧ (┐Q(xy)∨Q(yz)))
前束合取范式
题 22227777
(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④⑤Idintin@gmailcom 24
⑦ ( ∃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) CPdintin@gmailcom 25
(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）前提矛盾题推证效dintin@gmailcom 26
351 列出 X{abc} Y{s}
关系

解：Z1{}
Z2{}
Z3{}
Z4{}
Z5{}
Z6{}
Z7{}

352 n 元 素 集 合
少种关系

解 X中二元关系 X
×X子集 X×XX2中 n2
元素取 0n2元素组
成
2
2n
子集
2
2|)(| nXX ×℘

353 设A＝{6：006：307 ：30…
9：3010 ：30}表示晚隔半时
九时刻集合设 B{3121517}
表示四电视频道集合 设R1
R2 AB两二元关系
二关系 R1R2R1∪R2R1∩R2
R1
⊕
R2R1R2分出样解
释

解 ：A×B表示晚九时刻四
电视频道 组成电视节目表
R1R2分 A×B两子集
例R1表示音乐节目播出时间表
R2戏曲节日播出时间表 R1∪
R2表示音乐戏曲节目播出时间
表R1∩R2表示音乐戏曲起播出
时间表 R1
⊕
R2表示音乐节目表
戏曲节目表音乐戏曲
起节日表 R1R2表示戏曲时间
音乐节目时间麦

354 设L表示关系等 D
表示整关系 LD刀均定义
{1236} 分写出 LD元
素求出 L∩D

解 ：L{<12><13><16><23><26>
<36><11><22><33><66>}
D{<12><13><16><26><36><1
1><22><33><66>}
L∩D
{<12><13><16><26><36><11>
<22><33><66>}

355 列 式 出 A二元
关系试出关系图：
a){< xy>|0 ≤x∧y≤3}里
A{1234}
b){< x y>|2 ≤xy≤7x y
里A＝{n|n ∈N∧n≤10}
c) {< xy>|0 ≤xy<3} 里
A{01234}
d){< xy>|xy 互质 }里
A{23456}

解：
a) R {<00><01><02><03>
<10><11><12><13>
<20><21><22><23>
<30><31><32><33>}
关系图

b) R {<20><22><24><26>
<30><33><36>
<40><44>
<50><55>
<60><66>
<70><77>} dintin@gmailcom 27
361 分析集合 A{1 23} 述
五关系：
（1）R{ ＜11＞＜ 12＞＜1
3＞＜ 33＞}
（2）S{ ＜11＞＜ 12＞＜2
1＞＜ 22＞＜33＞}
（3）T{ ＜11＞＜ 12＞＜2
2＞＜ 23＞}
（4）Ø空关系
（5）A×A全域关系
判断A中述关系否 a）反
b）称 c）传递 d）反称


解（1）R传递反称
（2）S反称传递
（3）T反称
（4）空关系称传递反称

（5）全域关系反称传递


362 定A{1 234} 考虑 a
关系 R R{ ＜13＞＜14＞
＜23＞＜ 24＞＜34＞}
a) A×A坐标图标出 R绘出
关系图
b) Rⅰ)反ⅱ）称ⅲ )传
递iv) 反称？
解
a）













R传递反称
反称

363 举出A{1 23}关系 R
例子具述性质：
a）称反称
b）R称反称
c）R传递

解
a）R{ ＜11＞＜22＞＜33
＞}
b）R{ ＜12＞＜21＞＜23
＞}
c) R{ ＜12＞＜21＞＜11
＞＜ 22＞＜33＞}

364 果关系 RS反
称传递证明 R∩S反
称传递

证明 设RSX反称
传递关系
1）意 x∈X＜ xx＞∈R＜
xx＞∈S＜ xx＞∈R∩S
R∩SX反
2）意＜ xy＞∈R∩S＜ x
y＞∈R∧＜xy＞∈S RS
称必＜ yx＞∈R∧
＜yx＞∈S＜yx＞∈R∩S
R∩SX称
3）意＜ xy＞∈R∩S∧＜yz
＞∈R∩S
＜xy＞∈R∧＜xy＞∈S∧＜y
z＞∈R∧＜yz＞∈S
RS传递＜ xz＞
∈R∧＜xz＞∈S＜ xz＞∈R∩
S R∩SX传递

365 定 S{1 234} S关
系：R{ ＜12＞＜ 43＞＜22
＞＜ 21＞＜31＞}
说明 R传递找出关系 R 1 ⊇R
R 1 传递找 出







1 2


4
3 dintin@gmailcom 28
371 设R 1R 2A意关系
说明命题真假予证明
a）R1 R 2反 R 1○R 2
反
b）R1 R 2反反 R 1○R 2
反反
c）R1 R 2称 R 1○R 2
称
d）R1 R 2传递 R 1○R 2
传递

证明 a ）意 a∈A设R 1R 2
反＜ aa＞∈R 1＜ aa＞∈R 2
＜ aa＞∈R 1 ○R 2 R 1 ○R 2
反

b）假例：设 A{a b} R 1{ ＜
ab＞}R 2{ ＜ba＞}
R1 R 2反反 R 1○R 2{ ＜aa
＞} R 1○R 2A反反

c)假例：设 A{a bc}
R1 { ＜ab＞＜ ba＞＜cc＞}
R2 { ＜bc＞＜ cb＞}
R1 R 2称 R 1 ○R 2{ ＜ac＞
＜cb＞}
R 1 ○R 2 称

d）假例：设 A{a bc}
R1 { ＜ab＞＜ bc＞＜ac＞}
R2 { ＜bc＞＜ ca＞＜ ba＞}
R 1R 2传递 R 1 ○R 2{ ＜a
c＞＜ aa＞＜ ba＞}
R 1 ○R 2 传递

372 证明 S集合 X二元关
系：
a）S传递仅（ S○S）⊆S
b）S反仅 IX ⊆S
c）证明定理 373 （b）（ S反
称仅 S∩S c ⊆IX）

证明 a ）设 S传递＜ xz＞
∈S○S存某 y∈X＜ xy
＞∈S＜ yz＞∈S
S传递＜ x z＞∈S（ S○S）
⊆S

反设（ S○S）⊆S 假定＜ xy＞
∈S＜ yz＞∈S＜ xz＞∈S○S
（ S○S）⊆S＜ xz＞∈S
S传递

b）设 S反令＜ xy＞∈IX
xy ＜ xx＞∈S＜ xy
＞＜xx＞∈SIX ⊆S

反令 IX⊆S设意 x∈X＜xx
＞∈IX＜ xx＞∈S S
反

c）设S反称假定＜ xy＞∈
S∩S c
＜xy＞∈S∧＜ xy＞∈S c ⇒＜xy
＞∈S∧＜ yx＞∈S
S反称 x＝y
＜ xy＞＝＜ xx＞∈IXS∩
S c⊆IX

反 S∩S c⊆IX设＜ xy＞∈S
＜yx＞∈S
＜xy＞∈S∧＜ xy＞∈S c
⇔＜xy＞∈S∩S c
⇒＜xy＞∈IX
x＝yS反称

373 设SX关系证明 S
反传递 S○SS 逆真
？

证明 SX传递关系题
372a ）知（ S○S）⊆S
令＜xy＞∈S根反性必＜
xx＞∈S＜ xy＞∈S○S
S⊆S○S SS ○S

定理逆真例 X{1 23}
S{ ＜12＞＜ 22＞＜ 11＞}dintin@gmailcom 29
381 根图 381 中图写出邻接矩阵关系 R求出 R反闭包称闭包
解

MR


R{ ＜aa＞＜ ab＞＜ bc＞＜ cb＞＝
r（R） R ∪IX { ＜aa＞＜ bb＞＜ cc＞＜ ab＞＜ bc＞＜ cb＞＝
s（R） R ∪RC{＜aa＞＜ ab＞＜ ba＞＜ bc＞＜ cb＞}

382 设集合 A{a bcd}A 关系
R{ ＜ab＞＜ ba＞＜ bc＞＜ cd＞}
a） 矩 阵运算作图方法求出 R反称传递闭包
b） Warshall 算法求出 R传递闭包
解 a）

MR



R关系图图示





MR +MIA



r（R） R ∪IA
{＜aa＞＜ ab＞＜ba＞＜ bb＞＜ bc＞＜ cc＞＜ cd＞＜
dd＞}（图（ a））






MR +MRc


1 1 0
0 0 1
0 1 0
0 1 0 0 1 0 0 0
1 0 1 0 0 1 0 0
0 0 0 1 0 0 1 0
0 0 0 0


+
0 0 0 1
0 1 0 0 0 1 0 0
1 0 1 0 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0


+
0 0 1 0
a

b c
图381


a b

d c



a b

d c

图（ a）
0 1 0 0
1 0 1 0
0 0 0 1
0 0 0 0

1 1 0 0
1 1 1 0
0 0 1 1
0 0 0 1


0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0

dintin@gmailcom 30
391 4 元素集合少划分
解 整数4划分： 41+31+1+2 2+2 1+1+1+1
1+C 4
1+C 4
2+1
2 C 4
2+115 （种）
392 设{A 1A 2… A k}集合 A划分定义 A二元关系 R＜ ab
＞∈R仅 ab划分块中证明 R反称传递
证明 设意 a∈A必存 Aia∈Aiaa必作块中＜ aa＞
∈RR反
设ab ∈A＜ ab ＞∈Rab必块 ba块＜ b a ＞
∈RR称
意 abc ∈A
＜ab＞∈R∧＜bc ＞∈R
⇒（∃i）（a∈Ai∧b∈Ai）∧（ ∃j）（ b∈A j∧c∈A j）
⇒（∃i）（∃j）（a∈Ai∧c∈Aj∧b∈A i∩A j）
⇒（∃i）（∃j）（a∈Ai∧c∈Aj∧A i∩Aj≠Ø）
⇒（∃i）（∃j）（a∈Ai∧c∈Aj∧ij）（∵ i≠j⇒A i∩A j Ø）
⇒ac 块
⇒＜ac ＞∈R
∴R传递 dintin@gmailcom 31
3101 设RR′集合 A等价关系例子说明： R∪R′定等价关系
证明 设 A{123}SR∪R′
R{＜11＞＜22＞＜33＞＜ 31＞＜ 13＞}
R′{＜11＞＜ 22＞＜ 33＞＜ 32＞＜ 23＞}
R∪R′{＜11＞＜ 22＞＜ 33＞＜ 31＞＜ 13＞＜ 32＞＜ 23＞}
＜ 23＞∈S∧＜31＞∈S＜ 21＞∉S R∪R′传递 R∪R′
A等价关系

3102 试问 4元素组成 限集等价关系数少？
解 集合 X等价关系 X划分应 4元素限集等价关系
数目 4元素集合进行划分数目相题 391知 15 等
价关系

3103 定集合 S{12345}找出 S等价关系 R关系 R产生划分 {{1
2}{3}{45}}画出关系图
解 方法产生等价关系：
R1{12}×{12}{ ＜11＞＜12＞＜21＞＜ 22＞}
R2{3} ×{3}{ ＜33＞}
R3{45}×{45}{ ＜44＞＜45＞＜54＞＜ 55＞}
R R 1 ∪R 2∪R3 {＜11＞＜ 12＞＜ 21＞＜ 22＞＜ 33＞＜44＞＜45
＞＜54＞＜55＞}
关系图图







3104 设R二元关系 S{＜ab＞∣某 c＜ ac＞∈R∧＜cb＞∈R}
证明 R等价关系 S等价关系
证明 设RA等价关系：
（1） x∈ARA反 ＜xx＞∈R S定义 ＜xx＞∈S
S反
（2） 意 xy∈A ＜xy＞∈S存某 c＜ xc＞∈R∧＜cy＞
∈R R称：＜ yc＞∈R∧＜ cx＞∈R S定义知＜
yx＞∈S S称
（3） 意 xyz ∈A＜ xy＞∈S＜yz＞∈S必存某 c1＜ x
c1 ＞∈R＜ c1 y＞∈R R传递性知＜ xy＞∈R理存 c2 ＜
yc2 ＞∈R∧＜c2 z＞∈R R传递知＜ yz＞∈R S定义＜ x
z＞∈S S传递

3105 设正整数序偶 集合 A A定义二元关系 R：＜＜ xy＞ ＜uv＞＞∈R
仅 xvyu证明 R等价关系
证明 设A定义二元关系 R：
＜＜xy＞ ＜uv＞＞∈R⇔x
y u
v
1 意＜xy＞∈Ax
y x
y
＜＜xy＞ ＜xy＞＞∈R
R反
2 设＜xy＞∈A＜uv＞∈A
＜＜xy＞ ＜uv＞＞∈R⇒x
y u
v ⇒u
v x
y ⇒＜＜uv＞＜xy＞＞∈R
R称
3 设意＜xy＞∈A＜uv＞∈A＜ws＞∈A
＜＜xy＞ ＜uv＞＞∈R∧＜＜uv＞ ＜ws＞＞∈Rdintin@gmailcom 32
⇒（x
y u
v ）∧（u
v w
s ）⇒x
y w
s
⇒＜＜xy＞ ＜ws＞＞∈R
R传递 RA等价关系
3106 设R集合 A 称传递关系证明果 A中元素 aA中时存 bR中 R
等价关系
证明 意 a∈A必存 b∈A＜ab＞∈R
R传递称：
＜ab＞∈R∧＜b c＞∈R⇒＜a c＞∈R⇒＜ca＞∈R
＜ac＞∈R∧＜c a＞∈R⇒＜aa＞∈R
RA反 RA等价关系
3107 设R1R2 非空集合 A等价关系试确定述式 A等价关系式子提供反例证明
a）（A×A）R1
b）R1R2
c）R1
2
d) r（R1R2）（ R1R2反闭包）
解 a）（A×A）R1 A等价关系例：
A{ab}R1{＜aa＞＜bb＞}
A×A{＜aa＞＜ab＞＜ba＞＜bb＞}
（A×A）R1{＜ab＞＜ba＞}
（A×A）R1 A等价关系
b）设 A{abc}
R1{＜ab＞＜ba＞＜bc＞＜cb＞＜ac＞＜ca＞＜aa＞＜bb＞＜cc＞}
R2{＜aa＞＜bb＞＜cc＞＜bc＞＜cb＞}
R1R2{＜ab＞＜ba＞＜ac＞＜ca＞}
R1R2 A等价关系 R1R2 A等价关系
c） R1A等价关系
＜aa＞∈R1⇒＜aa＞∈R1○R1
R1
2A反
＜ab＞∈R1
2存 c＜a c＞∈R1∧＜cb＞∈R1 R1 称
＜b c＞∈R1∧＜ca＞∈R1⇒＜b a＞∈R1
2
R1
2称
＜ab＞∈R1
2∧＜b c＞∈R1
2
＜ab＞∈R1○R1∧＜b c＞∈R1○R1
⇒（∃e1）（＜a e1＞∈R1∧＜e1 b＞∈R1) ∧（∃e2）（＜b e2＞∈R1∧＜e2 c＞∈R1）
⇒＜ab＞∈R1∧＜b c＞∈R1（∵R1传递）
⇒＜ac＞∈R1
2
R1
2传递
R1
2A等价关系
d） b）设R1R2 A等价关系
r（R1R2）（R1R2）∪IA
{＜ab＞ ＜ba＞ ＜ac＞＜ca＞＜aa＞＜bb＞ ＜cc＞}
A等价关系dintin@gmailcom 33
3108 设C*实数部分非零全体复数组成集合C*关系 R定义：(a+bi)R(c+di)⇔ac>0证明 R等价关系出关系 R
等价类说明
证明：(1)意非零实数 a a2>0⇔(a+bi)R(a+bi)
RC*反
(2) 意(a+bi)R(c+di)⇔ac>0
caac>0⇔(c+di)R(a+bi)
RC*称
(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) RC*传递
关系 R等价类复数面第四象限点第二三象限点两种情况意两点 (ab)(cd)
横坐标积 ac>0
3109 设ΠΠ′非空集合 A 划分设 R R′分ΠΠ′诱导等价关系Π′细分Π充条件 R′ ⊆ R
证明：Π′细分Π假设 aR′bΠ′中某块 S′ ab∈S′Π′细分ΠΠ中必某块 S S′⊆ S ab
∈S aRbR′ ⊆ 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]RS′⊆ S
证明Π′细分Π
31010 设Rj表示 I模 j等价关系Rk 表示 I模 k等价关系证明 IRk细分 IRj 仅 kj整数倍
证明：题设 Rj{|x≡y(modj)}
Rk{|x≡y(modk)}
∈Rj⇔xyc⋅j (某 c∈I)
∈Rk⇔xyd⋅k (某 d∈I)
a)假设 IRk细分 IRj Rk ⊆ Rj
∈Rk⇒∈Rj
k01⋅kc⋅j (某 c∈I)
kj整数倍
b)某 r∈I krj ：
∈Rk⇔xyck (某 c∈I)
⇒ xycrj (某 cr∈I)
⇒∈Rj
Rk ⊆ Rj IRk细分 IRj34
5 1 代 数 系 统 引 入
511 设 集 合 A{1 2 3… 10} 问面定义二元运算 *关 集 合 A 否 封 闭 ？
a） x*ymax(xy)
b） x*ymin(xy)
c） x*yGCD(xy) （ 公 约 数 ）
d） x*yLCM(xy) （ 公 倍 数 ）
e） x*y 质 数 p 数 中 x≤ p≤ y
解 ： a ） 封 闭 b） 封 闭 c ） 封 闭 d） 封 闭 e） 封 闭
512 表列出集合运算中请根运算否相应集合封闭相应位置填
写否中 I 表 示 整 数 集 N 表 示 然 数 集 合
运 算 否 封 闭
集 合 + ∣ xy ∣ max min ∣ x∣
I
N
{x∣ 0≤ x ≤ 10}
{x ∣ 10 ≤ x≤ 10}
{2x ∣ x∈ I}
解 ：
运 算 否 封 闭
集 合 + ∣ xy ∣ max min ∣ x∣
I
N 否
{x∣ 0≤ x ≤ 10} 否 否
{x ∣ 10 ≤ x≤ 10} 否 否 否
{2x ∣ x∈ I}
5 2 运 算 性 质
521 实 数 集 合 R表列二元运算否具左边列中性质请相应位置
填写否
+ × max min ∣ x y∣
结 合 律
交 换 律
单 位 元
零 元
解 ：
+ × max min ∣ x y∣
结 合 律 否 否
交 换 律 否
单 位 元 否 否 否 否
零 元 否 否 否 否 否

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档