Logica e fondamenti d'informatica

Fondamenti di Logica e Informatica

Logica

La logica è una disciplina che studia i principi del ragionamento e del pensiero coerente. È

fondamentale in informatica per la progettazione di algoritmi, sistemi di calcolo e circuiti

digitali.

La logica proposizionale si occupa di proposizioni che possono essere vere o false, e delle

operazioni che collegano queste proposizioni. Le proposizioni sono frasi che sono o vere o

false, come "Il cielo è blu". Gli operatori logici principali sono:

AND (∧): Coniuga due proposizioni e il risultato è vero solo se entrambe sono vere.

 OR (∨): Coniuga due proposizioni e il risultato è vero se almeno una delle due è

 vera.

NOT (¬): Inverte il valore di verità di una proposizione.

 IMPLICA (→): Una proposizione implica un'altra se la prima è vera e la seconda

 deve essere vera.

EQUIVALENTE (↔): Due proposizioni sono equivalenti se entrambe sono vere o

 entrambe false.

Una tabella di verità rappresenta l'output di un'espressione logica in funzione delle

possibili combinazioni delle sue proposizioni.

Le leggi della logica includono:

Legge di De Morgan:

 ¬(P Q) = ¬P ¬Q

∧ ∨

o ¬(P Q) = ¬P ¬Q

∨ ∧

o

Contraddizione e tautologia:

 Una contraddizione è una proposizione sempre falsa, mentre una tautologia

o è una proposizione sempre vera.

La logica booleana è alla base della progettazione dei circuiti digitali. I circuiti possono

essere combinatori, che dipendono solo dalle entrate attuali, o sequenziali, che dipendono

anche dallo stato precedente.

Automata e Linguaggi Formali

Un automa è una struttura matematica che descrive i processi computazionali. Gli

automata a stati finiti (DFA) sono macchine che elaborano una sequenza di simboli, con

il comportamento determinato dallo stato corrente e dalle transizioni in base al simbolo

letto.

Un linguaggio formale è un insieme di stringhe costruite su un alfabeto, e i linguaggi

sono classificati in base alla loro complessità:

Lingua regolare: Descritta da un automa a stati finiti.

 Lingua context-free: Descritta da una grammatica senza contesto.

 Lingua context-sensitive: Più complessa, può essere descritta da una

 grammatica sensibile al contesto.

Teoria della Computabilità

La computabilità studia i limiti di ciò che può essere calcolato. Una funzione calcolabile

è una funzione che può essere computata da un algoritmo. Alcuni problemi sono

indecidibili, come il problema della fermata di Turing, che chiede se un dato

programma terminerà o meno.

La Macchina di Turing è un modello teorico di calcolatore composto da un nastro che

rappresenta la memoria, una testa di lettura/scrittura, uno stato e una tabella di transizione

che determina l'azione della macchina in base al simbolo letto.

Algoritmi e Strutture Dati

Gli algoritmi sono procedure per risolvere problemi, e le strutture dati organizzano e

archiviano i dati per una gestione efficiente.

La complessità computazionale misura quanto tempo e memoria richiede un algoritmo,

ed è espressa in termini di O-grande:

O(1): Tempo costante.

 O(log n): Tempo logaritmico (tipico in algoritmi come la ricerca binaria).

 O(n): Tempo lineare.

 O(n²): Tempo quadratico (tipico di algoritmi come bubble sort).

 O(2^n): Tempo esponenziale (tipico in problemi di ottimizzazione).



Le strutture dati comuni includono:

Liste: Sequenze ordinate di elementi.

 Pile (Stack): Struttura dati LIFO (Last In, First Out).

 Code (Queue): Struttura dati FIFO (First In, First Out).

 Alberi: Strutture dati gerarchiche, come gli alberi binari.

 Grafi: Strutture dati che rappresentano relazioni complesse tra nodi.



Gli algoritmi di ordinamento più comuni sono:

Ordinamento a bolle (Bubble Sort): Semplice ma inefficiente.

 Ordinamento rapido (Quick Sort): Divide et impera, molto efficiente.

 Ordinamento a fusione (Merge Sort): Efficiente, ma richiede memoria extra.



Programmazione

La programmazione è l'arte di scrivere istruzioni che i computer possono eseguire. I

principali paradigmi di programmazione includono:

Programmazione Imperativa: Scrittura di comandi sequenziali (es. C, Python).

 Programmazione Funzionale: Basata su funzioni pure e immutabilità (es.

 Haskell).

Programmazione Orientata agli Oggetti (OOP): Usa oggetti e classi per

 rappresentare entità nel mondo reale (es. Java, C++).

Programmazione Logica: Basata sulla logica formale, come nel linguaggio Prolog.



Ogni linguaggio di programmazione ha una sintassi e semantica unica:

Linguaggi di basso livello: Più vicini all'hardware, come l'assembly.

 Linguaggi di alto livello: Più facili da usare, come Python e Java.



Teoria degli Algoritmi

La teoria degli algoritmi riguarda lo studio dei metodi per risolvere problemi in modo

efficiente, minimizzando l'uso di risorse come tempo e memoria. Gli algoritmi di

ordinamento e di ricerca sono esempi comuni.

Le tipologie di complessità degli algoritmi sono:

Tempo di esecuzione (time complexity): Misurato con la notazione O-grande.

 Alcuni esempi sono:

O(1): Tempo costante.

o O(n): Tempo lineare.

o O(n²): Tempo quadratico.

o

Spazio (space complexity): Misura la memoria richiesta dall'algoritmo.



Architettura dei Calcolatori

L'architettura dei calcolatori si occupa della progettazione dei componenti hardware di

un sistema informatico, e di come questi interagiscono tra loro. I componenti principali di

un calcolatore sono:

CPU (Unità di elaborazione centrale): Responsabile dell'esecuzione delle

 istruzioni.

Memoria principale (RAM): Memoria volatile per dati e istruzioni.

 Memorie di massa: Dispositivi come hard disk e SSD per l'archiviazione

 permanente.

Unità di controllo: Gestisce il flusso delle istruzioni e coordina le operazioni.

 Bus di sistema: Canale di comunicazione tra i componenti.



Il ciclo di istruzione descrive il processo in cui la CPU esegue le istruzioni di un

programma:

1. Fetch: Recupero dell'istruzione dalla memoria.

2. Decode: Decodifica dell'istruzione.

3. Execute: Esecuzione dell'operazione.

4. Store: Memorizzazione del risultato.

Sistemi Operativi

Un sistema operativo (SO) è un software che gestisce le risorse hardware e software di

un calcolatore. Le sue principali funzioni includono la gestione dei processi, della memoria,

delle periferiche e dei file, nonché la fornitura di un'interfaccia utente.

Esistono vari tipi di sistemi operativi:

Monoutente e Multiutente: Un sistema può supportare uno o più utenti

 simultaneamente.

Multitasking: Permette di eseguire più programmi contemporaneamente.



Sicurezza Informatica

La sicurezza informatica riguarda la protezione dei dati e dei sistemi da accessi non

autorizzati, danni o attacchi. Le minacce comuni includono il malware, il phishing e gli

attacchi DDoS. Le tecniche di protezione includono la criptografia, l'autenticazione e i

firewall.

Logica Proposizionale

La logica proposizionale, o logica delle proposizioni, è un ramo della logica matematica

che si occupa dello studio delle proposizioni e dei loro collegamenti tramite connettivi

logici. Le proposizioni sono affermazioni che possono essere vere o false. I connettivi

logici sono operatori che permettono di costruire nuove proposizioni a partire da

proposizioni esistenti. I principali connettivi logici sono:

Negazione (¬): inverte il valore di verità di una proposizione. Se una proposizione è

 vera, la sua negazione è falsa, e viceversa.

Congiunzione (∧): la proposizione risultante è vera solo se entrambe le

 proposizioni congiunte sono vere.

Disgiunzione (∨): la proposizione risultante è vera se almeno una delle

 proposizioni disgiunte è vera.

Implicazione (→): l'implicazione "P → Q" è falsa solo quando P è vera e Q è falsa,

 altrimenti è vera.

Doppia implicazione (↔): è vera quando entrambe le proposizioni hanno lo stesso

 valore di verità.

La logica proposizionale si occupa anche di tabella di verità, un metodo per determinare

il valore di verità di una proposizione complessa in base ai valori di verità delle sue

componenti.

Logica del Primo Ordine

La logica del primo ordine, o logica predicativa, è un'estensione della logica proposizionale

che introduce i predicati e i quantificatori. I predicati sono funzioni che mappano un

insieme di oggetti su un insieme di valori di verità. I quantificatori, che includono il

quantificatore universale (∀) e il quantificatore esistenziale (∃), permettono di fare

affermazioni su tutti gli elementi di un dominio o su almeno uno di essi.

Un esempio di una proposizione in logica del primo ordine è:

"Tutti gli uomini sono mortali" può essere scritto come (Uomo(x) → Mortale(x)),

 ∀x

dove "Uomo(x)" è un predicato che afferma che "x è un uomo", e "Mortale(x)"

afferma che "x è mortale".

La logica del primo ordine è potente perché permette di esprimere una vasta gamma di

affermazioni formali, ed è la base della logica matematica e dell'intelligenza artificiale,

specialmente nell'ambito dei sistemi esperti e delle basi di conoscenza.

Teoria degli Insiemi

La teoria degli insiemi è un ramo della logica matematica che si occupa dello studio degli

insiemi, che sono collezioni di oggetti. Gli insiemi possono essere definiti in vari modi, ad

esempio tramite enumerazione degli elementi o tramite una proprietà che definisce gli

elementi. Alcuni concetti fondamentali nella teoria degli insiemi includono:

Sottoinsiemi: Un insieme A è un sottoinsieme di B se ogni elemento di A è anche

 un elemento di B, indicato come A B.

⊆

Unione (∪): L'unione di due insiemi A e B è l'insieme che contiene tutti gli elementi

 che appartengono ad almeno uno dei due insiemi.

Intersezione (∩): L'intersezione di due insiemi A e B è l'insieme che contiene s olo

 gli elementi che appartengono sia ad A che a B.

Differenza (−): La differenza di due insiemi A e B è l'insieme che contiene gli

 elementi che appartengono ad A ma non a B.

Complimento: Il complemento di un insieme A, rispetto a un insieme universale U,

 è l'insieme di tutti gli elementi che non appartengono ad A.

La teoria degli insiemi è un pilastro della