Logičke operacije i iskazi

Iskazna logika ima sledeće  ključne pojmove : iskaz, veznici, logičke operacije, iskazna formula, tautologija..

 

Iskazi, veznici

 

Definicija : Rečenica koja ima smisla i za koju se može utvrditi da li je tačna ili netačna, naziva se iskaz. 

Primer :

„Zemlja se okreće oko meseca“ – Netačan iskaz.

„2+5=7“- tačan iskaz.

„2 + 4 < 5“- netačan iskaz.

„Da li je ova rečenica iskaz?“ –nije iskaz.

Iskaze označavamo slovima  p, q, r , . . . , p1, q1, . . . , p2, q2, . . . .

 

Od iskaza gradimo nove iskaze povezujući ih sa iili, nije, ako .. onda, ako i samo ako. Veze nazivamo logičkim veznicima

Tačnost novog iskaza određujemo na osnovu tačnosti iskaza od kojih je sačinjen i značenja logičkih veznika u prirodnom jeziku.

U iskaznoj logici koriste se  sledeće logičke operacije : unarna (na jednom iskazu) operacija negacija i binarne (na dva iskaza) operacije  disjunkcije, konjukcije, implikacije i ekvivalencije.

Logičke operacije 

Disjunkcija iskaza

Definicija: disjunkcija redom iskaza p i q je iskaz “ p ili q“ u oznaci  p ∨ q, Koji je tačan ako i samo ako je bar jedan od iskaza tačan.

Primer:

„2+5=7 ili 2 + 4 < 5“ – tačan iskaz.

„2+5=7 ili 2 + 4 > 5.“ – tačan iskaz.

„Šećer je slan ili slon je riba“ -netačan iskaz.

Konjukcija iskaza 

Definicija: Konjukcija redom iskaza  p i q je iskaz  „p i q“, U oznaci   p ∧ q, koji je tačan ako i samo ako su oba iskaza tačna.

Primer:

„2+5=7 и 2 + 4 < 5.“- netačan iskaz.

Implikacija iskaza

Definicija : Implikacija redom iskaza  p i q je iskaz   „ako p onda  q“, U oznaci   p ⇒ q, koji je netačan ako i samo ako je iskaz p tačan, a iskaz q netačan.

Iskaz p je  pretpostavka (premisa ), a iskaz q je zaključak (konkluzija).

Primer:

„Iz 2 + 5 < 7 sledi 2 < 3“ – tačan iskaz.

„ako je  2 < 3 onda je  2+5=7“ -tačan iskaz.

„aкo je 2 < 3onda je  2+5<7“ -netačan iskaz.

„Ako voda mrzne na 100° onda je Beč glavni grad Austrije “ – tačan iskaz

Napomena: matematičku logiku ne interesuje značenje iskaza p i q, već samo njihova istinitost. Istinitost imolikacije p ⇒ q ne zavisi od značenja iskaza pi q , već samo od njihove istinitosti .

Implikaciju  p ⇒q možemo čitati na sledeći način:

„iz p sledi q“

„p povlači q“

„p inmplicira q“

„pje dovoljan uslov za  q“

„q je potreban uslov za  p“.

Primer:

Svakom od sledećih rečenica se tvrdi isto :

(1) Ako je prirodan broj deljiv sa 4 onda je deljiv i sa dva .

(2) Dovoljan uslov da prirodan broj bude deljiv sa 2 je da je on deljiv sa 4.

(3) Potrban uslov da prirodan broj bude deljiv sa 4 je da je on deljiv sa 2.

Ekvivalencija iskaza

Definicija:

Ekvivalencija redom iskaza  p i q je искaзje iskaz  „p ako i samo ako q“ ( p akko q), u oznaci p ⇔q, koji je tačan ako i samo ako su iskazi p i q oba tačna ili oba netačna (istih istinitosnih vrednosti).

Primer:

2 > 4 aккo 2 + 3 > 4 + 3. -tačan iskaz.

Ekvivalenciju  p ⇔ q možemo čitati na sledeći način:

„p je ekvivalentno sa q“

