Algebra booleana: storia, teoremi e postulati, esempi
Algebra booleana o algebra booleana è la notazione algebrica utilizzata per il trattamento di variabili binarie. Copre gli studi di qualsiasi variabile che ha solo 2 risultati possibili, complementari e reciprocamente esclusivi. Ad esempio, le variabili la cui unica possibilità è vera o falsa, corretta o errata, attivata o disattivata, sono alla base dello studio dell'algebra booleana.
L'algebra booleana costituisce la base dell'elettronica digitale, che la rende piuttosto presente nei tempi moderni. È governato dal concetto di porte logiche, in cui le operazioni note nell'algebra tradizionale sono significativamente influenzate.
storia
L'algebra booleana fu introdotta nel 1854 dal matematico inglese George Boole (1815-1864), che era un erudito autodidatta dell'epoca. La sua preoccupazione derivava da una disputa tra Augustus De Morgan e William Hamilton, sui parametri che definiscono questo sistema logico.
George Boole sosteneva che la definizione dei valori numerici 0 e 1 corrisponde, nel campo della logica, rispettivamente all'interpretazione di Nulla e dell'Universo .
L'intenzione di George Boole era di definire, attraverso le proprietà dell'algebra, le espressioni della logica proposizionale necessarie per trattare le variabili di tipo binario.
Nel 1854 le sezioni più significative dell'algebra booleana sono pubblicate nel libro " Un'indagine sulle leggi del pensiero su cui si basano le teorie matematiche della logica e della probabilità".
Questo curioso titolo sarebbe riassunto di seguito come " Le leggi del pensiero" ("Le leggi del pensiero"). Il titolo è balzato alla fama grazie all'attenzione immediata che ha avuto da parte della comunità matematica del tempo.
Nel 1948 Claude Shannon lo applicò nella progettazione di circuiti di commutazione elettrici bistabili. Ciò servì come introduzione all'applicazione dell'algebra booleana all'interno dell'intero schema elettronico-digitale.
struttura
I valori elementari in questo tipo di algebra sono 0 e 1, che corrispondono rispettivamente a FALSE e TRUE. Le operazioni fondamentali nell'algebra booleana sono 3:
- Operazione AND o congiunzione. Rappresentato da un punto (.). Sinonimo per il prodotto
- OPPURE operazione o disgiunzione. Rappresentato da una croce (+). Sinonimo della somma.
- Operazione NOT o negazione. Rappresentato dal prefisso NOT (NOT A). È anche conosciuto come un supplemento.
Se un insieme A definisce 2 leggi di composizione interna denotate come prodotto e somma (. +), Si dice che la tripla (A. +) sia un'algebra booleana se e solo se detta tripla soddisfa la condizione di essere un reticolo distributiva.
Per definire una rete distributiva, devono essere soddisfatte le condizioni di distribuzione tra le operazioni indicate:
. è distributivo rispetto alla somma + a. (b + c) = (a. b) + (a.c)
+ è distributivo rispetto al prodotto. a + (b c) = (a + b). (a + c)
Gli elementi che compongono l'insieme A devono essere binari, quindi avere valori dell'universo o vuoti.
applicazioni
Il suo principale scenario applicativo è il ramo digitale, in cui serve a strutturare i circuiti che costituiscono le operazioni logiche coinvolte. L'arte della semplicità dei circuiti a favore dell'ottimizzazione dei processi è il risultato della corretta applicazione e pratica dell'algebra booleana.
Dallo sviluppo di quadri elettrici, alla trasmissione di dati, alla programmazione in lingue diverse, possiamo trovare frequentemente l'algebra booleana in tutti i tipi di applicazioni digitali.
Le variabili booleane sono molto comuni nella struttura della programmazione. A seconda del linguaggio di programmazione utilizzato, ci saranno operazioni di codice strutturale che utilizzano queste variabili. Gli argomenti condizionali e di ogni lingua supportano le variabili booleane per definire i processi.
postulati
Ci sono teoremi che governano le leggi logiche strutturali dell'algebra booleana. Allo stesso modo, ci sono postulati per conoscere i possibili risultati in diverse combinazioni di variabili binarie, a seconda dell'operazione eseguita.
Somma (+)
L'operatore OR il cui elemento logico è l'unione (U) è definito per le variabili binarie come segue:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Prodotto (.)
L'operatore AND il cui elemento logico è l'intersezione (∩) è definito per le variabili binarie come segue:
0. 0 = 0
0. 1 = 0
1. 0 = 0
1. 1 = 1
Opposto (NON)
L'operatore NOT il cui elemento logico è il complemento (X) 'è definito per le variabili binarie come segue:
NOT 0 = 1
NON 1 = 0
Molti postulati differiscono dai loro equivalenti nell'algebra convenzionale. Ciò è dovuto al dominio delle variabili. Ad esempio, l'aggiunta di elementi dell'universo nell'algebra booleana (1 + 1) non può produrre il risultato convenzionale di 2, perché non appartiene agli elementi del set binario.
teoremi
Regola di zero e unità
Qualsiasi operazione semplice che coinvolge un elemento con le variabili binarie è definita:
0 + A = A
1 + A = 1
0. A = 0
1. A = A
Poteri uguali o idempotencia
Le operazioni tra le variabili uguali sono definite come:
A + A = A
A. A = A
complementazione
Ogni operazione tra una variabile e il suo complemento è definita come:
A + NOT A = 1
A. NON A = 0
Involuzione o doppia negazione
Qualsiasi doppia negazione sarà considerata come la variabile naturale.
NON (NON A) = A
commutativa
A + B = B + A; Commutatività della somma.
A. B = B A; Commutatività del prodotto.
associativo
A + (B + C) = (A + B) + C = A + B + C; Associatività della somma.
A. (B. C) = (A. B). C = A B. C; Associatività del prodotto.
distributivo
A + (B. C) = (A + B). (A + C); La distribuzione della somma rispetto al prodotto.
A. (B + C) = (A. B) + (A + C); La distribuzione del prodotto rispetto alla somma.
Leggi sull'assorbimento
Ci sono molte leggi di assorbimento tra più
A. (A + B) = A
A. (NON A + B) = A. B
NON A (A + B) = NON A. B
(A + B). (A + NOT B) = A
A + A. B = A
A + NON A. B = A + B
NON A + A. B = NON A + B
A. B + A. NON B = A
Il teorema di Morgan
Sono leggi di trasformazione, che gestiscono coppie di variabili che interagiscono tra le operazioni definite dell'algebra booleana (+.).
NOT (A. B) = NON A + NON B
NOT (A + B) = NOT A. NON B
A + B = NOT (NON A + NON B)
A. B = NOT (NON A. NON B)
dualità
Tutti i postulati e i teoremi hanno la facoltà della dualità. Ciò implica che quando si scambiano le variabili e le operazioni, viene verificata la proposizione risultante. Vale a dire, quando si scambia 0 per 1 e AND per OR o viceversa; viene creata un'espressione che sarà anche completamente valida.
Ad esempio, se si prende il postulato
1. 0 = 0
E la dualità è applicata
0 + 1 = 1
Si ottiene un altro postulato perfettamente valido.
Mappa di Karnaugh
La mappa di Karnaugh è un diagramma utilizzato nell'algebra booleana per semplificare le funzioni logiche. Consiste in una disposizione bidimensionale simile alle tavole di verità della logica proposizionale. I dati delle tabelle di verità possono essere catturati direttamente sulla mappa di Karnaugh.
La mappa di Karnaugh può ospitare processi fino a 6 variabili. Per le funzioni con un numero maggiore di variabili, si consiglia l'uso del software per semplificare il processo.
Proposto nel 1953 da Maurice Karnaugh, è stato stabilito come uno strumento fisso nel campo dell'algebra booleana, perché la sua implementazione sincronizza le potenzialità umane con la necessità di semplificare le espressioni booleane, un aspetto chiave nella fluidità dei processi digitali.
Esempi
L'algebra booleana viene utilizzata per ridurre le porte logiche in un circuito, dove la priorità è di portare la complessità o il livello del circuito alla sua espressione minima possibile. Ciò è dovuto al ritardo computazionale che ogni porta assume.
Nel seguente esempio osserveremo la semplificazione di un'espressione logica alla sua espressione minima, usando i teoremi e i postulati dell'algebra booleana.
NON (AB + A + B). NON (A + NON B)
NON [A (B + 1) + B]. NON (A + NON B); Factoring the A con fattore comune.
NON [A (1) + B]. NON (A + NON B); Per il teorema A + 1 = 1.
NON (A + B). NON (A + NON B); dal Teorema A. 1 = A
(NON A. NON B). [NON A. NON (NON B)];
Dal teorema di Morgan NOT (A + B) = NOT A. NON B
(NON A. NON B). (NON A. B); Per teorema doppio negativo NOT (NOT A) = A
NON A. NON B. NON A. B; Raggruppamento algebrico
NON A. NON A. NON B. B; Commutatività del prodotto A. B = B la
NON A. NON B. B; Per il teorema A. A = A
NON A. 0; Per il teorema A. NON A = 0
0; Per il teorema A. 0 = 0
A. B. C + NOT A + A. NON B. C
A. C. (B + NOT B) + NON A; Factoring (A. C) con fattore comune.
A. C. (1) + NON A; Per il Teorema A + NOT A = 1
A. C + NON A; Per regola regola zero e unità 1. A = A
NON A + C ; Dalla legge Morgan A + NOT A. B = A + B
Per questa soluzione, la legge di Morgan dovrebbe essere estesa per definire:
NON (NON A). C + NOT A = NON A + C
Perché NOT (NOT A) = A per involuzione.
Semplifica la funzione logica
NON A. NON B. NON C + NON A. NON B. C + NOT A. NON C alla sua espressione minima
NON A. NON B. (NON C + C) + NON A. NON C; Factoring (NOT A. NOT B) con fattore comune
NON A. NON B. (1) + NON A. NON C; Per il Teorema A + NOT A = 1
(NON A. NON B) + (NON A. NON C); Per regola regola zero e unità 1. A = A
NON A (NON B + NON C); Factoring NOT A con fattore comune
NON A. NON (B. C); Per le leggi di Morgan NOT (A. B) = NOT A + NOT B
NON [A + (B. C)] Per le leggi di Morgan NOT (A. B) = NOT A + NOT B
Qualsiasi delle 4 opzioni in grassetto rappresenta una possibile soluzione per ridurre il livello del circuito
Semplifica la funzione logica alla sua espressione minima
(A) NON B, C + A, NON B, B, D + NON A, NON B). C
(A, NON B, C + A, 0, D + NON, NON B). C; Per il teorema A. NON A = 0
(A, NON B, C + 0 + NON A, NON B). C; Per il teorema A. 0 = 0
(A, NON B, C + NON A, NON B). C; Per il Teorema A + 0 = A
A. NON B. C. C + NOT A. NON B. C; Dalla distributività del prodotto rispetto alla somma
A. NON B. C + NOT A. NON B. C; Per il teorema A. A = A
NON B. C (A + NOT A) ; Factoring (NOT B. C) con fattore comune
NON B. C (1); Per il Teorema A + NOT A = 1
NON B. C; Per regola regola zero e unità 1. A = A
