资源描述：
《北邮高级数理逻辑课件.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途形式系统形式系统由｛∑，TERM,FORMULA,AXIOM，RULE｝等5个部分构成，其中称为符号表，TERM为项集；FORUMULA为公式集;AIXIOM为公理集；RULE为推理规则集。：1、符号表∑为非空集合,其元素称为符号.2、设∑为∑上全体字的组合构成的集合。项集TERM为∑的子集，其元素称为项；项集TERM有子集VARIABLE称为变量集合,其元素称为变量。F(X)a，X，3、设∑为∑上全体字的组合构成的集合。公式结FORMULA为∑的子集，其元素称为公式；公式集
2、有子集ATOM，其元素称为原子公式。A（f（a,x1，y））,AàB4、公理集AXIOM是公式集FROMULA的子集,其元素称为公理。5、推理规则集RULE是公式集FORMULA上的n元关系集合，即RULE=，其元素称为形式系统的推理规则。其中公式集和项集之间没有交叉,即TERM∩FORMULA=φ，公式和项统称为表达式。由定义可知,符号表∑、项集TERM、公式集FORMULA是形式系统的语言部分。而公理集AXIOM、推理规则集RULE为推理部分形式系统特性1、符号表∑为非空、可数集合（有穷、无穷都
3、可以）。2、项集TERM、公式集FORMULA、公理集AXIOM和推理规则集RULE是递归集合，即必须存在一个算法能够判定给定符号串是否属于集合（可判定的）.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
4、à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.是公式，如果且，则根据：形式系统的联结词只有两个,因为在命题逻辑的语义上,其他联结词可以有这两个联结词表示。已知：求证：A成立（1)A是公式（2）{，}├{，｝├├反证(3)个人收集整理勿做商业用途3公理代入原理：设A(P）为含有变元P的公理（定理同样适用)
5、，如果将公式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自然推演：f(B)=1，f(A）=0或者f（BàC）=1。假设f（A)=0;则f(AàC）=1.假设f(A)=1，那
6、么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)语义构成结构：（有两个主要部分构成）＊确定研究对象集合,论域或个体域*把形
7、式系统中的变量到论域中的一组规则映射规则域值：指一组给公式赋值的规则根据这项规则将－AtomicValue中语义的特殊公式1)公式A为永真式，重言式tautologies,如果对一切赋值，。2)公式A为永假式，矛盾式contradictions,如果对一切赋值，3)A,B为逻辑等价的，如果对于一切赋值，，记做A╞B(A
8、=
9、B)4)公式A为可满足的，如果至少存在一个赋值,逻辑推论：设是一个FSPC上的公式集合,A是FSPC上的任一公式。A为的逻辑结果，记做｜=A，当且仅当对任何赋值映射v，如果＝1时
10、,则。
11、=读作逻辑蕴涵。逻辑等价：设公式A和公式B分别为FSPC上的两个公式。A和B为逻辑等价的，记做A｜=
12、B当且仅当A｜=B和B
13、=A同时成立。永真式：如果A为永真式，则公式集合为空集，即｜=A.演绎定理：个人收集整理勿做商业用途设为FSPC的公式集合，A和B分别为FSPC上的公式.
14、=成立的充分必要条件是:｜=。证明：从语义上：必要性：由于f1（)=1，则f1(AàB）=1;由于f1(AàB）=1,并且f1(A）=1，则f(B)=1充分性：对于映射f，若f（）=
