Glossario dei Simboli Logici e Matematici
Questa pagina elenca i principali simboli utilizzati nel corso di Elementi di Logica e Strutture Discrete, con una breve descrizione del loro significato e uso.
Logica Proposizionale
$p, q, r, \dots$
Variabili Proposizionali (Atomi)
Rappresentano proposizioni elementari che possono essere Vere (1) o False (0).
$\neg A$
Negazione (NOT)
Si legge "non A". È vera se $A$ è falsa, e falsa se $A$ è vera. Esempio: $\neg (p \wedge q)$.
$A \wedge B$
Congiunzione (AND)
Si legge "A e B". È vera se e solo se sia $A$ sia $B$ sono vere.
$A \vee B$
Disgiunzione Inclusiva (OR)
Si legge "A o B". È vera se almeno una tra $A$ e $B$ è vera (o entrambe).
$A \Rightarrow B$
Implicazione Materiale (Se... allora...)
Si legge "se A allora B" o "A implica B". È falsa solo quando $A$ è vera e $B$ è falsa.
$A \Leftrightarrow B$
Doppia Implicazione (Bicondizionale, Se e solo se)
Si legge "A se e solo se B". È vera se e solo se $A$ e $B$ hanno lo stesso valore di verità.
$A \oplus B$
OR Esclusivo (XOR)
Si legge "A o B, ma non entrambi". È vera se e solo se $A$ e $B$ hanno valori di verità diversi.
$\perp$
Falsum (Contraddizione, Assurdo)
Rappresenta una proposizione sempre falsa.
$\top$
Verum (Tautologia)
Rappresenta una proposizione sempre vera. (Può essere definita come $\neg \perp$).
$\equiv$
Equivalenza Logica
Indica che due formule proposizionali sono logicamente equivalenti (hanno la stessa tavola di verità). Esempio: $A \Rightarrow B \equiv \neg A \vee B$.
Teoria degli Insiemi
$A, B, C, \dots$
Insiemi
Collezioni di elementi.
$x, y, a, b, \dots$
Elementi
Oggetti appartenenti a un insieme.
$x \in A$
Appartenenza
"$x$ appartiene all'insieme $A$" o "$x$ è un elemento di $A$".
$x \notin A$
Non Appartenenza
"$x$ non appartiene all'insieme $A$".
$\{ \dots \}$
Definizione di Insieme per Elencazione
Esempio: $A = \{1, 2, 3\}$.
$\{x \mid P(x)\}$
Definizione di Insieme per Proprietà
"L'insieme degli $x$ tali che la proprietà $P(x)$ è vera".
$\emptyset$ o $\{\ \}$
Insieme Vuoto
L'insieme che non contiene alcun elemento.
$A \subseteq B$
Sottoinsieme (Inclusione Debole)
"$A$ è sottoinsieme di $B$". Ogni elemento di $A$ è anche elemento di $B$. $A$ può essere uguale a $B$.
$A \subset B$
Sottoinsieme Proprio (Inclusione Stretta)
"$A$ è sottoinsieme proprio di $B$". $A \subseteq B$ e $A \neq B$.
$A \not\subseteq B$
Non è Sottoinsieme
"$A$ non è sottoinsieme di $B$".
$\mathcal{P}(A)$ o $2^A$
Insieme delle Parti
L'insieme di tutti i sottoinsiemi di $A$.
$A \cup B$
Unione
L'insieme degli elementi che appartengono ad $A$ o a $B$ (o a entrambi).
$A \cap B$
Intersezione
L'insieme degli elementi che appartengono sia ad $A$ sia a $B$.
$\overline{A}$ o $A^c$
Complementare
L'insieme degli elementi (dell'universo considerato) che non appartengono ad $A$.
$A \setminus B$ o $A-B$
Differenza Insiemistica
L'insieme degli elementi che appartengono ad $A$ ma non a $B$.
$A \triangle B$
Differenza Simmetrica
L'insieme degli elementi che appartengono ad $A$ o a $B$, ma non a entrambi. Equivale a $(A \setminus B) \cup (B \setminus A)$.
$A \times B$
Prodotto Cartesiano
L'insieme di tutte le coppie ordinate $(a,b)$ con $a \in A$ e $b \in B$.
$|A|$
Cardinalità di A
Il numero di elementi nell'insieme $A$.
Logica del Primo Ordine (Logica dei Predicati)
$x, y, z, \dots$
Variabili Individuali
Segnaposto per oggetti/individui del dominio di discorso.
$a, b, c, \dots$
Costanti Individuali
Nomi per specifici oggetti/individui del dominio.
$f(t_1,\dots,t_n)$
Termine Funzionale
$f$ è un simbolo di funzione $n$-aria, $t_i$ sono termini. Denota un oggetto del dominio.
$P(t_1,\dots,t_n)$
Formula Atomica (Predicativa)
$P$ è un simbolo di predicato $n$-ario, $t_i$ sono termini. Esprime una proprietà o relazione.
$t_1 = t_2$
Uguaglianza
Formula atomica che afferma che i termini $t_1$ e $t_2$ denotano lo stesso oggetto.
$\forall x A$
Quantificatore Universale
Si legge "per ogni $x$, $A$ (è vera)". Afferma che la formula $A$ è vera per tutti i possibili valori di $x$ nel dominio.
$\exists x A$
Quantificatore Esistenziale
Si legge "esiste un $x$ tale che $A$ (è vera)". Afferma che c'è almeno un valore di $x$ nel dominio per cui $A$ è vera.
$FV(A)$
Insieme delle Variabili Libere
L'insieme delle variabili in una formula $A$ che non sono vincolate da un quantificatore.
$A[t/x]$
Sostituzione
La formula ottenuta sostituendo tutte le occorrenze libere della variabile $x$ in $A$ con il termine $t$ (con cautela per evitare cattura di variabili).
$\mathcal{M} = (D,I)$
Struttura / Modello
$D$ è il dominio (universo del discorso), $I$ è la funzione di interpretazione per costanti, funzioni e predicati.
Simboli di Inferenza e Calcolo
$\models A$
Validità Logica / Tautologia
"$A$ è logicamente valida" (o una tautologia, per la logica proposizionale). Significa che $A$ è vera in ogni interpretazione/struttura.
$\Gamma \models A$
Conseguenza Logica (Semantica)
"$A$ è una conseguenza logica dell'insieme di premesse $\Gamma$". Ogni interpretazione/struttura che rende vere tutte le formule in $\Gamma$ rende vera anche $A$.
$\Gamma \vdash A$
Derivabilità Sintattica
"$A$ è derivabile (o dimostrabile) dall'insieme di premesse $\Gamma$" usando un certo sistema di calcolo (es. Deduzione Naturale).
$(I\wedge), (E\wedge), \dots$
Regole di Inferenza
Nomi delle regole usate nei sistemi di calcolo come la Deduzione Naturale (es. Introduzione dell'AND, Eliminazione dell'OR, Modus Ponens).
Altri Simboli Matematici Utili
$\mathbb{N}$
Insieme dei Numeri Naturali
Solitamente $\{0, 1, 2, 3, \dots\}$ o talvolta $\{1, 2, 3, \dots\}$.
$\mathbb{Z}$
Insieme dei Numeri Interi
$\{\dots, -2, -1, 0, 1, 2, \dots\}$.
$\mathbb{Q}$
Insieme dei Numeri Razionali
Numeri esprimibili come frazioni $a/b$ con $a,b \in \mathbb{Z}$ e $b \neq 0$.
$\mathbb{R}$
Insieme dei Numeri Reali
Include razionali e irrazionali.
$\sum_{i=k}^{n} a_i$
Sommatoria
$a_k + a_{k+1} + \dots + a_n$.
$\prod_{i=k}^{n} a_i$
Produttoria
$a_k \cdot a_{k+1} \cdot \dots \cdot a_n$.
$n!$
Fattoriale
$n \cdot (n-1) \cdot \dots \cdot 1$. $0!=1$.
$\binom{n}{k}$
Coefficiente Binomiale
Si legge "$n$ su $k$". Numero di modi di scegliere $k$ elementi da un insieme di $n$ elementi. Vale $\frac{n!}{k!(n-k)!}$.
$x|y$
Divisibilità
"$x$ divide $y$". Significa che esiste un intero $k$ tale che $y = kx$.
$x \pmod n$
Modulo
Resto della divisione intera di $x$ per $n$.