Corso di Laurea in Informatica Linguaggio e Metodi della Matematica Soluzioni prima prova intermedia del 3 Novembre 2003

Esercizio 1. Tra le seguenti formule proposizionali:

(1) ( (a ∧ ¬b) → (a ∨ ¬b) ) ∨ (b → ¬a)
(2) ¬b → ¬a
(3) (a → b) → ( (b → a) ∧ (¬a ∧ b) )
(4) a ∧ ¬b

• individuare le tautologie;

• individuare le coppie di formule equivalenti;

• individuare le coppie di formule che siano l’una la negazione dell’altra.

Soluzione: (1) è una tautologia (ha tutti 1 nella tavola di verità). (3) e (4) sono equivalenti (stessa tavola di verità). Sia (3) che (4) equivalgono alla negazione di (2) (tavole di verità con 0 ed 1 invertiti).

Esercizio 2. Si consideri il seguente enunciato: “n è il più piccolo numero dell’insieme A”.

• Determinare quale delle seguenti formule esprime l’enunciato di sopra:

(1) n ∈ A ∧ ∀x(n ≤ x → x ∈ A)
(2) ∀x(x ∈ A ∧ n ≤ x)
(3) ∀x(x ∈ A → n ≤ x)
(4) n ∈ A ∧ ∀x(x ∈ A → n ≤ x)

• Determinare quale delle seguenti formule ne esprime la negazione:

(a) n ∉ A ∧ ∀x(x < n → x ∉ A)
(b) n ∉ A ∨ ∃x(x < n ∧ x ∈ A)
(c) n ∉ A ∨ ∃x(x < n → x ∉ A)
(d) n ∉ A ∧ ∃x(x < n → x ∉ A)

Soluzioni: (4), (b).

Esercizio 3. Si consideri la formula f(x) = x^{2} − x. Dire (giustificando) se tale formula definisce una funzione f : A → A, e se tale funzione è iniettiva, è suriettiva, è biunivoca, in ciascuno dei seguenti casi:

1. A è l’insieme dei numeri interi positivi pari.

2. A è l’insieme dei numeri interi positivi dispari.

3. A è l’insieme dei numeri reali maggiori o uguali a 2.

Soluzioni:

Domanda 1: definita, iniettiva, non surgettiva, quindi non biunivoca.

Dimostrazione: La formula definisce una funzione in quanto se x è pari anche x^{2} lo è e quindi lo è anche x^{2} − x in quanto differenza di due numeri pari. I primi valori della funzione sono f(2) = 2, f(4) = 12, f(6) = 30, f(8) = 56. Si intuisce che il valore 4 (ad esempio) non verrà mai preso e che quindi f non è surgettiva. Per dimostrarlo si cerca di risolvere l’equazione x^{2} − x = 4. Portando il 4 dall’altra parte dell’uguaglianza e applicando la formula risolutiva all’equazione x^{2}−x−4 = 0 si ottiene x = \frac{1±\sqrt{1+16}}{2}. Nessuno dei due valori della x è intero e quindi non può appartenere all’ insieme A. Risulta in questo modo dimostrato che f: A → A non è surgettiva. Per quanto riguarda l’iniettività si può ragionare come segue. Esaminando i primi valori di f si intuisce che f è crescente, cioè presi due valori in ingresso a < b (con a, b ∈ A) si ha f(a) < f(b). Per dimostrarlo basta riscrivere x^{2} − x come x(x − 1) e osservare che se a < b abbiamo anche a − 1 < b − 1 e pertanto, siccome le disuguaglianze si mantengono moltiplicandole per numeri positivi, si ottiene f(a) = a(a−1) < a(b−1) < b(b−1) = f(b). La f è quindi crescente, e quindi in particolare non può assumere due volte lo stesso valore, il che vuol dire che f è iniettiva.

Domanda 2. non definita.

Dimostrazione: f non è definita in quanto prendendo x = 3 si ottiene per x^{2} − x un valore pari che quindi non appartiene ad A. Infatti 3^{2} − 3 = 6 ∉ A.

Domanda 3. definita, surgettiva, iniettiva, quindi biunivoca. .

Idea geometrica: Il grafico di x^{2} − x è una parabola. Una parabola definisce una funzione da ℝ ad ℝ che non è nè iniettiva nè surgettiva. Tuttavia nel nostro caso stiamo considerando solo la porzione della parabola che parte dal punto (2, 2) e cresce verso l’infinito man mano che l’ascissa x cresce. Ciò implica che f è iniettiva e surgettiva nel dominio considerato, ovvero per ogni y ≥ 2 esiste un ed un solo valore x ≥ 2 tale che il punto (x, y) giace sulla porzione di parabola considerata.

