高级数理逻辑第2讲

1、3 命题逻辑形式系统（FSPC）3.1 命题逻辑与命题演算Leibniz提出逻辑推理变成符号演算不久，英国数学家BOOL提出了布尔代数。布尔代数把逻辑命题与逻辑推理归结为代数计算。把命题看作是计算对象；把联结词看作算子；讨论计算的性质。1、 命题（Propositions）：可以判断真假的陈述句。不涉及任何联结词的命题称为原子命题。2、 联结词：, , , , 为联结词，用于联结一个或者多个命题。A=1-A如果A成立则B成立，如果A成立则B成立，并且如果B成立则A成立；ABAB，或者A成立或者B成立；AB，A成立并且B成立。3、 真值表：命题的真假称为命题的真值，用0表示假；用1表示真。ABT

2、(A)=1-T(A) A=1, A=0, 1-ATrue(A)1- True(A)，如果True(A)0，True(A)=1：True(A)=1, True(A)0T(AB)=1 或者A不成立，或者B成立； A=1, B=1, AB =1A=0, B=1, AB=1A=0, B=0, AB=1A=1,B=0 AB=0或者A=0, 或者B1 AvB=ABA=B;A=BA=0,B=1A=0时，B=?,1;A=1,B=1,1;A=1,B=0,0;A=0,B=0,T(AB)=1;A=0,B=1,T(AB)=1;A=1,B=0,T(AB)=1;A=1,B=1,T(AB)=1;A=0;T(AB)=1B=1

