代数命题逻辑（二）

3.5 没有指数的直觉线性逻辑

我们将集合 {∧,∨,→,*,0,1,⊤,⊥} 作为无指数直觉线性逻辑语言，其中 ∧,∨,→,* 是二元连接词，0,1,⊤,⊥命题常数。我们用 ILL 来表示该逻辑。下面的公理和推理规则提供了该逻辑的希尔伯特式公理化。

公理：

L1。

1

L2。

(ψ→ψ)→((ψ→δ)→(ψ→δ))L3。

(ψ→(ψ→δ))→(ψ→(ψ→δ))L4。

ψ→(ψ→(ψ*ψ))L5。

(ψ→(ψ→δ))→((ψ*ψ)→δ)L6。

1→(Φ→Φ)L7。

(ψ∧ψ)→ψL8。

(ψ∧ψ)→ψL9。

ψ→(ψ∨ψ)L10。

ψ→(ψ∨ψ)L11。

((Φ→ψ)∧(Φ→δ))→(Φ→(ψ∧δ))L12。

((ψ→δ)∧(ψ→δ))→((ψ∨ψ)→δ)L13。

⊤L14。

⊥→ψ

推理规则：

ψ,ψ→ψ/ψ

ψ,ψ/ψ∧ψ

0 元连接词 0 用于通过 ψ := ψ → 0 定义否定。没有特定的公理模式处理 0。

有关更多信息，请参阅线性逻辑条目。

3.6 关联逻辑系统R

我们考虑的语言是集合{∧,∨,→,Ø}，其中∧,∨,→是二元连接词，Ø是一元连接词。 R 的希尔伯特式公理化可以由没有指数的直觉线性逻辑规则和该逻辑的公理 L2、L3、L7-L12 以及公理给出

(ψ→(ψ→ψ))→(ψ→ψ)

(ψ→ψ)→(ψ→ψ)

(ψ∧(ψ∨δ))→((ψ∧ψ)∨ψ∧δ))

←←φ→φ

有关更多信息，请参阅相关逻辑条目。

4.代数

特定逻辑的代数研究首先必须使用一类代数为其形式语言提供代数语义，利用代数的属性来理解该逻辑具有哪些属性。在本节中，我们将介绍如何对命题逻辑的形式语言进行代数解释。在下一节中，我们将讨论什么是逻辑系统的代数语义的问题。

我们首先描述命题逻辑代数研究中涉及的前两个步骤。为了赋予命题语言代数解释，两者都是必需的。为了阐述它们，我们将假设具有一阶逻辑知识（参见经典逻辑和一阶模型理论的条目），并且我们将称为代数一阶语言，或简称代数语言，即具有相等性和不具有相等性的一阶语言任何关系符号，以便这些语言在其非逻辑符号集中仅具有操作符号（也称为函数符号）（如果有的话）。

我们要阐述的两个步骤可以用口号来概括：

命题公式是项。

第一步包括将任何命题语言 L 的公式视为代数一阶语言的项，其中 L 作为其运算符号集。这意味着 (i) 元数 n 的 L 的每个连接词都被视为元数 n 的运算符号（因此 L 的每个 0 元符号被视为单独的常数）并且 (ii) L 的命题公式被取作为该一阶语言的术语；特别是命题变量是一阶语言的变量。从这个角度来看，L-公式的定义正是L-项的定义。我们将以L为运算符号集的代数语言称为L-代数语言。

第二步是以与在结构中解释一阶语言的项相同的方式解释命题公式。这样，L-代数的概念就发挥了作用。在给定的集合 A 上，n 元连接词由 A 上的 n 元函数解释（将 A 的一个元素分配给 A 的元素的每个序列 ⟨a1,…,an⟩ 的映射）。这个过程是对经典逻辑、Łukasiewicz 和 Post 有限值逻辑等逻辑系统语言的真值表解释的概括。在这些情况下，给定一组起作用的真值，解释连接词的函数由其真值表给出。

引入代数的一种方法是作为一些代数一阶语言的模型。我们遵循等效的路线，并使用命题语言的设置给出代数的定义。令 L 为命题语言。 L 型代数 A，或简称为 L-代数，是一个集合 A，称为 A 的载体或域，以及 A 上的 * 元数的函数 *A，对于 L 中的每个连接词 *（如果＊是0元，＊A是A)的一个元素。如果代数 A 的载体是单元素集，则代数 A 是平凡的。

