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

《命题逻辑的公理系统-进一步的讨论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，下面两个命