高级数理逻辑第3讲

1、3 命题逻辑形式系统（FSPC）续3.4 命题逻辑语义P(X)àQ(F(Xa) A(X)->A(X)X是复数，则（x-a）平方大于等于0；X=RPx是复数Q(x)代表的是大于等于0F代表的是平方X复数T(P(X)=0.5P(X)à(Q(X)àP(X)AàB3.4.1 基本概念1、什么是形式系统的语义（1） 形式系统与具体的系统无关（2） 能够用形式系统来描述现实系统（3） 把从形式系统解释成“”现实系统的过程成为语义 语义有多种类型：指称语义，克里普克语义，操作语义，公理语义等2语义构成 (指称语义)语义主要有两部分：（1） 结构：（有两个主要部分

2、构成）*确定研究对象集合，论域或个体域*把形式系统中的变量到论域中的一组规则映射规则（2） 域值：指一组给公式赋值的规则根据这项规则将 AtomicValue中3.4.2 命题逻辑语义1、语义结构由于没有变量，所以只有第二部分赋值，值域为0,1赋值规则：I.II.T(A)= 当T（A）0时，T(A)=1。当T（A）1时，T(A)=0。III.当T(A)=T(B)=1时，T()=1，其他情况T()=0。IV.当T(A)1或者T（B）1情况下，T（）1，其他情况T（）0。V.当T(A)=0时候，T（）=1,当T(B)=1时候，T（）=1。其他情况下T（）=0。AàBVI.2、 语义的特殊

3、公式1) 公式A为永真式，重言式tautologies，如果对一切赋值，.AàA=AvA(AàA)=1, Aà(BàA)=12) 公式A为永假式，矛盾式contradictions,如果对一切赋值，AA=03) A，B为逻辑等价的，如果对于一切赋值，记做AB(A|=|B)T(A)=T(B),对于任意TA->A A->(B->A) 4) 可满足的，公式A为可满足的，如果至少存在一个赋值，3、 真值计算有了赋值映射，我们可以计算任意公式的真值。通常真值计算的方法有：真值表计算方法和二叉树计算方法等。1) 真值表真值表是计算真值的简单工具。利

4、用这个工具可以计算任意公式的真值。例如：公式的真值表如下：000100110101011110011010110111112) 二叉树利用二叉树，可视化地计算公式的真值。例如：计算下面公式的真值，并给出他是否是重言式。 故A不为重言式，是可满足的3) 习题 求以下公式的真值表：（1）（2）（3）pqr000100110101011110001011110011113.5 逻辑推论（逻辑演算）有了公式的真值以后，对于一些公式我们可以比较公式的真值得大小。从而可以讨论公式真值之间的关系。讨论公式之间真值关系的就是我们在语义上进行演算的主要内容。3.5.1 基本概念（1）逻辑推论：设是一个FSPC上

5、的公式集合，A是FSPC上的任一公式。A为的逻辑结果，记做|=A，当且仅当对任何赋值映射v，如果1时，则。|=读作逻辑蕴涵。（2）逻辑等价：设公式A和公式B分别为FSPC上的两个公式。A和B为逻辑等价的，记做A|=|B当且仅当A|=B和B|=A同时成立。（3）永真式：如果A为永真式，则公式集合为空集，即|=A。3.5.2 逻辑推论的主要方法（1）永真式代入原理（principle of substitution）设A(P)为一含有命题变元P的永真式，那么将A中P的每一次出现代换为公式B，所得公式A(B)仍为永真式。C->(B->C) = C->(X->C)（2）替换原理

6、（principle of replacement）设命题公式A含有子公式C（C为命题公式），如果C|=|D，那么将A中子公式C提换为命题公式D，所得公式B满足A|=B。（3） 逻辑等价性：逻辑等价且有自反性、对称性和传递性。（4） 对偶原理： 设A是原子公式和联结符号组成的公式，并且在A中交换以原子公式与其否定互换得到的公式A,称A为A的对偶；A|=AA B(A B) （5） 演绎定理：设为FSPC的公式集合，A和B分别为FSPC上的公式。|=成立的充分必要条件是：|=。已知：存在一个证明序列A1,A2,An=AàB,An+1=A,An+2=B求证：存在另一个证明序列：从出发能够得

