Válcová algebra - Cylindric algebra - Wikipedia

Pojem válcová algebra, vynalezl Alfred Tarski, vzniká přirozeně v algebraizace z logika prvního řádu s rovností. To je srovnatelné s rolí Booleovy algebry hrát za výroková logika. Ve skutečnosti jsou cylindrické algebry booleovské algebry vybavené dalšími válcovacími operacemi, které modelují kvantifikace a rovnost. Liší se od polyadické algebry v tom, že tito nemodelují rovnost.

Definice válcové algebry

A válcová algebra dimenze ${ displaystyle alpha}$ (kde ${ displaystyle alpha}$ je jakýkoli pořadové číslo ) je algebraická struktura ${ displaystyle (A, +, cdot, -, 0,1, c _ { kappa}, d _ { kappa lambda}) _ { kappa, lambda < alpha}}$ takhle ${ displaystyle (A, +, cdot, -, 0,1)}$ je Booleova algebra, ${ displaystyle c _ { kappa}}$ unární operátor zapnutý ${ displaystyle A}$ pro každého ${ displaystyle kappa}$ (volal a válcování), a ${ displaystyle d _ { kappa lambda}}$ význačný prvek ${ displaystyle A}$ pro každého ${ displaystyle kappa}$ a ${ displaystyle lambda}$ (volal a úhlopříčka), takže platí:

(C1) ${ displaystyle c _ { kappa} 0 = 0}$

(C2) ${ displaystyle x leq c _ { kappa} x}$

(C3) ${ displaystyle c _ { kappa} (x cdot c _ { kappa} y) = c _ { kappa} x cdot c _ { kappa} y}$

(C4) ${ displaystyle c _ { kappa} c _ { lambda} x = c _ { lambda} c _ { kappa} x}$

(C5) ${ displaystyle d _ { kappa kappa} = 1}$

(C6) Pokud ${ displaystyle kappa notin { lambda, mu }}$, pak ${ displaystyle d _ { lambda mu} = c _ { kappa} (d _ { lambda kappa} cdot d _ { kappa mu})}$

(C7) Pokud ${ displaystyle kappa neq lambda}$, pak ${ displaystyle c _ { kappa} (d _ { kappa lambda} cdot x) cdot c _ { kappa} (d _ { kappa lambda} cdot -x) = 0}$

Za předpokladu prezentace logiky prvního řádu bez funkčních symbolů, operátor ${ displaystyle c _ { kappa} x}$ modely existenční kvantifikace přes proměnnou ${ displaystyle kappa}$ ve vzorci ${ displaystyle x}$ zatímco operátor ${ displaystyle d _ { kappa lambda}}$ modeluje rovnost proměnných ${ displaystyle kappa}$ a ${ displaystyle lambda}$. Od nynějška, přeformulovaný pomocí standardních logických notací, axiomy číst jako

(C1) ${ displaystyle existuje kappa. { mathit {false}} iff { mathit {false}}}$

(C2) ${ displaystyle x implikuje existuje kappa .x}$

(C3) ${ displaystyle existuje kappa. (x klín existuje kappa .y) iff ( existuje kappa .x) klín ( existuje kappa .y)}$

(C4) ${ Displaystyle existuje kappa existuje lambda .x iff existuje lambda existuje kappa .x}$

(C5) ${ displaystyle kappa = kappa iff { mathit {true}}}$

(C6) Pokud ${ displaystyle kappa}$ je proměnná odlišná od obou ${ displaystyle lambda}$ a ${ displaystyle mu}$, pak ${ Displaystyle lambda = mu iff existuje kappa. ( lambda = kappa klín kappa = mu)}$

(C7) Pokud ${ displaystyle kappa}$ a ${ displaystyle lambda}$ jsou tedy různé proměnné ${ displaystyle existuje kappa. ( kappa = lambda klín x) klín existuje kappa. ( kappa = lambda klín neg x) iff { mathit {false}}}$

Válcová sada algeber

A válcová množinová algebra dimenze ${ displaystyle alpha}$ je algebraická struktura ${ displaystyle (A, cup, cap, -, emptyset, X ^ { alpha}, c _ { kappa}, d _ { kappa lambda}) _ { kappa, lambda < alpha}}$ takhle ${ displaystyle langle X ^ { alpha}, A rangle}$ je pole množin, ${ displaystyle c _ { kappa} S}$ darováno ${ displaystyle {y v X ^ { alpha} mid existuje x v S all beta neq kappa y ( beta) = x ( beta) }}$, a ${ displaystyle d _ { kappa lambda}}$ darováno ${ displaystyle {x v X ^ { alpha} střední x ( kappa) = x ( lambda) }}$.^[1] Nutně validuje axiomy C1 – C7 válcové algebry s ${ displaystyle cup}$ namísto ${ displaystyle +}$, ${ displaystyle cap}$ namísto ${ displaystyle cdot}$, sada komplementu pro komplement, prázdná sada jako 0, ${ displaystyle X ^ { alpha}}$ jako jednotka a ${ displaystyle subseteq}$ namísto ${ displaystyle leq}$. Sada X se nazývá základna.

Ne každá válcová algebra má reprezentaci jako válcová množinová algebra.^{[Citace je zapotřebí ][potřebný příklad ]} Je jednodušší propojit sémantiku predikátové logiky prvního řádu s válcovou množinou algebry. (Další podrobnosti viz Další čtení sekce.)

Zobecnění

Válcové algebry byly zobecněny na případ mnohostranná logika (Caleiro a Gonçalves 2006), který umožňuje lepší modelování duality mezi formulemi a termíny prvního řádu.

Vztah k monadické booleovské algebře

Když ${ displaystyle alpha = 1}$ a ${ displaystyle kappa, lambda}$ jsou tedy omezeny pouze na 0 ${ displaystyle c _ { kappa}}$ se stává ${ displaystyle existuje}$, úhlopříčky lze vynechat a následující teorém cylindrické algebry (Pinter 1973):

${ displaystyle c _ { kappa} (x + y) = c _ { kappa} x + c _ { kappa} y}$

promění se v axiom

${ displaystyle existuje (x + y) = existuje x + existuje y}$

z monadická booleovská algebra. Axiom (C4) vypadne. Na monadickou booleovskou algebru lze tedy pohlížet jako na omezení válcové algebry na jeden proměnný případ.

Viz také

• Abstraktní algebraická logika
• Lambda kalkul a Kombinovaná logika —Další přístupy k modelování kvantifikace a eliminaci proměnných
• Hyperdoktriny plocha kategorický formulace válcových algeber
• Vztah algebry (RA)
• Polyadická algebra

Poznámky

Reference

• Charles Pinter (1973). „Jednoduchá algebra logiky prvního řádu“. Deník Notre Dame formální logiky. XIV: 361–366.
• Leon Henkin, Monk, J.D., a Alfred Tarski (1971) Cylindrické algebry, část I.. Severní Holandsko. ISBN  978-0-7204-2043-2.
• Leon Henkin, Monk, J.D. a Alfred Tarski (1985) Cylindrické algebry, část II. Severní Holandsko.
• Robin Hirsch a Ian Hodkinson (2002) Vztah algebry podle her Studium logiky a základů matematiky, Severní Holandsko
• Carlos Caleiro, Ricardo Gonçalves (2006). „O algebraizaci mnohonásobných logik“ (PDF). V J. Fiadeiro a P.-Y. Schobbens (ed.). Proc. 18. int. konf. k nedávným trendům v technikách algebraického vývoje (WADT). LNCS. 4409. Springer. 21–36. ISBN  978-3-540-71997-7.

Další čtení

• Imieliński, T.; Lipski, W. (1984). Msgstr "Relační model dat a válcových algeber". Journal of Computer and System Sciences. 28: 80–102. doi:10.1016/0022-0000(84)90077-1.

externí odkazy

• příklad válcové algebry od CWoo na planetmath.org