Booleova algebra

"Prije nego što krenemo, malo povijesti." rekao je Ivan.

Booleovu algebru u 19. stoljeću je definirao engleski matematičar George Boole, a smatra se temeljem informatike. Osnovni element Booleove algebre je logički sud (izjava) koji se može nedvosmisleno označiti kao istinit ili neistinit.

Primjer:

Zagreb je glavni grad Republike Hrvatske.	ISTINA
Zemlja je ravna ploča.	NEISTINA

Crno-bijela ilustracija Georgea Boolea. — George Boole

Kako bi izjave bile primjerene za korištenje u Booleovoj algebri, trebaju biti jasne i nedvosmislene. Što misliš, koje rečenice od ponuđenih možemo nazvati izjavama?

Ivana je najljepša djevojka na svijetu.

Ne možemo sa sigurnošću potvrditi.

Žirafa nema vrat.

Neistinita izjava.

Slon ne može letjeti.

Istinita izjava.

Petar možda ne voli jesti juhu.

Ne možemo sa sigurnošću potvrditi.

null

Zanimljivost

Booleova algebra temelj je za osnovne logičke sklopove (I, ILI i NE) pomoću kojih se grade svi složeni sklopovi unutar računala, primjerice sklop za zbrajanje binarnih brojeva unutar aritmetičko-logičke jedinice.

Radi jednostavnosti pisanja, izjave Booleove algebre označavamo varijablama, odnosno slovnim oznakama. Primjerice izjavu "Danas pada kiša." možemo označiti s A, dok izjavu "Čokolada je slatka." možemo označiti B i sl. Već smo naglasili da svaka izjava ima binarnu vrijednost, tj. da može biti istinita ili neistinita. Istinu označavamo s $1,$ dok neistinu označavamo s $0 .$

Odredi istinitost sljedećih izjava:

Kemijski simbol za kisik je N.

Istina

Neistina

null

Kemijski simbol za kisik je O.

Istina

Neistina

null

Osnovne logičke operacije

"OK, to mi je jasno." rekao je Petar. "A što ako imam više izjava? Kako ih povezujem?" upitao je Ivana. "Pa to je bar logično!" odgovorio mu je.

Logičke izjave možemo povezati logičkim operatorima te time stvoriti logičke izraze. Osnovne logičke operacije, s obzirom na prioritet izvođenja, su negacija, konjunkcija i disjunkcija.

Petar se namučio prije nego li je ispravno izgovorio posljednje dvije osnovne logičke operacije te ga je sada sve to skupa još više zainteresiralo.

Negacija

Negacija (logička operacija NE) je operacija Booleove algebre koja ima najviši prioritet. Rezultat negacije uvijek je suprotna vrijednost, a označava se s ¬ u logici, $\bar{}$ (crtom iznad izjave ili izraza) u matematici te riječima NOT ili znakom ! u programskim jezicima.

Primjerice, ako izjava $A$ glasi: "Rijeka je grad na moru.", tada izjava $\bar{A}$ glasi: "Rijeka nije grad na moru." Ako je ta izjava istinita, onda će njena negacija biti neistinita i obratno.

Istinitost logičkih izraza prikazujemo tablicom istinitosti. Tablicu istinitosti gradimo tako da u prvi red upišemo varijablu te u stupcu ispod sve moguće istinitosne vrijednosti. U slučaju samo jedne varijable postoje dvije $(2^{1} = 2)$ moguće istinitosne vrijednosti: $0$ i $1 .$

Tablica istinitosti za logičku operaciju negacije:

$A$	$\bar{A}$
$0$	$1$
$1$	$0$

Što misliš, je li negacija izjave: "Kemijski simbol za kisik je N." istinita?

Istinita je.

Neistinita je.

null

"Čekaj malo!" rekao je Petar. "Malo prije smo u tablici istinitosti stavili da neka izjava može istinita i neistinita, a tu tvrdimo da je negacija rečenice istinita. Zašto onda pišemo u tablici slučaj u kojem je neistinita?" Ivan se nasmijao i odogovorio mu: "Pa to je bar logično! U svijetu logike nisu bitne stvarne istinitosne vrijednosti izjava. U tom svijetu strogih pravila matematičke logike mi moramo ispitati sve istinitosne mogućnosti!" nadovezao se Ivan. "Pa to uopće nije logično!" revoltirano je zaključio Petar.

Konjunkcija

Konjunkcija (logička operacija I) je logička operacija koja djeluje na dvije izjave, a istinita je samo ako su obje izjave istinite. Simbol konjunkcije u logici je $\land,$ u informatici $\cdot,$ a u programiranju AND ili &&. Prioritetom slijedi iza negacije.

Primjerice, ako je $A =$ "SSD je poluvodička memorija", a $B =$ "CD je optička memorija.", onda je $A \cdot B =$ "SSD je poluvodička memorija i CD je optička memorija."

Budući da konjunkcija djeluje na dvije izjave, postoje četiri $(2^{2} = 4)$ moguće kombinacije istinitosti. Mogu biti obje izjave istinite, obje izjave neistinite ili može prva izjava biti istinita, a druga neistinita i obratno.

