2-命题公式类型-等值式-范式

离散数学语句的形式化我和他既是兄弟又是同学： p∧q p:我和他是兄弟， q:我和他是同学狗急跳墙： p→q p:狗急了， q:狗跳墙如果他不来那么是生病了或者不在本地： ¬p→(q ∨¬r) p:他来， q:他生病， r:他在本地无论是否下雨，我都去上学 (p→q) ∧(¬p→q) 或者 (p∧q)∨(¬p∧q) 或者 q p:天下雨， q:我去上学2语句的形式化要善于确定原子命题，如兄弟这个概念就无需进一步拆分；要善于识别自然语言中的联结词；对于涉及多个对象进行否定的否定词位置要准确；有时候语句的形式化结果不是唯一的，可能具有不同形式，但是逻辑上是等价的3命题 + 逻辑联结词 = ？4命题公式 命题常元（ proposition constants）表示具体命题及表示常命题的 p, q, r, s等和 t, f 命题变元（ proposition variables）以“真，假”或者“ 1， 0”为取值范围的变量仍用 p, q, r, s等表示 命题公式（ proposition formula）由命题常元、变元和联结词组成的形式更为复杂的命题5命题公式的归纳定义 命题公式（ proposition formula ）定义命题常元和命题变元是命题公式，称作原子公式如果 A,B是命题公式，那么 (¬A), (A∧B), (A∨B), (A→B), (A↔ B)也是命题公式只有 有限步 引用上述两条所组成的符号串是命题公式 命题公式简称做公式，采用大写 A,B,C等表示6复杂的命题公式包含太多括号 命题公式例子(¬(p→(q ∧r)))是命题公式(qp), p→r, (p 1∧(p2∧… 都不是命题公式 简化公式的约定公式最外层的括号一律可以省略约定逻辑联结词的优先级7逻辑联结词优先级 “先乘除后加减”联结词 {¬,∧,∨,→,↔ }中， ¬是一元联结词，其它都是连接两个命题的二元联结词我们定义优先级为： ¬,(∧,∨),→,↔除非有括号，否则按照优先级从高到低，从左到右的次序结合 p→q ∧r→s 等同于 (p→(q ∧r))→s8保留一些括号可以提高公式的可读性运算结果 真值函数（ truth function）如果将联结词看作逻辑运算符，那么包含命题变元 p1, p2, …p n的公式 A可以看作是 p1, p2, …p n的真值函数 指派（赋值 assignments）对任意给定的 p1, p2, …p n的一种取值状况，称为指派或者赋值用希腊字母 α, β等表示对于每个赋值，公式 A均有一个确定的真值9真值表 成真赋值和成假赋值当公式 A对赋值 α为真时，称 α是 A的成真赋值，或者 α弄真A，记做 α(A)=1反之，称 α是 A的成假赋值，或者 α弄假 A ，记做 α(A)=0 真值表对于所有可能的赋值，公式 A的真值可以用真值表来描述当 A(p1, p2, …p n)中有 k个联结词时，公式 A的真值表应为2n行、 k+n列。

100 0 0 0 1 00 0 1 0 0 10 1 0 1 0 10 1 1 1 1 01 0 0 1 0 11 0 1 1 1 11 1 0 1 0 11 1 1 1 1 1命题逻辑等值演算12命题公式的类型等值基本等值式等值演算置换规则13命题公式的类型重言式（永真式） tautology 命题变元的所有赋值都是命题公式的成真赋值矛盾式（永假式、不可满足式） contradiction 命题变元的所有赋值都是命题公式的成假赋值可满足式 (contingency) 命题公式至少有一个成真赋值 性质永真式是可满足式，但非永真式不一定是永假式如果命题公式 A是永真式，则 ¬A是永假式，反之亦然14命题公式的类型 例子：对于任何公式 AA∨¬A是重言式（排中律）A∧¬A是矛盾式（矛盾律） 证明 (p∨q)∧¬p→q 是重言式p q p∨q ¬p (p∨q)∧¬p (p∨q)∧¬p→q0 0 0 1 0 10 1 1 1 1 11 0 1 0 0 11 1 1 0 0 115等值A与 B等值： AB是重言式用 等值式 表示等值： AB例： (pq)  ((pq) (rr))16用真值表验证p(qr)  (p q) rp(qr) (pq) r17基本等值式双重否定律 : AA等幂律 ： AAA, AAA交换律 : ABBA, ABBA结合律 : (AB)CA(BC)(AB)CA(BC)分配律 : A(BC)(AB)(AC)A(BC) (AB)(AC)18基本等值式 (续 )德 ·摩根律 : (AB)AB(AB)AB19基本等值式 (续 )德 ·摩根律 : (AB)AB(AB)AB吸收律 : A(AB)A, A(AB)A零律 : A11, A00 同一律 : A0A, A1A排中律 : AA1矛盾律 : AA020基本等值式 (续 )蕴涵等值式 : ABAB等价等值式 : AB(AB)(BA)假言易位 : ABBA等价否定等值式 : ABAB归谬论 : (AB)(AB) AA↔ B  (A∧B)∨(¬A∧¬B)注意 : A,B,C代表任意的命题公式牢记这些等值式是继续学习的基础21等值演算与置换规则等值演算 :由已知的等值式推演出新的等值式的过程置换规则 ：若 AB, 则 (B)(A)等值演算的基础：(1) 等值关系的性质：自反 、 对称 、 传递(2) 基本的等值式(3) 置换规则22应用举例 —— 证明两个公式等值例 1 证明 p(qr)  (pq)r证 p(qr)p(qr) （ 蕴涵等值式 ， 置换规则 ）(pq)r （ 结合律 ， 置换规则 ）(pq)r （ 德 摩根律 ， 置换规则 ）(pq) r （ 蕴涵等值式 ， 置换规则 ）说明 :也可以从右边开始演算 （ 请做一遍 ）因为每一步都用置换规则 ， 故可不写出熟练后，基本等值式也可以不写出23应用举例 —— 证明两个公式不等值例 2 证明 : p(qr) (pq) r 用等值演算不能直接证明两个公式不等值 基本思想：找到一个赋值使一个成真，另一个成假 .24应用举例 —— 证明两个公式不等值例 2 证明 : p(qr) (pq) r 真值表法 —— 不能承受变量增多之苦！ 观察赋值法容易看出 000, 010等是左边的的成真赋值，是右边的成假赋值 —— 不容易时候怎么办？ 用等值演算先化简两个公式，再用真值表或观察法25应用举例 —— 判断公式类型例 3 用等值演算法判断下列公式的类型(1) q(pq)解 q(pq) q(pq) （ 蕴涵等值式 ） q(pq) （ 德 摩根律 ） p(qq) （ 交换律 ， 结合律 ） p0 （ 矛盾律 ） 0 （ 零律 ）由最后一步可知，该式为矛盾式 .26例 3 (续 )(2) (pq)(qp)解 (pq)(qp) (pq)(qp) （ 蕴涵等值式 ） (pq)(pq) （ 交换律 ） 1由最后一步可知 ， 该式为重言式 .问：最后一步为什么等值于 1？27例 3 (续 )(3) ((pq)(pq))r)解 ((pq)(pq))r) (p(qq))r （ 分配律 ） p1r （ 排中律 ） pr （ 同一律 ）这不是矛盾式 ， 也不是重言式 ， 而是非重言式的可满足式 .如 101是它的成真赋值 ,000是它的成假赋值 .2829总结： A为矛盾式当且仅当 A0A为重言式当且仅当 A1说明：演算步骤不惟一 ,应尽量使演算短些范 式30析取范式与合取范式主析取范式与主合取范式31范式的基本单元 文字命题变项命题变项的否定32简单析取式简单析取式 :有限个文字构成的析取式 pq pq pqr…33简单合取式简单合取式 :有限个文字构成的合取式 pq pq pqr…34析取范式 VS.合取范式析取范式 :由有限个简单合取式组成的析取式 A1A2 Ar其中 A1,A2, ,Ar是 简单合取式合取范式 :由有限个简单析取式组成的合取式 A1A2 Ar其中 A1,A2, ,Ar是 简单析取式35求公式 A的析取范式 /合取范式公式 A的析取范式 : 与 A等值的析取范式公式 A的合取范式 : 与 A等值的合取范式36特殊情况单 个文 字既 是简单析取 式又 是简单合取 式pqr, pqr既 是析取范式，又是合取范 式既是析取范式，又是合取范式为什么 ?37范式一定存在吗？定理 任何命题公式都存在着与之等值的析取范式与合取范式 .38怎么求？求公 式 A的范式的步骤：(1) 消去 A中的 , （ 若存在 ）(2) 否定联结词 的内移或消去(3) 使用分配律对 分配 （ 析取范式 ）对 分配 （ 合取范式 ）39求公式的范式举例例 求下列公式的析取范式与合取范式(1) A=(pq)r解 (pq)r (pq)r （ 消去 ）pqr （ 结合律 ）这既是 A的析取范式 （ 由 3个简单合取式组成的析取式 ） ，又是 A的合取范式 （ 由一个简单析取式组成的合取式 ）40求公式的范式举例 (续 )(2) B=(pq)r解 (pq)r  (pq)r （ 消去第一个 ）(pq)r （ 消去第二个 ） (pq)r （ 否定号内移 —— 德 摩根律 ）这一步已为析取范式 （ 两个简单合取式构成 ）继续： (pq)r (pr)(qr) （ 对 分配律 ）这一步得到合取范式（由两个简单析取式构成）41范式的唯一性问题 公式的范式存在，但不唯一 （不够规范） 能否进一步规范析取范式 / 合取范式 要解决这个问题，不得不引入极 小 项与极大项42极小项与极大项 极小项 简单合取式 每个命题变项均以文字的形式出现且仅出现一次 极大项 简单析取式 每个命题变项均以文字的形式出现且仅出现一次43有多少个这样的极小项 /极大项？ n个命题变项产生 2n个极小项 2n个极大项 各 个极小项 （ 极大项 ） 均互不等值44极小项的十进制表示法 在极小项中 文字 均按下标或字母 顺序排列 用 mi表示 第 i个 极小项 ， 其中 i是该极小项 成真赋值 的十进制表示 . 在极大项中 文字 均按下标或字母 顺序排列 用 Mi表示 第 i个 极大项 ， 其中 i是该极大项 成假赋值 的十进制表示 , mi与 Mi的关系 : mi Mi Mi mi45极小项与极大项 (续 )由 p, q两个命题变项形成的极小项与极大项公式 成真赋值 名称 公式 成假赋值 名称p qp。