命题演算系统.ppt

第六讲命题演算形式系统Lp命题演算形式系统Lpv命题演算形式系统Lp；v命题演算系统的可靠性；v命题演算系统的完全性命题演算系统Lpv命题演算系统通常记为：P，分为公理演算系统和 自然演绎推理系统，它们都是用形式语言构造出来 的所谓公理演算系统，指的是由一些基本命题（ 即公理）和推导规则以及由此推出的一些命题（即 定理）而形成的演绎系统所谓自然演绎系统，指 的是没有公理只依赖推导规则推出一些命题（即定 理）而形成的演绎系统 命题演算系统Lpv形式化的公理系统又称为形式系统一个形 式系统主要由形式语言、初始公式、变形规 则以及由它们得到的公式四部分组成下面 具体介绍命题演算系统 命题演算系统Lpv初始符号v1、命题变元：p，q，r，……；v2、命题联接词： ∧，∨，→，，﹁；v3、辅助符号：（，）v形成规则v1、任何命题变元是合式公式；v2、如果A是合式公式，则（﹁A）是合式公式；v3、如果A、B是合式公式，则（A ∧ B）、（A ∨ B）、（ A → B）、（A  B）是合式公式；v4、只有按照1、2、3的规定形成的符号串才是合式公式命题演算系统Lpv下面给出初始公式（即公理演算系统的公理）和初始规则：v初始公式AP1 A→（B → A）AP2 （A → （B → C）） → （（A → B） → （A → C） ）AP3 （﹁A → B）（（ ﹁ A → ﹁B） → A）v初始规则（又叫变形规则）MP 分离规则 若├ A → B且├A，则├B。

SB 代入规则 若 ├A，则├ A（p1/B1，p2/B2，…，pn/Bn ）其中，A（p1/B1，p2/B2，…，pn/Bn）表示将A中的命题 变元p1，p2，…，pn（如果有的话）处处分别换成B1， B2 ，…，Bn这就是代入规则，运用代入规则时请注意，一定 是处处代入命题演算系统Lpv一个使用形式语言的形式系统，通过初始公 式和初始规则得到的公式就是这个系统的定 理一个形式系统的任务也就是证明这些定 理的成立下面给出系统中的一些定义命题演算系统Lpv定义3（证明的定义） LP中的证明是一个合式公式 的有限序列：A1，A2，…An，且满足以下条件： 对每一个Ai（1in）要么是公理，要么是由前面的公 式根据变形规则得到的v定义4（A证明的定义）如果一个证明A1，A2， …An中的An=A，我们就称这个证明叫做关于A的证 明，也就是A证明v定义5（定理的定义） 如果有一个A证明，则称A是 这个系统的定理记作：├LP Av定理1 ├ A→Av证明：v（1） A → （B → A） AP1 v（2） A → （（A → A ） → A） （1）SBv（3）（A → （B → C）） → （（A → B） → （A → C） ） AP2v（4）A → （（A → A ） → A） → （（A → （A → A）） → （A → A）） （3）SBv（5）（A → （A → A）） → （A → A） （2）（4）MPv（6）A → （A → A） （1）SBv（7）A → A (5)(6)MP命题演算系统Lpv定义6（推演的定义） 如果A1，A2，…An是一个满足如下条件的公式序 列，则称它是以Γ为前提的推演。

v条件：v任一Ai（1≤i ≤ n）是Γ中的元素，或者v是公理，或者v是由前面的公式根据变形规则得到的v定义7 从Γ到A的推演：如果A1，A2，…An是Γ以为前提的推演，并且 An=A，我们就称它是从Γ到A的推演，或者说A是从Γ出发得到的推论 ，记作： Γ ├Av如果Γ ={B}，可以记作：B├A；如果Γ ={B，C}，可以记作：B，C├A ；如果Γ =Ø，就记作：├A从Ø出发推出A，A就是一个定理v演绎定理的证明见教材v演绎定理：如果Γ ∪{A}├ B，则Γ ├ A→Bv演绎定理的证明需要数学归纳法，数学归纳法是证 明无穷个命题成立的方法，它由两部分组成，分别 是归纳基础和归纳步骤归纳法可以分为两类：v第一类归纳法：有一批编了号码的命题v（1）我们能证明第1号命题是正确的；v（2）如果我们还能证明，在第n号命题正确的时候 ，第n+1号命题也正确，那么这一批命题就都是正 确的v第二类归纳法：有一批编了号码的命题v（1）我们能证明第1号命题是正确的；v（2）如果我们还能证明，在k﹤ n时命题正 确的时候，k=n时命题也正确，那么这一批命 题都是正确的v证明：v归纳基础：令该演绎序列有一个公式B构成，Γ为 LP中任意合式公式的集合，如果如果{Γ ，A}├ B， 则Γ ├ A→B。

