Информационная система Скотта

редактировать

В теории предметной области, ветви математики и информатики, информационная система Скотта является примитивной своего рода логическая дедуктивная система, часто используемая как альтернативный способ представления доменов Скотта.

Содержание

1 Определение
2 Примеры
- 2.1 Натуральные числа
- 2.2 Исчисление высказываний
- 2.3 Домены Скотта
3 Информационные системы и домены Скотта
4 См. Также
5 Ссылки

Определение

A Информационная система Скотта, A, является упорядоченной тройкой $(T, C on, ⊢) {\ displaystyle (T, Con, \ vdash)}$ $(T, Con, \ vdash)$

$T - набор токенов (основных единиц информации) {\ displaystyle T {\ t_dv {- это набор токенов (базовые единицы информации)}}}$ $T {\ t_dv {- это набор токенов (основных единиц информации)}}$
$C на ⊆ P f (T) конечных подмножествах T {\ displaystyle Con \ substeq {\ mathcal {P}} _ {f} (T) {\ t_dv {конечные подмножества}} T}$ ${\ displaystyle Con \ substeq {\ mathcal {P}} _ {f} (T) {\ t_dv {конечные подмножества}} T}$
$⊢ ⊆ (C на ∖ {∅}) × T {\ displaystyle {\ vdash} \ substeq (Con \ setminus \ lbrace \ emptyset \ rbrace) \ times T}$ ${\ displaystyle {\ vdash} \ substeq (Con \ setminus \ lbrace \ emptyset \ rbrace) \ times T}$

удовлетворяет

$Если a ∈ X ∈ C on, то X ⊢ a {\ displaystyle {\ t_dv {If}} a \ in X \ in Con {\ t_dv {then}} X \ vdash a}$ ${\ t_dv {If}} a \ in X \ in Con {\ t_dv {then}} X \ vdash a$
$Если X ⊢ Y и Y ⊢ a, то X ⊢ a {\ displaystyle {\ t_dv {If}} X \ vdash Y {\ t_dv {and}} Y \ vdash a {\ t_dv {, then}} X \ vdash a}$ ${\ t_dv {If}} X \ vdash Y {\ t_dv {и}} Y \ vdash a {\ t_dv {, затем}} X \ vdash a$
$Если X ⊢ a, то X ∪ {a} ∈ C на {\ displaystyle {\ t_dv {If}} X \ vdash a {\ t_dv {then}} X \ cup \ { a \} \ in Con}$ ${\ t_dv {If}} X \ vdash a {\ t_dv {then}} X \ cup \ {a \} \ в Con$
$∀ a ∈ T: {a} ∈ C на {\ displaystyle \ forall a \ in T: \ {a \} \ in Con}$ $\ forall a \ in T: \ {a \} \ in Con$
$Если X ∈ C on и X ′ ⊆ X, то X ′ ∈ C на. {\ displaystyle {\ t_dv {If}} X \ in Con {\ t_dv {and}} X ^ {\ prime} \, \ substeq X {\ t_dv {then}} X ^ {\ prime} \ in Con.}$ ${\ t_dv {Если}} X \ in Con {\ t_dv {and}} X ^ {\ prime} \, \ su bseteq X {\ t_dv {then}} X ^ {\ prime} \ in Con.$

Здесь $Икс ⊢ Y {\ displaystyle X \ vdash Y}$ $X \ vdash Y$ означает $∀ a ∈ Y, X ⊢ a. {\ displaystyle \ forall a \ in Y, X \ vdash a.}$ $\ forall a \ in Y, X \ vdash a.$

Примеры

Натуральные числа

Возвращаемое значение частично рекурсивной функции, которая либо возвращает натуральное число, либо переходит в бесконечную рекурсию, может быть выражено как простая информационная система Скотта следующим образом:

$T: = N {\ displaystyle T: = \ mathbb {N}}$ $T: = { \ mathbb {N}}$
$C on: = {∅} ∪ {{n} ∣ N ∈ N} {\ displaystyle Con: = \ {\ emptyset \} \ cup \ {\ {n \} \ mid n \ in \ mathbb {N} \}}$ $Con: = \ {\ emptyset \} \ cup \ {\ {n \} \ mid n \ in {\ mathbb {N}} \}$
$X ⊢ a ⟺ a ∈ X. {\ displaystyle X \ vdash a \ iff a \ in X.}$ ${\ displaystyle X \ vdash a \ iff a \ in X.}$

