Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIČKA LOGIKA

Uvod u logiku

[inlmath]\left[p\land\left(q\Rightarrow\lnot p\right)\right]\Leftrightarrow\lnot\left(p\Rightarrow q\right)[/inlmath]

Uvod u logiku

Postod ubavic » Ponedeljak, 12. Avgust 2013, 22:38

Naredni tekst predstavlja pojednostavljen uvod u iskaznu i predikatsku logiku. Ovaj tekst je namenjen osnovcima koji se prvi put susreću sa matematičkom logikom. Za nešto napredniji uvod u iskaznu logiku, pogledati tekst Iskazna logika.

U svakodnevnom životu ljudi međusobno komuniciraju koristeći se rečenicama. Tako se i u matematici javljaju rečenice koje su po svom značenju izjavne. Za takve rečenice u matematici kažemo da su sudovi ili iskazi. Oblast matematike koja se bavi iskazima nazivamo Logika. U matematici iskazi mogu biti samo tačni ili netačni. Iskaze koji su tačni obeležavamo sa [inlmath]1[/inlmath] ili [inlmath]\top[/inlmath] (čita se „tačno“ ili „te“), a iskaze koji su netačni obeležavamo sa [inlmath]0[/inlmath] ili [inlmath]\bot[/inlmath] (čita se „netačno“ ili „en-te“).
Npr.: „Nedelja ima sedam dana“ je tačna rečenica ( [inlmath]\top[/inlmath] ), dok je rečenica „Sunce se okreće oko Zemlje“ netačna rečenica ( [inlmath]\bot[/inlmath] ).
Rečenice možemo simbolično predstaviti kao latinična slova [inlmath]p[/inlmath], [inlmath]q[/inlmath], [inlmath]r[/inlmath], [inlmath]s[/inlmath], [inlmath]t[/inlmath] itd... Istinitosnu vrednost nekog iskaza [inlmath]p[/inlmath] obeležavaćemo sa [inlmath]\tau(p)[/inlmath] (čita se: tau od pe).
Npr.: ako obeležimo rečenicu „sneg je beo“ sa [inlmath]q[/inlmath], a rečenicu „[inlmath]2+2=5[/inlmath]“ sa [inlmath]r[/inlmath], onda je [inlmath]\tau(q)=\top[/inlmath] i [inlmath]\tau(r)=\bot[/inlmath].

Korišćenjem takozvane iskazne algebre (Bulove algebre) moguće je konstruisati složenije rečenice (iskaze). Kao što u aritmetici postoje operacije sabiranja, oduzimanja, množenja... tako i u logici postoje sledeće operacije: negacija, konjunkcija, disjunkcija, ekvivalencija i implikacija. Bitno je naučiti napamet pravila ovih operacija.

1. Negacija
Negacija nekog iskaza [inlmath]p[/inlmath] zapisuje se [inlmath]\lnot p[/inlmath] i definiše se na sledeći način: Negacija iskaza je tačna samo u slučaju kada je iskaz netačan.
Istinitosnu vrednost negacije možemo predstaviti sledećom tabelom:

[inlmath]\tau(p)[/inlmath] [inlmath]\tau(\lnot p)[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\bot[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\top[/inlmath]

Kao što se i vidi na tabeli, ako je iskaz tačan onda je njegova negacija netačna i obrnuto, ako je iskaz netačan onda je njegova negacija tačna.

2. Konjunkcija
Za razliku od negacije, za konjunkciju su potrebna dva iskaza. Konjunkciju obeležavamo sa [inlmath]\land[/inlmath] i čitamo kao veznik „i“. Konjunkcija se definiše na sledeći način: Konjunkcija je tačna samo kada su oba iskaza tačna.
Istinitosnu vrednost konjunkcije možemo predstaviti sledećom tabelom:

[inlmath]\tau(p)[/inlmath] [inlmath]\tau(q)[/inlmath] [inlmath]\tau(p\land q)[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\top[/inlmath] [inlmath]\top[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\top[/inlmath] [inlmath]\bot[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath]

3. Disjunkcija
Disjunkciju dva iskaza obeležavamo sa [inlmath]\lor[/inlmath] (čita se „ili“) i definišemo je na sledeći način: Disjunkcija je netačna samo onda kada su oba iskaza netačna.
Vrednosti disjunkcije dva iskaza predstavljamo sledećom tabelom:

[inlmath]\tau(p)[/inlmath] [inlmath]\tau(q)[/inlmath] [inlmath]\tau(p\lor q)[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\top[/inlmath] [inlmath]\top[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\bot[/inlmath] [inlmath]\top[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\top[/inlmath] [inlmath]\top[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath]

4. Ekvivalencija
Ekvivalenciju dva iskaza obeležavamo dvosmernom strelicom [inlmath]\iff[/inlmath]. Definišemo je na sledeći način: Ekvivalencija dva iskaza je tačna samo onda kada su oba iskaza tačna ili oba iskaza netačna, ili sledećom tabelom:

[inlmath]\tau(p)[/inlmath] [inlmath]\tau(q)[/inlmath] [inlmath]\tau(p\iff q)[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\top[/inlmath] [inlmath]\top[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\top[/inlmath] [inlmath]\bot[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath] [inlmath]\top[/inlmath]

O ekvivalenciji se može razmišljati kao o znaku jednakosti, tj. ekvivalencija je tačna samo onda kada iskazi s obe strane znaka ekvivalencije imaju istu istinitosnu vrednost. Operaciju ekvivalencije možemo da čitamo na sledeći način: „ako i samo ako“, „je potreban i dovoljan uslov“, „je ekvivalentno“.

5. Implikacija
Implikaciju obeležavamo sa [inlmath]\,\Longrightarrow\,[/inlmath] i definišemo je na sledeći način: Implikacija je netačna samo onda kada je prvi iskaz tačan a drugi netačan.
Operacija implikacije se čita kao: „iz [inlmath]p[/inlmath] sleduje [inlmath]q[/inlmath]“, „ako [inlmath]p[/inlmath] tada [inlmath]q[/inlmath]“. Obrati pažnju da ne postoji operacija [inlmath]\,\Longleftarrow\,[/inlmath], tj. znak implikacije je uvek okrenut ka desnoj strani.

[inlmath]\tau(p)[/inlmath] [inlmath]\tau(q)[/inlmath] [inlmath]\tau(p\,\Longrightarrow\,q)[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\top[/inlmath] [inlmath]\top[/inlmath]
[inlmath]\top[/inlmath] [inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\top[/inlmath] [inlmath]\top[/inlmath]
[inlmath]\bot[/inlmath] [inlmath]\bot[/inlmath] [inlmath]\top[/inlmath]

Operacija negacije predstavlja unarnu operaciju, tj. koristi samo jedan iskaz, dok su za ostale operacije potrebna dva iskaza i one predstavljaju tzv. binarne operacije.

U algebri iskaza koriste se zagrade koje označavaju operacije koje se prve izvršavaju. Negacija je operacija najvišeg prioriteta, zatim konjunkcija i disjunkcija, koje su međusobno ravnopravne, pa tek onda ekvivalencija i implikacija, koje su, takođe, međusobno ravnopravne.
Iskazne formule su iskazi formirani od drugih iskaza, kao i logičkih operacija i zagrada. Iskazne formule koje su uvek tačne nazivamo tautologije. Iskazne formule koje su uvek netačne nazivamo kontradikcije.

Poznatije tautologije

[inlmath]\left.\begin{array}{l}
(p\land q)\iff(q\land p)\\
(p\lor q)\iff(q\lor p)\\
(p\iff q)\iff(q\iff p)
\end{array}\right\}[/inlmath] – zakoni komutativnosti

[inlmath]\left.\begin{array}{l}
\bigl(p\land(q\land r)\bigr)\,\Longrightarrow\,\bigl((p\land q)\land r\bigr)\\
\bigl(p\lor(q\lor r)\bigr)\,\Longrightarrow\,\bigl((p\lor q)\lor r\bigr)
\end{array}\right\}[/inlmath] – zakoni asocijativnosti

[inlmath]\left.\begin{array}{l}
\bigl(p\lor(q\land r)\bigr)\,\Longrightarrow\,\bigl((p\lor q)\land(p\lor r)\bigr)\\
\bigl(p\land(q\lor r)\bigr)\,\Longrightarrow\,\bigl((p\land q)\lor(p\land r)\bigr)
\end{array}\right\}[/inlmath] – zakoni distribucije

[inlmath]p\lor\lnot p[/inlmath] - princip isključenja trećeg
[inlmath]\lnot\lnot p\iff p[/inlmath] - princip dvojne negacije
[inlmath](p\,\Longrightarrow\,q)\iff(\lnot q\,\Longrightarrow\,\lnot p)[/inlmath] - pravilo kontrapozicije
[inlmath](p\,\Longrightarrow\,q)\iff(\lnot p\lor q)[/inlmath] – definicija implikacije
[inlmath]p\land(p\,\Longrightarrow\,q)\;\Longrightarrow\;q[/inlmath] - modus ponens
[inlmath]\bigl(\lnot p\,\Longrightarrow\,(q\land\lnot q)\bigr)\;\Longrightarrow\;p[/inlmath] - svođenje na protivrečnost (reductio ad absurdum)

[inlmath]\left.\begin{array}{l}
\lnot(p\lor q)\iff\lnot p\land\lnot q\\
\lnot(p\land q)\iff\lnot p\lor\lnot q
\end{array}\right\}[/inlmath] - deMorganovi zakoni

[inlmath]\bigl((p\lor q)\land(p\,\Longrightarrow\,r)\land(q\,\Longrightarrow\,r)\bigr)\;\Longrightarrow\;r[/inlmath] - dokaz slučajevima
[inlmath]\bigl((p\,\Longrightarrow\,q)\land(q\,\Longrightarrow\,r)\bigr)\;\Longrightarrow\;(p\,\Longrightarrow\,r)[/inlmath] - silogizam

Kvantifikatori
Potrebno je još pomenuti i takozvane kvantifikatore (kvantore). Oni označavaju postojanje nekih elemenata koji imaju određenu osobinu. Postoje dva kvantifikatora:

1. Egzistencijalni kvantifikator [inlmath]\exists x[/inlmath] (čita se „postoji _ takav da...“), označava da postoji bar jedan [inlmath]x[/inlmath] takav da ima neku određenu osobinu.

2. Univerzalni kvantifikator [inlmath]\forall[/inlmath] (čita se „za svaki _...“), označava da svi elementi imaju određenu osobinu.

Često se kvantifikatori upotrebljavaju u ograničenom smislu, tj. upotrebljavamo ih samo za elemente nekog određenog skupa. Tada za te kvantifikatore kažemo da su ograničenog opsega i to beležimo [inlmath](\forall x\in X)[/inlmath] ili [inlmath](\exists y\in Y)[/inlmath]

Kvantifikator možemo da negiramo po sledećem pravilu:
1. [inlmath]\lnot(\forall x)A\iff(\exists x)\lnot A[/inlmath]
Možemo da tumačimo na sledeći način: Nisu svi [inlmath]x[/inlmath]-evi takvi da imaju osobinu [inlmath]A[/inlmath] je isto što i da postoji bar jedan [inlmath]x[/inlmath] takav da nema osobinu [inlmath]A[/inlmath].

2. [inlmath]\lnot(\exists x)A\iff(\forall x)\lnot A[/inlmath]
Rečima objašnjeno: Ne postoji [inlmath]x[/inlmath] takav da poseduje osobinu [inlmath]A[/inlmath] je isto što i da svaki [inlmath]x[/inlmath] nema osobinu [inlmath]A[/inlmath].

Logičke funkcije
Posmatrajmo rečenicu: Broj [inlmath]a[/inlmath] je veći od broja [inlmath]b[/inlmath] ili [inlmath]a>b[/inlmath]. Ova rečenica je izjavna ali ne možemo znati njenu istinitosnu vrednost, zato što ne znamo koji su brojevi [inlmath]a[/inlmath] i [inlmath]b[/inlmath]. Dajući ovim promenljivama izvesne vrednosti, gorenavedena rečenica postaje iskaz i dobija svoju istinitosnu vrednost. Za takve rečenice kažemo da su iskazne (logičke) funkcije. Iskazne funkcije obeležavamo sa [inlmath]P(q)[/inlmath]. Iskazne funkcije mogu imati i više elemenata, pa je onda njihov domen uređena [inlmath]n[/inlmath]-torka promenljivih [inlmath]P(q_1,q_2,\ldots,q_n)[/inlmath]. Svaka iskazna funkcija ima predikat koji označava odnos između promenljivih. U našoj rečenici [inlmath]a>b[/inlmath] predikat je „...je veće od...“ tj. [inlmath]>[/inlmath]

Hvala na pažnji. Ako imate pitanja slobodno otvorite novu temu, rado ćemo vam pomoći.
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 385 puta
Pohvaljen: 641 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Povratak na MATEMATIČKA LOGIKA

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 31 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 28. Mart 2024, 17:00 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs