Storia dell'algebra booleana, teoremi e postulati, esempi

Lui Algebra booleana o L'algebra di Boole è la notazione algebrica utilizzata per il trattamento delle variabili binarie. Copre gli studi di qualsiasi variabile che ha solo 2 risultati possibili, complementari ed esclusivi tra loro. Ad esempio, le variabili la cui unica possibilità è vera o falsa, corretta o errata, accesi o spenti sono la base dello studio dell'algebra booleana.

L'algebra booleana costituisce la base dell'elettronica digitale, che lo rende abbastanza presente nella contemporaneità. È governato dal concetto di porte logiche, in cui le operazioni note nell'algebra tradizionale sono notevolmente colpite.

Fonte: Pexels.com

[TOC]

Storia

L'algebra booleana fu introdotta nel 1854 dal matematico inglese George Boole (1815-1864), che era uno studioso auto -insegnato dell'epoca. La sua preoccupazione è nata da una disputa esistente tra Augusto di Morgan e William Hamilton, sui parametri che definiscono questo sistema logico.

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

L'intenzione di George Boole era di definire, attraverso le proprietà dell'algebra, le espressioni della logica proposizionale necessarie per affrontare le variabili binarie.

Nel 1854 le sezioni più significative dell'algebra booleana sono pubblicate nel libro "Un'indagine sulle leggi del pensiero su cui sono basate 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 è saltato alla fama a causa dell'immediata attenzione che aveva dalla comunità matematica dell'epoca.

Nel 1948 Claude Shannon lo applicò nella progettazione di circuiti di commutazione elettrica biestabile. Questo è servito da 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 al falso e al vero. Le operazioni fondamentali nell'algebra booleana sono 3:

- E operazione di congiunzione. Rappresentato da un punto ( . ). Sinonimo del prodotto.

- O o operazione di disgiunzione. Rappresentato da una croce ( +) .Sinonimo della somma.

- Nessuna operazione o denozione. Rappresentato dal prefisso non (non a). È anche noto come complemento.

Se in un set sono definite 2 leggi di composizione interna indicate come prodotto e somma ( .  + ), si dice che l'elenco (a . + ) È un'algebra booleana se e solo se detto elenco soddisfa la condizione di essere un reticolo distributivo.

Può servirti: numeri razionali: proprietà, esempi e operazioni

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

. è 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 il set A devono essere binari, avendo così valori di Universo o vuoto.

Applicazioni

Il suo più grande scenario di applicazione è il ramo digitale, dove serve a strutturare i circuiti che costituiscono le operazioni logiche coinvolte. L'arte dei circuiti semplicità per ottimizzare i processi, è il risultato della corretta applicazione e pratica dell'algebra booleana.

Dall'elaborazione delle schede elettriche, attraverso la trasmissione dei dati, fino a raggiungere la programmazione in linguaggi diversi, possiamo spesso trovare l'algebra di Boole in tutti i tipi di applicazioni digitali.

Le variabili booleane sono molto comuni nella struttura di programmazione. A seconda del linguaggio di programmazione utilizzato, ci saranno operazioni strutturali del codice che usano queste variabili. Il condizionale e gli argomenti di ciascuna lingua ammettono le variabili booleane per definire i processi.

Postula

Ci sono teoremi che regolano le leggi sulla logica strutturale dell'algebra booleana. Allo stesso modo, sono postulati per conoscere i possibili risultati in diverse combinazioni di variabili binarie, secondo l'operazione effettuata.

Somma (+)

L'operatore O 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 E 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 (no)

L'operatore Non Il cui elemento logico è il complemento (x) 'è definito per le variabili binarie come segue:

Non 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 universi nell'algebra booleana (1 + 1) non può produrre il risultato convenzionale di 2, poiché non appartiene agli elementi del complesso binario.

Teoremi

Regola e unità zero

Viene definito qualsiasi semplice operazione che coinvolga un elemento con variabili binarie:

0 + a = a

1 + a = 1

0 . A = 0

1 . A = a

Equal Powers o Idemploynce

Le operazioni tra variabili uguali sono definite come:

Può servirti: congruenza: personaggi congruenti, criteri, esempi, esercizi

A + a = a

A . A = a

Complementazione

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

A + not a = 1

A . Non a = 0

Involuzione o doppia negazione

Tutta la doppia negazione sarà considerata la variabile naturale.

Non (non a) = a

Commutativo

A + b = b + a; Estate della somma.

A . B = b . A ; Commutività del prodotto.

Associativo

A + (B + C) = (A + B) + C = A + B + C; Somma associazione.

A . (B . C) = (a . B) . C = a . B . C; Associazione del prodotto.

Distributivo

A + (B . C) = (a + b) . (A + C); Distribuire la somma rispetto al prodotto.

A . (B + C) = (a . B) + (a + c); Distributività del prodotto rispetto alla somma.

