Y a-t-il une expression booléenne d'algèbre qui ne peut pas être mise en 3SAT?

Question

Cela me semble assez évident, il n'y en a pas, mais je pourrais laisser un cas spécial. Comme je le vois, 1SAT (un seul littéral par clause) et 2SAT peuvent être facilement transformés en 3SAT. Une clause de plus de 3 littéras a été prouvée qu'elle peut être transformée en 3SAT. Alors peut-être que la question devrait être posée comme suit: toute algèbre booléenne peut-elle être mise en SAT? Ou pouvons-nous définir l'algèbre booléenne avec ces opérateurs? Et ou non

Answer 1

Non, il n'y en a pas.

Je ne donnerai pas la pleine preuve mais voici l'idée principale: écrire la formule donnée sous une forme normale, c'est-à-dire la conjonction de disjonctions. Utilisez l'induction sur le nombre de variables sur une expression. Choisissez la sous-expression la plus longue avec des variables N + 1, introduisez une nouvelle variable pour une partie de la sous-expression pour laisser une expression de n variables, ajoutez les contraintes de la nouvelle variable à la formule, répétez la procédure autant de fois que nécessaire pour avoir une formule où la sous-expression la plus longue a n variables.