„p je potreban i dovoljan uslov za q“

„ako  p onda q i ako  q onda p“.

Negacija iskaza 
Definicija:

Negacija iskaza p ,  „nije p“, u oznaci  ¬p, je iskaz koji je tačanako i samo ako je iskaz p netačan.

Primer

„Nije 2=2“ -netačan iskaz.

Alfabet iskazne logike

Iskazna logika nastaje formalizacijom računa sa iskazima. Potrebno je odrediti skup simbola (alfabet) koji će se koristiti za građenje formula i pravila po kojima će se formirati formule.
Formule se posmatraju isključivo kao nizovi simbola, ne uzimajući u obzir bilo kakvo njihovo (moguće) značenje.

Definicija

Alfabet iskazne logike se sastoji od sledećih simbola:

skupa iskaznih slova (iskaznih promenljivih) P = {p1, p2, p3, …},

skupa logičkih veznika {∨, ∧,⇒,⇔, ¬},

skupa logičkih konstanti {⊤,⊥} ( logičke konstane mogu, ali ne moraju učestvovati u građenju formula),

skupa pomoćnih simbola {(, )} (zagrade).

Od ovih simbola po precizno utvrđenim pravilima grade se iskazne formule.

 

Iskazne formule

Definicija

Iskazne formule se definišu induktivno, na sledeći način:

  1.  Iskazna slova i logičke konstante su iskazne formule.
  2.  Ako su A i B iskazne formule, onda su i (A ∧ B), (A ∨ B), (A ⇒ B),(A ⇔ B) i ¬A iskazne formule.
  3.  Iskazne formule se dobijaju samo konačnom primenom pravila (1) i(2).

Primer

Sledeći nizovi simbola su iskazne formule:

p, q, ⊤, ⊥

(p ∧ ⊤), ¬q, (⊤ ∨ ⊥),

((p ∧ ⊤) ∨ ¬q), (¬(p ∧ ⊤)), (¬q ⇔ (⊤ ∨ ⊥)).

Sledeći nizovi simbola nije iskazna formula:(p ∨ q)(⇒ p)

Konvencije

Iskazne formule označavaćemo velikim latiničnim slovima A,B,C, . . . . Zapis A = B će značiti da su formule A i B sintaksno identične (jednake kao nizovi simbola).

U svakoj formuli učestvuje samo konačno mnogo iskaznih slova.

Zappis A = A(p1, p2, . . . , pn) će značiti da su sva iskazna slova formule A u skupu {p1, p2, . . . , pn}.

Da bi se izbeglo gomilanje zagrada, po dogovoru,

◮ Brišemo spoljašnje zagrade,

◮ ako su A1, . . . ,An iskazne formule, umesto

(. . . ((A1 ∧ A2) ∧ A3) ∧ • • • ∧ An−1) ∧ An pišemo A1 ∧ A2 ∧ • • • ∧ An.

◮za B važi slična konvencija,

◮ veznicima dajemo sledeći prioritet:

¬ najjače vezuje,

∧ i ∨ slabije vezuju,

⇒ i ⇔ najslabije vezuju.

Primer:

-Formulu ((¬p ∨ q) ⇒ r ) kraće zapisujemo ¬p ∨ q ⇒ r ,

-formulu ((p ⇒ ⊤) ∧ q) zapisujemo (p ⇒ ⊤) ∧ q

-p ⇒ ⊤ ∧ q znači (p ⇒ (⊤ ∧ q)).

Vrlo često ćemo prilikom dokazivanja raznih osobina formula, koristiti tzv.dokaz po složenosti iskaznih formula.

Ako treba dokazati da neka osobina O važi za sve iskazne formule, dovoljno je dokazati da tu osobinu imaju sva iskazna slova (Baza indukcije), i da iz pretpostavke da formule A i B imaju osobinu O sledi da i formule A ∧ B, A ∨ B, A ⇒ B, A ⇔ B, ¬A imaju tu osobinu (indukcijski korak).

Semantika iskazne logike

Semantički aspekt iskazne logike govori o značenju iskaznih formula.

Da bi se pravila za određivanje vrednosti iskazne formule precizno formalizovala uvodi se sledeća algebarska struktura: dvoelementni skup, čije elemente možemo označiti sa 0 i 1 ili  T i F  ili ⊤ i ⊥  (kao što ćemo mi učiniti) jedna unarna i četiri binarne operacija na datom skupu, koje ćemo označiti sa ¬, ∧, ∨,⇒,⇔ i koje zadajemo talicama

Definicija

Dvoelementna algebra ({⊤,⊥}, ∧, ∨,⇒,⇔, ¬) je iskazna algebra ako su⊤ i ⊥ dva različita znaka,

∧, ∨,⇒,⇔Binarne operacije skupa {⊤,⊥} date sledećim tablicama

 

 

Logičke operacije predstavljene istinitosnim tablicama.

primenom definicije logičke operacije negacija
Logičke operacije -disjunkcija
Logičke operacije -implikacija
Logičke operacije -ekvivalencija

 

I ¬ unarna operacija skupa  {⊤,⊥} tada tablicom

 

Logičke operacije -negacija

Tautologije 

Definicija:

Iskazna formula koja je tačna za sve vrednosti iskaznih slova naziva se tautologija.

 

Važne tautologije:

(1) p ⇒p (zakon refleksije za implikaciju)

(2) p ∨ ¬p (zakon isključenja trećeg)

(3) ¬(p ∧ ¬p) (zakon neprotivrečnosti)

(4) (¬p ⇒ ⊥) ⇒p (svodjenje na apsurd)

(5) ¬¬p ⇔p (zakon dvojne negacije)

(6) p ∧ p ⇔p, p ∨ p ⇔p (zakon idempotencije)

(7) p ∨ ⊥ ⇔p, p ∨ ⊤ ⇔ ⊤

      p ∧ ⊤ ⇔p, p ∧ ⊥ ⇔ ⊥

     (p ⇒ ⊥) ⇔ ¬p, (⊤ ⇒ p) ⇔p

(8) p ∧ q ⇔q ∧ p, p ∨ q ⇔q ∨ p (zakoni komutacije)

(9) p ∧ (p ⇒q) ⇒ q (MP-modus ponens)

