En logique classique, si A est une formule alors il existe une formule conjonctive B telle que :
1. A et B sont équisatisfiables
2. La taille de B est linéaire en fonction de la taille de A.
Dans un devoir que je dois rendre très rapidement, je dois montrer que la taille (en nombre de connecteurs) de la formule conjonctive B est linéaire par rapport à la taille de la formule de départ A, c'est à dire dans un rapport 1/k (k fois inférieure) de la taille de A, avec k une constante à déterminer.
Je ne vois pas du tout comment m'y prendre pour démontrer cela. Pourriez-vous m'apporter votre aide s'il vous plaît?
Merci d'avance.
-----