ALGEBRA BOOLEANA: STORIA, TEOREMI E POSTULATI, ESEMPI - MATEMATICA - 2024

L' algebra booleana o algebra booleana è la notazione algebrica utilizzata per il trattamento delle variabili binarie. Copre gli studi di qualsiasi variabile che abbia solo 2 possibili risultati, complementari e mutuamente esclusivi. Ad esempio, le variabili la cui unica possibilità è vero o falso, corretto o errato, acceso o spento sono la base dello studio dell'algebra booleana.

L'algebra booleana costituisce la base dell'elettronica digitale, il che la rende abbastanza presente oggi. È governato dal concetto di porte logiche, dove le operazioni note dell'algebra tradizionale sono notevolmente influenzate.

Fonte: pexels.com

Storia

L'algebra booleana fu introdotta nel 1854 dal matematico inglese George Boole (1815-1864), uno studioso autodidatta dell'epoca. La sua preoccupazione nasceva da una disputa esistente tra Augustus De Morgan e William Hamilton, sui parametri che definiscono questo sistema logico.

George Boole ha sostenuto che la definizione dei valori numerici 0 e 1 corrisponde, nel campo della logica, all'interpretazione Niente e Universo rispettivamente.

L'intenzione di George Boole era quella di definire, attraverso le proprietà dell'algebra, le espressioni di logica proposizionale necessarie per trattare variabili di tipo binario.

Nel 1854 le sezioni più significative di algebra booleana furono 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 stato riassunto in seguito come "Le leggi del pensiero" ("Le leggi del pensiero"). Il titolo divenne famoso per l'immediata attenzione che ricevette dalla comunità matematica dell'epoca.

Nel 1948 Claude Shannon lo applicò alla progettazione di circuiti elettrici di commutazione bistabili. Questo è servito 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 in algebra booleana sono 3:

- Operazione AND o congiunzione. Rappresentato da un punto (.). Sinonimo del prodotto.

- Operazione OR o disgiunzione. Rappresentato da una croce (+) Sinonimo della somma.

- NON operazione o negazione. Rappresentato dal prefisso NOT (NOT A). È anche noto come complemento.

Se in un insieme A 2 le leggi della composizione interna sono definite denotate come prodotto e somma (. +), La tripla (A. +) Si dice che sia un'algebra booleana se e solo se detta tripla soddisfa la condizione di essere un reticolo distributiva.

Per definire un reticolo distributivo, le condizioni di distribuzione devono essere soddisfatte tra le operazioni date:

. è 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, avendo quindi valori universali o nulli.

applicazioni

Il suo principale scenario applicativo è il ramo digitale, dove serve a strutturare i circuiti che compongono 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.

Dall'elaborazione dei quadri elettrici, passando per la trasmissione dei dati, fino ad arrivare alla programmazione in diversi linguaggi, 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 strutturali nel codice che utilizzano queste variabili. I condizionali e gli argomenti di ogni lingua ammettono variabili booleane per definire i processi.

postulati

Ci sono teoremi che governano le leggi logiche strutturali dell'algebra booleana. Allo stesso modo, esistono postulati per conoscere i possibili risultati in diverse combinazioni di variabili binarie, a seconda dell'operazione svolta.

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

uno . 0 = 0

uno . 1 = 1

Opposto (NON)

L'operatore NOT il cui elemento logico è il complemento (X) 'è definito per le variabili binarie come segue:

NON 0 = 1

NON 1 = 0

Molti dei postulati differiscono dalle loro controparti nell'algebra convenzionale. Ciò è dovuto al dominio delle variabili. Ad esempio, l'aggiunta di elementi dell'universo in algebra booleana (1 + 1) non può produrre il risultato convenzionale di 2, perché non appartiene agli elementi dell'insieme binario.

teoremi

Regola dello zero e unità

Ogni semplice operazione che coinvolge un elemento con le variabili binarie, viene definita:

0 + A = A

1 + A = 1

0. A = 0

uno . A = A

Pari poteri o idempotenza

Le operazioni tra variabili uguali sono definite come:

A + A = A

PER . A = A

complementazione

Qualsiasi operazione tra una variabile e il suo complemento è definita come:

A + NON A = 1

PER . NON A = 0

Involuzione o doppia negazione

Ogni doppia negazione sarà considerata come variabile naturale.

NOT (NON A) = A

Commutativo

A + B = B + A; Commutatività della somma.

PER . B = B. PER ; Commutatività del prodotto.

Associativo

A + (B + C) = (A + B) + C = A + B + C; Associatività della somma.

PER . (B. C) = (A. B). C = A. B. C; Associatività del prodotto.

distributivo

A + (B. C) = (A + B). (A + C); Distributività della somma rispetto al prodotto.

PER . (B + C) = (A. B) + (A + C); Distribuibilità del prodotto rispetto alla somma.

Leggi di assorbimento

Esistono molte leggi di assorbimento tra più riferimenti, alcune delle più note sono:

PER . (A + B) = A

