§4一般逻辑系统 定义18.17:一个逻辑L是由下述集合所组成的系统：元素(称为命题)集P；函数集V(这些函数都是从P到某个值集W的，称为赋值.特别若|W|>2则称L为多值逻辑系统);以及对应于P的每个子集A导出P中元素的有限序列集(称为由前提A得到的证明)。

Presentation on theme: "§4一般逻辑系统 定义18.17:一个逻辑L是由下述集合所组成的系统：元素(称为命题)集P；函数集V(这些函数都是从P到某个值集W的，称为赋值.特别若|W|>2则称L为多值逻辑系统);以及对应于P的每个子集A导出P中元素的有限序列集(称为由前提A得到的证明)。"— Presentation transcript:

1 §4一般逻辑系统 定义18.17:一个逻辑L是由下述集合所组成的系统：元素(称为命题)集P；函数集V(这些函数都是从P到某个值集W的，称为赋值.特别若|W|>2则称L为多值逻辑系统);以及对应于P的每个子集A导出P中元素的有限序列集(称为由前提A得到的证明)。

2 例如：X上命题演算的逻辑，记为Prop(X)，它是由集合P=P(X)(X上自由命题代数)，所有的P(X)到Z2同态映射集V，以及满足定义18
例如：X上命题演算的逻辑，记为Prop(X)，它是由集合P=P(X)(X上自由命题代数)，所有的P(X)到Z2同态映射集V，以及满足定义18.13的证明集组成，后者包含从P(X)的每个子集A导出P(X)中元素的有限序列(称为由假设A得到的证明)集。

3 在逻辑L中，语义蕴含由赋值所定义，记号A╞p读成“A语义蕴含p”或称“p是A的后件”，语法蕴含由证明所定义，记号A┣p读成“A语法蕴含p”或称“p是A的推导”。若╞p，则称p是L的重言式；若┣p，则称p是L的定理。 定义18.18:如果A┣p必有A╞p，则称逻辑L是可靠的(sound)。 定义18.19:如果F不是L的定理，则称逻辑L是协调的(consistent)。

4 定义18.20:如果A╞p必有A┣p，则称逻辑L是完备的(complete)。
可靠性和完备性把真值和证明联系起来，而协调性则是纯语法性质，即任何逻辑都不会导致矛盾。 定义18.21:如果存在一个算法，对逻辑L的每个命题p，能在有限步内确定p是否为重言式，则称逻辑L是有效性可判定的。 定义18.22:如果存在一个算法，对逻辑L的每个命题p,能在有限步内确定p是否为定理，则称逻辑L是可证明性可判定的

5 §5 命题演算的性质 定理18.8(可靠性定理):设AP(X),pP(X)。若A┣p，则有A╞p。简言之：Ded(A) Con(A)。
证明：设p1,…,pn=p是从A推导p的证明序列，要证明的是p为A的后件。 设v是P(X)到Z2的赋值，且v(A){1}，施归纳于证明序列长度n。 n=1，则p=p1，故pA∪A，由习题18.6知每个公理都是重言式，且v(A){1}，所以v(p)=1。

6 现假设n>1，且对任何nk，若p可从A用 nk步证明序列推出，必有A╞p。
pn=p有下述两种情况: (i)pnA∪A，因此有v(pn)=1， (ii)对某个i,j<n，有pi=pjpn，此时 v(pi)=v(pjpn)，由v的同态性质知： v(pi)=v(pj)v(pn)，故v(pn)=1。

7 推论20.3:(协调性定理):F不是Prop(X)的定理。

8 定义18.23:设AP(X),若FDed(A)，则称A是协调的。若A是协调的，且对任何BP(X)，当B真包含A时，B必定不协调，则称A是极大协调子集。

9 引理18.3:设AP(X)，则A是极大协调子集当且仅当
(i)FA，并且 (ii)A=Ded(A)，并且 (iii)对所有的pP(X)，或者pA或者pA。 证明:(1)A是极大协调子集,则(i),(ii) 和(iii)成立. (2) 若(i),(ii)和(iii)成立,则A是极大协调子集.

10 引理18.4:设A是不协调的，则存在A的有限子集是不协调的。
引理18.5:设A是P(X)的协调子集，则A必被某个极大协调子集所包含。 用构造方法 (1)构造一组协调子集序列n和* (2)证明n是协调的 采用归纳法 (3)证明*是极大协调子集 先证*是协调的,采用反证法 再证*是极大的

11 定理18.9(可满足性定理):设A是P(X)的协调子集，则存在赋值v:P(X)Z2，使得v(A) {1}。
0元运算:v(F)=0 二元运算: (1)qM (2)pM (3)pM, qM

12 定理18.10(完备性定理):设AP(X),pP(X)，若在Prop(X)中有A╞p，则在 Prop(X)中有A┣p。
引理18.6:设w=w(x1,…,xn)P(X)，则╞w当且仅当w的真值函数fw是常值函数1。 定理18.11:Prop(X)的有效性是可判定的 推论18.4:Prop(X)是可证明性可判定的。

13 x>3,就无法用命题的形式来表示， 含有变量。 不能断定x>3是真还是假。 只有用变量x代之以具体的值时， 如以5代替x的值时：就变成5>3,这是一个真命题。 而当x取值为2时，就是2>3，成了一个假命题。

14 在数学中有下面三个命题： P： 所有的有理数都是实数。 Q： 3是有理数。 所以 R：3是实数。 当前面两个命题为真时，可得出第三个命题也是真的。即第三个命题是前两个命题的逻辑推论。 用符号P,Q,R分别表示这三个命题，则应有{P,Q}╞R， 但在命题逻辑中是无法得出此结论的。 需要引进新的逻辑系统——谓词逻辑

15 作业: P