第六讲命题演算系统课件.ppt

《第六讲命题演算系统课件.ppt》由会员分享，可在线阅读，更多相关《第六讲命题演算系统课件.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、公式四部分组成。下面具体介绍命题演算系统。第4页，此课件共24页哦命题演算系统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的规定形成的符号串才是合式公式。第5页，此课件共24页哦命题演算系统Lpv下面给出初始公式（即公理演算系统的公理）和初始规则：v初始公式 AP1 A（B A）AP2 （A （B C）（A B）（A C）AP3 （A B）

3、（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。这就是代入规则，运用代入规则时请注意，一定是处处代入。第6页，此课件共24页哦命题演算系统Lpv一个使用形式语言的形式系统，通过初始公式和初始规则得到的公式就是这个系统的定理。一个形式系统的任务也就是证明这些定理的成立。下面给出系统中的一些定义。第7页，此课件共24页哦命题演算系统Lpv定义定义3（证明的定义）LP中的证明是一

4、个合式公式的有限序列：A1，A2，An，且满足以下条件：对每一个Ai（1in）要么是公理，要么是由前面的公式根据变形规则得到的。v定义定义4（A证明的定义）如果一个证明A1，A2，An中的An=A，我们就称这个证明叫做关于A的证明，也就是A证明。v定义定义5（定理的定义）如果有一个A证明，则称A是这个系统的定理。记作：LP A。第8页，此课件共24页哦v定理定理1 AAv证明：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）（

5、4）MPv（6）A （A A）（1）SBv（7）A A (5)(6)MP第9页，此课件共24页哦命题演算系统Lpv定义定义6（推演的定义）如果A1，A2，An是一个满足如下条件的公式序列，则称它是以为前提的推演。v条件：v任一Ai（1i n）是中的元素，或者v是公理，或者v是由前面的公式根据变形规则得到的。v定义定义7 从到A的推演：如果A1，A2，An是以为前提的推演，并且An=A，我们就称它是从到A的推演，或者说A是从出发得到的推论，记作：A。v如果=B，可以记作：BA；如果=B，C，可以记作：B，CA；如果=，就记作：A。从出发推出A，A就是一个定理。v演绎定理的证明见教材。第10页，此

6、课件共24页哦v演绎定理：演绎定理：如果 A B，则 AB。v演绎定理的证明需要数学归纳法，数学归纳法是证明无穷个命题成立的方法，它由两部分组成，分别是归纳基础和归纳步骤。归纳法可以分为两类：v第一类归纳法：有一批编了号码的命题v（1）我们能证明第1号命题是正确的；v（2）如果我们还能证明，在第n号命题正确的时候，第n+1号命题也正确，那么这一批命题就都是正确的。第11页，此课件共24页哦v第二类归纳法：有一批编了号码的命题v（1）我们能证明第1号命题是正确的；v（2）如果我们还能证明，在kn时命题正确的时候，k=n时命题也正确，那么这一批命题都是正确的。第12页，此课件共24页哦v证明：v归

7、纳基础：令该演绎序列有一个公式B构成，为LP中任意合式公式的集合，如果如果，A B，则 AB。v情况1：B是公理v（1）B 公理v（2）B （A B）AP1 SBv（3）A B （1）（2）MPv即 A B得证。第13页，此课件共24页哦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归纳基础证毕。第14页，此课件共24页哦v归纳步骤：假设当由和A得出B的演绎的公式数目小于n时，演绎定义成立，现在证明当由和A得出B的演绎的公式数目等于n时，演绎定理也成立

8、。分四种情况：v情况1：B是公理，同归纳基础中情况1相同。v情况2：B是中的公式，同上。v情况3：B就是A，也同上。第15页，此课件共24页哦v情况4：B是由出现在演绎序列中在前的两个公式，通过分离规则得到的，此时前面必定有两个这样的公式：一个是C，一个是C B。两者中的任一必然在LP中由和A为前提推出，把这些公式序列数目分别设为：k和m，k和m都小于n。根据归纳假设可得：第16页，此课件共24页哦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）

9、（A B）（m）（m+1）MPv（m+3）A B （m+2）（k）MPv因此，在以上四种情况下，都有 A B。演绎定义证毕。第17页，此课件共24页哦命题演算系统的可靠性v命题演算系统命题演算系统LP的可靠性的可靠性v古典的一致性古典的一致性 系统S是一致的，当且仅当，不存在公式，和都是S-可证的。v语法的一致性语法的一致性 系统S是一致的，当且仅当，并非任一公式都是S-可证的。v语义的一致性语义的一致性 系统S是一致的，当且仅当，S的内定理都是有效的。v语义一致性就是可靠性，因此，通常情况下把系统的一致性和可靠性看作是相同的。第18页，此课件共24页哦v定义定义8 命题演算系统LP中的一个赋

10、值是一个函数v，v的定义域是系统LP中的合式公式，值域是1，0（1表示真，0表示假），对LP中的任意公式A，B，满足：v定义定义9 LP中的公式A是重言式，当且仅当，对每一个赋值v，都有v（A）=1。v引理引理1（MP保真性定理）令A，B是LP中的任意公式，如果A是重言式且AB是重言式，则B也是重言式。第19页，此课件共24页哦v定理定理4（可靠性定理）：系统LP中的每一个定理都是重言式。v证明：v令A是LP中的一个定理，必然存在LP中对A的一个证明，假设该证明是由n个公式A1，A2，An组成的序列，现在对n进行数学归纳即可证得可靠性定理。v归纳基础：v当n=1时，即A在LP中的证明序列只有一

11、个公式，很显然，A一定是系统中的一个初始公式，即公理，公理都是重言式。（可用真值表法证明）第20页，此课件共24页哦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也是重言式。可靠性定理证毕。第21页，此课件共24页哦v定义定义10 一个系统是一致的，当且

12、仅当，对系统中的任意合式公式A，A和A不能都是该系统的定理。v定理定理5（一致性定理）命题演算系统LP是一致的，即对LP中的任一公式，A和A不能都是命题演算系统LP的定理。v定理定理6 LP是一致的，当且仅当，LP中存在一个公式不是它的定理。第22页，此课件共24页哦命题演算系统的完全性v古典的完全性古典的完全性 系统S是古典完全的，当且仅当，对于任意A，或者A不可证，或者A不可证。v语法的完全性语法的完全性 系统S是语法完全的，当且仅当，把一个不可证的公式当作公理，将会导致系统的不一致。v语义的完全性语义的完全性 系统S是语义完全的，当且仅当，系统中的有效式都是S-定理，即：A iff A。第23页，此课件共24页哦命题演算系统的完全性v命题演算系统的古典完全性和语法完全性都是显而易见的，这里我们主要证明它的语义完全性，语义完全性证明的方法有很多，我们采用极大一致集的方法来证明命题演算系统的语义完全性。v具体证明过程见教材。第24页，此课件共24页哦