x本科数理逻辑-命题3-10.ppt

复 习1、命题公式的等值演算以等值定律为基础利用置换规则（等值代换）及其等值的性质得到其他的等值式2、等值演算的应用1）判断二个命题公式是否等值2）利用等值演算可确定公式的类型若能得到 A ⇔１则可得到公式A为重言式 A ⇔０ 则可得到公式A为矛盾式3）利用等值演算还可以化简一个命题公式3. 命题公式的范式1）文字：命题变项及其否定统称作文字．2）简单析取式：仅由有限个文字构成的析 取式3）简单合取式：仅由有限个文字构成的合 取式它们均表示不统一4) 简单析取式和简单合取式的性质：一个简单析取式是重言式 当且仅当它同时含某个命 题变项及它的否定式． 一个简单合取式是矛盾式 当且仅当它同时含某个命 题变项及它的否定式．5）由有限个简单合取式构成的析取式称为析取范式由有限个简单析取式构成的合取式称为合取范式． 6)性质一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 7)范式存在定理任一命题公式都存在着与之等值的析取范式与合取范式． 8)总可以通过以下方法步骤：1．消去联结词 ↔ 、→ (若存在)．2．否定号的消去(利用双重否定律)或内移(利用德摩根律)．3．利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律 9）与公式等值的析取范式和合取范式表示是不唯一的 例 ┑p→ ┑(p →q) ⇔⇔ p ∨ ┑(┑p ∨ q) ⇔⇔ p ∨ （p ∧ ┑q ） 析取范式 ⇔⇔ （p ∧（q ∨┑q））∨ （p ∧ ┑q） ⇔⇔ (p ∧q) ∨ (p ∧┑q) 析取范式 ⇔⇔ p 析取范式 ⇔⇔ (p ∨ p) ∧ ( p ∨┑q） ⇔⇔ p ∧ ( p ∨┑q） 合取范式 ⇔⇔ ( p ∨(q ∧┑q) ) ∧ ( p ∨┑q） ⇔⇔ ( p∨q ) ∧ (p ∨┑q) 合取范式⇔⇔ p 合取范式再如 ┑p ∨ q 既是p → q 的析取范式又是它的的合取范式公式的范式不唯一则对于将公式按等值进行分类的利用价值就不高 三、主析取范式析取范式和合取范式的不唯一性主要是由于：构成范式的基本元素：简单析取式和简单合取式的表示不唯一性将其约束为极小项和极大项1、极小项 在含有n个命题变项的简单合取式中，若每个命题变项和它的否定式不同时 出现，而二者之一必出现且仅出现一次，称这样的简单合取式极小项。

极小项与所含变元的个数有关含二个变元p,q 的极小项：两个变元p,q的所有极小项为 ┑p∧ ┑q 、 ┑p∧q、 p∧┑q、 p∧q 按字母标记为 m0 m1 m2 m3 相应极小项的成真赋值为 (0,0)、 （0，1）、 （1，0）、 （1，1）三个变元的所有极小项为：┑p∧┑q∧┑r、 ┑p∧┑q∧r、 ┑p∧q∧┑r、 ┑p∧q∧r 、 按字母排序为 m0、 m1、 m2、 m3 、 相应极小项的成真赋值为 (0,0，0)、 （0，0,1）、 （0,1，0）、 （0,1，1）p∧┑q∧┑r、 p∧┑q∧r、 p∧q∧┑r、 p∧q∧rm4、 m5、 m6、 m7(1,0，0)、 （1，0,1）、 （1,1，0）、 （ 1,1，1）2） n个变元的所有极小项共有 2n个(┐p→q)∧（p → r)⇔ (┐p∧q) ∨ (p ∧r ) ∨(q ∧ r) 仅是析取范式不是主析取范式 （简单合取式不是极小项，三个变元）2、主析取范式1）定义 设由n个命题变项构成的析取范式中所有的简单合 取式都是极小项，则称该析取范式为主析取范式。

例 （p→q）↔r ⇔ (p∧┐q∧┐r)∨(┐p∧ r)∨(q ∧ r)2）主析取范式的唯一性定理2．5 任何命题公式都存在着与之等值的主析取范 式，并且是惟一的a)析取范式的存在性b) 简单合取化为极小项－得到存在性c) 通过真值表得到唯一性3)公式的主析取范式中的极小项所对应的赋值均为成真赋值, 也是该公式的全部成真赋值(由真值表得出）公式的主析取范式包含全部极小项,则该公式为重言式(┐p∧q) ∨ r p ∨ q∨ r 仅是析取范式，不是主析取范式 （简单合取式不是极小项，三个变元）3、主析取范式的确定方法：（1）等值演算法 (┐p→q)∧（p → r)⇔⇔ (┐p∧q) ∨ (p ∧r ) ∨(q ∧ r) (p ↔ q) → ra)先确定公式的析取范式b)将简单合取式化为极小项（不断合取所缺变元的永真式）c)将相同极小项去掉 （2）真值表法列出公式的真值表 p ∨ q ∨ r将真值表中真值为真 的相应赋值所对应的极小项进行析取（3）利用主析取范式与主合取范式的关系若已知公式A的主析取范式首先写出 ┑A的主析取范式对 ┑A的主析取范式取否定可得到A的主合取范式4、主析取范式的应用a.确定公式的成真赋值b.判断公式的类型若公式的主析取范式包含所含变元的全部极小项则 该公式为永真式若公式的主析取范式包含所含变元的若干极小项则 该公式为可满足式若公式的主析取范式不包含所含变元的任何极小项 则该公式为永假式c.判断两个公式是否等值前面所介绍的： 二．析取范式和合取范式 1)由有限个简单析取式构成的合取式称为合取范式．p∨ ┑q ∨ r ┐p ∨ q p∧┐q (┐p∨q) ∧ ┐q ∧ p （┐p ∨ q）∧（┐q∨┐p∨r）∧┐q 均是合取范式． 2)性质：合取范式是重言式当且仅当它的每个简单析取式都是重言式3）范式存在定理任一命题公式都存在着与之等值的合取范式． 总可以通过以下方法步骤： 1．消去联结词 ↔ → (若存在)． 2．否定号的消去(利用双重否定律)或内移(利用德摩根律)． 3．利用分配律：利用∧对∨的分配律求合取范式，∨对∧的分配律 公式的合取范式表示不唯一 （主要是由于构成合取范式中的简单析取式表示不唯一）将简单析取式给予限制为极大项四、主合取范式 –极大项：在含有n个命题变项的简单析取式中，若每个命题变项和它 的否定式不同时出现，而二者之一必出现且仅出现一次，称这样的 简单析取式极大项。

