BAZA ZNANJA

Kurs: Matematika za prvi razred srednje škole

Modul: Logika i skupovi

Autor:

Naziv jedinice: Kvantori

Definisanje kvantora

U prethodnoj lekciji bilo je reči o tome šta predstavlja jedan iskaz, a šta ne.
Tako  npr. rečenica „ x+2=5“ nije bila iskaz, zato što se nije mogla utvrditi njena istinitosna vrednost. Ako umesto x stavimo broj 3, ona jeste tačna, ali ako stavimo bilo koju drugu vrednost, dobićemo netačnu rečenicu.

Međutim, dovoljno je da prethodnu rečenicu samo malo preformulišemo:

     „ postoji x tako da je x+2=5“    ili na drugi način
     „ za svaki broj x je x+2=5“

Sada ovako formulisane rečenice jesu iskazi. Prva rečenica jeste tačna zato što zaista postoji broj koji zadovoljava ovu jednakost, dok je istinitosna vrednost druge rečenice netačna zato što ova jednakost ne važi za bilo koji broj.

Ako uvedemo sledeće oznake:

• ∀ x    - čitamo: „za svako x“
• ∃ x    - čitamo: „postoji x“

Onda prethodne rečenice možemo kraće zapisati:

• (∃ x )   (x+2=5)
• (∀ x)     (x+2=5)

Reči za svaki (ili proizvoljan, bilo koji) i postoji (ili za neki) zovu se kvantorima ili kvantifikatorima, a formule u kojima se oni pojavljuju sa još nekom promenljivom (kao u prethodnom primeru x) nazivaju se predikatskim formulama.

Uslovni kvantori

Često su u upotrebi i tzv. uslovni ili ograničeni kvantori. Takvi kvantori su sadržani u rečenicama:

      „ za svaki prirodan broj y, 3•y=6“  ili
      „ postoji ceo broj, a takav da a >-9“

Pošto skup prirodnih brojeva označavamo sa N, a skup celih brojeva sa Z, onda prethodne rečenice možemo zapisati:

( ∀ y∈N) (3•y=6)

(∃ a∈Z) (a >-9)

One su logički ekvivalentne sa:

 
(∀ y) (y∈N ⇒ 3•y=6)

(∃ a) (a∈Z ∧ a >-9)

Jasno je da je istinitosna vrednost prve rečenice netačna, a druge tačna.

Primer 1: Zapisati sledeće rečenice:

1. Postoji racionalan broj manji od 5
2. Svaki prirodan broj je pozivan

Rešenje:

1. (∃ x∈Q) (x<5)
2. ( ∀ y∈N) (y>0)

 
Negacija i kvantori

Kako se kvantori transformišu ukoliko je znak negacije ispred njih najbolje pokazuju takozvane valjane formule:

U ovim formulama je sa A označeno neko svojstvo koje ima x.

Pokažimo na jednom običnom primeru tačnost ovih formula.

Primer 2:   Neka je data rečenica: „ sve mačka su bele“. Logično, negacija ove tvrdnje je da nisu sve mačke bele, tj. da postoji mačka koja nije bela.

Ako nam x predstavlja mačku a A osobinu da je mačka bela, onda tvrdnju možemo zapisati matematičkim jezikom:

    (∀ x) A

Rekli smo da je negacija ovog tvrđenja da postoji mačka koja nije bela:

 (∃ x) ¬A

Dakle, dobijamo da važi valjana formula: ¬(∀ x) A ⇔ (∃ x) ¬A.

 
Primer 3: Napisati tvrđenje „postoji najveći prirodan broj“, a potom i njegovu negaciju.

Rešenje:

              „postoji najveći prirodan broj x“ možemo zameniti i sa

              „postoji prirodan broj y koji je veći od svakog drugog prirodnog broja x“.
  
               Poslednju rečenicu zapisujemo na sledeći način:
         
                                           (∃ y∈N) (∀ x∈N) (y>x)

Logička negacija ovog tvrđenja je da za svaki prirodan broj y postoji prirodan broj x koji je veći ili jednak sa njim (samim tim to znači da ne postoji najveći prirodan broj).
                
 (∀ y∈N) (∃ x∈N) (y≤x)

Dobili smo da važi: ¬((∃ y∈N) (∀ x∈N) (y>x)) ⇔ (∀ y∈N) (∃ x∈N) (y≤x).

Primer 4: Da li je tačna sledeća formula:  (∀ a∈Z) (∃ b∈Z) (a•b=0)?

Rešenje:

Trebalo bi ispitati da li je tačno da za svaki ceo broj a postoji ceo broj b, takav da je njihov proizvod nula.
Pošto je 0 takođe iz skupa Z, dovoljno je da za bilo koji izabrani broj a stavimo b=0 i dobijamo da je formula tačna.

Primer 5: Napisati negaciju sledeće rečenice:

(∃ x) ( x je iracionalan broj ∧ x+1>6)

Rešenje:
            
¬((∃ x) ( x je iracionalan broj ∧ x+1>6)) ⇔ (∀x) ( x∉I ∨ x+1≤6)
        
U poslednjoj negaciji primenjeno je De Morganovo pravilo ¬(p∧q)⇔¬q∨¬p.