mini|desno|Primjeri upotrebe Booleove algebre Booleova algebra dio je matematičke logike – algebarska struktura koja sažima osnovu operacija I, ILI i NE kao i skup teorijskih operacija kao što su unija, presjek i komplement. Booleova algebra je dobila naziv po začetniku Georgeu Booleu, britanskome matematičaru iz 19. stoljeća. Booleova algebra je, osim kao dio apstraktne algebre, izuzetno utjecajna kao matematički temelj računarskih znanosti.

Povijest Booleovu algebru uveo je George Boole u djelu The Mathematical Analysis of Logic iz 1847. godine, a razradio je u knjizi An Investigation of the Laws of Thought iz 1854. godine. Boole je htio matematički formalizirati logičko zaključivanje koristeći algebarski pristup.

Krajem 19. stoljeća Charles Sanders Peirce i Ernst Schröder proširili su Booleov sustav i stvorili algebru relacija. Presudni korak prema primjeni u tehnici napravio je Claude Shannon u svom magistarskom radu iz 1937. godine, u kojemu je pokazao da se Booleova algebra može primijeniti na analizu i projektiranje električnih sklopova. Time je Booleova algebra postala temelj digitalne elektronike i računarstva.

Formalna definicija Booleova algebra je uređena šestorka gdje je neprazan skup, i su dvomjesne operacije na , je jednomjesna operacija na , a i su dva posebna elementa skupa , koji zadovoljavaju sljedeće aksiome za sve :

+ Aksiomi Booleove algebre Aksiom Množenje (·) Zbrajanje (+) Komutativnost Distributivnost Neutralni element Komplementarnost

Iz ovih aksioma mogu se izvesti svi ostali teoremi Booleove algebre.

Najmanji netrivijalni primjer Booleove algebre je dvočlana Booleova algebra , koja se koristi u digitalnoj logici i propozicijskoj logici.

Operacije Njezine su glavne operacijske radnje konjunkcija, disjunkcija i negacija.

Logička operacija I (konjunkcija) mini|Tablica istinitosti i oznaka za konjunkciju Konjunkcija (I, AND, logičko množenje) uključuje dvije logičke varijable (izjave) i istinita je samo ako su obje logičke izjave istinite.

Operacija I predočuje se simbolima ∩, ∧, & ili ·. Najčešće se koristi simbol za množenje ·.

Tablica istinitosti konjunkcije: A B A · B 0 0 0 0 1 0 1 0 0 1 1 1

Logička operacija ILI (disjunkcija) mini|Tablica istinitosti i oznaka za disjunkciju. Disjunkcija (ILI, OR, logičko zbrajanje) uključuje dvije logičke varijable (izjave) i lažna je samo ako su obje logičke izjave lažne.

Operacija ILI predočuje se simbolima ∪, ∨ ili +. Najčešće se koristi simbol za zbrajanje +.

Tablica istinitosti disjunkcije: A B A + B 0 0 0 0 1 1 1 0 1 1 1 1

Logička operacija NE (negacija) mini|Tablica istinitosti i oznaka za negaciju. Negacija (NE, NOT) uključuje jednu logičku varijablu (izjavu) i istinita je ako je početna izjava neistinita.

Operacija NE predočuje se simbolom ¬.

Tablica istinitosti negacije: A ¬A 0 1 1 0

Ostale izvedene operacije Iz temeljnih triju operacija izvode se i složenije operacije koje se često koriste u praksi:

NAND (NE-I): – jedina dovoljna operacija za izgradnju svih ostalih logičkih sklopova. NOR (NE-ILI): – također funkcionalno potpuna operacija. XOR (isključivo ILI): – istinita je ako se izjave razlikuju. XNOR (ekvivalencija): – istinita je ako su izjave jednake.

Teoremi Booleove algebre Teoremi Booleove algebre omogućuju pojednostavljivanje složenih logičkih izraza. Teoremi su dokazive tvrdnje; svaki od njih može se dokazati izrađivanjem tablice istinitosti za lijevu i desnu stranu jednakosti, ili izvođenjem iz aksioma.

+ Teoremi Booleove algebre Naziv involutivnost (zakon dvostruke negacije) logičko množenje i zbrajanje s nulom idempotentnost logičko množenje i zbrajanje s jedinicom komplementarnost apsorpcija De Morganovo pravilo komutativnost distributivnost asocijativnost

Načelo dualnosti Svaki teorem Booleove algebre ima svoj dual, koji se dobiva zamjenom operacije · s operacijom +, i zamjenom konstanti 0 i 1. Ako je neka tvrdnja valjana u Boolovoj algebri, onda je valjana i njezina dualna tvrdnja. Na primjer, dual apsorpcijskog zakona jest , što je također istinito.

Primjena Booleova algebra ima široku primjenu u različitim granama znanosti i tehnike:

Digitalna logika i računarstvo Najvažnija primjena Booleove algebre je u digitalnoj logici i računarstvu. Logički sklopovi kao što su vrata I, vrata ILI i vrata NE izravno odgovaraju operacijama Booleove algebre. Projektanti integriranih sklopova koriste Booleovu algebru za minimizaciju i optimizaciju logičkih funkcija, čime se smanjuje broj potrebnih sklopova i troši manje energije.

Teorija skupova Booleova algebra opisuje i operacije nad skupovima: unija skupova odgovara disjunkciji, presjek skupova odgovara konjunkciji, a komplement skupu odgovara negaciji. Algebra skupova nad partitivnim skupom nekog skupa tvori Booleovu algebru.

Pretraživanje informacija U bazama podataka i tražilicama Booleova algebra koristi se za oblikovanje upita. Operatori AND, OR i NOT omogućuju precizno sužavanje ili proširivanje skupa rezultata pretrage.

Propozicijska logika Propozicijska logika je izravno modelirana Booleovom algebrom. Logičke formule i njihova tablica istinitosti temelj su formalnog dokazivanja i automatskog rezoniranja.

Literatura

Vanjske poveznice Stanford Encyclopedia of Philosophy: The Mathematics of Boolean Algebra MathWorld: Boolean Algebra

Vidi još George Boole Logički sklop Propozicijska logika De Morganovi zakoni Digitalna logika Karnaughova mapa

Kategorija:Matematička logika Kategorija:Apstraktna algebra Kategorija:Arhitektura računala