Osnove matematičke logike

Sjedište: CARNET - Arhiva 2021 Loomen
E-kolegij: III. Gimnazija Osijek - Informatika 1
Knjiga: Osnove matematičke logike
Otisnuo/la: Gost (anonimni korisnik)
Datum: petak, 31. siječnja 2025., 00:44

Opis

Osnovne logičke operacije i složeni logički izrazi

1. Uvod

rubik

Do sada smo govorili o prikazivanju broja u računalu te o tome kako se zbrajaju dva broja u računalu. Te se aktivnosti obavljaju u procesoru računala točnije, u aritmetičko-logičkoj jedinici. U procesoru se nalaze sklopovi koji mogu napraviti dvojni komplement broja ili zbrojiti dva broja. Isto tako, pri programiranju važno nam je odrediti uz koje će se uvjete izvesti neki dio programa. Sve to odrađuju posebni sklopovi, a njih ne bi bilo bez matematičke logike.

U svakodnevnom životu vrlo često možemo čuti da je ne što logično. Obično tada mislimo da je to nešto što je očito, što se može jednoznačno obrazložiti.  Takvim problemima se bavi logika. Mi ćemo se baviti matematičkom logikom. Logika proučava izjave koje mogu biti ili istinite ili lažne. Radi kraćeg zapisivanja istinitost se označava s 1, a lažnost s 0.

Primjer: 

Odredimo istinitost sljedećih logičkih izraza:

a) 2 + 3 = 5

b) 2 > 3

c) Broj 6 je prost broj.

d) U hrvatskom jeziku ima 7 padeža.

 

Rješenje:

a) Istina, odnosno 1

b) Laž, odnosno 0

c) Laž, odnosno 0

d) Istina, odnosno 1


Za navedene logičke izraze možemo odmah utvrditi jesu li istiniti ili lažni. Takve izraze nazivamo osnovni ili jednostavni.

Osim osnovnih postoje i složeni izrazi, za koje ne možemo odmah utvrditi jesu li istiniti ili lažni, na primjer  ((2>3) ILI (2<3)) I (5>4).

Primjer:

Promotrimo sljedeće izjave. Možemo li za njih sa sigurnošću utvrditi jesu li istinite ili lažne?

a) Luka iz 1.a najljepši je dečko u školi.
b) Proljeće je najljepše godišnje doba.
c) Nogomet je najbolji sport.

Istinitost ovih izjava ne možemo sa sigurnošću utvrditi stoga se logika njima ne bavi.

2. Osnovne logičke operacije

uvodna_sklop

Matematička logika je grana matematike koja proučava složene logičke izraze. Osnove matematičke logike čini logička algebra ili Booleova algebra.

          George Boole (1815. – 1864.) – povezao je matematiku i logiku uvodeći matematički način zapisa u logiku.

Umjesto zapisivanja cijelih rečenica, izjave se u matematičkoj logici označuju slovima. Na primjer, umjesto izjave Informatika je obvezan predmet u prvom razredu gimnazije, možemo napisati slovo A.
Slova kojima zamjenjujemo logičke sudove nazivamo logičkim varijablama. Vrijednost logičke varijable je 1, ako je ona istinita, odnosno 0 , ako je ona lažna.

U Booleovoj algebri se, dakle, provode logičke operacije s logičkim varijablama. Za logičke operacije uvode se posebni simboli koje nazivamo logički operatori.

Od logičkih varijabli, logičkih operatora i zagrada tvorimo logičke izraze. Zagrade koristimo za definiranje prioriteta pri provođenju logičkih operacija.

U računalnoj primjeni bitne su tri operacije:

  • Negacija (logičko NE)
  • Konjunkcija (logički I)
  • Disjunkcija (logički ILI)

 

 

2.1. Negacija – logičko NE (NOT)

ne_uvodni

Logička varijabla A može poprimiti samo dvije vrijednosti: 1 ili 0.

Operacija logičko NE djeluje na jednu logičku varijablu tako da ju negira. Ako je varijabla istinita, ima vrijednost 1, a negacija je onda laž i ima vrijednost 0.

Dakle, negacija istine je laž, a negacija laži je istina.

Negaciju označavamo sa simbolom iznad varijable. Ovako .

Djelovanje logičkih operacija opisujemo tablicom istinitosti. Tablica istinitosti za negaciju je:

tablica ne

Primjer:

Odredimo istinitost sljedećih logičkih izraza:

a) NE(4 – 5 = 1)

b) NE (7 < 17)

Rješenje:

a) NE (laž) = istina, odnosno NE(0) = 1

b) NE (istina) = laž, odnosno NE(1) = 0

  čitamo kao „nije A“, „ne A“, „A negirano“, „A potez“ ili „negacija od A“.

2.2. Konjunkcija - logičko I (AND)

uvodna

Razmotrimo primjer iz svakodnevnog života. Tata je obećao Ivanu da će moći otići s prijateljima na tulum ako do odlaska dobije 5 iz matematike i opere auto. Iz primjera možemo zaključiti da je potrebno napraviti oboje. Nije dovoljno da Ivan napravi samo jedno od toga već mora oboje.

To možemo opisati dvjema logičkim varijablama koje ćemo međusobno povezati logičkom operacijom I ili AND  (konjunkcijom):

Logičko I (ili AND) ćemo označavati sa · (puta) pa se naziva i logičko množenje. Izraz A · B čita se A i B.

Dakle operacija logičko I (konjunkcija) djeluje na dvije varijable. Djelovanje konjunkcije opisuje se ovom tablicom istinitosti:

tablica istinitosti za I

Uočimo da je dvjema varijablama moguće postići četiri različite kombinacije njihovih vrijednosti. Rezultat operacije konjunkcija bit će istinit samo ako su obje logičke varijable istinite.

Pogledajmo kako bi to izgledalo na jednostavnom strujnom krugu sastavljenom od dviju sklopki koje predočuju varijable A i B, od žaruljice i izvora struje. Otvorenoj sklopki pridjeljujemo vrijednost 0, a zatvorenoj sklopki vrijednost 1. U kojem slučaju će žaruljica svijetliti?

     Žaruljica će svjetliti sam oak osu obje sklopke zatvorene, tj. u položaju 1, a to je slučaj d).

Primjer:

Odredimo istinitost sljedećih logičkih izraza:

a)       (4 > 5) I (3 ≤ 5)

b)      (2 < 7) I (6 > 5)

Rješenje:

a)       Laž I istina = 0 · 1 = 0 (laž)

b)      Istina I istina = 1 · 1 = 1 (istina)



2.3. Disjunkcija - logičko ILI (OR)

ili uvodna

Razmotrimo primjer sa tulumom, ali ovako: tata je obećao Ivanu da će moći otići s prijateljima na tulum ako do odlaska dobije 5 iz matematike ili opere auto. Iz primjera možemo zaključiti da je potrebno napraviti barem jedno od navedenog. Dakle, dovoljno je da Ivan napravi barem jedno od toga, ali može napraviti i oboje.

To možemo opisati dvjema logičkim varijablama koje ćemo međusobno povezati logičkom operacijom ILI odnosno OR  (disjunkcijom):

Logičko ILI (odnosno OR) ćemo označavati sa + pa se naziva i logičko zbrajanje. Izraz A + B čita se A ili B.

Dakle operacija logičko ILI (disjunkcija) djeluje na dvije varijable. Djelovanje disjunkcije opisuje se ovom tablicom istinitosti:

tablica - ili

Uočimo da je dvjema varijablama moguće postići četiri različite kombinacije njihovih vrijednosti. Rezultat operacije disjunkcije bit će istinit ako je barem jedna logička varijabla istinita. To dakako znači da mogu biti i obje.

Pogledajmo kako bi to izgledalo na jednostavnom strujnom krugu sastavljenom od dviju sklopki koje predočuju varijable A i B, od žaruljice i izvora struje. Otvorenoj sklopki pridjeljujemo vrijednost 0, a zatvorenoj sklopki vrijednost 1. U kojem slučaju će žaruljica svijetliti?

   Žaruljica će svijetliti ako je barem jedna od sklopki u položaju 1, dakle u slučajevima b), c) i d).