Tablica istinitosti za logičku operaciju konjunkcije:

$A$	$B$	$A \cdot B$
$0$	$0$	$0$
$0$	$1$	$0$
$1$	$0$	$0$
$1$	$1$	$1$

Iz tablice istinitosti vidimo da je konjunkcija istinita samo u posljednjem redu, odnosno u slučaju kad su obje izjave istinite.

Disjunkcija

Disjunkcija (logička operacija ILI) operacija je najnižeg prioriteta koja djeluje na dvije izjave, a istinita je kada je bar jedna izjava istinita. U logici je njen simbol $\lor,$ u informatici $+,$ a u programskim jezicima OR odnosno ||.

Primjerice, ako je $A =$ "Danas je utorak.", a $B =$ "Gitara ima šest žica.", onda je $A + B =$ "Danas je utorak ili gitara ima šest žica."

U tablici istinitosti vidimo da je disjunkcija istinita u svim redovima osim u prvom, gdje su obje izjave neistinite.

$A$	$B$	$A + B$
$0$	$0$	$0$
$0$	$1$	$1$
$1$	$0$	$1$
$1$	$1$	$1$

Na redoslijed operacija može se utjecati pomoću zagrada, kao u aritmetičkim zadacima u matematici.

Poredaj operacije Booleove algebre prema prioritetu izvođenja, počevši od one s najvišim prioritetom.

Negacija
Disjunkcija
Konjunkcija

null

Logički izrazi

Putem tablice istinitosti provjerimo za koje vrijednosti $A,$ $B$ i $C$ je izraz $\bar{A + B} \cdot \bar{C}$ istinit.

Primijećujemo da u slučaju tri varijable $(A),$ $B$ i $C$ ) tablica istinitosti ima osam $(2^{3} = 8)$ redova, tj. osam mogućih kombinacija istinitosti. Koliko će tablica imati redova jest $n$ -ta potencija broja dva, gdje $n$ predstavlja broj varijabli.

Kako glasi logički izraz opisan formulom $\bar{A \cdot B}$ ako izjava $A$ glasi: "Kiša pada.", a izjava $B :$ "Ulice su suhe"?

Kiša ne pada i ulice nisu suhe.

Ovaj izraz bismo zapisali kao NE A I NE B, što nije isto kao NE (A I B).

Nije slučaj da kiša pada i da su ulice suhe.

Točno. Negacija se odnosi na cijelu rečenicu.

null

Koliko redova će imati tablica istinitosti za izraz $A \cdot B + \bar{C} \cdot D ?$

2

Koliko različitih varijabli je u izrazu? Potenciraj broj dva s tim brojem!

4

Koliko različitih varijabli je u izrazu? Potenciraj broj dva s tim brojem!

8

Koliko različitih varijabli je u izrazu? Potenciraj broj dva s tim brojem!

16

Tako je. Četvrta potencija broja dva, budući su četiri varijable.

32

Koliko različitih varijabli je u izrazu? Potenciraj broj dva s tim brojem!

null

Primjer 1.

Nakon kratkog, ali jezgrovitog predavanja, Petar je dobio zadatak. "Napiši tablicu istinitosti za sljedeći logički izraz: 'Autobus ima četiri kotača te škola ne počinje u rujnu ili šparoge rastu uz more!'" rekao mu je Ivan. "Pa to je bar logično!" rekao je Petar u stilu svog brata. "Prvo moramo zapisati od kojih varijabli se sastoji izraz." prisjećao se naučenog.

Autobus ima četiri kotača.
$A$

Škola počinje u rujnu.
$B$

Šparoge rastu uz more.
$C$

Zatim je koristeći operatore Booleove algebre napravio logički izraz $(A \cdot \bar{B}) + C .$ Ivan mu je još predložio da makne zagrade jer mu one s obzirom na prioritete logičkim operacija u izrazu ne trebaju. Tako je dobio konačni izraz $A \cdot \bar{B} + C,$ za kojeg je napravio i tablicu istinitosti.

$A$ $B$ $C$ $\bar{B}$
$A· \bar{B}$
$A· \bar{B} +C$

$0$ $0$ $0$ $1$ $0$ $0$

$0$ $0$ $1$ $1$ $0$ $1$

$0$ $1$ $0$ $0$ $0$ $0$

$0$ $1$ $1$ $0$ $0$ $1$

$1$ $0$ $0$ $1$ $1$ $1$

$1$ $0$ $1$ $1$ $1$ $1$

$1$ $1$ $0$ $0$ $0$ $0$

$1$ $1$ $1$ $0$ $0$ $1$

$A$	$B$	$C$	$\bar{B}$	$A· \bar{B}$	$A· \bar{B} +C$
$0$	$0$	$0$	$1$	$0$	$0$
$0$	$0$	$1$	$1$	$0$	$1$
$0$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$	$1$	$1$
$1$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$0$	$1$

Iz tablice se da pročitati da je izraz istinit samo u prvom, drugom te petom i šestom redu gdje su:

$A$ i $B$ neistiniti, a $C$ istinit
$A$ neistinit, a $B$ i $C$ istiniti
$A$ istinit, a $B$ i $C$ neistiniti
$A$ i $C$ istiniti, a $B$ neistinit
$A$ , $B$ i $C$ istiniti

Vrijednosti varijabli $A$ , $B$ i $C$ još nazivamo i uređene trojke, a u primjeru prijestupnih godina, istinitost daju četiri uređene trojke:

$(0, 0, 1)$
$(0, 1, 1)$
$(1, 0, 0)$
$(1, 0, 1)$
$(1, 1, 1)$

Ako bismo umjesto imena varijabli uvrstili izjave zaključujemo da je izraz istinit u sljedećim slučajevima:

Izjave "Autobus ima četiri kotača" i "Škola počinje u rujnu" su neistinite, a "Šparoge rastu uz more" istinita.
Izjava "Autobus ima četiri kotača" je neistinita, dok su izjave "Škola počinje u rujnu" i "Šparoge rastu uz more" istinite.
Izjava "Autobus ima četiri kotača" je istinita, dok su preostale izjave neistinite
Izjave "Autobus ima četiri kotača" i "Šparoge rastu uz more" istinite, a "Škola počinje u rujnu" neistinita.
Sve tri izjave istinite.

Za koju uređenu trojku je izraz $\bar{A + B} \cdot C$ istinit?

(0, 0, 0)

(0, 0, 1)

(0, 1, 0)

(0, 1, 1)

(1, 0, 0)

(1, 0, 1)

(1, 1, 0)

(1, 1, 1)

Pomoć:

Za riješiti ovaj zadatak potrebno je ispisati tablicu istinitosti. Najprije ispiši svih osam mogućnosti istinitosti za varijable $A, B i C .$ Nakon toga prvo treba primijeniti operaciju disjunkcije na prva dva stupca $(A i B)$ te ju potom negirati. Na kraju preostaje dobiveno povezati konjunkcijom sa stupcem $C .$

null

...i na kraju

"Ova logika baš i nije logična!" rekao je Petar. Ivan se nasmijao. "Logika je itekako logična, ali unutar svojih pravila. Misija matematičke logike jest da odredi u kojem su odnosu izjave te što se događa u svim mogućim istinitosnim kombinacijama. Ako istine i neistine zamijenimo s nulama i jedinicama, ustvari smo dobili logičke sklopove, koji čine računalo!" rekao mu je Ivan. "Što je pak to?!" pobunio se Petar. "O tome nekom drugom prilikom, a sada procjeni svoje znanje!"

Procijenite svoje znanje

Booleova algebra temelji se na izjavama koje mogu imati tri vrijednosti.

Da

Izjava može biti samo istinita i neistinita.

Ne

Izjava može biti samo istinita i neistinita.

null

Koja je izjava pogodna za izjavu Booleove algebre?

Ima li Ivan psa?

Gdje je Ivanov pas?

Ivanov pas je zlatni retriever.

Pas.

null

Ako je zadan logički izraz $\bar{A + B} \cdot \bar{C,}$ kojim se redoslijedom raspisuje tablica istinitosti?

$\bar{A + B} \cdot \bar{C}$
$\bar{C}$
$\bar{A + B}$
$A + B$

null

Zagrade utječu na redoslijed operatora.

Da

Ne

null

Uparite simbole s operacijom Booleove algebre.

$\bar{}$
$\cdot$
$+$

null

3.1 Djelovanje osnovnih logičkih operacija (NE, I, ILI) te prioritet operacija

Booleova algebra

Zanimljivost

Osnovne logičke operacije

Negacija

Konjunkcija

Disjunkcija

Logički izrazi

Primjer 1.

...i na kraju

Procijenite svoje znanje

MOJE ZNANJE

Uspješno ste usvojili sve odgojno-obrazovne ishode:

Potrudite se još malo kako biste bolje usvojili sljedeće odgojno-obrazovne ishode:

Trebali biste ponovno proći sljedeće jedinice:

Autobus ima četiri kotača.	$A$
Škola počinje u rujnu.	$B$
Šparoge rastu uz more.	$C$

$A$	$B$	$C$	$\bar{B}$	$A· \bar{B}$	$A· \bar{B} +C$
$0$	$0$	$0$	$1$	$0$	$0$
$0$	$0$	$1$	$1$	$0$	$1$
$0$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$	$1$	$1$
$1$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$0$	$1$

$A$	$B$	$C$	$\bar{B}$	$A· \bar{B}$	$A· \bar{B} +C$
$0$	$0$	$0$	$1$	$0$	$0$
$0$	$0$	$1$	$1$	$0$	$1$
$0$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$	$1$	$1$
$1$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$0$	$1$

$A$	$B$	$C$	$\bar{B}$	$A· \bar{B}$	$A· \bar{B} +C$
$0$	$0$	$0$	$1$	$0$	$0$
$0$	$0$	$1$	$1$	$0$	$1$
$0$	$1$	$0$	$0$	$0$	$0$
$0$	$1$	$1$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$	$1$	$1$
$1$	$1$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$0$	$0$	$1$