HOARE LOGIC - CONTRUZIONE TOTALE DEI LOOP
-
04-11-2019 - |
Domanda
Considera un po 'di loop della forma:
$ texttt {while (c) {s}} $
con $ texttt {c} $ la condizione e $ texttt {s} $ il corpo del loop.
Lascia che $ texttt {i} $ e $ texttt {v} $ sia invariante e una variante di questo ciclo. La regola per la correttezza totale di White Loops è fornita nel mio libro di testo da:
If $ texttt {i} destrorrow texttt {v} geq 0 $
E $ [ texttt {i} land texttt {c} land texttt {v} = v_0] , texttt {s} , [ texttt {i} texttt {v} <v_0] $
Quindi $ [ texttt {i}] , texttt {while (c) {s}} , [ texttt {i} land neg texttt {c}] $
Da quello che penso ho capito, affinché il ciclo termini, la variante $ texttt {v} $ deve diminuire in modo stretto e che deve anche essere delimitata da zero. Tuttavia, quando lo traduzione matematicamente, ottengo una proposta diversa da quella del mio libro di testo:
$$ [ texttt {v} geq 0 land texttt {v} = v_0] , texttt {s} , [ texttt {v} geq 0 land texttt {v} <v_0] $ $
La mia domanda : Quest'ultima proposta e la regola del mio libro di testo dicono la stessa cosa su ciò che deve essere dimostrato per far terminare il ciclo? In altre parole: è
$ [ texttt {i} land texttt {c} land texttt {v} geq 0 land texttt {v} = v_0] , texttt {s} , [ texttt {i} Land texttt {v} geq 0 land texttt {v} <v_0] $
lo stesso di
$ texttt {i} destrorrow texttt {v} geq 0 $ insieme a $ [ texttt {i} land texttt {c} land texttt {v} = v_0] , texttt {s} , [ texttt {i} land texttt {v} <v_0] $
Perché o perché no?
Nessuna soluzione corretta