资源描述：
《北邮高级数理逻辑课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、形式系统形式系统由{∑,TERM,FORMULA,AXIOM,RULE}等5个部分构成，其中称为符号表，TERM为项集；FORUMULA为公式集；AIXIOM为公理集；RULE为推理规则集。：1、符号表∑为非空集合，其元素称为符号。2、设∑为∑上全体字的组合构成的集合。项集TERM为∑的子集，其元素称为项；项集TERM有子集VARIABLE称为变量集合，其元素称为变量。F(X)a,X,3、设∑为∑上全体字的组合构成的集合。公式结FORMULA为∑的子集，其元素称为公式；公式集有子集ATOM，其元素称为原子公式。A(f(a,x1,y)),AàB4、公理集AXIOM是公式集FROM
2、ULA的子集，其元素称为公理。5、推理规则集RULE是公式集FORMULA上的n元关系集合，即RULE=，其元素称为形式系统的推理规则。其中公式集和项集之间没有交叉，即TERM∩FORMULA=φ，公式和项统称为表达式。由定义可知，符号表∑、项集TERM、公式集FORMULA是形式系统的语言部分。而公理集AXIOM、推理规则集RULE为推理部分形式系统特性1、符号表∑为非空、可数集合（有穷、无穷都可以）。2、项集TERM、公式集FORMULA、公理集AXIOM和推理规则集RULE是递归集合，即必须存在一个算法能够判定给定符号串是否属于集合（可判定的）。3、形式系统中的项是用来描
3、述研究的对象，或者称为客观世界的。而公式是用来描述这些研究对象的性质的。这个语言被称为对象语言。定义公式和项产生方法的规则称为词法。公理：IIIIII证明：AàA(1)Aà(AàA)((Aà(BàC))à((AàB)à(AàC))((Aà(BàA))à((AàB)à(AàA))((Aà((AàA)àA))à((Aà(AàA))à(AàA))Aà((AàA)àA))(Aà(AàA))à(AàA)(Aà(AàA))AàA分离规则已知：R是一个有关公式的性质证明：R对于所有公式有效I.对于，则II.假设公式A和B都具有RIII.，且，则IV.是公式，如果且，则根据：形式系统的联结词只
4、有两个，因为在命题逻辑的语义上，其他联结词可以有这两个联结词表示。已知：求证：A成立(1)A是公式(2){，}├{，}├├反证(3)3公理代入原理：设A(P)为含有变元P的公理（定理同样适用），如果将公式A中的变元P替换为命题变元B，则A(B)仍为公理（定理）；（公理填充）等价替换原理：设命题公式A含有子公式C（C为命题公式），如果C├│D，那么将A中子公式C提换为命题公式D（不一定全部），所得公式B满足A├│B。紧致性：设为FSPC上的公式集合，A为FSPC的公式。如果├，则存在的有限子集0使得0├。已知：Aà(BàC),B证明：AàC公理推演：Aà(BàC)ABàCBC自然
5、推演：f(B)=1,f(A)=0或者f(BàC)=1。假设f(A)=0;则f(AàC)=1.假设f(A)=1,那么f(BàC)=1.f(B)=1,则f(C)=1.因此，f(AàC)=1.由此，命题成立。给出一个形式系统，其公理定义如下：{A,(,),à,}{}{---}给出公理如下：AàAAàAàA(AàA)à(AàA)(AàA)à(AàA)(A-->A-->A)-->(A-->A)下列哪些是定理？AàAà(AàA)(AàA)à(AàA)à(AàA)(AàAàA)à(AàAàA)(AàB)à(AàB)à(AàB)语义构成结构：（有两个主要部分构成）*确定研究对象集合，论域或个体
6、域*把形式系统中的变量到论域中的一组规则映射规则域值：指一组给公式赋值的规则根据这项规则将－AtomicValue中语义的特殊公式1)公式A为永真式，重言式tautologies，如果对一切赋值，.2)公式A为永假式，矛盾式contradictions,如果对一切赋值，3)A，B为逻辑等价的，如果对于一切赋值，，记做A╞B(A
7、=
8、B)4)公式A为可满足的，如果至少存在一个赋值，逻辑推论：设是一个FSPC上的公式集合，A是FSPC上的任一公式。A为的逻辑结果，记做
9、=A，当且仅当对任何赋值映射v，如果＝1时，则。
10、=读作逻辑蕴涵。逻辑等价：设公式A和公式B分别为FSPC上的两个
11、公式。A和B为逻辑等价的，记做A
12、=
13、B当且仅当A
14、=B和B
15、=A同时成立。永真式：如果A为永真式，则公式集合为空集，即
16、=A。演绎定理：设为FSPC的公式集合，A和B分别为FSPC上的公式。
17、=成立的充分必要条件是：
18、=。证明：从语义上：必要性：由于f1()=1，则f1(AàB)=1;由于f1(AàB)=1,并且f1(A)=1，则f(B)=1充分性：对于映射f，若f()=1，假设f1(A)=0;f1(AàB)=1.假设f1(A)=1,由于已知条件可以知道f(B)=1.因此，f(AàB)=1
