Popis (logika) - Circumscription (logic)

Popis je nemonotónní logika vytvořil John McCarthy formalizovat selský rozum předpoklad, že věci jsou podle očekávání, pokud není uvedeno jinak.^[1]^[2] Popis byl později použit McCarthym ve snaze vyřešit problém s rámem. Aby implementoval omezení ve své původní formulaci, McCarthy rozšířil logika prvního řádu umožnit minimalizaci rozšíření některých predikátů, kde příponou predikátu je sada n-tic hodnot, na kterých je predikát pravdivý. Tato minimalizace je obdobou předpoklad uzavřeného světa že to, co není známo jako pravdivé, je nepravdivé.^[3]

Původním problémem, který McCarthy zvažoval, byl problém misionáři a kanibali: na jednom břehu řeky jsou tři misionáři a tři kanibali; musí překročit řeku pomocí člunu, který může trvat jen dva, s dodatečným omezením, že kanibali nikdy nesmí převýšit počet misionářů na obou březích (jinak by byli misionáři zabiti a pravděpodobně i snědeni). McCarthy nezvažoval problém spočívající v nalezení řady kroků k dosažení cíle (článek o problém misionářů a kanibalů obsahuje jedno takové řešení), ale spíše vyloučení podmínek, které nejsou výslovně uvedeny. Například řešení „jít půl míle na jih a překročit řeku na mostě“ intuitivně neplatí, protože prohlášení o problému takový most nezmiňuje. Na druhou stranu existenci tohoto mostu nevylučuje ani prohlášení o problému. To, že most neexistuje, je důsledkem implicitního předpokladu, že prohlášení o problému obsahuje vše, co je relevantní pro jeho řešení. Výslovné prohlášení, že most neexistuje, není řešením tohoto problému, protože existuje mnoho dalších výjimečných podmínek, které by měly být vyloučeny (například přítomnost lana pro připevnění kanibalů, přítomnost větší lodi v okolí atd.) )

Popis byl později použit McCarthym k formalizování implicitního předpokladu setrvačnost: věci se nemění, pokud není uvedeno jinak. Popis se zdál být užitečný, aby se zabránilo specifikaci, že podmínky se nemění všemi akcemi kromě těch, o nichž je výslovně známo, že je mění; toto je známé jako problém s rámem. Řešení navržené McCarthym se však později ukázalo, což v některých případech, například v EU, vedlo k nesprávným výsledkům Problém střelby Yale scénář. Jiná řešení problému s rámem, která správně formalizují problém s Yaleovým střelením, existují; někteří používají popis, ale jiným způsobem.

Výrokový případ

Zatímco popis byl původně definován v logickém případě prvního řádu, je jeho definování u výrokového případu snazší.^[4] Vzhledem k tomu, výrokový vzorec ${ displaystyle T}$ , jeho popis je vzorec, který má pouze modely z ${ displaystyle T}$ které nepřiřazují proměnnou true, pokud to není nutné.

Formálně mohou být výrokové modely reprezentovány množinami výrokové proměnné; jmenovitě každý model je reprezentován množinou výrokových proměnných, které přiřadí k true. Například model přiřazující true k ${ displaystyle a}$ , false to ${ displaystyle b}$ a věrný ${ displaystyle c}$ je reprezentován množinou ${ displaystyle {a, c }}$ , protože ${ displaystyle a}$ a ${ displaystyle c}$ jsou přesně ty proměnné, které jsou tomuto modelu přiřazeny k true.

Vzhledem k tomu, dva modely ${ displaystyle M}$ a ${ displaystyle N}$ tento stav představoval ${ displaystyle N subseteq M}$ je ekvivalentní k ${ displaystyle M}$ nastavení na true každou proměnnou ${ displaystyle N}$ nastaví na true. Jinými slovy, ${ displaystyle subseteq}$ modeluje vztah „nastavení na skutečně méně proměnných“. ${ displaystyle N podmnožina M}$ znamená, že ${ displaystyle N subseteq M}$ ale tyto dva modely se neshodují.