L-代数 A 的估值是从变量集到其载体 A 的映射 v。代数与估值一起用于以组合方式解释 L 的公式，假设 L 的连接 * 被解释为L-代数 A 由函数 *A 表示。令 A 为 L 类型的代数，v 为 A 的估值。复合公式 ∗ 1 … ψ n 的值通过应用将 A 中的 * 解释为先前计算值 \bv(\phi_1) 的函数 *A 来计算，\公式 \phi_1,\ldots,\phi_n 的 ldots,\bv(\phi_n)。准确地说，公式 \phi 的值 \bv(\phi) 归纳定义如下：

\bv(p) = v(p)，对于每个变量 p，

\bv(\dagger) = \dagger^{\bA}，如果 \dagger 是 0 元连接词

\bv(* \phi_1 \ldots \phi_n) = * ^{\bA }(\bv(\phi_1), \ldots ,\bv(\phi_n))，如果 * 是 n 进制 (n \gt 0)连接词。

请注意，通过这种方式，我们获得了从 L 公式集到 \bA 的载体的映射 \bv。值得注意的是，估值下公式的价值仅取决于公式中实际出现的命题变量。因此，如果 \phi 是一个公式，那么我们使用符号 \phi(p_1 , \ldots ,p_n) 来指示 \phi 中出现的变量在列表 p_1 , \ldots ,p_n 中，并且给定元素 a_1 ，代数 \bA 的 \ldots ,a_n 我们用 \phi^{\bA }[a_1 , \ldots ,a_n] 表示\phi(p_1 , \ldots ,p_n) 在 \bA 上的任何估值 v 下的值，使得 v(p_1) = a_1 , \ldots ,v(p_n) = a_n 。

逻辑代数研究的第三个也是基本步骤是将语言 L 的公式集转化为代数，即 L 的公式代数，用 \bFm_L 表示。该代数以L-公式集作为载体，其运算定义如下。对于每个 n \gt 0 的 n 元连接词 * ，函数 * ^{\bFm_L} 是将每个公式元组 (\phi_1 , \ldots ,\phi_n) （其中 n 是 * 的元数）发送到公式 * \phi_1 \ldots \phi_n ，对于每个 0 元连接词 \dagger ， \dagger^{\bFm_L} 是 \dagger。如果不会造成混淆，我们将抑制 \bFm_L 中的子索引并写入 \bFm 。

4.1 泛代数和模型论的一些概念

代数是一种特殊类型的结构或模型。 L 代数是 L 代数一阶语言的结构或模型。因此，一阶语言的模型论概念适用于它们（参见经典逻辑和一阶模型论的条目）。我们需要其中一些概念。它们还用于通用代数，该领域在某种程度上可以被视为代数语言的模型理论。我们介绍我们需要的概念的定义。

给定 L 类型的代数 \bA，\bA 的同余是 \bA 载体上的等价关系 θ，它满足每个 n 元连接词 * \in L 的以下兼容性属性：对于每个 a_1 ， \ldots ， a_n, b_1 , \ldots ,b_n \in A,

\textrm{如果 } a_1\theta b_1 , \ldots ,a_n \theta b_1, \textrm{ 那么 } *^{\bA}(a_1 ,\ldots ,a_n)\ \theta *^{\bA}(b_1 ,\ ldots，b_n)。

给定 \bA 的同余 \theta，我们可以通过识别与 \theta 相关的元素来简化代数。得到的代数是\bA 模\theta 的商代数。它用\ ba/\ theta表示，其载体是模块的元素a/e \ theta的集合a/\ theta a/\ theta a modulo a的等价关系\ theta的元素a/\ theta，并且操作定义如下：

\ dagger^{\ ba/\ theta} = [\匕首^{\ ba}]

* ^{\ ba/\ theta}（[a_1]，\ ldots，[a_n]）= [ * ^{\ ba}（a_1，\ ldots，a_n）] GT 0。

兼容性属性可确保定义是正确的。

令\ ba和\ bb为l-algebras。从\ ba到\ bb的同构h是从a到b的映射h，使得在l和l中的每个n-ary连接 * \ in l in l in a b a到b。

h（\匕首^{\ ba}）= \匕首^{\ bb}

h（ * ^{\ ba}（a_1，\ ldots，a_n））= * ^{\ bb}（h（b_1），\ ldots，h（b_n）） 。

