Otisni knjiguOtisni knjigu

Osnove matematičke logike

Sjedište: CARNET - Arhiva 2021 Loomen
E-kolegij: Pripreme za ispit iz informatike na državnoj maturi
Knjiga: Osnove matematičke logike
Otisnuo/la: Gost (anonimni korisnik)
Datum: nedjelja, 24. studenoga 2024., 14:28

Opis

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

Sadržaj

1. Uvod

Osnovni element matematičke logike (booleove algebre) je IZJAVA za koju se može ustanoviti je li ISTINITA ili LAŽNA.

Istinitost i laž neke izjave može se označiti na više načina. U informatici, zbog povezivanja sa zapisom brojeva u računalu, istinitost i laž izjava označavat ćemo znamenkama 0 i 1.
Istinitu izjavu označit ćemo sa 1, a lažnu sa 0.

Primjeri izjava:
Danas je prvi dan jeseni.
Pada kiša.
U torbi nosim kišobran.
Redovno učim i pripremam se za državnu maturu.
Položit ću državnu maturu sa odličnim ocjenama.
Upisat ću željeni fakultet.

Za svaku od prethodno navedenih rečenica možemo utvrditi jesu li istinite ili lažne. Isto tako, između istinitosti pojedinih izjava može postojati veza.

Možemo reći da će izjava "Upisat ću željeni fakultet." biti istinita ako su istinite obje izjave: "Redovno učim i pripremam se za državnu maturu." i "Položit ću državnu maturu sa odličnim ocjenama."

To znači da izjave možemo povezati LOGIČKIM operacijama. Jednako kao što brojeve možemo povezati aritmetičkim operacijama.

Logičkim operacijama izračunavamo istinitost logičkih izraza na temelju istinitosti početnih izjava.

2. Osnovne logičke operacije

U osnovne logičke operacije pripadaju: logička operacija NE (negacija), logička operacija I (logičko množenje, konjunkcija) i logička operacija ILI (logičko zbrajanje, disjunkcija).

LOGIČKA OPERACIJA I

Logička operacija I (konjunkcija) uključuje dvije izjave i istinita je samo ako su obje izjave ISTINITE.

Postoji više načina označavanja logičkih operacija. Pošto logičku operaciju I nazivamo i logičko množenje, označavat ćemo ju znakom "·"

Isto tako, nepraktično je da izjave zapisujemo kao rečenice. Zbog toga ćemo svaku rečenicu zamijeniti jednim slovom (najčešće velikim, ali nije uvjet).

Znači, umjesto da pišemo dvije rečenice, logičku funkciju I koju primjenjujemo na izjave A i B, možemo zapisati ovako: Z=A·B. Z je rezultat logičke funkcije.

Umjesto definicije logičke operacije na način na koji smo to napravili u prvoj rečenici, ona se može definirati tzv. TABLICOM ISTINITOSTI ili TABLICOM STANJA.

Tablica stanja definira istinitost cjelokupne logičke operacije zasnovane na istinitosti izjava uključenih u tu operaciju.

Tablica stanja logičke operacije I:
 

A

B

A · B

0

0

0

0

1

0

1

0

0

1

1

1

Iz tablice stanja logičke operacije I vidimo da je logička operacija I istinita (1) samo ako su obje izjave uključene u operaciju istinite (1).

LOGIČKA OPERACIJA ILI

Logička operacija ILI (disjunkcija) također uključuje dvije izjave. Istinita je ako je barem jedna od njih ISTINITA.

Logičku operaciju ILI nazivamo i logičko zbrajanje i označavamo ju znakom "+"

Tablica stanja logičke operacije ILI:
 

A

B

A + B

0

0

0

0

1

1

1

0

1

1

1

1

LOGIČKA OPERACIJA NE

Logička operacija NE (negacija) uključuje samo jednu izjavu. Istinita je ako je početna izjava neistinita.

\( \overline A \)

Tablica stanja logičke operacije NE:
 

A

\( \overline A \)

0

1

1

0

 

3. Složeni logički izrazi

Osnovne logičke operacije često se kombiniraju u složene.

Primjer:

Z=A·B+C·B

Znajući definicije i (ili) tablice istinitosti osnovnih logičkih operacija lako možemo napraviti tablicu istinitosti zadane složene logičke operacije.

Kod izrade tablice istinitosti složene logičke operacije potrebno je znati:

1. Prioritet izvršavanja osnovnih logičkih operacija i

2. Koliko različitih kombinacija postoji za zadan broj izjava

Prioritet izvršavanja osnovnih logičkih operacija

Kada imamo više logičkih operacija, a one nisu odvojene zagradama, najprije ćemo napraviti negaciju, zatim logičko množenje (I), a tek na kraju zbrajanje (ILI). Operacije istog prioriteta izvršavamo s lijeva na desno.

Broj kombinacija u složenoj logičkoj operaciji

Broj kombinacija ovisi o broju različitih izjava. Kako svaka izjava može poprimiti stanje 1 ili 0, postoji 2broj izjava različitih kombinacija.

Ako imamo 2 izjave (A i B) postoje 4 različite kombinacije "nula" i "jedinica".

U prethodnom primjeru imamo tri izjave (A, B, C), odnosno 8 kombinacija.

Postavlja se pitanje: kako popuniti početne vrijednosti u tablici istinitosti, a da budemo sigurni da smo uzeli u obzir sve kombinacije i da niti jednu nismo ponovili?

Za prethodni primjer početne kombinacije u tablici istinitosti popunjavamo ovako: Imamo tri izjave, što znači 8 kombinacija. Za popunjavanje prvog stupca prepolovimo broj kombinacija (8:2=4) i prvu polovicu (prve 4) popunimo nulama, dok drugu polovicu popunimo jedinicama.
U sljedećem stupcu (izjava B) prepolovimo onaj "prepolovljeni" broj iz prethodnog stupca (4:2=2). Sada popunjavamo stupac najprije sa dvije nule, pa dvije jedinice, pa dvije nule, dvije jedinice.
Zadnji stupac popunjavamo tako da kombiniramo nulu, pa jedinicu dok ne dođemo do kraja (opet smo broj 2 iz prethodnog stupca podijelili sa dva)

Ovo možda izgleda komplicirano kad se prvi puta čita, ali kad pogledate u tablici sve će vam postati jasno.

A B C
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

Za četiri izjave imamo 16 kombinacija. Prvi stupac popunjavamo sa osam nula i osam jedinica, a zatim opet za svaki sljedeći prepolovimo broj iz prethodnog stupca (Znači 8, pa 4, pa 2 i na kraju 1)

Idemo konačno napraviti tablicu istinitosti za naš primjer. Kako množenje ima veći prioritet od zbrajanja, ne možemo ići redom. Najprije moramo izračunati AB, zatim BC i tek na kraju zbrojiti dobivene rezultate. Slično kao u matematici, zar ne?

A B C AB BC AB+AC
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 1 1 0 1 1
1 0 0 0 0 0
1 0 1 0 0 0
1 1 0 1 0 1
1 1 1 1 1 1

 

3.1. Pojednostavljivanje složenih logičkih izraza

Osnovna pravila koja nam mogu pomoći u pojednostavljivanju logičkih izraza su:

\( \overline{\overline{ A}} = A \)

De Morganovo pravilo:

Komutativnost:

Distributivnost:

3.2. Zadatci s provedenih ispita

  1. (2010, ljetni rok, zadatak 17) Koji će oblik nakon pojednostavljenja imati logička formula

    A.0
    B.1
    C. A B
    D.

  2. (2010, ljetni rok, zadatak 30) Logički izraz napišite tako da rabite samo operacije disjunkcije i negacije.

  3. (2010, jesenski rok, zadatak 17) Koji će oblik nakon pojednostavljenja imati logička formula ?
    A. 0
    B. 1
    C.
    D.

  4. (2010, jesenski rok, zadatak 30) Logički izraz napišite tako da rabite samo operacije konjunkcije i negacije.

  5. (2011, ljetni rok, zadatak 17) Koji će oblik imati logička formula nakon pojednostavljenja?
    A. 1
    B. A⋅ B
    C. 0
    D. C

  6. (2011, ljetni rok, zadatak 30) Pojednostavnite logički izraz tako da sadrži minimalni broj simbola i to tako da rabite samo operacije disjunkcije i negacije.
  7. (2011, jesenski rok, zadatak 17) Koji će oblik imati logička formula nakon pojednostavljenja?

    A.
    B. A + B
    C.
    D. 1
  8. (2011, jesenski rok, zadatak 30) Napišite logički izraz rabeći točno tri logičke operacije.

  9. (2012, ljetni rok, zadatak 13) Za koje će od ponuđenih vrijednosti logički izraz biti istinit?
    A. A = 1, B = 1
    B. A = 1, B = 0
    C. A = 0, B = 1
    D. A = 0, B = 0

  10. (2012, ljetni rok, zadatak 15) Pojednostavnite logički izraz na način da ga napišete s najmanjim mogućim brojem operacija i operanada.

  11. (2012, jesenski rok, zadatak 13) Kako će izgledati logički izraz nakon pojednostavljenja?
    A. 0
    B. 1
    C. A
    D. B

  12. (2012, jesenski rok, zadatak 24) Pojednostavnite logički izraz na način da ga napišete s najmanjim mogućim brojem operacija i operanada.

  13. (2013, ljetni rok, zadatak 13) Kako glasi logički izraz nakon pojednostavljenja?
    A.
    B.
    C.
    D.

  14. (2013, ljetni rok, zadatak 15) Koja tablica istinitosti odgovara logičkomu izrazu ?



  15. (2013, ljetni rok, zadatak 23) Pojednostavnite logički izraz tako da ga napišete s najmanjim mogućim brojem operacija i operanada.

  16. (2013, jesenski rok, zadatak 13) Kako glasi pojednostavljeni logički izraz ?
    A. 0
    B. 1
    C.
    D.

  17. (2013, jesenski rok, zadatak 23) Pojednostavnite logički izraz tako da ga napišete s najmanjim mogućim brojem operacija i operanada.

  18. (2014, ljetni rok, zadatak 13) Kako će izgledati logički izraz nakon pojednostavljenja?
    A. 0
    B. 1
    C. A
    D.

  19. (2014, ljetni rok, zadatak 25) Pojednostavnite logički izraz na način da ga napišete s najmanjim mogućim brojem osnovnih operacija.

  20. (2014, jesenski rok, zadatak 13) Kako će izgledati logički izraz nakon pojednostavljenja?
    A. 0
    B.
    C. B
    D.
  21. (2014, jesenski rok, zadatak 25) Pojednostavnite logički izraz na način da ga napišete s najmanjim mogućim brojem osnovnih operacija.

  22. (2015, ljetni rok, zadatak 13) Kako glasi pojednostavljeni logički izraz ?
    A. A⋅ B
    B. A
    C. 0
    D. 1

  23. (2015, ljetni rok, zadatak 15) Kako glasi pojednostavljeni logički izraz ?
    A. 0
    B. 1
    C.
    D. A⋅ B⋅C
  24. (2015, ljetni rok, zadatak 23) Pojednostavnite logički izraz tako da ga napišete s najmanjim mogućim brojem operacija i operanada.

  25. (2015, jesenski rok, zadatak 13) Kako glasi pojednostavljeni logički izraz ?
    A. A+ B
    B.
    C. 0
    D. 1
  26. (2015, jesenski rok, zadatak 15) Koja tablica istinitosti odgovara logičkomu izrazu

  27. (2015, jesenski rok, zadatak 23) Pojednostavnite logički izraz tako da ga napišete s najmanjim mogućim brojem operacija i operanada.

  28. (2016., ljetni rok, zadatak 8) Čemu je jednaka negacija konjunkcije?
    A. disjunkciji negacija
    B. konjunkciji negacija
    C. negaciji disjunkcije
    D. disjunkciji konjunkcija

  29. (2016., ljetni rok, zadatak 13) Kako će izgledati logički izraz nakon pojednostavljenja?

    A.
    B.
    C.
    D.
  30. (2016., ljetni rok, zadatak 25) Zadan je logički izraz . Kako glasi pojednostavljeni zadani logički izraz ako se upotrebljava najmanji mogući broj osnovnih operacija I, ILI i NE? 

3.3. Rješenja

  1. C
  3. B
  4.  
  5. A
  6.  
  7. A
  8.  
  9. C
  10.  
  11. B
  12. AB+C
  13. A
  14. C
  15. 0
  16. D
  17.  
  18. A
  19.  
  20. D
  21. AB
  22. D
  23. D
  24.  
  25. A
  26. A
  27. AB+C
  28. A
  29. C

4. Konjunktivna i disjunktivna normalna forma

U logici ne moramo uvijek krenuti od izraza prema tablici istinitosti. Problem se može postaviti i obrnuto: za danu tablicu istinitosti potrebno je napisati logički izraz.

