Semantica modelului stabil

Modelul stabil ^[1] (modelul stabil), sau setul de răspunsuri, este un concept folosit pentru a defini o semantică declarativă în programarea logică cu negație. Conceptul de model stabil, introdus de Gelfond și Lifschitz în 1988, ^[2] stă la baza programării setului de răspunsuri .

Introducere

Având în vedere următorul program:

p\

{\ displaystyle p \}

p \

r\leftarrow p,\ q

{\ displaystyle r \ leftarrow p, \ q}

{\ displaystyle r \ leftarrow p, \ q}

s\leftarrow p,\ {\hbox{not }}q.

{\ displaystyle s \ leftarrow p, \ {\ hbox {not}} q.}

{\ displaystyle s \ leftarrow p, \ {\ hbox {not}} q.}

interogarea $p$ ${\ displaystyle p}$ $p$ va avea succes, după cum indică programul $p$ ${\ displaystyle p}$ $p$ ca fapt; interogarea $q$ ${\ displaystyle q}$ $q$ va eșua pentru negare în mod implicit , deoarece nu este necesar nicăieri în partea stângă a regulilor programului. Și interogarea $r$ ${\ displaystyle r}$ $r$ va eșua, deoarece un atom cu o valoare negativă apare în corpul regulii. În cele din urmă, interogarea $s$ ${\ displaystyle s}$ $s$ va avea succes, deoarece este scopul $p$ ${\ displaystyle p}$ $p$ acea ${\hbox{not }}q$ ${\ displaystyle {\ hbox {not}} q}$ ${\ displaystyle {\ hbox {not}} q}$ sunt pozitivi. Prin urmare, interpretarea implicită $THE$ ${\ displaystyle I}$ $THE$ dintre cele patru litere vor fi următoarele:

$p$ ${\ displaystyle p}$ $p$	$q$ ${\ displaystyle q}$ $q$	$r$ ${\ displaystyle r}$ $r$	$s$ ${\ displaystyle s}$ $s$
T.	F.	F.	T.

Dacă calculăm valorile adevărului regulilor programului folosind interpretarea de mai sus, toate se vor dovedi a fi T. Cu alte cuvinte, interpretarea $THE$ ${\ displaystyle I}$ $THE$ este un model al programului.

Cu toate acestea, pot exista și alte interpretări, în general non-minime, care fac adevărate toate regulile programului. În acest caz:

$p$ ${\ displaystyle p}$ $p$	$q$ ${\ displaystyle q}$ $q$	$r$ ${\ displaystyle r}$ $r$	$s$ ${\ displaystyle s}$ $s$
T.	T.	T.	F.

Această interpretare, pe care o numim ${THE}^{'}$ ${\ displaystyle I '}$ $„$ este un model non-minim al programului, deoarece are o cardinalitate mai mare decât $THE$ ${\ displaystyle I}$ $THE$ (referit ca $I<I'$ ${\ displaystyle I <I '}$ ${\ displaystyle I <I '}$ ).

Definiție

Este $P.$ ${\ displaystyle P}$ $P.$ un program format din reguli exprimate în următoarea formă:

A\leftarrow B_{1},\dots ,B_{m},{\hbox{not }}C_{1},\dots ,{\hbox{not }}C_{n}

{\ displaystyle A \ leftarrow B_ {1}, \ dots, B_ {m}, {\ hbox {not}} C_ {1}, \ dots, {\ hbox {not}} C_ {n}}

{\ displaystyle A \ leftarrow B_ {1}, \ dots, B_ {m}, {\ hbox {not}} C_ {1}, \ dots, {\ hbox {not}} C_ {n}}

unde este $A,B_{1},\dots ,B_{m},C_{1},\dots ,C_{n}$ ${\ displaystyle A, B_ {1}, \ dots, B_ {m}, C_ {1}, \ dots, C_ {n}}$ ${\ displaystyle A, B_ {1}, \ dots, B_ {m}, C_ {1}, \ dots, C_ {n}}$ sunt atomi la sol , adică nu conțin variabile. De sine $P.$ ${\ displaystyle P}$ $P.$ nu conține negative ( $n=0$ ${\ displaystyle n = 0}$ $n = 0$ în fiecare regulă a programului), prin definiție, singurul model stabil al $P.$ ${\ displaystyle P}$ $P.$ este modelul său minimal.

Pentru a extinde această definiție la cazul programelor cu negație, este necesar conceptul auxiliar de „reducere”, definit astfel.

Pentru fiecare set $THE$ ${\ displaystyle I}$ $THE$ de atomi la sol , o reducere de $P.$ ${\ displaystyle P}$ $P.$ relativ la $THE$ ${\ displaystyle I}$ $THE$ —Indicat cu $P^{I}$ ${\ displaystyle P ^ {I}}$ ${\ displaystyle P ^ {I}}$ —Este setul de reguli fără negarea obținută de la $P.$ ${\ displaystyle P}$ $P.$ eliminarea:

fiecare regulă pe care o am $C_{i}$ ${\ displaystyle C_ {i}}$ $Acolo}$ în corpul lui, dacă $C_{i}\in I$ ${\ displaystyle C_ {i} \ în I}$ ${\ displaystyle C_ {i} \ în I}$ ;
pretutindeni $not\ C_{j}$ ${\ displaystyle not \ C_ {j}}$ ${\ displaystyle not \ C_ {j}}$ în cadrul celorlalte reguli.