7、到B。已知：对于任意一个赋值映射f,如果f()=1,则f(AàB)=1;求证：对于任意的赋值映射f,如果f(,A)=1，则f(B)=1证明：已知：对于任意的赋值映射f，如果f满足f()=1,则f(AàB)=1.求证：对于任意的赋值映射f1,f1满足f1()=1,且f1(A)=1；则f1(B)=1.证明：任意的赋值映射f,f满足f1()=1,且f(A)=1.由于f1()=1，则f1(AàB)=1;由于f1(AàB)=1,并且f1(A)=1;条件：f()=1,且f(A)=1, f(AàB)=1，证明：f(B)=1由已知：f(AàB)=1.

8、因此，f(B)=1.因此，对于任意的赋值映射f,f满足f()=1,且f(A)=1；则f(B)=1.必要性：已知：对于任意的赋值映射f,f满足f()=1,且f(A)=1；则f(B)=1.求证：对于任意的赋值映射f1，如果f1满足f1()=1,则f1(AàB)=1.对于任意的赋值映射f，使得f()=1.F1()=1,f1(A)=0 f1(AàB)=1F1()=1,f1(A)=1 ,f1(B)=1, f1(AàB)=1假设f1(A)=0;f1(AàB)=1.假设f1(A)=1, 由于已知条件可以知道f(B)=1.因此，f(AàB)=1.证明： a)首

9、先证明充分性：已知，证明成立。对于任意赋值映射v，如果1成立，则成立。对于成立有两种情况，为了证明成立，只需考虑，使1的情况。如果赋值映射v，满足1，1且，则有1。因此，成立。b)证明必要性：已知 ，证明成立。已知：如果对于任意的赋值映射且则；要证明：即证明对于任意赋值映射v，满足，则有成立。任取赋值映射v，满足，则有：当0时，有当1时，由已知1，因此3.5.3 逻辑推论性质1、公理为重言式A1vA2vA3v2、推理规则保真性设A和B为FSPC上的公式；如果|=A且|=成立，则|=成立。3、重要永真式T1 T(P)<=T(P)T2 P<=Max(P,Q)T3 Min(P,Q)<

