Iz Wikipedije, proste enciklopedije

Dobrodošli v Peskovniku Wikipedije! Na tej strani lahko po mili volji vadite in preizkušate urejanje. Za urejanje kliknite tukaj ali zavihek uredite stran zgoraj (oziroma pri nekaterih brskalnikih v meniju pogled), vnesite spremembe in, ko ste končali, kliknite gumb Shrani stran. Vsebina tu ne bo ostala trajno. Stran na vsake toliko izpraznimo. Prosimo vas, da v peskovnik(-e) ne dodajate avtorsko zavarovane, žaljive ali profane vsebine. Če imate glede Wikipedije kakršna koli vprašanja, jih postavite pod lipo. Hvala! Ta stran je virtualni peskovnik Wikipedije. Resnične peskovnike opisuje članek peskovnik. Za eksperimentiranje lahko uporabljate tudi predloge X1, X2, X3, X4, X5 in X6.

Bližnjica: WP:PK WP:PESEK Več podatkov: Dobrodošli, novinci Uvod v Wikipedijo Najpogostejša vprašanja

[uredi] IZJAVNI RAČUN

Izjava je stavek, ki je resničen ali neresničen. Vsak stavek pa ni izjava.

Na primer:

Zapri okno!   ni izjava- ukazi, pogojni in velelni stavki niso izjave
Danes dežuje. je izjava

Izjave po vsebini ločimo na resnične (pripada jim logična vrednost 1) in na neresnične (pripada jim logična vrednost 0). Po zgadbi pa jih ločimo na enostavne in sestavljene.

Na primer:

Zunaj je 40°C.   - neresnična, enostavna izjava
Peter sedi na vrtu. - enostavna izjava
Zunaj sije sonce in Peter sedi na vrtu.  - sestavljena izjava

Izjave sestavljamo z izjavnimi vezniki, ti so lahko enomestni (ni res, da ...), dvomestni (... in ..., ... ali..., če ...,potem...) ali pa tromestni (če ...,potem ..., sicer...).

Resničnost sestavljene izjave je odvisna samo od resničnosti sestavnih delov. Zato lahko izjavne veznike definiramos pomočjo resničnostnih tabel.

[uredi] Logični izjavni vezniki

majaaaaaaA:

oznaka: ¬

¬A je resnična natanko tedaj, ko je A neresničen.

A	¬A
0	1
1	0

'Kmaja

oznaka: ∧

A ∧ B je resnična natanko tedaj, ko sta obe izjavi A in B resnični.

A B	A ∧ B
0 0	0
0 1	0
1 0	0
1 1	1

'majaA

oznaka: ∨

A ∨ B je resnična natanko tedaj, ko je vsaj ena od izjav A in B resnična.

maja

A B	A ∨ B
0 0	0
0 1	1
1 0	1
1

IMPLIKACIJA

oznaka: =>

A => B je neresničen natanko tedaj, ko je A resničen in B lažen.

A... antecedens

B... konsekvens

A B	A => B
0 0	1
0 1	1
1 0	0
class="wikitable"
1

'maja^{Nadpisano besedilo{| class="wikitable" |- Nadpisano besedilo |}}

oznaka: <=>

Ekvivalenca A <=> je resnična

|}[[Kategorija: natanko tedaj, ko imata A in B isto]]logično vrednost.

A B	A <=> B
0 0	1
0 1	0
1 0	0
1 1	1

[uredi] Dogovor o opuščanju oklepajev

Če z oklepaji ni drugače določeno, velja:

• negacija veže močneje kot konjunkcija
• konjunkcija veže močneje kot disjunkcija
• disjunkcija veže močneje kot implikacija
• implikacija veže močneje kot ekvivalenca

negacija (¬) -> konjunkcija (∧) -> disjunkcija (∨) -> implikacija (=>) -> ekvivalenca (<=>)

Če imam istovrstne veznike jih združujem od leve proti desni.

Primer ekvivalence: A => B ∨¬ C <=> A ∧ D pomeni:

( ( A => ( B ∨ ( ¬C ) ) ) <=> ( A ∧ D ) )

vrstni red:

• () negacija
• () konjunkcija
• () disjunkcija
• () implikacija
• () ekvivalenca

[uredi] Izjavni izrazi

Osnovne izjave označujemo s črkami p, q, r... - to so izjavne spremenljivke.

Namesto o izjavah govorimo raje o izjavnih izrazih.

DEFINICIJA:

• Izjavni konstanti 0 in 1 sta izjavna izraza.
• Izjavne spremenjlivke p, q, r,... so tudi izjavni izrazi.
• Če je F n-mestni izjavni veznik in so A₁, A₂,...A_n izjavni izrazi, je tudi F(A₁, A₂,...A_n) izjavni izraz.
  • če je A izjavni izraz, je tudi ¬ (A) izjavni izraz.
  • če je * ∈ {∧, ∨, =>, <=>} in sta A in B izjavna izraza, potem je tudi (A) * (B) izjavni izraz.

