命题逻辑的公理系统-进一步的讨论2new

命题逻辑的公理系统-进一步的讨论2new

ID:21671469

大小:36.50 KB

页数:5页

时间:2018-10-23

命题逻辑的公理系统-进一步的讨论2new_第1页
命题逻辑的公理系统-进一步的讨论2new_第2页
命题逻辑的公理系统-进一步的讨论2new_第3页
命题逻辑的公理系统-进一步的讨论2new_第4页
命题逻辑的公理系统-进一步的讨论2new_第5页
资源描述:

《命题逻辑的公理系统-进一步的讨论2new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、[N与P的等价性]自然演绎系统N和公理系统P中的形式推演具有等价性。[定理]如果G├PA则G├NA(其中├P和├N分别表示推演在P中或在N中进行)。[证明][定理]如果G├NA则G├PA。[证明][命题演算P的解释]我们之前关于P的研究是语法性质的,只涉及到符号或符号串之间的形式关系,并未涉及符号或符号串的意义。下面给出的是P在命题逻辑下的解释,使P成为一个关于命题逻辑的演绎系统,P中公式表示命题形式,P中定理表达命题逻辑的有效推理形式或逻辑规律。相关研究称为P的语义理论(或赋值理论)。在建立P的语言时,我们把P的第一类符号p1,p

2、2,…解释为命题变元,命题的真值非“真”即“假”,并分别以符号T和F表示。把第二类符号Ø和®分别称为否定词和蕴涵词,解释为命题联结词。在这样的解释下,P的每一公式不再是纯粹的符号组合,而拥有了真值意义。在确定一个公式中出现的命题变元的真值后,可以根据联结词的意义确定这个公式的真值。对命题变元指定确定的真值称为对命题变元的真值指派。根据上面的直观的解释,有下面的定义:[定义]对P的公式的一个真值赋值s是对P的每一公式A指定一个真值As(读做“赋值s下A的值”,取值非真即假)的一个映射,即从P的公式集合Fp到{T,F}上的一个映射s:F

3、p®{T,F},使得(1)对每个原子公式(命题变元)指派一个真值;(2)(ØA)s=T当且仅当As=F;(3)(A®B)s=T当且仅当As=F或者Bs=T。Ø上述定义的(2)(3)可用真值表的形式表示。公式含有的所有命题变元获得解释后,通过真值表可以获得公式的真值。[定义]设s是P的一个真值赋值,F是P的一个公式集合。如果对每个AÎF,都有As=T,则说s满足F,记作s╞F。如果存在一个真值赋值s,使得s╞F,就说公式集合F是可满足的。如果F是只有一个公式A组成的集合,可以将s╞{A}简记为s╞A。如果存在一个真值赋值s,使得s╞A

4、,就说公式A是可满足的。[定义]P的一个公式A称为重言式(永真式),如果对P的任意一个真值赋值s,都有As=T。[定义]P的一个公式A称为矛盾式(永假式/不可满足式),如果对P的任意一个真值赋值s,都有As=F。[定理]P的公式A是一个重言式,当且仅当ØA不可满足。[证明][定理]P中的公理都是重言式。[证明]从真值表易知。[定理]设A、B都是P中公式,若A和A®B都是重言式,则B也是重言式。[证明][定理](代入定理同样成立)[定理](等值置换定理同样成立)[定义]如果P的任意一个满足公式集F的真值赋值s(s╞F)都能满足公式A(

5、s╞A),那么称A是F的重言继承(A是F的逻辑推论/F可逻辑推出A),记作F╞A(或FÞA)。如果A是空的公式集Æ的重言继承,可以将Æ╞A简记作╞A。[定理]公式A是重言式当且仅当╞A。[证明]Ü空集中没有公式,没有一个P的真值赋值s会使得空集中的公式的值是F,即每一s都满足空集。A是空集的重言继承,所以每一s都满足A,即A是一个重言式。Þ反过来,如果A是重言式,P的每一s都满足它,A可以是任何公式集的重言继承,因此也是空集的重言继承。要证明一个公式A不是公式集F的重言继承,只需找到一个P的赋值s,s能够满足F中的每一公式(s╞F)

6、,但不能满足A(非s╞A)。注意“非s╞A”和“s╞ØA”是有区别的。重言继承关系与可满足性之间有下面定理陈述的关系:[定理]对于P的公式集F和公式A,F╞A当且仅当FÈ{ØA}不可满足。[证明][定理]P的公式B是{A1,A2,...,An}的重言继承当且仅当公式A1®(…(An®B)…)是一个重言式。[证明][定义]P的两个公式A和B是重言等值(逻辑等值)的如果它们是彼此的重言继承。即对P中任意的赋值s,As=Bs。[P系统的可靠性和协调性][引理]对P的两个公式A和B,有A,A®B╞B。[证明]引理表明,在保真性的意义下,即“

7、如果As=(A®B)s=T,则Bs=T”,分离规则是可靠的。应用分离规则从真的前提确实得出了真的结论。[可靠性定理]对P的公式集F和P的公式A,如果F├A,则F╞A。特别地,如果├A,则╞A。(这里的“├”指P上的推演)[证明]可靠性定理表明命题演算P是可靠的:命题演算P在反映命题逻辑范围内的推理规律方面是可靠的,P的定理都是重言式。一个命题形式如果应用P所提供的工具从一定的前提可推演,那么它一定是这些前提的重言继承。可靠性定理也表明命题演算P是协调的:在P中不可能推出逻辑矛盾。[定义]一个公式集F是协调的,如果不存在一个公式A,使

8、得F├A并且F├ØA。(或:一个系统是协调的,如果不存在一个系统的公式A,使得A和ØA在系统中都是可证的。)[定理]命题演算P是协调的。[证明][定理]P的任何可满足的公式集合都是协调的。[证明][定理]对公式集F和公式A,下面两个命

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。