Mnohostranná logika - Many-sorted logic

Mnohostranná logika může formálně odrážet náš záměr nezacházet s vesmírem jako homogenní sbírka předmětů, ale rozdělit je to podobné jako u typů v typické programování. Funkční i asertivní “části řeči „v jazyce logiky odrážejí toto typické rozdělení vesmíru, a to i na úrovni syntaxe: substituci a předávání argumentů lze provádět pouze odpovídajícím způsobem, při respektování„ druhů “.

Výše uvedený záměr lze formalizovat různými způsoby; A mnohostranná logika je jakýkoli balíček informací, který jej splňuje. Ve většině případů jsou uvedeny následující:

soubor druhů, S
an vhodné zobecnění pojmu podpis být schopen zpracovat další informace, které přicházejí s druhy.

The doména diskurzu ze všech struktura tohoto podpisu je pak fragmentován do nesouvislých podmnožin, jedna pro každý druh.

Příklad

Při úvahách o biologických organismech je užitečné rozlišovat dva druhy: ${displaystyle mathrm {rostlina}}$ a ${displaystyle mathrm {animal}}$ . Zatímco funkce ${displaystyle mathrm {matka} dvojtečka mathrm {zvíře} o mathrm {zvíře}}$ dává smysl, podobná funkce ${displaystyle mathrm {matka} dvojtečka mathrm {rostlina} o mathrm {rostlina}}$ obvykle ne. Mnohostříděná logika umožňuje mít výrazy jako ${displaystyle mathrm {matka} (mathrm {lassie})}$ , ale zahodit výrazy jako ${displaystyle mathrm {mother} (mathrm {my _favorite _oak})}$ jako syntakticky špatně formovaný.

Algebraizace

Algebraizace mnohonásobné logiky je vysvětlena v článku Caleira a Gonçalvese,^[1] který zobecňuje abstraktní algebraická logika k mnoha seřazeným případům, ale lze je také použít jako úvodní materiál.

Logika seřazená podle objednávky

Zatímco mnoho seřazeno logika vyžaduje dva odlišné druhy, aby měla nesouvislé vesmírné sady, seřazeno podle objednávky logika umožňuje jeden druh ${displaystyle s_ {1}}$ být prohlášen za podřízený jiného druhu ${displaystyle s_ {2}}$ , obvykle psaním ${displaystyle s_ {1} subseteq s_ {2}}$ nebo podobná syntaxe. V výše uvedený příklad, je žádoucí deklarovat

{displaystyle {extit {dog}} subseteq {extit {masožravec}}}

,

{displaystyle {extit {dog}} subseteq {extit {savec}}}

,

{displaystyle {extit {carnivore}} subseteq {extit {animal}}}

,

{displaystyle {extit {save}}} subseteq {extit {animal}}}

,

{displaystyle {extit {animal}} subseteq {extit {organismus}}}

,

{displaystyle {extit {rostlina}} subseteq {extit {organismus}}}

,

a tak dále.

Kdekoli nějaký termín ${displaystyle s}$ je vyžadován termín jakéhokoli podřízeného účtu ${displaystyle s}$ místo toho mohou být dodány (Princip substituce Liskov ). Například za předpokladu deklarace funkce ${displaystyle {extit {matka}}: {extit {animal}} longrightarrow {extit {animal}}}$ a konstantní deklarace ${displaystyle {extit {lassie}}: {extit {dog}}}$ , termín ${displaystyle {extit {matka}} ({extit {lassie}})}$ je naprosto platný a má svůj druh ${displaystyle {extit {animal}}}$ . Za účelem poskytnutí informace, že matka psa je zase pes, další prohlášení ${displaystyle {extit {matka}}: {extit {dog}} longrightarrow {extit {pes}}}$ mohou být vydány; tomu se říká přetížení funkce, podobný přetížení v programovacích jazycích.

Logiku seřazenou podle objednávek lze převést do netříděné logiky pomocí unárního predikátu ${displaystyle p_ {i} (x)}$ pro každý druh ${displaystyle s_ {i}}$ a axiom ${displaystyle forall x (p_ {i} (x) ightarrow p_ {j} (x))}$ pro každé podřízené prohlášení ${displaystyle s_ {i} subseteq s_ {j}}$ . Zpětný přístup byl úspěšný v automatizovaném dokazování vět: v roce 1985 Christoph Walther mohl vyřešit srovnávací problém tehdy tím, že jej přeložil do logiky seřazené podle pořadí, čímž jej zredukoval o řádovou velikost, protože mnoho unárních predikátů se změnilo v druhy.^[2]

Aby bylo možné začlenit logiku seřazenou podle pořadí do automatizovaného ověřovače vět založeného na klauzuli, odpovídající sjednocení podle objednávky je nutný algoritmus, který vyžaduje pro dva deklarované druhy ${displaystyle s_ {1}, s_ {2}}$ jejich křižovatka ${displaystyle s_ {1} cap s_ {2}}$ bude také deklarováno: pokud ${displaystyle x_ {1}}$ a ${displaystyle x_ {2}}$ jsou proměnné svého druhu ${displaystyle s_ {1}}$ a ${displaystyle s_ {2}}$ rovnice ${displaystyle x_ {1} {stackrel {?} {=}}, x_ {2}}$ má řešení ${displaystyle {x_ {1} = x,; x_ {2} = x}}$ , kde ${displaystyle x: s_ {1} cap s_ {2}}$ .

Smolka zobecnila logiku seřazenou podle objednávek parametrický polymorfismus.^[3]^[4]V jeho rámci jsou podřízené deklarace šířeny do komplexních výrazů typu. Jako příklad programování je to parametrické řazení ${displaystyle {extit {list}} (X)}$ mohou být deklarovány (s ${displaystyle X}$ být parametrem typu jako v a Šablona C ++ ) a z deklarace subsortu ${displaystyle {extit {int}} subseteq {extit {float}}}$ vztah ${displaystyle {extit {list}} ({extit {int}}) subseteq {extit {list}} ({extit {float}})}$ je automaticky odvozeno, což znamená, že každý seznam celých čísel je také seznamem plováků.

Schmidt-Schauß zobecněná logika seřazená podle objednávky, která umožňuje termíny deklarací.^[5]Jako příklad předpokládáme deklarace subsortu ${displaystyle {extit {even}} subseteq {extit {int}}}$ a ${displaystyle {extit {odd}} subseteq {extit {int}}}$ , termínová deklarace jako ${displaystyle forall i: {extit {int}}.; (i + i): {extit {even}}}$ umožňuje deklarovat vlastnost přidání celého čísla, kterou nelze vyjádřit běžným přetížením.

Viz také

Reference

^ Carlos Caleiro, Ricardo Gonçalves (2006). "O algebraizaci mnoha seřazených logik". Proc. 18. int. konf. k nedávným trendům v technikách algebraického vývoje (WADT) (PDF). Springer. 21–36. ISBN 978-3-540-71997-7.
^ Walther, Christoph (1985). „Mechanické řešení Schubertova parního válce podle mnohonásobného rozlišení“ (PDF). Artif. Intell. 26 (2): 217–224. doi:10.1016/0004-3702(85)90029-3.
^ Smolka, Gert (listopad 1988). "Logické programování s polymorfně seřazenými typy podle pořadí". Int. Workshop Algebraické a logické programování. LNCS. 343. Springer. str. 53–70.
^ Smolka, Gert (květen 1989), Logické programování přes polymorfně seřazené typy podle pořadí, Univ. Kaiserslautern, Německo
^ Schmidt-Schauß, Manfred (duben 1988). Výpočtové aspekty logiky seřazené podle objednávky s deklaracemi termínů. LNAI. 395. Springer.

První články o mnohonásobné logice zahrnují:

Wang, Hao (1952). "Logika mnoha seřazených teorií". Journal of Symbolic Logic. 17: 105–116. doi:10.2307/2266241., shromážděné v autorovi Výpočet, logika, filozofie. Sbírka esejů, Peking: Science Press; Dordrecht: Kluwer Academic, 1990.
Gilmore, P.C. (1958). „Dodatek k“ Logice mnoha seřazených teorií"" (PDF). Compositio Mathematica. 13: 277–281.
A. Oberschelp (1962). „Untersuchungen zur mehrsortigen Quantorenlogik“. Mathematische Annalen. 145 (4): 297–333. doi:10.1007 / bf01396685. Archivovány od originál dne 2015-02-20. Citováno 2013-09-11.
F. Jeffry Pelletier (1972). „Třídicí kvantifikace a omezená kvantifikace“ (PDF). Filozofické studie. 23: 400–404. doi:10.1007 / bf00355532.

externí odkazy

"Mnohokrát seřazená logika", první kapitola v Poznámky k přednášce o rozhodovacích postupech podle Calogero G. Zarba

[1] Carlos Caleiro, Ricardo Gonçalves (2006). "O algebraizaci mnoha seřazených logik". Proc. 18. int. konf. k nedávným trendům v technikách algebraického vývoje (WADT) (PDF). Springer. 21–36. ISBN 978-3-540-71997-7.

[2] Walther, Christoph (1985). „Mechanické řešení Schubertova parního válce podle mnohonásobného rozlišení“ (PDF). Artif. Intell. 26 (2): 217–224. doi:10.1016/0004-3702(85)90029-3.

[3] Smolka, Gert (listopad 1988). "Logické programování s polymorfně seřazenými typy podle pořadí". Int. Workshop Algebraické a logické programování. LNCS. 343. Springer. str. 53–70.

[4] Smolka, Gert (květen 1989), Logické programování přes polymorfně seřazené typy podle pořadí, Univ. Kaiserslautern, Německo

[5] Schmidt-Schauß, Manfred (duben 1988). Výpočtové aspekty logiky seřazené podle objednávky s deklaracemi termínů. LNAI. 395. Springer.

[1]

[2]

[3]

[4]

[5]