第2章命题逻辑等值演算

1、1第第2章命题逻辑等值演算章命题逻辑等值演算等值式与基本的等值式等值式与基本的等值式等值演算与置换规则等值演算与置换规则析取范式与合取范式，主析取范式与主合取析取范式与合取范式，主析取范式与主合取范式范式联结词完备集联结词完备集可满足性问题与消解法可满足性问题与消解法22.1 等值式等值式q等值式：公式等值式：公式A，B的等价式的等价式AB为永为永真式真式v符号：符号：，也称，也称A逻辑恒等于逻辑恒等于B 32.1 等值式等值式pppp pFTFTTFTTq例子例子v 判断判断pp 42.1 等值式等值式pqppqp qpq p qFFTTTTFTTTTTTFFFFTTTFTTTq例子例子v

2、判断判断 pq p q 52.1 等值式等值式q否定律否定律v双重否定律双重否定律 ppv德摩根律德摩根律 (p q) p q (p q) p qq幂等律幂等律 p p p， p p pq交换律交换律 vp q q p vp q q p ；vp q q p62.1 等值式等值式q结合律结合律v(p q) r p (q r)v(p q) r p (q r)v(p q) r p (q r)q分配律分配律vp (q r) (p q) (p r)vp (q r) (p q) (p r)72.1 等值式等值式q吸收律吸收律vp (p q) pvp (p q) pq常元律常元律v零律: p T T， p

3、F Fv同一律: p F p， p T pv排中律: p p Tv矛盾律: p p F82.1 等值式等值式q蕴含等值式蕴含等值式 p q p qq等价等值式等价等值式 p q (p q) (q p)q假言易位假言易位 p q q pq等价否定等值式等价否定等值式 p q p qq归缪律归缪律 (p q ) (p q ) p 92.1 等值式等值式说明：说明： (1)16组等值模式都可以给出无穷多个同类型的具组等值模式都可以给出无穷多个同类型的具体的等值式。体的等值式。 (2)证明上述证明上述16组等值式的组等值式的代入实例代入实例方法可用真值方法可用真值表法，把表法，把改为改为所得的命题公式

4、为永真式，则所得的命题公式为永真式，则成立。成立。102.1 等值式等值式q置换规则置换规则：设：设(A)是含公式是含公式A的命题公式，的命题公式， (B)是用公式是用公式B置换了置换了(A)中所有中所有A后得到的后得到的命题公式，若命题公式，若B ，则，则(A) (B) 。q说明：说明：v等值演算过程中遵循的重要规则。等值演算过程中遵循的重要规则。v一个命题公式一个命题公式A，经多次置换，所得到的新公式经多次置换，所得到的新公式与原公式等价。与原公式等价。v称由已知的等值式推演出另外一些等值式的过程称由已知的等值式推演出另外一些等值式的过程为等值演算。为等值演算。112.1 等值式等值式1.

