Termín algebra - Term algebra
v univerzální algebra a matematická logika, a termínová algebra je volně generovaný algebraická struktura nad daným podpis.[1][2] Například v a podpis skládající se z jediného binární operace, termín algebra na množině X proměnných je přesně zdarma magma generováno uživatelem X. Další synonyma pro tento pojem zahrnují absolutně zdarma algebra a anarchická algebra.[3]
Od a teorie kategorií perspektiva, termín algebra je počáteční objekt pro kategorie všech algeber stejného podpisu, a tento objekt, jedinečný až izomorfismus, se nazývá počáteční algebra; generuje homomorfní projekce všech algeber v kategorii.[4][5]
Podobný pojem je a Herbrandův vesmír v logika, obvykle se pod tímto názvem používá v logické programování,[6] který je (zcela volně) definován počínaje množinou konstant a funkčních symbolů v sadě doložky. To znamená, že Herbrandův vesmír se skládá ze všeho základní pojmy: výrazy, které v sobě nemají žádné proměnné.
An atomový vzorec nebo atom je obecně definována jako a predikát aplikováno na n-tici podmínek; A pozemní atom je potom predikát, ve kterém se objevují pouze základní pojmy. The Herbrandova základna je sada všech pozemních atomů, které mohou být vytvořeny z predikátových symbolů v původní sadě klauzí a termínů v jejím Herbrandově vesmíru.[7][8] Tyto dva koncepty jsou pojmenovány po Jacques Herbrand.
Termín algebry také hraje roli v sémantika z abstraktní datové typy, kde deklarace abstraktního datového typu poskytuje podpis více tříděné algebraické struktury a termín algebra je konkrétním modelem abstraktní deklarace.
Rozhodnutelnost
![]() | tento článek možná matoucí nebo nejasné čtenářům.Říjen 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Termín algebry lze zobrazit rozhodnutelné pomocí eliminace kvantifikátoru. Složitost rozhodovacího problému je v NELENÁRNÍ.[9]
Herbrandova základna
The podpis σ jazyka je trojnásobek <Ó, F, P> skládající se z abecedy konstant Ó, funkční symboly Fa predikáty P. The Herbrandova základna[10] podpisu σ se skládá ze všech základních atomů σ: všech vzorců formuláře R(t1, …, tn), kde t1, …, tn jsou termíny neobsahující žádné proměnné (tj. prvky Herbrandova vesmíru) a R je n-ary symbol relace (tj. predikát ). V případě logiky s rovností obsahuje také všechny rovnice formuláře t1 = t2, kde t1 a t2 neobsahují žádné proměnné.
Viz také
- Programování odpovědí
- Klon (algebra)
- Doména diskurzu / Vesmír (matematika)
- Rabinova věta o stromu (monadická teorie nekonečna kompletní binární strom je rozhodnutelné)
- Počáteční algebra
- Abstraktní datový typ
Reference
- ^ Wilifrid Hodges (1997). Kratší teorie modelů. Cambridge University Press. str.14. ISBN 0-521-58713-1.
- ^ Franz Baader; Tobias Nipkow (1998). Přepisování termínů a tak dále. Cambridge University Press. str. 49. ISBN 0-521-77920-0.
- ^ Klaus Denecke; Shelly L. Wismath (2009). Univerzální algebra a koalgebra. World Scientific. 21–23. ISBN 978-981-283-745-5.
- ^ T.H. Tse (2010). Sjednocující rámec pro strukturovanou analýzu a návrhové modely: přístup využívající počáteční sémantiku algebry a teorii kategorií. Cambridge University Press. str. 46–47. doi:10.1017 / CBO9780511569890. ISBN 978-0-511-56989-0.
- ^ Jean-Yves Béziau (1999). „Matematická struktura logické syntaxe“. V Walter Alexandre Carnielli, Itala M. L. D'Ottaviano (ed.). Pokroky v současné logice a informatice: Sborník z jedenácté brazilské konference o matematické logice, 6. – 10. Května 1996, Salvador, Bahia, Brazílie. Americká matematická společnost. str. 9. ISBN 978-0-8218-1364-5. Citováno 18. dubna 2011.
- ^ Dirk van Dalen (2004). Logika a struktura. Springer. str. 108. ISBN 978-3-540-20879-2.
- ^ M. Ben-Ari (2001). Matematická logika pro informatiku. Springer. str. 148–150. ISBN 978-1-85233-319-5.
- ^ Monroe Newborn (2001). Automatizované ověřování vět: Teorie a praxe. Springer. str. 43. ISBN 978-0-387-95075-4.
- ^ Jeanne Ferrante; Charles W. Rackoff (1979). Výpočtová složitost logických teorií. Springer.
- ^ Rogelio Davila. Přehled nastavení programování odpovědí.
Další čtení
- Joel Berman (2005). "Struktura volných algeber". v Strukturální teorie automatů, poloskupin a univerzální algebry. Springer. 47 až 76. PAN2210125.