Ricerc@Sapienza

I circuiti e le formule proposizionali ammettono forme equivalenti di varia grandezza. Per molte applicazioni, una minore dimensione é preferibile. La questione della sintesi di circuiti minimi o più in generale di formule proposizionali minime esiste da numerosi anni. Analogamente, la questione della riduzione di formule mediante eliminazione di variabili esiste in diversi ambiti quali il calcolo proposizionale, la logica del primo ordine, la soddisfazione di vincoli e le ontologie. Il problema che viene studiato in questo progetto é quello della formulazione minima mediante eliminazione o introduzione di nuove variabili. In particolare, viene considerato il problema di esistenza di una formula che abbia grandezza minore di un certo valore dato e che sia equivalente alla formula di partenza a meno di un insieme di variabili da cancellare. Lo stesso problema viene poi considerato mediante aggiunta di variabili piuttosto che eliminazione.