第一部分 第二章 命题逻辑等值演算

第二章命题逻辑等值演算•2.1等值式•2.2析取范式与合取范式•2.3联结词的完备集•2.4可满足性问题与消解法重点难点2.1等值式定义2.1设A、B是任意两个命题公式，若等价式A↔B为重言式，则称A与B是等值的，记作：AB•⑴自反性，即对任意命题公式A，AA•⑵对称性，即对任意命题公式A和B，若AB，则BA•⑶传递性，即对任意命题公式A，B和C，若AB，BC，则AC两点注意•“”与“=”“A=B”表示两公式一样，“AB”表示两公式真值一样•与↔是两类完全不同的符号↔是联结词、运算符，A↔B是一个公式。不是联结词，而是两个公式之间的关系符真值表判断等值pqrp(qr）(pq)r(p∧q)r000101001111010101011111100111101111110000111111十六组重要的等值式（模式）•1.双重否定律A¬¬A•2.幂等律A∧AA，A∨AA•3.交换律A∨BB∨A，A∧BB∧A•4.结合律(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)十六组重要的等值式•5.分配律(提取公因式）A∧(B∨C)(A∧B)∨(A∧C)A∨(B∧C)(A∨B)∧(A∨C)•6.德摩根律¬(A∨B)¬A∧¬B¬(A∧B)¬A∨¬B德摩根律的例子•“地大物博”的否定：地不大或物不博¬(A∧B)¬A∨¬B•“用人民币或港币支付”的否定：既不能用人民币支付，也不能用港币支付¬(A∨B)¬A∧¬B十六组重要的等值式•7.吸收律A∨(A∧B)A，A∧(A∨B)A•8.零律A∨11，A∧00•9.同一律A∨0A，A∧1A•10.排中律A∨¬A1•11.矛盾律A∧¬A0十六组重要的等值式•12.蕴涵等值式A→B¬A∨B•13.等价等值式A↔B(A→B)∧(B→A)•14.假言易位A→B¬B→¬A•15.等价否定等值式A↔B¬A↔¬B•16.归谬论(A→B)∧(A→¬B)¬A蕴涵等值式的例子•蕴涵等值式：A→B¬A∨B•否定形式：并非（pq)¬(p→q)p∧¬q•例：并非招手即停招手且不停车归谬论的应用•归谬论(A→B)∧(A→¬B)¬A•反证法如果非p，则q如果非p，则非q所以，p归谬论的例子•亚理士多德：物体的下落速度与物体的重量成正比。•伽利略的思想实验：A快B慢，A＋B比A快；A快B慢，A＋B比A慢。归谬论的例子•一个岛上有一个风俗，凡是外乡人都要作为祭品被杀掉。•但允许被杀的人在临死前说一句话。•如果这句话是真的，则死在真理之神面前。•如果这句话是假的，则死在错误之神面前。•一个哲学家说了一句话，而免于一死。等值演算与置换规则•由已知的等值式推演出另外的等值式的过程称为等值演算。•置换规则设（A）是一个含有公式A的命题公式，（B）是用公式B置换了（A）中的公式A后得到的公式，如果AB，那么（A）（B）。等值演算的例子【例2.1】用等值演算验证等值式p→（q→r）（p∧q）→r()()()()()()pqrpqrpqrpqrpqrpqr等值演算的例子【例2.2】用等值演算法判断下列公式的类型。⑴q∨¬((¬p∨q)∧p)⑵(p∨¬p)→((q∧¬q)∧r)⑶(p→q)∧¬p等值演算的例子解：⑴q∨¬((¬p∨q)∧p)q∨¬((¬p∧p)∨(q∧p))(分配律)q∨¬(0∨(q∧p))(矛盾律)q∨¬(q∧p)(同一律)q∨(¬q∨¬p)(德摩根律)(q∨¬q)∨¬p(结合律)1∨¬p(排中律)1(零律)由此可知，⑴为重言式。等值演算的例子解：⑵(p∨¬p)→((q∧¬q)∧r)1→((q∧¬q)∧r)(排中律)1→(0∧r)(矛盾律)1→0(零律)0(条件联结词的定义)由此可知，⑵为矛盾式。⑶(p→q)∧¬p(¬p∨q)∧¬p(蕴涵等值式)¬p(吸收律)由此可知，⑶是可满足式。练习1.用等值演算验证等值式（1）(p∨q)→r(p→r)∧(q→r)（2）（(p∨q)∧¬（p∧q））¬（p↔q）2.判断公式的类型（1）（p→q）∧p→q（2）（¬（p→q）∧q）∧r判断问题【例2.6】判断王教授是哪里人：•甲说王教授不是苏州人，是上海人•乙说王教授不是上海人，是苏州人•丙说不是上海人，也不是杭州人•王教授说三个人中一个说的全对，一个说对了一半，另一个全不对。解：p：王教授是苏州人q：王教授是上海人r：王教授是杭州人解题思路•pqr001010100•王教授的话是对的，写出公式A（p,q,r)，找出它的成真赋值根据实际情况，只有3个赋值，而不是8个作业习题二38－39页题目：3，417，1819，202.2析取范式与合取范式定义2.2•将命题变元及其否定统称为文字（literal）。•简单析取式（基本和）：仅由有限个文字构成的析取式，也称为子句（clause）。•简单合取式（基本积）：仅由有限个文字构成的合取式。例如：p、q既是一个文字的简单析取式，又是一个文字的简单合取式。p∨q，p∨¬r均是有两个文字的简单析取式，即子句。p∧q∧r，p∧q∧¬q均是有三个文字的简单合取式。定理2.1(1)一个简单析取式是重言式，当且仅当它同时含有一个命题变元及其否定。(2)一个简单合取式是矛盾式，当且仅当它同时含有一个命题变元及其否定。•例如，p∨q∨¬p是重言式p∧¬q∧q是矛盾式范式（normalform）的定义定义2.3•析取范式由有限个简单合取式构成的析取式，简称DNF（disjunctivenormalform）。•合取范式由有限个简单析取式构成的合取式，简称CNF（conjunctivenormalform）。析取范式的例子：A=A1∨A2∨…∨An=(p∧q∧r)∨(p∧q∧¬q)∨p合取范式的例子：A=B1∧B2∧…∧Bm=(p∨q∨r)∧(p∨q∨¬q)∧p子句范式存在定理定理2.3•任一命题公式都存在着与之等值的析取范式•任一命题公式都存在着与之等值的合取范式求范式的步骤如下：⑴消去联结词“→”和“↔”⑵利用双重否定律消去否定联结词“¬”或利用德摩根律将否定联结词“¬”移到各命题变元前(¬内移)。⑶利用分配律，结合律将公式归约为合取范式和析取范式。例题【例2.7】求(p∨q)↔p的合取范式和析取范式。(p∨q)↔p((p∨q)→p)∧(p→(p∨q))(¬(p∨q)∨p)∧(¬p∨(p∨q))((¬p∧¬q)∨p)∧(¬p∨(p∨q))(¬p∨p)∧(¬q∨p)∧(¬p∨p∨q))1∧(¬q∨p)∧(1∨q)1∧(¬q∨p)∧1(¬q∨p)合取范式合取范式析取范式练习•求析取范式与合取范式：(p→q)↔r•合取范式（p∨r)∧(¬q∨r)∧(¬p∨q∨¬r)•析取范式（p∧¬q∧¬r）∨（¬p∧r）∨（q∧r）极小项与极大项定义2.4极小项：在含有n个命题变元的简单合取式中，（1）若每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次（2）且第i个命题变元（或它的否定式）出现在从左算起的第i位上。极大项：简单析取式中满足如上条件。极小（大）项的核心性质•定理：n个命题变元共有2n个极小项（极大项）。pqp∧qp∧¬q¬p∧q¬p∧¬q000001010010100100111000•每个极小（大）项只有一个成真（假）赋值，且各极小项的成真赋值互不相同。•极小项和它的成真赋值构成了一一对应的关系。极小项的记号与编码极小项成真赋值名称¬p∧¬q00m0¬p∧q01m1p∧¬q10m2p∧q11m3•可用成真赋值为极小项进行编码，并把编码作为m的下标来表示该极小项，叫做该极小项的名称。•极小项与其成真赋值的对应关系为：变元对应1，而变元的否定对应0。极小项的记号（n＝3）极小项成真赋值名称¬p∧¬q∧¬r000m0¬p∧¬q∧r001m1¬p∧q∧¬r010m2¬p∧q∧r011m3p∧¬q∧¬r100m4p∧¬q∧r101m5p∧q∧¬r110m6p∧q∧r111m7极大项成假赋值名称p∨q00M0p∨¬q01M1¬p∨q10M2¬p∨¬q11M3极大项成假赋值名称p∨q∨r000M0p∨q∨¬r001M1p∨¬q∨r010M2p∨¬q∨¬r011M3¬p∨q∨r100M4¬p∨q∨¬r101M5¬p∨¬q∨r110M6¬p∨¬q∨¬r111M7极大项的记号（n＝2，3）练习•写出极小项的公式：m4m6m7（当变元的个数分别为3、4时）•写出极大项的公式：M4M6M7（当变元的个数分别为3、4时）定理：极小项与极大项定理2.4¬miMimi¬Mi极大项成假赋值名称p∨q00M0p∨¬q01M1¬p∨q10M2¬p∨¬q11M3极小项成真赋值名称¬p∧¬q00m0¬p∧q01m1p∧¬q10m2p∧q11m3主范式的定义定义2.5主析取范式：析取范式中所有的简单合取式都是极小项。主合取范式：合取范式中所有的简单析取式都是极大项。例：m0∨m1∨m7（n＝3）M0∧M2∧M6（n＝3）22n问题：对于n个命题变元，有多少个主析（合）取范式？主范式的存在性与唯一性定理2.5任何命题公式都存在与之等值的主析取范式和主合取范式，并且是唯一的。证明：（1）存在性：等值演算（2）唯一性：反证法例题与练习【例2.8】求主析取范式与主合取范式：(p→q)↔r•合取范式（p∨r)∧(¬q∨r)∧(¬p∨q∨¬r)•析取范式（p∧¬q∧¬r）∨（¬p∧r）∨（q∧r）练习：求p→q的主范式主范式与真值表定理•若公式A中含n个命题变元，A的主析取范式含s（0≤s≤2n）个极小项，则A有s个成真赋值，•它们是所含极小项编号的二进制表示•其余2n–s个赋值都是成假赋值。•反之也成立。•对主合取范式有相同的结果（对应成假赋值）从真值表求主范式【例】用真值表法，求(p→q)→r的主范式。pqrp→q(p→q)→r0001000111010100111110001101011101011111m001∨m011∨m100∨m101∨m111m1∨m3∨m4∨m5∨m7“排斥或”的公式排斥或pq排斥或000011101110排斥或：(¬p∧q)∨(p∧¬q)m1∨m2通过主范式判别公式类型定理•A为重言式当且仅当A的主析取范式含全部2n个极小项（主合取范式0个极大项）•A为矛盾式当且仅当A的主析取范式不含任何极小项（主合取范式含所有的极大项）•A为可满足式当且仅当A的主析取范式至少含一个极小项。主析取范式与主合取范式的关系定理•同一公式的主析取范式中极小项m的下标和主合取范式中极大项M的下标是互补的。•换言之，对于任一公式，在它的2n个赋值中，非0即1，因此其主析取范式中的极小项和其主合取范式中的极大项的个数之和恰为2n，且其下标不会相同。练习•由主析取范式，求主合取范式（1）A＝m1∨m2（两个变元）（2）B＝m1∨m2∨m3（三个变元）作业习题二38－40页题目：5，6，910，1213，1425，26练习12.已知公式A含3个命题变项p,q,r,且它的成真赋值为000，011，110，求A的主范式。13.已知公式A含3个命题变项p,q,r,且它的成假赋值为010，011，110，111求A的主范式。14.已知公式A含n个命题变项，且无成假赋值，求A的主合取范式。2.3联结词的完备集定义2.6n元真值函数F：{0,1}n→{0,1}定理•每个真值函数，都一一对应一个真值表。每个真值函数，都存在许多与之等值的命题公式。反之，每个命题公式对应唯一的与之等值的真值函数。定义2.7•设S是联结词集合，如果任何n元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。联结词的完备集定理2.6•S＝¬，∧，∨联结词完备集。推论以下集合都是完备集•¬，∧，∨，→，↔•¬，∧，∨，→•¬，∧•¬，∨•¬，→联结词的完备集定义2.8与非联结词：p↑q¬(p∧q)或非联结词：p↓q¬(p∨q)定理2.7