Booleova algebra

Ovaj članak ili dio članka nije pokriven izvorima. Pomozite Wikipediji navođenjem odgovarajućih knjiga, članaka u časopisima ili internetskih stranica. Sadržaj bez izvora može biti osporen i uklonjen.

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.

Booleovu algebru uveo je George Boole u djelu The Mathematical Analysis of Logic iz 1847. godine,^[1] 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.

Booleova algebra je uređena šestorka ${\displaystyle (B,\,\cdot ,\,+,\,\neg ,\,0,\,1)}$ gdje je ${\displaystyle B}$ neprazan skup, ${\displaystyle \cdot }$ i ${\displaystyle +}$ su dvomjesne operacije na ${\displaystyle B}$, ${\displaystyle \neg }$ je jednomjesna operacija na ${\displaystyle B}$, a ${\displaystyle 0}$ i ${\displaystyle 1}$ su dva posebna elementa skupa ${\displaystyle B}$, koji zadovoljavaju sljedeće aksiome za sve ${\displaystyle a,b,c\in B}$:

Aksiomi Booleove algebre

Aksiom	Množenje (·)	Zbrajanje (+)
Komutativnost	${\displaystyle a\cdot b=b\cdot a}$	${\displaystyle a+b=b+a}$
Distributivnost	${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$	${\displaystyle a+(b\cdot c)=(a+b)\cdot (a+c)}$
Neutralni element	${\displaystyle a\cdot 1=a}$	${\displaystyle a+0=a}$
Komplementarnost	${\displaystyle a\cdot \neg a=0}$	${\displaystyle a+\neg a=1}$

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

Najmanji netrivijalni primjer Booleove algebre je dvočlana Booleova algebra ${\displaystyle B=\{0,1\}}$, koja se koristi u digitalnoj logici i propozicijskoj logici.

Njezine su glavne operacijske radnje konjunkcija, disjunkcija i negacija.

Logička operacija I (konjunkcija)

[uredi | uredi kôd]

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)

[uredi | uredi kôd]

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)

[uredi | uredi kôd]

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

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
${\displaystyle \neg \neg A=A}$		involutivnost (zakon dvostruke negacije)
${\displaystyle A\cdot 0=0}$	${\displaystyle A+0=A}$	logičko množenje i zbrajanje s nulom
${\displaystyle A\cdot A=A}$	${\displaystyle A+A=A}$	idempotentnost
${\displaystyle A\cdot 1=A}$	${\displaystyle A+1=1}$	logičko množenje i zbrajanje s jedinicom
${\displaystyle A\cdot \neg A=0}$	${\displaystyle A+\neg A=1}$	komplementarnost
${\displaystyle A\cdot (A+B)=A}$	${\displaystyle A+A\cdot B=A}$	apsorpcija
${\displaystyle A\cdot (\neg A+B)=A\cdot B}$	${\displaystyle A+\neg A\cdot B=A+B}$
${\displaystyle \neg (A\cdot B)=\neg A+\neg B}$	${\displaystyle \neg (A+B)=\neg A\cdot \neg B}$	De Morganovo pravilo
${\displaystyle A\cdot B=B\cdot A}$	${\displaystyle A+B=B+A}$	komutativnost
${\displaystyle A\cdot (B+C)=A\cdot B+A\cdot C}$	${\displaystyle A+(B\cdot C)=(A+B)\cdot (A+C)}$	distributivnost
${\displaystyle (A\cdot B)\cdot C=A\cdot (B\cdot C)}$	${\displaystyle (A+B)+C=A+(B+C)}$	asocijativnost
${\displaystyle (A+B)\cdot (C+D)=A\cdot C+A\cdot D+B\cdot C+B\cdot D}$

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 ${\displaystyle A\cdot (A+B)=A}$ jest ${\displaystyle A+(A\cdot B)=A}$, što je također istinito.

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

• Boole, George. 1854. An Investigation of the Laws of Thought. Walton and Maberly. London.
• Givant, Steven; Halmos, Paul. 2009. Introduction to Boolean Algebras. Springer. New York. ISBN 978-0-387-40293-2
• Shannon, Claude E. 1938. A Symbolic Analysis of Relay and Switching Circuits. MIT. Cambridge.
• Mendelson, Elliott. 2009. Introduction to Mathematical Logic. CRC Press. ISBN 978-1-58488-876-5

• Stanford Encyclopedia of Philosophy: The Mathematics of Boolean Algebra eng. {{{1}}}
• MathWorld: Boolean Algebra eng. {{{1}}}

• George Boole
• Logički sklop
• Propozicijska logika
• De Morganovi zakoni
• Digitalna logika
• Karnaughova mapa

1. ↑ Boole, George. 28. srpnja 2011. The Mathematical Analysis of Logic - Being an Essay Towards a Calculus of Deductive Reasoning