Raisonnement automatisé avec des nombres réels

Question

J'ai un grand nombre d'équivalences qui ressemblent à:

$ (A \ Leq 0.54 \ wedge b \ geq 0.12) \ VEE (c \ gt 0.98) $ $ \ Leftrightarrow $ $ (x \ leq 0,25) \ vee (x \ gt 0.91 \ wedge y \ geq 0.01) $

Ceci est juste un exemple. En général, des formules sur la partie gauche ou droite de l'équivalence pourraient être tout ce qui prend la forme d'une clause de formulaire normale disjonctive (DNF), les chiffres pourraient être des nombres réels avec une précision fixe et que les signes d'inégalité pourraient être $ \ leq $ , $ \ lt $ , $ \ geq $ , ou $ \ gt $ .

Ce qui est important, c'est que les variables possibles sur le côté gauche de toutes les formules (ici $ \ {a, b, c \} $ ) qui est distincte des variables possibles du côté droit de toutes les formules (ici $ \ {x, y, z \} $ ). Il pourrait y avoir un nombre fixe de variables de chaque côté: n'a pas besoin d'être 3 variables et n'a pas besoin d'être un nombre égal de chaque côté.

J'ai aussi des implications de la forme:

$ (A \ leq 0,32 \ wedge b \ geq 0.62) $ $ \ rightarrow $ < span class="math-conteneur"> $ (c \ gt 0.00) $

Ici, les côtés gauche et droit ne sont que des conjonctions d'inégalités, mais ce qui est important, c'est que l'ensemble de variables sur les deux les côtés gauche et droit, c'est-à-dire $ \ {a, b, c \} $ ici, est identique à l'ensemble de variables sur uniquement le côté gauche du type précédent de la formule (c'est-à-dire des équivalences).

Ma question est la suivante: quel type de raisonneur automatisé devrais-je trouver les conséquences logiques d'un ensemble de telles formules? Je suis juste à la recherche d'une identification concrète de la classe générale des problèmes qui appartient à et de tout raisonneurs hors de la boîte pouvant être disponibles. Peut-être que c'est un problème SMT?

Answer 1

Oui, vous pouvez résoudre celui-ci avec un solveur SMT qui prend en charge la véritable arithmétique linéaire. Cependant, SMT prend en charge des inégalités plus générales dans lesquelles vous pouvez avoir des sommes linéaires de variables (par exemple, 2A + 3x \ le 5.7 $ ) au lieu de comparaisons simples entre une seule variable et un constante (par exemple, $ A \ le 1,6 $ ), il peut donc être plus puissant que nécessaire, donc si vous n'avez pas d'inégalités linéaires impliquant des sommes impliquant des sommes, alors Je suis d'accord avec pseudonyme que la meilleure approche puisse être d'utiliser un solveur SAT.

Je suggérerais un codage légèrement différent de SAT. Au lieu d'un codage à un chaud, où $ x_i $ signifie que $ C_ {i-1} \ le x \ le C_I $ , je suggérerais un codage légèrement différent: $ x_i $ signifie $ x \ le c_i $ < / span>. Ainsi, au lieu d'encodage à un $ (x_1, \ dots, x_n) $ vecteur comme $ (0,0,0, 1,0) $ vous encoderiez à $ (1,1,1,1,0) $ . Vous ajoutez des contraintes que $ x_i \ implique x_ {i-1} $ , puis chaque inégalité $ x \ le c_i $ correspond à une variable booléenne $ x_i $ .

Answer 2

Dans votre cas, la solution la plus simple peut être d'utiliser SAT.

Votre première clause comprend $ x \ le 0.25 $ et $ x> 0.91 $ . Cela signifie qu'il y a cinq régions d'intérêt pour la variable $ x $ , que nous identifions avec des variables booléennes: $ x_1 \ Equiv x \ in (- \ \ \fty, 0,25) $ , $ x_2 \ équivalez x= 0,25 $ , $ X_3 \ Equiv x \ in (0,25, 0,91) $ , $ x_4 \ equiv x= 0,91 $ , $ X_5 \ Equiv x \ in (0.91, \ \fty) $ .

Créer une variable booléenne pour chacune de ces gammes et convertir la clause pour les utiliser. Donc, par exemple, $ x \ le 0.25 $ serait convertir en $ x_1 \ vee x_2 $ et $ x <0.91 $ serait convertir en $ x_1 \ vee x_2 \ vee x_3 $

.

.

Plus de clauses signifieraient plus de constantes, et donc plus de gammes d'intérêt pour une variable primitive.