10、;=PT4 P<=Q, Q<=R, P<=R T5 P=Q,Q=R, P=R4、重要等价式E1 P=1-(1-P)=P E2 （等幂律） E3 (交换律)E4 E5 （分配律）E6 （德摩根定律）E7 E8 E9 Pv(QàR) =Pv(QvR)=(PvQ)vR=(Q P)vR=(P Q)àR如果P=1，则QàR=1;如果min(Q,P)=1,则R=1.E10 (PvQ) (QvP)=(PvQ)Q)v(PvQ) P)=(QP)v(PQ)E11 E12 Max(P, Min(P,Q)=P MIN(P,Q)<PMIN(P,MAX(P,Q)=PM

11、AX(P,Q)>=P. （吸收律）3.6 公式化简3.6.1 基本概念有了赋值规则和上述的等价公式后，我们就可以将公式进行等价形式的转化。转换的目标是获得一个标准的公式形式，从而使公式计算更简单，同时使计算机能够进行基于符号的演算和推理过程。范式是常用的公式的标准形式。1、范式：设A和B为FSPC上的两个公式，称公式B为公式A的析取（合取）范式，如果B|=A，并且B型如：C1, C2, C3, ,Cm L1Vl2， L2vL1 L2P(x), P(5+y)= x=5+y, P(5y) P(5+y)其中，称为B的子句（Clause），子句型如：Ci=其中为原子公式或其否定式，被称为文字。2

12、、对于FSPC上的任意公式A，存在一个析取（合取）范式与其逻辑等值。3、举例：求的析取范式。如果P与Q同时成立，则R成立的同时Q不成立。(PQ) v(QR)=(PvQ)v(QR)= PvQv(QR)= PvQ（1）（2）（3）（4）（5）3.6.2 化简过程由以上的论述可知，对于任意公式，存在与其等价的析取（合取）范式。对于任意公式A，可以通过以下步骤得到他的析取（合取）范式。（1）销去：利用E7 ，E10 和E11 销去公式中存在的联结词，和。（2）深入：将深入到原子公式之前。（3）利用E4 和E5将公式展开。 3.6.3 联结词完备集在自然推理系统中，联结词有, , , , （还可以有其他

13、多种联结词，如异或等）。在TASKI语义下，联结词可以由其他的联结词表示。那么是否存在一个最小的联结词的集合，能够表示所有的其他联结词？答案是肯定的。1、联结词的完备集：联结词的集合为完备的，当且仅当对于其他的联结词都可以由这个联结词的集合中的元素来表示。2、FSPC中的完备集：、等。如果引入异或，那么异或与也构成一个完备集合。3.7 元理论与元语言3.7.1 基本概念1、对象语言：形式语言本身，他是用来描述形式系统研究的对象的。AàB2、元语言：用来描述对象语言性质的语言。Meta math=meta data 3、元语言的组成：（1）形式系统各组成部分的称谓，如：公式、公理等。（

14、2）对形式分析讨论时所使用的逻辑术语，如：如果.，那么.等。（3）描述形式系统有关性质的语言，如：一致性、完备性等。4、元理论：研究形式系统所得到的定理和性质等。3.7.2 元理论的内容元理论是数理逻辑研究的主要内容之一，元理论主要包含以下内容：1、语法构成研究（Syntax）：主要是关于形式系统语言构成规律的研究。研究符号串的推演规律（重写规则）。2、语义研究（Semantics）：在这类研究中，符号被赋予一定的意义。研究在这种意义下，对公式作出各种解释的性质，特别是真值性质的研究。3、语法与语义关系：这种关系主要研究，语法演算与语义推理之间的性质。主要研究语法与语义之间能否具有一致性关系。

15、3.8 命题逻辑元理论根据元理论的主要内容，有语法、语义和语法与语义关系。形式化系统à语义结构à元理论à自动化3.8.1 语法研究1. 语法构成语法构成研究形式系统语言构成规律。主要研究推演（重写）规律；主要规律：（1）独立性：如果形式系统中每一个公理都是独立的，即把任一公里A从形式系统中删除后，所得形式系统FS不满足FSA（即A不是FS的定理），则称形式系统为独立的；l 独立形式系统是简洁的；（2）一致性：形式系统FS称为一致性，或相容的（consistent）如果不存在FS的公式A，使得A，同时成立；l 所有形式系统都应该是一致的；（3）完全性：形式系统为完全

16、的，如果对形式系统中任意公式A，或者A成立，或者成立；l 完全性的形式系统，一切都是可知的；因此，几乎没有价值；A并且是定理：1. 有限步骤内，可以给出证明2. 有限步骤内，不能给出证明A不是定理1. 有限步骤内，可以给出不是定理的证明2. 有限步骤内，不能给出不是定理的证明（4）可判定性：形式系统FS称为可判定的，如果存在一个算法，对FS对的任一公式A，可确定A是否成立，否则称FS是可判定的；如果上述算法对定理能作出判断，而对于非定理未必终止（作判断），称FS为半可判定的；l FS为可判定的，当且仅当定理集合为递归集；（5）公式集合一致性：称形式系统的公式集合为一致的，如果形式系统是一致的，

17、且不存在公式A使A ， 同时成立。2. 命题逻辑系统的语法构成命题逻辑主要以下定理：1) FSPC一致性：FSPC是一致的，即不存在公式A，使A ，同时成立，l 若公式（FSPC）集可满足的，则为一致的。2) FSPC不完全性：FSPC不是完全的，即存FPSC的公式A，使A ， 都不成立。证明：只需证明原子命题和其否定式，不是FSPC的定理。设P为FSPC的任意命题变元，如果P是定理，如果 P，则存在P的证明序列：其中或者为公理或者由 由rmp的到；由代入原理可知，为永真式；这与P不是永真式矛盾。3) FSPC可判定性：FSPC是可判定的。4) FSPC是独立的3.8.2 语义研究可满足性：F

18、SPC的公式A称为可满足的，如果存在赋值V使V(A)1，否则称A为不可满足的；3.8.3 语法语义关系语法和语义关系是元理论中最重要的内容，语法语义关系评价了一个形式系统的性质。语法语义关系的核心问题是合理性与完备性。形式：A1,A2,An=Af(A1)=1,.f(An)=1: f(A)=0 语法à语义 合理性语义à语法 完备性I 语法和语义关系研究语法语义关系，首先关心的问题是在语法上的形式演算，在语义的逻辑推论上是否成立。这个问题被称作合理性（Soundness）。其次，是对于语义上的逻辑推理，在形式演算上是否成立。这个问题是完备性（Completeness）。这两个问

