LOGICA PER LA PROGRAMMAZIONE – a.a. 2017/18 Quinta esercitazione – 23/11/2017 – Soluzioni Proposte
Attenzione: Le soluzioni che seguono sono considerate corrette dai docenti. Per ogni esercizio possono esistere altre soluzioni corrette, anche molto diverse da quelle proposte.
ESERCIZIO 1 Si fornisca per ognuno dei seguenti enunciati una formula del primo ordine che lo formalizza usando l’interpretazione standard sui naturali e ipotizzando che bar e foo siano due array con dominio rispettivamente [0, n) e [0, m):
1. L’array bar ha al massimo un elemento minore di tutti gli elementi dell’array foo
2. Il primo elemento dell’array foo, se esiste, `e proprio uguale al doppio della somma degli elementi pari dell’array bar
3. La sequenza costituita dall’array bar seguito dall’array foo `e strettamente crescente.
4. Il numero di elementi dell’array bar che sono uguali all’elemento successivo `e minore della somma degli elementi dell’array foo che sono uguali al doppio dell’elemento precedente
5. Ogni elemento dell’array foo di posizione pari `e il triplo di un elemento dell’array bar , mentre tutti gli altri sono minori di tutti gli elementi di bar
SOLUZIONE ESERCIZIO 1
1. L’array bar ha al massimo un elemento minore di tutti gli elementi dell’array foo
#{x : x ∈ [0, n) | bar[x] < (min y : y ∈ [0, m) . foo[y])} ≤ 1
2. Il primo elemento dell’array foo, se esiste, `e proprio uguale al doppio della somma degli ele- menti pari dell’array bar
(m > 0) ⇒ foo[0] = 2 × Σ x : x ∈ [0, n) ∧ pari(bar[x]) . bar[x] 3. La sequenza costituita dall’array bar seguito dall’array foo `e strettamente crescente.
(∀x . x ∈ [0, n − 1) ⇒ bar[x] < bar[x + 1]) ∧ (∀x . x ∈ [0, m − 1) ⇒ foo[x] < foo[x + 1])
∧ ((n > 0) ∧ (m > 0) ⇒ bar[n − 1] < foo[0])
4. Il numero di elementi dell’array bar che sono uguali all’elemento successivo `e minore della somma degli elementi dell’array foo che sono uguali al doppio dell’elemento precedente
#{i : i ∈ [0, n − 1) | bar[i] = bar[i + 1]} < (Σj : j ∈ (0, m) ∧ foo[j] = 2 ∗ foo[j − 1] . foo[j]) 1
5. Ogni elemento dell’array foo di posizione pari `e il triplo di un elemento dell’array bar , mentre tutti gli altri sono minori di tutti gli elementi di bar
∀x . x ∈ [0, m) ⇒ (pari(x) ⇒ (∃y . y ∈ [0, n) ∧ foo[x] = 3 ∗ bar[y])) ∧ (dispari(x) ⇒ (∀y . y ∈ [0, n) ⇒ foo[x] < bar[y]))
ESERCIZIO 2 Si consideri il seguente array a con dominio [0, 4):
7 6 11 4
Si dimostri, utilizzando pi`u volte la legge dell’intervallo per la sommatoria, la validit`a della seguente formula:
m = (Σx : x ∈ [0, 4) ∧ pari (a[x]) . (a[x] − 1)2) ≡ m = 34 SOLUZIONE ESERCIZIO 2
m = (Σx : x ∈ [0, 3] ∧ pari (a[x]) . (a[x] − 1)2)
≡ {(Intervallo-Σ), pari(a[3])}
m = (Σx : x ∈ [0, 2] ∧ pari (a[x]) . (a[x] − 1)2) + 9
≡ {(Intervallo-Σ), ¬pari(a[2])}
m = (Σx : x ∈ [0, 1] ∧ pari (a[x]) . (a[x] − 1)2) + 9
≡ {(Intervallo-Σ), pari(a[1])}
m = (Σx : x ∈ [0, 0] ∧ pari (a[x]) . (a[x] − 1)2) + 9 + 25
≡ {(Intervallo-Σ), ¬pari(a[0])}
m = (Σx : x ∈ [0, 0) ∧ pari (a[x]) . (a[x] − 1)2) + 34
≡ {(Σ-vuoto)}
m = 34
ESERCIZIO 3 Si consideri il seguente array a con dominio [0, 5): 5 2 4 0 3 Si spieghi a parole cosa calcola la seguente formula e si dica quanto vale k:
k = (Σx : x ∈ [0, 5) ∧ (a[x] ∈ [0, 5) ⇒ pari (a[a[x]])). x) SOLUZIONE ESERCIZIO 3
La formula dice che k `e la somma degli indici degli elementi di a che se contengono un valore del dominio di a allora l’elemento in quella posizione `e un numero pari. Quindi k = 0 + 1 + 4 = 5.
Formalmente abbiamo che
k = (Σx : x ∈ [0, 5) ∧ (a[x] ∈ [0, 5) ⇒ pari (a[a[x]])). x)
≡ {(Intervallo-Σ), a[4] = 3 ∈ [0, 5) ∧ pari (a[3]), quindi l’implicazione `e vera per x 7→ 4}
k = (Σx : x ∈ [0, 4) ∧ (a[x] ∈ [0, 5) ⇒ pari (a[a[x]])). x) + 4
≡ {(Intervallo-Σ), a[3] = 0 ∈ [0, 5) ∧ ¬pari (a[0]), quindi l’implicazione `e falsa per x 7→ 3}
2
k = (Σx : x ∈ [0, 3) ∧ (a[x] ∈ [0, 5) ⇒ pari (a[a[x]])). x) + 4
≡ {(Intervallo-Σ), a[2] = 4 ∈ [0, 5) ∧ ¬pari (a[4])}
k = (Σx : x ∈ [0, 2) ∧ (a[x] ∈ [0, 5) ⇒ pari (a[a[x]])). x) + 4
≡ {(Intervallo-Σ), a[1] = 2 ∈ [0, 5) ∧ pari (a[2])}
k = (Σx : x ∈ [0, 1) ∧ (a[x] ∈ [0, 5) ⇒ pari (a[a[x]])). x) + 4 + 1
≡ {(Intervallo-Σ), ¬a[0] ∈ [0, 5), quindi l’implicazione `e vera per x 7→ 0}
k = (Σx : x ∈ [0, 0) ∧ (a[x] ∈ [0, 5) ⇒ pari (a[a[x]])). x) + 0 + 4 + 1
≡ {(Σ-vuoto)}
k = 5
ESERCIZIO 4 Dimostrare la seguente formula usando le ipotesi non tautologiche e la legge dell’intervallo per la sommatoria:
m = Σy : y ∈ [0, z) . a[y] + 2 ∗ Σy : y ∈ [0, z) . y ⇒
m + a[z] + 2 ∗ z = Σy : y ∈ [0, z] . a[y] + 2 ∗ Σy : y ∈ [0, z] . y
SOLUZIONE ESERCIZIO 4
Per dimostrare l’implicazione partiamo dalla conseguenza usando la premessa come ipotesi non tautologica:
m + a[z] + 2 ∗ z = Σy : y ∈ [0, z] . a[y] + 2 ∗ Σy : y ∈ [0, z] . y
≡ {(Intervallo-Σ)}
m + a[z] + 2 ∗ z = Σy : y ∈ [0, z) . a[y] + a[z] + 2 ∗ Σy : y ∈ [0, z] . y
≡ {calcolo}
m + 2 ∗ z = Σy : y ∈ [0, z) . a[y] + 2 ∗ Σy : y ∈ [0, z] . y
≡ {(Intervallo-Σ)}
m + 2 ∗ z = Σy : y ∈ [0, z) . a[y] + 2 ∗ ( Σy : y ∈ [0, z) . y + z)
≡ {calcolo}
m = Σy : y ∈ [0, z) . a[y] + 2 ∗ Σy : y ∈ [0, z) . y
≡ Ip: m = Σy : y ∈ [0, z) . a[y] + 2 ∗ Σy : y ∈ [0, z) . y
T
ESERCIZIO 5 Usando le ipotesi non tautologiche e le opportune leggi dell’intervallo, dimo- strare la seguente formula assumendo che gli array a e b abbiano dominio [0, n) e che x ∈ (0, n):
∀i . i ∈ [0, x) ⇒ b[i] = Σj : j ∈ [0, i] . a[j]
∧ b[x] = b[x − 1] + a[x] ⇒
∀i . i ∈ [0, x] ⇒ b[i] = Σj : j ∈ [0, i] . a[j]
SOLUZIONE ESERCIZIO 5
Per dimostrare l’implicazione partiamo dalla conseguenza usando la premessa come ipotesi non tautologica:
3
∀i . i ∈ [0, x] ⇒ b[i] = Σj : j ∈ [0, i] . a[j]
≡ {(Intervallo-∀), x > 0}
∀i . i ∈ [0, x) ⇒ b[i] = Σj : j ∈ [0, i] . a[j]
∧ b[x] = Σj : j ∈ [0, x] . a[j]
≡ Ip: ∀i . i ∈ [0, x) ⇒ b[i] = Σj : j ∈ [0, i] . a[j], (Unit`a) b[x] = Σj : j ∈ [0, x] . a[j]
≡ {Ip: b[x] = b[x − 1] + a[x]}
b[x − 1] + a[x] = Σj : j ∈ [0, x] . a[j]
≡ {(Intervallo-Σ)}
b[x − 1] + a[x] = Σj : j ∈ [0, x) . a[j] + a[x]
≡ {calcolo}
b[x − 1] = Σj : j ∈ [0, x) . a[j]
≡ Ip: ∀i . i ∈ [0, x) ⇒ b[i] = Σj : j ∈ [0, i] . a[j], (Elim-∀), x > 0 e quindi x − 1 ∈ [0, x) T
4
