Complexité de l'annulation de la négation

Question

Considérez la logique propositionnelle sur les connecteurs $ land $, $ lor $, et $ lnot $. Notation: $ | alpha | $ est la longueur de la formule $ alpha $.

On nous donne une formule $ phi $. Annuler toutes les négations abandonnées dans $ phi $ en appliquant tous les biconditionnels valides possibles (éditer: comme les exemples ci-dessous) pour obtenir $ phi '$; Pour plus de clarté, nous notons que $ phi leftrightarrow phi '$. On nous donne également que $ phi '$ est monotone. Y a-t-il des exemples où $ | phi '| $ doit croître de façon exponentielle, ou est $ | phi '| $ délimité par un polynôme? S'il y a un exemple de croissance exponentielle, veuillez le montrer.

EDIT: Les bicondtionsals suivants sont des exemples de ce que j'essaie d'obtenir, des formules qui peuvent être utilisées pour annuler les négations tout en préservant l'équivalence. La procédure serait vraisemblablement d'unifier le côté gauche de la formule avec $ phi $ via l'unification et remplacez le côté droit, selon le cas, par unification.

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