Fondamenti di informatica - Laurea triennale Informatica/Logica proposizionale
Una frase che è vera oppure falsa (ma non entrambe) si chiama proposizione.
Operatori logici: AND, OR, NOT
[modifica | modifica sorgente]Useremo variabili come p,q,r per rappresentare proposizioni, e le combineremo con connettivi come and, or, not.
AND
[modifica | modifica sorgente]Siano p e q proposizioni.
La congiunzione di p e q, indicata con p∧q, è la proposizione “p e q”.
Il valore di verità di p∧q è definito dalla seguente tavola di verità:
Tavola di verità di p∧q
[modifica | modifica sorgente]| p | q | p∧q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Questa tavola formalizza l’interpretazione usuale di “e”: la congiunzione è vera solo se entrambe le proposizioni sono vere.
OR
[modifica | modifica sorgente]Siano p e q proposizioni.
La disgiunzione (in senso inclusivo) di p e q, indicata con p∨q, è la proposizione “p oppure q”.
Il valore di verità di p∨q è definito dalla seguente tavola di verità:
Tavola di verità di p∨q
[modifica | modifica sorgente]| p | q | p∨q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Qui “or” è inclusivo: la disgiunzione è vera se è vera almeno una tra p e q (anche se lo sono entrambe).
Esiste anche l’“or esclusivo” (XOR) che risulta vero quando è vera una sola delle due.
Tavola di verità di p⊕q
[modifica | modifica sorgente]| p | q | p⊕q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
NOT
[modifica | modifica sorgente]Sia p una proposizione.
La negazione di p, indicata con ¬p, è la proposizione “non p” (o “non è vero che p”).
Il valore di verità di ¬p è definito dalla seguente tavola di verità:
Tavola di verità di ¬p
[modifica | modifica sorgente]| p | ¬p |
|---|---|
| T | F |
| F | T |
Tabelle di verità e costruzione sistematica
[modifica | modifica sorgente]Le tabelle di verità elencano tutte le combinazioni possibili di valori di verità delle proposizioni componenti (T/F) e, per ciascuna combinazione, indicano il valore di verità della proposizione composta.
Se una proposizione P è formata da n proposizioni elementari, la sua tavola di verità contiene 2n righe.
Precedenza degli operatori
[modifica | modifica sorgente]In assenza di parentesi, si segue di solito questa precedenza:
- prima si valuta ¬ (NOT)
- poi ∧ (AND)
- infine ∨ (OR)