DISKRETNE STRUKTURE 1 - Vežba 1 PDF

DISKRETNE STRUKTURE 1 Zorana Jančić Deprtman za računarske nauke Prirodno-matematički fakultet Univerzitet u Nišu, Srbija 1 Zorana Jančić DISKRETNE STRUKTURE 1 1 / 16  Sadržaj predmeta 2 Zorana Jančić DISKRETNE STRUKTURE 1 2 / 1...

DISKRETNE STRUKTURE 1 Zorana Jančić Deprtman za računarske nauke Prirodno-matematički fakultet Univerzitet u Nišu, Srbija 1 Zorana Jančić DISKRETNE STRUKTURE 1 1 / 16  Sadržaj predmeta 2 Zorana Jančić DISKRETNE STRUKTURE 1 2 / 16 Sadržaj predmeta (1) Iskazna logika (2) Predikatska logika (3) Skupovi (4) Relacije (5) Funkcije 3 Zorana Jančić DISKRETNE STRUKTURE 1 3 / 16 Pismeni deo ispita se sastoji iz dva kolokvijuma: I Iskazna logika i predikatska logika II Skupovi, relacije i funkcije 4 Zorana Jančić DISKRETNE STRUKTURE 1 4 / 16  Iskazna logika 5 Zorana Jančić DISKRETNE STRUKTURE 1 5 / 16 Iskazna logika Iskaz je izjava koja ima svojstvo da je istinita (tacna) ili neistinita (netacna) (samo jedno od toga). Iskazi se zadaju izjavnim rečenicama. Rečenica: ”Ceo broj 1 je najmanji pozitivan ceo broj.” jeste iskaz i to tačan Tačnost iskaza ili njegova netačnost čini istinitosnu vrednost iskaza. Rečenice: ”Ko si ti?”, ”Za sledeći cas uradite domaći!”, ”Ova rečenica nije tačna.” nisu iskazi. Prva i druga rečenica nemaju istinitosnu vrednost, dok trća rečenica istovremeno ima obe istinitosne vrednosti, što nije dozvoljeno. Zadatak 1. Ispitati koje su od navedenih rečenica iskazi i odrediti njihovu istinitosnu vrednost: 1 Koliko je sati? 2 Ako je x = 3, onda je x2 = 6. 3 Pazi auto! 4 Svi parni bojevi su deljivi sa 2. 5 Jupiter je planeta najbliža Suncu. 6 Zorana Jančić DISKRETNE STRUKTURE 1 6 / 16 Iskazna logika Proste iskaze označavamo slovima p, q, r, p1 , q1 , r1 ,... (iskazna slova ili iskazne promenljive). Iskaznim slovima pridružujemo istinitosne vrednosti: > − ”tačno”(1), ⊥ − ”netačno”(0) Od prostih iskaza gradimo složene upotrebom logičkih veznika koje označavamo smbolima: nije ¬ - negacija iskaza, ¬p i ∧ - konjunkcija iskaza, p ∧ q ili ∨ - disjunkcija iskaza, p∨q ako...onda... ⇒ - implikacija iskaza, p⇒q ako i samo ako ⇔ - ekvivalencija iskaza, p ⇔ q ili...ili... ⊕, ∨ - ekskluzivna disjunkcija, p⊕q U implikaciji p ⇒ q, iskaz p je premisa, pretpostavka ili antecedent, dok je iskaz q zaključak, posledica ili konsekvent. p ⇒ q se čita: iz p sledi q, q ako p, p povlači q, p je dovoljno za q, p samo ako q, q je potrebno za p. p ⇔ q se čita: p ako samo ako q, p je potrebno i dovoljno za q. 7 Zorana Jančić DISKRETNE STRUKTURE 1 7 / 16 Iskazna logika Zadatak 2. Sledeće rečenice prevesti u formule: (a) On je pametan i vredan. (b) On je pametan, ali nije vredan. (c) On nije napisao pismo ili je pismo izgubljeno. (d) On mora vredno da uči, inače će pasti na ispitu. (e) Ako je izvod funkcije f definisan na intervalu (a, b), potreban uslov da f bude rastuća na tom intervalu je da joj je prvi izvod pozitivan na (a, b). Rešenje: (a) p – ”on je pametan”, q – ”on je vredan” p∧q (b) p – ”on je pametan”, q – ”on je vredan” p ∧ ¬q (c) p – ”on je napisao pismo”, q – ”pismo je izgubljeno” ¬p ∨ q (d) p – ”on vredno uči”, q – ”on će pasti na ispitu” ¬p ⇒ q (e) p – ”izvod funkcije f je definisan na (a, b)”, q – ”funkcija f je rastuća na (a, b)”, r – ”izvod funkcije f je pozitivan na (a, b)” p ⇒ (r ⇒ q) 8 Zorana Jančić DISKRETNE STRUKTURE 1 8 / 16 Iskazna logika Jezik iskazne logike čine: – iskazna slova, p, q, r,..., p1 , q1 , r1 ,... – znaci logičkih operacija, ¬, ∧, ∨, ⇒ i ⇔ – pomoćni simboli, (, ). Znak ¬ je unaran, dok su ostali znaci logičkih operacija binarni. Konačan niz simbola iskazne logike je izraz (reč). Induktivna definicija iskazne formule: (1) Iskazna slova su iskazne formule. (2) Ako su A i B iskazne formule tada su sledeći izrazi takodje iskazne formule: (a) ¬A, (b) (A ∧ B), (c) (A ∨ B), (d) (A ⇒ B), (e) (A ⇔ B) (3) Iskazne formule su samo oni izrazi koji se mogu formirati primenom pravila (1) i (2) konačan broj puta. Svaka podreč iskazne formule koja je i sama iskazna formula je njena podformula. 9 Zorana Jančić DISKRETNE STRUKTURE 1 9 / 16 Iskazna logika Zadatak 3: Odrediti da li su sledeći izrazi iskazne formule: (a) ((p ∧ q) ∨ ¬r) (b) ((p3 ⇔ p1 ) ∧ ¬p) (c) ((p∧ ⇒)q) (d) (¬(p ∧ q) ⇔ s) (e) (⇔ (r ∨ p)) Rešenje: Na osnovu definicije skupa iskaznih formula, možemo zaključiti da izrazi (a), (b) i (d) jesu iskazne formule, dok izrazi (c) i (e) to nisu. Zadatak 4: Odrediti sve potfromule sledećih iskaznih formula: (a) ((p ∧ q) ∨ ¬r) (b) ((¬p3 ⇔ p1 ) ∧ ¬p) (c) ((¬r ∨ p) ⇒ (¬q ∧ s)) (d) (¬(p ⇒ q) ⇔ s) (e) (¬r ⇔ (p ∨ ¬q)) Rešenje: (a) p, q, r, ¬r, (p ∧ q), ((p ∧ q) ∨ ¬r) (b) p, p1 , p3 , ¬p, ¬p3 , (¬p3 ⇔ p1 ), ((¬p3 ⇔ p1 ) ∧ ¬p) (c) p, q, r, s, ¬q, ¬r, (¬r ∨ p), (¬q ∧ s), ((¬r ∨ p) ⇒ (¬q ∧ s)) (d) p, q, s, (p ⇒ q), ¬(p ⇒ q), (¬(p ⇒ q) ⇔ s) (e) p, q, r, ¬q, ¬r, (p ∨ ¬q), (¬r ⇔ (p ∨ ¬q)) 10 Zorana Jančić DISKRETNE STRUKTURE 1 10 / 16 Iskazna logika Konvenciju o brisanju zagrada čine sledeća pravila: (1) Izostavljanje spoljnjih zagrada p ∧ q, (p ∨ q) ⇒ r (2) Izostavljanje zagrada u odnosu na asocijativnost p ∧ q ∧ r umesto (p ∧ q) ∧ r ili p ∧ (q ∧ r) p ∨ q ∨ r ∨ s umesto (p ∨ q) ∨ (r ∨ s) (3) Dogovor o redosledu veznika ∧, ∨ ”jače vezuju” u odnosu na ⇒ i ⇔ p ∧ ¬q ⇔ ¬p ∨ r umesto (p ∧ ¬q) ⇔ (¬p ∨ r) 11 Zorana Jančić DISKRETNE STRUKTURE 1 11 / 16 Iskazna logika Zadatak 5: Sledeće rečenice prevesti u iskazne formule koristeći navedena slova kao iskazna: (a) Mika i Laza su fudbaleri. (m, l) (b) Ana voli operu ili voli latino muziku. (o, l) (c) Ugovor obavezuje ako nije prevara. (u, p) (d) Deljivost sa 2 je potreban uslov za broj da bi on bio deljiv sa 6. (d, s) Rešenje: (a) m ∧ l (b) o ∨ l (c) ¬p ⇒ u (d) s ⇒ d 12 Zorana Jančić DISKRETNE STRUKTURE 1 12 / 16 Iskazna logika Zadatak 6: Andjela, Branko i Kristina su studenti koji slušaju predmet ”Logika”. Neka su dati sledeći iskazi: p – ”Andjela je položila ispit iz Logike” q – ”Branko je položio ispit iz Logike” r – ”Kristina je položila ispit iz Logike” Pomoću ovih iskaza zapisati sledeće rečenice na jeziku iskazne logike: (a) Kristina je jedina položila ispit iz Logike (b) Andjela je jedina koja nije položila ispit iz Logike (c) Samo jedan od ovo troje studenata je položio ispit iz Logike (d) Bar jedan od ovo troje studenata je položio ispit iz Logike (e) Bar dvoje od ovo troje studenata je položilo ispit iz Logike (f) Najviśe dvoje od ovo troje studenata je položilo ispit iz Logike (g) Tačno dvoje od ovo troje studenata je položilo ispit iz Logike Rešenje: (a) r ∧ ¬p ∧ ¬q (b) ¬p ∧ q ∧ r (c) (r ∧ ¬p ∧ ¬q) ∨ (p ∧ ¬r ∧ ¬q) ∨ (q ∧ ¬r ∧ ¬p) (d) r ∨ p ∨ q (e) (r ∧ p) ∨ (p ∧ q) ∨ (q ∧ r) 13 Zorana Jančić DISKRETNE STRUKTURE 1 13 / 16 Istinitosna vrednost iskazne formule Valuacija je pravilo po kojem se svakom iskaznom slovu jezika iskazne logike pridružuje tačno jedna vrednost: tačno (>) ili netačno (⊥). Valuacija v je proizvoljno prelikavanje v : {p, q, r,..., p1 , q1 , r1 ,...} → {>, ⊥} Vrednost v(p) je istinitosna vrednost iskaznog slova p. Vrednost formule A u valuaciji v, u oznaci v(A), definiše se induktivno sa: 1. Ako je A iskazno slovo p, tada važi v(A) = v(p); 2. Ako je A = ¬B, tada je v(A) = > ako i samo ako v(B) = ⊥; 3. Ako je A = B ∧ C, tada je v(A) = > ako i samo ako je v(B) = > i v(C) = >; 4. Ako je A = B ∨ C, tada je v(A) = ⊥ ako i samo ako je v(B) = ⊥ i v(C) = ⊥; 5. Ako je A = B ⇒ C, tada je v(A) = ⊥ ako i samo ako je v(B) = > i v(C) = ⊥; 6. Ako je A = B ⇔ C, tada je v(A) = > ako i samo ako je v(B) = v(C). Za iskaznu formulu A kažemo da je tačna u valuaciji v, ako je v(A) = >. U suprotnom kažemo da je formula A netačna u valuaciji v. 14 Zorana Jančić DISKRETNE STRUKTURE 1 14 / 16 Istinitosna vrednost iskazne formule Iskazna formula je zadovoljiva, ako postoji bar jedna valuacija u kojoj je ta formula tačna. Tautologija je iskazna formula koja je tačna u svakoj valuaciji (|= A). Kontradikcija je iskazna formula koja je netačna u svakoj valuaciji. Iskazne formule A i B su semantički ekvivalentne ako i samo ako važi v(A) = v(B) za svaku valuaciju v (A ≡ B). Zadatak 7: Odrediti istinitosnu vrednost formula: (a) p ∧ (q ⇔ ¬r) (b) p ⇒ (q ⇒ r) (c) p ⇒ ¬q (d) ¬p ∨ q (e) ¬(p ∧ ¬q) (f) (¬p ∨ ¬q) ∧ (p ∨ q) (g) (p ∧ q) ⇒ r (h) p ∧ ¬q (i) ¬(p ⇔ q) u valuaciji v za koju važi v(p) = >, v(q) = v(r) = ⊥ 15 Zorana Jančić DISKRETNE STRUKTURE 1 15 / 16 Istinitosna vrednost iskazne formule Rešenje: (a) v(p ∧ (q ⇔ ¬r)) = v(p) ∧ v(q ⇔ ¬r) = > ∧ (v(q) ⇔ v(¬r)) = = > ∧ (⊥ ⇔ ¬v(r)) = > ∧ (⊥ ⇔ ¬⊥) = > ∧ (⊥ ⇔ >) = > ∧ ⊥ = ⊥ (b) v(p ⇒ (q ⇒ r)) = v(p) ⇒ v(q ⇒ r) = > ⇒ (v(q) ⇒ v(r)) = > ⇒ (⊥ ⇒ ⊥) = > ⇒ > = > (c) v(p ⇒ ¬q) = v(p) ⇒ v(¬q) = > ⇒ (¬v(q)) = > ⇒ (¬⊥) = > ⇒ > = > (d) v(¬p ∨ q) = v(¬p) ∨ v(q) = (¬v(p)) ∨ ⊥ = (¬>) ∨ ⊥ = ⊥ ∨ ⊥ = ⊥ (e) v(¬(p ∧ ¬q)) = ¬v(p ∧ ¬q) = ¬(v(p) ∧ v(¬q)) = ¬(> ∧ ¬v(q)) = ¬(> ∧ ¬⊥) = ¬(> ∧ >) = ¬> = ⊥ (f) v((¬p ∨ ¬q) ∧ (p ∨ q)) = v(¬p ∨ ¬q) ∧ v(p ∨ q) = (v(¬p) ∨ v(¬q)) ∧ (v(p) ∨ v(q)) = = (¬v(p) ∨ ¬v(q)) ∧ (> ∨ ⊥) = ((¬>) ∨ (¬⊥)) ∧ > = = (⊥ ∨ >) ∧ > = > ∧ > = > (g) v((p ∧ q) ⇒ r) = v(p ∧ q) ⇒ v(r) = (v(p) ∧ v(q)) ⇒ ⊥ = (> ∧ ⊥) ⇒ ⊥ = > ⇒ ⊥ = ⊥ (h) v(p ∧ ¬q) = v(p) ∧ v(¬q) = > ∧ (¬v(q)) = > ∧ (¬⊥) = > ∧ > = > (i) v(¬(p ⇔ q)) = ¬v(p ⇔ q) = ¬(v(p) ⇔ v(q)) = ¬(> ⇔ ⊥) = ¬⊥ = > 16 Zorana Jančić DISKRETNE STRUKTURE 1 16 / 16