Primer: 0, 1, p, q, r ¬ p <=> ¬(p), p => q, p => q => p, q ∧ (p => ¬r)

[uredi] Konstrukcijsko drevo

Vsakemu izjavnemu izrazu pripada konstrukcijsko drevo.

Primer:

   q  ∧ (p => ¬ r)
   /              \
  q             p => ¬ r
               /      \
               p       ¬ r
                        \ 
                         r

Izjavni izraz A nastopa v izjavnem izrazu B, če je A v eni izmed "vrstic" kontrukcijskega drevesa B.

Primer: B = q ∧ (p => ¬ r) A = q, p, r => q, p => q => p

[uredi] Resničnostna tabela

Vsakemu izjavnemu izrazu pripada tudi resničnostna tabela.

Na primer:

q ∧ (p => ¬ r)	p => ¬ r	¬ r	p q r
0	1	1	0 0 0
0	1	0	0 0 1
1	1	1	0 1 0
1	1	0	0 1 0
0	1	1	1 0 0
0	0	0	1 0 1
1	1	1	1 1 0
0	0	0	1 1 1

Možni nabori: 2^x;x - število izjavnih spremenljivk

DEFINICIJA

• Izjavni izraz je TAVTOLOGIJA, če je resničen pri vseh vrednostih izjavnih spremenljivk, ki v njem nastopajo.
• Izjavni izraz je PROTISLOVJE, če je neresničen pri vseh vrednostih izjavnih spremenljivk, ki v njem nastopajo.

Če izjavni izraz ni niti tavtologija, niti protislovje, ravimo da je NEVTRALEN.

• Izjavna izraza A in B sta ENAKOVREDNA, če imata pri vseh naborih vrednosti izjavnoh spremenljivk isto vrednost. V tem primeru pišemo A ~ B.
  • Izjavna izraza A in B sta enakoredna, natanko tedaj, ko je njuna ekvivalenca (A <=> B) tavtologija.
  • A in B sta enakovredna, ko imata vedno isto logično vrednost, torej 1, kadar je A <=> B - tavtologija.

[uredi] Zakoni izjavnega računa

Nekateri pari enakovrednih izjavnih izrazov imajo posebna imena. To so zakoni izjavnega računa. A, B in C so poljubni izrazi.

[uredi] Polni nabori izjavnih veznikov

Primer: Izjavni izraz A s tabelo:

A	p q r
0	0 0 0
1	0 0 1
0	0 1 0
1	0 1 1
1	1 0 0
1	1 0 1
0	1 1 0
1	1 1 1

A je resničen natanko tedaj, ko je:

• p neresničen, q neresničen in r resničen
• p neresničen, q resničen in r resničen
• p resničen, q neresničen in r neresničen
• p resničen, q resničen in r resničen
• p resničen, q resničen in r resničen

A <=> (¬ p ∧ ¬ q ∧ r) ∨ (¬ p ∧ q ∧ r) ∨ (p ∧ ¬ q ∧ ¬ r) ∨ (p ∧ ¬ q ∧ r) ∨ (p ∧ q ∧ r) ~ A

DNO - DISJUNKTIVNA NORMALNA OBLIKA izjavnega izraza A

DEFINICIJA

DNO izjavnega izraza A je izjavni izraz, ki je enakovreden A.

DNO je disjunkcija osnovnih konjunkcij.

Osnovna konjunkcija je konjunkcija osnovnih spremenljivk in/ali njihovijh negacij.

Osnovne konjunkcije ustrezajo vrsticam v katerih je A resničen. V taki konjunkciji vežemo resnične spremenljivke in negacije neresničnih spremenljivk.

Primer:

B	p q r
0	0 0 0
0	0 0 1
0	0 1 0
0	0 1 1
0	1 0 0
0	1 0 1
1	1 1 0
1	1 1 1

Izjavni izraz z resničnostno tabelo pa lahko sestavimo tudi drugače.

DEFINICIJA

KNO izjavnega izraza A je izjavni izraz, ki je enakovreden A.

KNO je konjunkcija osnovnih disjunkcij.

Osnovna disjunkcija je disjunkcija izjavnih spremenljivk in/ali njihovih negacij

Osnovne disjunkcije ustrezajo vrsticam v katerih je A neresničen. V taki disjunkciji vežemo spremenljivke, ki so lažne (0) in negacije resničnih (1) spremenljivk.

Vsak izraz, ki ni protislovje, ima DNO. Vsak izraz, ki ni tavtologija, ima KNO.

