数理逻辑
§1.1命题 §1.2.重言式 §1.3.范式 §1.4.联结词的扩充和归约 §1.5.推理规则和证明方法 §1.6.谓词和量词 §1.7.谓词演算的永真公式 §1.8.谓词演算的推理规则 1 §1.2.1 重言式 命题公式的永真式,永假式和可满 足式 举最简单例子,如左图真值表 P PP∨ PP∧ P FT T F TF T F 2 』完全指派设公式A中有n个不同的原子变元P1,…Pn,(n为 正整数).该变元组的任意一组确定的值(u1,…un)称为A关于 P1,…Pn的一个完全指派, 其中ui或为T,或为F. 』部分指派如果对于A中部分变元赋以确定值,其余变元没 有赋以确定的值, 则这样的一组值称为公式A的关于该变元 组的部分指派. 』成真指派凡使公式A取真的指派称为A的成真指派. §1.2.1 重言式(永真式) 』永真式如果一个命题公式的所有完全指派均为成真指派,则该公式 称为永真式. 』永假式如果一个命题公式的所有完全指派均为成假指派,则该公式 称为永假式. 』可满足式既不是永真式,又不是永假式,则称此命题公式是可满足 式. 为什么需要考虑重言式的情况 1. 永真式的否定为永假式( T F), 永假式的否定为永真式 ( F T). 2.二个永真式的析取,合取,蕴含,等价均为永真式. 3.永真式中存在许多有用的恒等式和永真蕴含式. 3 §1.2.2.恒等式 恒等式 如果对两个公式A, B不论作何种指派,它们真值均相同,则称A, B是逻辑等价的, 亦说A等价于B. 并记作:A B 4 P Q P∨ PQ ∨ Q F F T T F T T T T F T T T T T T 例1 P∨ P Q∨ Q 例2 判断公式A: (P∨ Q)∧(P∨Q)与B: (P∨ R) ∧(P∨R)是否等价. §1.2.2.恒等式 定理1.命题公式A B的充要条件是A B为永真式. 说明: 为等价关系符, A B表示A和B有等价关系; A B不为命题公式,表示一永真式. 为联结词(运算符), A, B为命题公式,则(A B)也为 一命题公式. 5 由定理可知:A A(自反性) 若A B, 则B A(对称性) 若A B, B C,则A C(传递性) 例1 证明 P P; P →Q P ∨Q §1.2.2.恒等式 下面列出15组等价公式 (1) 双重否定律 P P (2) 等幂律P∨P P;P ∧P P (3) 交换律P∨Q R∨P; P ∧Q Q ∧P; P Q Q P (4) 结合律(P∨Q)∨R P∨(Q∨R); (P ∧Q) ∧R P ∧(Q ∧R); (P Q) R P ( Q R) 6 §1.2.2.恒等式 (5) 分配律 P ∧(Q∨R) (P ∧Q) ∨( P ∧R) P ∨(Q ∧R) ( P ∨Q) ∧( P ∨R) (6) 德.摩根律 (P ∨Q) P ∧ Q (P ∧Q) P ∨ Q (7) 吸收律 P ∨(P ∧Q) P P ∧(P∨Q) P 7 §1.2.2.恒等式 (8) 蕴含律P →Q P ∨Q (9) 等价律P Q (P →Q) ∧( Q →P) (10)零律P ∨T T;P ∧F F (11)同一律P ∨F P;P ∧T P (12)互补律P∨ P T;P ∧ P F (13)输出律P ∧Q →R P →(Q →R) (14)归缪律(P →Q) ∧(P → Q) P (15)逆反律P →Q Q → P 8 §1.2.2.恒等式 说明∨证明上述15组等价公式的方法可用真值表法,把 改为 所得的命题公式为永真式, 则 成立. ∨∧,∨, 均满足结合律,则在单一用∧,∨, 联结词组成的 命题公式中, 括号可以省去. ∨每个等价模式实际给出了无穷多个同类型的具体的命题公 式. 9 例如 (P ∨Q) ( P ∧ Q), ((P ∧Q) ∨(R ∧S)) ( (P ∨Q) ∧ (R ∨S), ((P→Q) ∨ R) ( (P →Q) ∧ R) §1.2.3.永真蕴含式 永真蕴含式命题公式A称为永真蕴含命题公式B,当且仅当A→B是一 个永真式,记作: A B. 说明:A B读作A永真蕴含B,A蕴含B,A 能推得B 是关系符, A B不为命题公式. 证明方法, 真值表法, 由定义出发给出证明. 例:证明:P P∨Q; P ∧Q P 10 PQ P→(P∨Q) (P∧Q)→P F F F T F F T F F T F T T F T F T F T T T F T T T T T T T T T T §1.2.3.永真蕴含式 下面给出常用的永真蕴含式 I1 P P∨Q( Q P ∨Q)加法式 I2P ∧Q P( P ∧Q Q)简化式 I3 P∧(P →Q) Q假言推理 I4 ( P →Q ) ∧ Q P拒取式 I5 P ∧( P∨Q ) Q析取三段论 I6 (P →Q) ∧(Q →R ) ( P →R)前提三段论 I7 (P →Q) ∧(R →S) (P ∧R →Q ∧S) I8 (P Q ) ∧( Q R) ( P R ) I9 P P →Q善意的推定 11 §1.2.3.永真蕴含式 I10 Q P→Q I11 (P →Q) P I12 (P→Q) Q I13 (P∨Q)∧( P →R)∧(Q→R) R构造性两难推理 PQP→Q FFT FTT TFF TTT 12 §1.2.3.永真蕴含式 13 证明上述永真蕴含式的方法有下述三种: (1) 把 关系符改为→联结词,证明它为永真式. (a) 真值表法 (b) 命题演算法 (2) 找出使条件命题前件为T的所有真值指派,试看能否导 致后件均为T,若为T,则永真蕴含关系成立(肯定前件,推出 后件为真). (3) 找出使条件命题的后件均为F的所有真值指派,试看前件 的所有真值是否为F,若是则蕴含成立.(否定后件,推出前件 为假) §1.2.3.永真蕴含式 例1P ∧( P→Q) Q 例2 Q ∧(P→Q) P 例3 (P →Q) ∧(R →S) (P ∧R →Q ∧S) 例4 (P →Q) ∧(R →S) (P ∧R →Q ∧S) 14 §1.2.3.永真蕴含式 定理1 设A,B是二个命题公式,A B的充分必要条件是 A B 且B A. (此定理在 和 之间建立了相应的联系) 定理2 给定命题公式A, B, C,若A B,且B C,则A C. 推论若A B1, B1 B2…Bm B, 则A B 定理3给定命题公式A, B, C, 若A B, A C, 则A ( B ∧C) 15 §1.2.3.永真蕴含式 H1, H2 ,…,Hm,Q均为命题公式, 若(H1 ∧H2∧…Hm) C,则称H1, H2,…, Hm,共同蕴含C,并记作H1, H2 ,…,Hm C. 定理4 若(H1 ∧H2∧…Hm), H C, 则( H1 ∧H2 ∧…Hm) ( H →C). (CP 规则) 16 §1.2.3.永真蕴含式 讨论一下永真式, 可得出以下三个结论: ∨若一个命题公式等价于另一个永真式,则该公式一定 为永真式. ∨若一个永真的命题公式永真蕴含另一个命题公式,则 此命题公式一定也为永真式. ∨若一个永假的命题公式P永真蕴含一个命题公式Q,则 公式Q可能是永真式,永假式或可满足的. 17 §1.2.5 代入规则和替换规则 代换实例给定一命题公式B, 其中P1, P2 …Pn是B中的原子命题 变元. 若 ∨用某些命题公式代换B中的原子命题变元Pi ∨用命题公式Ai代换Pi, 则必须用Ai代换B中的所有Pi 由此而得到的新命题公式A称为命题公式B的代换实例. 代入规则重言式中的某个命题变元出现的每一处均代入同一公 式后, 所得的仍是重言式. 18 §1.2.5 代入规则和替换规则 讨论∨用命题公式只能代入原子命题变元,而不能去代换分 子命题公式; ∨要用命题公式同时代入同一个原子命题变元; ∨一个命题公式的代换实例有许多个,但不一定都等价 于原来的命题公式; ∨永真式的代换实例仍为永真式, 反之代换实例为永真 式时, 则不能断定原公式也一定是永真式. 19 §1.2.5 代入规则和替换规则 例1 B: P →( Q ∧P ) 若用(R S)代换B中的P, 得A: (R S) →( Q ∧(R S))是B的代换实例 而A': (R S) →( Q ∧P) 不是B的代换实例. 例2 P → Q的代换实例有: (R ∧ S)→ M, (R∧ S) →P, Q → ( P→ Q)等 所以,一个命题公式的代换实例有无限个. 20 §1.2.5 代入规则和替换规则 给定一命题公式A, A'是A的任何部分.若A'也是一命题 公式, 则称A'是A的子命题公式. 例1 A (P∨Q) →( Q ∨( R ∧ S) ) 其子命题公式有: P, Q, R, S, (P ∨Q), ( R ∧ S ), (Q∨( R ∧ S) ), (P∨Q)→( Q ∨( R ∧ S))等. 替换规则给定一命题公式A, A'是A的子公式.设B' 是一命题公式,若A' B',并用B'取代A中的A', 从而生 成一新的命题公式B,则A B. 21 §1.2.5 代入规则和替换规则 应用代入规则和替换规则和已有的重言式可以得出新的 重言式. 例1 证明: P→(Q→R) ( P ∧Q)→R 例2 证明: ((P∨Q)∧ ( P∧( Q∨ R))) ∨( P∧ Q) ∨( P ∧ R) 为一永真式 课本P11-例2 22 §1.2.6 对偶原理 对偶式给定二个命题公式A和A*, A和A*中仅有∧,∨, . 若用∧代换∨, 用∨代换∧, 用T代换F, 用F代换T, 则其中一个 命题公式可由另一个命题公式得来, 称A和A*是互为对偶的,而 联结词∧和∨也是互为对偶的. 例: 写出下列命题公式的对偶式: A : P∨(Q ∧R) 对偶式A*: P ∧( Q∨R) 23 §1.2.6 对偶原理 讨论定义 ∨若命题公式中有联结词→, 则必须把化成由联结词∧, ∨组成 的等价的命题公式,然后求它的对偶式 例求(P→Q)∧(P→R)的对偶式 ( P ∨Q) ∧( P ∨R) 对偶式: ( P ∧Q) ∨( P ∧R) ∨在写对偶式时, 原命题公式中括号不能省去, 必须按优先级的次 序画上括号,并在求其对偶式时仍将保留括号. 例(P∧Q)∨R对偶式写成(P∨Q)∧R, 而不能写成P∨Q∧R 24 §1.2.6 对偶原理 设A和A*为对偶式P1, P2…Pn是出现在A和A*中的所有原子命题变元, 于是有: A(P1,P2…Pn) A*( P1, P2 … Pn) ——(1) A( P1, P2… Pn) A*(P1, P2 …Pn)——(2) 证明: 由德.摩根定理 ( P∨Q ) P ∧ Q——(1) ( P ∧Q ) P ∨ Q ——(2) 对于具体的命题公式,通过连续使用德.摩根定律可证. 德.摩根推广原理 不难看出, 一个命题公式的否定等价于它的对偶式, 且把变元的否定 代替每一个变元. 25 §1.2.6 对偶原理 例:设A(P, Q, R) P ∧ (Q∨R), 验证上述定理. 证明: (1) A( P, Q, R) P ∧ Q ∧ R A( P,Q, R) P∨Q∨R A*(P, Q, R) P∨ Q∨ R A*( P, Q, R) P∨Q∨R (2) A( P, Q, R) P ∧Q ∧R A*(P, Q, R) ( P∨Q∨ R) P ∧Q ∧R 有A( P, Q, R) A*(P, Q, R) 26 §1.2.6 对偶原理 若A B, 且A, B为命题变元P1, P2…Pn及联接词∧,∨, 构成的公 式,则A* B*成立. 若A B, 且A, B为命题变元P1, P2…Pn及联接词∧,∨, 构成的公 式,则B* A*成立. 若P∨F P , 则P ∧T P 若P∨T T, 则P ∧F F 作业:习题1.2 P11-154, 7, 9 27 第一章数理逻辑 §1.1命题 §1.2.重言式 §1.3.范式 §1.4.联结词的扩充和归约 §1.5.推理规则和证明方法 §1.6.谓词和量词 §1.7.谓词演算的永真公式 §1.8.谓词演算的推理规则 28 1.3.范式 范式命题公式的一种标准表示形式称为范式. 一些定义 ∨设命题变元为P, Q, R,则P∨Q∨R的析取式称为和,P∧Q∧R的合 取式称为积. ∨命题公式的变元和变元的否定之积称为基本积,而变元和变元的 否定之和称为基本和. 例设P,Q为二个命题变元, 则P∨P, Q∨Q, P∨Q, Q∨ P, P∨Q, P∨ Q称为基本和; P∧P,Q∧Q, P∧Q, Q∧ P, P∧Q, P∧ Q称为基本积. 29 ∨基本和或基本积中的子公式,称为此基本积(和)的因子. 例: Q∧P∧ P的因子有: Q, P, P, Q∧P,P∧ P 1.3.范式 定理1 一个基本积必定是永假式的充分必要条件是:至少包含一 对因子, 其中一个因子是另一个的否定. 定理2 一个基本和必定为永真式的充要条件是,它至少包含一对 因子,其中一个因子是另一个的否定. 析取范式与给定命题公式等价的一个公式,如果是由基本积之和组成, 则称为命题公式的析取范式. 并记为P P1∨P2 ∨…∨Pn(n∈I+) 其中P1,P2…Pn均为基本积. 30 1.3.范式 合取范式与给定命题公式等价的一个公式,如果它是由基本 和之积所组成,则称它是给定命题公式的合取范式. 并表示成:Q Q1∧Q2∧…∧Qn,(n∈I+),其中Q1, Q2, … Qn均为基本和. 31 讨论定义: ∨一个命题公式的析(合)取范式不是唯一的, 但同一命题 公式的析(合)取范式一定是等价的. ∨若一个命题公式的析(合)取范式中每一个基本积(和)均 为永假(真)式, 则该公式也一定为永假式. 1.3 范式 析取范式求解方法可按下列三步(或四步)进行: 1. 利用等价公式:化去"→"," "联结词,把命题公式变为与 其等价的用{ ,∧,∨}表达的公式. 例: P→Q P∨Q P Q (P∧Q)∨( P∧ Q) ( P∨Q)∧(P∨ Q) 2. 深入到原子命题变元之前,并使变元之前最多只有一个 词. 例: ( P∨ Q) P∧ Q P∧Q 3. 利用∧对∨的分配,将公式化成为析取范式. 4. 去掉永假项得最简析取范式. 32 1.3.范式 例1 求 (P∨Q) (P∧Q) 的析取范式: 求一个命题公式的合取范式和求析取范式的方法类似: 第1, 2步相同; 第3步,利用∨对∧的分配; 第4步,去掉永真项. 例2求Q∨ (P→Q)∨ (P∨Q)的合取范式 33 1.3 范式 主析取范式对给定的命题公式, 仅含有极小项的析取的等价式称为 给定命题公式的主析取范式. 在n 个变元的基本积中,若每个变元及其否定并不同时存在,且二者之 一出现一次且仅出现一次,则称此基本积为极小项. 34 对一个命题变元讲, 极小项有21=2个, 即P, P 对二个命题变元, 极小项有22=4个, 即P ∧Q, P ∧Q, P ∧ Q, P ∧ Q n个命题变元构成的不同极小项有2n个(n∈I+), 每个极小项 为真的赋值仅有一个. 1.3 范式 在真值表中, 一个公式的真值为T的指派所对应的极小项的析 取, 即为此公式的主析取范式. 例求出P →Q, P∨ Q, (P∧Q), P∧ Q的主析取范式 35 PQP∨ Q (P∧Q) P∧ QP→Q FF T T F T FT F T F T TF T T T F TT T F F T P →Q ( P ∧ Q ) ∨( P ∧Q ) ∨( P ∧Q ) P ∨ Q ( P ∧ Q ) ∨( P ∧ Q ) ∨( P ∧Q ) 1.3 范式 36 讨论: (1) 只要命题公式不是永假式, 则可以根据该命题公式 的真值表直接写出其主析取范式,且是唯一的.方法是 找出该公式为T的行, 对应写出极小项的析取式, (2) 若命题公式是含有n个变元的永真式, 则它的主析取 范式一定含有2n个极小项. (3) 若二个命题公式对应的主析取范式相同, 则二个命 题公式一定是等价的. (4) 命题公式的主析取范式中极小项的个数等于真值表 中真值为T的行数. 1.3 范式 下面介绍直接求命题公式主析取范式的方法,分四步: (1) 将命题公式化归为与其等价的析取范式; (2) 除去永假项, 合并相同项( P∧P∧Q P∧Q ), 变为最 简析取范式; (3) 利用添变元的方法,将所有基本积变为极小项. (4) 合并相同的极小项变为一项. 例:二个变元P, Q,用∧对∨的分配添项 P P ∧( Q ∨ Q ) ( P ∧Q ) ∨( P ∧ Q) Q Q ∧( P ∨ P ) ( P ∧Q ) ∨( P ∧Q) 37 例求(P∧(P→Q))∨Q的主析取范式 1.3 范式 在n个变元的基本和中, 若每个变元与其否定,并不同时 存在且二者之一出现一次且仅出现一次, 则称这种基本 和为极大项. 主合取范式对给定的命题公式,仅含有极大项的合取 的等价公式式称为给定命题公式的主合取范式. 例:有二个变元P, Q的极大项有22=4个, (P∨Q), (P ∨ Q ), ( P∨Q), ( P∨ Q) 有n个变元,则有2n个极大项(n∈I+). 38 1.3 范式 在真值表中,一个公式的真值为F的指派所对应极大项的合 取, 即为此公式的主合取范式. 例求出(P→Q), (P∨Q), (P∧Q), (P∧Q)的主合取范式. PQP∨Q (P∧Q) P∧QP→Q FF F T F T FT T T F T TF T T F F TT T F T T P ∨Q P ∨Q( P →Q ) ( P ∨Q ) P ∧Q (P ∨Q) ∧(P ∨ Q ) ∧( P ∨Q) 39 1.3 范式 讨论 (1)与命题公式等价的主合范式中极大项的个数等于其真值 表中真值为F的行数. (2)只要命题公式不是永真式, 则一定可以写出与其等价的 唯一的主合取范式. (3) 已知一个命题公式的主析取范式, 则可写出与其等价的主 合取范式来. (4) 对应于有n个变元的命题公式, 则一定有主析取范式极小 项数+主合取范式极大项数=2n 例:P∨ Q ( P∧ Q)∨(P∧ Q)∨(P∧Q)主析取范式 P∨ Q主合取范式 40 1.3 范式 下面介绍直接命题公式主合取范式的方法: (1) 化为与命题公式等价的合取范式; (2) 除去真值为T的析取项和除去析取项中相同变元且只保留 一个,简化合取式; (3) 添项, 使析取项均变为极大项; 例如P, Q为二个变元, 即 P P∨(Q∧ Q) (P∨Q) ∧(P∨ Q) (4) 合并相同的极大项, 保留一项. 例:求P∧( P →Q ) ∨Q的主合取范式 41 1.3 范式 为了确保主范式的唯一性,我们需要做如下安排: (a) 各命题变元的位置安排一固定次序; (b) 对极小项, 极大项安排一个次序. 对于有n个变元的命题公式, 则最多可有2n个极小项, 用m0 ∨m1 …∨m2n-1来表示. 例:设一命题公式有五个变元,P0,P1,P2,P3,P4 (次序已定),则必可 写出25=32个极小项, 如m(11)十=m(01011) =( P0∧P1∧ P2∧P3∧P4) m(18)十=m(10010) =( P0∧ P1∧ P2∧P3∧ P4) 42 1.3 范式 极小项m(i)十的表示方法: (a) 把(i)十变换成等价的(J0, J1…Jn-1) 二; (b) 由二进制写出其对应的极小项; 43 用M0, M1,…, M2n-1表示有n个变元的命题公式的极大项. 极大项的表示方法: (a) 把(i)十变换成等价的(J0, J1 …Jn-1)二; (b) 由二进制数写出其对应的极大项; 极大项和极小项编码约定刚好相反. 极大项的构造 F/0 对应着变量本身; T/1 对应着变量否定. 极小项的构造 F/0对应着变量的否定; T/1对应着变量本身. 1.3 范式 例1求(P∧Q)∨( P∧R)的编码表达式(设P, Q, R次序已 定) 44 例3 写出( P ∨ Q)的主析取范式和主合取范式编码表示. 极大项与极小项性质 mi ∧mj F(i ≠j) Mi∨Mj T(i ≠j) …(见书P19) 例2 求(P∧Q)∨( P∧R)的极大项编码表示(设P,Q,R次序 已定) 1.3 范式 一个原子命题变元有4个不同的真值表(221 ); 二个原子命题变元有16个不同的真值表(222 ); n个原子命题变元有22n 个不同的真值表; 对于含有n个变元的命题公式,必定可写出个主范式 , 若排除永真式或永假式,则实际可写出( 22n -1) 个 主析(合)范式. 主范式的个数 45 1.3 范式 (1) 真值表法对于变元的所有真值指派,看对应命题公 式的真值. (2) 命题演算方法化简命题公式至最简式, 看是否存 在和(P∨ P), (P∧ P)等价, 若否则为可满足的. (3) 范式方法找到其主析取和主合取的形式. 如何判定命题公式为永真式, 永假式和可满足或二 个命题公式等价, 归纳有三种方法: 作业习题1.3 2, 3 |
|