Salta al contenuto principale

02 - Logica per la specifica: proposizionale e primo ordine

Logica proposizionale e del primo ordine, triple di Hoare, invarianti e weakest precondition, con programmi che verificano ogni definizione.

Cosa ne pensi di questo articolo?

02 - Logica per la specifica: proposizionale e primo ordine
Metodi Formalifedericocalo.dev

In Breve

Logica proposizionale e del primo ordine, triple di Hoare, invarianti e weakest precondition, con programmi che verificano ogni definizione.

Quando scrivi un commento come «questa funzione vuole un array ordinato» o «esce un indice fra 0 e len-1», stai già facendo una specifica, ma in una frase che nessuno strumento può controllare. La logica formale è la notazione che rende quelle frasi esatte: una precondizione P dice che cosa assumi prima, una postcondizione Q dice che cosa garantisci dopo, e la tripla di Hoare {P} C {Q} li lega al codice C: se parti da uno stato in cui P è vera ed esegui C fino in fondo, ottieni uno stato in cui Q è vera. Per dimostrarla senza provare tutti gli input servono tre attrezzi, che questo articolo costruisce con programmi eseguibili: gli invarianti per i cicli, la weakest precondition per calcolare all'indietro che cosa serve, la funzione di rango per la terminazione.

Connettivi e quantificatori

La logica proposizionale lavora con affermazioni che sono vere o false, per esempio x > 5, e le combina con cinque connettivi. La logica del primo ordine aggiunge i quantificatori per parlare di collezioni di oggetti senza elencarli.

  • P ∧ Q (e): vera se lo sono entrambe. È l'&& di un if.
  • P ∨ Q (o): vera se lo è almeno una.
  • ¬P (non): vera se P è falsa.
  • P → Q (se... allora): falsa solo quando P è vera e Q è falsa.
  • P ↔ Q (se e solo se): vera quando hanno lo stesso valore.
  • ∀x ∈ L: P(x) (per ogni): P vale per tutti gli elementi di L; ∃x ∈ L: P(x) (esiste): P vale per almeno uno.

Il connettivo che sorprende è l'implicazione, perché con P falsa risulta vera in ogni caso. Pensa alla regola «se piove, prendo l'ombrello»: la violi solo nei giorni in cui piove e non lo prendi, mentre nei giorni di sole la regola resta rispettata qualunque cosa tu faccia. Le precondizioni delle funzioni funzionano così: se P è falsa, la tripla non dice nulla. Il programma seguente stampa la tavola di verità dell'implicazione e controlla quattro leggi su tutte le assegnazioni, poi verifica la negazione dei quantificatori su tutti i 16 predicati possibili su un dominio di 4 elementi.

from itertools import product

def implica(p, q):
    return (not p) or q

print("P      Q      P->Q")
for p, q in product([True, False], repeat=2):
    print(f"{p!s:<6} {q!s:<6} {implica(p, q)}")

# Equivalenze verificate su tutte le assegnazioni di verita'
controlli = {
    "P->Q == (not P) or Q": lambda p, q: implica(p, q) == ((not p) or q),
    "P->Q == (not Q)->(not P)": lambda p, q: implica(p, q) == implica(not q, not p),
    "not(P and Q) == (not P) or (not Q)": lambda p, q: (not (p and q)) == ((not p) or (not q)),
    "P->Q == Q->P": lambda p, q: implica(p, q) == implica(q, p),
}
print()
for nome, f in controlli.items():
    esito = all(f(p, q) for p, q in product([True, False], repeat=2))
    print(f"{nome}: {esito}")

# Negazione dei quantificatori: dominio di 4 elementi, ogni predicato possibile
# (un predicato e' una scelta vero/falso per ciascun elemento: 2**4 = 16).
dominio = [0, 1, 2, 3]
n_ok = 0
n_tot = 0
for valori in product([True, False], repeat=len(dominio)):
    P = dict(zip(dominio, valori))
    n_tot += 1
    a = not all(P[x] for x in dominio)       # not forall x. P(x)
    b = any(not P[x] for x in dominio)       # exists x. not P(x)
    c = not any(P[x] for x in dominio)       # not exists x. P(x)
    d = all(not P[x] for x in dominio)       # forall x. not P(x)
    n_ok += (a == b) and (c == d)
