命题逻辑

研究由命题经使用命题连接词构成的更复杂的命题,以及这样构成的命题之间的推理关系。命题演算是命题逻辑形式系统(见逻辑演算),它是19世纪70年代至20世纪初,在对数学基础及数学推理规律研究的推动下最早建立起来的重要的、完备的逻辑演算系统。其奠基人当推(F.L.)G.弗雷格及其后的G.皮亚诺,B.A.W.罗素等。

在命题逻辑中,将被命题连接词组合的初始命题作为整体处理,即不再分析它们的内部结构,它们的性质只有真与假的区别。

在命题逻辑中通常使用五个命题连接词:“非(塡)”,“与(∧)”,“或(∨)”,“如果,则(→)”和“当且仅当(凮)”,它们依次称为“否定词”,“合取词”,“析取词”,“蕴涵词”和“等值词”。由命题A经使用否定词构成命题“非A”。由命题A和B经使用合取词,析取词,蕴涵词和等值词依次构成命题“A与B”,“A或B”,“如果A,则B,”和“A当且仅当B”。

这些更复杂的命题的真假性由构成它们的命题的真假性及命题连接词的性质决定。“非A”当A真时为假,当A假时为真;“A与B”当A和B都真时为真,否则为假;“A或B”当A和B都假时为假,否则为真;“如果A则B”当A真B假时为假,否则为真;“A当且仅当B”当A和B的真假性相同时为真,否则为假。

当一组命题Γ中的每个命题均为真时,命题A也必为真,则称A是Γ的逻辑推论,记为Γ喺A。“喺”表示逻辑推理关系。例如,A→B,A喺B;A喺A∨B等。一个命题A,无论其初始命题为真或假,A恒为真,则称A为重言式,记作喺A。例如喺A→(B→A);喺塡A∨塡A等等。

按照建立形式系统的一般原则(见逻辑演算),命题演算包括以下几个部分:

符号系统包括命题变元pq,…(表示初始命题的形式符号)及命题连接词,例如塡,∧,∨,→及凮等。

形成规则:

(1)每个命题变元是公式,称为原子公式。

(2)若A是公式,则塡A是公式,若AB是公式,则ABABABAB是公式。

公式表示命题,形成规则描述了在形式系统中怎样由简单命题用逻辑连接词构造复杂的命题。以上两部分称为命题演算的语言

可以取如下的公式作为命题演算的公理,例如: A→(BA), (AB)→((A→(BC)→(AC)), (AB)→((A→塡B)→塡A), 塡塡AA, (AB)→A,(AB)→B A→(B→(AB)), A→(AB),B→(AB), (AC)→((BC)→((AB)→C)),等。命题演算的推理规则可取为

公理和推理规则一经给定,命题演算的定理就完全确定了(见逻辑演算)。公式A 是命题演算的定理记为喩A

命题演算的公理表示永真的命题,即重言式。推理规则则保证,当假定被解释为真命题时,结论的解释也必为真命题。因此,命题演算的定理一定是重言式,即对于任意公式A,若喩A,则喺A。这个性质称为命题演算的有效性或可靠性,即形式推理可靠地反映了直观的逻辑推理。

反之,若公式A为重言式,则A必为命题演算的定理,即若喺A,则喩A。这个性质称为命题演算的完备性,即形式推理完全反映了命题逻辑中的直观推理而无遗漏。是E.L.波斯特于1921年首先证明的。

可靠性与完备性刻画了命题演算的语法与语义(命题逻辑)之间的关系。可以说,命题演算就是具有可靠性及完备性的命题逻辑的形式系统。

由命题变元的合取式构成的析取式称为析取范式;类似地,由命题变元的析取式构成的合取式称为合取范式。任何一个命题演算的公式 A都等值于一个析取范式A┡及一个合取范式A″,即AA┡及AA″为重言式。A┡及A″分别称为A的析取范式及合取范式。

如果将命题逻辑中的命题变元看作一般的变元;用“0”和“1”依次代替命题变元的两个取值“假”和“真”;用“┡”,“·”,“+”依次代替逻辑连接词“非”,“和”,“或”而保持它们原有的意义不变,这样就得到了一个定义在两个元素0和1上的布尔代数。由G.布尔于1847年建立的布尔代数(也称逻辑代数)是用数学方法研究逻辑学的最初尝试。

参考书目
  1. 王宪钧编:《数理逻辑引论》,北京大学出版社,北京,1982。
  2. A.Church,Introduction to MatheMatical logic,Princeton Univ. Press, Princeton, 1956.
  3. J.L.Bell and M. Machover,A Course in Mathe-Matical Logic,North-Holland,Amsterdam,1977.
  4. J.R.Shoenfield,MatheMatical Logic,Addison-Wesley,Reading Mass., 1967.