To nám umožňuje definovat modely, které nepřiřazují proměnné k true, pokud to není nutné ${ displaystyle M}$ a teorie ${ displaystyle T}$ je nazýván minimálnípouze tehdy, pokud neexistuje žádný model ${ displaystyle N}$ z ${ displaystyle T}$ pro který ${ displaystyle N podmnožina M}$ .

Popis je vyjádřen výběrem pouze minimálních modelů. Je definován takto:

{ displaystyle CIRC (T) = {M ~ | ~ M { mbox {je minimální model}} T }}

Alternativně lze definovat ${ displaystyle CIRC (T)}$ jako vzorec, který má přesně výše uvedenou sadu modelů; dále se lze vyhnout definici ${ displaystyle CIRC}$ a definovat pouze minimální odvození jako ${ displaystyle T modely _ {M} Q}$ právě tehdy, když každý minimální model ${ displaystyle T}$ je také modelem ${ displaystyle Q}$ .

Jako příklad vzorec ${ displaystyle T = a land (b lor c)}$ má tři modely:

${ displaystyle a}$ , ${ displaystyle b}$ , ${ displaystyle c}$ jsou pravdivé, tj. ${ displaystyle {a, b, c }}$ ;
${ displaystyle a}$ a ${ displaystyle b}$ jsou pravdivé, ${ displaystyle c}$ je nepravdivé, tj. ${ displaystyle {a, b }}$ ;
${ displaystyle a}$ a ${ displaystyle c}$ jsou pravdivé, ${ displaystyle b}$ je nepravdivé, tj. ${ displaystyle {a, c }}$ .

První model není v sadě proměnných, které přiřazuje true, minimální. Druhý model ve skutečnosti dělá stejná přiřazení kromě ${ displaystyle c}$ , který je přiřazen k false a ne k true. První model proto není minimální. Druhý a třetí model jsou nesrovnatelné: zatímco druhý přiřazuje true ${ displaystyle b}$ , třetí přiřadí true ${ displaystyle c}$ namísto. Proto modely vymezují ${ displaystyle T}$ jsou druhým a třetím modelem seznamu. Propoziční vzorec, který má přesně tyto dva modely, je následující:

{ displaystyle a land neg (b leftrightarrow c)}

Intuitivně je v rámci popisu proměnná přiřazena k hodnotě true, pouze pokud je to nutné. Dvojí, pokud proměnná umět buď falešný musí být falešný. Například alespoň jeden z ${ displaystyle b}$ a ${ displaystyle c}$ musí být přiřazen k true podle ${ displaystyle T}$ ; v popisu musí přesně jedna ze dvou proměnných platit. Proměnná ${ displaystyle a}$ nemůže být nepravdivý v žádném modelu ${ displaystyle T}$ a ani jeden z popisu.

Opravené a měnící se predikáty

Rozšíření popisu s pevnými a proměnlivými predikáty je způsobeno Vladimír Lifschitz.^[5] Myšlenka je, že některé podmínky nelze minimalizovat. Z hlediska výrokové logiky nelze některé proměnné pokud možno falšovat. Zvažovat lze zejména dva druhy proměnných:

různé: jedná se o proměnné, které se v průběhu minimalizace vůbec nezohledňují;

pevný: to jsou proměnné považované za pevné při minimalizaci; jinými slovy, minimalizaci lze provést pouze porovnáním modelů se stejnými hodnotami těchto proměnných.

Rozdíl je v tom, že hodnota proměnlivých podmínek se jednoduše předpokládá, že na tom nezáleží. Pevné podmínky místo toho charakterizují možnou situaci, takže srovnání dvou situací, kdy mají tyto podmínky jinou hodnotu, nemá smysl.

Formálně je rozšíření popisu, které zahrnuje proměnné a pevné proměnné, následující, kde ${ displaystyle P}$ je sada proměnných k minimalizaci, ${ displaystyle Z}$ pevné proměnné a proměnné proměnné nejsou v ${ displaystyle P cup Z}$ :

{ displaystyle { text {CIRC}} (T; P, Z) = {M ~ | ~ M modely T { text {a}} ne existuje N { text {takový, že}} N modely T, ~ N cap P podmnožina M cap P { text {a}} N cap Z = M cap Z }}

Slovy, minimalizace proměnných přiřazených k true se provádí pouze pro proměnné v ${ displaystyle P}$ ; kromě toho se modely porovnávají, pouze pokud proměnným proměnné přiřazují stejné hodnoty ${ displaystyle Z}$ . Při porovnávání modelů nejsou brány v úvahu všechny ostatní proměnné.

Řešení rámcového problému navrženého McCarthym je založeno na popisu bez pevných podmínek. V propozičním případě lze toto řešení popsat následovně: kromě vzorců přímo kódujících to, co je známé, definujeme také nové proměnné představující změny hodnot podmínek; tyto nové proměnné jsou poté minimalizovány.

Například z domény, ve které jsou dveře, které jsou zavřeny v čase 0 a ve které je akce otevření dveří provedena v čase 2, je to, co je výslovně známé, představováno dvěma vzorci:

{ displaystyle neg { text {open}} _ {0}}

{ displaystyle { text {true}} rightarrow { text {open}} _ {2}}

Problém rámce se v tomto příkladu zobrazuje jako problém, který ${ displaystyle neg open_ {1}}$ není důsledkem výše uvedených vzorců, zatímco dveře mají zůstat zavřené, dokud není provedena akce jejich otevření. K tomuto účelu lze použít popis pomocí definice nových proměnných ${ změna zobrazení _open_ {t}}$ modelovat změny a poté je minimalizovat:

{ displaystyle { text {change open}} _ {0} equiv ({ text {open}} _ {0} not equiv { text {open}} _ {1})}

{ displaystyle { text {change open}} _ {1} equiv ({ text {open}} _ {1} not equiv { text {open}} _ {2})}

...

Jak ukazuje Problém střelby Yale, tento druh řešení nefunguje. Například, ${ displaystyle neg { text {open}} _ {1}}$ ještě neznamená omezení výše uvedených vzorců: model, ve kterém ${ displaystyle { text {change open}} _ {0}}$ je pravda a ${ displaystyle { text {change open}} _ {1}}$ je false je nesrovnatelné s modelem s opačnými hodnotami. Situace, kdy se dveře v okamžiku 1 otevřou a poté zůstanou otevřené v důsledku akce, tedy není vyloučena omezením.

Bylo vyvinuto několik dalších formalizací dynamických domén, které netrpí takovými problémy (viz problém s rámem pro přehled). Mnoho lidí používá popis, ale jiným způsobem.

Predikční omezení

Původní definice omezení navržená McCarthym je o logice prvního řádu. Role proměnných ve výrokové logice (něco, co může být pravda nebo nepravda) hrají v logice prvního řádu predikáty. Totiž výrokový vzorec lze vyjádřit v logice prvního řádu nahrazením každé výrokové proměnné predikátem nulové arity (tj. Predikát bez argumentů). Proto se minimalizace provádí u predikátů v logické verzi prvního řádu s popisem: je získán popis vzorce, který nutí predikáty být nepravdivé, kdykoli je to možné.^[6]

Vzhledem k logickému vzorci prvního řádu ${ displaystyle T}$ obsahující a predikát ${ displaystyle P}$ , vymezení tohoto predikátu znamená výběr pouze modelů ${ displaystyle T}$ ve kterém ${ displaystyle P}$ je přiřazen k true na minimální sadě n-tic hodnot.

Formálně rozšíření predikátu v modelu prvního řádu je sada n-tic hodnot, které tento predikát v modelu přiřadí k true. Modely prvního řádu skutečně zahrnují vyhodnocení každého predikátového symbolu; takové hodnocení říká, zda je predikát pravdivý nebo nepravdivý pro jakoukoli možnou hodnotu jeho argumentů.^[7] Vzhledem k tomu, že každý argument predikátu musí být termínem a každý člen se hodnotí na hodnotu, modely říkají, zda ${ displaystyle P (v_ {1}, ldots, v_ {n})}$ platí pro jakoukoli možnou n-tici hodnot ${ displaystyle langle v_ {1}, ldots, v_ {n} rangle}$ . Rozšíření ${ displaystyle P}$ v modelu je množina n-tic výrazů taková ${ displaystyle P (v_ {1}, ldots, v_ {n})}$ platí v modelu.

