Clausola di Horn

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:

\neg A\vee \neg B\vee C

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:

\neg (A\wedge B)\vee C

Dopodiché utilizziamo l'equivalenza logica:

\neg X\vee Y\equiv X\Rightarrow Y

Ricaviamo quindi:

(A\wedge B)\Rightarrow C

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".

A

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

\neg A\vee \neg B\vee \neg C

De Morgan:

\neg (A\wedge B\wedge C)

\neg (A\wedge B\wedge C)\vee Falso

(A\wedge B\wedge C)\Rightarrow Falso

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:

(p\land q\land ...\land t)\to u

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

u\gets (p\land q\land ...\land t)

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

per dimostrare $u$ , dimostra $p$ e dimostra $q$ e ... e dimostra $t$ .

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 $D$ ha un unico modello minimale $M_{D}$ . Una formula atomica $A$ è logicamente implicata da $D$ se e solo se $M\vDash A$ , ovvero se $A$ è vera secondo $M$ . Il concetto di modello minimale per le clausole di Horn è alla base della semantica del modello stabile.^[3]