Podpis (logika) - Signature (logic)

V logice , obzvláště formální logika , o podpisu uvádí a popisuje non-logické symboly z k formálním jazyce . V univerzální algebře obsahuje podpis seznam operací, které charakterizují algebraickou strukturu . V teorii modelu se podpisy používají pro oba účely. Ve filozofičtějším zacházení s logikou jsou zřídka výslovně vyjádřeny.

Definice

Formálně lze (single-tříděný) podpis definovat jako trojitý σ = ( S func , S rel , ar), kde S func a S rel jsou disjunktní sady neobsahující žádné další základní logické symboly, nazývané příslušně

  • funkční symboly (příklady: +, ×, 0, 1) a
  • relační symboly nebo predikáty (příklady: ≤, ∈),

a funkce ar: S func  S rel →, která každé funkci nebo relačnímu symbolu přiřadí přirozené číslo zvané arity . Symbol funkce nebo relace se nazývá n -ary, pokud je její arity n . Symbol funkce nullary ( 0 -ary) se nazývá konstantní symbol .  

Podpis bez funkčních symbolů se nazývá relační podpis a podpis bez relačních symbolů se nazývá algebraický podpis . Konečný podpis je podpis takové, že S fun a S rel jsou omezené . Obecněji je mohutnost podpisu σ = ( S func , S rel , ar) definována jako | σ | = | S func | + | S rel |.

Jazyk podpisu je množina všech dobře vytvořených vět postavené ze symbolů v tomto podpisu spolu s symbolů logického systému.

Další konvence

V univerzální algebře se typ slova nebo typ podobnosti často používá jako synonymum pro „podpis“. V teorii modelu se podpis σ často nazývá slovní zásoba nebo se identifikuje jazykem (prvního řádu) L , kterému poskytuje nelogické symboly . Nicméně, mohutnost jazykové L bude vždy být nekonečný; je-li σ konečná, pak | L | bude 0 .

Jelikož formální definice je pro každodenní použití nepohodlná, definice konkrétního podpisu se často zkracuje neformálním způsobem, například:

"Standardní podpis pro abelianské skupiny je σ = (+, -, 0), kde - je unární operátor."

Někdy se algebraický podpis považuje pouze za seznam arit, jako například v:

"Typ podobnosti pro abelianské skupiny je σ = (2,1,0)."

Formálně by to definovalo funkční symboly podpisu jako něco jako f 0  (nullary), f 1  (unární) a f 2  (binární), ale ve skutečnosti se obvyklá jména používají i v souvislosti s touto konvencí.

V matematické logice velmi často není dovoleno, aby symboly byly nulové, takže s konstantními symboly je třeba zacházet samostatně, nikoli jako se symboly nullové funkce. Tvoří množinu S const disjunktní od S func , na které není aritní funkce ar definována. To však slouží pouze ke zkomplikování věci, zejména u důkazů indukcí nad strukturou vzorce, kde je třeba vzít v úvahu další případ. Libovolný symbol relace nullary, který podle takové definice také není povolen, lze emulovat unárním symbolem relace spolu s větou vyjadřující, že jeho hodnota je pro všechny prvky stejná. Tento překlad selže pouze u prázdných struktur (které jsou konvencí často vyloučeny). Pokud jsou povoleny symboly nullary, pak každý vzorec výrokové logiky je také vzorec logiky prvního řádu .

Příklad nekonečného podpisu používá S func = {+} ∪ {f a : a F } a S rel = {=} k formalizaci výrazů a rovnic o vektorovém prostoru nad nekonečným skalárním polem F , kde každé f a označuje unární operace skalárního násobení a . Tímto způsobem lze podpis a logiku udržovat v jediném řazení, přičemž vektory jsou jediným způsobem.

Použití podpisů v logice a algebře

V rámci logiky prvního řádu , symboly v podpisu jsou také známé jako non-logické symboly , protože spolu s logickými symboly tvoří základní abecedu, nad nímž dvě formální jazyky jsou indukčně definovaná: soubor podmínek přes podpis a sada (dobře tvarovaných) vzorců nad podpisem.

Ve struktuře , což je interpretace vazby funkční a symbolů vztahu k matematickými objekty, které odůvodňují jejich jména: Výklad z n -ary funkční symbol f ve struktuře A s doméně A je funkce f A A n  →  A , a interpretace n -aryho relačního symbolu je relace R A  ⊆  A n . Zde n = x x ... x označuje n -násobnou kartézský produkt z domény A sama se sebou, a proto f je ve skutečnosti n -ary funkce, a R n -ary vztah.

Mnoho tříděných podpisů

U logiky s mnoha třídami a u struktur s mnoha třídami musí podpisy kódovat informace o druzích. Nejpřímější způsob, jak toho dosáhnout, je prostřednictvím typů symbolů, které hrají roli zobecněných arit.

Typy symbolů

Nechť S je množina (druhů) neobsahující symboly × nebo →.

Typy symbolů nad S jsou určitá slova nad abecedou : typy relačních symbolů s 1 ×… × s n a typy funkčních symbolů s 1 ×… × s ns ′ pro nezáporná celá čísla n a . (Pro n = 0 znamená výraz s 1 ×… × s n prázdné slovo.)

Podpis

Podpis (mnoho seřazený) je trojitý (typ S , P ), který se skládá z

  • množina druhů S ,
  • soubor P symbolů a
  • typ mapa, která asociuje ke každému symbolu P takového typu, jaký symbol přes S .

Poznámky

  1. ^ Mokadem, Riad; Litwin, Witold; Rigaux, Philippe; Schwarz, Thomas (září 2007). "Rychlé vyhledávání řetězců na základě nGram přes data kódovaná pomocí algebraických podpisů" (PDF) . 33. mezinárodní konference o velmi velkých databázích (VLDB) . Vyvolány 27 February 2019 . CS1 maint: discouraged parameter ( link )
  2. ^ George Grätzer (1967). „IV. Univerzální algebra“. V James C. Abbot (ed.). Trendy v teorii mřížky . Princeton / NJ: Van Nostrand. 173–210. CS1 maint: discouraged parameter ( link ) Zde: str.173.
  3. ^ Mnohostranná logika , první kapitola přednášek o rozhodovacích postupech , autor Calogero G. Zarba .

Reference

externí odkazy