5、试证：试证：p(qr) (p q)r证明：证明：a. p(qr)p(qr) b. p(qr)pqr c.pqr(p q) rd. (p q) r (p q)r122.1 等值式等值式2 试证：试证：(p q)(p(p q)(pq)左边左边 (p q) (p(p q) (p q) (p(p q) (p q) (p q) (p p q) (q p q) (p q)132.1 等值式等值式3. 证明：证明：(pq) (p (qr)(p q)(p r)为一为一永真式永真式证明：原式证明：原式 (pq) (p(q r)(pq)(pr) (pq) (pq) (pr)(pq) (pr) (pq) (pr)(

6、pq) (pr)P19 例例2.3 从左面演算从左面演算142.2 析取范式和合取范式析取范式和合取范式 q文字文字(literal): 命题变元及其否定命题变元及其否定q简单析取式简单析取式:仅由有限个文字构成的析取式仅由有限个文字构成的析取式q简单合取式简单合取式:仅由有限个文字构成的合取式仅由有限个文字构成的合取式q例：设例：设p、q为二个命题变元为二个命题变元vp，q，pp，qq，pq， q p，pq，p q 称为简单析取式称为简单析取式vq，pp，qq， pq， q p，pq，p q 称为简单合取式。称为简单合取式。152.2 析取范式和合取范式析取范式和合取范式q定理定理: 1)一

7、个简单析取式是永真式当且仅当它同时含一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否定式某个命题变元及它的否定式证明？证明？2)一个简单合取式是永假式当且仅当它同时含一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否定式某个命题变元及它的否定式证明？证明？162.2 析取范式和合取范式析取范式和合取范式q析取范式析取范式:由有限个简单合取式构成的析取式由有限个简单合取式构成的析取式vA1 An, Ai 为合取式为合取式v( p q) (p r)q合取范式合取范式:由有限个简单析取式构成的合取式由有限个简单析取式构成的合取式vA1 An, Ai 为合取式为合取式v( p q)

8、(p r)q析取范式与合取范式统称为析取范式与合取范式统称为范式范式17182.2 析取范式和合取范式析取范式和合取范式q定理：定理：v设设Ai 为简单合取式，析取范式为简单合取式，析取范式A1 An F 当且仅当当且仅当 Ai F，任意，任意Aiv设设Ai 为简单析取式，为简单析取式， 合取范式合取范式A1 An T 当且仅当当且仅当 Ai T，任意，任意Ai192.2 析取范式和合取范式析取范式和合取范式q范式存在定理范式存在定理: 任意命题公式都存在着与之等值任意命题公式都存在着与之等值的析取范式与合取范式的析取范式与合取范式方法：方法： 步骤一：步骤一：消去消去“”、“”联结词联结词步

9、骤二：步骤二：消去双重否定符，内移否定符消去双重否定符，内移否定符步骤三：步骤三：使用分配律使用分配律202.2 析取范式和合取范式q范式存在定理范式存在定理: 任意命题公式都存在着与之等值任意命题公式都存在着与之等值的析取范式与合取范式的析取范式与合取范式方法：方法： 步骤一：消去步骤一：消去“”、“”联结词联结词步骤二：消去双重否定符，内移否定符步骤二：消去双重否定符，内移否定符步骤三：使用分配律步骤三：使用分配律212.2 析取范式和合取范式q步骤一：利用等值公式：化去步骤一：利用等值公式：化去“”、“”联结联结词词v p q p qv p q (p q) (q p)222.2 析取范式

10、和合取范式q范式存在定理范式存在定理: 任意命题公式都存在着与之等值任意命题公式都存在着与之等值的析取范式与合取范式的析取范式与合取范式方法：方法： 步骤一：消去步骤一：消去“”、“”联结词联结词步骤二：消去双重否定符，内移否定符步骤二：消去双重否定符，内移否定符步骤三：使用分配律步骤三：使用分配律232.2 析取范式和合取范式q消去双重否定符，内移否定符消去双重否定符，内移否定符v德摩根律德摩根律 (p q) p q (p q) p qv双重否定律双重否定律 p p242.2 析取范式和合取范式q范式存在定理范式存在定理: 任意命题公式都存在着与之等值任意命题公式都存在着与之等值的析取范式与

11、合取范式的析取范式与合取范式方法：方法： 步骤一：消去步骤一：消去“”、“”联结词联结词步骤二：消去双重否定符，内移否定符步骤二：消去双重否定符，内移否定符步骤三：使用分配律步骤三：使用分配律252.2 析取范式和合取范式q利用利用“ ”对对“ ”的分配，将公式化成为析取范式的分配，将公式化成为析取范式vp (q r) (p q) (p r)262.2 析取范式和合取范式q 例：求例：求(p q) (p q)的析取范式的析取范式 1. 化去化去 ( p q) (p q)2. “ ”对对“ ”分配，化为析取范式分配，化为析取范式 ( p p q) (q p q) 3. 最简析取范式最简析取范式

12、p q 那么如何获得合取范式呢？那么如何获得合取范式呢？272.2 析取范式和合取范式q例：求例：求(p q) r) p的合取范式和析取范式的合取范式和析取范式 (一一) 求析取范式求析取范式原式原式 ( (p q) r) p ( (p q) r) p ( (p q) r) p (p q) r) p (p r) (q r) p p (p r) (q r) p (q r)282.2 析取范式和合取范式(二二)求合取范式求合取范式原式原式 ( (p q) r) p ( (p q) r) p ( (p q) r) p (p q) r) p (p p q) (p r) (p q) (p r)292.2

