第六讲 命题演算系统.ppt

1、第六讲,命题演算形式系统Lp,命题演算形式系统Lp,命题演算形式系统Lp； 命题演算系统的可靠性； 命题演算系统的完全性。,命题演算系统Lp,命题演算系统通常记为：P，分为公理演算系统和自然演绎推理系统，它们都是用形式语言构造出来的。所谓公理演算系统，指的是由一些基本命题（即公理）和推导规则以及由此推出的一些命题（即定理）而形成的演绎系统。所谓自然演绎系统，指的是没有公理只依赖推导规则推出一些命题（即定理）而形成的演绎系统。,命题演算系统Lp,形式化的公理系统又称为形式系统。一个形式系统主要由形式语言、初始公式、变形规则以及由它们得到的公式四部分组成。下面具体介绍命题演算系统。,命题演算系统L

2、p,初始符号 1、命题变元：p，q，r，； 2、命题联接词： ，； 3、辅助符号：（，）。 形成规则 1、任何命题变元是合式公式； 2、如果A是合式公式，则（A）是合式公式； 3、如果A、B是合式公式，则（A B）、（A B）、（A B）、（A B）是合式公式； 4、只有按照1、2、3的规定形成的符号串才是合式公式。,命题演算系统Lp,下面给出初始公式（即公理演算系统的公理）和初始规则： 初始公式 AP1 A（B A） AP2 （A （B C） （A B） （A C） AP3 （A B）（ A B） A） 初始规则（又叫变形规则） MP 分离规则 若 A B且A，则B。 SB 代入规则 若 A

3、，则 A（p1/B1，p2/B2，pn/Bn） 其中，A（p1/B1，p2/B2，pn/Bn）表示将A中的命题变元p1，p2，pn（如果有的话）处处分别换成B1， B2，Bn。这就是代入规则，运用代入规则时请注意，一定是处处代入。,命题演算系统Lp,一个使用形式语言的形式系统，通过初始公式和初始规则得到的公式就是这个系统的定理。一个形式系统的任务也就是证明这些定理的成立。下面给出系统中的一些定义。,命题演算系统Lp,定义3（证明的定义） LP中的证明是一个合式公式的有限序列：A1，A2，An，且满足以下条件：对每一个Ai（1in）要么是公理，要么是由前面的公式根据变形规则得到的。 定义4（A证

4、明的定义）如果一个证明A1，A2，An中的An=A，我们就称这个证明叫做关于A的证明，也就是A证明。 定义5（定理的定义） 如果有一个A证明，则称A是这个系统的定理。记作：LP A。,定理1 AA 证明： （1） A （B A） AP1 （2） A （A A ） A） （1）SB （3）（A （B C） （A B） （A C） AP2 （4）A （A A ） A） （A （A A） （A A） （3）SB （5）（A （A A） （A A） （2）（4）MP （6）A （A A） （1）SB （7）A A (5)(6)MP,命题演算系统Lp,定义6（推演的定义） 如果A1，A2，An是一个满足

5、如下条件的公式序列，则称它是以为前提的推演。 条件： 任一Ai（1i n）是中的元素，或者 是公理，或者 是由前面的公式根据变形规则得到的。 定义7 从到A的推演：如果A1，A2，An是以为前提的推演，并且An=A，我们就称它是从到A的推演，或者说A是从出发得到的推论，记作： A。 如果 =B，可以记作：BA；如果 =B，C，可以记作：B，CA；如果 =，就记作：A。从出发推出A，A就是一个定理。 演绎定理的证明见教材。,演绎定理：如果 A B，则 AB。 演绎定理的证明需要数学归纳法，数学归纳法是证明无穷个命题成立的方法，它由两部分组成，分别是归纳基础和归纳步骤。归纳法可以分为两类： 第一类

