版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领
文档简介
第一章命题演算基础1.1命题和联结词1.2真假性1.3范式及其应用
1.3.1范式
1.3.2主范式1.3.3范式应用1/52合取式、析取式定义1命题变元、或者命题变元否定、或由它们利用合取词组成合式公式称为合取式。定义2命题变元、或者命题变元否定、或由它们利用析取词组成合式公式称为析取式。例显然，P，
P，P
Q，
P
Q
R均为合取式；
P，
P，P
Q，
P
Q
R均为析取式。2/52(一)解释与合取式、析取式之间关系
定理1
任给一个成真解释有且仅有一个合取式与之对应；任给一个成假解释有且仅有一个析取式与之对应。反之亦然。例成真解释(P，Q，R)=(T,F,T)
成假解释(P，Q，R)=(F,F,T)合取式P
Q
R析取式P
Q
R3/52析取范式、合取范式定义3形如A1
A2
…
An公式称为析取范式，
其中Ai(i=1,2…,n)为合取式。定义4形如A1
A2
…
An公式称为合取范式，其中Ai(i=1,2…,n)为析取式。例如：P，
P，P
Q，P
Q
，(
P
Q)
(S
R)
均为析取范式。如：P，
P，P
Q，P
Q
，
(
P
Q)
(S
R)均为合取范式。4/52例:考查公式
=PQ析取范式有两个成真解释：
(T,T),(F,F),分别对应于两个合取式为P∧Q,P∧Q于是，有
=(P∧Q)∨(P∧Q)PQP
QTTTTFFFTFFFT5/52例:考查公式
=PQ合取范式成假解释(T,F),(F,T),对应析取式为
P∨Q,P∨Q于是，有：
=(P∨Q)∧(P∨Q)PQP
QTTTTFFFTFFFT6/52定理2任何命题演算公式均能够化为合取范式，也能够化为析取范式。证实：
(1)设公式
为永真公式 因为任何一个永真公式均与公式P
P逻辑等价，而P
P既是析取范式又是合取范式，所以公式既可表示为析取范式又可表示为合取范式。
(2)设公式为永假公式 因为任何一个永假公式均与公式P
P逻辑等价，而P
P既是析取范式又是合取范式，所以公式既可表示为析取范式又可表示为合取范式。7/52定理2证实(续)(3)设公式
既非永真又非永假 设公式
成真解释为
1，
2，……，
n，成假解释为
1，
2，……，
t。 依据解释和范式关系知： 对应于成真解释
1，
2，……，
n合取式为
1，
2，……，
n
对应于成假解释
1，
2，……，
t析取式为
1，
2，……，
t
而公式
1
2
……
n成真解释为
1，
2，……，
n； 公式
1
2
……
t成假解释为
1，
2，……，
t。 依据两个公式逻辑等价定义知
=
1
2
……
n=
1
2
……
t
故公式
既可表示为析取范式又可表示为合取范式。8/52(二)析取范式和合取范式求解方法
等价变换法解释法9/52等价变换法(1)利用前面介绍等价公式消去公式中联结词“
”和“
”；(2)重复使用等值公式，把否定词内移到命题变元上，等值公式以下：
(P
Q)=
P
Q
(P
Q)=
P
Q，
P=P(3)重复使用分配律将公式化为合取式析取或析取式合取，等值公式以下：
P
(Q
R)=(P
Q)
(P
R)
P
(Q
R)=(P
Q)
(P
R)10/52解释法(1)求出公式全部成真(假)解释；(2)写出全部成真(假)解释对应有合(析)取式；(3)把全部合(析)取式用析(合)取词联结起来就组成析(合)取范式。11/52例(p11)
求公式范式
((P
Q)
(R
P))
((R
Q)
P)解法一：求析取范式原式=((
P
Q)(
R
P))
((
R
Q)
P)=(
(
P
Q)
(
R
P))((
(
R
Q)
P)=(P
Q)
(R
P)((R
Q)
P)=(P
Q)(R
P)(P
R)
(P
Q)=(P
Q)
(P
R)
(
P
R)12/52解法一：再求合取范式原式=(P
Q)
(P
R)
(
P
R)
(析取范式)
=(P(Q
R))
(
P
R)=(P
(
P
R))((Q
R)
(P
R))(分配率)
=((P
P)(P
R))
(
P
Q
R)(Q
R
R)=(P
R)
(
P
Q
R)例(p11)
求公式范式
((P
Q)
(R
P))
((R
Q)
P)13/52例(p11)
求公式范式
((P
Q)
(R
P))
((R
Q)
P)另解:
由析取范式，有
=(P∧
Q)∨(P∧
R)∨(
P∧R)
于是，
=(
P∨Q)∧(P∨R)∧(P∨
R) =(P∧Q∧R)∨(
P∧
R)
所以
=(P∨Q∨R)∧(P∨R)14/52解法二：先求公式全部成真解释和成假解释(见下一张)
成真解释为：(P,Q,R)=(T,F,),(F,,T),(T,,F)
成假解释为：(P,Q,R)=(T,T,T),(F,,F)由成真解释可分别求出对应合取式：
P
Q，
P
R，P
R
公式析取范式即为上面合取式析取：
(P
Q)
(P
R)
(
P
R)由成假解释可分别求出对应析取式：
P
Q
R，P
R
公式合取范式为上面析取式合取：
(
P
Q
R)
(P
R)例(p11)
求公式范式
((P
Q)
(R
P))
((R
Q)
P)15/52解：P=T时,原式=((T
Q)∧(RT))∨((R
Q)T)
=(Q∧T)∨
((R
Q)) =
Q∨(R
Q)
=
Q∨(R∨Q)=Q∨
RP=F时,原式=((F
Q)∧(RF))∨((R
Q)F)
=(T∧R)∨T=(R)=R
所以有:
成真解释为：(P,Q,R)=(T,F,),(F,,T),(T,,F)
成假解释为：(P,Q,R)=(T,T,T),(F,,F)6？例(补)求公式成真(假)解释
((P
Q)
(R
P))
((R
Q)
P)16/52例(补)求公式成真(假)解释
((P
Q)
(R
P))
((R
Q)
P)P
QPQRPRPP
QRQ
QPP(P
Q)P(P
Q)
(R
P)((P
Q)
(R
P))
((P
Q)P)
17/52另解：所以有:成真解释为：(P,Q,R)=(T,F,),(F,,T),(T,,F)
成假解释为：(P,Q,R)=(T,T,T),(F,,F)(P,Q,R)A=P
QB=R
PC=(AB)D=R
QE=DPCE(T,T,T)TTFFTF(T,T,F)TTFTFT(T,F,T)FTTTFT(T,F,F)FTTTFT(F,T,T)TFTFTT(F,T,F)TTFTTF(F,F,T)TFTTTT(F,F,F)TTFTTF例(补)求公式成真(假)解释
((P
Q)
(R
P))
((R
Q)
P)18/52范式不唯一性例
求(P
Q)
P析取范式和合取范式．解:(P
Q)
P=((
P∨Q))∨P
=(P∧
Q)∨P
析取范式
=
P析取范式
(P
Q)
P=(P∧
Q)∨P
析取范式
=P∧(
Q∨P)合取范式
=P合取范式19/52第一章命题演算基础1.1命题和联结词1.2真假性1.3范式及其应用
1.3.1范式
1.3.2主范式1.3.3范式应用20/52(一)主析取范式定义1对于n个命题变元P1，P2，……，Pn，公式Q1
Q2
……
Qn
称为极小项，其中Qi=Pi或Pi(i=1，……，n)。例由两个命题变元P，Q组成极小项有四个，它们分别为：
P
Q
PQ
PQ
PQ21/52三个命题变元P、Q和R可结构8个极小项把命题变元否定形式看成0，必定形式看成1，则每个极小项对应一个二进制数，也对应一个十进制数。它们对应以下：
P
Q
R与000或0对应，简记为m0
P
Q
R与001或1对应，简记为m1
P
Q
R与010或2对应，简记为m2
P
Q
R与011或3对应，简记为m3
P
Q
R与100或4对应，简记为m4
P
Q
R与101或5对应，简记为m5
P
Q
R与110或6对应，简记为m6
P
Q
R与111或7对应，简记为m722/52n个命题变元组成极小项有2n个公式每一个完全成真解释对应一个极小项公式全部完全成真解释对应极小项析取例:考查公式
=PQ有两个成真解释：
(T,T),(F,F)
分别对应于两个极小项(合取式)为P∧Q,P∧Q于是，有
=(P∧Q)∨(P∧Q)23/52主析取范式
定义2仅有极小项组成析取范式称为主析取范式。定理1任何一个合式公式，都有惟一一个主析取范式与该合式公式等价。主析取范式就是公式全部完全成真解释对应极小项析取。
24/52求主析取范式两种方法(1)解释法:
依据公式全部完全成真解释，求出与这些成真解释对应合取式，全部合取式析取就为公式主析取范式。(2)等价变换法:
将析取范式中每一个合取式用A
A填满命题变元，然后用等价公式进行变换，消去相同部分，即得公式主析取范式。25/52例(p12)求(P
R)
(P
(Q
R))
主析取范式。解法1：等价变换法原式=(
P
R)((
P
Q
R)(P
(Q
R)))
(去蕴涵词、等价词)
=(P
R)((
P
Q
R)(P
(
Q
R)))（否定深入）
=(
P
R)((
P
Q
R)((P
Q)
(P
R)))（分配率）
=(P
Q
R)(P
Q
R)(P
R)
(分解后，六项剩三项）=(P
Q
R)(P
Q
R)((P
R)(Q
Q))
26/52例(p12)求(P
R)
(P
(Q
R))
主析取范式。解法1：等价变换法（续上页）原式=(P
Q
R)(P
Q
R)((P
R)(Q
Q))
=(P
Q
R)(P
Q
R)((P
Q
R)
(P
Q
R))
=(P
Q
R)(P
Q
R)((P
Q
R)
=010101111
=m2m5m7=去等价词两个公式需要灵活利用，才能将原式快速转化为析取范式！27/52解法2：解释法公式全部成真解释为：(P，Q，R)=(F，T，F),(T，F，T),(T，T，T)对应于成真解释极小项为：
P
Q
R,P
Q
R,
P
Q
R
故主析取范式为：
(P
Q
R)(P
Q
R)(P
Q
R)例(p12)求(P
R)
(P
(Q
R))
主析取范式。28/52例(p12)
补求(P
R)
(P
(Q
R))解释解:P=T时,原式=(T
R)
(T
(Q
R))
=R
(Q
R))
=R
(
Q
R))
=(R
Q)
R=
RP=F时,原式=(F
R)
(F
(Q
R)
=T
(Q
R)
=Q
R
于是,全部成真解释为：
(T，*，T)、(F，T，F)全部成假解释为：
(T，*，F)、(F，F，*)、(F，T，T)29/52(二)主合取范式定义3对于n个命变元P1，P2，……，Pn，公式
Q1
Q2……
Qn
称为极大项，其中Qi=Pi或
Pi(i=1，…，n)。例由两个命题变元P，Q组成极大项有四个，它们分别为：
PQ
PQ
PQ
PQ30/52三个命题变元P、Q和R可结构8个极大项
把命题变元否定形式看成1，必定形式看成0，则每个极大项对应一个二进制数，也对应一个十进制数。它们对应以下：
P
Q
R与000或0对应，简记为M0
P
Q
R与001或1对应，简记为M1
P
Q
R与010或2对应，简记为M2
P
Q
R与011或3对应，简记为M3
P
Q
R与100或4对应，简记为M4
P
Q
R与101或5对应，简记为M5
P
Q
R与110或6对应，简记为M6
P
Q
R与111或7对应，简记为M731/52n个命题变元组成极大项有2n个公式每一个完全成假解释对应一个极大项公式全部完全成假解释对应极大项合取例:考查公式
=PQ有两个成假解释：
(T,F),(F,T)
分别对应于两个极大项(析取式)为
P∨Q,P∨Q于是，有
=(P∨Q)∧(P∨Q)32/52主合取范式定义4仅有极大项组成合取范式称为主合取范式。定理2任何一个合式公式，都有惟一一个主合取范式与该合式公式等价。主合取范式就是公式全部完全成假解释对应极大项合取。33/52求主合取范式两种方法(1)解释法依据公式全部完全成假解释，求出与这些成假解释对应析取式，全部析取式合取就为公式主合取范式。(2)等价变换法将合取范式中每一个析取式用A
A填满命题变元，然后用等价公式进行变换，消去相同部份，即得公式主合取范式。34/52解：原式=(
P
R)
((P
(Q
R))
(
P
(Q
R)))（去蕴涵词、等价词）
=(
P
R)
(P
Q)
(P
R)
(
P
Q
R)于是，(
P
R)=(
P
R)
(QQ)=(
P
R
Q)
(
P
RQ)(P
Q)=(PQ)
(RR)=(P
Q
R)
(PQ
R)(P
R)=(P
R)
(QQ)=(PQR)
(PQR)原式=(100110)(000001)(001011)110=100110000001011=例(p12)求(P
R)
(P
(Q
R))主合取范式勘误！35/52例试求α=(P
R)
(
P
(
Q
R))
主析取范式和主合取范式解:α=(P∨R)
((P∧(Q∧R))∨(P∧((Q∧R))))（去蕴涵词、等价词）=(
P∨R)((
P∧Q∧R)∨(P∧Q)∨(P∧R))（化简）=(P∧R)
∨(
P∧Q∧R)∨(P∧Q)∨(P∧R)（去蕴涵词）=(P∧R)∨(
P∧Q∧R)∨(P∧Q)=(110∨100)∨001∨(111∨110)=∑(1,4,6,7)36/52例试求(P
R)
(
P
(
Q
R))
主析取范式和主合取范式解:已经得到
α
=(
P∧Q∧R)∨(P∧Q)∨(P∧R)∴α=((
P∨P)∧(
P∨Q)∧(Q∨P)∧(Q∨Q)∧(P∨R)∧(Q∨R))∨(P∧R)=((
P∨Q)∧(Q∨P)∧(P∨R)∧(Q∨R))∨(P∧R)=(T∧(P∨Q∨R))
∧((Q∨P)∧(P∨Q∨R)) ∧((P∨R)∧T)∧((P∨Q∨R)∧T)=101∧(010∧011)∧(010∧000)∧000=∏(0,2,3,5)37/52例试求(P
R)
(
P
(
Q
R))
主析取范式和主合取范式另解:已经得到
α
=(
P∧Q∧R)∨(P∧Q)∨(P∧R)
α=(P∨Q∨R)∧(P∨
Q)∧(P∨R)=(P∨Q∨R
)∧(P∨(Q∧R))=(P∧Q∧R)∨(Q∧
P)∨(R∧P)分解,共6项=(P∧Q∧R)∨(Q∧
P∧R) ∨(Q∧P∧R)∨(R∧Q∧P)
∴α=(P∨Q∨R))∧(P∨Q∨R) ∧(P∨Q∨R)∧(P∨Q∨R)=∏(0,2,3,5)38/52主合取范式和主析取范式关系(1)紧密相关性：
一个公式主合取范式和主析取范式是紧密相关。
如例：
=(P
R)
(
P
(Q
R))=
=(P
R)
(
P
(Q
R))=(2)惟一性：任何一个命题演算公式，含有惟一主合取范式和主析取范式，所以假如两个公式含有相同主析取范式或主合取范式，则称两公式逻辑等价。39/52第一章命题演算基础1.1命题和联结词1.2真假性1.3范式及其应用
1.3.1范式
1.3.2主范式
1.3.3范式应用40/52例运筹学问题从甲、乙、丙、丁4个人之中派两个出去执行任务,按以下3个条件共有几个派法？怎样派?(1)假如派甲去,那么丙和丁之中最少要派一;(2)乙和丙不能同时都去;(3)假如派丙去,那么丁必须留下。41/52解:分别用A、B、C、D表示依次派甲、乙、丙、丁去,则依据题意,三种派法分别翻译为:A→(C∨D),﹁(B∧C),C→﹁D都是真命题。于是T=(A→(C∨D))∧﹁(B∧C)∧(C→﹁D)=(﹁A∨C∨D)∧(﹁B∨﹁C)∧(﹁C∨﹁D)=(﹁A∧﹁B∧﹁C)∨(﹁A∧﹁B∧﹁D)∨(﹁A∧﹁C)∨(﹁A∧﹁C∧﹁D)∨(C∧﹁B∧﹁D)∨(D∧﹁B∧﹁C)∨(D∧﹁C)=(﹁A∧﹁B∧﹁C)∨(﹁A∧﹁B∧﹁D)∨(﹁A∧﹁C∧D)∨(﹁A∧﹁C∧﹁D)∨(C∧﹁B∧﹁D)∨(D∧﹁B∧﹁C)∨(D∧B∧﹁C)42/52解:=(﹁A∧﹁B∧﹁C)∨(﹁A∧﹁B∧﹁D)∨(﹁A∧﹁C∧D)∨(﹁A∧﹁C∧﹁D)∨(C∧﹁B∧﹁D)∨(D∧﹁B∧﹁C)∨(D∧B∧﹁C)=(﹁A∧﹁B∧﹁C)∨(﹁A∧﹁B∧﹁D)∨(﹁A∧B∧﹁C∧D)∨(﹁A∧﹁B∧﹁C∧D)
∨(﹁A∧﹁C∧﹁D)∨(A∧C∧﹁B∧﹁D)∨(﹁A∧C∧﹁B∧﹁D)∨(A∧D∧﹁B∧﹁C)∨(﹁A∧D∧﹁B∧﹁C)∨(A∧D∧B∧﹁C)∨(﹁A∧D∧B∧﹁C)43/52另解：从4人中任意取出2人，共有6种取法：(1)挑出甲、乙，不符合第一条。(2)挑出甲、丙，符合全部条件。(3)挑出甲、丁，符合全部条件。(4)挑出乙、丙，不符合第二条。(5)挑出乙、丁，符合全部条件。(6)挑出丙、丁，不符合第三条。44/52例问路问题有A、B两个相邻小岛。A岛居民都是老实人，B岛居民都是骗子。一个旅游者独自登上了两岛中某个岛，他分辨不清这个岛是A岛还是B岛，只知道这个岛上人现有本岛，也有另一岛，他能够向一个人问路1次。
温馨提示
- 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论