Complessità della cancellazione della negazione

Question

Considera la logica proposizionale sui connettivi $ land $, $ lor $, e $ lnot $. Notazione: $ | alpha | $ è la lunghezza della formula $ alpha $.

Ci viene data una formula $ phi $. Annulla tutte le negazioni cancellabili in $ phi $ Applicando tutti i bicondizionali validi possibili (modifica: come gli esempi seguenti) da ottenere $ phi '$; per chiarezza lo notiamo $ phi leftrighrow phi '$. Ci viene anche dato $ phi '$ è monotonico. Ci sono esempi in cui $ | phi '| $ deve crescere in modo esponenziale o è $ | phi '| $ delimitato da un polinomio? Se c'è un esempio di crescita esponenziale, ti preghiamo di mostrarlo.

EDIT: i seguenti biconudizionari sono esempi di ciò che sto cercando di ottenere, formule che possono essere utilizzate per annullare le negazioni preservando l'equivalenza. La procedura sarebbe presumibilmente per unificare il lato sinistro della formula con $ phi $ tramite unificazione e sostituire il lato destro come appropriato per unificazione.

$$ alpha land ( lnot alpha lor beta) leftrighrow alpha land beta $$ $$ lnot lnot alpha leftrighrow alpha $$