То есть результатом может быть натуральное число, представленное синглетным набором ${n} {\ displaystyle \ {n \}}$ $\ {n \}$ , или «бесконечная рекурсия», представленная как $∅ {\ displaystyle \ emptyset}$ $\ empty$ .

Конечно, то же самое построение может быть выполнено с любым другим набором вместо $N {\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ .

Исчисление высказываний

Исчисление высказываний дает нам очень простую информационную систему Скотта следующим образом:

$T: = {ϕ ϕ ϕ выполнимо } {\ displaystyle T: = \ {\ phi \ mid \ phi {\ t_dv {выполнимо}} \}}$ $T: = \ {\ phi \ mid \ phi {\ t_dv {выполнимо}} \}$
$C on: = {X ∈ P f (T) ∣ X согласован} {\ displaystyle Con : = \ {X \ in {\ mathcal {P}} _ {f} (T) \ mid X {\ t_dv {непротиворечиво}} \}}$ $Con: = \ {X \ in {\ mathcal {P}} _ {f} (T) \ mid X {\ t_dv {согласован}} \}$
$X ⊢ a ⟺ X ⊢ a в исчислении высказываний. {\ displaystyle X \ vdash a \ iff X \ vdash a {\ t_dv {в исчислении высказываний}}.}$ ${\ displaystyle X \ vdash a \ iff X \ vdash a {\ t_dv {в исчислении высказываний}}.}$

Домены Скотта

Пусть D будет доменом Скотта. Затем мы можем определить информационную систему следующим образом

$T: = D 0 {\ displaystyle T: = D ^ {0}}$ $T : = D ^ {0}$ набор компактных элементов из $D {\ displaystyle D}$ $D$
$C on: = {X ∈ P f (T) ∣ X имеет верхнюю границу} {\ displaystyle Con: = \ {X \ in {\ mathcal {P}} _ {f} (T) \ mid X {\ t_dv {имеет верхнюю границу}} \}}$ $Con: = \ {X \ in {\ mathcal {P}} _ {f} (T) \ mid X {\ t_dv {имеет верхнюю границу}} \}$
$X ⊢ d ⟺ d ⊑ ⨆ X. {\ displaystyle X \ vdash d \ iff d \ sqsubseteq \ bigsqcup X.}$ ${\ displaystyle X \ vdash d \ iff d \ sqsubseteq \ bigsqcup X.}$

Пусть $I {\ displaystyle {\ mathcal {I}}}$ ${\ mathcal {I}}$ будет отображением, которое выводит нас из Скотта, D, в указанную выше информационную систему.

Информационные системы и домены Скотта

Для информационной системы $A = (T, C on, ⊢) {\ displaystyle A = (T, Con, \ vdash)}$ $A = (T, Con, \ vdash)$ , мы можем построить домен Скотта следующим образом.

Определение: Икс ⊆ T {\ displaystyle x \ substeq T}является точкой тогда и только тогда, когда
- $Если X ⊆ fx, то X ∈ C на {\ displaystyle {\ t_dv {If}} X \ substeq _ {f} x {\ t_dv {then}} X \ in Con}$ ${\ t_dv {If}} X \ substeq _ {f} x {\ t_dv {then}} X \ in Con$
- $Если X ⊢ a и X ⊆ fx, то a ∈ x. {\ displaystyle {\ t_dv {If}} X \ vdash a {\ t_dv {and}} X \ substeq _ {f} x {\ t_dv {then}} a \ in x.}$ ${\ t_dv {If}} X \ vdash a {\ t_dv {and}} X \ substeq _ {f} x {\ t_dv {then}} a \ in х.$

Пусть $D (A) {\ displaystyle {\ mathcal {D}} (A)}$ ${\ mathcal {D}} (A)$ обозначает набор точек A с упорядочением подмножеств. $D (A) {\ displaystyle {\ mathcal {D}} (A)}$ ${\ mathcal {D}} (A)$ будет счетным доменом Скотта, когда T является счетным. В общем, для любого домена Скотта D и информационной системы A

$D (I (D)) ≅ D {\ displaystyle {\ mathcal {D}} ({\ mathcal {I}} (D)) \ cong D}$ ${\ mathcal {D}} ({\ mathcal {I}} (D)) \ cong D$
$I (D (A)) ≅ A {\ displaystyle {\ mathcal {I}} ({\ mathcal {D}} (A)) \ cong A}$ ${\ mathcal {I}} ({\ mathcal {D}} (A)) \ cong A$

, где второе сравнение дается выражением.

См. Также

Ссылки

Глинн Винскель: «Формальная семантика языков программирования: введение», MIT Press, 1993 (глава 12)