Uno studio sulla negazione in Programmazione Logica

La programmazione logica e un paradigma di programmazione che adotta costrutti logici sia per rappresentare che per elaborare l’informazione. Un programma logico e eseguito "ponendogli delle domande", dette query, e viene determinato, eseguendo un proof engine, a seconda che queste domande siano conseguenze del programma o meno. L’utilizzo delle regole e della sintassi della logica classica al primo ordine e un ovvio candidato a tale scopo, tuttavia i risultati di incompletezza ci dicono che, mentre potremmo essere in grado di dire quando una query segue, non possiamo dire in generale quando non lo fa: questo e il problema della negazione. In questo contesto si e quindi costretti a rinunciare alla completezza (in senso classico) della logica classica a favore di una efficienza sulle possibili query. Prolog e uno dei linguaggi di programmazione logica piu utilizzati, basato sulla logica classica al primo ordine. Escludendo la negazione, e in grado di calcolare esattamente relazioni ricorsivamente enumerabili; tuttavia, se aggiungiamo la negazione, dovremmo aspettarci di avere complementari di relazioni ricorsivamente enumerabili, che potrebbero essere non ricorsivamente enumerabili, e quindi non gestibili da Prolog [per maggiori informazioni sugli insiemi ricorsivamente enumerabili, vedasi Appendice A]. Per questo motivo in Prolog viene aggiunta una versione piu debole di negazione, la negazione come fallimento, in cui si conclude non X se X non e una conseguenza. L’obiettivo di questo studio e un’analisi delle problematiche causate dall’aggiunta della negazione, e una ricerca di metodi, per lo piu teorici, per poterle gestire.