PER . (NON A + B) = A. B

NON A (A + B) = NON A. B

(A + B). (A + NON B) = A

A + A. B = A

A + NON A. B = A + B

NON A + A. B = NON A + B

PER . B + A. NON B = A

Teorema di Morgan

Sono leggi di trasformazione, che gestiscono coppie di variabili che interagiscono tra le operazioni definite dell'algebra booleana (+.).

NON (A. B) = NON A + NON B

NON (A + B) = NON A. NON B

A + B = NON (NON A + NON B)

PER . B = NON (NON A. NON B)

dualità

Tutti i postulati e i teoremi possiedono la facoltà della dualità. Ciò implica che scambiando le variabili e le operazioni si verifica la proposizione risultante. Cioè, quando si scambiano 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

uno . 0 = 0

E viene applicata la dualità

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 tabelle di verità della logica proposizionale. I dati delle tabelle di verità possono essere acquisiti 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 di software per semplificare il processo.

Proposta nel 1953 da Maurice Karnaugh, si è affermata come strumento fisso nel campo dell'algebra booleana, perché la sua implementazione sincronizza il potenziale umano con la necessità di semplificare le espressioni booleane, aspetto fondamentale nella fluidità dei processi digitali.

Esempi

L'algebra booleana viene utilizzata per ridurre le porte logiche in un circuito, dove la priorità è portare la complessità o il livello del circuito alla sua espressione più bassa possibile. Ciò è dovuto al ritardo computazionale supposto da ogni porta.

Nell'esempio seguente osserveremo la semplificazione di un'espressione logica alla sua minima espressione, utilizzando i teoremi e i postulati dell'algebra booleana.

NON (AB + A + B). NON (A + NON B)

NON. NON (A + NON B); Fattorizzare A con un fattore comune.

NON. NON (A + NON B); Dal teorema A + 1 = 1.

NON (A + B). NON (A + NON B); dal teorema A. 1 = A

(NON A. NON B). ;

Per il teorema di Morgan NOT (A + B) = NOT A. NON B

(NON A. NON B). (NON A. B); Per teorema della doppia negazione 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. PER

NON A. NON B. B; Dal teorema A. A = A

NON A. 0; Dal teorema A. NON A = 0

0; Dal teorema A. 0 = 0

PER . B. C + NON A + A. NON B. C

PER . C. (B + NON B) + NON A; Factoring (A. C) con un fattore comune.

PER . C. (1) + NON A; Dal teorema A + NON A = 1

PER . C + NON A; Per regola del teorema zero e unità 1. A = A

NON A + C ; Per legge di Morgan A + NON A. B = A + B

Per questa soluzione, la legge di Morgan deve essere estesa per definire:

NON (NON A). C + NON 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 + NON A. NON C fino alla sua espressione minima

NON A. NON B. (NON C + C) + NON A. NON C; Factoring (NON A. NON B) con fattore comune

NON A. NON B. (1) + NON A. NON C; Dal teorema A + NON A = 1

(NON A. NON B) + (NON A. NON C); Per regola del teorema zero e unità 1. A = A

NON A (NON B + NON C); Factoring NON A con un fattore comune

NON A. NON (B. C); Per le leggi di Morgan NON (A. B) = NON A + NON B

NON Per le leggi di Morgan NON (A. B) = NON A + NON B

Una qualsiasi delle 4 opzioni in grassetto rappresenta una possibile soluzione per ridurre il livello del circuito

Semplifica la funzione logica nella sua forma più semplice

(A. NON B. C + A. NON B. B. D + NON A. NON B). C

(A. NON B. C + A. 0. D + NON A. NON B). C; Dal teorema A. NON A = 0

(A. NON B. C + 0 + NON A. NON B). C; Dal teorema A. 0 = 0

(A. NON B. C + NON A. NON B). C; Per teorema A + 0 = A

PER . NON B. C. C + NON A. NON B. C; Per distributività del prodotto rispetto alla somma

PER . NON B. C + NON A. NON B. C; Dal teorema A. A = A

NON B. C (A + NON A) ; Factoring (NON B. C) con fattore comune

NON B. C (1); Dal teorema A + NON A = 1

NON B. C; Per regola del teorema zero e unità 1. A = A

Riferimenti

1. Algebra booleana e sue applicazioni J. Eldon Whitesitt. Continental Publishing Company, 1980.
2. Matematica e Ingegneria in Informatica. Christopher J. Van Wyk. Istituto di informatica e tecnologia. National Bureau of Standards. Washington, DC 20234
3. Matematica per l'informatica. Eric Lehman. Google Inc.
   F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory, Massachussetts Institute of Technology; Akamai Technologies.
4. Elementi di analisi astratta. Mícheál O'Searcoid PhD. Dipartimento di matematica. College universitario di Dublino, Beldfield, Dublino.
5. Introduzione alla logica e alla metodologia delle scienze deduttive. Alfred Tarski, New York Oxford. La stampa dell'università di Oxford.