1673068217

Problematyczny dowód to takie drzewo (wieeeelkie, niefajne, nudne, żmudne i paskudne)¹:

coś...

_inne reguł!/_    __ rutututu

tu możemy wstawić regułę na złożenie... {^} blablablabla...

{X = n} S := 1, while x * 1 do ... blablabla {S = n!}

Potrzebujemy jakiegoś lepszego mechanizmu (bo przekonanie kogoś, że program liczy silnię za pomocą takiego drzewka nie jest raczej spektakularnym sukcesem...).

Będziemy sobie robili coś takiego jak „dedukcja asercji” (rekonstrukcja):

1    *    i^x = n}

2    *    {X=« Al = l}

3    S := 1

4    *    {X =tiaS= 1}

5    *    {SX! = n!}

6    while X * 1 do

7    *    {S - X! = n! a X *    1}

s    *    {(X • S) • (X - 1)! = n!}

₉    S := X x S;

10    *    {S-(X-l)!=n!}

n    X := X - 1;

12    *    {SX! = n!}

13    done

H *    {5 X! = n! a -.X * 1}

i5    *    {S = n!}

A co będzie, jeśli ten program wywołamy tak, że w początkowym stanie pamięci będzie miał za X podstawione 0? Oczywiście program się zapętli (X nigdy nie przyjmie wartości 1 zakładamy, że mamy komórki pamięci o nieskończonej pojemności).

Definicja. Częściowa poprawność:

1= {tp}c{xp} WtW V7r3ł7 (7T, 77 1= ip A7T 6 Z?Om[c]|) =► [c]7T, 1J 1= Xp Prawdą jest, że przed wykonaniem programu c zachodzi formula tp a po jego wykonaniu ip wtedy i tylko wtedy, gdy

dla każdej pamięci ir istnieje wartościowanie g takie, że jeśli prawdziwa jest formula <p (przy wybranej pamięci n i wartościowaniu g) oraz program c się zatrzyma to formula ip jest prawdziwa w pamięci [cJtt i przy wartościowaniu g.

Definicja. Całkowita poprawność:

N [(/?]c[^>] wtw V7r3r/7r,7? =► (7r € Dom\c\ a [c]7t, t\ ^ ifi)

Prawdą jest, że przed wykonaniem programu c zachodzi formula p a po jego wykonaniu ip

20

1

rysowanie tego drzewa zajęło pierwszą godzinę wykładu