print(f"\nPredicati controllati: {n_tot}; negazione dei quantificatori valida in {n_ok}")

# La confusione tipica: 'non tutti' NON e' 'nessuno'
P = dict(zip(dominio, (True, True, False, True)))
print("non tutti:", not all(P.values()), "| nessuno:", not any(P.values()))

# Output:
# P      Q      P->Q
# True   True   True
# True   False  False
# False  True   True
# False  False  True
#
# P->Q == (not P) or Q: True
# P->Q == (not Q)->(not P): True
# not(P and Q) == (not P) or (not Q): True
# P->Q == Q->P: False
#
# Predicati controllati: 16; negazione dei quantificatori valida in 16
# non tutti: True | nessuno: False

Le prime tre leggi risultano True: l'implicazione equivale a ¬P ∨ Q e alla sua contronominale ¬Q → ¬P, e la prima legge di De Morgan vale. La quarta, P → Q == Q → P, risulta False: scambiare ipotesi e tesi cambia il significato, ed è l'errore di ragionamento più comune. Sulla negazione dei quantificatori il conto è 16 su 16: «non tutti» equivale a «ne esiste uno che no», e «nessuno» è un'altra cosa. L'ultima riga lo mostra su un esempio: se un solo elemento su quattro non soddisfa la proprietà, «non tutti soddisfano» è vero e «nessuno soddisfa» è falso. Questa equivalenza è lo strumento del debug: per confutare «tutti gli elementi sono positivi» ti basta trovare un elemento che non lo è.

La tripla di Hoare, controllata su un dominio finito

Nel suo articolo del 1969 Hoare scrive la tripla nella forma P {Q} R, con il programma Q fra parentesi graffe, e la legge così: se l'asserzione P è vera prima dell'esecuzione del programma Q, allora R sarà vera al suo termine. Qui uso la scrittura {P} C {Q}, che è soltanto un'altra convenzione grafica. Nota il «al suo termine»: è la correttezza parziale, che non dice nulla se il programma non termina. La correttezza totale aggiunge la terminazione ed è l'argomento della sezione sulla funzione di rango.

Il caso classico è la ricerca binaria: P è «la lista è ordinata in modo non decrescente», Q è «il risultato è -1 e l'obiettivo non è nella lista, oppure è l'indice di un elemento uguale all'obiettivo». Il programma che segue codifica P e Q come funzioni Python e prova la ricerca su tutte le liste ordinate di lunghezza da 0 a 5 con valori da 0 a 3, per ciascun obiettivo da -1 a 4. Insieme alla versione corretta ci sono due versioni con un solo carattere sbagliato, per vedere come si manifesta un errore nella tripla.

from itertools import combinations_with_replacement


def pre(A):
    """P: la lista e' ordinata in modo non decrescente."""
    return all(A[i] <= A[i + 1] for i in range(len(A) - 1))


def post(A, target, r):
    """Q: r e' -1 e target non e' in A, oppure A[r] == target."""
    if r == -1:
        return target not in A
    return 0 <= r < len(A) and A[r] == target