Za rješavanje takvih problema koristimo konjunktivnu i disjunktivnu normalnu formu.

4.1. Konjunktivna normalna forma

Postupak za dobivanje izraza je sljedeći:

  1. U tablici istinitosti gledamo samo one redove u kojima je rezultat nula

  2. U svakom od tih redova zbrajamo varijable, ali s tim da varijable čija je vrijednost jedan negiramo (one čija je vrijednost nula samo prepišemo).

  3. Na kraju dobivene sume pomnožimo.

Da to nije tako komplicirano kako izgleda na prvi pogled, pogledajmo na primjeru.

Primjer:

Na osnovi tablice istinitosti odredimo konjunktivnu normalnu formu:

A B f(A,B)
0 0 0
0 1 1
1 0 0
1 1 1

  1. U tablici istinitosti gledamo samo one redove u kojima je rezultat nula

A B f(A,B)
0 0 0
0 1 1
1 0 0
1 1 1
  1. U svakom od tih redova zbrajamo varijable, ali s tim da varijable čija je vrijednost jedan negiramo (one čija je vrijednost nula samo prepišemo).
A B f(A,B)  
0 0 0 A+B
0 1 1  
1 0 0  Ā+B
1 1 1  

  1. Na kraju dobivene sume pomnožimo.
    f(A, B)= (A+B)* (Ā+B)

4.2. Disjunktivna normalna forma

Postupak za dobivanje izraza je sljedeći:

  1. U tablici istinitosti gledamo samo one redove u kojima je rezultat jedan

  2. U svakom od tih redova množimo varijable, ali s tim da varijable čija je vrijednost nula negiramo (one čija je vrijednost jedan samo prepišemo).

  3. Na kraju dobivene umnoške zbrojimo.

Pogledajmo primjer:

Primjer:

Na osnovi tablice istinitosti odredimo disjunktivnu normalnu formu:

A B f(A,B)
0 0 0
0 1 1
1 0 0
1 1 1

  1. U tablici istinitosti gledamo samo one redove u kojima je rezultat jedan

A B f(A,B)
0 0 0
0 1 1
1 0 0
1 1 1
  1. U svakom od tih redova množimo varijable, ali s tim da varijable čija je vrijednost nula negiramo (one čija je vrijednost jedan samo prepišemo).
A B f(A,B)  
0 0 0  
0 1 1 ĀB
1 0 0  
1 1 1 AB

  1. Na kraju dobivene umnoške zbrojimo.
    f(A, B)= (ĀB)+ (AB)

Napomena: hoćemo li raditi konjunktivnu ili disjunktivnu normalnu formu, ovisi o tome ima li u tablici manje nula ili jedinica!

Zadatak za vježbu:

  1. Na osnovu sljedećih tablica istinitosti odredite konjunktivnu i disjunktivnu normalnu formu:

A B f(A,B)
0 0 1
0 1 1
1 0 0
1 1 0

 

A B C f(A,B,C)
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

 

4.3. Zadatci s provedenih ispita

  1. (2012, ljetni rok, zadatak 15) Kojem od navedenih logičkih izraza odgovara ova tablica istinitosti?Kojem od navedenih logičkih izraza odgovara ova tablica istinitosti?


  2. (2012, jesenski rok, zadatak 14) Kojem od navedenih logičkih izraza odgovara ova tablica istinitosti?


  3. (2013, jesenski rok, zadatak 14) Kojemu od navedenih logičkih izraza odgovara prikazana tablica istinitosti?


  4. (2014, ljetni rok, zadatak 15) Kojemu logičkomu izrazu odgovara navedena tablica istinitosti?


  5. (2014, jesenski rok, zadatak 15) Kojemu od navedenih logičkih izraza odgovara navedena tablica istinitosti?


  6. (2015, ljetni rok, zadatak 14) Kako glasi logički izraz koji je opisan prikazanom tablicom istinitosti?

  7. (2015, jesenski rok, zadatak 14) Koji je od navedenih logičkih izraza opisan prikazanom tablicom istinitosti?
  8. (2016., ljetni rok, zadatak 15) Koji logički izraz odgovara sljedećoj tablici istinitosti?

4.4. Rješenja

  1. C
  2. B
  3. A
  4. C
  5. A
  6. A
  7. C
  8. A