Algebra di Boole

Algebra di Boole Algebra di Boole INTRODUZIONE   Ramo della matematica caratterizzato da leggi e proprietà simili a quelle dell'algebra ordinaria. È particolarmente utile in logica e nella teoria degli insiemi grazie alla sua peculiare impostazione su proposizioni e valori di verità, piuttosto che su variabili e valori numerici. 2. DEFINIZIONE DI UN'ALGEBRA DI BOOLE  Formalmente un'algebra di Boole è un sistema matematico costituito da un insieme di elementi, che può essere chiamato B, in cui sono definite due operazioni binarie, che possono essere indicate con i simboli ? e ? soddisfacenti ai seguenti assiomi: 1. ? e ? sono entrambe operazioni commutative. Cioè, presa una coppia qualunque di elementi x, y appartenenti all'insieme B, vale la proprietà per cui x?y = y?x e x?y = y?x. 2. Sussiste per entrambe le operazioni ? e ? la proprietà distributiva. Cioè, per ogni terna di elementi x, y e z appartenenti all'insieme B, sono verificate le relazioni x?(y?z) = (x?y)?(x?z) e x?(y?z) = (x?y)?(x?z). 3. Nell'insieme B esistono due particolari elementi, indicati generalmente con i simboli 0 e 1, tali che 0 ? 1, 0 ?x = x e 1 ?x = x per ogni elemento x dell'insieme B. 0 e 1 sono gli elementi identità, o elementi neutri, rispettivamente per le operazioni ? e ?. 4. Per ogni elemento x dell'insieme B esiste un elemento corrispondente detto il complemento di x, di solito indicato con il simbolo x'. Rispetto alle operazioni ? e ?, l'elemento x' gode della proprietà per cui x?x' = 1 e x?x' = 0. Un'algebra di Boole può essere definita da gruppi di assiomi diversi, ma pur sempre equivalenti a quelli sopra elencati. In questa voce ci siamo attenuti alla formulazione adottata dal matematico statunitense Edward Huntington nel suo lavoro Postulates for the Algebra of Logic (Postulati per l'algebra della logica, 1904). Quest'ultimo contiene una esposizione strettamente assiomatizzata e perfezionata dell'algebra booleana, pubblicata per la prima volta nel 1854 in un originale trattato del matematico britannico George Boole. I simboli per le operazioni ? e ? possono essere scelti con grande libertà; in particolare +, ?, e ? sono talvolta usati in luogo di ?, e ×, ^, ?, ·, e O invece di ?. Dalle proprietà di simmetria degli assiomi rispetto alle due operazioni e dall'esistenza delle loro rispettive identità, si può dimostrare il cosiddetto principio di dualità, secondo cui qualunque affermazione algebrica deducibile dagli assiomi dell'algebra di Boole conserva validità solo se le operazioni ? e ? e le identità 1 e 0 sono interscambiabili all'interno dell'affermazione stessa. Dei molti teoremi che si possono dedurre dagli assiomi di un'algebra di Boole, sono degne di essere menzionate le leggi di Morgan, secondo cui (x?y)' = x'?y' e (x?y)' = x'?y'. 3. ESEMPI  Come esempio di algebra di Boole, si consideri un insieme generico X e sia P(X) la collezione di tutti i possibili sottoinsiemi di X, detto insieme delle parti, o insieme potenza dell'insieme X. P(X), con le due op