def ricerca(A, target):
    left, right = 0, len(A) - 1
    rango = right - left + 1            # funzione di rango: elementi ancora in gioco
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == target:
            return mid
        if A[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
        nuovo = right - left + 1
        assert 0 <= nuovo < rango, f"il rango non scende: {rango} -> {nuovo}"
        rango = nuovo
    return -1


def ricerca_bug_a(A, target):           # 'left = mid' invece di 'mid + 1'
    left, right = 0, len(A) - 1
    rango = right - left + 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == target:
            return mid
        if A[mid] < target:
            left = mid
        else:
            right = mid - 1
        nuovo = right - left + 1
        assert 0 <= nuovo < rango, f"il rango non scende: {rango} -> {nuovo}"
        rango = nuovo
    return -1


def ricerca_bug_b(A, target):           # 'left < right' invece di '<='
    left, right = 0, len(A) - 1
    while left < right:
        mid = (left + right) // 2
        if A[mid] == target:
            return mid
        if A[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


def controlla(f):
    """Prova f su tutte le liste ordinate di lunghezza 0..5 con valori 0..3."""
    n_casi, primo_errore = 0, None
    for n in range(6):
        for A in combinations_with_replacement(range(4), n):
            A = list(A)
            assert pre(A)
            for target in range(-1, 5):
                n_casi += 1
                try:
                    r = f(A, target)
                    ok = post(A, target, r)
                    motivo = f"risultato {r}"
                except AssertionError as e:
                    ok, motivo = False, str(e)
                if not ok and primo_errore is None:
                    primo_errore = (A, target, motivo)
    return n_casi, primo_errore


for nome, f in (("corretta", ricerca), ("bug_a", ricerca_bug_a), ("bug_b", ricerca_bug_b)):
    n, errore = controlla(f)
    print(f"{nome}: {n} casi, primo controesempio: {errore}")

print("\nRango sul caso A=[1,3,5,7,9], target=7:")
A, left, right = [1, 3, 5, 7, 9], 0, 4
while left <= right:
    mid = (left + right) // 2
    print(f"  rango={right - left + 1}  [{left},{right}]  A[{mid}]={A[mid]}")
    if A[mid] == 7:
        break
    left, right = (mid + 1, right) if A[mid] < 7 else (left, mid - 1)

# Output:
# corretta: 756 casi, primo controesempio: None
# bug_a: 756 casi, primo controesempio: ([0], 1, 'il rango non scende: 1 -> 1')
# bug_b: 756 casi, primo controesempio: ([0], 0, 'risultato -1')
#
# Rango sul caso A=[1,3,5,7,9], target=7:
#   rango=5  [0,4]  A[2]=5
#   rango=2  [3,4]  A[3]=7

I casi sono 756: le liste ordinate di lunghezza n con 4 valori sono C(n+3, 3), cioè 1, 4, 10, 20, 35, 56 per n da 0 a 5, e la somma 126 moltiplicata per i 6 obiettivi dà 756. La versione corretta passa tutti i casi. Con left = mid al posto di left = mid + 1 il ciclo non può terminare: sulla lista [0] con obiettivo 1 l'intervallo resta invariato, e l'asserzione sul rango lo segnala. Con left < right al posto di left <= right il ciclo termina ma sbaglia la postcondizione: su [0] con obiettivo 0 restituisce -1. Sono due fallimenti di natura diversa, e la tripla li distingue: il secondo viola Q, il primo viola la terminazione.

Un controllo su 756 casi non è una dimostrazione: copre liste lunghe al più 5 e valori fra 0 e 3. Dà però un'informazione utile in fretta, perché gli errori di questo tipo si manifestano quasi sempre su input piccoli, come qui la lista di un elemento. La dimostrazione completa si fa con gli attrezzi delle sezioni seguenti, che valgono per qualunque lista.

Invarianti di ciclo: come si trovano

Un invariante di ciclo è una proprietà che vale all'ingresso del ciclo (inizializzazione), resta vera dopo ogni giro se era vera prima (mantenimento) e, all'uscita, insieme alla condizione di fine ciclo implica la postcondizione (conclusione). Il mantenimento è un passo induttivo: è questo che riduce a una verifica finita la verifica di un numero qualsiasi di giri. Non è un «valore che non cambia»: è una proprietà che resta vera mentre le variabili cambiano.

Come trovarlo: parti dalla postcondizione e sostituisci la costante di fine ciclo con la variabile del ciclo. Per il massimo di una lista la postcondizione è m == max(A); il ciclo scorre l'indice i da 1 a len(A), quindi l'invariante è m == max(A[:i]): il massimo della parte già vista. All'ingresso i = 1 e m = A[0], che è il massimo di A[:1]; all'uscita i = len(A) e l'invariante coincide con la postcondizione. Il programma controlla l'invariante con un assert a ogni giro, e include un invariante sbagliato (m == A[0], troppo forte) per mostrare che cosa succede.

def massimo(A):
    """P: A non vuota. Invariante: m == max(A[:i])."""
    m = A[0]
    i = 1
    assert m == max(A[:i])              # inizializzazione
    while i < len(A):
        if A[i] > m:
            m = A[i]
        i += 1
        assert m == max(A[:i])          # mantenimento
    return m                            # a fine ciclo i == len(A): m == max(A)


def massimo_sbagliato(A):
    """Invariante troppo forte: m == A[0] resta vero solo finche' non si aggiorna."""
    m = A[0]
    for i in range(1, len(A)):
        if A[i] > m:
            m = A[i]
        assert m == A[0], f"invariante rotto a i={i}"
    return m


print("massimo([3, 9, 2, 9, 4]) =", massimo([3, 9, 2, 9, 4]))
try:
    massimo_sbagliato([3, 9, 2])
except AssertionError as e:
    print("massimo_sbagliato([3, 9, 2]):", e)

# Output:
# massimo([3, 9, 2, 9, 4]) = 9
# massimo_sbagliato([3, 9, 2]): invariante rotto a i=1

La prima riga stampa 9, il massimo vero, e le asserzioni sull'invariante non scattano. Nella seconda l'invariante sbagliato si rompe a i=1, perché A[1] = 9 aggiorna m a 9 mentre A[0] vale 3. Un invariante deve reggere in ogni giro, non solo all'inizio, e deve anche essere abbastanza forte da implicare Q all'uscita: m == A[0] non lo è. Ricorda che questi assert sono controlli su input concreti: sono test travestiti da prova. La prova è l'argomento induttivo scritto sopra. Python, inoltre, non esegue gli assert quando l'interprete parte con l'opzione -O, come descrive la documentazione del linguaggio:

assert 1 + 1 == 3, "l'aritmetica e' rotta"
print("ho superato l'assert")

# Ultima riga dell'uscita nei due modi:
# python3 -I assert_o.py  ->  AssertionError: l'aritmetica e' rotta
# python3 -I -O assert_o.py  ->  ho superato l'assert

Con -O la riga dell'asserzione sparisce e il programma stampa la riga successiva. Per questo i contratti che non devono mai essere ignorati vanno scritti con un controllo esplicito e un'eccezione, non con assert; l'asserzione resta lo strumento giusto per documentare e controllare in fase di test.

La weakest precondition di Dijkstra

Dati un comando C e una postcondizione Q, qual è la precondizione meno restrittiva, cioè la più debole, che garantisce Q? Dijkstra la chiama wp(C, Q) e, nella nota EWD 472 (che ha lo stesso titolo del suo articolo del 1975 sui comandi con guardia), la definisce come la precondizione più debole tale che l'esecuzione di C termini correttamente lasciando il sistema in uno stato che soddisfa Q. Le regole che servono qui sono tre.

  • Assegnamento: wp(x := E, Q) è Q con E al posto di ogni occorrenza di x (la stessa regola è l'assioma D0 dell'articolo di Hoare).
  • Sequenza: wp(S1; S2, Q) = wp(S1, wp(S2, Q)), si calcola da destra verso sinistra.
  • Scelta con due rami: wp(if B then S1 else S2, Q) è «se B allora wp(S1, Q), altrimenti wp(S2, Q)»; è il caso con guardie B e ¬B della regola di Dijkstra per l'alternativa.

Con un esempio: per x := x + 1 e Q uguale a x > 5 basta sostituire, e si ottiene x + 1 > 5, cioè x > 4. Se prima dell'istruzione vale x > 4, dopo vale x > 5; una precondizione più forte come x > 10 funziona ma esclude input utili. Calcolare wp all'indietro e confrontarla con la precondizione che hai è il modo in cui gli strumenti di verifica controllano una tripla. Il programma che segue implementa le tre regole come tre classi, confronta wp con l'esecuzione reale su un programma di scambio, e applica lo stesso calcolo al valore assoluto con due aritmetiche: interi illimitati e interi a 16 bit con avvolgimento.

class Assegna:
    """x := E.  wp(x := E, Q) = Q con E al posto di x."""
    def __init__(self, var, expr):
        self.var, self.expr = var, expr

    def esegui(self, s):
        return {**s, self.var: self.expr(s)}

    def wp(self, Q):
        return lambda s: Q(self.esegui(s))


class Seq:
    """S1; S2.  wp(S1; S2, Q) = wp(S1, wp(S2, Q))."""
    def __init__(self, a, b):
        self.a, self.b = a, b

    def esegui(self, s):
        return self.b.esegui(self.a.esegui(s))

    def wp(self, Q):
        return self.a.wp(self.b.wp(Q))


class Se:
    """if C then S1 else S2: wp = (C -> wp(S1,Q)) and (not C -> wp(S2,Q))."""
    def __init__(self, cond, a, b):
        self.cond, self.a, self.b = cond, a, b

    def esegui(self, s):
        return self.a.esegui(s) if self.cond(s) else self.b.esegui(s)

    def wp(self, Q):
        return lambda s: self.a.wp(Q)(s) if self.cond(s) else self.b.wp(Q)(s)


# 1. wp(x := x + 1, x > 5) e' x > 4: confronto su 201 valori di x
inc = Assegna("x", lambda s: s["x"] + 1)
wp1 = inc.wp(lambda s: s["x"] > 5)
print("wp(x := x+1, x>5) coincide con x>4:",
      all(wp1({"x": x}) == (x > 4) for x in range(-100, 101)))

# 2. Scambio con variabile d'appoggio, postcondizione con valori "fantasma" X, Y
scambio = Seq(Assegna("t", lambda s: s["x"]),
              Seq(Assegna("x", lambda s: s["y"]),
                  Assegna("y", lambda s: s["t"])))
Q = lambda s: s["x"] == s["Y"] and s["y"] == s["X"]
P = lambda s: s["x"] == s["X"] and s["y"] == s["Y"]
stati = [{"x": a, "y": b, "t": 0, "X": a, "Y": b} for a in range(-5, 6) for b in range(-5, 6)]
print("scambio: P implica wp(scambio, Q) su", len(stati), "stati:",
      all(scambio.wp(Q)(s) for s in stati if P(s)))
print("scambio: wp(Q) coincide con Q dopo l'esecuzione:",
      all(scambio.wp(Q)(s) == Q(scambio.esegui(s)) for s in stati))


# 3. Valore assoluto: stessa tripla, due semantiche dell'aritmetica
def w16(v):
    return (v + 32768) % 65536 - 32768


def valore_assoluto(neg):
    return Se(lambda s: s["x"] < 0,
              Assegna("x", lambda s: neg(s["x"])),
              Assegna("x", lambda s: s["x"]))


Q_non_neg = lambda s: s["x"] >= 0
for nome, neg in (("interi illimitati", lambda v: -v), ("16 bit, modulo", lambda v: w16(-v))):
    wp = valore_assoluto(neg).wp(Q_non_neg)
    falliti = [x for x in range(-32768, 32768) if not wp({"x": x})]
    print(f"abs con {nome}: stati in cui wp(x >= 0) e' falsa: {falliti}")

# Output:
# wp(x := x+1, x>5) coincide con x>4: True
# scambio: P implica wp(scambio, Q) su 121 stati: True
# scambio: wp(Q) coincide con Q dopo l'esecuzione: True
# abs con interi illimitati: stati in cui wp(x >= 0) e' falsa: []
# abs con 16 bit, modulo: stati in cui wp(x >= 0) e' falsa: [-32768]

La prima riga conferma x > 4 su 201 valori. Le due righe sullo scambio dicono che, per tutti i 121 stati di prova, la precondizione implica wp e che wp(Q) coincide con Q valutata dopo l'esecuzione: la seconda uguaglianza è un vero controllo delle regole di sequenza e di assegnamento contro l'interprete. L'ultima parte è la più istruttiva. Il valore assoluto soddisfa x >= 0 con gli interi illimitati, ma con i 16 bit e l'avvolgimento fallisce per un solo stato, -32768, il cui opposto avvolto vale ancora -32768. Stessa tripla, aritmetica diversa, risultato diverso: è la lettura «modulo» del caso Ariane 501 che trovi nel primo articolo, e il motivo per cui la semantica dell'aritmetica va scritta nella specifica.

Terminazione e funzione di rango

Dimostrare che un ciclo termina richiede una funzione di rango: un'espressione sullo stato che resta un intero non negativo e diminuisce strettamente a ogni giro. Un intero non negativo non può diminuire per sempre, quindi il ciclo si ferma. Nella ricerca binaria il rango è right - left + 1, il numero di elementi ancora in gioco, ed è esattamente ciò che l'asserzione assert 0 <= nuovo < rango controlla nel programma della ricerca. Sulla lista [1, 3, 5, 7, 9] con obiettivo 7 il rango passa da 5 a 2 e al secondo giro l'elemento viene trovato; con left = mid il rango non scende e l'asserzione lo segnala.

La correttezza totale è quindi parziale più terminazione. Dijkstra, nella stessa nota, introduce una funzione intera t definita sullo stato e la precondizione più debole che garantisce che l'esecuzione di un'istruzione termini facendo diminuire t di almeno 1: è la stessa idea della funzione di rango, scritta con la sua notazione. Nella pratica, quando una funzione «sembra» terminare ma non hai il rango, scrivilo: se non riesci a esibire una quantità che decresce, spesso hai individuato il caso limite in cui il ciclo non finisce.

Esercizi

1. Per il ciclo fact = 1; for i in range(1, n + 1): fact *= i scrivi un invariante che implichi fact == n! all'uscita.

Soluzione

All'inizio di ogni giro con indice i vale fact == (i - 1)!. All'ingresso i = 1 e fact = 1 = 0!; dopo fact *= i vale i!, cioè ((i + 1) - 1)! per il giro successivo; all'uscita i = n + 1 e quindi fact == n!. Un controllo con assert su n da 0 a 7 passa.

2. Scrivi la negazione di «tutti gli elementi della lista sono ≥ 0» e un esempio che la rende vera.

Soluzione

La negazione è «esiste un elemento minore di 0»: per la lista [3, -1, 2] è vera, perché -1 < 0. Non è «nessun elemento è ≥ 0», che per quella lista è falsa.

3. Calcola wp(y := 2*y + 1, y > 9) sugli interi.

Soluzione

Si sostituisce: 2*y + 1 > 9, cioè y > 4. Un controllo su y da -100 a 100 conferma che le due condizioni coincidono.

Domande frequenti

Che cosa è una tripla di Hoare, in una riga?

È l'affermazione che, se P è vera prima di eseguire il programma C e C termina, allora Q è vera dopo. Hoare la scrive P {Q} R nell'articolo del 1969; la scrittura {P} C {Q} è equivalente.

Perché un invariante troppo forte è un errore?

Perché deve restare vero a ogni giro: nel programma, m == A[0] vale all'inizio e si rompe quando m viene aggiornato. L'invariante giusto descrive la parte già elaborata (m == max(A[:i])), non il valore iniziale.

La logica del primo ordine basta per specificare tutto?

No. Descrive proprietà di uno stato, non di sequenze di stati nel tempo. Per dire «prima o poi succede» o «non succede mai» serve la logica temporale, argomento del quarto articolo.

Che cosa sai fare adesso

Sai leggere e scrivere precondizioni, postcondizioni e quantificatori in notazione esatta, e sai dire che la negazione di «per ogni» è «esiste uno che no». Sai controllare una tripla di Hoare su un dominio finito con un programma, distinguere un errore sulla postcondizione da uno sulla terminazione, derivare l'invariante di un ciclo dalla postcondizione e calcolare una weakest precondition per assegnamenti, sequenze e scelte. Il prossimo passo è modellare il comportamento di un sistema con gli automi a stati finiti.

Questo è il secondo articolo della serie Metodi Formali. Il precedente è Quando conviene investire in metodi formali; il successivo è Macchine a stati finiti e automi.

L'ultimo articolo della serie, Reti di Petri: struttura, marcature, raggiungibilità, vivezza e sicurezza, chiude il percorso con un modello alternativo alla macchina a stati.

Fonti

Programmi eseguiti con Python 3.14.4 (python3 -I), due volte ciascuno con uscita identica. I conteggi dei casi (756, 16, 201, 121) nascono dai programmi sopra; il numero 756 ha un secondo conto in forma chiusa nel testo.

Articolo pubblicato 2026-10-03, livello graduate.

Commenti

Caricamento commenti...

Accedi per commentare

Articoli e strumenti nuovi anche su Telegram

Il canale Telegram segnala gli articoli e gli strumenti nuovi del sito.

Ti è piaciuto questo articolo?

Esplora altri contenuti sul blog o scopri i miei progetti