Primjer:

Odredimo istinitost sljedećih logičkih izraza:

a)       (3 = 5) ILI (3 < 5)

b)      Laž ILI (0 < 0)

Rješenje:

a)       Laž ILI istina = 0 + 1 = 1 (istina)

b)      Laž ILI laž = 0 + 0 = 0 (laž)


2.4. Prioritet izvršavanja logičkih operacija

Prioritet izvođenja logičkih operacija:

1. Zagrade
2. Negacija
3. Konjunkcija
4. Disjunkcija

2.5. Zadaci za vježbu s rješenjima

1. Za A=0, B=0, C=1, izračunaj: 

          a)  A ILI NE (A I B) ILI NE C

          b)  (A ILI NE A) I B ILI NE C

          c)  (A ILI NE A I B) ILI NE C

          d)  NE (A ILI NE B) ILI NE C

Rješenje:
          a) 0 ILI NE (0 I 0) ILI NE 1 = 0 ILI NE 0 ILI NE 1 = 0 ILI 1 ILI 0 = 1 ILI 0 = 1, istina,
          b) (0 ILI NE 0) I 0 ILI NE 1 = (0 ILI 1) I 0 ILI NE 1 = 1 I 0 ILI 0 = 0 ILI 0 = 0, laž,
          c) (0 ILI NE 0 I 0) ILI NE 1 = (0 ILI 1 I 0) ILI 0 = (0 ILI 0) ILI 0 = 0, laž,
          d) NE (0 ILI NE 0) ILI NE 1 = NE (0 ILI 1) ILI NE 1 = NE 1 ILI NE 1 = 0 ILI 0 = 0, laž.

2. Primjenom tablica istinitosti i prioriteta odredite istinitost sljedećih logičkih izraza:

          a) ((2<1) ILI (3=3)) I (5>1),

          b) NE(6<5) ILI (3=1) I (1<4),

          c)  ((2<3) I (3<6)) ILI NE(5=5).
Rješenje:

         a)  (0 ILI 1) I 1 = 1 I 1=1, istina,
         b)  NE 1 ILI 1 I 1 = 1 ILI (1 I 1) = 1 ILI 1 = 1, istina,
         c)  (1 I 1) ILI NE 1 = 1 ILI NE 1 = 1 ILI 0 = 1, istina.

3. Za A=1, B=0, C=0, izračunaj:

         a)  A I NE B ILI C ,

         b)  C I NE B ILI NE A,

         c)  NE B ILI C I NE A,

         d)  NE (C ILI A) ILI NE B,

Rješenje:

        a)  1 I 1 ILI 0 = 1 ILI 0 = 1, istina,
        b)  0 I 1 ILI 0 = 0 ILI 0 = 0, laž,
        c)  1 ILI 0 I 0 = 1 ILI 0 = 1, istina,
        d)  NE (0 ili 1) ILI 1 = NE 1 ILI 1 = 0 ILI 1 = 1, istina.

4. Primjenom tablica istinitosti i prioriteta odredite istinitost sljedećih logičkih izraza:

        a)  ((2 > 3) ILI (2 < 3)) I (5 > 4)

        b)  NE (6 < 9) ILI (3 = 3) I (1 > 1).

Rješenje:

        a)  (0 ILI 1) I 1 = 1 I 1 =1

        b)  NE (1) ILI 1 I 0 = 0 ILI 1 I 0 = 0 ILI 0 = 0   PAZITE NA PRIORITET!!!

5. Ana, Marko i Vedrana brali su jabuke. Ana tvrdi da je ubrala najviše jabuka. Napišite logički izraz čija će vrijednost biti istinita ako je Ana ubrala najviše jabuka, a laž inače.

Rješenje:

Pretpostavimo da je Ana ubrala A jabuka, Marko M jabuka, a Vedrana V jabuka. Aninu tvrdnju da je ubrala najviše jabuka moramo rastaviti u dvije tvrdnje povezane operatorom I:

Ana je ubrala više jabuka od Marka I Ana je ubrala više jabuka od Vedrane. To možemo zapisati ovako: (A > M) I (A > V).