Ragionamento automatico con numeri reali

Question

Ho un gran numero di equivalenze che sembrano:

$ (a \ leq 0.54 \ wedge b \ geq 0.12) \ vee (c \ gt 0.98) $ $ \ Leftrigerow $ $ (x \ leq 0.25) \ vee (x \ gt 0.91 \ wedge y \ geq 0,01) $

Questo è solo un esempio. In generale, le formule sul lato sinistro o destro dell'equivalenza potrebbero essere tutto ciò che prende la forma di una clausola normale della forma normale disgiuntiva (DNF), i numeri potrebbero essere numeri reali con una precisione fissa e i segni di disuguaglianza potrebbero essere < class="container di matematica"> $ \ leq $ , $ \ lt $ , $ \ geq $ o $ \ gt $ .

Ciò che è importante è che le possibili variabili sul lato sinistro di tutte le formule (qui $ \ {A, B, c \} $ ) Formare un set Questo è distinto dalle possibili variabili sul lato destro di tutte le formule (qui $ {x, y, z \} $ ). Potrebbe esserci qualsiasi numero fisso di variabili su entrambi i lati: non è necessario essere 3 variabili e non deve essere un numero uguale su entrambi i lati.

Ho anche alcune implicazioni del modulo:

$ (a \ leq 0.32 \ wedge b \ geq 0.62) $ $ \ reapyarrow $ < Span Class="Math-Container"> $ (c \ gt 0.00) $

Qui i lati sinistro e destro sono solo congiunzioni di disuguaglianze, ma ciò che è importante è che il set di variabili su sia lati sinistro e destro, ovvero $ \ {A, B, C \} $ qui, è la stessa del set di variabili su solo il lato sinistro del tipo precedente della formula (cioè le equivalenze).

La mia domanda è: che tipo di ragionamento automatico dovrei trovare le conseguenze logiche di un insieme di tali formule? Sto solo cercando un'identificazione concreta della classe generale dei problemi a cui appartiene, e tutti i responsabili fuori combattimento che possono essere disponibili. Forse questo è un problema SMT?

Answer 1

Sì, potresti risolverlo con un risolutore SMT che supporta il vero aritmetico lineare. Tuttavia SMT supporta le disuguaglianze più generali in cui è possibile avere somme lineari di variabili (ad esempio, $ 2A + 3x \ Le 5.7 $ ) anziché semplici confronti tra una singola variabile e a costante (ad esempio, $ a \ le 1.6 $ ), quindi potrebbe essere più potente di quanto necessiti, quindi se non si dispone di disuguaglianze lineari che coinvolgono somme, allora Sono d'accordo con lo pseudonimo che l'approccio migliore possa essere quello di utilizzare un risolutore satellitare.

Suggerirei una codifica leggermente diversa da sedere. Invece di una codifica a caldo, dove $ x_i $ significa che $ c_ {i-1} \ le x \ le c_i $ , suggerirei una codifica leggermente diversa: $ x_i $ significa $ x \ le c_i $ < / span>. Quindi invece di codificare a $ (x_1, \ dots, x_n) $ vector come $ (0,0,0, 1,0) $ Si codifichi a $ (1,1,1,1,0) $ . Si aggiungi vincoli che $ x_i \ implica x_ {i-1} , e quindi ciascuna disuguaglianza $ x \ le c_i $ corrisponde a una variabile booleana $ x_i $ .

Answer 2

Nel tuo caso, la soluzione più semplice potrebbe essere quella di utilizzare SAT.

La prima clausola include $ x \ le 0.25 $ e $ x> 0,91 $ . Ciò significa che ci sono cinque regioni di interesse per la variabile $ x $ , che ci identifichiamo con variabili booleane: $ 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) $ .

Creare una variabile booleana per ciascuna di queste gamme e convertire la clausola per utilizzarle. Quindi, ad esempio, $ x \ le 0.25 $ convertire in $ x_1 \ vee x_2 $ , e $ x <0,91 $ Convertire in $ x_1 \ vee x_2 \ vee x_3 $ .

Più clausole significherebbe più costanti e quindi più gamme di interesse per una variabile primitiva.