Pages: [1]   Go Down
Print
Author Topic: Esercizio di verifica formale di programmi  (Read 287 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.927



WWW
« on: 12-12-2017, 14:01:59 »

Dimostrare formalmente che il seguente programma settete
calcola la funzione identita' su liste.

settete []     = []
settete (a:ys) = [a]++(settete ys)



Dimostrare formalmente che il seguente programma s
calcola la somma degli elementi della lista di interi fornita in input.

s []     = 0
s (n:xs) = n + (s xs)
Logged
teo998
Matricola
*
Offline Offline

Posts: 43



WWW
« Reply #1 on: 12-12-2017, 15:00:59 »

i è la funzione che indica il numero di elementi dell'argomento

passo base, per i=0
settete [] = []

passo induttivo
Ip. settete a = a, per qualunque a tale che i a = k
Ts. settete b = b, per qualunque b tale che i b = k+1
Dim.
qualunque b, esiste una coppia x,a tale che a = [ x]++b
settete b = settete (x:a) = [ x]++(settete a) = [ x]++a = b



passo base, per i=0
s [] = 0

passo induttivo
Ip. s a = a[0]+a[1]+a[2]+...+a[k-1], per qualunque a tale che i a = k
Ts. s b = b[0]+b[1]+b[2]+...+b[k-1]+b[k], per qualunque b tale che i b = k+1
Dim.
qualunque b, esiste una coppia x,a tale che a = [ x]++b
b[0]=x, b[1]=a[0], b[2]=a[1], ..., b[k]=a[k-1]
s b = s (x:a) = x+(s a) = x+a[0]+a[1]+a[2]+...+a[k-1] =  b[0]+b[1]+b[2]+...+b[k-1]+b[k]
Logged
Pages: [1]   Go Up
Print
Jump to: