《第二章补充材料命题逻辑部分》由会员分享，可在线阅读，更多相关《第二章补充材料命题逻辑部分（90页珍藏版）》请在金锄头文库上搜索。
1、等值演算 Equivalent CalculusLIUDThursday,August22,20241well-formed formula (wff,合式公式)(1)p,q,r,是合式公式；(2)如果A是合式公式，则A也是；(3)如果A和B是合式公式，则由逻辑联结词联结A和B的符号串也是；(A B)、(A B)、(AB)等等。(4)有限次应用(1)-(3)构成的符号串才是合式公式。2等值演算设A，B为两个合式公式，A B即AB为一个重言式。命题形式相等的判断真值表法等值演算法当命题变项的数目较多时,可把合式公式化成标准型(主析取范式和主合取范式).3等值演算例：判断下述3个公式之间的等值关系
2、：p(qr),(pq)r,(p q)r.InputsOutputsp qrp(qr) (pq)r (p q)rT T TTTTT T FFFFT F TTTTT F FTTTF T TTTTF T FTFTF F TTTTF F FTFT4等值演算设A，B为两个合式公式，A B即AB为一个重言式。命题形式相等的判断真值表法等值演算法当命题变项的数目较多时,可把合式公式化成标准型(主析取范式和主合取范式)5等值演算等值演算:由已知的等值式推演出新的等值式的过程等值演算法等值式模式为基础Theorem1&2应用等值演算规则逐步等值演算将一个命题形式演算成另一个将两个命题形式演算成同一个6等值演算等
3、值演算规则代入规则/替换规则代入规则一个重言式，对其中所有相同的命题变项都用一合式公式代换，其结果仍为一重言式。这一规则称为代入规则代入规则。p ( q p ) p(st) (q (st) (st)7等值演算使用代入规则证明重言式。例：判断(r s) (r s)为重言式。p p为重言式,作代入依据代入规则,便得(r s) (r s)。这公式必是重言式。8等值演算等值演算规则代入规则/替换规则置换规则定理：设(A)是含命题公式A的命题公式，(B)是用命题公式B置换了(A)中的A之后得到的命题公式（不一定是每一处）。如果AB，则(A)(B)。9等值演算例：(p q) p) (p r) p (p r
4、) p(p q) p p10等值演算例：证明p(qr) (p q)r证明：p(qr) p (q r)(蕴涵等值式)( p q) r(结合律) (p q) r(德摩根律)(p q)r(蕴涵等值式)11等值演算例：证明(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 (分配律)T r(排中律)r12等值演算例：证明(p q) ( p ( q r) ( p q) ( p r)T证：左 (p q) (p (q r) (p q) (p r)(
5、德摩根律)(p q) (p q) (p r) (p q) (p r)(分配律)(p q) (p r) (p q) (p r)(结合律，等幂率)(p q) (p r) (p q) (p r)(德摩根律)T(排中律)13等值演算例用等值演算法判断下列公式的类型(3) (p q) (p q) r (p (q q) r(p F) rp r非重言式的可满足式.(2)(pq)( qp)( p q)(q p)( p q)(q p)T该式为重言式.(1)q (pq)q ( p q)q (p q)p (q q)p FF该式为矛盾式.14等值演算等值演算不能直接证明两个公式不等值.证明两个公式不等值的基本思想是找
6、到一个赋值使一个成真,另一个成假.例：证明p(qr)和(pq)r不等值。真值表法先用等值演算化简公式,再观察使用主范式15等值演算化简语句：“情况并非如此：如果他不来，那么我也不去”。p：他来；q：我去 ( p q) (p q) (p q) pq我去了，而他没来。16Normal Form范式LIUDThursday,August22,202417Normal Form(范式)文字与互补对命题变项P及其否定式P统称文字文字(literal)。且P与P称为互补对析取式由文字的析取所组成的公式称为析取式析取式(fundamental disjunction)。合取式由文字的合取所组成的公式称为合取
7、式合取式(fundamental conjunction)。18范式析取式p、p、pq、pqq合取式p、p、pq、pqp19范式析取范式 (disjunctivenormalform,DNF) 形如 A1A2An 的公式，其中Ai (i = 1,n)为合取式。合取范式 (conjunctivenormalform,CNF) 形如 A1A2 An的公式，其中Ai (i = 1,n)为析取式。 20范式析取范式( p q r) ( p q r) (p q r)( p r) (q r)(p q) ( p q)合取范式(p q) ( p q)( p q) r21范式一个析取范式是矛盾式,当且仅当它的每
8、个合取式都是矛盾式；一个合取范式是重言式,当且仅当它的每个析取式都是重言式。22范式求范式的步骤：利用等值式模式将其它联结词转化成 , , ；简化双重否定号，并将所有 写到文字里；利用分配律，将其最终变成合取范式或析取范式。23范式求范式的步骤：利用等值式模式将其它联结词转化成 , , ： pq p q pq ( p q) ( q p) (p q) ( q p)24范式求范式的步骤：简化双重否定号，并将所有 写到文字里： ( p) p ( p q ) p q ( p q ) p q25范式求范式的步骤：利用分配律，将其最终变成合取范式或析取范式：p ( q r ) ( p q ) ( p r
9、) p ( q r ) ( p q ) ( p r )26Normal FormE.G.FindaDNFof (p q)(p q). (p q)(p q)( (p q) (p q) ( (p q) (p q)( p q p q ) (p q) ( p q)( p q p q ) (p p) (p q) (q p) (q q)(p q) (q p)AB (A B) ( A B)27Normal FormE.G.FindaCNFof (p q) (p q). (p q) (p q)(p q) (p q) ( (p q) (p q)(p q) (p q) ( p q) ( p q)(p q) ( p
10、 q)AB ( A B) ( B A)28Normal FormE.G.FindaCNFof (p q)(p q). (p q)(p q) ( (pq)(pq) )(pq) (pq) ) ( p qpq ) ( (pq)( p q) )(p q) ( p q)AB (A B) ( A B)29Normal FormE.G.(p qr)p( (p q) r)p ( (p q) r) p(p q) r) p(p q) r) p(p q p) ( r p)(p q) ( r p) (pq) r)(pq)p)(q r) (p r) p(q r) p30范式范式存在定理任一命题公式都存在与之等值的合取范
11、式和析取范式。但命题公式的合取范式和析取范式不是唯一的。由于范式一般不唯一，所以有必要进一步研究主范式主范式。31范式主范式极小项和极大项极小项(minterm)n个命题变项P1,P2,Pn组成的合取式：Q1 Q2 Qn其中Qi=Pi或Pi。即每个命题变项与它的否定式不同时出现，但二者之一必出现且仅出现一次；且第i个命题变项或其否定出现在从左起的第i位上，则称合取式Q1 Q2 Qn为极小项，并以mi表示。32范式3个命题变项，8个极小项对应情况如下： p q r 0000,记作m0； p q r0011,记作m1； p q r0102,记作m2； p q r0113,记作m3；p q r100
12、4,记作m4；p q r 1015,记作m5；p q r1106,记作m6；p q r1117,记作m7.一般情况下,n个命题变项共产生2n个极小项,分别记为m0,m1,.,m2n-1.33范式主范式极小项和极大项极大项(maxterm)n个命题变项P1,P2,Pn组成的析取式：Q1 Q2 Qn其中Qi =Pi或Pi。即每个命题变项与它的否定式不同时出现，但二者之一必出现且仅出现一次；且第i个命题变项或其否定出现在从左起的第i位上。则称析取式Q1 Q2 Qn为极大项，并以Mi 表示。34范式同极小项情况类似,n个命题变项可产生2n个极大项,每个极大项对应一个二进制数和一个十进制数.十进制数作为
13、该极大项抽象表示的角码.35Normal Form3个命题变项，8个极大项对应情况如下： p q r0000，记作M0 p q r0011，记作M1 p q r0102，记作M2 p q r0113，记作M3 p q r1004，记作M4 p q r1015，记作M5 p q r1106，记作M6 p q r 1117，记作M736范式极大项与极小项的关系：miMi极小项极大项m71117p.q.r0000 M0m61106 p.q.r0011 M1m51015p.q.r0102 M2m41004p.q.r0113 M3m30113p.q.r1004 M4m20102p.q.r1015 M5m
14、10011p.q.r1106 M6m00000p.q.r1117 M737范式主范式极小项的性质(1)任一含有n个命题变项的公式，所有可能的极小项的个数和该公式的解释个数相同，都是2n。(2)每个极小项只在一个解释下为真。(3)极小项两两不等值，并且mi mj F(ij)。(4)任一含有n个命题变项的公式，都可由k个(k2n)极小项的析取来表示。(5)恰由2n个极小项的析取构成的公式必为重言式。38范式主范式极大项的性质(1)任一含有n个命题变项的公式，所有可能的极大项的个数和该公式的解释个数相同，都是2n。(2)每个极大项只在一个解释下为假。(3)极大项两两不等值，并且Mi Mj T(ij)
15、。(4)任一含有n个命题变项的公式，都可由k个(k2n)极大项的合取来表示。(5)恰由2n个极大项的合取构成的公式必为矛盾式。39范式主析取范式与主合取范式主析取范式(fulldisjunctivenormalform)设由n个命题变项构成的析取范式中所有的合取式都是极小项，则称该析取范式为主析取范式（仅由极小项构成的析取范式称为主析取范式）。用表示。主合取范式(fullconjunctivenormalform)设由n个命题变项构成的合取范式中所有的析取式都是极大项，则称该合取范式为主合取范式（仅由极大项构成的合取范式称为主合取范式）。用表示。40范式求给定命题公式A的主析取范式的步骤(1)
16、求A的析取范式A；(2)若A的某简单合取式B中不含命题变项pi或其否定pi,则将B展成如下形式：B B (pi pi) (B pi) (B pi).(3)将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”,如p p用p代,p p用F代,mi mi用mi代.(4)将极小项按由小到大的顺序排列,并用表示之.如m1 m2 m5用(1,2,5)表示.41范式例：求主析取范式.(p q)r)p.解：原公式的析取范式为,p (q r)用p (q q) (r r)取代p.用(p p) (q r)取代(q r).然后展开得极小项.42范式(p q)r)pp (q r)(析取范式)(p ( q q) (
17、r r) ( p p) (q r)(p q r) (p q r) (p q r) (p q r) ( p q r) (p q r)m4 m5 m6 m7 m2 m6m2 m4 m5 m6 m7(2,4,5,6,7).43范式求一命题公式A的主合取范式的步骤(1)先求出合取范式A.(2)若A的某简单析取式B中不含命题变项pi,或其否定pi,则将B展成如下形式：B B (pi pi) (B pi) (B pi).(3)将重复出现的命题变项、重言式及重复出现的极大项都“消去”.(4)将极大项按由小到大的顺序排列,并用表示之.如M1 M2 M5用(1,2,5)表示.44范式例:求(p q)r)p的主合
18、取范式.解:(p q)r)p(p q) (p r)(合取范式)(p q (r r) (p (q q) r)(p q r) (p q r) (p q r) (p q r)(p q r) (p q r) (p q r)M0 M1 M3(0,1,3)45范式例：试由真值表求主范式.(2,4,5,6,7)如何求主合取范式InputsOutputsmpqr(p q)r)p7TTTT6TTFT5TFTT4TFFT3FTTF2FTFT1FFTF0FFFF46范式设命题公式A中含n个命题变项,且设A的主析取范式中含k个极小项mil,mi2,mik则A的主析取范式中必含2n-k个极小项,设为mjl,mj2,mj
19、2n-k.即 A mjl mj2 mj2n-k A A (mjl mj2 mj2n-k) mjl mj2 mj2n-k Mjl Mj2 Mj2n-k47范式由A的主析取范式求主合取范式的步骤(1)求出A的主析取范式中没包含的极小项mj1,mj2,mj2n-k.(2)求出与(1)中极小项角码相同的极大项Mj1,Mj2,Mj2n-k.(3)由以上极大项构成的合取式为A的主合取范式.48范式例：(p q)r)pm2 m4 m5 m6 m7(2,4,5,6,7)M0 M1 M3(0,1,3)49范式主析取范式定理任一含有n个命题变项的公式，都存在唯一的与之等值的且恰仅含这n个命题变项的主析取范式。主合
20、取范式定理任一含有n个命题变项的公式，都存在唯一的与之等值的且恰仅含这n个命题变项的主合取范式。50范式主析取范式的用途1.判断两命题公式是否等值.2.判断命题公式的类型.3.求命题公式的成真和成假赋值.51范式1.判断两命题公式是否等值.由于任何命题公式的主析取范式都是唯一的,因而若AB，说明A与B有相同的主析取范式。反之，若A,B有相同的主析取范式，必有AB。52范式2.判断命题公式的类型设A是含n个命题变项的命题公式,A为重言式，当且仅当A的主析取范式中含全部2n个极小项；当且仅当A的主合取范式中不含任意极大项即为空公式。A为矛盾式，当且仅当A的主析取范式中不含任何极小项即为空公式；当且
21、仅当A的主合取范式中含全部2n个极大项。若A的主析取范式中至少含一个极小项，则A是可满足式。53范式例判断下列命题公式的类型.(1)(pq) p)q；(2)(pq) q。54范式(1)(pq) p)q ( p q) p) q（消去） ( pq) p q（内移）(p q) p q（得到析取范式）(p q) ( p (q q) (p p) q)（加项）(p q) ( p q) (p q) (p q)m0 m1 m2 m3 (0,1,2,3).55范式(2)(pq) q( p q) qqq (p p)(p q) (p q)m1 m3 (1,3).由以上推演可知,(1)为重言式,(2)为可满足式.56
22、范式3.求命题公式的成真和成假赋值.在上例(2)中(pq) q (1,3).“FT”、“TT”是成真赋值,“FF”、“TF”是成假赋值.57推理理论58推理理论学院发生了Bat的早餐包子失窃案，得到以下事实：(1)某甲或阳阳拿走了Bat的包子；(2)若阳阳作案，则作案时间不是早晨；(3)若阳阳提供的证明正确，则Bat的办公室未上锁；(4)若阳阳提供的证明不正确，则作案时间是早晨；(5)Bat的办公室是上了锁的。Bat推出是某甲盗窃了他的包子！他的推断是否正确呢？59推理理论推理是从前提推出结论的思维过程，前提是指已知的命题公式p1,p2pn，结论是从前提出发应用推理规则推出的命题公式q。正确的
23、推理即是指p1 p2 pn q 是重言式。60推理理论解推理问题,应先将命题符号化,然后写出前提、结论和推理的形式结构,最后进行判断.判断推理是否正确的方法:真值表法等值演算法主析取范式法构造证明法61推理理论例：判断下面推理是否正确:(1)若今天是周二，则要来上课。今天是周二，所以要来上课。解设p:今天是周二,q:我来上课推理的形式结构为(pq) pq证明 用等值演算法 (pq) p q ( p q) p) q (p q) p) q p q q T得证推理正确得证推理正确62推理理论例：判断下面推理是否正确:(2)若今天是周二,则要来上课.我来上课了.所以,今天是周二.解：设p:今天是周二,
24、q:我来上课推理的形式结构为(pq) qp证明：用主析取范式法 (p q) qp ( p q) qp ( p q) q) p q p ( p q) (p q) (p q) (p q) m0 m2 m3 不是重言式,所以推理不正确.63推理理论例：判断下面推理是否正确:(3)如果三角形的两边相等，则其所对的角相等；一个三角形的两边不相等，所以其所对角不相等。解设p:三角形的两边相等,q:三角形的两边所对的角相等推理的形式结构为(pq) p q推理不正确，或论证并非有效。根据欧几里得几何，上述例题中的结论确实成立，但是这个结论的正确性实际并不是由例中的两个前提推得！64推理理论判断推理是否正确的方
25、法:真值表法等值演算法主析取范式法构造证明法直接证明法附加前提证明法归谬法(反证法)65推理理论推理演算出发点欲直观看出由前提A到结论B的推演过程，且便于在谓词逻辑中使用。方法（1）引入几条推理规则（2）利用基本推理公式从前提A1，A2，An出发，配合使用推理规则和基本推理公式，逐步推演出结论B。66推理理论理论依据(AB)(BC)r) (AC)r)是重言式。也即，从前提A，C出发，推演出结论r。可以先由前提A推演出结论B，而后再由前提B，C出发，推演出结论r。67推理理论推理定律A (A B) 附加律(A B) A 化简律(AB) A B 假言推理/分离式(AB) B A 拒取式(A B)
26、B A 析取三段论(AB) (BC) (AC) 假言三段论(AB) (BC)(AC) 等价三段论68推理理论推理演算主要的推理规则(1)前提引入规则：在证明的任何步骤上，都可引入前提(2)结论引入规则：在证明的任何步骤上，所证明的结论都可以作为后续证明的前提。(3)代入规则：仅限于重言式中的命题变项(4)置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以用与之等值的命题公式置换。(5)分离规则：由A及AB成立,可将B分离出来(6)条件证明规则：A1 A2 B与A1(A2B)等价69构造推理的论证70例：构造下面推理的证明:前提：p q,qr,ps, s结论：r (p q)证明：(1
27、)ps前提引入(2) s 前提引入(3) p(1)(2)拒取式(4)p q前提引入(5)q(3)(4)析取三段论(6)qr前提引入(7)r(5)(6)假言推理(8)r (p q)(7)(4)合取推理正确,r (p q)是有效结论推理理论71推理理论例：构造下面推理的证明:前提:p q, q r,rs结论:p s证明：(1) p q前提引入(2)pq(1)置换(3) q r前提引入(4)qr (3)置换(5)pr(2)(4)假言推理(6)rs前提引入(7)ps (5)(6)假言推理(8)p s(8)置换推理正确72推理理论例:证明( (pq)(r s) (qp) r) r)(pq)证明：(1)(
28、qp) r前提引入(2)r(qp)(1)置换(3)r前提引入(4)qp(2)(3)分离(5) (pq) (r s)前提引入(6)(r s) (pq)(5)置换(7)r s(3)+附加率(8)p q(6)(7)分离(9)pq(4)(8)73推理理论学院发生了Bat的早餐包子失窃案，得到以下事实：(1)某甲或阳阳拿走了Bat的包子；(2)若阳阳作案，则作案时间不是早晨；(3)若阳阳提供的证明正确，则Bat的办公室未上锁；(4)若阳阳提供的证明不正确，则作案时间是早晨；(5)Bat的办公室是上了锁的。Bat推出是某甲盗窃了他的包子！他的推断是否正确呢？74推理理论符号化：p：某甲拿走了Bat的包子，
29、q：阳阳拿走了Bat的包子，r：作案时间是早晨，s：阳阳提供的证明正确,t：Bat的办公室上了锁；前提：p q,qr,st, sr,t结论：p75推理理论前提：p q,q r,s t, s r,t 结论：p(1)t(2)s t(3) s(4) s r(5)r(6)q r(7) q(8)p q(9)p76附加前提证明法77推理理论欲证明欲证明 等价地证明等价地证明前提前提: A1, A2, , Ak 前提前提: A1, A2, , Ak, C结论结论: CB 结论结论: B附加前提证明法理由: (A1A2Ak) (CB) (A1A2Ak)( CB) (A1A2AkC)B (A1A2AkC) B7
30、8推理理论附加前提证明法例：构造下面推理的证明:前提: p q, q r,rs结论:ps证明：(1)p附加前提引入(2) p q前提引入(3)q (1)(2)析取三段论(4) q r前提引入(5)r (3)(4)析取三段论(6)rs 前提引入(7)s (5)(6)假言推理推理正确，ps是有效结论79归谬法（反证法）80推理理论欲证明前提：A1,A2,Ak结论：B将B加入前提,若推出矛盾,则得证推理正确.归谬法（反证法）理由: A1 A2 AkB (A1 A2 Ak) B (A1 A2 Ak B)括号内部为矛盾式当且仅当 (A1 A2 AkB)为重言式81推理理论例：构造下面推理的证明前提：p(
31、 (r s) q),p, s结论： q(1)p( (r s)q)前提(2)p前提(3) (r s) q(1)(2)假言推理(4) ( q) 否定结论(5)q (4)置换(6)r s (3)(5)拒取式(7) s 前提(8)s (6)化简(9)s s (7)(8)合取由(9)得出矛盾，说明推理正确。82归结法83推理理论归结法（Resolution）出发点基于推理规则的方法，规则与公式较多，技巧较高。能否仅建立一条推理规则，便于机器证明与程序实现。理论依据定理AB为重言式的充分必要条件是A B为矛盾式。 84推理理论归结法（Resolution）归结法步骤1.从A B出发（欲证AB是重言式，等价
32、于证A B是矛盾式）2.建立子句集S，将A B化成合取范式：C1 C2 Cn其中Ci为析取式。由诸Ci构成子句集 S=C1，C2，Cn3.对S中的子句作归结（消互补对），归结结果（归结式）仍放入S中。重复此步。4.直至归结出空子句(矛盾式)。85推理理论归结法（Resolution）归结推理规则设子句1C1=L C1子句2C2=L C2（其中L和L为互补对）新子句R(C1,C2)=C1 C2理由理由 C1 C2 C1 C2 ( (L C1)()(L C2) ) (C1 C2) ( ( L L) (C1 C2) T86推理理论归结法（Resolution）例1:证明 (pq)p q证明：1. 先
33、将(pq)p q 化成合取范式( pq)p q2. 建立子句集s = pq, p, q 87推理理论归结法（Resolution）3. 归结过程:(1) p q(2)p(3)q (1)(2)归结(4) q(5)(3)(4)归结归结出空子句(矛盾式)证明结束。S = qq,S = qS = pq, p,88推理理论例2:用归结法证明(p q) (q r)(p r)证明：1.先将(pq) (qr) (pr)化成合取范式( p q) ( q r) p r2.建立子句集s = p q, q r,p, r89推理理论归结过程:(1) p q(2) q r(3)p(4) r(5) p r(1)(2)归结(6)r(3)(5)归结(7)(4)(6)归结归结出空子句(矛盾式)证明结束。 rr,S = rp,S = rS = pq, p, pr, qr, S =90
