Formulario del Corso
Questa pagina contiene un riepilogo delle principali formule e regole utili per il corso di Elementi di Logica e Strutture Discrete.
Sommatorie Notevoli
$\sum_{i=1}^{n} 1 = n$
$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
(Somma di Gauss)
$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$
(Somma dei primi n quadrati)
$\sum_{i=1}^{n} i^3 = \frac{n^2(n+1)^2}{4} = \left(\sum_{i=1}^{n} i\right)^2$
(Somma dei primi n cubi)
$\sum_{i=0}^{n} q^i = \frac{1-q^{n+1}}{1-q} = \frac{q^{n+1}-1}{q-1} \quad (\text{con } q \neq 1)$
(Somma dei termini di una progressione geometrica)
Se $q=1$, $\sum_{i=0}^{n} 1 = n+1$.
$\sum_{i=1}^{n} (2i-1) = n^2$
(Somma dei primi n numeri dispari)
Regole di Precedenza degli Operatori Logici
L'ordine di valutazione, dal più restrittivo (lega di più) al meno restrittivo:
$\forall, \exists$ (stessa priorità) $\quad < \quad \neg \quad < \quad \wedge \quad < \quad \vee \quad < \quad \Rightarrow, \Leftrightarrow$ (stessa priorità)
In caso di parità di precedenza tra $\Rightarrow$ e $\Leftrightarrow$, o tra $\forall$ e $\exists$, si consiglia l'uso di parentesi per chiarezza, sebbene spesso si intenda un'associazione da sinistra a destra.
Regole di Deduzione Naturale
Regole Elementari
$\frac{A \quad B}{A \wedge B}$ ($I\wedge$)
Introduzione Congiunzione
$\frac{A \wedge B}{A}$ ($E\wedge_1$)
Eliminazione Congiunzione
$\frac{A \wedge B}{B}$ ($E\wedge_2$)
Eliminazione Congiunzione
$\frac{A}{A \vee B}$ ($I\vee_1$)
Introduzione Disgiunzione
$\frac{B}{A \vee B}$ ($I\vee_2$)
Introduzione Disgiunzione
$\frac{A \quad A \Rightarrow B}{B}$ (MP, $E\Rightarrow$)
Eliminazione Implicazione (Modus Ponens)
$\frac{A \quad \neg A}{\perp}$ ($I\perp$ o $E\neg$)
Introduzione Falsità / Eliminazione Negazione
$\frac{\perp}{A}$ (EFQ, $E\perp$)
Eliminazione Falsità (Ex Falso Quodlibet)
Regole Condizionali (con scaricamento di ipotesi)
$\begin{array}{c} [A]^u \\ \vdots \\ B \\ \hline A \Rightarrow B \end{array}$ ($I\Rightarrow, u$)
Introduzione Implicazione
$\begin{array}{c c c} & [A]^u & [B]^w \\ & \vdots & \vdots \\ A \vee B & C & C \\ \hline & C & \end{array}$ ($E\vee, u, w$)
Eliminazione Disgiunzione (Prova per Casi)
$\begin{array}{c} [A]^u \\ \vdots \\ \perp \\ \hline \neg A \end{array}$ ($I\neg, u$)
Introduzione Negazione
$\begin{array}{c} [\neg A]^u \\ \vdots \\ \perp \\ \hline A \end{array}$ (RAA, $u$)
Reductio Ad Absurdum