Clausola di Horn

disgiunzione di letterali in cui al massimo uno dei letterali è positivo

In logica, e in particolare nel calcolo proposizionale, una clausola di Horn è una disgiunzione di letterali in cui al massimo uno dei letterali è positivo. Prendono il nome da Alfred Horn che per primo ne evidenziò l'importanza (1951).[1]

Un esempio di clausola di Horn è il seguente:

Il numero dei letterali può essere arbitrario (anche zero); la condizione che al massimo uno sia positivo permette di scrivere la clausola sotto forma di implicazione.

Se il numero di letterali positivi è esattamente uno, la clausole di Horn vengono dette "definite", la cui premessa (corpo) è una congiunzione di letterali positivi e la sua conclusione (testa) è un singolo letterale positivo.

Partendo dall'esempio, applichiamo prima De Morgan:

Dopodiché utilizziamo l'equivalenza logica:

Ricaviamo quindi:

Casi particolari

modifica

Una clausola di Horn senza letterali negativi, può essere vista come una clausola di Horn definita che si limita ad asserire una determinata proposizione, e talvolta viene chiamata "fatto".

 

Una clausola di Horn senza letterali positivi può essere scritta come una implicazione la cui conclusione vale falso. Esempio:

 

De Morgan:

 
 
 

Nel campo dei database, formule di questo tipo sono chiamate vincoli di integrità.

Horn-soddisfacibilità

modifica

Nella teoria della complessità le clausole di Horn risultano essere particolarmente interessanti poiché il problema della soddisfacibilità di una formula booleana nel caso particolare in cui le clausole della formula siano tutte Clausole di Horn (detto problema della Horn-soddisfacibilità) ha complessità polinomiale.[2]

Programmazione logica

modifica

Le clausole di Horn sono alla base della programmazione logica, dove è comune scrivere clausole definite in forma di implicazione logica:

 

Tale implicazione viene solitamente scritta al contrario, per enfatizzarne la semantica:

 

La regola basata su tale clausola, infatti, ha il seguente significato:

per dimostrare  , dimostra   e dimostra   e ... e dimostra  .

In Prolog la regola è scritta nel modo seguente:

u :- p, q, ..., t.

Van Emden and Kowalski (1976) investigarono sulle proprietà delle clausole di Horn all'interno della teoria dei modelli e programmazione logica, dimostrando che ogni insieme di clausole definite   ha un unico modello minimale  . Una formula atomica   è logicamente implicata da   se e solo se  , ovvero se   è vera secondo  . Il concetto di modello minimale per le clausole di Horn è alla base della semantica del modello stabile.[3]

Voci correlate

modifica

Collegamenti esterni

modifica