Razonamiento automatizado con números reales.

Question

Tengo una gran cantidad de equivalencias que parecen:

$ (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) $

Este es solo un ejemplo. En general, las fórmulas en el lado izquierdo o derecho de la equivalencia podrían ser cualquier cosa que tome la forma de una cláusula de forma de forma disyuntiva (DNF), los números podrían ser números reales con una precisión fija, y los signos de desigualdad podrían ser $ \ leq $ , $ \ lt $ , $ \ geq $ , o $ \ gt $ .

Lo que es importante es que las posibles variables en el lado izquierdo de todas las fórmulas (aquí $ \ {a, b, c \} $ ) forman un conjunto Eso es distinto de las posibles variables en el lado derecho de todas las fórmulas (aquí $ \ {x, y, z \} $ ). Podría haber cualquier número fijo de variables a cada lado: no necesita ser 3 variables, y no necesita ser un número igual en cada lado.

También tengo algunas implicaciones de la forma:

$ (A \ leq 0.32 \ wedge b \ geq 0.62) $ $ \ judowarrow $ < Span Class="Math-contenedor"> $ (C \ GT 0.00) $

Aquí, ambos lados izquierdo y derecho son solo conjunciones de desigualdades, pero lo que es importante es que el conjunto de variables en ambos laterales izquierdo y derecho, es decir, $ \ {A, B, C \} $ aquí, es el mismo que el conjunto de variables en solo el lado izquierdo del tipo anterior de la fórmula (es decir, las equivalencias).

Mi pregunta es: ¿Qué tipo de razonador automatizado necesitaría encontrar las consecuencias lógicas de un conjunto de tales fórmulas? Solo estoy buscando una identificación concreta de la clase general de problemas que pertenece a esto, y cualquier razonador fuera de la caja que pueda estar disponible. Tal vez este es un problema de SMT?

Answer 1

Sí, podría resolver esto con un solucionador SMT que admite aritmética real lineal. Sin embargo, SMT admite desigualdades más generales donde puede tener sumas lineales de variables (por ejemplo, $ 2A + 3x \ le 5.7 $ ) en lugar de comparaciones simples entre una sola variable y una constante (por ejemplo, $ a \ le 1.6 $ ), por lo que podría ser más poderoso de lo que necesita, por lo que si no tiene desigualdades lineales que involucren sumas, entonces Estoy de acuerdo con el seudónimo que el mejor enfoque puede ser usar un solucionador SAT.

Me sugeriría una codificación ligeramente diferente para sentarse. En lugar de una codificación de una sola corriente, donde $ x_i $ significa que $ c_ {i-1} \ le x \ le C_I $ , sugeriría una codificación ligeramente diferente: $ x_i $ significa $ x \ le c_i $ < / span>. Por lo tanto, en lugar de codificar a un $ (x_1, \ puntos, x_n) $ vector como $ (0,0,0, 1,0) $ Codearía $ (1,1,1,1,0) $ . Agrega restricciones que $ x_i \ implica x_ {i-1} $ , y luego cada desigualdad $ x \ le c_i $ corresponde a una variable booleana $ x_i $ .

Answer 2

En su caso, la solución más simple puede ser usar SAT.

Su primera cláusula incluye $ x \ le 0.25 $ y $ x> 0.91 $ . Esto significa que hay cinco regiones de interés para la variable $ x $ , que identificamos con variables booleanas: $ x_1 \ EQUIV X \ IN (- \ INFTY, 0.25) $ , $ x_2 \ Equiv 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, \ INFTY) $ .

Crear una variable booleana para cada uno de estos rangos, y convertir la cláusula para usarlos. Entonces, por ejemplo, $ x \ le 0.25 $ se convertiría a $ x_1 \ vee x_2 $ , y $ x <0.91 $ se convertiría a $ x_1 \ vee x_2 \ vee x_3 $ .

Más cláusulas significarían más constantes y, por lo tanto, más rangos de interés para una variable primitiva.