我们说，如果从\ ba到\ bb存在同态的同性形态，则\ bb是\ ba的同态图像，这是从a到a的映射。从a到a的地图上的地图。如果存在\ ba到\ bb的同构，我们说\ ba和\ bb是同构的，\ bb是一个\ ba的同构图像（或副本）。

令\ ba和\ bb为l-algebras。 \ ba是\ bb的子代数，如果（1）a \ subseteq b，（2）\ bb中l的0- ary符号的解释属于a，并且在解释非bb的功能下，A a a a a a a a a a a a a a a a a的解释是关闭的。 0- ary符号，以及（3）\ ba中0- yar符号的解释与它们在\ bb中的解释相吻合，而在\ bb中的解释是L中其他符号的解释是对其\ ba的限制。 \ bb中的解释。

我们将读者转介到一阶模型理论的条目中，以直接乘积（称为产品）和超副产品的概念。

4.2品种和准植物

为命题逻辑提供语义的大多数代数类别是准里埃，在大多数情况下，各种品种。品种和准植物的理论是普遍代数的主要主题之一。

L-Algebras的方程式类别是一类L-Elgebras，可以使用L-Elgebraic语言以非常简单的方式（按公式）定义。 l-方程是一种公式\ phi \ ot \ psi，其中\ phi and \ psi是l-algebraic语言的术语（即，如果我们采用命题逻辑的观点，则是l型）平等的形式符号（始终被解释为身份关系）。方程\ phi \ lot \ psi在代数\ ba中有效，或者\ ba是\ phi \ liot \ psi的模型，如果对于每个估值v on \ ba，\ bv（\ phi）= \ bv（\ bv（\ bv（\ bv（\ phi）磅/平方英寸）。这与说\ phi \ psi的通用闭合是\ ba中的一个句子是完全相同的，该句子是根据均等逻辑的常规语义在\ ba中呈现的。 L-Algebras的方程式类别是一类L-代数，这是给定的一组L-方程的所有模型的类别。

准平等的L-代数类是一类使用L-Elgebraic语言的L-代数类别，其方式比Equination.lasses中更复杂。适当的l-quasiequation是\ bigwedge_ {i \ le n} \ phi_i \ of \ psi_i \ rightArrow \ phi \ phi \ oft \ psi的表单的公式。 l-quasiequation是上述形式的公式，但可能具有空的先例，在这种情况下，它只是方程式\ phi \ oft \ psi。因此，l-quasiequations是适当的l-quasiequations和l qua-equations。如果在l-algebra \ ba中有效，则有效，或者代数是它的模型，如果\ ba中的quasiequation的普遍闭合是句子为true的。准平等的L-代数类是一类代数，这是给定的一组L- Quasiequations模型的类别。由于方程式是准Quake的，因此每个方程式都是准平等的。匡威是错误的。此外，由于在微不足道的代数中，所有方程式以及适当的代数语言的所有排序都是有效的，因此等式和准平等类都是非空的。

代数的方程式和准平等类的特征是他们所享有的封闭特性。如果在亚代数，直接产物和同形图像下关闭，则非空的L-代数类是一种多样性。如果它在亚代毛，直接产物，超副型，同构图像并包含一个琐碎的代数下关闭，那是一种准会。可以很容易地看出，方程类是品种，准平等类是准则。 Birkhoff的定理指出，所有品种都是方程式类别，Malcev的定理，所有的Quasivarieties都是准平等类。

L-Algebras的非置类\ bk产生的品种是包括\ bk的L-代数最少，并在亚代词，直接产物和同型图像下关闭。代数的类也是\ bk中有效的方程模型。例如，两个真实价值的代数为古典逻辑产生的品种是布尔代数类别。如果我们仅将该代数限制在连词和脱节的操作中，它将生成各种分布晶格，如果我们将其限制在连接和脱节的操作中，以及\ top and \ top和\ bot的解释，它将产生各种有限的分布式分布式分布。格子。

L-Algebras的类别\ bk产生的准疗法是包括\ bk，琐事代数在内的L-Elgebras最少的类别，并在亚代代代代数，直接产物，超副产物和同构图像下封闭。

一类L-Algebras是一类L-Elgebras，其中包含一个微不足道的代数，并在同构图像，亚代词和直接产物下封闭。因此，准体和品种都是Sp类。 L-Algebras的类\ bk产生的SP级是包括\ bk，琐事代数，并在亚代代代数，直接产物和同构图像下关闭的L-代数最少。

