PredikatniRačun

Question 1

Kaj je področje pogovora in kaj je predikat? Navedite primer.

Answer 1

a. Področje pogovora je neprazna množica (ljudje, številke, živali).
b. Predikati so logične funkcije, ki za svoje argumente uporabljajo elemente
področja pogovora

Question 2

Kaj so enomestni predikati in kaj so dvomestni predikati? Navedite po en
primer za vsakega od njiju.

Answer 2

a. Pri danem področju pogovora enomestni predikati opisujejo lastnost
elementa
i. x**2 je pozitivno število

b. dvomestni pa opisujejo relacijo med elementoma.
i. x je večje od y

Question 3

Katera kvantifikatorja poznate?

Answer 3

a. ∀ “za vsak”
i. ∀x ∈ D, P(x) je izjava, ki je resnična natanko takrat, ko imajo vsi
elementi iz D lastnost P. Sicer je neresnična.

b. ∃ “obstaja”
i. ∃x ∈ D, P(x) je izjava, ki je resnična natanko takrat, ko obstaja
element iz D , ki ima lastnost P. Sicer je neresnična

Question 4

Kaj so predikati?

Answer 4

Predikati so logične funkcije, ki za svoje argumente lahko dobijo elemente področja
pogovora. Če v predikate vstavljamo elemente področja pogovora dobimo izjave.

Question 5

Kako ločimo predikate?

Answer 5

Predikate ločimo po mestnosti. Enomestni predikati so lastnosti elementov v področju pogovora. Dvomestni predikati pa so relacije (ali tudi zveze) med elementi področja pogovora.

Question 6

Katera kvantifikatorja poznaš?

Answer 6

Univerzalni kvantifikator: ∀ (beremo: za vsak),

Eksistenčni kvantifikator: ∃ (beremo: obstaja)

Question 7

Kakšen je pomen univerzalnega kvantifikatorja?

Answer 7

∀x P(x) je izjava, ki je resnična natanko takrat, ko imajo vsi elementi področja pogovora
lastnost P. Sicer je neresnična. (Velja samo za izbrano interpretacijo)

Question 8

Kakšen je pomen eksistenčnega kvantifikatorja?

Answer 8

∃x P(x) je izjava, ki je resnična natanko takrat, ko obstaja (vsaj en) element področja
pogovora, ki ima lastnost P. Sicer je neresnična. (Velja samo za izbrano interpretacijo)

Question 9

Kaj so termi in kaj atomi?

Answer 9

Spremenljivkam in konstantam pravimo tudi termi.
Atomi predikatnega računa pa so na primer: P(x), P(a), P(x, y), Q(a, x) …
Atome dobimo tako, da terme vstavimo v predikate. Torej so to izjavne formule

Question 10

Kaj je doseg kvantifikatorja?

Answer 10

Doseg kvantifikatorja je najmanjši možen: najmanjša izjavna formula, ki jo preberemo desno od kvantifikatorja (skupaj z njegovo spremenljivko).
Kvantifikator veže svojo spremenljivko in proste spremenljivke z istim imenom v svojem dosegu.

Question 11

Katere spremenljivke so vezane in katere proste?

Answer 11

Vstop spremenljivke x je vezan, če se ta x nahaja v območju delovanja/dosega kvantifikatorja
∀x ali ∃x. Vstop spremenljivke, ki ni vezan, je prost.

Question 12

Kaj je interpretacija izjavne formule?

Answer 12

Interpretacija I izjavne formule W je sestavljena iz neprazne množice D, ki ji pravimo področje pogovora interpretacije. Poleg tega:
a. Vsakemu predikatu ustreza 0/1 logična funkcija v D
b. Vsaki konstanti določimo vrednost v D (ponavadi je implicitno določena že z imenomkonstante)
c. Vsaki prosti spremenljivki v W določimo vrednost v D, pri tem vsem prostim
spremenljivkam z istim imenom določimo isto vrednost iz D

Question 13

Če formula ni zaprta, kako jo dobimo?

Answer 13

Proste spremenljivke nadomestimo z elementi področja pogovora ali pa jih zapiramo z uporabo kvantifikatorjev. Na ta način dobimo zaprto formulo, ki je (ob izbranem PP in pomenu predikatov) izjava.

Question 14

Kaj pravi izrek o vpeljavi kvantifikatorjev?

Answer 14

Naj bo W formula. Z W(x/a) označimo formulo, ki jo dobimo tako, da v formuli W vse proste
vstope spremenljivke x nadomestimo z a.
Formula ∀�� je resnična v interpretaciji I, če je za vsak element področja pogovora d ∈ D
resnična formula W(x/d). Sicer je ∀�� neresnična.
Formula ∃�� je resnična v interpretaciji I, če v področju pogovora obstaja d ∈ D, za katerega
je formula W(x/d) resnična. Sicer je ∃�� neresnična.

Question 15

Kaj lahko poveš o preimenovanju spremenljivk?

Answer 15

Želja: če je W formula, potem imen prostih spremenljivk ne smemo spreminjati, če želimo pridelati enakovredno formulo. Vezane spremenljivke lahko preimenujemo tako, da ista spremenljivka (tj. spremenljivka z istim imenom):

a) Ne nastopa pri več kvantifikatorjih
b) Ni hkrati vezana in prosta

Question 16

Kdaj pravimo, da sta izjavni formuli enakovredni?

Answer 16

Izjavni formuli W in V sta enakovredni, če imata isto logično vrednost v vseh možnih interpretacijah. V tem primeru pišemo W ~ V

Question 17

Kdaj je izjavna formula splošno veljavna?

Answer 17

Izjavna formula W je splošno veljavna, če je resnična v vsaki interpretaciji

Question 18

Kdaj je izjavna formula neizpolnljiva?

Answer 18

Izjavna formula V je neizpolnljiva, če je neresnična v vsaki interpretaciji.

Question 19

Kaj je preneksna normalna oblika izjavne formule?

Answer 19

Trditev: Vsako izjavno formulo lahko zapišemo tako, da se kvantifikatorji nahajajo na začetku.
Izjavno formulo moramo preoblikovati tako da:
a) Preimenujemo spremenljivke
b) Namesto => in <=> uporabljamo ⌐, Ʌ, V
c) Kvantifikatorje postavimo na začetek formule z uporabo zakonov izjavnega računa Tako preoblikovani izjavni formuli pravimo prenexna normalna oblika izjavne formule.

Question 20

Kako iz formule naredimo izjavo?

Answer 20

a) Namesto spremenljivke vstavimo konstante

b) Formulo zapremo s kvantifikatorji

Question 21

Kaj lahko poveš o zamenjavi kvantifikatorjev?

Answer 21

Zamenjava raznovrstnih kvantifikatorjev (na primer: ∀x∃x) v splošnem ni možna.
Zamenjujemo lahko le istovrstne kvantifikatorje (na primer: ∀x∀y <=> ∀y∀x