高级数理逻辑02

3 命题逻辑形式系统（FSPC）

3.1 命题逻辑与命题演算

Leibniz提出逻辑推理变成符号演算不久，英国数学家BOOL提出了布尔代数。布尔代数把逻辑命题与逻辑推理归结为代数计算。把命题看作是计算对象；把联结词看作算子；讨论计算的性质。

1、 命题（Propositions）：可以判断真假的陈述句。不涉及任何联结词的命题称为原

子命题。

2、 联结词：?, ?, ?, ?, ?为联结词，用于联结一个或者多个命题。

~A=1-A

?如果A成立则B成立，<->如果A成立则B成立，并且如果B成立则A成立； A?B

A?B，或者A成立或者B成立；A?B，A成立并且B成立。

3、 真值表：命题的真假称为命题的真值，用0表示假；用1表示真。

A??B

T(~A)=1-T(A) A=1, ~A=0, 1-A

True(?A)＝1- True(A)，如果True(A)＝0，True(?A)=1：True(A)=1, True(?A)＝0

T(A?B)=1 或者A不成立，或者B成立； A=1, B=1, A?B =1 A=0, B=1, A?B=1 A=0, B=0, A?B=1 A=1,B=0 A?B=0

或者A=0, 或者B＝1 ~AvB=A?B A<=B;;;; A<=B A=0,B=1

A=0时，B=?,1;A=1,B=1,1;A=1,B=0,0;

A=0,B=0,T(A?B)=1;A=0,B=1,T(A?B)=1;A=1,B=0,T(A?B)=1;A=1,B=1,T(A?B)=1;

A=0;T(A?B)=1 B=1;T(A?B)=1

A?B是或者A=0,或者B=1；=～AvB A<=B

A?B=MAX(A,B) A=1, B=0, 1;A=1,B=1, 1, A=0,B=1;1, A=0,B=0, 0 A?B=MIN(A,B) =~(~A v ~B) DEMORGAN ~A ?B

True(A->B)：True（A）《＝True（B）

A＝0,1；如果True(A)=1,则 True（B）=1,True(A->B)=1:或者True(A)=0或者True(B)=1：或者A不成立，或者B成立=?A?B；如果True(A)=0,则 True（B）=0，1；True(A)=B)=1； True(A?B);A=1,B=0,1,A=1,B=1, 1;A=0,B=0,0,A=0,B=1,1. True(A?B),A=1,B=0,0,A=1,B=1,1;1=0,B=0,0; A=0,B=1,0

True(A?B)=max(True(A), True(B)); True(A?B)= min(True(A), True(B)); 4、 命题变元：以真值为值域的变量称为命题变元。T(A)-----{0,1}

5、 赋值映射：命题变元集合到{0,1}上的函数。如果公式A对任意的赋值映射，取

值为真，则称A为永真式TAUTLOGY。如果公式A对于所有赋值映射为假，称为A为矛盾式。对于任意赋值映射，公式A的真值等于公式B的真值，成A与B等价。

(A?(B?C))?((A?B)?(A?C))=1

A?A 1 A?(B?A)= A=0, 1; A=1, 1; A&~A =0

T(A?B)= T(~AVB) A1?A1=1=~A1VA1 ~A1?A1=A1

A?A (A?A)?(A?A) ......

A?A A?B 或者~A,或者A

命题逻辑有以下特点：

1、 从语义角度研究逻辑命题之间真值变化规律。对于任意公式可以给出其所有的

真值可能性。 2、

存在永真式，例如：P??P,P?P等。

3、 永真式通过三段论推理方法得到的公式，仍然为永真式。 基于这样的事实，提出一个问题“是否有永真式的最小集合？”。答案是肯定的。公理方法的出现，使人们开始用公理方法研究逻辑系统。于是产生了命题逻辑形式系统。

A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 (AVB)?C 3.2 命题逻辑形式系统（FSPC）

PC最著名的形式化系统可能源于Whitehead和Russell 的《数学原理》(Principia Mathematica)。

3.2.1 FSPC定义

1、 语言部分

（1）符号集：∑＝{（, ）,? , ?, ,p1 ,p2 ,p3…….} ，其中?, ?, ?, ?,

（，）为技术符号，即括号；p1 ,p2 ,p3……为命题变量（命题变元或?为联接词；

者命题符号）。

（2）项集：为空集。

（3）公式集合：公式集合有以下递归定义。

I. p1 ,p2 ,p3……（命题变元）为公式，称为原子公式。 II. 如果A、B为公式，那么（?A），（A?B），为公式。

III. 所有的公式都是由1和2有限步骤得到的，除此之外没有公式。

语言部分定义了FSPC的公式（语言）产生规则。

2、 推理部分

（1）公理：FSPC包含下列三个公理模式：

I II III

( )?(A?A) 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

(A?B)?(A?A)

B?>(A?B)

A1

(A?(B?A))

A2 ((A?(B?C))?((A?B)?(A?C)) A3 (((?A)?(?B))?(B?A))

C?(B?A)

A?B 形式化： A 1 1 0 0 B 1 0 0 1 A?B 1 0 1 1

语义上的理解

(如果A成立，则B成立)

如B?(A?A)

(如果x是实数，则x2大于等于0B) A 0 0 1 1 B 0 1 0 1

A(x为实数)?B(x2大于等于0)

如果(x不是实数)则x2不一定大于0 在x不是实数(A=0)的情况下；

(A?(B?A)) 1 1 1 1