5。代数语义

文学中的“代数语义”一词在文献中以宽松的方式使用。为代数语义提供逻辑是在一类代数中解释其语言，在同类的代数中定义了对公式的满意度（在估值下）的概念，并证明是一种健全和完整的定理，通常用于定理仅逻辑。如今，对于逻辑系统来说，有一个代数语义的精确概念。它是由Blok and Pigozzi在Blok＆Pigozzi 1989中引入的。在这个概念中，我们找到了一种用数学上精确的术语来陈述的一般方法，与许多在文献中发现的特定逻辑系统的声称为代数语义的案例相同。我们在本节中揭示了概念。为了激发定义，我们首先讨论了几个示例，强调了它们共享的相关属性。读者不需要了解提供我们在示例中提到的代数语义的代数类别。它的存在是重要的。

命题逻辑代数语义语义的原型示例是布尔代数的BA类，该代数是古典逻辑的代数语义，而Heyting代数的HA级是直觉逻辑的代数语义。每个布尔代数和每个Heyting代数\ ba都根据其自然秩序最大的元素。该元素通常用1^{\ ba}表示，并解释命题常数符号\ top。它被视为给出代数语义的杰出元素。这两种逻辑的代数语义如下：

令\ bl为古典或直觉逻辑，让\ bk（\ bl）为代数ba或ha的相应类。它认为

\ gamma \ vdash _ {\ bl} \ phi \ phi \ txtiff for \ bk（\ bl）in \ bk（\ bl）和每个估值v on \ ba，如果\ bv（\ psi）= 1^{\ ba} \ in \ gamma，然后\ bv（\ phi）= 1^{\ ba}。

这是陈述的确切内容，即BA和HA分别是古典逻辑和直觉逻辑的代数语义。上面表达式从左到右的含义是代数稳定性定理，以及从右到左代数完整定理的含义。

在文献中，文献中提供了代数语义的逻辑，与上面的模式略有不同。让我们考虑无指数的直觉线性逻辑第3.5节中的示例。我们用\ bilsubz表示，在1992年Troelstra中定义为零的IL-Elgebras类（但适用于\ Bill的语言）。每个\ ba \ in \ bilsubz是一个具有额外操作的晶格，因此具有其晶格顺序\ le^{\ ba}。该晶格顺序具有最大的元素，我们将其作为\ top的解释。在这些代数\ ba中，每个代数中都有一个指定的元素1^{\ ba}（常数1的解释）可能与最大元素不同。它持有：

\ gamma \ vdash _ {\ bill} \ phi \ phi \ txtiff for \ ba \ in \ bilsubz in \ bilsubz in \ ba in \ ba上的每个估值v，如果1^{\ ba} \ le^{\ le^{\ ba} {\ ba} \ ba} \ bv（\ psi） \ psi \ in \ gamma，然后1^{\ ba} \ le^{\ ba} \ bv（\ phi）。

在这种情况下，不仅考虑每个代数\ ba中的指定元素，而是一组指定的元素，即\ ba的元素大于或等于1^{\ ba}，以提供定义。让我们用\ td（\ ba）表示此设置，并注意\ td（\ ba）= \ {a \ in a：1^{\ ba} \ wedge^{\ ba} a = 1^{\ ba = 1^{\ ba } \}。因此，

\ gamma \ vdash _ {\ bill} \ phi \ txtiff for每个\ ba \ in \ bilsubz in \ bilsubz if \ bv [\ gamma] \ subseteq \ td（\ ba），然后\ bv（\ phi（\ phi） ）。

仍然存在更复杂的情况。其中之一是相关逻辑的系统\ br。考虑Font＆Rodríguez1990中定义的代数\ Bral类（另请参见Font＆Rodríguez1994），并用“ \ br”表示。让我们考虑每个\ ba \ in \ bral in s seet \ te（\ ba）：= \ {a \ in A：a \ wedge^{\ ba}（a \ rightArrow^{\ ba} a）= a \ a \ a \ rightarrow^{\ ba} a \}。然后，\ bral据说是\ br的代数语义，因为以下内容存在：

\ gamma \ vdash _ {\ br} \ phi \ phi \ txtiff for \ in \ bral in \ bral和每个估值v on \ ba，如果\ ba，如果\ bv [\ gamma] \ subseteq \ subseteq \ subseteq \ te（\ ba），那么）\ in \ te（\ ba）。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。