Matemaatiline loogika

Allikas: Teadmusbaas

Lingid välistele allikatele, kus on veel täiendavat infot

Boole’i algebra sissejuhatus

Kaasaegsete digitaalsete (kahendsüsteemsete) arvutite tööoperatsioonid põhinevad kaheväärtuselistele või kahendsüsteemile. Kahendsüsteem oli tuntud muistses Hiina tsivilisatsioonis ja klassikalistele Kreeka filosoofidele, kes lõid hästistruktureeritud kahendsüsteemi, mida nimetatakse lausearvutuseks (propositional logic). Väited või eelliited (propositions) võivad olla TÕENE (TRUE) või VÄÄR (FALSE) ja olla esitatud, kui funktsioonid teistest väidetest, millised on seotud 3 põhilise loogika ehk lausearvutuse tehtega AND, OR ja NOT. Näiteks lause või väide: „Ma võtan kaasa vihmavarju, kui väljas sajab või kui ilmaennustus lubab vihma“ ühendab väite „Ma võtan kaasa vihmavarju“ kahe väite või tingimusega „väljas sajab“ ja „ilmaennustus lubab vihma“. On võimalik taibata või näha, et vihmavarju väide on tingitud või tulenev sajab ja ilmaennustus väidete või lausetega. Funktsionaalses mõttes võime vaadata vihmavarju väite või lause tõest väärtust kui väljundit kahest ülejäänud lausest või väitest. Senise arutelu võib kokku võtta või esitada lihtsa blokkskeemiga, vt sele 1.

Sele1.png

OR tehte või funktsiooni sisu seisneb selles, et tema väljundi väärtus on TÕENE, kui ükskõik kumb sisenditest on TÕENE, muudel juhtudel on väljundi väärtus VÄÄR. Kuna iga sisendväite võimalike väärtuste arv on ainult 2 (TÕENE, VÄÄR), siis on võimalik lihtsalt leida tõesed väärtused kõikide „Võta vihmavari“ tingimuste jaoks. Sellist kõikide sisend- ja väljundväidete tabelit nimetatakse OR tehte või funktsiooni TÕEVÄÄRTUSTABELIKS, vt tabel 1.

Tabel 1. OR tehte tõeväärtuste tabel


Tabel 1.  OR tehte tõeväärtuste tabel

loogikaväärtused
Sajab (vihm) Vihma ennustus Võta vihmavari
VÄÄR VÄÄR VÄÄR
VÄÄR TÕENE TÕENE
TÕENE VÄÄR TÕENE
TÕENE TÕENE TÕENE

Lausearvutuse lauseid võib teha nii keerukaks, kui tingimused on keerukad või kui me seda vajame. Näiteks, kui tahame lisada väite „Ma võtan auto“, siis võib tervikväite moodustada järgmiselt: „Kui ma ei võta autot, siis võtan vihmavarju, kui ilm on vihmane või ilmaennustus lubab vihma“. Korrektse struktureeritud blokkskeemi loomiseks peaks esitama väite struktureeritult, kasutades sulgusid, näitamaks, kuidas väide koosneb. Üks võimalikke esitusi võiks olla näiteks:

(Võta vihmavari)=(NOT(Võta auto)) AND ((Vihma ennustus) OR (Vihm sajab)) (1)

Nagu märkasite, asendasime verbaalse konstruktsiooni „kui“ (IF) võrdusega kahendmuutujatest. Selle lausearvutuse lause blokkskeem on esitatud selel 2.

Lsele2.png

Et lihtsustada keerukate kahendmuutujate ja nende funktsioonide (tehete) kasutamist töötas matemaatik George Boole sajand tagasi välja matemaatika osa, mida nimetatakse Boole’i algebraks ja kus kasutatakse tavalist algebralist tähistust ja arvu 1 väärtuse TÕENE ning arvu 0 väärtuse VÄÄR tähistamiseks. Tavaliselt kasutatakse AND tehte jaoks tavalist matemaatika korrutusmärki „·“ – punkt keskel, (ASCII kooditabeli kood 0183), „+“ märki OR tehte jaoks ja priim märki („’“) NOT tehte jaoks. Kirjanduses kasutatakse ka teisi märke nagu ^-sümbolit AND jaoks ja ∨-sümbolit OR jaoks ning ¬- sümbolit NOT jaoks, mõnikord, kui see segadust ei tekita jäetakse AND tähistav punkt keskel ära või asendatakse see tavalise punktiga „.“, enam-vähem täieliku ülevaate kasutatavast sümboolikast annab tabel 2.

Tabel 2. Loogikatehete ehk Boole'i funktsioonide tähistuste tabel


Tabel 2.  Loogikatehete tähistamine

TEHE TÄHISTUS
And Konjunktsioon (AND) A^B, A∙B, A.B, AB, A&B, A&&B
Equivalent Ekvivalentsus (EQV) A≡B, A⇔B, A↔B, A~B
Implies Implikatsioon (IMP) A⇒B, A⊃B, A->B
Nand Eitav konjunktsioon (NAND) A|B, A↑B, !(AB), A⊼B
Nonequivalent Antiekvivalentsus A=/=>B, A≢B
Nonimplication Antiimplikatsioon A⊅B, A-/>B
Nor Eitav disjunktsioon (NOR) A⊽B, !(A+B)
Not Eitus, negatsioon (NOT) !A, ¬A, ~A
Or Disjunktsioon (OR) A⋁B, A+B, A|B, A||B
Xnor Välistav, eitav disjunktsioon (XNOR) A XNOR B, A=B, A↔B
Xor Välistav disjunktsioon (XOR) A⊻B, A⊕B, A≠B

Mingi hulga matemaatika sümboleid leiab ka veebist, vt Matemaatika sümbolid ja Unicode Math Symbols

Lausearvutuse ja Boole’i algebra lihtlauseid või väited tähistatakse Ladina tähestiku suurtähtedega (A…Z), seega võiks lause (1) esitada lühivormis: A=(B’)·(C+D). Tavaliselt lausearvutuse ja Boole’i algebra juures lihtlausete ja liitlausete sisu ei analüüsita ja lühivormis lausete kasutamise ja lihtsustamise eesmärk on leida selle lause loogikaväärtuste loogiliste vastuse kollektsioon ehk tõeväärtuste tabel. Kolme Boole’i põhifunktsiooni või lausearvutuse tehte tõeväärtustabelid on toodud tabelites 3..5

Tabel 3. AND funktsiooni tõeväärtuste tabel
A        B        A AND B
0 0 0
0 1 0
1 0 0
1 1 1
Tabel 4. OR funktsiooni tõeväärtuste tabel
A        B        A OR B
0 0 0
0 1 1
1 0 1
1 1 1
Tabel 5. NOT funktsiooni tõeväärtuste tabel
A        NOT A
0 1
1 0

Boole’i tehteid viiakse läbi kindlas tehete järjekorras, tehete prioriteete näitab tabel 6

Tabel 6. Loogikatehete prioriteedid
Operaator, tehe Tehte sümbol Prioriteet
NOT ' 1
AND . 2
OR + 3

Sulgudes olevaid tehteid tehakse kõigepealt, seega sulgusid saab kasutada täiendavalt prioriteetide määramiseks.

Loogikafunktsioonid (Boole’i funktsioonid)