离散数学 教学课件 作者 赵一鸣 阚海斌 吴永辉 dshu24n.ppt

《离散数学 教学课件 作者 赵一鸣 阚海斌 吴永辉 dshu24n.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§4一般逻辑系统定义18.17:一个逻辑L是由下述集合所组成的系统：元素(称为命题)集P；函数集V(这些函数都是从P到某个值集W的，称为赋值.特别若

2、W

3、>2则称L为多值逻辑系统);以及对应于P的每个子集A导出P中元素的有限序列集(称为由前提A得到的证明)。例如：X上命题演算的逻辑，记为Prop(X)，它是由集合P=P(X)(X上自由命题代数)，所有的P(X)到Z2同态映射集V，以及满足定义18.13的证明集组成，后者包含从P(X)的每个子集A导出P(X)中元素的有限序列(称为由假设A得到的证明)集。在逻辑L中，语义蕴含由赋值所定义，记号

4、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)。定义18.20:如果A╞p必有A┣p，则称逻辑L是完备的(complete)。可靠性和完备性把真值和证明联系起来，而协调性则是纯语法性质，即任何逻辑都不会导致矛盾。定义18.21:如果存在一个算法，对逻辑L的每个

5、命题p，能在有限步内确定p是否为重言式，则称逻辑L是有效性可判定的。定义18.22:如果存在一个算法，对逻辑L的每个命题p,能在有限步内确定p是否为定理，则称逻辑L是可证明性可判定的§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)

6、{1}，所以v(p)=1。现假设n>1，且对任何nk，若p可从A用nk步证明序列推出，必有A╞p。下面就是证明对n=k+1也成立。pn=p有下述两种情况:(i)pnA∪A，因此有v(pn)=1，(ii)对某个i,j

7、则称A是极大协调子集。引理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是极大协调子集.引理18.4:设A是不协调的，则存在A的有限子集是不协调的。引理18.5:设A是P(X)的协调子集，则A必被某个极大协调子集所包含。用构造方法(1)构造一组协调子集序列n和*(2)证明n是协调的采用归纳法(3)证明*是极大协调

8、子集先证*是协调的,采用反证法再证*是极大的定理18.9(可满足性定理):设A是P(X)的协调子集，则存在赋值v:P(X)Z2，使得v(A){1}。构造P(X)Z2的函数v,证明所构造的v是赋值(即为同态映射)0元运算:v(F)=0二元运算:(1)qM(2)pM(3)pM,qM定理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)的

9、有效性是可判定的推论18.4:Prop(X)是可证明性可判定的。x>3,就无法用命题的形式来表示，含有变量。不能断定x>3是真还是假。只有用变量x代之以具体的值时，如以5代替x的值时：就变成5>3,这是一个真命题。而当x取值为2时，就是2>3，成了一个假命题。在数学中有下面三个命题：P：所有的有理数都是实数。Q：3是有理数。所以R：3是实数。当前面两个命题为真时，可得出第三个命题也是真的。即第三个命题是前两个命题的逻辑推论。用符号P,Q,R分别表示这三个命题，则应有{P,Q}╞R，但在命题逻辑中是无法得出此结论的。需要引进新的逻辑系统——

10、谓词逻辑作业:P24114