13、 析取范式和合取范式讨论：讨论：q一个命题公式的析取范式不是唯一的，但同一一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等值的命题公式的析取范式一定是等值的q练习练习vP38 5(2) 6(2)302.2 析取范式和合取范式q极小项极小项(极大项极大项):含有含有n个命题变元的简单合取式个命题变元的简单合取式 (简单析取式简单析取式)并满足并满足v每个命题变元和它的否定式不同时出现，而二者之一每个命题变元和它的否定式不同时出现，而二者之一必出现且仅出现一次必出现且仅出现一次v第第i个命题变元或它的否定式出现在从左算起的第个命题变元或它的否定式出现在从左算起的第i位上位上(若无

14、角标则按字典顺序排列若无角标则按字典顺序排列)q若有若有个命题变元，则有个命题变元，则有2n个极小项（极大项）个极小项（极大项）312.2 析取范式和合取范式q极小项的编码极小项的编码:对应成真赋值对应成真赋值三个变元三个变元p、q、r可构造可构造8个极小项：个极小项： pqr FFF 0 记作记作 m0 pqr FFT 1 记作记作 m1 pqr FTF 2 记作记作 m2 pqr FTT 3 记作记作 m3 pqr TFF 4 记作记作 m4 pqr TFT 5 记作记作 m5 pqr TTF 6 记作记作 m6 pqr TTT 7 记作记作 m7322.2 析取范式和合取范式q极大项的编

15、码极大项的编码:对应成假赋值对应成假赋值如三个变元如三个变元 p、q、r，其记法如下：其记法如下：pqr F F F 0 记作记作 M0p q r F F T 1 记作记作 M1p qr F T F 2 记作记作 M2p q r F T T 3 记作记作 M3 p q r T T T 7 记作记作 M7332.2 析取范式和合取范式q定理定理:设设mi和和Mi是命题变元是命题变元p1, p2 pn形成的形成的极小项和极大项，则：极小项和极大项，则：(1) mi mj F, (ij)(2) Mi Mj T, (ij)(3) mi T, (i =0,1,2n-1) (4) Mi F, (i =0,

16、1,2n-1) (5) mi Mi； Mi mi342.2 析取范式和合取范式q 主析取范式主析取范式(主合取范式主合取范式)：由：由n个命题变元构成个命题变元构成的的析取范式析取范式(合取范式合取范式)中中所有的简单合取式所有的简单合取式(简单简单析取式析取式)都是极小项都是极小项(极大项极大项)q定理定理: 任何命题公式都存在着与其等值的主析取任何命题公式都存在着与其等值的主析取范式和主合取范式，并且是唯一的。范式和主合取范式，并且是唯一的。352.2 析取范式和合取范式q证法一证法一v在真值表中，使命题公式的真值为在真值表中，使命题公式的真值为T的指派所对应的的指派所对应的极小项的析取，

17、即为此公式的主析取范式极小项的析取，即为此公式的主析取范式证：证：给定一个命题公式给定一个命题公式A，使其为使其为T的真值指派所的真值指派所对应的极小项为对应的极小项为m1, m2, mk,这些极小项的这些极小项的析取记为析取记为B，为此要证为此要证AB，即要证即要证A与与B在相在相同的指派下具有相同的真值。同的指派下具有相同的真值。362.2 析取范式和合取范式首先对于使首先对于使A为为T的指派显然使的指派显然使B为为T对于使对于使A为为F的指派，它对应的极小项的指派，它对应的极小项(设为设为mj )不不包含在包含在m1, m2, mk 中。所以中。所以 mj为使为使B为为F的指派的指派所以