v情况1：B是公理v（1）B 公理v（2）B → （A → B） AP1 SBv（3）A → B （1）（2）MPv即Γ ├ A → B得证v情况2：B是Γ中的公式，记作：B∈ Γv（1）B 前提v（2）B → （A → B） AP1 SBv（3）A → B （1）（2）MPv即├ A → B得证v情况3：B就是A此时要证├ A → A，根据定理1得 证v归纳基础证毕v归纳步骤：假设当由Γ和A得出B的演绎的公 式数目小于n时，演绎定义成立，现在证明当 由Γ和A得出B的演绎的公式数目等于n时， 演绎定理也成立分四种情况：v情况1：B是公理，同归纳基础中情况1相同 v情况2：B是中的公式，同上v情况3：B就是A，也同上v情况4：B是由出现在演绎序列中在前的两个 公式，通过分离规则得到的，此时前面必定 有两个这样的公式：一个是C，一个是C → B 。

两者中的任一必然在LP中由Γ和A为前提 推出，把这些公式序列数目分别设为：k和m ，k和m都小于n根据归纳假设可得：vΓ ├（A → C）和Γ ├（A → （C → B））v以为Γ前提得出（A → B）的演绎如下：v（1）v …v（k）（A → C）v …v（m）A → （C → B）v（m+1）（A → （C → B）） → （（A → C） → （A → B）） AP2v（m+2）（A → C） → （A → B） （m）（m+1）MPv（m+3）A → B （m+2）（k）MPv因此，在以上四种情况下，都有Γ ├ A → B演绎定义证毕命题演算系统的可靠性v命题演算系统LP的可靠性v古典的一致性 系统S是一致的，当且仅当，不存在 公式，和都是S-可证的v语法的一致性 系统S是一致的，当且仅当，并非任 一公式都是S-可证的v语义的一致性 系统S是一致的，当且仅当，S的内 定理都是有效的v语义一致性就是可靠性，因此，通常情况下把系统 的一致性和可靠性看作是相同的。

v定义8 命题演算系统LP中的一个赋值是一个函数v ，v的定义域是系统LP中的合式公式，值域是{1，0} （1表示真，0表示假），对LP中的任意公式A，B ，满足：v定义9 LP中的公式A是重言式，当且仅当，对每一 个赋值v，都有v（A）=1v引理1 （MP保真性定理）令A，B是LP中的任意公 式，如果A是重言式且A→B是重言式，则B也是重 言式v定理4（可靠性定理）：系统LP中的每一个定理都是重言式 v证明：v令A是LP中的一个定理，必然存在LP中对A的一个证明，假 设该证明是由n个公式A1，A2，…An组成的序列，现在对n 进行数学归纳即可证得可靠性定理v归纳基础：v当n=1时，即A在LP中的证明序列只有一个公式，很显然，A 一定是系统中的一个初始公式，即公理，公理都是重言式 （可用真值表法证明）v归纳步骤：v假设LP中的证明序列小于n的所有定理都是重言式，证明LP 中的证明序列为n的定理也是重言式现在令A的证明序列为 n，证明序列中的第n个公式就是A，有两种情况：v情况1：A是公理v情况2：A是由证明序列中在前的两个公式通过分离规则得到 的，此时必有两个公式为：B和B → A。

又因为它们都是在A 前面的公式，因此证明序列必然小于n，根据归纳假设，B和 B → A都是重言式再根据引理1，得到A也是重言式可靠 性定理证毕v定义10 一个系统是一致的，当且仅当，对系 统中的任意合式公式A，A和A不能都是该系 统的定理v定理5（一致性定理）命题演算系统LP是一 致的，即对LP中的任一公式，A和A不能都是 命题演算系统LP的定理v定理6 LP是一致的，当且仅当，LP中存在一 个公式不是它的定理命题演算系统的完全性v古典的完全性 系统S是古典完全的，当且仅当，对 于任意A，或者A不可证，或者A不可证v语法的完全性 系统S是语法完全的，当且仅当，把 一个不可证的公式当作公理，将会导致系统的不一 致v语义的完全性 系统S是语义完全的，当且仅当，系 统中的有效式都是S-定理，即：A iff ├A命题演算系统的完全性v命题演算系统的古典完全性和语法完全性都 是显而易见的， 这里我们主要证明它的语义 完全性，语义完全性证明的方法有很多，我 们采用极大一致集的方法来证明命题演算系 统的语义完全性v具体证明过程见教材。