Posledica:

Vsak izjavni izraz ima enakovreden izjavni izraz, ki uporablja (vsebuje) samo negacijo, konjunkcijo in disjunkcijo.

Dokaz:

Vedno lahko vzamemo njegov DNO ali KNO, Vsaj ena od obeh možnosti obstaja:

DEFINICIJA

Množica N izjavnih veznikov je poln nabor, če za vsak izjavni izraz A obstaja enakovreden izjavni izraz B, ki uporablja le veznike iz nabora N.

Zgled:

{ ¬, ∧, ∨} je poln nabor

• Kako pokažemo, da je nabor izjavnih veznikov N polen?

  izberem nek poln nabor Z

  vsak veznik iz nabora Z izrazim z uporabo veznikov iz nabora N

Trditev: Nabori {¬, ∧}, {¬, ∨}, {¬, =>} in {=>, 0} so polni.

[uredi] Še nekaj izjavnih veznikov

STROGA (EKSKLUZIVNA) KONJUNKCIJA: A V B

Stroga konjunkcija je resnična natanko tedaj ko je resničen natanko eden od A, B.

A	B	A V B
0	0	0
0	1	1
1	0	1
1	1	0

SHEFFERJEV VEZNIK: AB

Shefferjev veznik je resničen natanko tedaj, ko vsaj ena od izjav A, B ni resnična.

A	B	AB
0	0	1
0	1	1
1	0	1
1	1	0

LUKASIEWICZEV VEZNIK: AB

Lukasiewiczev veznik je resničen natanko tedaj, ko nobena od izjav A, B ni resnična.

A	B	AB
0	0	1
0	1	0
1	0	0
1	1	0

Velja:

AB ~ ¬ (A <=> B)

AB ~ ¬ (A ∧ ∨ B) in

AB ~ ¬ (A ∧ ∨ B) ali

Dogovor o prednosti:

in imata isto vrednost kot ∧.

ima isto vrednost kot ∨.

[uredi] Sklepanje v izjavnem računu

Sklep je pravilen, če velja:

kadar so vse predpostavke resnične, je resničen tudi zaključek.

DEFINICIJA:

Zaporedje izjavnih izraziv A₁, A₂,..., A_n,B je pravilen,sklep s predpostavkami A₂,..., A_n in zaključkom B., če je zaključek resničen pri vseh tistih naborih logičnih vrednosti spremenljivk, pri katerih so resnične vse predpostavke.

Pišemo:

predpostavkami A₂,..., A_n|= B (iz predpostavk A₂,..., A_n logično sledi zaključek B).

[uredi] Pravila sklepanja

• Modus poneus (MP):

  A, A => B |= B

• Modus tollens(MT):

  A => B, ¬ B |= A

• Disjunktivni silogizem (DS):

  A ∨ B, ¬ A |= B

• Hipotetični silogizem (HS):

  A ∨ B, B => C |= A => C

• Združitev (Zd):

  A, B |= A ∧ B

• Poenostavitev (Po):

  A ∧ B |= A (B)

• Pridružitev (Pr):

  A |= A ∨ B

A₁,..., A_n |= B natanko tedaj, ko A₂,..., A_n=>B je tavtologija.

Dokaz pravilnosti sklepa:

Pravilnost sklepa (A₁,..., A_n|=B) lahko dokažemo tako, da sestavimo zaporedje izjavnih izrazov C₁,..., C_m:

zadnji izjavni izraz C_m je zaključek

za i=1,2,...,m velja:

C_i je ena izmed predpostavk

C_i je lahko tavtologija

C_i je lahko enakovreden kakšnemu od prejšnjih izjavnih izrazov v zaporedju

C_i logično sledi iz prejšnjih izrazov po enem od pravil sklepanja.

Kako dokazati, da sklep ni pravilen?

Poiskati je potrebno nabor vrednosti spremenljivk, pri katerem so vse predpostavke resnične, zaključek pa napačen (protiprimer).

[uredi] Pomožni sklepi

Pogojni sklep (PS):

PS uporabljamo, če je zaključek sklepa implikacija ali nekaj kar je podobno implikaciji.

A₁,..., A_n |= B=>C natanko tedaj,ko iz predpostavk A₁,..., A_n,B |=C.

Sklep s protislovjem (RA-reductio absurnum):

RA lahko uporabimo kadarkoli.

A₁,..., A_n |= B natanko tedaj, ko iz A₁,..., A_n,¬B |= 0.

Analiza primerov (AP):

AP uporabljamo takrat, ko ima ena od predpostavk obliko disjunkcije.

A₁,..., A_n , B₁ v B₂ |= C natanko tedaj,ko iz predpostavk A₁,..., :A_n, B₁ |=C in A₁,..., A_n, B₂ |=C.