2.极大项与所含变元的个数有关 两个变元p,q的所有极大项为 p∨q 、 p∨┑q、 ┑p∨q、 ┑p∨ ┑q 按字母排序为 M0、 M1、 M2、 M3相应极大项的成真假值为 (0,0)、 （0，1）、（1，0）、（1，1 ）三个变元的所有极大项为： p∨q∨r、 p∨q∨┑r、 p∨┑q∨r、 p∨┑q∨┑r 、 M0(0,0,0)、 M1(0,0,1)、 M2(0,1,0)、 M3(0,1,1) 、┑p∨q∨r、 ┑p∨q∨┑r、 ┑p∨┑q∨r、 ┑p∨┑q∨┑r M4(1,0,0)、 M5(1,0,1)、 M6(1,1,0)、 M7(1,1,1) 3.n个变元的所有极大项共有 2n 4.主合取范式1）定义 设由n个命题变项构成的合取范式中所有的简单合取式都 是极大项，则称该合取范式为主合取范式例 ( p → q) ↔ r ⇔ (p ∨ r) ∧(┐ q ∨ r) ∧(┐ p ∨ q ∨ ┐ r)先确定相应的合取范式 ，再将简单析取式化为极大项（通过析取 F） 注：该式的极大项所对应的赋值均为该公式的成假赋值，也是该公式的全部成假赋值（可从真值表得出）3、主合取范式的确定方法：（1）等值演算法 例：p →（p ∨ q )a)先确定公式的合取范式b)将简单析取式化为极大项（不断析取所缺变元的永假式）c)将相同极大项去掉（2）真值表法列出公式的真值表将真值表中真值为假的相应赋值所对应的极大项进行合取（3）利用主析取范式与主合取范式的关系若已知公式A的主析取范式首先写出 ┑A的主析取范式(从全部极小项去掉A式包含的极小项得 到）对 ┑A的主析取范式取否定可得到A的主合取范式 例：（p ∨ q) → r 确定主析取范式和主合取范式4、主合取范式的唯一性 （可从真值表的唯一性得到）定理2．5 任何命题公式都存在着与之等值的主合取范式，并且是惟一的证明：1）合取范式的存在性2）将合取范式中的简单合取式化为极大项即可得到存在性唯一性可从极大项的不同得出其成假赋值的不同得到 5、应用a. 确定公式的全部成假赋值.A(p,q) ⇔ M0 ∧M3 ⇔ (p ∨ q) ∧( ┐p ∨ ┐q) 全部成假赋值为 （0，0）与（1，1）b.判断公式的类型若公式的主合取范式包含所含变元的全部极大项则该公式为永假式若公式的主合取范式包含所含变元的若干极大项则该公式为可满足式c.判断两个公式是否等值例 判断（p → q ) → r 与 (p ∧ q) →r 是否等值 （p → q ) → r ⇔ m1 ∨ m3 ∨ m4 ∨ m5 ∨ m7(p ∧ q) →r ⇔ m0 ∨ m1 ∨ m2 ∨ m3 ∨ m4 ∨ m5 ∨ m7 故不等值2.3 联接词的完备集 一、联接词的扩充 1) 异或联接词 ∇P ∇ q ⇔ (p∧┓ q ) ∨(┓p∧ q ) 2) 与非联接词定义 设p、q为两个命题，复合命题“p与q的否定式”称 作p，q的与非式，记作p↑q ，符号 ↑)称作与非联结词， p↑q为真当且仅当p与q不同时为真。

