Počet konstrukcí - Calculus of constructions

tento článek vyžaduje pozornost odborníka na informatiku. Přidejte prosím důvod nebo a mluvit parametr k této šabloně pro vysvětlení problému s článkem. WikiProject Počítačová věda může pomoci s náborem odborníka. (Listopadu 2008)

v matematická logika a počítačová věda, Počet konstrukcí (CoC) je teorie typů vytvořil Thierry Coquand. Může sloužit jako zadaný programovací jazyk i jako konstruktivní základ pro matematiku. Z tohoto druhého důvodu bylo základem CoC a jeho varianty Coq a další důkazní asistenti.

Některé z jeho variant zahrnují Kalkul indukčních konstrukcí^[1] (což dodává indukční typy ), počet (Co) indukčních konstrukcí (který dodává koindukce ) a Predikativní počet indukčních konstrukcí (který některé odstraňuje.) nedůtklivost ).

Obecné vlastnosti

CoC je vyššího řádu zadaný lambda kalkul, původně vyvinutý společností Thierry Coquand. Je dobře známo, že je na vrcholu Barendregt je lambda kostka. V rámci CoC je možné definovat funkce od pojmů k pojmům, jakož i pojmy k typům, typy k typům a typy k pojmům.

CoC je silně normalizující, i když je nemožné prokázat tuto vlastnost v CoC, protože z toho vyplývá konzistence, která by Gödelova věta o neúplnosti ze samotného systému nelze prokázat.

Používání

CoC byl vyvinut spolu s Coq důkaz asistent. Jakmile byly do teorie přidány funkce (nebo odstraněny možné závazky), byly k dispozici v Coq.

Varianty CoC se používají u jiných zkušebních asistentů, jako např Matita.

Základy stavebního počtu

Počet konstrukcí lze považovat za prodloužení Curry – Howardův izomorfismus. Curom – Howardův izomorfismus spojuje pojem v jednoduše zadaný lambda kalkul s každým důkazem o přírodním odpočtu v intuicionistická výroková logika. Calculus of Constructions rozšiřuje tento izomorfismus na důkazy v úplném intuicionistickém predikátovém počtu, který zahrnuje důkazy kvantifikovaných výroků (které budeme také nazývat „propozice“).

Podmínky

A období v počtu konstrukcí je konstruován pomocí následujících pravidel:

• ${ displaystyle mathbf {T}}$ je termín (nazývaný také Typ);
• ${ displaystyle mathbf {P}}$ je termín (nazývaný také Podpěra, typ všech propozic);
• Proměnné (${ displaystyle x, y, ldots}$) jsou termíny;
• Li ${ displaystyle A}$ a ${ displaystyle B}$ jsou termíny, pak také jsou ${ displaystyle (AB)}$;
• Li ${ displaystyle A}$ a ${ displaystyle B}$ jsou termíny a ${ displaystyle x}$ je proměnná, pak jsou to také termíny:
  • ${ displaystyle ( lambda x: A.B)}$,
  • ${ displaystyle ( forall x: A.B)}$.

Jinými slovy, termín syntaxe, v BNF, pak je:

${ displaystyle e :: = mathbf {T} mid mathbf {P} mid x mid e , e mid lambda x { mathbin {:}} ee mid forall x { mathbin { :}} ee}$

Calculus of Constructions má pět druhů objektů:

1. důkazy, což jsou výrazy, jejichž typy jsou propozice;
2. propozice, které jsou také známé jako malé typy;
3. predikáty, což jsou funkce, které vracejí návrhy;
4. velké typy, což jsou typy predikátů (${ displaystyle mathbf {P}}$ je příklad velkého typu);
5. ${ displaystyle mathbf {T}}$ sám, což je typ velkých typů.

Rozsudky

Calculus of Constructions umožňuje dokazování psaní úsudků:

${ displaystyle x_ {1}: A_ {1}, x_ {2}: A_ {2}, ldots vdash t: B}$

Což lze číst jako implikaci

Pokud proměnné ${ displaystyle x_ {1}, x_ {2}, ldots}$ mít typy ${ displaystyle A_ {1}, A_ {2}, ldots}$, pak termín ${ displaystyle t}$ má typ ${ displaystyle B}$.

Platné úsudky pro počet konstrukcí lze odvodit ze sady odvozovacích pravidel. V následujícím textu používáme ${ displaystyle Gamma}$ znamenat posloupnost přiřazení typů ${ displaystyle x_ {1}: A_ {1}, x_ {2}: A_ {2}, ldots}$; ${ displaystyle A, B, C, D}$ znamenat pojmy; a ${ displaystyle K, L}$ to znamená buď ${ displaystyle mathbf {P}}$ nebo ${ displaystyle mathbf {T}}$. Budeme psát ${ displaystyle B [x: = N]}$ znamená výsledek nahrazení termínu ${ displaystyle N}$ pro volnou proměnnou ${ displaystyle x}$ v termínu ${ displaystyle B}$.

Pravidlo odvození je zapsáno ve formuláři

${ displaystyle { Gamma vdash A: B} nad { Gamma ' vdash C: D}}$

což znamená

Li ${ displaystyle Gamma vdash A: B}$ je platný úsudek, pak také je ${ displaystyle Gamma vdash C: D}$

Pravidla odvození pro počet konstrukcí

1. ${ displaystyle {{} nad Gamma vdash mathbf {P}: mathbf {T}}}$

2. ${ displaystyle {{} nad { Gamma, x: A, Gamma ' vdash x: A}}}$

3. ${ displaystyle { Gamma vdash A: K qquad qquad Gamma, x: A vdash B: L nad { Gamma vdash ( forall x: A.B): L}}}$

4. ${ displaystyle { Gamma vdash A: K qquad qquad Gamma, x: A vdash N: B over { Gamma vdash ( lambda x: AN): ( forall x: AB)}} }$

5. ${ displaystyle { Gamma vdash M: ( forall x: A.B) qquad qquad Gamma vdash N: A over { Gamma vdash MN: B [x: = N]}}}$

6. ${ displaystyle { Gamma vdash M: A qquad qquad A = _ { beta} B qquad qquad Gamma vdash B: K over { Gamma vdash M: B}}}$

Definování logických operátorů

The Calculus of Constructions has very few basic operators: the only logical operator for creating propositions is ${ displaystyle forall}$. Tento jeden operátor je však dostatečný k definování všech ostatních logických operátorů:

${ displaystyle { begin {array} {ccll} A Rightarrow B & equiv & forall x: A.B & (x notin B) A klín B & equiv & forall C: mathbf {P} . (A Rightarrow B Rightarrow C) Rightarrow C & A vee B & equiv & forall C: mathbf {P}. (A Rightarrow C) Rightarrow (B Rightarrow C) Rightarrow C & neg A & equiv & forall C: mathbf {P}. (A Rightarrow C) & existuje x: A.B & equiv & forall C: mathbf {P}. ( forall x : A. (B Rightarrow C)) Rightarrow C & end {pole}}}$

Definování datových typů

Základní datové typy používané v informatice lze definovat v rámci počtu konstrukcí:

Booleovci

${ displaystyle forall A: mathbf {P} .A Rightarrow A Rightarrow A}$

Přírodní

${ displaystyle forall A: mathbf {P}. (A Rightarrow A) Rightarrow (A Rightarrow A)}$

Produkt ${ displaystyle A krát B}$

${ displaystyle A klín B}$

Nespojitá unie ${ displaystyle A + B}$

${ displaystyle A vee B}$

Všimněte si, že Booleans a Naturals jsou definovány stejným způsobem jako v Kódování kostela. Další problémy však vyplývají z propoziční roztažnosti a důkazní irelevance.^[2]

Viz také

• Systém čistého typu
• Lambda kostka
• Systém F
• Závislý typ
• Intuicionistická teorie typů
• Teorie typu homotopy

Reference