离散数学命题逻辑课后总结.docx
- 文档编号:13959992
- 上传时间:2023-06-19
- 格式:DOCX
- 页数:17
- 大小:72.58KB
离散数学命题逻辑课后总结.docx
《离散数学命题逻辑课后总结.docx》由会员分享,可在线阅读,更多相关《离散数学命题逻辑课后总结.docx(17页珍藏版)》请在冰点文库上搜索。
离散数学命题逻辑课后总结
离散数学(课件上习题)
第一章
例1-1.1判定下面这些句子哪些是命题。
⑴2是个素数。
⑵雪是黑色的。
⑶2013年人类将到达火星。
⑷如果a>b且b>c,则a>c。
(其中a,b,c都是
确定的实数)
⑸x+y<5
⑹请打开书!
⑺您去吗?
⑴⑵⑶⑷是命题
例1-2.1P:
2是素数。
ØP:
2不是素数。
例1-2.2P:
小王能唱歌。
Q:
小王能跳舞。
P∧Q:
小王能歌善舞。
例1-2.3.灯泡或者线路有故障。
(析取“∨”)
例1-2.4.第一节课上数学或者上英语。
(异或、排斥或。
即“⊽”)
注意:
P⊽Q与(P∧ØQ)∨(Q∧ØP)是一样的。
归纳自然语言中的联结词,定义了六个逻辑联结词,分别是:
(1)否定“”
(2)合取“∧”(3)析取“∨”(4)异或“⊽”(5)蕴涵“”(6)等价“”
例1-2.5:
P表示:
缺少水分。
Q表示:
植物会死亡。
P®Q:
如果缺少水分,植物就会死亡。
P®Q:
也称之为蕴涵式,读成“P蕴涵Q”,“如果P则Q”。
也说成P是P®Q的前件,Q是P®Q的后件。
还可以说P是Q的充分条件,Q是P的必要条件。
以下是关于蕴含式的一个例子
P:
天气好。
Q:
我去公园。
1.如果天气好,我就去公园。
2.只要天气好,我就去公园。
3.天气好,我就去公园。
4.仅当天气好,我才去公园。
5.只有天气好,我才去公园。
6.我去公园,仅当天气好。
命题1.、2.、3.写成:
P®Q
命题4.、5.、6.写成:
Q®P
例1-2.6:
P:
△ABC是等边三角形。
Q:
△ABC是等角三角形。
P«Q:
△ABC是等边三角形当且仅当它是等角三角形。
课后练习:
填空
已知P∧Q为T,则P为(),Q为()。
已知P∨Q为F,则P为(),Q为()。
已知P为F,则P∧Q为()。
已知P为T,则P∨Q为()。
已知P∨Q为T,且P为F,则Q为()。
已知P®Q为F,则P为(),Q为()。
已知P为F,则P®Q为()。
已知Q为T,则P®Q为()。
已知ØP®ØQ为F,则P为(),Q为()。
已知P为T,P®Q为T,则Q为()。
已知ØQ为T,P®Q为T,则P为()。
已知P«Q为T,P为T,则Q为().
已知P«Q为F,P为T,则Q为().
P«P的真值为().
P®P的真值为()。
1—3节
例1.说离散数学无用且枯燥无味是不对的。
P:
离散数学是有用的。
Q:
离散数学是枯燥无味的。
该命题可写成:
Ø(ØP∧Q)
例2.如果小张与小王都不去,则小李去。
P:
小张去。
Q:
小王去。
R:
小李去。
该命题可写成:
(ØP∧ØQ)®R
如果小张与小王不都去,则小李去。
该命题可写成:
Ø(P∧Q)®R
也可以写成:
(ØP∨ØQ)®R
例3.仅当天不下雨且我有时间,才上街。
P:
天下雨。
Q:
我有时间。
R:
我上街。
分析:
由于“仅当”是表示“必要条件”的,既“天不下雨且我有时间”,是“我上街”的必要条件。
所以
该命题可写成:
R®(ØP∧Q)
例4.人不犯我,我不犯人;人若犯我,我必犯人。
P:
人犯我。
Q:
我犯人。
该命题可写成:
(ØP®ØQ)∧(P®Q)或写成:
P«Q
例5.若天不下雨,我就上街;否则在家。
P:
天下雨。
Q:
我上街。
R:
我在家。
该命题可写成:
(ØP®Q)∧(P®R).
注意:
中间的联结词一定是“∧”,而不是“∨”,也不是“⊽”。
1—4节
重言(永真)蕴涵式证明方法
方法1.列真值表。
方法2.假设前件为真,推出后件也为真。
例如求证:
((A∧B)®C)∧ØD∧(ØC∨D)ÞØA∨ØB
证明:
设前件((A∧B)®C)∧ØD∧(ØC∨D)为真则((A∧B)®C)、ØD、(ØC∨D)均真,
ØD为T,则D为F
ØC∨D为T得C为F
((A∧B)®C)为T得A∧B为F
如果A为F,则ØA为T,所以ØA∨ØB为T。
如果B为F,则ØB为T,所以ØA∨ØB为T。
\((A∧B)®C)∧ØD∧(ØC∨D)ÞØA∨ØB
方法3.假设后件为假,推出前件也为假。
例如求证:
((A∧B)®C)∧ØD∧(ØC∨D)ÞØA∨ØB
证明:
假设后件ØA∨ØB为F,则A与B均为T。
1.如C为F,则(A∧B)®C为F,所以前件((A∧B)®C)∧ØD∧(ØC∨D)为F。
2.如C为T,则
⑴若D为T,则ØD为F,所以前件((A∧B)®C)∧ØD∧(ØC∨D)为假;
⑵若D为F,则ØC∨D为F,所以前件((A∧B)®C)∧ØD∧(ØC∨D)为假。
\((A∧B)®C)∧ØD∧(ØC∨D)ÞØA∨ØB
重要的重言蕴涵式(如教材第43页所示)(课件中出现过多次,可不用记忆)
I1.P∧QÞPI2.P∧QÞQ
I3.PÞP∨QI4.QÞP∨Q
I5.ØPÞP®QI6.QÞP®Q
I7.Ø(P®Q)ÞPI8.Ø(P®Q)ÞØQ
I9.P,QÞP∧QI10.ØP∧(P∨Q)ÞQ
I11.P∧(P®Q)ÞQI12.ØQ∧(P®Q)ÞØP
I13.(P®Q)∧(Q®R)ÞP®R
I14.(P∨Q)∧(P®R)∧(Q®R)ÞR
I15.A®BÞ(A∨C)®(B∨C)
I16.A®BÞ(A∧C)®(B∧C)
1—5节
重要的等价公式(课件中出现多次,可不用记忆)
⑴对合律ØØPÛP⑵幂等律P∨PÛPP∧PÛP
⑶结合律P∨(Q∨R)Û(P∨Q)∨RP∧(Q∧R)Û(P∧Q)∧R
⑷交换律P∨QÛQ∨PP∧QÛQ∧P
⑸分配律P∨(Q∧R)Û(P∨Q)∧(P∨R)P∧(Q∨R)Û(P∧Q)∨(P∧R)
⑹吸收律P∨(P∧Q)ÛPP∧(P∨Q)ÛP
⑺底-摩根定律Ø(P∨Q)ÛØP∧ØQØ(P∧Q)ÛØP∨ØQ
⑻同一律P∨FÛPP∧TÛP⑼零律P∨TÛTP∧FÛF
⑽互补律P∨ØPÛTP∧ØPÛF⑾P®QÛØP∨Q
⑿P®QÛØQ®ØP⒀P«QÛ(P®Q)∧(Q®P)
⒁P«QÛ(ØP∨Q)∧(P∨ØQ)⒂P«QÛ(P∧Q)∨(ØP∧ØQ)
例题1.求证吸收律P∧(P∨Q)ÛP
证明:
P∧(P∨Q)
Û(P∨F)∧(P∨Q)(同一律)
ÛP∨(F∧Q)(分配律)
ÛP∨F(零律)
ÛP(同一律)
例题2.求证(ØP∨Q)→(P∧Q)ÛP
证明(ØP∨Q)→(P∧Q)
ÛØ(ØP∨Q)∨(P∧Q)(公式E16)
Û(ØØP∧ØQ)∨(P∧Q)(摩根定律)
Û(P∧ØQ)∨(P∧Q)(对合律)
ÛP∧(ØQ∨Q)(分配律)
ÛP∧T(互补律)
ÛP(同一律)
公式E16:
P®QÛØP∨Q
例题3.化简Ø(P∧Q)→(ØP∨(ØP∨Q))
解原公式ÛØØ(P∧Q)∨((ØP∨ØP)∨Q)(E16,结合)
Û(P∧Q)∨(ØP∨Q)(对合律,幂等律)
Û(P∧Q)∨(Q∨ØP)(交换律)
Û((P∧Q)∨Q)∨ØP(结合律)
ÛQ∨ØP(吸收律)
公式E16:
P®QÛØP∨Q
1-6.范式(Paradigm)
例1.求P®Q和P«Q的主析取范式
方法一:
真值表
P®QÛm0∨m1∨m3
Û(ØP∧ØQ)∨(ØP∧Q)∨(P∧Q)
P«QÛm0∨m3
Û(ØP∧ØQ)∨(P∧Q)
方法Ⅱ:
用公式的等价变换
⑴先写出给定公式的析取范式A1∨A2∨...∨An。
⑵为使每个Ai都变成小项,对缺少变元的Ai
补全变元,比如缺变元R,就用∧联结永真式(R∨ØR)形式补R。
⑶用分配律等公式加以整理。
P®QÛØP∨Q
Û(ØP∧(Q∨ØQ))∨((P∨ØP)∧Q)
Û(ØP∧Q)∨(ØP∧ØQ)∨(P∧Q)∨(ØP∧Q)
Û(ØP∧Q)∨(ØP∧ØQ)∨(P∧Q)
思考题:
永真式的主析取范式是什么样?
(包含所有小项)
例2.求P®Q和P«Q的主合取范式
P®QÛM2ÛØP∨Q
P«QÛM1∧M2
Û(P∨ØQ)∧(ØP∨Q)
方法Ⅱ:
用公式的等价变换
⑴先写出给定公式的合取范式A1∧A2∧...∧An。
⑵为使每个Ai变成大项,对缺少变元的析取式Ai补全变元,比如缺变元R,就用∨联
结永假式(R∧ØR)形式补R。
⑶用分配律等公式加以整理。
例如,求(P®Q)®R的主合取范式
(P®Q)®R
ÛØ(ØP∨Q)∨R
Û(P∧ØQ)∨R
Û(P∨R)∧(ØQ∨R)
Û(P∨(Q∧ØQ)∨R)∧((P∧ØP)∨ØQ∨R)
Û(P∨Q∨R)∧(P∨ØQ∨R)∧
(P∨ØQ∨R)∧(ØP∨ØQ∨R)
Û(P∨Q∨R)∧(P∨ØQ∨R)∧(ØP∨ØQ∨R)
例3.安排课表,教语言课的教师希望将课程安排在第一或第三节;教数学课的教师
希望将课程安排在第二或第三节;教原理课的教师希望将课程安排在第一或第二节。
如何安排课表,使得三位教师都满意。
令L1、L2、L3分别表示语言课排在第一、第二、第三节。
M1、M2、M3分别表示数学课排在第一、第二、第三节。
P1、P2、P3分别表示原理课排在第一、第二、第三节。
三位教师都满意的条件是:
(L1∨L3)∧(M2∨M3)∧(P1∨P2)为真。
将上式写成析取范式(用分配律)得:
((L1∧M2)∨(L1∧M3)∨(L3∧M2)∨
(L3∧M3))∧(P1∨P2)
Û(L1∧M2∧P1)∨(L1∧M3∧P1)∨
(L3∧M2∧P1)∨(L3∧M3∧P1)∨
(L1∧M2∧P2)∨(L1∧M3∧P2)∨
(L3∧M2∧P2)∨(L3∧M3∧P2)
可以取(L3∧M2∧P1)、(L1∧M3∧P2)为T,得到两种排法。
课堂练习:
1.已知A(P,Q,R)的真值表如图:
求它的主析取和主合取范式。
2.已知A(P,Q,R)的主析取范式中
含有下面小项m1,m3,m5,m7
求它的主合取范式.
3.已知A(P1,P2,…,Pn)的主合取范式中
含有k个大项,问它的主析取范式
中有多少个小项?
课堂练习答案
1.A(P,Q,R)的主析取范式:
A(P,Q,R)Ûm0∨m3∨m4∨m6∨m7
Û(ØP∧ØQ∧ØR)∨(ØP∧Q∧R)∨
(P∧ØQ∧ØR)∨(P∧Q∧ØR)∨(P∧Q∧R)
A(P,Q,R)的主合取范式:
A(P,Q,R)ÛM1∧M2∧M5Û(P∨Q∨ØR)∧(P∨ØQ∨R)∧(ØP∨Q∨ØR)
2.A(P,Q,R)ÛM0∧M2∧M4∧M6
Û(P∨Q∨R)∧(P∨ØQ∨R)∧(ØP∨Q∨R)∧(ØP∨ØQ∨R)
3.A(P1,P2,…,Pn)的主析取范式中含有2n-k个小项.
1-7.命题逻辑推理
例题1求证P→Q,Q→R,PÞR
证明
序号前提或结论所用规则从哪几步得到所用公式
(1)PP
(2)P®QP
(3)QT
(1)
(2)I11
(4)Q→RP
(5)RT(3)(4)I11
例题2求证
Ø(P∧Q)∧(Q∨R)∧ØRÞØP
(1)Q∨RP
(2)ØRP
(3)QT
(1)
(2)I10
(4)Ø(P∧Q)P
(5)ØP∨ØQT(4)E8
(6)ØPT(3)(5)I10
注公式I10为:
ØP,P∨QÞQ
公式E8为:
Ø(P∧Q)ÛØP∨ØQ
例题3用命题逻辑推理方法证明下面推理的有效性:
如果我学习,那么我数学不会不及格。
如果我不热衷于玩朴克,那么我将学习。
但是我数学不及格。
因此,我热衷于玩朴克。
解:
设P:
我学习。
Q:
我数学及格。
R:
我热衷于玩朴克。
于是符号化为:
P→Q,ØR→P,ØQÞR
P→Q,ØR→P,ØQÞR
(1)P→QP
(2)ØQP
(3)ØPT
(1)
(2)I12
(4)ØR→PP
(5)ØØRT(3)(4)I12
(6)RT(5)E1
注:
公式I12为:
ØQ,P→QÞØP
公式E1为:
ØØRÛR
例题4求证P→(Q→S),ØR∨P,QÞR→S
证明
(1)P→(Q→S)P
(2)ØP∨(ØQ∨S)T
(1)E16
(3)ØP∨(S∨ØQ)T
(2)E3
(4)(ØP∨S)∨ØQT(3)E5
(5)QP
(6)ØP∨ST(4)(5)I10
(7)P→ST(6)E16
(8)ØR∨PP
(9)R→PT(8)E16
(10)R→ST(7)(9)I13
例题5用条件论证,证明例题4
P→(Q→S),ØR∨P,QÞR→S
证明
(1)RP(附加前提)
(2)ØR∨PP
(3)PT
(1)
(2)I10
(4)P→(Q→S)P
(5)Q→ST(3)(4)I11
(6)QP
(7)ST(5)(6)I11
(8)R→SCP
例题6用命题逻辑推理方法证明下面推理的有效性:
如果体育馆有球赛,青年大街交通就拥挤。
在这种情况下,如果小王不提前出发,就会迟到。
因此,小王没有提前出发也未迟到,则体育馆没有球赛。
证明先将命题符号化。
设P:
体育馆有球赛。
Q:
青年大街交通拥挤。
R:
小王提前出发。
S:
小王迟到。
P→Q,(Q∧ØR)→SÞ(ØR∧ØS)→ØP
P→Q,(Q∧ØR)→SÞ(ØR∧ØS)→ØP
证明
(1)ØR∧ØSP(附加前提)
(2)ØRT
(1)I1
(3)ØST
(1)I2
(4)(Q∧ØR)→SP
(5)Ø(Q∧ØR)T(3)(4)I12
(6)ØQ∨RT(5)E8
(7)ØQT
(2)(6)I10
(8)P→QP
(9)ØPT(7)(8)I12
(10)(ØR∧ØS)→ØPCP
例7P→Q,(ØQ∨R)∧ØR,Ø(ØP∧S)ÞØS
证明
(1)ØØSP(假设前提)
(2)ST
(1)E1
(3)Ø(ØP∧S)P
(4)P∨ØST(3)E8
(5)PT
(2)(4)I10
(6)P→QP
(7)QT(5)(6)I11
(8)(ØQ∨R)∧ØRP
(9)ØQ∨RT(8)I1
(10)ØRT(8)I2
(11)RT(7)(9)I10
(12)R∧ØRT(10)(11)I9
第一章习题课
1.有工具箱A、B、C、D,各个箱内装的工具如下表所示。
试问如何携带数量最少工具箱,而所包含的工具种类齐全。
工具箱
改锥
扳手
钳子
锤子
A
有
有
B
有
有
有
C
有
有
D
有
有
解:
设A、B、C、D分别表示带A、B、C、D箱。
则总的条件为:
(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D)为真。
改锥扳手钳子锤子
将(A∨C)∧(A∨B∨D)∧(B∨C)∧(B∨D)写成析取范式,上式Û((A∨C)∧(B∨C))∧((A∨(B∨D))∧(B∨D))(交换)
Û((A∧B)∨C))∧(B∨D)
(分配(提取C)、吸收)
Û(A∧B∧B)∨(C∧B)∨(A∧B∧D)∨(C∧D)(分配)
Û(A∧B)∨(C∧B)∨(A∧B∧D)∨(C∧D)
分别可以取(A∧B)、(C∧B)、(C∧D)为真。
于是可以得到三种携带方法:
带A和B箱,带B和C箱,带C和D箱。
请根据下面事实,找出凶手:
1.清洁工或者秘书谋害了经理。
2.如果清洁工谋害了经理,则谋害不会发生在午夜前。
3.如果秘书的证词是正确的,则谋害发生在午夜前。
4.如果秘书的证词不正确,则午夜时屋里灯光未灭。
5.如果清洁工富裕,则他不会谋害经理。
6.经理有钱且清洁工不富裕。
7.午夜时屋里灯灭了。
令A:
清洁工谋害了经理。
B:
秘书谋害了经理。
C:
谋害发生在午夜前。
D:
秘书的证词是正确的.
E:
午夜时屋里灯光灭了。
H:
清洁工富裕.
G:
经理有钱.
命题符号为:
A∨B,AC,DC,DE,HA,G∧H,E⇒?
A∨B,AC,BC,DCDE,HA,G∧H,E?
⑴EP
⑵DEP
⑶DT⑴⑵I
⑷DT⑶E
⑸DCP
⑹CT⑷⑸I
⑺ACP
⑻AT⑹⑺I
⑼A∨BP
⑽BT⑻⑼I
结果是秘书谋害了经理。
第一章小结
本章的重点内容、及要求:
1.逻辑联结词,要熟练掌握联结词的真值表定义以及它们在自然语言中的含义。
其中特别要注意“∨”和“→”的用法。
2.会命题符号化。
3.掌握永真式的证明方法:
(1).真值表。
(2).等价变换,化简成T。
(3).主析取范式。
4.掌握永真蕴含式的证明方法,熟练记忆并会应用
43页中表1-8.3中的永真蕴含式。
5.掌握等价公式的证明方法,熟练记忆并会应用
43页表1-8.4中的等价公式。
6.熟练掌握范式的写法及其应用。
7.熟练掌握三种推理方法。
以上自己是不是都已经熟练掌握了呢?
?
【最新资料Word版可自由编辑!
!
】
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 命题逻辑 课后 总结
![提示](https://static.bingdoc.com/images/bang_tan.gif)