离散数学命题逻辑课后总结.docx
- 文档编号:4978952
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:17
- 大小:42.42KB
离散数学命题逻辑课后总结.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表示:
植物会死亡。
PQ:
如果缺少水分,植物就会死亡。
PQ:
也称之为蕴涵式,读成“P蕴涵Q”,“如果P则Q”。
也说成P是PQ的前件,Q是PQ的后件。
还可以说P是Q的充分条件,Q是P的必要条件。
以下是关于蕴含式的一个例子
P:
天气好。
Q:
我去公园。
1.如果天气好,我就去公园。
2.只要天气好,我就去公园。
3.天气好,我就去公园。
4.仅当天气好,我才去公园。
5.只有天气好,我才去公园。
6.我去公园,仅当天气好。
命题1.、2.、3.写成:
PQ
命题4.、5.、6.写成:
QP
例1-2.6:
P:
△ABC是等边三角形。
Q:
△ABC是等角三角形。
PQ:
△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为()。
已知PQ为F,则P为(),Q为()。
已知P为F,则PQ为()。
已知Q为T,则PQ为()。
已知PQ为F,则P为(),Q为()。
已知P为T,PQ为T,则Q为()。
已知Q为T,PQ为T,则P为()。
已知PQ为T,P为T,则Q为().
已知PQ为F,P为T,则Q为().
PP的真值为().
PP的真值为()。
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:
我犯人。
该命题可写成:
(PQ)∧(PQ)或写成:
PQ
例5.若天不下雨,我就上街;否则在家。
P:
天下雨。
Q:
我上街。
R:
我在家。
该命题可写成:
(PQ)∧(PR).
注意:
中间的联结词一定是“∧”,而不是“∨”,也不是“⊽”。
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∧QPI2.P∧QQ
I3.PP∨QI4.QP∨Q
I5.PPQI6.QPQ
I7.(PQ)PI8.(PQ)Q
I9.P,QP∧QI10.P∧(P∨Q)Q
I11.P∧(PQ)QI12.Q∧(PQ)P
I13.(PQ)∧(QR)PR
I14.(P∨Q)∧(PR)∧(QR)R
I15.AB(A∨C)(B∨C)
I16.AB(A∧C)(B∧C)
1—5节
重要的等价公式(课件中出现多次,可不用记忆)
⑴对合律PP⑵幂等律P∨PPP∧PP
⑶结合律P∨(Q∨R)(P∨Q)∨RP∧(Q∧R)(P∧Q)∧R
⑷交换律P∨QQ∨PP∧QQ∧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∨FPP∧TP⑼零律P∨TTP∧FF
⑽互补律P∨PTP∧PF⑾PQP∨Q
⑿PQQP⒀PQ(PQ)∧(QP)
⒁PQ(P∨Q)∧(P∨Q)⒂PQ(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:
PQP∨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:
PQP∨Q
1-6.范式(Paradigm)
例1.求PQ和PQ的主析取范式
方法一:
真值表
PQm0∨m1∨m3
(P∧Q)∨(P∧Q)∨(P∧Q)
PQm0∨m3
(P∧Q)∨(P∧Q)
方法Ⅱ:
用公式的等价变换
⑴先写出给定公式的析取范式A1∨A2∨...∨An。
⑵为使每个Ai都变成小项,对缺少变元的Ai
补全变元,比如缺变元R,就用∧联结永真式(R∨R)形式补R。
⑶用分配律等公式加以整理。
PQP∨Q
(P∧(Q∨Q))∨((P∨P)∧Q)
(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)
(P∧Q)∨(P∧Q)∨(P∧Q)
思考题:
永真式的主析取范式是什么样?
(包含所有小项)
例2.求PQ和PQ的主合取范式
PQM2P∨Q
PQM1∧M2
(P∨Q)∧(P∨Q)
方法Ⅱ:
用公式的等价变换
⑴先写出给定公式的合取范式A1∧A2∧...∧An。
⑵为使每个Ai变成大项,对缺少变元的析取式Ai补全变元,比如缺变元R,就用∨联
结永假式(R∧R)形式补R。
⑶用分配律等公式加以整理。
例如,求(PQ)R的主合取范式
(PQ)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,PR
证明
序号前提或结论所用规则从哪几步得到所用公式
(1)PP
(2)PQP
(3)QT
(1)
(2)I11
(4)Q→RP
(5)RT(3)(4)I11
例题2求证
(P∧Q)∧(Q∨R)∧RP
(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∨QQ
公式E8为:
(P∧Q)P∨Q
例题3用命题逻辑推理方法证明下面推理的有效性:
如果我学习,那么我数学不会不及格。
如果我不热衷于玩朴克,那么我将学习。
但是我数学不及格。
因此,我热衷于玩朴克。
解:
设P:
我学习。
Q:
我数学及格。
R:
我热衷于玩朴克。
于是符号化为:
P→Q,R→P,QR
P→Q,R→P,QR
(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→QP
公式E1为:
RR
例题4求证P→(Q→S),R∨P,QR→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,QR→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.熟练掌握三种推理方法。
以上自己是不是都已经熟练掌握了呢?
?
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 命题逻辑 课后 总结