Dimostrazione formale: Se x ≥ 2, allora x^{2} − x = x(x − 1) ≥ 2 · 1 = 2. Quindi f è definita. Per la surgettività basta osservare che se y ≥ 2 allora l’equazione x^{2} − x = y (con x incognita e y dato) ha soluzione (in ℝ) x = \frac{1±\sqrt{1+4y}}{2} (dove il numero sotto il segno di radice è positivo e pertanto la radice è ben definita). Delle due soluzioni così ottenute, almeno una (quella con il segno + davanti alla radice) è maggiore o uguale a 2 (essendo \frac{1+\sqrt{1+4y}}{2} ≥ \frac{1+\sqrt{1+4·2}}{2} ≥ 2). Quindi f è surgettiva. Infine osserviamo che l’altra soluzione, quella con il segno − davanti alla radice, non è mai maggiore o uguale a 2 (essendo minore di 1/2). Quindi per ogni y ∈ A, l’equazione x^{2} − x = y ha una ed una sola soluzione x nell’insieme A. Ciò equivale a dire che f è iniettiva.

Esercizio 4. Dimostrare per induzione che se n ≥ 5 allora 3^{n} > 7n^{2}.

Soluzione: Caso base: svolgendo i calcoli si vede che 3^{5} > 7 · 5^{2}, quindi il caso base è verificato. Passo induttivo: supponiamo per ipotesi induttiva che 3^{n} > 7n^{2}. Dobbiamo verificare che

3^{n+1} > 7(n + 1)^{2}.  (1)

Analizziamo i due termini di questa disuguaglianza. Per quanto riguarda il primo termine, usando l’ipotesi induttiva otteniamo 3^{n+1} = 3 · 3^{n} > 3 · 7n^{2} = 21n^{2}. D’altra parte svolgendo i calcoli nel secondo termine otteniamo 7(n + 1)^{2} = 7n^{2} + 14n + 7. Per ottenere la (1) basta quindi dimostrare che 21n^{2} ≥ 7n^{2} + 14n + 7 e cioè (cancellando 7n^{2} da entrambi i lati e dividendo per 7)

2n^{2} ≥ 2n + 1  (2)

La (2) (che implica la (1) componendo le disuguaglianze) è di facile verifica. Infatti: 2n^{2} = 2n · n ≥ 2n · 2 = 2n + 2n ≥ 2n + 1, dove la prima disuguaglianza dipende dal fatto che n ≥ 2 (essendo in effetti n ≥ 5).

Corso di Laurea in Informatica Linguaggio e Metodi della Matematica Prima prova intermedia del 3 Novembre 2003

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Tra le seguenti formule proposizionali:

(1) (a → b) → ( (¬a ∧ b) ∧ (b → a) )

(2) ¬b → ¬a
(3) ¬b ∧ a
(4) ( (a ∧ ¬b) → (a ∨ ¬b) ) ∨ (a → ¬b)

• individuare le tautologie;

• individuare le coppie di formule equivalenti;

• individuare le coppie di formule che siano l’una la negazione dell’altra.

Esercizio 2. Si consideri il seguente enunciato: “n è il più grande numero dell’insieme B”.

• Determinare quale delle seguenti formule esprime l’enunciato di sopra: (1) ∀x(x ∈ B → x ≤ n)

(2) ∀x(x ≤ n → x ∈ B) ∧ (n ∈ B)
(3) ∀x(x ∈ B → x ≤ n) ∧ (n ∈ B)
(4) ∀x(x ≤ n ∧ x ∈ B)

• Determinare quale delle seguenti formule ne esprime la negazione: (a) ∃x(n < x → x ∉ B) ∨ n ∉ B

(b) ∀x(n < x → x ∉ B) ∧ n ∉ B
(c) ∃x(n < x → x ∉ B) ∧ n ∉ B
(d) ∃x(n < x ∧ x ∈ B) ∨ n ∉ B

Esercizio 3. Si consideri la formula g(z) = 2z^{2} + 2z. Dire (giustificando) se tale formula definisce una funzione g : A → A, e se tale funzione è iniettiva, è suriettiva, è biunivoca, in ciascuno dei seguenti casi:

1. A è l’insieme dei numeri reali maggiori o uguali a 1.

2. A è l’insieme dei numeri interi positivi pari.

3. A è l’insieme dei numeri interi positivi dispari. Esercizio 4. Dimostrare per induzione che se n ≥ 4 allora 2 · 3^{n} > 9n^{2}.

Corso di Laurea in Informatica Linguaggio e Metodi della Matematica Prima prova intermedia del 3 Novembre 2003

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Tra le seguenti formule proposizionali:

(1) ¬a → ¬b

(2) ( (¬a ∧ b) → (b ∨ ¬a) ) ∨ (a → ¬b)
(3) ¬a ∧ b
(4) (b → a) → ( (a → b) ∧ (a ∧ ¬b) )

• individuare le tautologie;

• individuare le coppie di formule equivalenti;

• individuare le coppie di formule che siano l’una la negazione dell’altra.

Esercizio 2. Si consideri il seguente enunciato: “k è il più piccolo numero dell’insieme B”.

• Determinare quale delle seguenti formule esprime l’enunciato di sopra: (1) ∀x(x ∈ B → k ≤ x) ∧ k ∈ B

(2) ∀x(k ≤ x ∧ x ∈ B)
(3) ∀x(k ≤ x → x ∈ B) ∧ k ∈ B
(4) ∀x(x ∈ B → k ≤ x)

• Determinare quale delle seguenti formule ne esprime la negazione: (a) ∃x(x < k → x ∉ B) ∨ k ∉ B

(b) ∀x(x < k → x ∉ B) ∧ k ∉ B
(c) ∃x(x < k → x ∉ B) ∧ k ∉ B
(d) ∃x(x < k ∧ x ∈ B) ∨ k ∉ B

Esercizio 3. Si consideri la formula g(x) = x^{2} +2x. Dire (giustificando) se tale formula definisce una funzione g : B → B, e se tale funzione è iniettiva, è suriettiva, è biunivoca, in ciascuno dei seguenti casi:

1. B è l’insieme dei numeri reali maggiori o uguali a 1.

2. B è l’insieme dei numeri interi positivi pari.

3. B è l’insieme dei numeri interi positivi dispari. Esercizio 4. Dimostrare per induzione che se n ≥ 8 allora 2^{n} > 3n^{2}.

Corso di Laurea in Informatica Linguaggio e Metodi della Matematica Prima prova intermedia del 3 Novembre 2003

Cognome e nome: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numero di matricola:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corso e Aula: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Firma: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E-mail (per eventuali comunicazioni): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Esercizio 1. Tra le seguenti formule proposizionali:

(1) (b → a) → ( (a → b) ∧ (a ∧ ¬b) )

(2) ( (¬a ∧ b) → (b ∨ ¬a) ) ∨ (b → ¬a)
(3) ¬a → ¬b
(4) b ∧ ¬a

• individuare le tautologie;

• individuare le coppie di formule equivalenti;

• individuare le coppie di formule che siano l’una la negazione dell’altra.

Esercizio 2. Si consideri il seguente enunciato: “k è il più grande numero dell’insieme A”.

• Determinare quale delle seguenti formule esprime l’enunciato di sopra: (1) ∀x(x ∈ A ∧ x ≤ k)

(2) ∀x(x ∈ A → x ≤ k)
(3) k ∈ A ∧ ∀x(x ∈ A → x ≤ k)
(4) k ∈ A ∧ ∀x(x ≤ k → x ∈ A)

• Determinare quale delle seguenti formule ne esprime la negazione: (a) k ∉ A ∧ ∀x(k < x → x ∉ A)

(b) k ∉ A ∨ ∃x(k < x ∧ x ∈ A)
(c) k ∉ A ∨ ∃x(k < x → x ∉ A)
(d) k ∉ A ∧ ∃x(k < x → x ∉ A)

Esercizio 3. Si consideri la formula f(z) = z^{2} −2z. Dire (giustificando) se tale formula definisce una funzione f : B → B, e se tale funzione è iniettiva, è suriettiva, è biunivoca, in ciascuno dei seguenti casi:

1. B è l’insieme dei numeri interi positivi pari.

2. B è l’insieme dei numeri interi positivi dispari.

3. B è l’insieme dei numeri reali maggiori o uguali a 3. Esercizio 4. Dimostrare per induzione che se n ≥ 6 allora 3 · 2^{n} > 4n^{2}.