3、;T(AB)=1AB是或者A=0,或者B=1；=AvBAB)：True（A）True（B）A0,1；如果True(A)=1,则 True（B）=1,True(A-B)=1:或者True(A)=0或者True(B)=1：或者A不成立，或者B成立=AB；如果True(A)=0,则 True（B）=0，1；True(A)=True（B）；True(A) =True(B)，True(AB)=1；True(AB);A=1,B=0,1,A=1,B=1, 1;A=0,B=0,0,A=0,B=1,1.True(AB),A=1,B=0,0,A=1,B=1,1;1=0,B=0,0; A=0,B=1,0True(A

4、B)=max(True(A), True(B); True(AB)= min(True(A), True(B);4、 命题变元：以真值为值域的变量称为命题变元。T(A)-0,15、 赋值映射：命题变元集合到0,1上的函数。如果公式A对任意的赋值映射，取值为真，则称A为永真式TAUTLOGY。如果公式A对于所有赋值映射为假，称为A为矛盾式。对于任意赋值映射，公式A的真值等于公式B的真值，成A与B等价。(A(BC)(AB)(AC)=1AA 1 A(BA)= A=0, 1; A=1, 1;A&A =0T(AB)= T(AVB)A1A1=1=A1VA1A1A1=A1AA (AA)(AA) .AA AB

5、 或者A,或者A命题逻辑有以下特点：1、 从语义角度研究逻辑命题之间真值变化规律。对于任意公式可以给出其所有的真值可能性。2、 存在永真式，例如：等。3、 永真式通过三段论推理方法得到的公式，仍然为永真式。基于这样的事实，提出一个问题“是否有永真式的最小集合？”。答案是肯定的。公理方法的出现，使人们开始用公理方法研究逻辑系统。于是产生了命题逻辑形式系统。ABC(AVB)C000100110100011110001011110011113.2 命题逻辑形式系统（FSPC）PC最著名的形式化系统可能源于Whitehead和Russell 的数学原理(Principia Mathematica)。3

6、.2.1 FSPC定义1、 语言部分（1）符号集：（, ）, , , ,p1 ,p2 ,p3. ，其中, , , 为联接词；（，）为技术符号，即括号；p1 ,p2 ,p3为命题变量（命题变元或者命题符号）。（2）项集：为空集。（3）公式集合：公式集合有以下递归定义。I. p1 ,p2 ,p3（命题变元）为公式，称为原子公式。II. 如果A、B为公式，那么（），（），为公式。III. 所有的公式都是由1和2有限步骤得到的，除此之外没有公式。语言部分定义了FSPC的公式（语言）产生规则。2、 推理部分（1）公理：FSPC包含下列三个公理模式：I A1II A2 III A3 -(A-A) ( )(

7、AA)A(AA)(A(BC)(AB)(AC)(A(BA)(AB)(AA)(A(AA)A)(A(AA)(AA)A(AA)A)(A(AA)(AA)(A(AA)AA(AB)(AA)B(AB)C(BA)AB形式化：ABAB111100001011语义上的理解(如果A成立，则B成立)如B(AA)(如果x是实数，则x2大于等于0B)AB001011101111A(x为实数)B(x2大于等于0)如果(x不是实数)则x2不一定大于0在x不是实数(A=0)的情况下；AB是否成立？1如果（x如果是超出4中数定义之外的数）则x2大于0(2) 推理规则集合：只有一条推理规则，称为分离规则：分离规则（modus pon

8、eus）3.2.2 公式结构1、公式产生序列：l 对于一个上的字符串A是公式的充分必要条件是存在一个公式序列其中为（1）到（3）中的一种：（1）：为原子公式（2）：存在，使得（3）：存在，使得l 公式生成过程举例：例如公式：，的生成过程。（1）首先p、q、r为公式（原子公式）p, q, r, p, q, r, pq, qr, rp, p( qr),（2）（）、为公式（3）为公式（4）公式我们有树能够更清晰地给出公式的生成过程：为公式 3、公式结构特点（1）括号是在公式中，是成对出现，左右括号数量相同。（2）在自然逻辑中，公式有否定式、合取式、析取式、蕴涵式、等值式等不同类型的概念。（3）由于公

9、式采用递归定义的方法来定义，因此，对上的任意字符串能够判断是否为公式。（4）形式系统的联结词只有两个，因为在命题逻辑的语义上，其他联结词可以有这两个联结词表示。 , &（5）由于公式是采用递归定义方式来定义的，因此，对于公式的性质通常采用递归证明方法来证明。例如：归纳法证明：R证明其在自然数集成立， （1）证明，当1的时候，R成立（2）假设，当K的时候，R成立（3）证明，当k+1的时候R成立设：R是一个有关公式的性质，如果要证明R对于所有公式有效则通过下面的证明步骤：I. 对于，则II. 假设公式A和B都具有RIII. ，且，则IV. 是公式，如果且，则由以上三条，可知R对于FSPC上的所有公

10、式成立。3.3 命题形式演算3.3.1 形式演算1、概念：演绎结果与定理：设A为FSPC上一公式，集合为FSPC上一公式集合。称A为的演绎结果，记为，如果存在一个公式序列：A1, A2, A3, A4, A使得或者为形式系统FSPC的公理，或者为公式集合中的元素，或者为由推理规则r得到；则称A为FSPC的演绎结果。当时，称A为定理FSPC上的定理。称为A的证明序列。逻辑等价：公式A和B分别为两个公式，如果A,B满足B，且AB同时成立，则称公式A和B为逻辑等价公式，记为AB。即A,B互为演绎结果。AvB=ABA,A2,B:B,A2,.,A例如：|，|，|。对偶：设A为FSPC上由联结词, , 和

11、原子公式构成的公式。在A中交换和，以及原子公式和他的否定公式，得到公式，则称为A的对偶。True(AB)=True(AB)=( AB)(AB) 2、形式演算举例例：证明为FSPC的定理。证明：（1） A1 ：（2） A2 ：（3）A1 ：（4） （1）（2）（5）（3）（4）已知求证A成立A3.3.2 形式演算方法1、主要的证明方法与手段形式演算方法多种多样，通常有以下方法：（1） 公理代入原理：设A(P)为含有变元P的公理（定理同样适用），如果将公式A中的变元P替换为命题变元B，则A(B)仍为公理（定理）；（公理填充）A-(B-A), A-(A-A)-A)（2）等价替换原理：设命题公式A含有

12、子公式C（C为命题公式），如果CD，那么将A中子公式C提换为命题公式D（不一定全部），所得公式B满足AB。（3）对偶原理：设A为FSPC上的公式，为其对偶，则A。（4）形式演算规则：在FSPC之上，利用分离规则扩展的推理规则。例如：AA（自反规则）；如果A，则A，其中为一个公式集合（引入规则）等。这样扩充后的系统被称为自然推理系统。(公理比较多，连接词贴近自然语言)（公理只有3个，连接词少计算机可以使用）（5）联结词运算规则：针对联结词的运算规律。例如：交换律、结合律、莫根定律等。对于（1）是对于任何证明序列所必须的。其他的定律都可以由分离规则产生。2、不同类型的证明方法在命题演算时，主要是证

13、明以下问题：1) 命题2) 命题3) 命题4) 命题5) 命题6) 命题针对这些要证明的问题，通常有以下方法来证明：1) 命题：l 自反规则：l 证明，只需证明0中，0l 销去：如果 则（分离规则）l 销去（反证法）：如果， ， 则-BA1,A2,A3=A1A2A3(BB)-(A-B-C)l 包含：l 销去：如果则2) 命题 （同上）3) 命题 ，则）（演绎定理）A1,An=AB, A,B;4) 命题5) 命题如果或者或者B则6) 命题如果并且B则例：证明：（1），包含（2），包含（3）（反证规则）3.3.3 形式演算性质形式演算主要有以下特点：1) 紧致性：设为FSPC上的公式集合，A为FS

14、PC的公式。如果，则存在的有限子集0 使得0 。由已知，存在A的一个证明序列：A1,.Am=A;其中，Ai或者是公里，或者是中的元素，或者是由i前边的通过分离规则得到的。Ai, Aj= 0我们将这个证明序列中，所有中的元素抽取出来构成新的集合：0，这个0 是 的子集。A1,.Am是由0 证明A的一个证明序列。所以，0 可以推倒出A来。A1,A2,A3,A4=A假设A1公理，A2是,A3是分离得到，A4=A,分离规则A2AA2,A3,A5,A6,A,A2A A2) 传递性：设和1为FSPC上的公式集合，A为FSPC的公式。如果1 ，1；则成立。B1,B2,B3=1=B1B2B3公式集合公式|-B

15、1 A11, A1,2, ., A1m=B1 A2,1., A2m=B2 A31,.,A3m=B3B0, A11, A1,2, ., A1m,B2,B3 ,B4, Bn =A由于1 可以推倒出A来，因此存在一个证明序列：A1An=A，其中Ai或者为公里，或者为1 中的元素，或者为前边的公式推倒出来的。假设Aj是1 元素且是证明中的元素。只要证明存在一个1 中的证明序列可以证明Aj就可以了。由于已知，因此对于每个1 的元素都存在一个 上的证明序列。因此，Aj存在一个 上的证明序列的。将所有的A1An证明序列中，属于1 的元素的证明序列按照先后顺序排成一个证明序列，那么这个证明序列就是由 推导A的

16、一个证明序列。因此， 可以推导出A，AA1,A2,A3,A4=B1,B2=1C1,C2,B1,C3,B2,AC4,A2,A1,B1C5,A3,A4,A2,B2C1,C2,C4,A2,A1,B1,C3,C5,A3,A4,A2,B2,A例：证明（1）前提（2）A1 （3）（1）（2）分离规则（4）(AA)(AA)A3（5）（3）（4）（6）A3（7）（5）（6）（8）* 公理推演系统模式单一，易于机械化，而推理过程复杂。* 自然推演系统，模式复杂，相对证明过程简单。证明：已知A(BC), B, 证明:AC是已知的逻辑结果。A(BC),B,A C（1） A(BC) 前提（2） A 前提（3） BC 1,2分离（4） B 前提（5） C 3，4分离证明：只需证明对于任何赋值映射f，如果f使得f(A(BC)=1,并且f(B)=1,则f使得f(AC)=1。由已知可以知道：f(B)=1,f(A)=0或者f(BC)=1。因此分两种情况：1、假设f(A)=0;则f(AC)=1.2、假设f(A)!=0,那么f(BC)=1.f(B)=1,则f(C)=1.因此，f(AC)=1.由此，命题成立。证明：A(BC), B, A，证明CA(BC)1B2A3BC 4（1，3）C5（2，4）证明：如果A(BC), B成立，则AC成立。题目：如果一个赋值映射