18、所以A B 得证得证372.2 析取范式和合取范式q一个公式的主析取范式即为令此公式的真值为一个公式的主析取范式即为令此公式的真值为T的指派所对应的极小项的析取。的指派所对应的极小项的析取。q一个命题公式的真值表是唯一的，因此一个命一个命题公式的真值表是唯一的，因此一个命题公式的主析取范式也是唯一的题公式的主析取范式也是唯一的382.2 析取范式和合取范式析取范式和合取范式p q r m1 m3 m5 m6 m7pqrpqrFFFFFFTTFTFFFTTTTFFFTFTTTTFTTTTTp q r的真值表的真值表392.2 析取范式和合取范式析取范式和合取范式q证法二：构造法证法二：构造法v

19、用等值演算方法求命题公式主析取范式的方法用等值演算方法求命题公式主析取范式的方法 将命题公式化归为与其等值的析取范式将命题公式化归为与其等值的析取范式 添变元添变元: 消去重复项消去重复项Ai (pj pj) (Ai pj) (Ai pj) 402.2 析取范式和合取范式q例：求例：求(p(pq)q的主析取范式的主析取范式解：解：原式原式(pp)(pq)q v-(1)化为析取范式化为析取范式 (pq)q v-(2)化简化简(pq)(q(pp)(pq)(pq)(pq) v-(3)添项添项(pq)(pq) v-(4)合并相同最小项合并相同最小项412.2 析取范式和合取范式q主析取范式的用途讨论：

20、主析取范式的用途讨论： 求公式的成真与成假赋值求公式的成真与成假赋值 判断公式类型判断公式类型 判断两个命题公式是否等值判断两个命题公式是否等值 应用主析取范式分析和解决实际问题应用主析取范式分析和解决实际问题422.2 析取范式和合取范式q例：某研究所要从例：某研究所要从3名科研骨干名科研骨干A，B，C中挑中挑选选12名出国进修，由于工作需要，选派时名出国进修，由于工作需要，选派时要满足以下条件：要满足以下条件： 若若A去，则去，则C同去。同去。 若若B去，则去，则C不能去。不能去。 若若C不去，则不去，则A或或B可以去。可以去。解解:设设p：派：派A去；去；q：派：派B去；去；r：派：派C

21、去。去。则则(pr) (qr)(r (pq) 432.2 析取范式和合取范式经演算可得：经演算可得：(pr) (qr)(r (pq) m1m2m5可知选派方案有三种：可知选派方案有三种： C去，去，A，B都不去。都不去。 B去，去，A，C不去。不去。 A，C去，去，B不去。不去。442.2 析取范式和合取范式q主合取范式主合取范式v任何一个命题公式都可求得它的主合取范式任何一个命题公式都可求得它的主合取范式v一个命题公式的主合取范式是唯一的一个命题公式的主合取范式是唯一的v在真值表中，令命题公式的真值为在真值表中，令命题公式的真值为“F”的的指派就对应其主合取范式的一个极大项指派就对应其主合取

22、范式的一个极大项452.2 析取范式和合取范式q 例例:求求p(pq)q的主合取范式的主合取范式 解：原式解：原式 p( pq)q(p p)(pq)q(pq)q(pq) q(pq)(q(p p) (pq)( pq) M0 M2 pq上式上式FFFFTTTFFTTT462.2 析取范式和合取范式 主合取范式与主析取范式转换主合取范式与主析取范式转换q公式公式: A = mi1 mi2 misv A = mj1 mj2 mjt ，t=2n-sv A A (mj1 mj2 mjt ) mj1 mj2 mjt Mj1 Mj2 Mjt 472.2 析取范式和合取范式q讨论：具有讨论：具有n个变元的命题公

23、式有多少个不同的主个变元的命题公式有多少个不同的主析取范式？析取范式？q对于含有个变元的命题公式，必定可写出对于含有个变元的命题公式，必定可写出22n个个主析取范式主析取范式(包括包括F)。q同理，含有个变元的命题公式，也可写出同理，含有个变元的命题公式，也可写出22n个个主合取范式主合取范式(包括包括T)。练习练习8 (3), 11(3)48492.3 联结词的完备集性质：pq(pq)(qp)(pq)(pq)pq (pq) pqqp(可交换的)(pq)rp(qr)(可结合的)pqpqFFFFTTTFTTTFn排斥或排斥或(异或异或) 符号：符号：“”( )502.3 联结词的完备集“与非与非

24、”联结词：联结词：符号符号“”(pq)读作：读作：“p与与q的的否定否定”q(pq)(pq)pqpqFFTFTTTFTTTF512.3联结词的完备集q“或非或非”联结词：联结词：(a)符号：符号：“” (b)(pq) (pq)pqpqFFTFTFTFFTTF522.3 联结词的完备集联结词的完备集q真值函数真值函数F: 0,1n 0,1q联结词完备集联结词完备集S: vS是一个联接词集合是一个联接词集合v每一个真值函数都可以由仅含每一个真值函数都可以由仅含S中的联接词构成中的联接词构成的公式表示的公式表示q定理定理: S = ， ， 是联接词完备集是联接词完备集 证明：证明：任何一个任何一个n

25、（n 1）元真值函数都与唯一）元真值函数都与唯一的一个主析取范式等值，而主析取范式仅含的一个主析取范式等值，而主析取范式仅含 ， ， 532.3 联结词的完备集联结词的完备集q推论推论: S = ， 是联接词完备集是联接词完备集 证明：证明：p q (p q) ( p q) 542.3 联结词的完备集联结词的完备集q定理定理: ， 是联接词完备集是联接词完备集证明：证明：首先，首先， p (p p) pp其次，其次，p q (p q) (pq) (pq) (pq) (pq) (p q)552.4 消解法消解法q可满足性问题：可满足性问题：v用于证明用于证明A是否永真是否永真v用于验证逻辑蕴涵用

26、于验证逻辑蕴涵 A1 Ak B 永真永真 当且仅当当且仅当 A1 Ak B 永假永假q解决方法解决方法v真值表真值表v主析取范式主析取范式v主合取范式主合取范式u缺点：计算量大缺点：计算量大引入消解法！引入消解法！56q文字文字l的补：的补： vlc= p，如果，如果l =pvlc=p，如果，如果l = pq消解式：消解式： C1 , C2是简单析取式，是简单析取式，C1= C1 l, C2= C2 lcvRes(C1,C2)= C1 C2q定理定理：C1 C2 Res(C1,C2)v消解式是原公式的逻辑推论消解式是原公式的逻辑推论v讨论！是简单析取式讨论！是简单析取式2.4 消解法消解法57

27、q定理定理： C1 C2和和Res(C1,C2)可满足性相同可满足性相同 证明：证明：C1= C1 l, C2= C2 lc 如果如果C1 C2可满足，则存在可满足，则存在v，v(Ci)=T 假设假设v(l)=T，则，则v(C2)=T。 如果如果Res(C1,C2)可满足，则存在可满足，则存在v 存在存在l在在C1使得使得v(l)=T, v可以扩展为可以扩展为 v(p)=F 如果如果p=l v(p)=T 如果如果p=lc v对对C1 C2赋值为赋值为Tv(C1 C2)=T2.4 消解法消解法58qC1 C2和和Res(C1,C2)不等值不等值q例：例：C1=p q r, C2=prvRes(C

28、1,C2) = p qvv=FTT满足满足Res(C1,C2) 但不满足但不满足C1 C22.4 消解法消解法59q消解推导：消解推导：S=C1 Cn和和Cv符号：符号：C1,Cn Cv存在公式序列存在公式序列A1, A2,Ak，对每个，对每个i(i=1,k), Ai是某个是某个Cj或者或者 Ai是有序列中前面的公式应用消解得到是有序列中前面的公式应用消解得到 Ak=Cv称称A1,Ak是由是由S到到C的推导的推导v如果如果C 为空子句为空子句，则称此序列是，则称此序列是S的一个否证的一个否证2.4 消解法消解法60：如果合取范式如果合取范式S有否证，则有否证，则S是不是不可满足可满足 证明：证

29、明：每次使用消解，都保持可满足性。如果每次使用消解，都保持可满足性。如果消解结果不可满足，则消解结果不可满足，则S必不可满足。必不可满足。：如果合取范式如果合取范式S是不可满足，则是不可满足，则S有否证有否证 2.4 消解法消解法61q消解算法（分层饱和法）消解算法（分层饱和法）输入：合式公式输入：合式公式A输出：输出：yes (A可满足可满足)，no (A不可满足不可满足)2.4 消解法消解法1. 求求A的合取范式的合取范式S.2. 令令i=1, S(0)=S.3. 若若S(i)包含空子句，则包含空子句，则S不可满足，算法终止不可满足，算法终止. 4. i=i+1.5. 构造构造S(i)=R

30、es(C1,C2) | C1 (S(0) S(i-1)且且C2 S(i-1).6. 若若S(i) S(0) S(i-1)则则S是可满足的，算法终止是可满足的，算法终止.7. 转转362q书书P37页例题页例题2.14A=( p q) (p q) ( q)v循环循环1 开始，开始， S(0) = S(1) = p q, p q, q S(2) =通过对通过对S(0) 、S(1) ， S(1) 进行消解得到进行消解得到 S(2) = q, p, pv循环循环2开始，开始， S(0) = p q, p q, q S(1)=q, p, p S(2) =v得到得到，算法终止，算法终止2.4 消解法消解法

31、63q例例2：S= p q, p q, pq, pq2.4 消解法消解法 p qp q q p q q p p q q 6465：如果合取范式如果合取范式S含有文字含有文字l，S为为vS先删除包含先删除包含l的简单析取式的简单析取式v再删除剩下的简单析取式中再删除剩下的简单析取式中lc则则S和和S可满足性相同可满足性相同 证明：证明： 如果如果v为满足为满足S的赋值，的赋值，S含有文字含有文字l，v(l)=T，对任意，对任意S中中C，必有，必有v(S)=T。 如果如果v为满足为满足S的赋值，则可以扩展为满足的赋值，则可以扩展为满足S的的赋值（验证）！赋值（验证）！ 2.4 消解法消解法66：如

32、果合取范式如果合取范式S是不可满足，则是不可满足，则S有否证有否证 证明：证明：对对S中所含命题个数中所含命题个数k归纳证明归纳证明 第一步骤第一步骤 k=1: S中有中有p, p 第二步骤第二步骤 假设假设kn时定理成立，证明时定理成立，证明k=n时定时定理成立理成立 1. 对对S p应用引理应用引理1，得到等满足性的，得到等满足性的S 2. 对对S p应用引理应用引理1，得到等满足性的，得到等满足性的S 由假设，存在由假设，存在S的否证的否证C1,Ci，S的否证的否证 D1,Dj2.4 消解法消解法67q 证明（继续）：证明（继续）： 1. 对对S p应用引理应用引理1，得到等满足性的，得

33、到等满足性的S 2. 对对S p应用引理应用引理1，得到等满足性的，得到等满足性的S 由假设，存在由假设，存在S的否证的否证C1,Ci，S的否证的否证 D1,Dj 情况情况1：Ct (i t 1)或或Ds (j t 1)都是由不含都是由不含p的简单的简单析取式消解得到，析取式消解得到， C1,Ci或或D1,Dj为为S的否证的否证 情况情况2： Ct (或或Ds)不满足情况不满足情况1条件，则扩展条件，则扩展Ct (或或Ds)得到得到Ct= Ct p (或或Ds = Ds p ) ，则，则Ct (或或Ds )属于属于S ，且，且 Ci= p， Dj=p，消解得到，消解得到空子句空子句2.4 消解

34、法消解法68第二章第二章 习题课习题课q主要内容主要内容l等值式与等值演算等值式与等值演算l基本等值式（基本等值式（1616组，组，2424个公式）个公式）l主析取范式与主合取范式主析取范式与主合取范式l联结词完备集联结词完备集l消解法消解法69基本要求基本要求l 深刻理解等值式的概念深刻理解等值式的概念l 牢记基本等值式的名称及它们的内容牢记基本等值式的名称及它们的内容l 熟练地应用基本等值式及置换规则进行等值演算熟练地应用基本等值式及置换规则进行等值演算l 理解文字、简单析取式、简单合取式、析取范式、合取范式的概理解文字、简单析取式、简单合取式、析取范式、合取范式的概念念l 深刻理解极小项

35、、极大项的概念、名称及下角标与成真、成假赋深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系值的关系，并理解简单析取式与极小项的关系l 熟练掌握求主范式的方法（等值演算、真值表等）熟练掌握求主范式的方法（等值演算、真值表等）l 会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值断两个公式是否等值l 会将公式等值地化成指定联结词完备集中的公式会将公式等值地化成指定联结词完备集中的公式l 会用命题逻辑的概念及运算解决简单的应用问题会用命题逻辑的概念及运算解决简单的应用问题l

36、 掌握消解规则及其性质掌握消解规则及其性质l 会用消解算法判断公式的可满足性会用消解算法判断公式的可满足性70练习练习1:概念概念1. 设设A与与B为含为含n个命题变项的公式，判断下列命题是个命题变项的公式，判断下列命题是否为真？否为真？(1) AB当且仅当当且仅当A与与B有相同的主析取范式有相同的主析取范式(2) 若若A为重言式，则为重言式，则A的主合取范式为的主合取范式为0(3) 若若A为矛盾式，则为矛盾式，则A的主析取范式为的主析取范式为1(4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公

37、式说明说明:(2) 重言式的主合取范式不含任何极大项，为重言式的主合取范式不含任何极大项，为1. (3) 矛盾式的主析取范式不含任何极小项矛盾式的主析取范式不含任何极小项, 为为0. (4) , 不是完备集，如矛盾式不能写成不是完备集，如矛盾式不能写成 , 中的公式中的公式. (5) , 是完备集是完备集. 真真假假假假假假真真71练习练习2: 判断公式类型判断公式类型解解 用等值演算法求主范式用等值演算法求主范式 (pq)( qp) ( p q) (qp) (pq) (qp) (pq) ( p q) (p q) ( pq) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式主析取范式

38、 1 主合取范式主合取范式2. 判断下列公式的类型判断下列公式的类型: (1) (pq)( qp)重言式重言式72练习题练习题2(续续)解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式(2) (pq) q矛盾式矛盾式73解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式(3) (pq)p练习练习2(续续)非重言式的可满足式非重言式的可满足式

39、74练习练习3：求公式的主范式求公式的主范式3已知命题公式已知命题公式A中含中含3个命题变项个命题变项p, q, r，并知道它的成真，并知道它的成真赋值为赋值为001, 010, 111, 求求A的主析取范式和主合取范式，及的主析取范式和主合取范式，及A对应的真值函数对应的真值函数.解解 A的主析取范式为的主析取范式为m1 m2 m7A的主合取范式为的主合取范式为M0 M3 M4 M5 M6 p q r F p q r F0 0 0 0 1 0 0 00 0 1 1 1 0 1 00 1 0 1 1 1 0 00 1 1 0 1 1 1 175练习练习4：联结词完备集联结词完备集4将将A =

40、(pq) r改写成下述各联结词集中的公改写成下述各联结词集中的公式式: (1) , , (2) , (3) , (4) , (5) (6) 解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)76练习练习4 解答解答 (4) (pq) r ( (pq)r) (pq)r) (5) (pq) r (p q) r (p q) r (p q) r) (p q) r) (p q) r) (6) (pq) r ( pq) r ( ( pq)r) ( pq)r (p p) (q q) (r r) 说明：答案不惟一说明：答案不惟一77练习练习5：应用题：应用题5. 某公司要从赵、钱、孙、李、周五名新毕业的大某公司要从赵、钱、孙、李、周五名新毕业的大学生中选学生中选派一些人出国学习派一些人出国学习. 选派必须满足以下条件：选派必须满足以下条件：(1) 若赵去，钱也去若赵去，钱也去.(2) 李、周两人中至少有一人去李、周两人中至少有一人去(3) 钱、孙两人中去且仅去一人钱、孙两人中去且仅去一人.(4) 孙、李两人同去或同不去孙、李两人同去或同不去.(5) 若周去，则赵、钱也去若周去，则赵、钱也去. 用等值演算法分析该公司如何选派他们出国？用等值演算法分析该公司如何选派他们出国？