Corso di Laurea in Informatica Linguaggio e Metodi della Matematica: Lista di esercizi per prepararsi al compitino

Esercizio 1. Si esprima in linguaggio naturale il significato della seguente formula ∀x∃y(x < y) → ¬∃y∀x(x ≤ y).

Esercizio 2. Usando le notazioni logiche, le costanti numeriche 0, 1, 2, …, e le operazioni di somma e prodotto, si esprima l’enunciato

“Ogni numero intero è pari o dispari”.

Esercizio 3. Dire se le seguenti inclusioni valgono per tutti gli insiemi A, B, C, D, motivando la risposta. 1. B ∩ D ⊆ (C ∩ B) ∪ (A ∩ D) ∪ (A ∩ C);

2. A ∪ C ∪ D ⊇ (B − A) ∩ C;

3. (B − D) − A ⊇ (B − A) − (C ∪ D). Esercizio 4. Dati tre sottoinsiemi A, B, C di N, usando le consuete operazioni insiemistiche (unione, intersezione, differenza e complemento) scrivere un’espressione che denota:

1. l’insieme dei numeri naturali che appartengono ad uno ed uno solo degli insiemi A o B.

2. l’insieme dei numeri naturali che appartengono ad uno ed uno solo degli insiemi A o B o C. Esercizio 5. Si considerino le funzioni:

• f : Z → Q definita per ogni z ∈ Z da f(z) = \frac{3z+1}{2z+1}

• g : Q → Q definita per ogni q ∈ Q da g(q) = q^{2} − \frac{1}{2}.

1. Per ciascuna delle due funzioni, f e g, dire se è iniettiva, surgettiva o biunivoca.

2. Dire se si possono definire le funzioni f ∘g e g∘f ed in caso affermativo dire se sono iniettive, surgettive o

biunivoche. Giustificare le risposte. Esercizio 6. Siano A, B e C tre insiemi. Dire se ciascuna delle seguenti affermazioni è vera o falsa, giustificando la risposta.

1. Se B ∩ A ⊆ C allora B ⊆ C e A ⊆ C;

2. Se B \ A ⊆ C allora B ⊆ A ∪ C;

3. Se B ⊆ A ∪ C e B ∩ A = ∅ allora B ⊆ C \ A;

4. Se B ⊆ A ∪ C allora B ∩ A ≠ ∅.

Esercizio 7.

• Stabilire se la seguente formula è o no una tautologia: [A → (B ∨ C) ∧ (¬B ∧ ¬C)] → ¬A.

• Stabilire se Q è conseguenza logica di (P → Q) ∧ (¬P → Q). Esercizio 8. Si considerino le seguenti 5 formule ed i seguenti 5 enunciati.

1. ∀x ∈ R (x > 0 → f(x) ≠ 0). a. La funzione f assume un valore non positivo sul numero 0.
2. ∀x ∈ R (f(x) ≤ 0 → x = 0). b. La funzione f si annulla su qualche numero positivo.
3. ∃x ∈ R(f(x) < 0 ∧ x < 0). c. Su qualche numero diverso da zero, la funzione f assume valori non positivi.
4. ∀x ∈ R (f(x) > 0 → x ≠ 0). d. La funzione f non si annulla mai su numeri reali positivi.
5. ∃x ∈ R (f(x) = 0 ∧ x > 0). e. C’è un numero non negativo la cui immagine mediante f è un numero positivo.

• Individuare, se ve ne sono, le coppie costituite da una formula ed un enunciato aventi lo stesso significato (per ogni coppia specificare il numero della formula e la lettera dell’enunciato corrispondente).

• Individuare, se ve ne sono, le coppie di formule che sono una equivalente alla negazione dell’altra (per ogni coppia di formule specificare i due numeri corrispondenti).

Esercizio 9. Si considerino le seguenti funzioni:

1. f : Z → Z definita da f(x) = 3x + 5 per ogni x ∈ Z;

2. g : R → R definita da g(x) = 3x + 5 per ogni x ∈ R;

3. h : R → R definita da h(x) = x^{2} + 7 per ogni x ∈ R;

4. φ : R → R è la funzione composizione di g con h, cioè φ = h ∘ g.

• Stabilire se le funzioni f, g, h e φ siano iniettive, surgettive o biunivoche e, nei casi possibili, determinare l’inversa della funzione;

• Determinare l’immagine di h, cioè l’insieme {y ∈ R | ∃x ∈ R h(x) = y};

• Determinare le controimmagini di y = 8 mediante φ, cioè l’insieme {x ∈ R | φ(x) = 8}.

Esercizio 10. Dimostrare per induzione che, per ogni n ≥ 1, vale l’uguaglianza

3 · \frac{5}{2} + 3 · (\frac{5}{2})^{2} + 3 · (\frac{5}{2})^{3} + ... + 3 · (\frac{5}{2})^{n} = \frac{5 · (5^{n} − 2^{n})}{2^{n}}

Esercizio 11. Si considerino le seguenti funzioni:

• f : Z → Z definita per ogni z ∈ Z da f(z) = 1 − 3z ;

• g : Z → Q definita per ogni z ∈ Z da g(z) = \frac{5}{z^{2}+1} .

1. Dire se le due funzioni sono iniettive, surgettive, biunivoche. Giustificare le risposte.

