离散数学基础试题（）
判断题(题2分12分)
1设AB意命题公式吸收律(A∧B)∨ A ( )
2 x (F(y) →G(x)) F(y) → xG(x) ( )
3图中初级回路简单回路 ( )
4图G中存桥G点连通度边连通度0 ( )
5设ABC意三集合A×(B×C)A×(B×C) ( )
6设A{abc} Rí A×AR{} R传递 ( )
二填空题(空3分30分)
1设p 天雨q 天刮风r 书店命题果天雨刮风书
店符号化形式_______________
2设F(x) xG(x) x右手写字命题右手写字阶逻辑中符
号化形式_______________
3p q合取范式____________
4设Gn阶m条边简单边通图G生成树应G基割集系统中
均________________元素
5完全二部图Krs边连通度λ等_________________
61111224树度数列生成_________________棵非构
树
7设A{ab}A__________偏序关系
8设A{abc}B{123}AB产生_____________双射函数
9设An(n≥1)元集A22n二元运算中______________AA函数
10设A{1 2 3}A定义二元运算： xy A x*ymin{xy}*运算表___________
三计算题(43分)
1求(q p)ù pù r析取范式（写出程）（6分）
2求公式 xF(x) yG(xy) 前束范式（6分）
3已知图G11条边2度3度顶点2余4度顶点求G中
顶点（写出程）
4求棵带权11122345优二元树T计算W(T)(6分) 5设二元关系R{ <{a} b><{φ} {φ}> <{φ} {φ}>}求：(6分)
（1）domR
（2）ranR
（3）R° R
（4）R1° R1
6设A{a b c d e f} RIA∪{ }RA等价关系(6分)
(1)求a等价类[a]R
(2)求c等价类[c]R
(3)求商集AR
7设R’非零数集式右边运算普通四运算（7分）
(1) ab R’ a° b
(2) ab R’ a*bab
(3) ab R’ aD ba× b
试确定三代数系统中群群求单位元元素逆元
四证明题(题5分15分)
1命题逻辑然推理系统P中构造面推理证明：
前提：(pú q) r1 rú s s 结： p
2设G连通简单图已知δ(G)≥2
证明：G中存长度等3初级回路
3设AB二集合已知Aí B
证明：P(A) í P(B)中P(B) P(B)分AB幂集
判断题（题2分12分）
1命运题逻辑中命题公式合取范式存唯（）
2等值（）
3设非连通面图G偶图设分顶点数边数面数间满足欧拉公式：（）
4设图G具割点G中定存哈密尔顿通路（）
5设A恒等关系A等价关系A偏序关系（）
6设ABCD均非空集合已知A*BC*D定 （）
二填空题（题3分30分）
1设p王走路q王听音乐命题逻辑中命题王边走路边听音乐符号化形式___________________
2设F(x)xH(xy)xy样高阶逻辑中命题样高符号化形式_________________
3成真赋值________________________
4设Gn阶带权边通图变权均a(a>0)设TG棵生成树T权W(T)_______________________
5设G1G2G3G44阶3条边简单图间少___________________构
6．设Gn（n2）阶二部图面图命题G偶图欧拉图真值_______________________
7设整数集f值域ranf___________
8设A____________等价关系
9设恒等关系IA传递闭包t(IA)_________________
10实数集合R定义二元运算：____________中普通减法命题代数系统真值___________________
三计算题（43分）
1求面公式析取范式(写程6分)
2求面公式前束范式（6分）
3画棵带权22233458优二元树T计算权W（T）（6分）
4（1）棵22度顶点43度顶点余顶点树叶树中应该片树叶？（2）画出两棵非构满足（1）中顶点度数树T1T2（6分）
5设全集E{123456}子集A{12}B{234}C{56}求面集合：（1） （2） （3）（6分）
6设偏序集中A{1234692454}A整关系
（1）画出哈斯图
（2）求R关A极元
（3）求B{469}界界（6分）
7GA{abc}*运算表：（7分）
1）G否阿贝尔群？
（2）找出G单位元
（3）找出G幂等元
（4）求b逆元c逆元
四证明题（题5分15分）
1阶逻辑中构造面证明：前提：F(a)结（5分）
2图G图示（1）证明G哈密尔图（2）引证G面图（5分）
3设AB全集E子集已知证明（5分）
离散数学试题(A卷答案)
证明题（10分）
1)((P∨Q)∧Ø(ØP∧(ØQ∨ØR)))∨(ØP∧ØQ)∨(ØP∧ØR)ÛT
证明 左端Û((P∨Q)∧(P∨(Q∧R)))∨Ø((P∨Q)∧(P∨R))(摩根律)
Û ((P∨Q)∧(P∨Q)∧(P∨R))∨Ø((P∨Q)∧(P∨R))(分配律)
Û ((P∨Q)∧(P∨R))∨Ø((P∨Q)∧(P∨R)) (等幂律)
ÛT (代入)
2)x(P(x)®Q(x))∧xP(x)Ûx(P(x)∧Q(x))
证明：x(P(x)®Q(x))∧xP(x)Ûx((P(x)®Q(x)∧P(x))
Ûx((ØP(x)∨Q(x)∧P(x))
Ûx(P(x)∧Q(x))ÛxP(x)∧xQ(x)
Ûx(P(x)∧Q(x))
二求命题公式(ØP®Q)®(P∨ØQ) 析取范式合取范式（10分）
解：(ØP®Q)®(P∨ØQ)ÛØ(ØP®Q)∨(P∨ØQ)
ÛØ(P∨Q)∨(P∨ØQ)
Û(ØP∧ØQ)∨(P∨ØQ)
Û(ØP∨P∨ØQ)∧(ØQ∨P∨ØQ)
Û(P∨ØQ)ÛM1
Ûm0∨m2∨m3
三推理证明题（10分）
1)(P®(Q®S))∧(ØR∨P)∧QÞR®S
证明：（1）R 附加前提
（2）ØR∨P P
（3）P T(1)(2)I
（4）P®(Q®S) P
（5）Q®S T(3)(4)I
（6）Q P
（7）S T(5)(6)I
（8）R®S CP
2) x(P(x)∨Q(x))xØP(x)Þx Q(x)
证明：(1)xØP(x) P
(2)ØP(c) T(1)US
(3)x(P(x)∨Q(x)) P
(4)P(c)∨Q(c) T(3)US
(5)Q(c) T(2)(4)I
(6)x Q(x) T(5)EG
四边长1正方形意放置九点证明中必存三点组成三角形（退化）面积超18（5分）
证明：边长1正方形分成四全等正方形少正方形三点组成三角形（退化）面积超正方形半18
五已知ABC三集合证明A∩(B∪C)(A∩B)∪(A∩C) （10分）
证明：∵xÎ A∩（B∪C）Û xÎ A∧xÎ（B∪C）
Û xÎ A∧（xÎB∨xÎC）
Û（ xÎ A∧xÎB）∨（xÎ A∧xÎC）
Û xÎ（A∩B）∨xÎ A∩C
Û xÎ（A∩B）∪（A∩C）
∴A∩（B∪C）（A∩B）∪（A∩C）
六A{ x1x2x3 }B{ y1y2}R{}求关系矩阵关系图（10分）
解：关系矩阵
七设R{<21><25><24><34><44><52>}求r(R)s(R)t(R)作出R关系图（15分）
解：r(R){<21><25><24><34><44><52><11><22><33><44><55>}
s(R){<21><25><24><34><44><52><12><42><43>}
R2R5{<22><24><34><44><51><55><54>}
R3{<21><25><24><34><44><52><54>}
R4{<22><24><34><44><51><55><54>}
t(R){<21><25><24><34><44><52><22><51><54><55>}
八p{A1A2…An}集合A划分定义R{|ab∈AiI12…n}RA等价关系（15分）
证明：a∈A必ia∈Ai定义知aRaR反
ab∈AaRb ab∈Aiba∈AibRaR称
abc∈AaRb bRcab∈Aibc∈Aji≠j时Ai∩AjFijabc∈AiaRcR传递
总RA等价关系
九fA→B双射f1B→A双射（15分）
证明意x∈AfAB函数存y∈B∈f∈f1f1满射
意x∈A存y1y2∈B∈f1∈f1∈f∈ff函数y1y2f1单射
f1双射
离散数学试题(B卷答案）
证明题（10分）
1)(ØP∧(ØQ∧R))∨(Q∧R)∨(P∧R)ÛR
证明 左端Û(ØP∧ØQ∧R)∨((Q∨P)∧R)
Û((ØP∧ØQ)∧R))∨((Q∨P)∧R)
Û(Ø(P∨Q)∧R)∨((Q∨P)∧R)
Û(Ø(P∨Q)∨(Q∨P))∧R
Û(Ø(P∨Q)∨(P∨Q))∧R
ÛT∧R(置换)ÛR
2)x(A(x)®B(x))Û xA(x)®xB(x)
证明 ：x(A(x)®B(x))Ûx(ØA(x)∨B(x))
ÛxØA(x)∨xB(x)
ÛØxA(x)∨xB(x)
ÛxA(x)®xB(x)
二求命题公式(P∨(Q∧R))®(P∧Q∧R)析取范式合取范式（10分）
证明：(P∨(Q∧R))®(P∧Q∧R)ÛØ(P∨(Q∧R))∨(P∧Q∧R))
Û（ØP∧(ØQ∨ØR)）∨(P∧Q∧R)
Û(ØP∧ØQ)∨(ØP∧ØR))∨(P∧Q∧R)
Û(ØP∧ØQ∧R)∨(ØP∧ØQ∧ØR)∨(ØP∧Q∧ØR))∨(ØP∧ØQ∧ØR))∨(P∧Q∧R)
Ûm0∨m1∨m2∨m7
ÛM3∨M4∨M5∨M6
三推理证明题（10分）
1） C∨D (C∨D)® ØE ØE®(A∧ØB) (A∧ØB)®(R∨S)ÞR∨S
证明：(1) (C∨D)®ØE P
(2) ØE®(A∧ØB) P
(3) (C∨D)®(A∧ØB) T(1)(2)I
(4) (A∧ØB)®(R∨S) P
(5) (C∨D)®(R∨S) T(3)(4) I
(6) C∨D P
(7) R∨S T(5)I
2) x(P(x)®Q(y)∧R(x))xP(x)ÞQ(y)∧x(P(x)∧R(x))
证明(1)xP(x) P
(2)P(a) T(1)ES
(3)x(P(x)®Q(y)∧R(x)) P
(4)P(a)®Q(y)∧R(a) T(3)US
(5)Q(y)∧R(a) T(2)(4)I
(6)Q(y) T(5)I
(7)R(a) T(5)I
(8)P(a)∧R(a) T(2)(7)I
(9)x(P(x)∧R(x)) T(8)EG
(10)Q(y)∧x(P(x)∧R(x)) T(6)(9)I
四某班25名学生中14会篮球12会排球6会篮球排球5会篮球网球2会三种球6会网球会外种球求会三种球数（10分）
解：ABC分表示会排球网球篮球学生集合|A|12|B|6|C|14|A∩C|6|B∩C|5|A∩B∩C|2
先求|A∩B|
∵6|（A∪C）∩B||（A∩B）∪（B∩C）||（A∩B）|+|（B∩C）||A∩B∩C||（A∩B）|+52∴|（A∩B）|3
|A∪B∪C|12+6+14653+220会三种球数25205
五已知ABC三集合证明A(B∪C)(AB)∩(AC) （10分）
证明：∵xÎ A（B∪C）Û xÎ A∧xÏ（B∪C）
Û xÎ A∧（xÏB∧xÏC）
Û（xÎ A∧xÏB）∧（xÎ A∧xÏC）
Û xÎ（AB）∧xÎ（AC）
Û xÎ（AB）∩（AC）
∴A（B∪C）（AB）∩（AC）
六已知RSN关系定义：R{| xyÎN∧yx2}S{| xyÎN∧yx+1}求R1R*SS*R
R{12}S[{12}]（10分）
解：R1{| xyÎN∧yx2}
R*S{| xyÎN∧yx2+1}
S*R{| xyÎN∧y（x+1）2}R{12}{<11><24>}S[{12}]{14}
七设R{}求r(R)s(R)t(R) （15分）
解：r(R){}
s(R){}
R2 R5{}
R3{}
R4{}
t(R){}
八证明整数集I模m余关系R{|xºy(mod m)}等价关系中xºy(mod m)含义xym整（15分）
证明：1）x∈I（xx）m0xºx(mod m)xRx
2）xy∈IxRyxºy(mod m)（xy）mk∈I（y x）mk∈Iyºx(mod m)yRx
3）xyz∈IxRyyRz（xy）mu∈I（yz）mv∈I（xz）m（xy+yz）mu+v ∈IxRz
九fA→BgB→C双射（gf）1f1g1（10分）
证明：fg双射gf：A→C双射gf逆函数（gf）1：C→A理推f1g1：C→A双射
∈f1g1Û存z（∈g1Ù∈f1）Û存z（∈fÙ∈g）Û∈gfÛ∈（gf）1（gf）1f1g1
计算机数学基础离散数学试题
单项选择题(题2分10分)
1列命题公式等值( )
2 谓词公式取真值1充分必条件( )
(A) 意yP(y)取真值1 (B) 存y0P(y0)取真值1
(C) 存某yP(y)取真值1 (D) 存y0P(y0)取真值0
3 设集合A＝{0b}B{1b3}AÈB恒等关系 ( )
(A) {<00><11><33>} (B){<00><11><33>}
(C) {<11><33>} (D) {<01><1b><30>}
4 已知集合A＝{abc}二元关系R关系矩阵MR＝R＝( )
(A) {} (B) {}
(C) {} (D) {}
5设V＝{abcd}V构成强连通图边集E＝( )
(A) {} (B) {}
(C) {} (D) {}
二填空题(题3分15分)
6 设命题公式G：P®Ø(Q®P)公式G假真值指派
7 设P：划船G：跑步命题划船跑步符号化
8 设体域D＝{12}谓词公式消量词等值式
9设图D＝邻接矩阵A(D)½E½＝
10 连通图G含欧拉回路充分必条件
三化简解答题(题8分32分)
11 回答问题：列集合中相等 说明理
A1＝{ab} A2＝{ba} A3＝{aab} A4＝{abc}
A5＝{} A6＝{}
(2) 设图G＝ 图G中½V½½E½满足什条件图G定树
13判谓词公式类型
四．计算题(题8分24分)
14求命题公式合取范式
15 设全集E＝(abcdef) A{ad}B{abe}C{bd}求列集合：
(1) (2)
v4 h h v3
v1 h h v2
第16题图
16 已知图D(第16题图)邻接矩阵
A(D)
求v2v4长度2v3v3长度
2通路条数具体写出
17 设代数系统(Z*)中Z整数集二元运算定义
求a逆元
五证明题(第18题10分第19
题9分) 18 设R集合A称关系传递关系试证明：aÎAbÎA(ab)ÎRR等价关系
19 设格(LÙÚ)满足分配律证明
计算机数学基础离散数学试题解答
单项选择题(题2分15分)
1C 2 A 3B 4D 5A
二填空题(题3分15分)
6 1011
7
8 A(1)ÚA(2)Ú(B(1)ÙB(2))
9 7
10 含奇数度结点
三化简解答题(题8分32分)
11集合中元素序重复A1＝A2＝A3 (3分)
(x－a)(x－b)(x－c)0解xabcx2－(a+b)x+ab0解xab (6分)
A1＝A2＝A3＝A6A4＝A5 (8分)
h h
h h
h h
h h
第12题答案图
h
12 (1)
图G嵌入图第12题答案图
图G面图 (4分)
(2) 图G连通½E½＝½V½－1
图G定树 (8分)
13 设I意解释DI体域 解释I该公式前件0
取值1 (2分)
解释I该公式前件11蕴含着11y¢意性必11
总意解释I1 该公式永真式 (8分)
四计算题(题8分24分)
14
15 (1) (4分)
(2)
＝ (8分)
16 A2(D) (4分)
矩阵A2(D)中a242a332知
v2v4长度2通路2条 ： v2v3v4v2v1v4 (6分)
v3v3长度2通路2条 ： v3v4v3v3v2v3 (8分)
17 易知二元运算满足交换律
∵aÎZ a*2a+2－2＝a＝2*a2ÎZ单位元 (3分)
aÎZ a逆元记作a－1
(单位元) ＼ a－14－a (8分)
五证明题(第18题10分第19题9分)
18 已知R称关系传递关系需证明R反关系 (3分)
aÎAbÎA(ab)ÎRR称(ba)ÎR (6分)
R传递(ab)ÎR(ba)ÎRÞ(aa)ÎR元素a意性知R反 (9分)
R等价关系 (10分)
19
＝ (分配律) (3分)
＝ (幂等律) (6分)
＝ (吸收律) (9分)
外种法：pq真时析取起假两命题取项真称排斥(排异)p排斥q表示 例：天晚电影球
例13 列命题符号化
(1) 张晓静爱唱歌爱听音乐
(2) 张晓静江西安徽
解 解题时先原子命题符号化
(1) p：张晓静爱唱歌
q：张晓静爱听音乐
显然(1)中相容pq时真符号化p∨q
(2) r：张晓静江西
s：张晓静安徽
易知(2)中应排斥rs时真符号化r排斥s
1．然语言里特数学中qp必条件许叙述方式例pqpqp仅qqp非q否非p等等种叙述方式表面表达qp必条件联结词均应符号化→述种叙述方式应符号化p→q
课作业
列命题符号化：
命题中出现a定正整数：
(5)a4整a定2整
(6)a4整仅a2整
(7)非a2整a4整
(8)非a2整否a4整
(9)a2整a4整
(10)a4整a2整
解：令r：a4整
s：a2整
仔细分析知(5)(9)五命题均叙述a2整a4整必条件叙述符号化r→s(10)中a4整成a2整必条件应符号化s→r
（3）p∧(((p∨q)∧┐p)→q)
ó p∧(┐((p∨q)∧┐p)∨q)
ó p∧(┐((p∧┐p)∨(q∧┐q))∨q)
ó p∧(┐(0∨(q∧┐p))∨q)
ó p∧(┐q∨p∨q)
óp∧1
ó p
结果说明（3）中公式重言式0001成假赋值矛盾式1011成真赋值
四 等价判定定理
• 定理132 两重言式合取析取然重言式
• 定理133 重言式分量合式公式置换结果重言式
• 定理134 A B两命题公式 A B仅A B重言式
14 蕴含式
定义141 仅A→B重言式称A蕴含B记A > B
A→B种变换式：
逆换式 B→ A
反换式 ┐ A→ ┐ B
逆反式 ┐ B → ┐ A
等价式知：A →B ┐ B → ┐ A
蕴涵式证明两种方法：
① 前件真导件真方法
设公式前件真推导出件真条件式永真式蕴涵式成立
欲证AÞB证A®B永真式A®BA取真B取假时A®B假外余A®B皆真A®B前件A真推出B真A®B永真式AÞB
② 件假导前件假方法
设条件式件假推导出前件假条件式永真式蕴涵式成立
A→B件B取假推出A取假推证：ùBùÞAA→BùÛB→ùAAÞB成立
例题1 推证： ┐ q ∧(p→q) ┐p
想证明A B假定AT证明BT
假定BF证明AF
证法1 假定┐ q ∧(p→q)T┐ qT (p→q)TqF (p→q)T必须pF┐pT
证法2 假定┐pFpT
a) qF(p→q)F ┐ q ∧(p→q)F
b) qT ┐ qF ┐ q ∧(p→q)F
┐ q ∧(p→q) ┐p 成立
求((Ｐ∧┐Ｑ)«(P→R)析取范式合取范式
解(Ｐ∧┐Ｑ)«(P→R)
((Ｐ∧┐Q)→(P→R))∧((P→R)→(Ｐ∧┐Ｑ))
(┐(Ｐ∧┐Ｑ)∨(P→R))∧(┐(P→R)∨(Ｐ∧┐Ｑ))
((┐Ｐ∨Ｑ)∨(┐P∨R))∧(┐(┐P∨R)∨(Ｐ∧┐Ｑ))
(┐Ｐ∨Ｑ∨┐P∨R)∧((P∧┐R)∨(Ｐ∧┐Ｑ))
(┐Ｐ∨Ｑ∨R)∧P∧(┐R∨┐Ｑ)───合取范式
((┐Ｐ∧P)∨(Ｑ∧P)∨(R∧P))∧(┐R∨┐Ｑ)
(Ｑ∧P∧┐R)∨(R∧P∧┐R)∨
(Ｑ∧P∧┐Q)∨(R∧P∧┐Ｑ)
(Ｑ∧P∧┐R)∨(R∧P∧┐Ｑ)───析取范式
• 例两命题变元PQ构成项PÙQPùÙQùPÙQùPùÙQ三命题变元PQR构成项PÙQÙRPÙQùÙRPùÙQÙRPùÙQùÙRùPÙQÙR ùPÙQùÙRùPùÙQÙRùPùÙQùÙR
• 证明n命题变元形成2n项
• 两命题变元PQ构成项PÚQPùÚQùPÚQùPùÚQ三命题变元PQR构成PÚQÚRPÚQùÚRPùÚQÚRPùÚQùÚRùPÚQÚRùPÚQùÚRùPùÚQÚRùPùÚQùÚR够证明n命题变元2n项
• ３析取范式合取范式间关系
ù mi Û Mi
(1)求析取范式
(a)真值表知该公式G恰五解释公式取值真选出已公式取值1行应变元取值：
2 0014011
5 1 0 0 6 1 0 1
8 111
行应极项分：
┐P∧┐Ｑ∧Ｒ┐P∧Ｑ∧ＲP∧┐Ｑ∧┐ＲP∧┐Ｑ∧ＲP∧Ｑ∧Ｒ
极项析取该公式G析取范式
G┐（Ｐ→Ｑ）∨Ｒ
(┐P∧┐Ｑ∧Ｒ) ∨(┐P∧Ｑ∧Ｒ) ∨(P∧┐Ｑ∧┐Ｒ) ∨(P∧┐Ｑ∧Ｒ) ∨(P∧Ｑ∧Ｒ)
(2)求合取范式
(a)真值表知该公式G恰三解释公式取值假选出已公式取值0行应变元值：
10 0 030 1 071 1 0
• 行应极项分：
• P∨Ｑ∨ＲP∨┐Ｑ∨Ｒ┐Ｐ∨┐Ｑ∨Ｒ
• 极项合取该公式G合取范式：
• G┐（Ｐ→Ｑ）∨Ｒ
• ( P∨Ｑ∨Ｒ)∧(P∨┐Ｑ∨Ｒ)∧(┐Ｐ∨┐Ｑ∨Ｒ)
– ３推理定律
• 推理程中推理规需许条推理定律定律前讲命题定律蕴涵式运定理171面出蕴涵式出推理定律：
• (1) PQÞP
• (2) PQÞQ
• (3) PÞP∨Q
• (4) ùPÞP→Q
• (5) QÞP→Q
• (6) ù(P→Q)ÞP
• (7) ù(P→Q)ùÞQ
• (8) P(P→Q)ÞQ
• (9) ùQ(P→Q)ùÞP
• (10) ùP(P∨Q)ÞQ
• (11) (P→Q)(Q→R)ÞP→R
• (12) (P«Q)(Q«R)ÞP«R
• (13) (P→Q)(R→S)(P∧R)ÞQ∧S
• (14) (P→Q)(R→S)∧(P∨R)ÞQ∨S
• 特QS时
• (P→Q)(R→Q)(P∧R)ÞQ
• (P→Q)(R→ Q)(P∨R)ÞQ
• (15)P→QÞ(P∨R)→(Q∨R)
• P→QÞ(P∧R)→(Q∧R)
例1 设前提Г{P∨QP«RQ→S}公式GS∨R证明 ГÞG
证：法1：⑴ P∨Q P
⑵ ┐P→Q T(1)E
⑶ Q→S P
⑷ ┐P→S T⑵⑶I
⑸ ┐S→P T⑷E
⑹ P«R P
⑺ (P→R)Ù(R→P) Ｔ⑹E
⑻ P→R Ｔ⑺I
⑼ ┐S→R T⑸⑻I
⑽ S∨R T⑺E
设Г{P→(Q→S)┐R∨PQ} GR→S证明：ГÞG
证：⑴ R P(附加前提)
⑵ ┐R∨P P
⑶ P T⑴⑵I
⑷ P→(Q→S) P
⑸ Q→S T⑶⑷I
⑹ Q P
⑺ S T⑸⑹I
⑻ R→S CP⑴⑺
果天星期进行离散数学数结构考试果数结构课老师生病考数结构天星期数结构老师生病天进行离散数学考试
• 解：设P：天星期
• Q：进行离散数学考试
• R：进行数结构考试
• S：数结构课老师生病
• P→Q ∨ RS→┐RP∧SÞQ
• 证 ⑴ P∧S Ｐ
• ⑵ S Ｔ⑴I
• ⑶ S→┐R Ｐ
• ⑷ ┐R Ｔ⑵(3)I
• ⑸ P Ｔ⑴I
• ⑹ P→Q R Ｐ
• ⑺ Q R Ｔ⑸⑹I
• ⑻ Q Ｔ⑷⑺I
例6 反证法证明二难推
P∨Q P→R Q→R Þ R
证： ⑴ ┐R Ｐ(附加前提)
⑵ P→R P
⑶ ┐P T⑴⑵I
⑷ Q→R P
⑸ ┐Q T⑵⑷I
⑹ P∨Q Ｐ
⑺ P Ｔ⑸⑹I
⑻ P∧┐P Ｔ⑶⑺I
设公式：P(a)∧(x)P(x)(x)P(x)→P(a)求公式真值中①体域D＝{23}②a指定：2③P(2)指定：1P(3)指定：0
：P(a)∧(x)P(x)
＝P(2)∧(P(2)∧P(3))＝1∧(1∧0)＝0
(x)P(x)→P(a)
＝(P(2)∧P(3))→P(2)＝(1∧0)→1＝1
例213：求公式真值：P(a)→(x)P(x)
(x)P(x)→P(a)
解：（1）解释I：
（a）P(a)取值真时P(x)必真时
P(a)→(x)P(x)真值真
（b）P(a)取值假时P(x)真假时P(a)→(x)P(x)真值真
公式P(a)→(x)P(x)关切结构切赋值恒取T值谓词公式
§ (a) (x)(A(x)∧B)Û(x)A(x)∧B
§ (b) (x)(A(x)∨B)Û(x)A(x)∨B
§ (c) (x)(A(x)→B)Û(x)A(x)→B
§ (d) (x)(B→A(x))ÛB→(x)A(x)
§ (e) (x)(A(x)∧B)Û(x)A(x)∧B
§ (f) (x)(A(x)∨B)Û(x)A(x)∨B
§ (g) (x)(A(x)→B)Û(x)A(x)→B
§ (h) (x)(B→A(x))ÛB→(x)A(x)
1) E22：(x)G(x)＝(y)G(y)
E23：(x)G(x)＝(y)G(y)
1) E24：┐(x)G(x)＝(x)┐G(x)
E25：┐(x)G(x)＝(x)┐G(x)
1) E26：(x)(G(x)∨S)＝(x)G(x)∨S
E27：(x)(G(x)∧S)＝(x)G(x)∧S
E28：(x)(G(x)∨S)＝(x)G(x)∨S
E29：(x)(G(x)∧S)＝(x)G(x)∧S
4) E30：(x)(G(x)∧H(x))＝(x)G(x)∧(x)H(x)
E31：(x)(G(x)∨H(x))＝(x)G(x)∨(x)H(x)
4) E32：(x)G(x)∨(x)H(x)
＝(x)(y)(G(x)∨H(y))
E33：(x)G(x)∧(x)H(x)
＝(x)(y)(G(x)∧H(y))
4) I16：(x)G(x)Þ(x)G(x)
5) I17：(x)G(x)∨(x)H(x)Þ(x)(G(x)∨H(x))
I18：(x)(G(x)∧H(x))Þ(x)G(x)∧(x)H(x)
4) I19：(x)(G(x)→H(x))Þ(x)G(x)→(x)H(x)
I20：(x)(G(x)→H(x))Þ(x)G(x)→(x)H(x)
9) E34：(x)(y)G(xy)＝(y)(x)G(xy)
E35：(x)(y)G(xy)＝(y)(x)G(xy)
9) I21：(x)(y)G(xy)Þ(y)(x)G(xy)
I22：(x)(y)G(xy)Þ(y)(x)G(xy)
I23：(x)(y)G(xy)Þ(x)(y)G(xy)
I24：(y)(x)G(xy)Þ(x)(y)G(xy)
I25：(x)(y)G(xy)Þ(y)(x)G(xy)
I26：(x)(y)G(xy)Þ(x)(y)G(xy)
I27：(x)(y)G(xy)Þ(x)(y)G(xy)
I28：(y)(x)G(xy)Þ(y)(x)G(xy)
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
判断题(题2分12分)
1设AB意命题公式吸收律(A∧B)∨ A ( )
2 x (F(y) →G(x)) F(y) → xG(x) ( )
3图中初级回路简单回路 ( )
4图G中存桥G点连通度边连通度0 ( )
5设ABC意三集合A×(B×C)A×(B×C) ( )
6设A{abc} Rí A×AR{} R传递 ( )
二填空题(空3分30分)
1设p 天雨q 天刮风r 书店命题果天雨刮风书
店符号化形式_______________
2设F(x) xG(x) x右手写字命题右手写字阶逻辑中符
号化形式_______________
3p q合取范式____________
4设Gn阶m条边简单边通图G生成树应G基割集系统中
均________________元素
5完全二部图Krs边连通度λ等_________________
61111224树度数列生成_________________棵非构
树
7设A{ab}A__________偏序关系
8设A{abc}B{123}AB产生_____________双射函数
9设An(n≥1)元集A22n二元运算中______________AA函数
10设A{1 2 3}A定义二元运算： xy A x*ymin{xy}*运算表___________
三计算题(43分)
1求(q p)ù pù r析取范式（写出程）（6分）
2求公式 xF(x) yG(xy) 前束范式（6分）
3已知图G11条边2度3度顶点2余4度顶点求G中
顶点（写出程）
4求棵带权11122345优二元树T计算W(T)(6分) 5设二元关系R{ <{a} b><{φ} {φ}> <{φ} {φ}>}求：(6分)
（1）domR
（2）ranR
（3）R° R
（4）R1° R1
6设A{a b c d e f} RIA∪{ }RA等价关系(6分)
(1)求a等价类[a]R
(2)求c等价类[c]R
(3)求商集AR
7设R’非零数集式右边运算普通四运算（7分）
(1) ab R’ a° b
(2) ab R’ a*bab
(3) ab R’ aD ba× b
试确定三代数系统中群群求单位元元素逆元
四证明题(题5分15分)
1命题逻辑然推理系统P中构造面推理证明：
前提：(pú q) r1 rú s s 结： p
2设G连通简单图已知δ(G)≥2
证明：G中存长度等3初级回路
3设AB二集合已知Aí B
证明：P(A) í P(B)中P(B) P(B)分AB幂集
判断题（题2分12分）
1命运题逻辑中命题公式合取范式存唯（）
2等值（）
3设非连通面图G偶图设分顶点数边数面数间满足欧拉公式：（）
4设图G具割点G中定存哈密尔顿通路（）
5设A恒等关系A等价关系A偏序关系（）
6设ABCD均非空集合已知A*BC*D定 （）
二填空题（题3分30分）
1设p王走路q王听音乐命题逻辑中命题王边走路边听音乐符号化形式___________________
2设F(x)xH(xy)xy样高阶逻辑中命题样高符号化形式_________________
3成真赋值________________________
4设Gn阶带权边通图变权均a(a>0)设TG棵生成树T权W(T)_______________________
5设G1G2G3G44阶3条边简单图间少___________________构
6．设Gn（n2）阶二部图面图命题G偶图欧拉图真值_______________________
7设整数集f值域ranf___________
8设A____________等价关系
9设恒等关系IA传递闭包t(IA)_________________
10实数集合R定义二元运算：____________中普通减法命题代数系统真值___________________
三计算题（43分）
1求面公式析取范式(写程6分)
2求面公式前束范式（6分）
3画棵带权22233458优二元树T计算权W（T）（6分）
4（1）棵22度顶点43度顶点余顶点树叶树中应该片树叶？（2）画出两棵非构满足（1）中顶点度数树T1T2（6分）
5设全集E{123456}子集A{12}B{234}C{56}求面集合：（1） （2） （3）（6分）
6设偏序集中A{1234692454}A整关系
（1）画出哈斯图
（2）求R关A极元
（3）求B{469}界界（6分）
7GA{abc}*运算表：（7分）
1）G否阿贝尔群？
（2）找出G单位元
（3）找出G幂等元
（4）求b逆元c逆元
四证明题（题5分15分）
1阶逻辑中构造面证明：前提：F(a)结（5分）
2图G图示（1）证明G哈密尔图（2）引证G面图（5分）
3设AB全集E子集已知证明（5分）
离散数学试题(A卷答案)
证明题（10分）
1)((P∨Q)∧Ø(ØP∧(ØQ∨ØR)))∨(ØP∧ØQ)∨(ØP∧ØR)ÛT
证明 左端Û((P∨Q)∧(P∨(Q∧R)))∨Ø((P∨Q)∧(P∨R))(摩根律)
Û ((P∨Q)∧(P∨Q)∧(P∨R))∨Ø((P∨Q)∧(P∨R))(分配律)
Û ((P∨Q)∧(P∨R))∨Ø((P∨Q)∧(P∨R)) (等幂律)
ÛT (代入)
2)x(P(x)®Q(x))∧xP(x)Ûx(P(x)∧Q(x))
证明：x(P(x)®Q(x))∧xP(x)Ûx((P(x)®Q(x)∧P(x))
Ûx((ØP(x)∨Q(x)∧P(x))
Ûx(P(x)∧Q(x))ÛxP(x)∧xQ(x)
Ûx(P(x)∧Q(x))
二求命题公式(ØP®Q)®(P∨ØQ) 析取范式合取范式（10分）
解：(ØP®Q)®(P∨ØQ)ÛØ(ØP®Q)∨(P∨ØQ)
ÛØ(P∨Q)∨(P∨ØQ)
Û(ØP∧ØQ)∨(P∨ØQ)
Û(ØP∨P∨ØQ)∧(ØQ∨P∨ØQ)
Û(P∨ØQ)ÛM1
Ûm0∨m2∨m3
三推理证明题（10分）
1)(P®(Q®S))∧(ØR∨P)∧QÞR®S
证明：（1）R 附加前提
（2）ØR∨P P
（3）P T(1)(2)I
（4）P®(Q®S) P
（5）Q®S T(3)(4)I
（6）Q P
（7）S T(5)(6)I
（8）R®S CP
2) x(P(x)∨Q(x))xØP(x)Þx Q(x)
证明：(1)xØP(x) P
(2)ØP(c) T(1)US
(3)x(P(x)∨Q(x)) P
(4)P(c)∨Q(c) T(3)US
(5)Q(c) T(2)(4)I
(6)x Q(x) T(5)EG
四边长1正方形意放置九点证明中必存三点组成三角形（退化）面积超18（5分）
证明：边长1正方形分成四全等正方形少正方形三点组成三角形（退化）面积超正方形半18
五已知ABC三集合证明A∩(B∪C)(A∩B)∪(A∩C) （10分）
证明：∵xÎ A∩（B∪C）Û xÎ A∧xÎ（B∪C）
Û xÎ A∧（xÎB∨xÎC）
Û（ xÎ A∧xÎB）∨（xÎ A∧xÎC）
Û xÎ（A∩B）∨xÎ A∩C
Û xÎ（A∩B）∪（A∩C）
∴A∩（B∪C）（A∩B）∪（A∩C）
六A{ x1x2x3 }B{ y1y2}R{
解：关系矩阵
七设R{<21><25><24><34><44><52>}求r(R)s(R)t(R)作出R关系图（15分）
解：r(R){<21><25><24><34><44><52><11><22><33><44><55>}
s(R){<21><25><24><34><44><52><12><42><43>}
R2R5{<22><24><34><44><51><55><54>}
R3{<21><25><24><34><44><52><54>}
R4{<22><24><34><44><51><55><54>}
t(R){<21><25><24><34><44><52><22><51><54><55>}
八p{A1A2…An}集合A划分定义R{
证明：a∈A必ia∈Ai定义知aRaR反
ab∈AaRb ab∈Aiba∈AibRaR称
abc∈AaRb bRcab∈Aibc∈Aji≠j时Ai∩AjFijabc∈AiaRcR传递
总RA等价关系
九fA→B双射f1B→A双射（15分）
证明意x∈AfAB函数存y∈B
意x∈A存y1y2∈B
f1双射
离散数学试题(B卷答案）
证明题（10分）
1)(ØP∧(ØQ∧R))∨(Q∧R)∨(P∧R)ÛR
证明 左端Û(ØP∧ØQ∧R)∨((Q∨P)∧R)
Û((ØP∧ØQ)∧R))∨((Q∨P)∧R)
Û(Ø(P∨Q)∧R)∨((Q∨P)∧R)
Û(Ø(P∨Q)∨(Q∨P))∧R
Û(Ø(P∨Q)∨(P∨Q))∧R
ÛT∧R(置换)ÛR
2)x(A(x)®B(x))Û xA(x)®xB(x)
证明 ：x(A(x)®B(x))Ûx(ØA(x)∨B(x))
ÛxØA(x)∨xB(x)
ÛØxA(x)∨xB(x)
ÛxA(x)®xB(x)
二求命题公式(P∨(Q∧R))®(P∧Q∧R)析取范式合取范式（10分）
证明：(P∨(Q∧R))®(P∧Q∧R)ÛØ(P∨(Q∧R))∨(P∧Q∧R))
Û（ØP∧(ØQ∨ØR)）∨(P∧Q∧R)
Û(ØP∧ØQ)∨(ØP∧ØR))∨(P∧Q∧R)
Û(ØP∧ØQ∧R)∨(ØP∧ØQ∧ØR)∨(ØP∧Q∧ØR))∨(ØP∧ØQ∧ØR))∨(P∧Q∧R)
Ûm0∨m1∨m2∨m7
ÛM3∨M4∨M5∨M6
三推理证明题（10分）
1） C∨D (C∨D)® ØE ØE®(A∧ØB) (A∧ØB)®(R∨S)ÞR∨S
证明：(1) (C∨D)®ØE P
(2) ØE®(A∧ØB) P
(3) (C∨D)®(A∧ØB) T(1)(2)I
(4) (A∧ØB)®(R∨S) P
(5) (C∨D)®(R∨S) T(3)(4) I
(6) C∨D P
(7) R∨S T(5)I
2) x(P(x)®Q(y)∧R(x))xP(x)ÞQ(y)∧x(P(x)∧R(x))
证明(1)xP(x) P
(2)P(a) T(1)ES
(3)x(P(x)®Q(y)∧R(x)) P
(4)P(a)®Q(y)∧R(a) T(3)US
(5)Q(y)∧R(a) T(2)(4)I
(6)Q(y) T(5)I
(7)R(a) T(5)I
(8)P(a)∧R(a) T(2)(7)I
(9)x(P(x)∧R(x)) T(8)EG
(10)Q(y)∧x(P(x)∧R(x)) T(6)(9)I
四某班25名学生中14会篮球12会排球6会篮球排球5会篮球网球2会三种球6会网球会外种球求会三种球数（10分）
解：ABC分表示会排球网球篮球学生集合|A|12|B|6|C|14|A∩C|6|B∩C|5|A∩B∩C|2
先求|A∩B|
∵6|（A∪C）∩B||（A∩B）∪（B∩C）||（A∩B）|+|（B∩C）||A∩B∩C||（A∩B）|+52∴|（A∩B）|3
|A∪B∪C|12+6+14653+220会三种球数25205
五已知ABC三集合证明A(B∪C)(AB)∩(AC) （10分）
证明：∵xÎ A（B∪C）Û xÎ A∧xÏ（B∪C）
Û xÎ A∧（xÏB∧xÏC）
Û（xÎ A∧xÏB）∧（xÎ A∧xÏC）
Û xÎ（AB）∧xÎ（AC）
Û xÎ（AB）∩（AC）
∴A（B∪C）（AB）∩（AC）
六已知RSN关系定义：R{
R{12}S[{12}]（10分）
解：R1{
R*S{
S*R{
七设R{
解：r(R){
s(R){
R2 R5{
R3{
R4{
t(R){
八证明整数集I模m余关系R{
证明：1）x∈I（xx）m0xºx(mod m)xRx
2）xy∈IxRyxºy(mod m)（xy）mk∈I（y x）mk∈Iyºx(mod m)yRx
3）xyz∈IxRyyRz（xy）mu∈I（yz）mv∈I（xz）m（xy+yz）mu+v ∈IxRz
九fA→BgB→C双射（gf）1f1g1（10分）
证明：fg双射gf：A→C双射gf逆函数（gf）1：C→A理推f1g1：C→A双射
计算机数学基础离散数学试题
单项选择题(题2分10分)
1列命题公式等值( )
2 谓词公式取真值1充分必条件( )
(A) 意yP(y)取真值1 (B) 存y0P(y0)取真值1
(C) 存某yP(y)取真值1 (D) 存y0P(y0)取真值0
3 设集合A＝{0b}B{1b3}AÈB恒等关系 ( )
(A) {<00><11><33>} (B){<00><11>
(C) {<11>
4 已知集合A＝{abc}二元关系R关系矩阵MR＝R＝( )
(A) {
(C) {
5设V＝{abcd}V构成强连通图边集E＝( )
(A) {
(C) {
二填空题(题3分15分)
6 设命题公式G：P®Ø(Q®P)公式G假真值指派
7 设P：划船G：跑步命题划船跑步符号化
8 设体域D＝{12}谓词公式消量词等值式
9设图D＝
10 连通图G含欧拉回路充分必条件
三化简解答题(题8分32分)
11 回答问题：列集合中相等 说明理
A1＝{ab} A2＝{ba} A3＝{aab} A4＝{abc}
A5＝{} A6＝{}
(2) 设图G＝
13判谓词公式类型
四．计算题(题8分24分)
14求命题公式合取范式
15 设全集E＝(abcdef) A{ad}B{abe}C{bd}求列集合：
(1) (2)
v4 h h v3
v1 h h v2
第16题图
16 已知图D(第16题图)邻接矩阵
A(D)
求v2v4长度2v3v3长度
2通路条数具体写出
17 设代数系统(Z*)中Z整数集二元运算定义
求a逆元
五证明题(第18题10分第19
题9分) 18 设R集合A称关系传递关系试证明：aÎAbÎA(ab)ÎRR等价关系
19 设格(LÙÚ)满足分配律证明
计算机数学基础离散数学试题解答
单项选择题(题2分15分)
1C 2 A 3B 4D 5A
二填空题(题3分15分)
6 1011
7
8 A(1)ÚA(2)Ú(B(1)ÙB(2))
9 7
10 含奇数度结点
三化简解答题(题8分32分)
11集合中元素序重复A1＝A2＝A3 (3分)
(x－a)(x－b)(x－c)0解xabcx2－(a+b)x+ab0解xab (6分)
A1＝A2＝A3＝A6A4＝A5 (8分)
h h
h h
h h
h h
第12题答案图
h
12 (1)
图G嵌入图第12题答案图
图G面图 (4分)
(2) 图G连通½E½＝½V½－1
图G定树 (8分)
13 设I意解释DI体域 解释I该公式前件0
取值1 (2分)
解释I该公式前件11蕴含着11y¢意性必11
总意解释I1 该公式永真式 (8分)
四计算题(题8分24分)
14
15 (1) (4分)
(2)
＝ (8分)
16 A2(D) (4分)
矩阵A2(D)中a242a332知
v2v4长度2通路2条 ： v2v3v4v2v1v4 (6分)
v3v3长度2通路2条 ： v3v4v3v3v2v3 (8分)
17 易知二元运算满足交换律
∵aÎZ a*2a+2－2＝a＝2*a2ÎZ单位元 (3分)
aÎZ a逆元记作a－1
(单位元) ＼ a－14－a (8分)
五证明题(第18题10分第19题9分)
18 已知R称关系传递关系需证明R反关系 (3分)
aÎAbÎA(ab)ÎRR称(ba)ÎR (6分)
R传递(ab)ÎR(ba)ÎRÞ(aa)ÎR元素a意性知R反 (9分)
R等价关系 (10分)
19
＝ (分配律) (3分)
＝ (幂等律) (6分)
＝ (吸收律) (9分)
外种法：pq真时析取起假两命题取项真称排斥(排异)p排斥q表示 例：天晚电影球
例13 列命题符号化
(1) 张晓静爱唱歌爱听音乐
(2) 张晓静江西安徽
解 解题时先原子命题符号化
(1) p：张晓静爱唱歌
q：张晓静爱听音乐
显然(1)中相容pq时真符号化p∨q
(2) r：张晓静江西
s：张晓静安徽
易知(2)中应排斥rs时真符号化r排斥s
1．然语言里特数学中qp必条件许叙述方式例pqpqp仅qqp非q否非p等等种叙述方式表面表达qp必条件联结词均应符号化→述种叙述方式应符号化p→q
课作业
列命题符号化：
命题中出现a定正整数：
(5)a4整a定2整
(6)a4整仅a2整
(7)非a2整a4整
(8)非a2整否a4整
(9)a2整a4整
(10)a4整a2整
解：令r：a4整
s：a2整
仔细分析知(5)(9)五命题均叙述a2整a4整必条件叙述符号化r→s(10)中a4整成a2整必条件应符号化s→r
（3）p∧(((p∨q)∧┐p)→q)
ó p∧(┐((p∨q)∧┐p)∨q)
ó p∧(┐((p∧┐p)∨(q∧┐q))∨q)
ó p∧(┐(0∨(q∧┐p))∨q)
ó p∧(┐q∨p∨q)
óp∧1
ó p
结果说明（3）中公式重言式0001成假赋值矛盾式1011成真赋值
四 等价判定定理
• 定理132 两重言式合取析取然重言式
• 定理133 重言式分量合式公式置换结果重言式
• 定理134 A B两命题公式 A B仅A B重言式
14 蕴含式
定义141 仅A→B重言式称A蕴含B记A > B
A→B种变换式：
逆换式 B→ A
反换式 ┐ A→ ┐ B
逆反式 ┐ B → ┐ A
等价式知：A →B ┐ B → ┐ A
蕴涵式证明两种方法：
① 前件真导件真方法
设公式前件真推导出件真条件式永真式蕴涵式成立
欲证AÞB证A®B永真式A®BA取真B取假时A®B假外余A®B皆真A®B前件A真推出B真A®B永真式AÞB
② 件假导前件假方法
设条件式件假推导出前件假条件式永真式蕴涵式成立
A→B件B取假推出A取假推证：ùBùÞAA→BùÛB→ùAAÞB成立
例题1 推证： ┐ q ∧(p→q) ┐p
想证明A B假定AT证明BT
假定BF证明AF
证法1 假定┐ q ∧(p→q)T┐ qT (p→q)TqF (p→q)T必须pF┐pT
证法2 假定┐pFpT
a) qF(p→q)F ┐ q ∧(p→q)F
b) qT ┐ qF ┐ q ∧(p→q)F
┐ q ∧(p→q) ┐p 成立
求((Ｐ∧┐Ｑ)«(P→R)析取范式合取范式
解(Ｐ∧┐Ｑ)«(P→R)
((Ｐ∧┐Q)→(P→R))∧((P→R)→(Ｐ∧┐Ｑ))
(┐(Ｐ∧┐Ｑ)∨(P→R))∧(┐(P→R)∨(Ｐ∧┐Ｑ))
((┐Ｐ∨Ｑ)∨(┐P∨R))∧(┐(┐P∨R)∨(Ｐ∧┐Ｑ))
(┐Ｐ∨Ｑ∨┐P∨R)∧((P∧┐R)∨(Ｐ∧┐Ｑ))
(┐Ｐ∨Ｑ∨R)∧P∧(┐R∨┐Ｑ)───合取范式
((┐Ｐ∧P)∨(Ｑ∧P)∨(R∧P))∧(┐R∨┐Ｑ)
(Ｑ∧P∧┐R)∨(R∧P∧┐R)∨
(Ｑ∧P∧┐Q)∨(R∧P∧┐Ｑ)
(Ｑ∧P∧┐R)∨(R∧P∧┐Ｑ)───析取范式
• 例两命题变元PQ构成项PÙQPùÙQùPÙQùPùÙQ三命题变元PQR构成项PÙQÙRPÙQùÙRPùÙQÙRPùÙQùÙRùPÙQÙR ùPÙQùÙRùPùÙQÙRùPùÙQùÙR
• 证明n命题变元形成2n项
• 两命题变元PQ构成项PÚQPùÚQùPÚQùPùÚQ三命题变元PQR构成PÚQÚRPÚQùÚRPùÚQÚRPùÚQùÚRùPÚQÚRùPÚQùÚRùPùÚQÚRùPùÚQùÚR够证明n命题变元2n项
• ３析取范式合取范式间关系
ù mi Û Mi
(1)求析取范式
(a)真值表知该公式G恰五解释公式取值真选出已公式取值1行应变元取值：
2 0014011
5 1 0 0 6 1 0 1
8 111
行应极项分：
┐P∧┐Ｑ∧Ｒ┐P∧Ｑ∧ＲP∧┐Ｑ∧┐ＲP∧┐Ｑ∧ＲP∧Ｑ∧Ｒ
极项析取该公式G析取范式
G┐（Ｐ→Ｑ）∨Ｒ
(┐P∧┐Ｑ∧Ｒ) ∨(┐P∧Ｑ∧Ｒ) ∨(P∧┐Ｑ∧┐Ｒ) ∨(P∧┐Ｑ∧Ｒ) ∨(P∧Ｑ∧Ｒ)
(2)求合取范式
(a)真值表知该公式G恰三解释公式取值假选出已公式取值0行应变元值：
10 0 030 1 071 1 0
• 行应极项分：
• P∨Ｑ∨ＲP∨┐Ｑ∨Ｒ┐Ｐ∨┐Ｑ∨Ｒ
• 极项合取该公式G合取范式：
• G┐（Ｐ→Ｑ）∨Ｒ
• ( P∨Ｑ∨Ｒ)∧(P∨┐Ｑ∨Ｒ)∧(┐Ｐ∨┐Ｑ∨Ｒ)
– ３推理定律
• 推理程中推理规需许条推理定律定律前讲命题定律蕴涵式运定理171面出蕴涵式出推理定律：
• (1) PQÞP
• (2) PQÞQ
• (3) PÞP∨Q
• (4) ùPÞP→Q
• (5) QÞP→Q
• (6) ù(P→Q)ÞP
• (7) ù(P→Q)ùÞQ
• (8) P(P→Q)ÞQ
• (9) ùQ(P→Q)ùÞP
• (10) ùP(P∨Q)ÞQ
• (11) (P→Q)(Q→R)ÞP→R
• (12) (P«Q)(Q«R)ÞP«R
• (13) (P→Q)(R→S)(P∧R)ÞQ∧S
• (14) (P→Q)(R→S)∧(P∨R)ÞQ∨S
• 特QS时
• (P→Q)(R→Q)(P∧R)ÞQ
• (P→Q)(R→ Q)(P∨R)ÞQ
• (15)P→QÞ(P∨R)→(Q∨R)
• P→QÞ(P∧R)→(Q∧R)
例1 设前提Г{P∨QP«RQ→S}公式GS∨R证明 ГÞG
证：法1：⑴ P∨Q P
⑵ ┐P→Q T(1)E
⑶ Q→S P
⑷ ┐P→S T⑵⑶I
⑸ ┐S→P T⑷E
⑹ P«R P
⑺ (P→R)Ù(R→P) Ｔ⑹E
⑻ P→R Ｔ⑺I
⑼ ┐S→R T⑸⑻I
⑽ S∨R T⑺E
设Г{P→(Q→S)┐R∨PQ} GR→S证明：ГÞG
证：⑴ R P(附加前提)
⑵ ┐R∨P P
⑶ P T⑴⑵I
⑷ P→(Q→S) P
⑸ Q→S T⑶⑷I
⑹ Q P
⑺ S T⑸⑹I
⑻ R→S CP⑴⑺
果天星期进行离散数学数结构考试果数结构课老师生病考数结构天星期数结构老师生病天进行离散数学考试
• 解：设P：天星期
• Q：进行离散数学考试
• R：进行数结构考试
• S：数结构课老师生病
• P→Q ∨ RS→┐RP∧SÞQ
• 证 ⑴ P∧S Ｐ
• ⑵ S Ｔ⑴I
• ⑶ S→┐R Ｐ
• ⑷ ┐R Ｔ⑵(3)I
• ⑸ P Ｔ⑴I
• ⑹ P→Q R Ｐ
• ⑺ Q R Ｔ⑸⑹I
• ⑻ Q Ｔ⑷⑺I
例6 反证法证明二难推
P∨Q P→R Q→R Þ R
证： ⑴ ┐R Ｐ(附加前提)
⑵ P→R P
⑶ ┐P T⑴⑵I
⑷ Q→R P
⑸ ┐Q T⑵⑷I
⑹ P∨Q Ｐ
⑺ P Ｔ⑸⑹I
⑻ P∧┐P Ｔ⑶⑺I
设公式：P(a)∧(x)P(x)(x)P(x)→P(a)求公式真值中①体域D＝{23}②a指定：2③P(2)指定：1P(3)指定：0
：P(a)∧(x)P(x)
＝P(2)∧(P(2)∧P(3))＝1∧(1∧0)＝0
(x)P(x)→P(a)
＝(P(2)∧P(3))→P(2)＝(1∧0)→1＝1
例213：求公式真值：P(a)→(x)P(x)
(x)P(x)→P(a)
解：（1）解释I：
（a）P(a)取值真时P(x)必真时
P(a)→(x)P(x)真值真
（b）P(a)取值假时P(x)真假时P(a)→(x)P(x)真值真
公式P(a)→(x)P(x)关切结构切赋值恒取T值谓词公式
§ (a) (x)(A(x)∧B)Û(x)A(x)∧B
§ (b) (x)(A(x)∨B)Û(x)A(x)∨B
§ (c) (x)(A(x)→B)Û(x)A(x)→B
§ (d) (x)(B→A(x))ÛB→(x)A(x)
§ (e) (x)(A(x)∧B)Û(x)A(x)∧B
§ (f) (x)(A(x)∨B)Û(x)A(x)∨B
§ (g) (x)(A(x)→B)Û(x)A(x)→B
§ (h) (x)(B→A(x))ÛB→(x)A(x)
1) E22：(x)G(x)＝(y)G(y)
E23：(x)G(x)＝(y)G(y)
1) E24：┐(x)G(x)＝(x)┐G(x)
E25：┐(x)G(x)＝(x)┐G(x)
1) E26：(x)(G(x)∨S)＝(x)G(x)∨S
E27：(x)(G(x)∧S)＝(x)G(x)∧S
E28：(x)(G(x)∨S)＝(x)G(x)∨S
E29：(x)(G(x)∧S)＝(x)G(x)∧S
4) E30：(x)(G(x)∧H(x))＝(x)G(x)∧(x)H(x)
E31：(x)(G(x)∨H(x))＝(x)G(x)∨(x)H(x)
4) E32：(x)G(x)∨(x)H(x)
＝(x)(y)(G(x)∨H(y))
E33：(x)G(x)∧(x)H(x)
＝(x)(y)(G(x)∧H(y))
4) I16：(x)G(x)Þ(x)G(x)
5) I17：(x)G(x)∨(x)H(x)Þ(x)(G(x)∨H(x))
I18：(x)(G(x)∧H(x))Þ(x)G(x)∧(x)H(x)
4) I19：(x)(G(x)→H(x))Þ(x)G(x)→(x)H(x)
I20：(x)(G(x)→H(x))Þ(x)G(x)→(x)H(x)
9) E34：(x)(y)G(xy)＝(y)(x)G(xy)
E35：(x)(y)G(xy)＝(y)(x)G(xy)
9) I21：(x)(y)G(xy)Þ(y)(x)G(xy)
I22：(x)(y)G(xy)Þ(y)(x)G(xy)
I23：(x)(y)G(xy)Þ(x)(y)G(xy)
I24：(y)(x)G(xy)Þ(x)(y)G(xy)
I25：(x)(y)G(xy)Þ(y)(x)G(xy)
I26：(x)(y)G(xy)Þ(x)(y)G(xy)
I27：(x)(y)G(xy)Þ(x)(y)G(xy)
I28：(y)(x)G(xy)Þ(y)(x)G(xy)
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档