6、归纳法：有一批编了号码的命题 （1）我们能证明第1号命题是正确的； （2）如果我们还能证明，在第n号命题正确的时候，第n+1号命题也正确，那么这一批命题就都是正确的。,第二类归纳法：有一批编了号码的命题 （1）我们能证明第1号命题是正确的； （2）如果我们还能证明，在kn时命题正确的时候，k=n时命题也正确，那么这一批命题都是正确的。,证明： 归纳基础：令该演绎序列有一个公式B构成，为LP中任意合式公式的集合，如果如果 ，A B，则 AB。 情况1：B是公理 （1）B 公理 （2）B （A B） AP1 SB （3）A B （1）（2）MP 即 A B得证。,情况2：B是中的公式，记作：B （

7、1）B 前提 （2）B （A B） AP1 SB （3）A B （1）（2）MP 即 A B得证。 情况3：B就是A。此时要证 A A，根据定理1得证。 归纳基础证毕。,归纳步骤：假设当由和A得出B的演绎的公式数目小于n时，演绎定义成立，现在证明当由和A得出B的演绎的公式数目等于n时，演绎定理也成立。分四种情况： 情况1：B是公理，同归纳基础中情况1相同。 情况2：B是中的公式，同上。 情况3：B就是A，也同上。,情况4：B是由出现在演绎序列中在前的两个公式，通过分离规则得到的，此时前面必定有两个这样的公式：一个是C，一个是C B。两者中的任一必然在LP中由和A为前提推出，把这些公式序列数目分

8、别设为：k和m，k和m都小于n。根据归纳假设可得：, （A C）和 （A （C B） 以为前提得出（A B）的演绎如下： （1） （k）（A C） （m）A （C B） （m+1）（A （C B） （A C） （A B） AP2 （m+2）（A C） （A B） （m）（m+1）MP （m+3）A B （m+2）（k）MP 因此，在以上四种情况下，都有 A B。演绎定义证毕。,命题演算系统的可靠性,命题演算系统LP的可靠性 古典的一致性 系统S是一致的，当且仅当，不存在公式，和都是S-可证的。 语法的一致性 系统S是一致的，当且仅当，并非任一公式都是S-可证的。 语义的一致性 系统S是一致的，

9、当且仅当，S的内定理都是有效的。 语义一致性就是可靠性，因此，通常情况下把系统的一致性和可靠性看作是相同的。,定义8 命题演算系统LP中的一个赋值是一个函数v，v的定义域是系统LP中的合式公式，值域是1，0（1表示真，0表示假），对LP中的任意公式A，B，满足： 定义9 LP中的公式A是重言式，当且仅当，对每一个赋值v，都有v（A）=1。 引理1 （MP保真性定理）令A，B是LP中的任意公式，如果A是重言式且AB是重言式，则B也是重言式。,定理4（可靠性定理）：系统LP中的每一个定理都是重言式。 证明： 令A是LP中的一个定理，必然存在LP中对A的一个证明，假设该证明是由n个公式A1，A2，A

10、n组成的序列，现在对n进行数学归纳即可证得可靠性定理。 归纳基础： 当n=1时，即A在LP中的证明序列只有一个公式，很显然，A一定是系统中的一个初始公式，即公理，公理都是重言式。（可用真值表法证明）,归纳步骤： 假设LP中的证明序列小于n的所有定理都是重言式，证明LP中的证明序列为n的定理也是重言式。现在令A的证明序列为n，证明序列中的第n个公式就是A，有两种情况： 情况1：A是公理。 情况2：A是由证明序列中在前的两个公式通过分离规则得到的，此时必有两个公式为：B和B A。又因为它们都是在A前面的公式，因此证明序列必然小于n，根据归纳假设，B和B A都是重言式。再根据引理1，得到A也是重言式。可靠性定理证毕。,定义10 一个系统是一致的，当且仅当，对系统中的任意合式公式A，A和A不能都是该系统的定理。 定理5（一致性定理）命题演算系统LP是一致的，即对LP中的任一公式，A和A不能都是命题演算系统LP的定理。 定理6 LP是一致的，当且仅当，LP中存在一个公式不是它的定理。,命题演算系统的完全性,古典的完全性 系统S是古典完全的，当且仅当，对于任意A，或者A不可证，或者A不可证。 语法的完全性 系统S是语法完全的，当且仅当，把一个不可证的公式当作