Popis predikátu ${ displaystyle P}$ ve vzorci ${ displaystyle T}$ se získá výběrem pouze modelů ${ displaystyle T}$ s minimálním rozšířením ${ displaystyle P}$ . Například pokud má vzorec pouze dva modely, liší se jen proto, že ${ displaystyle P (v_ {1}, ldots, v_ {n})}$ je true v jednom a false v druhém, pak je vybrán pouze druhý model. To je proto, že ${ displaystyle langle v_ {1}, ldots, v_ {n} rangle}$ je v rozšíření ${ displaystyle P}$ v prvním modelu, ale ne ve druhém.

Původní definice McCarthyho byla spíše syntaktická než sémantická. Daný vzorec ${ displaystyle T}$ a predikát ${ displaystyle P}$ , vymezující ${ displaystyle P}$ v ${ displaystyle T}$ je následující vzorec druhého řádu:

{ Displaystyle T (P) klín forall p neg (T (p) klín p

V tomto vzorci ${ displaystyle p}$ je predikát stejné arity jako ${ displaystyle P}$ . Toto je vzorec druhého řádu, protože obsahuje kvantifikaci nad predikátem. Podformule ${ displaystyle p$ je zkratka pro:

{ displaystyle forall x (p (x) rightarrow P (x)) klín neg forall x (P (x) rightarrow p (x))}

V tomto vzorci ${ displaystyle x}$ je n-tice členů, kde n je arity ${ displaystyle P}$ . Tento vzorec uvádí, že je třeba provést minimalizaci rozšíření: aby bylo možné vyhodnotit pravdu ${ displaystyle P}$ uvažovaného modelu musí platit, že žádný jiný predikát ${ displaystyle p}$ může přiřadit k nule každou n-tici ${ displaystyle P}$ přiřadí k false a přesto se liší od ${ displaystyle P}$ .

Tato definice umožňuje vymezit pouze jeden predikát. Zatímco rozšíření na více než jeden predikát je triviální, minimalizace rozšíření jednoho predikátu má důležitou aplikaci: zachycení myšlenky, že věci jsou obvykle podle očekávání. Tuto myšlenku lze formalizovat minimalizací jediného predikátu vyjadřujícího abnormality situací. Každá známá skutečnost je vyjádřena logicky s přídavkem literálu ${ displaystyle neg Abnormální (...)}$ s uvedením, že skutečnost platí pouze v normálních situacích. Minimalizace rozšíření tohoto predikátu umožňuje uvažování za implicitního předpokladu, že věci jsou podle očekávání (tj. Nejsou abnormální) a že tento předpoklad je vytvořen, pouze pokud je to možné (abnormalitu lze považovat za nepravdivou, pouze pokud je to v souladu s fakta.)

Bodový popis

Bodový popis je varianta popisu prvního řádu, kterou zavedl Vladimír Lifschitz.^[8] V propozičním případě se bodová a predikční okolnost shodují. Důvodem pointpoint circumscription je to, že minimalizuje hodnotu predikátu pro každou n-tici hodnot samostatně, spíše než minimalizuje rozšíření predikátu. Například existují dva modely ${ Displaystyle P (a) equiv P (b)}$ s doménou ${ displaystyle {a, b }}$ , jedno nastavení ${ displaystyle P (a) = P (b) = nepravdivé}$ a další nastavení ${ displaystyle P (a) = P (b) = pravda}$ . Od rozšíření ${ displaystyle P}$ v prvním modelu je ${ displaystyle emptyset}$ zatímco rozšíření pro druhý je ${ displaystyle {a, b }}$ , popis vybírá pouze první model.

V bodovém popisu je každá n-tice hodnot považována samostatně. Například ve vzorci ${ Displaystyle P (a) equiv P (b)}$ jeden by zvažoval hodnotu ${ displaystyle P (a)}$ odděleně od ${ displaystyle P (b)}$ . Model je minimální pouze v případě, že není možné změnit libovolnou takovou hodnotu z true na false a přitom splňovat vzorec. Výsledkem je model, ve kterém ${ displaystyle P (a) = P (b) = pravda}$ je vybrán bodovým omezením, protože pouze otáčení ${ displaystyle P (a)}$ do false nesplňuje vzorec a totéž se děje pro ${ displaystyle P (b)}$ .

Popis domény a vzorce

Dřívější formulace popisu od McCarthyho je založena na minimalizaci doména modelů prvního řádu, nikoli rozšíření predikátů. Konkrétně je model považován za méně než jiný, pokud má menší doménu a dva modely se shodují při vyhodnocení společných n-tic hodnot. Tuto verzi omezení lze zredukovat na predikční omezení.

Popis vzorce byl pozdější formalismus zavedený McCarthym. Toto je zobecnění popisu, ve kterém je rozšíření vzorce minimalizováno, spíše než rozšíření predikátu. Jinými slovy lze zadat vzorec tak, aby byla sada n-tic hodnot domény, které splňují vzorec, co nejmenší.

Teorie omezování

Opis nemusí vždy správně zacházet s disjunktivními informacemi. Ray Reiter za předpokladu, že následující příklad: mince je hodena přes šachovnici a výsledkem je, že mince je buď na černé ploše, nebo na bílé ploše, nebo na obou. Existuje však celá řada dalších možných míst, kde by mince neměla být; je například implicitní, že mince není na podlaze, na ledničce nebo na povrchu měsíce. K minimalizaci prodloužení o. Lze proto použít popis ${ displaystyle zapnuto}$ predikát, takže ${ displaystyle zapnuto ({ text {coin}}, { text {moon}})}$ je nepravdivé, i když to není výslovně uvedeno.

Na druhou stranu minimalizace ${ displaystyle zapnuto}$ predikát vede k nesprávnému výsledku, že mince je buď na černé ploše, nebo na bílé ploše, ale ne obojí. Je to proto, že modely, ve kterých ${ displaystyle zapnuto}$ platí pouze na ${ displaystyle ({ text {coin}}, { text {bílá oblast}})}$ a jen na ${ displaystyle ({ text {coin}}, { text {černá oblast}})}$ mít minimální příponu ${ displaystyle zapnuto}$ , zatímco model, ve kterém rozšíření ${ displaystyle zapnuto}$ se skládá z obou párů není minimální.

Omezení teorie je řešením navrženým Thomas Eiter, Georg Gottlob, a Jurij Gurevič.^[9] Myšlenka spočívá v tom, že model, který je popsán, se nepodaří vybrat, ten, ve kterém oba ${ displaystyle zapnuto ({ text {coin}}, { text {bílá oblast}})}$ a ${ displaystyle zapnuto ({ text {coin}}, { text {černá oblast}})}$ jsou pravdivé, je model vzorce, který je větší (w.r.t. přípona ${ displaystyle zapnuto}$ ) než oba dva vybrané modely. Přesněji řečeno, mezi modely vzorce je vyloučený model nejmenší horní mez ze dvou vybraných modelů. Omezení teorie vybírá takové modely s nejmenšími horními hranicemi kromě těch, které jsou vybrány podle popisu. Toto zahrnutí se provádí, dokud není sada modelů uzavřena, v tom smyslu, že zahrnuje všechny nejmenší horní hranice všech sad modelů, které obsahuje.

Viz také

Reference

^ McCarthy, J. (únor 1986). "Aplikace omezení na formalizaci znalostí zdravého rozumu". Umělá inteligence. 28 (1): 89–116. doi: 10,1016 / 0004-3702 (86) 90032-9.
^ McCarthy, J. (duben 1980). "Popis - forma non-monotónního uvažování". Umělá inteligence. 13: 27–39. doi: 10,1016 / 0004-3702 (80) 90011-9.
^ Eiter, T .; Gottlob, G. (červen 1993). "Propoziční omezení a argumenty rozšířeného uzavřeného světa jsou Pi ^ p_2-úplné". Teoretická informatika. 114 (2): 231–245. doi: 10,1016 / 0304-3975 (93) 90073-3.
^ Cadoli, M .; Lenzerini, M. (duben 1994). "Složitost propozičního uvažování a omezení uzavřeného světa". Journal of Computer and System Sciences. 48 (2): 255–310. doi: 10.1016 / S0022-0000 (05) 80004-2.
^ Lifschitz, V. (listopad 1985). "Databáze uzavřeného světa a popis". Umělá inteligence. 27: 229–235. doi: 10,1016 / 0004-3702 (85) 90055-4.
^ Lifschitz, V. (1994). "Popis". V Gabbay, D.M .; Hogger, C.J .; Robinson, J.A. Nemonotonické zdůvodnění a nejisté zdůvodnění. Příručky logiky v informatice a umělé inteligenci a logické programování. 3. Oxford University Press. 297–352. ISBN 0198537476.
^ Cadoli, M. (listopad 1992). "Složitost kontroly modelu pro popisné vzorce". Dopisy o zpracování informací. 44 (3): 113–8. doi: 10.1016 / 0020-0190 (92) 90049-2.
^ Lifschitz, V. (1986). "Bodový popis". Sborník AAAI-86 Pátá národní konference o umělé inteligenci, 11. – 15. Srpna 1986, Philadelphia, PA. 406–410. ISBN 0934613133.
^ Eiter, T .; Gottlob, G .; Gurevich, Y. (1993). „CURB vaše teorie!“. V Bajcsy, Růženě. IJCAI-93: sborník z Třinácté mezinárodní společné konference o umělé inteligenci, Chambéry, Francie, 28. srpna - 3. září 1993. IJCAII. str. 634–9. ISBN 155860300X.

externí odkazy

Popis - forma nonmonotonic uvažování, papír od McCarthyho.
Vysvětlení ve Stanfordské encyklopedii o filozofii

[1] McCarthy, J. (únor 1986). "Aplikace omezení na formalizaci znalostí zdravého rozumu". Umělá inteligence. 28 (1): 89–116. doi: 10,1016 / 0004-3702 (86) 90032-9.

[2] McCarthy, J. (duben 1980). "Popis - forma non-monotónního uvažování". Umělá inteligence. 13: 27–39. doi: 10,1016 / 0004-3702 (80) 90011-9.

[3] Eiter, T .; Gottlob, G. (červen 1993). "Propoziční omezení a argumenty rozšířeného uzavřeného světa jsou Pi ^ p_2-úplné". Teoretická informatika. 114 (2): 231–245. doi: 10,1016 / 0304-3975 (93) 90073-3.

[4] Cadoli, M .; Lenzerini, M. (duben 1994). "Složitost propozičního uvažování a omezení uzavřeného světa". Journal of Computer and System Sciences. 48 (2): 255–310. doi: 10.1016 / S0022-0000 (05) 80004-2.

[5] Lifschitz, V. (listopad 1985). "Databáze uzavřeného světa a popis". Umělá inteligence. 27: 229–235. doi: 10,1016 / 0004-3702 (85) 90055-4.

[6] Lifschitz, V. (1994). "Popis". V Gabbay, D.M .; Hogger, C.J .; Robinson, J.A. Nemonotonické zdůvodnění a nejisté zdůvodnění. Příručky logiky v informatice a umělé inteligenci a logické programování. 3. Oxford University Press. 297–352. ISBN 0198537476.

[7] Cadoli, M. (listopad 1992). "Složitost kontroly modelu pro popisné vzorce". Dopisy o zpracování informací. 44 (3): 113–8. doi: 10.1016 / 0020-0190 (92) 90049-2.

[8] Lifschitz, V. (1986). "Bodový popis". Sborník AAAI-86 Pátá národní konference o umělé inteligenci, 11. – 15. Srpna 1986, Philadelphia, PA. 406–410. ISBN 0934613133.

[9] Eiter, T .; Gottlob, G .; Gurevich, Y. (1993). „CURB vaše teorie!“. V Bajcsy, Růženě. IJCAI-93: sborník z Třinácté mezinárodní společné konference o umělé inteligenci, Chambéry, Francie, 28. srpna - 3. září 1993. IJCAII. str. 634–9. ISBN 155860300X.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]