19、题是语法语义关系的核心。: A1,.An=AF()<=f(A)F()=1,F(A)=1,F(B)=1,F(C)=1.1) 合理性（soundness）：称形式系统FS是合理的，FS的任意公式A有：FS，则|=M，M为所有结构；2) 完备性（Completeness）：称形式系统FS是完备的，如果对FS的任意公式有：若|=M，则FS，这里M为FS所讨论的一类结构；3) 紧致性：称形式系FS是紧致的，如果对FS的任意公式集有：如果公式集的所有穷子集是可满足的，那么公式集也是可满足的；II FSPC语法语义关系1、FSPC合理性：FSPC是合理的，即对FSPC中任一公式A，如果A成立，则|=v

20、A成立。已知：A是定理求证：A是永真的由于A是定理，存在一个证明序列A1,A2,An=A。N=1时：A1=A。由于A1或者为公理或者是前边的公式通过推理规则得到。因此，A1是公理，也就是A是公理。对于任意的赋值映射f，则f(A)=1。假设：n<m时，命题成立：A是定理则A是永真的。证明：当n=m时，命题成立。A1,A2,Am-1, Am=A1, Am是公理：公理是永真的，因此命题成立。2, Am是前边通过推理规则得到的。推理分离规则，三段论。假设Am是由Ai和Aj通过分离规则得到。假设Aj=AiàAm或者Ai=AjàAm。我们I,j <m。由于归纳假设，Ai和A

21、j都是永真的。由于推理规则保真性，那么Am是永真的。因此，命题成立。1. 证明序列àT1<=T22. 一致可满足3. 序列证明则一定存在逻辑结果4. 存在逻辑结果，一定存在证明序列证明：（1）由于A成立，因此存在A的证明序列；（2）对A的证明序列长度归纳证明；（3）当1时，A为公理；由于公理都为永真式，因此A为永真，即vA成立；（4）假设当<m时成立；（5）当m时A或者为公理，如果为公理由（3）可知vA ；或者A由，通过分离规则（rmp）得到；（6）由于，的序列长度<m；（7）所以有B，；（8）由分离规则（rmp）保真性，则A成立。l 推论：设为FSPC的公式集合，

22、A为FSPC的公式；如果A成立，则|=A成立。2、FSPC完备性：FSPC是完备的，即对FSCP的任意公A，如果|=A成立，则A成立。l 推论：设是FSPC的公式集合，A为FSPC的公式；如果|=A成立，则A成立。1、 若FSPC的公式集是一致的，那么是可满足的，且其逆亦真。充分性：已知是一致的，证明是可满足的。4、 FSPC紧致性：FSPC具有紧致性，即对于FSPC的公式集合，如果其所有的有穷子集为可满足的，则是可满足的。已知：所有的有穷子集都是可满足的求证：为可满足的假设为不可满足的，由于上边的定理，可知是不一致的。因此，|-A,又可以推导出|-A因此，A和A都同时存在证明序列。假设证明分

23、别为：A1,An Ai或者为公理，或者为中的元素，或者为推理规则得到。1B1,BmBi或者为公理，或者为中的元素，或者为推理规则得到。2可满足，证明：任意FSPC的公式集合，其所有有穷子集为可满足的；假设为不可满足的，则为不一致的，即存在公式A，使得：A，A同时成立；由FSPC的完备性，可知：A，A同时成立。因此，存在A和A的证明序列。假设A的证明序列中，包含的公式组成的集合为1，假设A的证明序列中包含的公式组成公式集合为2；则1A，2A，同时成立。A；因此，为不可满足的。与题设矛盾，因此为可满足的。形式化和演算：语义：元理论：简化：计算机推理：3.9 总结3.9.1 主要内容回顾1. 形式系统的结构符号公式 可判定递归集合公理 独立性，完全的，一致的，可判定推理规则 分离规则，是n元关系2. 命题逻辑系统Ø 符号：命题变元，联结词（），技术符号，（，）Ø 公理：A1 A2 A3 Ø 公式：递归集合Ø 推理规则：A，AB，B3. 语义： *结构（U，Z）P(X)àQ(F(x) 赋值：Atomic,映射范式，完备集的概念4