(10 ((p ⇒q) ∧ ¬q) ⇒ ¬p (MT-modus tollens)

(11) ((p ⇒q) ⇒p) ⇒ p (Pirsov zakon)

(12) p ∧ (p ∨ q) ⇔p, p ∨ (p ∧ q) ⇔p (zakoni apsoppcije)

(13) (p ⇒q) ⇔ (¬q ⇒ ¬p) (zakon kontrapozicije)

(14) ¬(p ∧ q) ⇔ ¬p ∨ ¬q,¬(p ∨ q) ⇔ ¬p ∧ ¬q (De Morganovi zakoni)

(15) (p ⇒q) ⇔ ¬p ∨ q (zakon uklanjanja implikacije)

(16) (p ⇔q) ⇔ (p ⇒q) ∧ (q ⇒p) (zakon uklanjanja ekvivalencije)

(17) p ∧ (q ∧ r ) ⇔ (p ∧ q) ∧ r ,p ∨ (q ∨ r ) ⇔ (p ∨ q) ∨ r (zakoni asocijacije)

(18) p ∧ (q ∨ r ) ⇔ (p ∧ q) ∨ (p ∧ r ),

        p ∨ (q ∧ r ) ⇔ (p ∨ q) ∧ (p ∨ r ) (zakoni distribucije)

(19) (p ⇒ q) ⇒ ((q ⇒ r ) ⇒ (p ⇒ r )) (tranzitivnost implikacije)

(20) (p ⇔ q) ∧ (q ⇔r ) ⇒ (p ⇔ r ) (tranzitivnost ekvivalencije)

 

Tablični metod

Istinitosna vrednost date iskazne formule zavisi samo od vrednosti iskaznih slova koja u njoj učestvuju.

Za formulu A(p1, . . . , pn) (sa n iskaznih slova) ima 2n različitih „kombinacija“ vrednosti iskaznih slova.

Ovaj postupak se sastoji u proveri istinitosne vrednosti formule u svih 2n slučajeva, što se prikazuje tablicom.

 

Primer

 

Iz tablice istinitosti za formulu A = (p ⇒q) ⇔ ¬p ∨ q

zaključujemo da je ova formula tautologija.

Zaglavlje tablice formiramo tako što najpre unesemo sva iskazna slova (u ovom sličaju p i q), a zatim postavljamo manje celine za koje možemo utvrditi istinitost. Koristimo tablice (definicije) odgovarajuče logičke operacije.

Centralna operacija ove formule je ekvivalencija. Leva strana fomule je p⇒q ( iskazi  su postavljeni u tablici ) i možemo utvrditi tačnost ove implikacija. Nju unosimo u zaglavlje tablice. Desna strana formule je  ¬p∨q  . Za navedenu disjunkciju ne možemo utvrditi tačnost jer nije određena tačnost ¬p. Iz tog razloga najpre pišemo ¬p, a zatim ¬p∨q . Kada odredimo istinitosnu vrednost leve i desne strane ispituje se centralna operacija ⇔.

Broj redova u tablici izračunava se kao 2n, gde je n broj iskaznih slova u formuli. u našem slučaju 22 =4. 

Istinitosnu vrednost iskaza postavljamo tako da pokrijemo sve moguće rasporede( za prvi iskaz dva tačna, dva netačna, a za drugi naizmenično tačno netačno).

Za formule sa 3 iskazna slova broj redova je 8 (postavljamo za prvi iskaz 4 tačna, četiri netačna,za drugi  iskaz dva tačna, dva netačna, a za treći naizmenično tačno netačno)

 

 

Rešeni zadaci 

Primeri

 Dati su iskazi  p i q. Naći vrednost formule  F ako je   a) F: (p∧¬q)⇔p   ; b)F:(¬p∨q)⇒(p∧q)   a za iskaze  p i q važi

Najpre određujemo istinitosnu vrednost iskaza  p . Sređujemo levu i desnu stranu i utvrđujemo da li su jednake. Ako jesu potvrđena je tačnost iskaza i njegova istinitosna vrednost je T a ako nisu tada je istinitosna vrednst  ⊥ (nete).

τ(p)=Τ ili  τ(p)=⊥ (tau od r)

V(p)=T ili  V(q)=⊥

Mešovite brojeve prevodimo u razlomke.

Određujemo NZS .

Izvršavamo naznačene operacije .

 

Leva strana iskaza nije jednaka desnoj.

Zaključujemo da je iskaz netačan. V(p)=⊥

Postupak ponavljamo za iskz  q.

 

Leva strana iskaza jednaka je desnoj, pa zaključujemo da je istinitasna vrednost iskaza je T .

V(q)=T.

a)U formuli    (p∧¬q)⇔p menjamo iskazna slova sa njihovom istinitosnom vrednošću

(⊥∧¬T)⇔⊥    ,primenom definicije logičke operacije negacija ¬T=⊥

(⊥∧⊥)⇔⊥      ,primenom definicije logičke operacije konjukcija ⊥∧⊥=⊥

⊥⇔⊥             ,slično rešavamo ekvivalenciju

T                   , za date iskaze formula je tačna 

 

b) U formuli  (¬p∨q)⇒(p∧q)  menjamo iiskazna slova istinitosnom vrednošću tih iskaza.

(¬⊥∨T)⇒(⊥∧T)    ,rešavamo negaciju

(T∨T)⇒(⊥∧T)       ,rešavamo disjunkciju i konjikciju

T⇒⊥                     ,rešavamo implikaciju

⊥                          ,zaključujemo za date iskaze formule nije tačna.

 

Ispitati da li su sledeće formule tautologije :

I) (¬q⇒¬p)⇒(p⇒q)

II) (¬p⇒q)⇔((r∨p)∧q

Iskazna logika Il3
Test

Povratak na stranu Matematička logika i skupovi