Leggi di assorbimento

Ci sono molte leggi di assorbimento tra più riferimenti, alcuni dei più noti sono:

A . (A + b) = a

A . (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

A . B + A . Non b = a

Il teorema di Morgan

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

NOTA . B) = non a + non b

Non (a +b) = non a . Non B

A + b = not (non a + non b)

A . B = no (non a . Non B)

Dualità

Tutti i postulati e i teoremi hanno il potere della dualità. Ciò implica che scambiando le variabili e le operazioni, viene verificata la proposta risultante. Cioè, quando si scambia 0 per 1 e e e o viceversa; Viene creata un'espressione che sarà anche completamente valida.

Ad esempio, se prendi il postulato

1 . 0 = 0

E la dualità viene applicata

0 + 1 = 1

Si ottiene un altro postulato perfettamente valido.

Karnaugh Map

La mappa di Karnaugh è un diagramma utilizzato nell'algebra booleana per semplificare le funzioni logiche. È costituito da una disposizione bidimensionale simile alle tabelle di verità della logica proposizionale. I dati delle tabelle reali possono essere incorporati 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, fu istituito come strumento fisso nel campo di Boole.

Esempi

L'algebra booleana serve a ridurre le porte logiche in un circuito, dove la priorità è quella di portare la complessità o il livello del circuito alla sua espressione minima possibile. Ciò è dovuto al ritardo computazionale che ogni porta suppone.

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

NOT (AB + A + B) . NOT (a + non b)

NOT [A (B + 1) + B] . Non (a + non b); Factoring the a with Common Factor.

Può servirti: calcolo degli approcci usando differenziali

Non [a (1) + b] . Non (a + non b); Per teorema a + 1 = 1.

NON (A + B) . Non (a + non b); Di Teorema a . 1 = a

( NOTA . Non B) . [ NOTA . Non (non b)];

Per teorema di Morgan non (a + b) = not a . Non B

( NOTA . Non B) .  ( NOTA . B); Dal doppio teorema di negazione non (non a) = a

NOTA . Non B . NOTA . B; Gruppo algebrico.

NOTA . NOTA . Non B . B; Commutività del prodotto a . B = b . A

NOTA . Non B . B; Di Teorema a . A = a

NOTA . 0; Di Teorema a . Non a = 0

0; Di Teorema a . 0 = 0

A . B . C + non a + a . Non B . C

A . C . (B + non b) + non a; Fattorizzazione (a . C) con fattore comune.

A . C . (1) + non a; Per teorema a + non a = 1

A . C + non a; Per zero regola teorema e unità 1 . A = a

Non a + c ; Per legge da 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 = not a + c

Perché non (non a) = a per involuzione.

Semplificare la funzione logica

NOTA . Non B . Non c + non a . Non B . C + non a . Non c fino alla sua espressione minima

NOTA . Non B . (Non c + c) + non a . Non c; Fattorizzazione (non a . Non b) con fattore comune

NOTA . Non B . (1) + non a . Non c; Per teorema a + non a = 1

(NOTA . Non b) + (non a . Non c);  Per zero regola teorema e unità 1 . A = a

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

NOTA . Non B . C); Dalle leggi di Morgan no (a . B) = non a + non b

Non [a + (b . C)] Dalle leggi di Morgan no (a . B) = non a + non b

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

Semplificare la funzione logica fino 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 a . Non B) . C; Di Teorema a . Non a = 0

( A . Non B . C + 0 + non a . Non B) . C; Di Teorema a . 0 = 0

( A . Non B . C + non a . Non B) . C; Di teorema a + 0 = a

A . Non B . C . C + non a . Non B . C; Dalla distribuzione del prodotto rispetto alla somma

A . Non B . C + non a . Non B . C; Di Teorema a . A = a

Non B . C (a + non a) ; Fattorizzazione (non b . C) con fattore comune

Non B . C (1); Per teorema a + non a = 1

Non B . C; Per zero regola teorema e unità 1 . A = a

Riferimenti

1. Algebra booleana e le sue applicazioni J. Eldon Whitesett. Azienda editoriale continentale, 1980.
2. Matematica e ingegneria in informatica. Christopher J. Van Wyk. Institute for Computer Sciences and Technology. National Bureau of Standards. Washington, d. C. 20234
3. Matematica per l'informatica. Eric Lehman. Google inc.
   F Thomson Leighton Dipartimento di matematica e il laboratorio di informatica e AI, Massachussetts Institute of Technology; Akamai Technologies.
4. Elementi di analisi astratta. Mícheál O'Searcoid PhD. Dipartimento di Matematica. University College Dublino, Beldfield, Dublind.
5.  Introduzione alla logica e alla metodologia delle scienze deduttive. Alfred Tarski, New York Oxford. la stampa dell'università di Oxford.