v teorie domény, pobočka matematika a počítačová věda, a Informační systém Scott je primitivní druh logiky deduktivní systém často se používá jako alternativní způsob prezentace Scott domény.
Definice
A Informační systém Scott, A, je objednaná trojka ![(T, Con, vdash)](https://wikimedia.org/api/rest_v1/media/math/render/svg/38e2c1e19402c7b5f765d8a947259f169b506892)
![T {mbox {je sada tokenů (základní informační jednotky)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0dcc4b897789bf15519990392edc59c8e8029db)
![{displaystyle Consubseteq {mathcal {P}} _ {f} (T) {mbox {konečné podmnožiny}} T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2361258141521a468f070130038407865682d5d)
![{displaystyle {vdash} subseteq (Consetminus lbrace emptyset brace) je T}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25ed03181c0a49f83eb2af5942c7e149bbee1bdc)
uspokojující
![{mbox {If}} ain Xin Con {mbox {then}} Xvdash a](https://wikimedia.org/api/rest_v1/media/math/render/svg/040ccb35c8e5d40f650cc0445feeb4e6cd7f5c24)
![{mbox {If}} Xvdash Y {mbox {a}} Yvdash a {mbox {, pak}} Xvdash a](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0b9664573ad7abf0dff9a2a433d6016843c5257)
![{mbox {If}} Xvdash a {mbox {then}} Xcup {a} v Con](https://wikimedia.org/api/rest_v1/media/math/render/svg/b75dd36c3c97bfd6358fa56f4d653da625de5ec6)
![forall ain T: {a} in Con](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ee9a67c929d97965d4ded48fa01546590d7072a)
![{mbox {If}} Xin Con {mbox {a}} X ^ {prime}, subseteq X {mbox {then}} X ^ {prime} v Con.](https://wikimedia.org/api/rest_v1/media/math/render/svg/12b633601ed489730f2aefab52e6d20528f1a727)
Tady
prostředek ![forall ain Y, Xvdash a.](https://wikimedia.org/api/rest_v1/media/math/render/svg/6209074f1d21ba1c8c2706ff172641d76228bf5d)
Příklady
Přirozená čísla
Návratová hodnota a částečná rekurzivní funkce, který buď vrací přirozené číslo, nebo jde do nekonečné rekurze, lze vyjádřit jako jednoduchý Scottův informační systém takto:
![T: = {mathbb {N}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a275c84b8ecdffa2a275d9e2f96510551f55f72)
![Con: = {emptyset} cup {{n} mid nin {mathbb {N}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3c910a3b8365286d2c5439d787252a37f82e713)
![{displaystyle Xvdash aiff ain X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f21a64c3a70725367fe31713f2a21815645ab16)
To znamená, že výsledkem může být buď přirozené číslo reprezentované množinou singletonů
, nebo „nekonečná rekurze“, představovaná
.
Stejnou konstrukci lze samozřejmě provést místo jakékoli jiné sady
.
Výrokový počet
The výrokový kalkul nám poskytuje následující velmi jednoduchý informační systém Scott:
![T: = {phi mid phi {mbox {je uspokojivý}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de280f0eed05d468489cce85f3bb9147b743bbc4)
![Con: = {Xin {mathcal {P}} _ {f} (T) mid X {mbox {is consistent}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f33350019789ebda920702320476c20c8434a710)
![{displaystyle Xvdash aiff Xvdash a {mbox {v propozičním počtu}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d2d1e2914b00101a52083ab408390b7e6a8db7d)
Scott domény
Nechat D být Scott doména. Pak můžeme definovat informační systém následovně
soubor kompaktní prvky z ![D](https://wikimedia.org/api/rest_v1/media/math/render/svg/f34a0c600395e5d4345287e21fb26efd386990e6)
![Con: = {Xin {mathcal {P}} _ {f} (T) střední X {mbox {má horní mez}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bcc8d6ffbe75cb8cdcf54dfa8e8811d6e282edc1)
![{displaystyle Xvdash diff dsqsubseteq igsqcup X.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cbdd8974c19a9520a73f7d11ac8669442ed9720)
Nechat
být mapováním, které nás vezme z domény Scott, D, do výše definovaného informačního systému.
Informační systémy a domény Scott
Vzhledem k informačnímu systému
, můžeme postavit Scott doména jak následuje.
- Definice:
je bod právě tehdy, když![{mbox {If}} Xsubseteq _ {f} x {mbox {then}} Xin Con](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f1b3cfbd54478b67505a780d550e517a81500ed)
![{mbox {If}} Xvdash a {mbox {and}} Xsubseteq _ {f} x {mbox {then}} ain x.](https://wikimedia.org/api/rest_v1/media/math/render/svg/dacada668103fc8dec8b3a1b961aef34fb8afe2e)
Nechat
označit množinu bodů A s objednávkou podmnožiny.
bude počitatelně založená doména Scott, když T je spočítatelné. Obecně platí, že pro jakoukoli doménu Scott D a informační systém A
![{mathcal {D}} ({mathcal {I}} (D)) cong D](https://wikimedia.org/api/rest_v1/media/math/render/svg/8bcb10a49cf19b57a4b4819283e8252f9018136d)
![{mathcal {I}} ({mathcal {D}} (A)) cong A](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf1f6206c0da2b6a1db86d38b41c65d5c6f31c21)
kde druhá shoda je dána vztahem přibližné zobrazení.
Viz také
Reference
- Glynn Winskel: „Formální sémantika programovacích jazyků: úvod“, MIT Press, 1993 (kapitola 12)