Să spunem asta $THE$ ${\ displaystyle I}$ $THE$ este un model stabil (sau un set de răspunsuri ) de $P.$ ${\ displaystyle P}$ $P.$ de sine $THE$ ${\ displaystyle I}$ $THE$ este un model stabil de $P^{I}$ ${\ displaystyle P ^ {I}}$ ${\ displaystyle P ^ {I}}$ . Deoarece reducerea nu conține negative, definiția modelului stabil pentru acesta din urmă a fost deja dată, astfel încât definiția nu este recursivă.

În general, un program poate avea mai multe seturi de răspunsuri .

Exemplu

Pentru a ilustra definițiile de mai sus, să verificăm asta $I=\{p,s\}$ ${\ displaystyle I = \ {p, s \}}$ ${\ displaystyle I = \ {p, s \}}$ este un model stabil pentru program:

p\

{\ displaystyle p \}

p \

r\leftarrow p,\ q

{\ displaystyle r \ leftarrow p, \ q}

{\ displaystyle r \ leftarrow p, \ q}

s\leftarrow p,\ {\hbox{not }}q.

{\ displaystyle s \ leftarrow p, \ {\ hbox {not}} q.}

{\ displaystyle s \ leftarrow p, \ {\ hbox {not}} q.}

Reducerea acestui program comparativ cu $THE$ ${\ displaystyle I}$ $THE$ Și:

p\

{\ displaystyle p \}

p \

r\leftarrow p,\ q

{\ displaystyle r \ leftarrow p, \ q}

{\ displaystyle r \ leftarrow p, \ q}

s\leftarrow p.

{\ displaystyle s \ leftarrow p.}

{\ displaystyle s \ leftarrow p.}

(de cand $q\not \in I$ ${\ displaystyle q \ not \ in I}$ ${\ displaystyle q \ not \ in I}$ , reducerea se realizează prin îndepărtare ${\hbox{not }}q\$ ${\ displaystyle {\ hbox {not}} q \}$ ${\ displaystyle {\ hbox {not}} q \}$ în toate regulile care îl conțin)
Modelul stabil (adică modelul minim) de reducere $P^{I}$ ${\ displaystyle P ^ {I}}$ ${\ displaystyle P ^ {I}}$ este exact $\{p,s\}$ ${\ displaystyle \ {p, s \}}$ ${\ displaystyle \ {p, s \}}$ . În consecință, $I=\{p,s\}$ ${\ displaystyle I = \ {p, s \}}$ ${\ displaystyle I = \ {p, s \}}$ este un model stabil pentru program.

Prin verificarea celorlalte 15 seturi posibile care conțin atomii $p,\ q,\ r,\ s$ ${\ displaystyle p, \ q, \ r, \ s}$ ${\ displaystyle p, \ q, \ r, \ s}$ se arată că programul nu are alte modele stabile.
De exemplu, reducerea legată de interpretare $I'=\{p,q,r\}$ ${\ displaystyle I '= \ {p, q, r \}}$ ${\ displaystyle I '= \ {p, q, r \}}$ Și:

p\

{\ displaystyle p \}

p \

r\leftarrow p,\ q.

{\ displaystyle r \ leftarrow p, \ q.}

{\ displaystyle r \ leftarrow p, \ q.}

(de cand $q\in I'$ ${\ displaystyle q \ in I '}$ ${\ displaystyle q \ in I '}$ , reducerea se obține prin eliminarea din program a tuturor regulilor care conțin ${\hbox{not }}q\$ ${\ displaystyle {\ hbox {not}} q \}$ ${\ displaystyle {\ hbox {not}} q \}$ )
Modelul stabil (adică modelul minim) de reducere $P^{I'}$ ${\ displaystyle P ^ {I '}}$ ${\ displaystyle P ^ {I '}}$ Și $\{p\}$ ${\ displaystyle \ {p \}}$ ${\ displaystyle \ {p \}}$ , care este diferit de interpretarea inițială.

Notă

^ Russel-Norvig , p. 453.
^ (EN) Paul Liberatore, Stable Model Semantics , pe cs.cmu.edu, Universitatea Carnegie Mellon . Accesat la 2 aprilie 2016 ( arhivat la 15 septembrie 2015) .

Bibliografie

M. Gelfond și V. Lifschitz, Semantica modelului stabil pentru programarea logică , în Proceedings of the Fifth Logic Programming Symposium , The MIT Press, 1988, pp. 1070-1080.
Stuart Russel, Peter Norvig, Inteligența artificială - O abordare modernă , vol. 1, ediția a II-a, Milano, Pearson Education Italia, 2005, ISBN 88-7192-228-X .

Elemente conexe

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] Russel-Norvig , p. 453.

[liberatore-2] (EN) Paul Liberatore, Stable Model Semantics , pe cs.cmu.edu, Universitatea Carnegie Mellon . Accesat la 2 aprilie 2016 ( arhivat la 15 septembrie 2015) .

[1]

[2]