Concatenazione in avanti

La concatenazione in avanti è un metodo di inferenza logica per verificare la coerenza di un'affermazione ( ipotesi ) nei confronti di una base di conoscenza ( KB ) composta esclusivamente da clausole definite ( letterali positivi ). Nella logica proposizionale un fatto è rappresentato da un letterale positivo. La congiunzione di più fatti compone l'ipotesi da verificare. Alcuni fatti dell'ipotesi sono considerate premesse vere, altri fatti sono invece considerati delle premesse da verificare. A partire dalle premesse note l'algoritmo applica la tecnica del Modus Ponens per derivare nuovi fatti ( letterali ) da aggiungere all'area di memoria del ragionamento logico. Il processo di elaborazione si conclude quando l'affermazione iniziale viene provata ( affermazione corretta ) oppure quando non è possibile inferire altri nuovi fatti all'area di ragionamento ( affermazione non provata ).

Ad esempio, la seguente affermazione ( A ∧ B ∧ G ) è composta dalla tre letterali positivi ( fatti ). I fatti A e B sono assunti come premesse vere (P_v), in quanto sono già verificati dai percettori dell'agente razionale, mentre il fatto G è ancora da verificare (P_dv).

P_v = { A, B }

P_dv = { G }

Essendoci dei fatti ancora da verificare (G) nelle premesse, l'agente razionale non può sapere con certezza se l'affermazione ( A ∧ B ∧ G ) è corretta oppure meno. Per verificare la veridicità dell'affermazione ( A ∧ B ∧ G ) il sistema esperto deve valutare la sua coerenza logica nei confronti della base di conoscenza (KB) di riferimento. La base di conoscenza è composta da un insieme di regole di inferenza. A partire dalle premesse vere ( A ∧ B ) l'algoritmo elabora "in avanti" le conseguenze logiche per dimostrare la veridicità delle premesse ancor da verificare ( G ).

• Primo ciclo di elaborazione. Nel primo ciclo di elaborazione l'algoritmo conosce soltanto le premesse ( A ∧ B ). A partire da queste premesse vere, l'algoritmo ricerca quali regole di inferenza della base di conoscenza consentono di aggiungere altri fatti al ragionamento logico. In questo caso, la regola ( A ∧ B ⇒ C ) permette di aggiungere all'area del ragionamento logico un nuovo fatto (C) tra le premesse vere. Per evitare di riconsiderare nuovamente la regola di inferenza ( A ∧ B ⇒ C ), questa viene temporaneamente disabilitata poiché tutti i fatti ( letterali ) sono ormai noti all'agente razionale. Il nuovo fatto (C) viene aggiunto alle premesse vere.
• Secondo ciclo di elaborazione. Nel secondo ciclo di elaborazione l'area di lavoro è ora composta dalle seguenti premesse vere ( A ∧ B ∧ C ). L'algoritmo confronta le premesse con la base di conoscenza e individua la regola di inferenza ( C ∧ B ⇒ E ) che consente di aggiungere un nuovo fatto (E) al ragionamento. La regola di inferenza viene temporaneamente disabilitata per evitare di riutilizzarla nel seguito del ragionamento.
• Terzo ciclo di elaborazione. Nel terzo ciclo di elaborazione l'algoritmo di concatenazione analizza nuovamente l'area di lavoro ( A ∧ B ∧ C ∧ E ). La regola di inferenza logica ( A ∧ E ⇒ F ) consente di aggiungere un nuovo fatto ( E ) all'area di lavoro. È importante sottolineare un aspetto importante. Durante questo ciclo l'algoritmo non prende in considerazione la regola ( A ∧ E ⇒ C ) poiché sarebbe inutile farlo. L'agente razionale è già a conoscenza che il fatto (C) è vero. Sarebbe, quindi, del tutto inutile elaborare questa regola di inferenza per calcolare una conseguenza logica di cui si conosce già il risultato. Al termine di questo ciclo di elaborazione l'algoritmo disabilita temporaneamente entrambe le regole di inferenza per evitare di riutilizzarle.
• Quarto ciclo di elaborazione. Nel quarto ciclo di elaborazione l'algoritmo elabora le premesse ( A ∧ B ∧ C ∧ E ∧ F ) e individua nella base di conoscenza la regola di inferenza ( F ∧ E ⇒ G ) che permette di aggiungere il fatto (G) tra le premesse vere e, quindi, di chiudere il ragionamento logico. Non essendoci più premesse da verificare l'affermazione ( A ∧ B ∧ G ) è giudicata vera poiché è coerente con la base di conoscenza (KB).

L'algoritmo di concatenazione conclude l'elaborazione in due casi, dopo aver dimostrato la coerenza logica dell'affermazione iniziale ( ipotesi ), ossia quando l'insieme delle premesse da verificare è vuoto, oppure nel momento in cui il processo di inferenza logica non consente di aggiungere altri fatti all'area di lavoro ( premesse vere ). Nel primo caso l'algoritmo dimostra la veridicità dell'affermazione.

Efficienza. Quando l'algoritmo di concatenazione raggiunge l'obiettivo può cessare l'esecuzione. Sarebbe, infatti, del tutto inutile continuare a elaborare altre conseguenze logiche. Ad esempio, una volta confermata la veridicità del fatto (G) è del tutto inutile continuare il processo ed elaborare la regola di inferenza (G ∧ A ⇒ D) per aggiungere il fatto (D) al ragionamento. Il fatto (D) è un dettaglio che non aggiunge alcuna informazione utile al ragionamento stesso. Può, quindi, essere omesso.

Complessità lineare. L'algoritmo della concatenazione ha una complessità spaziale e temporale lineare. L'algoritmo memorizza soltanto i letterali ( fatti ) veri e quelli ancora da analizzare. I letterali ( fatti ) già noti come veri non sono rielaborati. Ad esempio, nel terzo ciclo del nostro esempio la regola ( A E => C ) non viene elaborata poiché l'algoritmo è già a conoscenza che il fatto C è vero. È quindi inutile elaborare le premesse ( A E ) per ottenere nuovamente il fatto C.

---

• Ragionamento basato sui dati. L'algoritmo di concatenazione in avanti è una forma di ragionamento logico basata sui dati poiché l'algoritmo elabora tutte le conseguenze logiche a partire dai dati conosciuti. Man mano che l'algoritmo li elabora, aggiunge nuove informazioni e fatti ( conoscenza ).
• Completezza. L'algoritmo di concatenazione in avanti è completo poiché, a partire da un insieme di fatti iniziali, tutte le formule e le conseguenze logiche sono elaborate.
• Clausole di Horn / clausole definite. La concatenazione in avanti è applicabile soltanto se le base di conoscenza è composta da clausole di Horn o da clausole definite.
• Concatenazione all'indietro. La concatenazione all'indietro è il processo inferenziale inverso che permette di ricostruire le premesse logiche di un fatto ( letterale ).
• Concatenazione in avanti del primo ordine. La concatenazione in avanti può essere utilizzata anche nella logica del primo ordine oltre che nella logica proposizionale. Il principio di funzionamento è il medesimo. Nella logica del primo ordine la forward chaining è applicata alle formule atomiche della base di conoscenza, le quali sono caratterizzate da variabili.