2. Determinare tutti i numeri interi che appartengono all’immagine di g

3. Scrivere la funzione g ∘ f.

Esercizio 12. Determinare (se ve ne sono) le coppie di enunciati equivalenti:

1. ∃x∀y(y = 0 ∧ x < y)

2. ∃x∀y(y ≠ 0 → x < y)

3. ∃x∀y(y ≠ 0 ∨ x < y)

4. ∀x∃y(y = 0 ∨ y < x)

5. ∃x∀y(x < y ∨ y = 0) Esercizio 13. Usando le notazioni logiche e le operazioni aritmetiche di somma, prodotto ed elevamento a potenza, si trovi una espressione della forma {x | P (x)} che denoti l’insieme dei numeri naturali maggiori di uno che sono potenza di un numero primo (si ricordi che una potenza di un primo è un numero della forma p^{n}, con p primo). Esercizio 14. Elencare tutti i numeri naturali minori di 20 che appartengono all’insieme

{x | x > 4 → ∀y[(∃k(yk = x) ∧ y è primo ) → y ≤ 5]}.

Esercizio 15. Sia f: N → N la funzione definita nel modo seguente.

f(n) = \{ \begin{matrix}\frac{n}{2} & se n è pari \\ \frac{n}{5} & se n non è pari ed è multiplo di 5 \\ n & se n non è pari e non è multiplo di 5 \end{matrix}

Stabilire se f è iniettiva, surgettiva, biunivoca. Esercizio 16. Siano A, B e C tre insiemi assegnati. Usando esclusivamente i simboli di unione ∪, intersezione ∩, differenza insiemistica \, insieme vuoto ∅, inclusione ⊆, uguaglianza =, non uguaglianza ≠, e le parentesi, si formalizzino i seguenti enunciati: (Attenzione: non si può usare il simbolo ∈ di appartenenza).

1. Ogni elemento di C appartiene a B o ad A.

2. Non vi sono elementi di B che appartengono ad A ma non a C. Esercizio 17. Si dimostri per induzione su n ∈ N che n^{n} ≥ n!. Esercizio 18. Si formalizzi nel linguaggio dei numeri naturali con somma, prodotto, ordine (<), e predicato di divisibilità (x | y), e il predicato “x è primo”, il seguente enunciato:

Non tutti i divisori primi di n sono minori di 10.

Esercizio 19. Si determinino tutte le equivalenze che sussistono tra i seguenti enunciati.

1. X = {x | P (x)} ∩ {y | Q(y)}.

2. X = {x | P (x)} ∩ {x | Q(x)}.

3. X = {x | P (x) ∧ Q(x)}.

4. X = {(x, y) | P (x) ∧ Q(y)}.

5. {x | P (x)} ⊆ {x | Q(x)}.

6. ∀xP (x) → ∀xQ(x).

7. ∀x(P (x) → Q(x)).

8. ∀xy(P (x) → Q(y)).

9. ∀x(Q(x) → P (x)). Esercizio 20. Determinare nella seguente lista se vi siano due espressioni che denotano lo stesso insieme, qualunque sia la scelta degli insiemi A, B, C. La risposta deve essere giustificata.

1. (A × C) ∪ (B × C)

2. (A ∪ C) × (B ∪ C)

3. (A ∪ B) × C

4. (A × B) ∪ C Esercizio 21. Assumendo che il dominio delle variabili sia Z, si considerino i seguenti insiemi e si stabiliscano le mutue relazioni di inclusione e/o di uguaglianza.

1. A = {x | ∃k(x = 6k)}

2. B = {x | ∃k(x = 10k)}

3. C = {x | ∃k(x = 30k)}

4. A ∩ B. Esercizio 22. Si determini quali delle seguenti formule sono equivalenti:

1. ¬(p ∧ (q ∨ r))

2. p ∧ q ∧ ¬r

3. (¬p ∨ ¬q) ∧ (¬p ∨ ¬r) Esercizio 23. Si stabilisca quali delle seguenti formule sono vere nel dominio N degli interi non negativi. Si svolga poi lo stesso esercizio per i domini Z ed R.

1) ∃x∀y(x + y = y),

2) ∀y∃x(x + y = 0),

3) ∀x∀y∃z(x < z ∧ z < y),

4) ∀x∃y(x < y ∧ ¬∃z(x < z ∧ z < y)). Esercizio 24. Dire quali delle seguenti sono vere per ogni insieme A, B e C:

• \overline{A} ∪ \overline{B} = \overline{A ∪ B}.

• (A − B) ∩ C = (A ∩ C) − B.

• A − (B ∩ C) = (A − B) ∩ (A − C).

• A − (B ∪ C) = (A − B) ∩ (A − C).

• (A − B) − C = (A − C) − B Esercizio 25. Si dimostri che per ogni intero n ≥ 1 si ha 3^{n} > n^{2} + n. Esercizio 26. Si stabilisca quali delle seguenti funzioni sono iniettive, quali sono surgettive, e quali biunivoche. Nel caso di funzioni biunivoche si calcoli l’inversa.

1. f : Z → Z definita da f(x) = 4x + 1.

2. g : Z → Z definita da g(x) = x − 3.

3. f ∘ g, con f, g come sopra.

4. h : R → {x ∈ R | x ≥ 0} definita da h(x) = (x − 1)^{2}