Centar za edukaciju-BiH


Stranice (2):1,2

#1 12.09.2010 16:58
roza Van mreze
Super Moderator
Registrovan od:06.01.2009
Postovi:641


Predmet:Elementi matematicke logike
Algebra sudova je najjednostavniji dio matematicke logike.
U matematici cesto upotrebljavamo znakove ili simbole.
x je simbol za promjenljivu .

Najvazniji iskazi su oni za koje mozemo utvrditi istinitost.

SUD je iskaz za koji mozemo utvrditi da li je istinit ili neistinit.
5+6=11 je istinit sud (i)
5+6=10 je neistinit sud (n)

Logicka vrijednost suda je istina ili neistina.

Sud istovremeno ne moze biti istinit i neistinit.

Oznacavamo ih simbolima A, B, C, D...
Ako je sud istinit pisemo (i), a ako je neistinit (n)

Sud A moze biti istinit ili lazan.
Za dva suda A i B imamo ove mogucnosti

Sud A je istinit, sud B je istinit,
Sud A je istinit, sud B je lazan,
Sud A je lazan, sud B je istinit,
4. Sud A je lazan, sud B je lazan,

Tabela kojom se prikazuju sve n-torke vrijednosti sudova A1, A2... An je logicka tabela.

Simboli A, B, C, …, X, Y, Z su VARIJABLE (promjenljive) algebre sudova.
1, 2, 3, 4 su KONSTANTE. One odredjuju odredjen objekat.

Pomocu konstanti i varijabli formiraju se iskazi. upotrebom relacijskih oznaka dobijamo FORMULE.

Operacije algebre sudova

Elementarne operacije algebre sudova su:
negacija,
konjunkcija i
disjunkcija.

Cesto se uvode kao elementarne operacije jos
implikacija
ekvivalencija.

Negacija

Negacija je operacija koja ima samo jedan argument . Jos se zove unarna operacija.
Negacija _A suda A je sud koji je istinit kad je sud A lazan, a lazan
kad je sud A istinit.
Negacija negacije suda A je sud _(_A) je dvostruka negacija suda A.

Konjunkcija

Konjunkcija sudova odgovara upotrebi veznika i. Ona je binarna operacija. Konjunkcija A ∧ B sudova A i B je sud koji je istinit ako i samo ako su oba suda A i B istiniti sudovi.

Za konjunkciju vazi
A ∧ A = A,
A ∧ _A = (n).

Sud koji je lazan, bez obzira na vrijednosti svojih argumenata, zove se KONTRADIKCIJA, a sud koji je istinit za svaku vrijednost argumenata, zove se TAUTOLOGIJA .

Disjunkcija

Disjunkcija sudova odgovara upotrebi veznika ili
Disjunkcija A ∨ B sudova A i B je sud koji je istinit ako je barem jedan od sudova A i B istinit.

Zakon IDEMPOTENCIJE za disjunkciju: A ∨ A = A.
Sud A ∨_A = (i) bez obzira na logicku vrijednost suda A, tj. taj sud je tautologija.

De Morganove formule:

Negacija disjunkcije je konjunkcija negacija.

Simbolički: _(A ∨ B) = _A ∧ _B

Negacija konjunkcije je disjunkcija negacija.

Simbolički: _(A ∧ B) = _A ∨ _B

Sud na lijevoj strani jednakosti po logickoj vrijednosti jednak je sudu na desnoj strani.
"Ne treba se stidjeti nikakvog posla, pa čak ni onog najprljavijeg; treba se stidjeti samo besposlenog života." - Tolstoj
↑  ↓

#2 12.09.2010 17:10
roza Van mreze
Super Moderator
Registrovan od:06.01.2009
Postovi:641


Predmet:Re: Elementi matematicke logike
Neki zakoni koji vaze za sudove

Zakon asocijacije za disjunkciju
(A ∨ B) ∨ C = A ∨ (B ∨ C),

zakon asocijacije za konjunkciju
(A ∧ B) ∧ C = A ∧ (B ∧ C),

zakon distribucije konjunkcije prema disjunkciji
(A ∨ B) ∧ C = (A ∧ C) ∨ (B ∧ C),

zakon distribucije disjunkcije prema konjunkciji
(A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C).

Implikacija

Sud B je nuzanuslov za sud A, a sud A dovoljanuslov za sud B. Pa tako kazemo da sud A ima za posljedicu, ili da logicki povlaci (implicira) sud B.

A → B

Sud A je hipoteza dok je sud B teza ili implikacije A → B.

Implikacije koje su u nekoj nauci posebno vazne nazivaju se TEOREME, poucci ili
zakoni.

Manje vazne implikacije su LEME. Lema je pomocno sredstvo za dokazivanje
teorema.
Posljedica nekog teorema, koja se dobije na jednostavan nacin, zove se KOROLAR
ili posljedica.

Implikacija je lazna samo u jednom slucaju. I disjunkcija je lazna samo u jednom
slucaju, samo za jednu kombinaciju varijabli.

A→B i _A∨B jednake .

Ekvivalencija

Ako za dva suda istovremeno vrijede implikacije A→B i B→A, kažemo da su sudovi
logicki ekvivalentni i pišemo A↔B.

A↔B = (A→B)∧(B→A)

Za ekvivalentne sudove kayemo da su jedan drugome nuzan i dovoljan uslov.

Formula algebre sudova

Formula algebre sudova je svaki niz znakova varijabli x, y, z,…, konstanti (i) i (n), te znakova operacija negacije, konjunkcije, disjunkcije, implikacije i ekvivalencije za koje vrijede pravila formiranja:

a) Da su znakovi varijabli i konstanti formule,
b) Ako su x i y formule, tada su formule i nizovi _x, _y, x∨y, x∧y, x→y, y↔x,
x=y, x↔y,
c) Da se svaka formula dobiva konacnim brojem primjene pravila a) i b).

Predikati

P(x): x je paran broj

Istinitost, odnosno neistinitost ovoga iskaza zavisi od vrijednosti varijable x. Ovakvim elementarnim iskazima postavljaju se relacije izmedju njihovih argumenata, u ovome slucaju x i paran broj. Ove su relacije iskazane predikatima.
Varijable koje nismo specificirali u predikatu zovemo slobodnim varijablama.

Npr.:
P(x, y): x-y=1.

Univerzum razmatranja

Ako je predikat P(x1, x2, x3, … xn) istinit sud za svaki izbor argumenata iz univerzuma razmatranja kaze se da P
vrijedi u univerzumu razmatranja U.

Ako je predikat P istinit sud za neku n-torku argumenata iz U (ne nužno za sve), kaze se da je P zadovoljiv u U.
Ako ne postoji n-torka u U za koju je predikat P(x1, x2, x3, … xn) kaze se da P nije zadovoljiv u U.

Kvantifikatori

Kvantifikatori utvrdjuju da li neki (ili svi) objekti imaju neko osobinu ili
zadovoljavaju neki uslov.

Egzistencijalni kvantifikator utvrdjuje postojanje barem jednog objekta s trazenom osobinom. Oznacavamo ga simbolom ∃ (postoji). Ako tvrdimo
da postoji samo jedan x koji zadovoljava neki uslov, upotrebljavamo kvantifikator !∃.
Univerzalni kvantifikator utvrdjuje da za sve x vrijedi neki uslov. Njega oznacavamo simbolom ∀.

Postoje i predikati s više kvantifikatora.

Npr.:
∀ x ∀ y P(x, y)
∀ x ∃ y P(x, y)
∃ x ∀ y P(x, y)
∃ x ∃ y P(x, y)

Poredak kvantifikatora varijabli ne smije se mijenjati osim u ∀x∀y P(x, y) i ∃ x ∃ y P(x,y)
"Ne treba se stidjeti nikakvog posla, pa čak ni onog najprljavijeg; treba se stidjeti samo besposlenog života." - Tolstoj
↑  ↓

#3 12.09.2010 17:38
roza Van mreze
Super Moderator
Registrovan od:06.01.2009
Postovi:641


Predmet:Re: Elementi matematicke logike
DEFINICIJA

Definicija (lat. definitus - odredjen, razgovjetan, jasan) predstavlja odredjivanje jednog pojma po njegovim sosobinama da bude jasan i razgovjetan; jasno tumacenje.

Definicija se izrice najblizim rodnim pojmom i pojedinacnim razlikama (prema drugim pojmovima koji takodje spadaju pod isti rodni pojam)

Vazno je pravilo:

definicija neka ne bude odricna (ne treba odredjivati sta neki pojam nije nego sta jeste)

Defininicija matematickog pojma - odredjivanje (utvrdjivanje) smisla, sadrzaja matematickog pojma.

Pri ovome utvrdjivanje smisla (sustine) pojma moze da se sprovede na razne nacine:
1. geneticki - kad se ukazuje nacin obrazovanja datog pojma;
2. svodjenjem datog pojma na pojmove koji su vec poznati - najcesce pomocu pojmova vrste i vida, tj. kriterijumom vrste i razlikom u vidu;
3. aksiomatski - kad se pojam odredjuje implicitno u aksiomama (na primjer, tacka, prava, ravan).

Primjeri definicija

1. Sferom (trodimenzionalnog Euklidovog prostora) se naziva povrs koja nastaje obrtanjem kruga oko njegovog precnika (ovo je geneticka definicija. pojma sfere).
Ali se sfera moze definisati pomocu pojma geometrijskog mesta tacaka u prostoru ili analiticki.
2. Logaritam broja N > 0 za osnovu a > 0, a razlicito od 1

moze se definisati kao rjesenje eksponencijalne funkcije ax = N,
sto se pise:

x = loga N,
a moze se definisati i kao neko neprekidno resenje funkcionalne jednacine
f(xy) = f(x) + f(y),

Objasnjenje sustinenekog matematickog pojma u skoli je najlakse postici razmatranjem konkretnih primjera.

Genus i specificne odlike- razlike

Primjer:
Paralelogram je cetverougao kome su naspramne stranice paralelne.

Iz ove definicije proizlazi

1. paralelogram je cetverougao
2. skup paralelograma je podskup skupa cetverouglova
3. paralelogram je vrsta cetverouglacije su naspramne stranice paralelne.

To znaci da je pojam cetverougla genus (rod tj sira skupina) za pojam paralelograma.

Naspramne stranice su paralelne –specificna odlika (odlika vrste) paralelograma po kojima se paralelogrami razlikuju od cetverouglova. Svaka definicija sadrzi genus i specificna odlika

Definicija:
Kruznica je skup tacaka koje su jednako udaljene od stalne tacke nije ispravna jer nije navedeno da se te tacke nalaze u jednoj ravni, ovo je definicija lopte; treba reci skup tacaka ravni.

Definicija:
Paralelogram je cetverougao kome su naspramne stranice paralelne i jednake- nije ispravna jer je suvisno receno jednake. Naspramne stranice samim tim sto su paralelne i jednake.

Matematika rezultate svojih dokazivanja i zakljucivanja formulise u logicke sudove(stavove). Pri izvodjenju nekih stavova polazimo od pocetnih stavova.
Ove pocetne stavove nazivamo aksiome. U matematickoj teoriji njihov broj je mali.

Primjer

* Datom tackom A prolazi jedna i samo jedna prava paralelna datoj pravoj.

Pri izboru aksioma bitno je da su one saglasne nasem iskustvu.

Treba razlikovati definicije i teoreme. Teoremama tvrdimo pa ih dokazujemo. Definicijama sporazumno dajemo naziv nekom pojmu. Za njh se ne postavlja pitanje istinitosti nego pitanje da li odgovaraju tacno pojmovima koje definisemo i da li su dovoljno prikladne- pogodne. Nema smisla govoriti o dokazivanju.
"Ne treba se stidjeti nikakvog posla, pa čak ni onog najprljavijeg; treba se stidjeti samo besposlenog života." - Tolstoj
↑  ↓

#4 12.09.2010 17:59
roza Van mreze
Super Moderator
Registrovan od:06.01.2009
Postovi:641


Predmet:Re: Elementi matematicke logike
AKSIOM

Aksiom (grc. aksios - bez) je temeljna istina koja se ne dokazuje i sluzi kao osnova neke matematicke teorije. Za razliku od dogme uglavnom se ne tvrdi njena nuzna istinitost jer je to logicki nemoguce utvrditi, nego se uzima kao pretpostavka na kojoj se gradi teorija. Zato je u matematici normalno uzeti druge ili cak suprotne aksiome za izgradnju neke druge teorije.

Aksiomatska izgradnja neke matematicke teorije sadrzi sljedece etape:

1. Navodjenje osnovnih pojmova, sto znaci uvodjenje pojmova koji se ne definisu (skup, prava, tacka, itd.)
2. Formulacija aksioma
3. Definisanje novih pojmova (definicije)
4. Izvodjenje i dokazivanje teorema, lema, korolara, itd.

Formulacija aksioma mora zadovoljavati sljedeca tri principa:

1. princip nezavisnosti - aksiomi medjusobno moraju biti nezavisni i jedan se pomoc drugoga ne smije moci dokazati
2. aksiomi ne smiju biti medjusobno kontradiktorni

3. princip potpunosti - svaka matematicka teorija mora imati dovoljan broj aksioma da se moze izgraditi cijela teorija

Cesto se insistira da aksiomatska izgradnje bude minimalna.

TEOREMA

Teorema ili poucak je iskaz u kojem se uocava da neki matematicki pojam ima jos neke karakteristike osim onih koji su dati u definiciji tog pojma (npr. da je 1>0) i ta se tvrdnja mora dokazati. Dok se tvrdnja ne dokaze zovemo je hipotezom.

Radi lakseg razumijevanja teoreme se dijele na cetiri grupe

Teorem u uzem smislu je nesto jako bitno sto se cesto koristi i izvan uskog podrucja u kojem je dokazan. Najbolji primjer je Pitagorin teorem.

Propozicija je manji teorem koji sluzi u izgradnji neke teorije. Koristi se uglavnom samo u radu u kojem je uvedena ili se radi o opcepoznatoj tvrdnji koja je pretrivijalna da bi se zvala teoremom. Dobar primjer je tvrdnja da svaki broj pomnozen s nulom daje nulu.

Lema je teorem koji, u principu, nema korisnost osim u dokazivanju jednog ili nekoliko vecih teorema. Obicno se radi samo o pomagalu za jasnije iznosenje dokaza, te je prilagodjena dokazu i tesko da bi se mogla igdje drugdje upotrijebiti. Ipak, postoje "leme", kao npr. Zornova lema, koje se tako zovu jer zvuce tehnicki i koriste se u drugim dokazima, ali su po opsegu primjene zapravo teoremi.
Dobar primjer leme je tvrdnja koja kaze da determinanta transponirane matrice nije veca od determinante originalne matrice. Kada se ova lema iskoristi na samu sebe i time dokaze teorem da je determinanta transponirane matrice jednaka determinanti originalne matrice, tvrdnja leme postaje bespotrebna, iako nam je bila nuzna u dokazu tog teorema (osim ako netko ne uspije dokazati teorem na neki drugi nacin).

Korolar je kratki teorem koji slijedi direktno iz nekog prethodnog teorema. cesto se radi o najvaznijem posebnom slucaju nekog teorema koji se koristi cesce od samog teorema.

Ovo je "labava" podjela, tj. nista od toga nije egzaktno matematicki nego se tako dijeli cisto radi lakseg razumijevanja.
"Ne treba se stidjeti nikakvog posla, pa čak ni onog najprljavijeg; treba se stidjeti samo besposlenog života." - Tolstoj
↑  ↓

#5 16.05.2012 19:49
zidar Van mreze
Moderator
Registrovan od:03.02.2009
Postovi:27


Predmet:Re: Elementi matematicke logike
Ima jedna divna knjiga o matematickoj logici, moze se skinuti besplatno kao PDF, "applied mathematics for database professionals, de Haaan, Koopelars"

Prediban knjiga, nije laka za citanje za laike, ali posto je ovo forum matematike, verjem da ce vecina razumeti o cemu se radi. Knjiga ima uvodni deo o skupovima i matematicku logiku. Ono sto dodje posle, o bazama podataka, mozete da zanemarite, to je za one sa foruma o bazama.

Poglavlja o skupovima i matematickoj logici napisana su lepse i opsirnije nego sita sto sam video na nasim jezicima (zavrsio matematicku gimnaziju davne 1978 godine, ucio logiku i skupove). Ono 'lepse' je verovatno stvar ukusa, ali obno opsirniej stoji.

Tano kazu na primer, da su nam dovoljna dva operatora AND i OR da pokrijemo sve iskaze u logici. Podrazumeva se i NOT (koji nije operator u smislu AND i OR, vec vidse kao neka odrednica). Dakle, NOT, AND i OR su dovoljni => ne treba nam implikacija i ekvivalencija, barem teoretski. AUtori idu i dalje, pa tvrde da je u stvari NAND (NOT AND) operator dovoljan da se pokriju svi logicki iskazi. Doduse, iskazi napisani isklucivo pomocu NAND operatora jako su necitljivi i nerazumljivi, pa se to ni ne radi nigde u praksi. Sto se tice eliminisanja implikacije (=>) i ekvivalencije (<=>), tu vec imamo primenu.

Svi (ili gotovo svi) poznati komputerski programi i sistemi za upravljanje bazama podataka i imaju samo NOT, OR i AND. Kako to moze, i kako predstavljamo => ili <=> ? Odgovor imate u postu koji je ostavila Roza, samo se ne vidi bas odmah:

"Implikacija je lazna samo u jednom slucaju. I disjunkcija je lazna samo u jednom
slucaju, samo za jednu kombinaciju varijabli.

A→B i _A∨B jednake .
"

Obratite paznju na poslednji red, koji kao visi u vazduhu. To u stvari kaze:

(A => B) <=> (NOT A OR B)

Postavite tablicu istinitost, kao kad dokazujete tautologiju i videcete da je iskaz (A => B) <=> (NOT A OR B) u stvari tautologija. (NOT A OR B) dkale zamenjuje A => B. Za matematicare i teoreticare nista vazno, jos jedna tautologija i to je sve. Medjutim, za prakticare (one sto programiraju i vode racuna o bazama podataka) nemerljivo velika stvar. Za cudjenje je koliko malo i teoreticara i prakticara zna za ovo. Moji programeri sa iskustvom nikad nisu culi za ovo. Nedavno smo dobili mladog diplomca sa matematike, koji takodje nije znao, p akd smo mu pokazali, jedini komentar je bio "This is pure magic mann!"

Eto, podelili smo sa vama deo 'pure magic". Ako neko cita ovo ko predaje matematiku ili programiranje u skoli, ne zaboravite da ovu "pure magic" prenesete djacima. Valjace im nekad u buducnosti.
↑  ↓

#6 19.05.2012 19:43
dex Van mreze
Super Moderator
Registrovan od:23.02.2012
Postovi:625


Predmet:Re: Elementi matematicke logike
Mislio sam da su ovo opste poznate stvari.
Gomilu ovakvih "pure magic" moguce je napraviti pomocu Karnoovih mapa.
Samo jedan od gomile primera na netu.

Prilozi:
Informacije o tipu datoteke za:pdf  Karnoove_mape.pdf
Preuzimanja:946
Velicina datoteke:73.63 KB

↑  ↓

#7 20.05.2012 13:16
dex Van mreze
Super Moderator
Registrovan od:23.02.2012
Postovi:625


Predmet:Re: Elementi matematicke logike
Kako se koriste

Pa prvo napravimo istinitosnu tablicu, odnosno definisemo za koju kombinaciju ulaza zelimo/treba nam
koji izlaz.

Jedinicama iz istinitosne tablice popunimo karnoovu mapu

Vrsimo grupisanje i resavanje po gore navedenim pravilima

Pogodnosti:

Brzo i lako se resavaju
dobijaju se prilicno jednostavne funkcije
funkcije sadrze samo operacije I, ILI i NEGACIJU, pa se stoga lako prevode u programski kod ili semu povezivanja logickih kola u elektronici
↑  ↓

#8 23.05.2012 19:23
zidar Van mreze
Moderator
Registrovan od:03.02.2009
Postovi:27


Predmet:Re: Elementi matematicke logike
"Mislio sam da su ovo opste poznate stvari.
Gomilu ovakvih "pure magic" moguce je napraviti pomocu Karnoovih mapa."

Problem je u tome sto i nisu opste poznate stvari, a trebalo bi da budu. Ako imas prilike da razgovaras sa 10 programera, bar 9 od njih ne zna da je (A=>B) <=> ( NOT A OR B). Za Karnoove mape nisu ni culi, 10 od 10. AKo razgovars sa 10 inzenjera elektronicara, imaces vise uspeha. Ali, elektronicari uglavnom rade na povezivanju logickih kola u elektronici, a ne na gradjenju baza podataka.

Zato smo ovde na forumu, da razmenimo sta znamo - ono sto je u nekoj oblasti trivijalno, u nekoj drugoj je velika glavobolja i nepoznanica.

Mozes li da nam pokazes akko pomocu Karnoovih mapa da transformisemo A => B u nesto sto koristi samo AND, OR ili NOT?
↑  ↓

#9 27.05.2012 19:40
dex Van mreze
Super Moderator
Registrovan od:23.02.2012
Postovi:625


Predmet:Re: Elementi matematicke logike
Evo, salljem kao PDF zbog crteza

Prilozi:
Informacije o tipu datoteke za:pdf  Primer Karnoove mape.pdf
Preuzimanja:442
Velicina datoteke:10.75 KB

↑  ↓

#10 30.05.2012 18:47
dex Van mreze
Super Moderator
Registrovan od:23.02.2012
Postovi:625


Predmet:Re: Elementi matematicke logike
Kao sto iz prilozenog vidimo Karnoova mapa kod ekvivalencije ne pomaze mnogo jer mapa izgleda kao sahovska tabla pa je grupisanje nemoguce i dobijamo prilicno slozen izraz.
Kako smo uocili sto je veca grupa, sve vise clanova ispada i dobijamo sve jednostavniji izraz

Ipak nije sve bas tako crno.
Srecom operacija ekvivalencije ima svoju "rodjaku" operaciju excluzivno ili.

za nju istinitosna tablica izgleda

A    B    AÅB
0    0    0
1    0    1
0    1    1
1    1    0

Kao sto vidimo ona predstavlje negaciju ekvivalencije.
Interesantno je primetiti da ako imamo dve ekvivalencije to je isto sto i dve
negacije ekskluzivne disjunkcije, odnosno samo dve ekskluzivne disjunkcije (dve negacije
ponistavaju jedna drugu)

odnosno

A<=>B<=>C je isto sto i AÅBÅC

i tako na dalje paran broj ekvivalencija isto sto i ekskluzivna disjunkcija, neparan broj ekvivalencija
isto sto i negacija ekskluzivne disjunkcije.

Mnogi programski jezici poznaju operaciju excluzivne disjunkcije, obicno se obelezava sa XOR, ali i nju mnogi programeri slabo poznaju i koriste.

Cak i ako jezik nema operaciju XOR opet ima resenja.
Operacija XOR ima svoju "sestru bliznakinju" operaciju MOD2 ili narodski receno da li je broj paran ili neparan.
Znaci potrebno je promenljive aritmeticki sabrati i videti da li je zbir paran ili neparan.
Podrazumeva se da logicki tacno ima vrednost 1, a logicki netacno vrednost 0

Izvinjavam se ako sam malo dosadan i preopsiran, ali ovo su za nekoga mozada potpuno nepoznate stvari, a mogu mnogo da koriste

Prilozi:
Informacije o tipu datoteke za:pdf  Karnoove Mape ekvivalencija.pdf
Preuzimanja:413
Velicina datoteke:10.68 KB

↑  ↓

Stranice (2):1,2


Sva vremena su GMT +01:00. Trenutno vrijeme: 10: 10 am.