p↑q ⇔ ┓(p∧ q)3) 或非联接词 定义 设p、q为两个命题，复合命题“p或q的否定式”称 作p，q的或非式，记作 p ↓ q 符号 ↓ 或非联结词p ↓ q为真当且仅当p与q同时为假 p ↓ q ⇔ ┓(p∨ q)4) 几种连接词的关系 （1) ┓p ⇔ ┓(p∧ p ) ⇔ p↑p ┓p ⇔ ┓(p∨ p ) ⇔ p↓p(2） p∧ q ⇔ ┓┓(p∧ q ) ⇔ ┓( p↑p ) ⇔ ( p↑p ) ↑ ( p↑p )（3）(p∨ q) ⇔ ┓┓(p∨ q) ⇔ ┓(p ↓ q) ⇔ (p↓q)↓(p↓q)（4）p∧ q ⇔ ┓┓(p∧ q ) ⇔ ┓(┓ p∨┓q ) ⇔ (┓p ↓┓q ) （5）(p∨ q) ⇔ ┓┓(p∨ q) ⇔ ┓(┓p ∧┓ q) ⇔ (p↓p) ↑(q↓q)（6）(a) ┐(P↑Q ) ⇔ ┐P↓┐Q(b) ┐(P↓Q ) ⇔ ┐P↑┐Q二、联接词的完备集 1、定义 设S是一个联结词集合，如果任何n(n≥1)元公式 都可以由仅含S中的联结词构成的等值公式表示，则称S 是联结词完备集．(极小联接词完备集） 2. 可验证 s1={ ┓、∨、 ∧} s2 = { ┓、 ∨ } 为联接词完备集(极小)s3 = { ┓、 ∧ }为联接词完备集(极小)s4 = { ┓、→ }为联接词完备集(极小)特别地 s5 = { ↑ } 为联接词完备集(极小)s6 = { ↓ } 为联接词完备集(极小) 作业： P38 5、(1) (3) 6、(1) (3) 7、 9、(2) 10、（2）12、 13 18、(1) （3） 19、(2) 。