北邮高级数理逻辑课件.docVIP

形式系统 形式系统由{∑, TERM, FORMULA, AXIOM, RULE}等5个部分构成，其中 称为符号表，TERM为项集；FORUMULA为公式集；AIXIOM为公理集；RULE为推理规则集。： 符号表∑为非空集合，其元素称为符号。 设∑为∑上全体字的组合构成的集合。项集TERM为∑的子集，其元素称为项；项集TERM有子集VARIABLE称为变量集合，其元素称为变量。F(X) a, X, 设∑为∑上全体字的组合构成的集合。公式结FORMULA为∑的子集，其元素称为公式；公式集有子集ATOM，其元素称为原子公式。 A(f(a,x1,y)), A?B 公理集AXIOM是公式集FROMULA的子集，其元素称为公理。 推理规则集RULE是公式集FORMULA上的n元关系集合，即RULE=，其元素称为形式系统的推理规则。 其中公式集和项集之间没有交叉，即TERM∩FORMULA =φ，公式和项统称为表达式。 由定义可知，符号表∑、项集TERM、公式集FORMULA是形式系统的语言部分。而公理集AXIOM、推理规则集RULE为推理部分 形式系统特性 符号表∑为非空、可数集合（有穷、无穷都可以）。 项集TERM、公式集FORMULA、公理集AXIOM和推理规则集RULE是递归集合，即必须存在一个算法能够判定给定符号串是否属于集合（可判定的）。 形式系统中的项是用来描述研究的对象，或者称为客观世界的。而公式是用来描述这些研究对象的性质的。这个语言被称为对象语言。定义公式和项产生方法的规则称为词法。 公理： 证明：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对于所有公式有效 对于，则 假设公式A和B都具有R ，且，则 是公式，如果且，则 根据：形式系统的联结词只有两个，因为在命题逻辑的语义上，其他联结词可以有这两个联结词表示。 已知： 求证：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) A B?C B C 自然推演： 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?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?A) (A?B)?(A?B)?(A?B) 语义构成 结构：（有两个主要部分构成） *确定研究对象集合，论域或个体域 *把形式系统中的变量到论域中的一组规则映射规则 域值：指一组给公式赋值的规则 根据这项规则将 －AtomicValue中 语义的特殊公式 公式A为永真式，重言式tautologies，如果对一切赋值，. 公式A为永假式，矛盾式contradictions,如果对一切赋值， A，B为逻辑等价的，如果对于一切赋值，，记做A╞B(A|=|B) 公式A为可满足的，如果至少存在一个赋值， 逻辑推论：设是一个FSPC上的公式集合，A是FSPC上的任一公式。A为的逻辑结果，记做|=A，当且仅当对任何赋值映射v，如果＝1时，则。|=读作逻辑蕴涵。 逻辑等价：设公式A和公式B分别为FSPC上的两个公式。A和B为逻辑等价的，记做A|=|B当且仅当A|=B和B|=A同时成立。 永真式：如果A为永真式，则公式集合为空集，即|=A。 演绎定理： 设为FSPC的公式集合，A和B分别为FSPC上的公式。|=成立的充分必要条件是：|=。 证明： 从语义上： 必要性： 由于f1()=1，则f1(A?B)=1; 由于f1(A?B)=1,并且f1(A)=1，则f(B)=1 充分