Règles d'inférence pour dériver des invariants dans la logique Hoare

Question

L'algorithme suivant est censé comparer deux chaînes $ s_1 $ et $ s_2 $ ("/ " pour la chaîne vide):

X = S1   
Y = S2

E = true   
// (1) S1 = S2 <=> X = Y and E = true
while X != /\ and Y != /\ and E == true          
  if head(X) == head(Y)           
    X = tail(X)
    Y = tail(Y)
  else
    E = false
// (2) S1 = S2 <=> X = /\ and Y = /\ and E = true
if !(X == /\ and Y == /\)    
  E = false 
  // (3) S1 != S2 and E = false
else // an empty else; just for inserting an assertion (i.e., 3' below) here
  // (3') S1 = S2 <=> E = true
// (4) S1 = S2 <=> E = true
return E

Il y a cinq invariants:

(1). $ S_1 = s_2 iff x = y land e = true $

(2). $ S_1 = s_2 iff x = lambda land y = lambda land e = true $

(3). $ S_1 neq s_2 land e = false $

(3 '). $ S_1 = s_2 iff e = true $

(4). $ S_1 = s_2 iff e = true $

Je peux comprendre ces invariants et comment ils sont dérivés des précédents de manière intuitive et donc informelle. Par exemple, nous pouvons dériver (3 ') de (2) comme suit:

Au point (2), nous savons que $ s_1 $ est égal à $ s_2 $ iff $ x = lambda land y = lambda land e = true $. Au point (3 '), nous savons en outre que $ x = lambda land y = lambda $. Ainsi, à ce stade, nous devons seulement vérifier si $ e = true $ pour décider si $ s_1 = s_2 $ détient.

Cependant, le raisonnement ci-dessus ne peut pas être justifié par les règles d'inférence conventionnelles de la logique propositionnelle par laquelle nous aurions

$$ S_1 = s_2 iff (x = lambda land y = lambda land e = true) Land (x = lambda land y = lambda), $$ qui est $ s_1 = s_2 iff x = Lambda land y = lambda land e = true. $

---

Problème: Quelles sont les règles d'inférence pour la dérivation de (2) à (3 ')?

Article similaire: Développer des invariants pour comparer deux chaînes

---

Éditer:Comme indiqué par @chi dans le commentaire, il devrait être $$ big (s_1 = s_2 iff (x = lambda land y = lambda land e = true) big) land (x = lambda land y = lambda), $$ qui implique (3 ') $ s_1 = s_2 iff e = true $ comme la réponse donnée par @kne le montre.