Matematica discreta
La matematica discreta è la matematica delle cose separate e contabili: vero o falso, dentro un insieme o fuori, questo percorso o quello. È la matematica su cui girano i computer, e comincia con una logica che puoi accendere e spegnere.
Ultimo aggiornamento
La matematica discreta è la matematica delle cose separate e contabili. Un'affermazione è vera o falsa, un elemento sta in un insieme oppure no, una rete ha un collegamento tra due punti oppure non ce l'ha. Non c'è niente in mezzo, ed è questo che significa "discreto": è esattamente il modo in cui un computer vede il mondo.
Un primo corso tratta sei argomenti: logica, insiemi, calcolo combinatorio, grafi, teoria dei numeri e dimostrazione. La logica viene per prima, perché tutti gli altri argomenti sono scritti con lei. Scegli un connettivo qui sotto e cambia p e q.
Tavola di verità di p ∧ q
| p | q | p ∧ q |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Cambia p e q, o clicca su una riga. La riga evidenziata è quella che scelgono.
Leggi p come "x sta in A" e q come "x sta in B". Le regioni colorate sono quelle in cui l'affermazione è vera; il punto è la riga attuale.
p ∧ q
Si legge p e q
Con questi valori, p ∧ q è vera.
Vera solo quando p e q sono entrambe vere.
Come insiemi AND è l'intersezione: x sta in A ∩ B esattamente quando x sta in A e x sta in B.
Logica: proposizioni e connettivi
Una proposizione è una frase che è vera o falsa, come "7 è primo" o "sta piovendo". La logica costruisce proposizioni più grandi a partire da altre più piccole con pochi connettivi, e una tavola di verità elenca il risultato per ogni combinazione di input.
| simbolo | nome | si legge | vera quando |
|---|---|---|---|
| ∧ | AND, congiunzione | "p e q" | sono vere entrambe |
| ∨ | OR, disgiunzione | "p o q" | almeno una è vera |
| ¬ | NOT, negazione | "non p" | p è falsa |
| ⊕ | XOR, disgiunzione esclusiva | "p o q, ma non entrambe" | esattamente una è vera |
| → | IMPLICA, condizionale | "se p, allora q" | in tutti i casi tranne p vera e q falsa |
| ↔ | SSE, bicondizionale | "p se e solo se q" | p e q hanno lo stesso valore |
Due di questi sorprendono. L'OR logico è inclusivo: "p o q" è vera quando sono vere entrambe, a differenza del "tè o caffè?" di tutti i giorni. La versione esclusiva ha un nome tutto suo, XOR.
L'altro è IMPLICA. p → q è falsa in una sola riga, quando p è vera e q è falsa. Pensala come una promessa: "se piove, porterò l'ombrello". La promessa è infranta solo se piove e l'ombrello non c'è. In una giornata asciutta la promessa non è stata infranta, qualunque cosa tu abbia con te, quindi l'affermazione conta come vera.
Proposizioni equivalenti
Due proposizioni sono equivalenti quando le loro tavole di verità coincidono su ogni riga. Nel widget, scegli OR e nega p: la colonna di ¬p ∨ q è identica alla colonna di p → q, quindi le due dicono la stessa cosa.
Le equivalenze più utili sono le leggi di De Morgan, che dicono come NOT passa attraverso AND e OR:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
A parole: "non entrambe" è lo stesso di "l'una o l'altra è falsa", e "nessuna delle due" è lo stesso di "sono false entrambe". I programmatori le usano ogni giorno per riscrivere una condizione come "non (ha fatto l'accesso ed è verificato)".
Logica e insiemi sono la stessa idea
Leggi p come "x sta in A" e q come "x sta in B". Allora AND è l'intersezione, OR è l'unione e NOT è il complementare, e ogni tavola di verità è un diagramma di Venn colorato, ed è per questo che il widget ne disegna uno accanto alla tabella. Le leggi di De Morgan diventano regole sugli insiemi:
(A ∩ B)′ = A′ ∪ B′
La pagina sulla notazione degli insiemi colora ognuna di queste su un diagramma su cui puoi cliccare.
Contare
In matematica discreta contare significa contare senza elencare. Due regole fanno quasi tutto il lavoro.
La regola del prodotto. Se una scelta si può fare in m modi e una seconda in n modi, la coppia si può fare in m × n modi. Un PIN di 4 cifre ha 10 scelte per ogni cifra, quindi ci sono 10^4 = 10000 PIN possibili.
Combinazioni. Il numero di modi di scegliere k cose tra n, quando l'ordine non conta, si scrive C(n, k). Scegliere 3 condimenti tra 8:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
Il numeratore conta le scelte ordinate, e dividere per 3 × 2 × 1 elimina i 6 ordini in cui si sarebbero potuti scegliere gli stessi tre condimenti.
La risposta è 6 × 5 diviso 2, cioè 15. Se ti è venuto 30, hai contato ogni coppia due volte, una per ciascun ordine.
Grafi
Un grafo è un insieme di punti, chiamati vertici, uniti da linee, chiamate archi (o spigoli). Modella qualsiasi cosa fatta di collegamenti: strade tra città, amici in un social network, link tra pagine web.
Un primo risultato: se 5 persone si stringono tutte la mano una volta sola, le strette di mano sono C(5, 2) = 10. Ogni persona stringe 4 mani, il che dà 5 × 4 = 20 estremità, e ogni stretta di mano ha due estremità, quindi 20 / 2 = 10. Questo ragionamento è il lemma delle strette di mano: la somma dei gradi di tutti i vertici è il doppio del numero di archi.
Teoria dei numeri e dimostrazione
L'aritmetica modulare è l'aritmetica dell'orologio. 17 mod 5 fa 2, il resto della divisione di 17 per 5. Nove ore dopo le 8 sono le 5, perché 17 mod 12 fa 5. La stessa idea, con numeri molto grandi, è il modo in cui funziona la crittografia RSA dietro i siti web sicuri.
La dimostrazione per induzione mostra che un'affermazione vale per ogni numero intero n in due passi: verificala per n = 1, poi mostra che se vale per un certo n vale anche per n + 1. È così che si dimostra, per esempio, che
1 + 2 + ... + n = n(n + 1) / 2
per ogni n, non solo per i valori che hai provato.
A cosa serve la matematica discreta
- Programmazione: ogni istruzione if è logica, e le leggi di De Morgan riscrivono le condizioni.
- Database: una query che unisce o filtra tabelle è fatta di operazioni tra insiemi.
- Algoritmi: il calcolo combinatorio ti dice quanti passi fa un programma quando l'input cresce.
- Reti e mappe: i percorsi più brevi e i social network sono problemi sui grafi.
- Sicurezza: la crittografia si basa sulla teoria dei numeri e sull'aritmetica modulare.
- Hardware: un processore è costruito con porte logiche, che sono tavole di verità nel silicio.
La matematica discreta è difficile?
È difficile in modo diverso dall'algebra e dall'analisi. Ci sono poche formule da memorizzare e i calcoli sono piccoli, ma molte domande ti chiedono di dimostrare qualcosa invece di calcolarlo, e scrivere un ragionamento convincente è un'abilità nuova per la maggior parte degli studenti.
Ciò che aiuta di più è risolvere a mano i casi piccoli prima di cercare lo schema: disegna il diagramma di Venn, scrivi la tavola di verità, elenca ogni caso. All'inizio la notazione sembra pesante, ma in gran parte sono i simboli di questa pagina e della pagina sulla notazione degli insiemi.
Domande frequenti
- Cos'è la matematica discreta?
- La branca della matematica che studia oggetti separati e contabili invece di grandezze che variano con continuità. I suoi argomenti principali sono logica, insiemi, calcolo combinatorio, grafi, teoria dei numeri e dimostrazione. L'analisi si chiede come cambiano le cose in modo continuo; la matematica discreta si chiede quanti, quali, e se un'affermazione è vera.
- La matematica discreta è difficile?
- È difficile in modo diverso dall'analisi. Ci sono meno formule da applicare e più ragionamenti da costruire, e per molti studenti è il primo corso costruito attorno alla scrittura di dimostrazioni. L'algebra di solito è leggera. Chi la trova difficile si sta soprattutto abituando alle dimostrazioni, e questo migliora in fretta allenandosi su esempi piccoli.
- A cosa serve la matematica discreta?
- A quasi tutto in informatica. La logica è il modo in cui funzionano i circuiti e le istruzioni if, gli insiemi stanno sotto le query dei database, il calcolo combinatorio ti dice quanto tempo impiega un algoritmo, i grafi modellano reti e mappe, e la teoria dei numeri è la base della crittografia che protegge i pagamenti online.
- Quali argomenti si studiano in matematica discreta?
- Un tipico primo corso tratta logica proposizionale e tavole di verità, insiemi e diagrammi di Venn, funzioni e relazioni, tecniche di dimostrazione tra cui l'induzione, calcolo combinatorio con permutazioni e combinazioni, probabilità di base, grafi e alberi, e aritmetica modulare. Alcuni corsi aggiungono relazioni di ricorrenza e algebra di Boole.
- Serve la matematica discreta per l'informatica?
- Sì. Quasi ogni corso di laurea in informatica la richiede, di solito al primo o al secondo anno, perché algoritmi, strutture dati e teoria della computazione la danno per scontata. Per programmare e basta puoi iniziare senza, ma logica, insiemi e calcolo combinatorio saltano fuori nel codice di tutti i giorni prima di quanto la maggior parte delle persone si aspetti.
- Che differenza c'è tra matematica discreta e continua?
- La matematica discreta tratta valori che puoi elencare uno per uno, come i numeri interi, vero e falso, o i nodi di una rete. La matematica del continuo, come l'analisi, tratta grandezze che possono assumere qualsiasi valore in un intervallo, come il tempo, la distanza o la temperatura.
- Cos'è una tavola di verità?
- Una tabella che elenca ogni combinazione di vero e falso per gli input di un'affermazione logica, e il valore dell'affermazione per ciascuna. Con due input p e q ci sono quattro righe. La tavola di verità è il modo per dimostrare che due affermazioni sono equivalenti: se le loro colonne coincidono su ogni riga, sono sempre d'accordo.
