Teoremi di Shannon
Data una proposizione logica qualsiasi Q, ciascuno dei due teoremi di Shannon produce una proposizione booleana equivalente a Q.
Nonostante siano attribuiti a Claude Shannon, i teoremi sono stati enunciati per la prima volta da George Boole.
Primo teorema di Shannon
Data la tavola di verità di una proposizione logica Q:
- Considera solo le righe della tavola di verità in cui il risultato è VERO
- Per ciascuna riga considerata, osserva i valori di verità delle proposizioni semplici. Se la proposizione ha valore di verità VERO, trascrivila. Altrimenti, negala.
- Unisci proposizioni di una stessa riga con il connettivo logico AND.
- Unisci righe diverse con il connettivo logco OR.
Ad esempio, data la seguente tavola di verità:
| A | B | C | Q |
|---|---|---|---|
| V | V | V | F |
| V | V | F | F |
| V | F | V | V ← |
| V | F | F | F |
| F | V | V | V ← |
| F | V | F | F |
| F | F | V | F |
| F | F | F | F |
Applicando il primo teorema di Shannon, otterremmo la seguente proposizione booleana, equivalente a Q:
Secondo teorema di Shannon
Data la tavola di verità di una proposizione logica Q:
- Considera solo le righe della tavola di verità in cui il risultato è FALSO
- Per ciascuna riga considerata, osserva i valori di verità delle proposizioni semplici. Se la proposizione ha valore di verità FALSO, trascrivila. Altrimenti, negala.
- Unisci proposizioni di una stessa riga con il connettivo logico OR.
- Unisci righe diverse con il connettivo logco AND.
Ad esempio, data la seguente tavola di verità:
| A | B | C | Q |
|---|---|---|---|
| V | V | V | F ← |
| V | V | F | V |
| V | F | V | V |
| V | F | F | F ← |
| F | V | V | V |
| F | V | F | V |
| F | F | V | V |
| F | F | F | F ← |
Applicando il secondo teorema di Shannon, otterremmo la seguente proposizione booleana, equivalente a Q:
Domanda: Secondo te, ci sono casi in cui è più opportuno applicare il primo teorema di Shannon, e altri in cui è più opportuno applicare il secondo? Se sì, motiva la tua risposta.