IzjavniRačun

Question 1

Zapišite resničnostno tabelo za izjavni veznik

negacija, konjunkcija, disjunkcija, implikacija, ekvivalenca

Question 2

Kakšen je prednostni vrstni red izjavnih veznikov ∧, ∨, ⇒, ¬, ⇔?

Answer 2

¬, ∧, ∨, ⇒, ⇔

Question 3

Naj bo n ∈ N naravno število. Koliko različnih n-mestnih izjavnih veznikov
obstaja? Odgovor dobro utemeljite.

Answer 3

Število n-mestnih veznikov = 2 . N-izjavni veznik je neka n-člen operacija v

n**2

množici {0,1}, oz. to je preslikava oblike F:{0,1}**n -> {0,1}

Question 4

Kako so definirani izjavni izrazi? Navedite vse štiri točke definicije.
-Kaj vse so izjavni izrazi..

Answer 4

a. Izjavni kostanti 0,1 (laž in resnica) sta izjavna izraza
b. Izjavne spremenljivke (a, q, r) so izjavni izrazi
c. Če je A izjavni izraz, je tudi ¬A izjavni izraz
d. Če sta A in B izjavna izraza, so tudi (A ∧ B, A ∨ B, A ⇒ B, A ⇔ B) izjavni izrazi

Question 5

Kaj je izjava?

Answer 5

Izjava je vsak stavek, ki je bodisi resničen, bodisi neresničen

Question 6

Kako delimo izjave?

Answer 6

a. Po vsebini na: resnične (1), neresnične/lažne (0)

b. Po obliki na: osnovne/enostavne, sestavljene

Question 7

Naštej nekaj izjavnih veznikov! Po mestnosti.

Answer 7

a. Enomestni: negacija

b. Dvomestni: konjunkcija, disjunkcija, implikacija, ekvivalenca

Question 8

Kako je definirana ekskluzivna disjunkcija?

Answer 8

Ekskluzivna disjunkcija (A ⊻ B – beremo: A ekskluzivni ali B) je resnična natanko tedaj, ko
je natanko eden od izjavnih izrazov A in B resničen.

Question 9

Kaj je resničnostna tabela izjavnega izraza?

Answer 9

Resničnostna tabela izjavnega izraza za vsak nabor logičnih vrednosti izjavnih spremenljivk
pove logično vrednost izjavnega izraza.

Question 10

Kaj je tavtologija?

Answer 10

Tavtologija je izjava, ki je »vedno« resnična.

Question 11

Kaj je protislovje?

Answer 11

Protislovje je izjava, ki je »vedno« neresnična.

Question 12

Kdaj je izjavni izraz nevtralen?

Answer 12

Izjavni izraz je nevtralen, če ni ne tavtologija, ne protislovje

Question 13

Napiši nekaj primerov tavtologije!

Answer 13

Tipične tavtologije so: p V ⌐p p => p p <=> p

Question 14

Napiši nekaj primerov protislovja!

Answer 14

Tipična protislovja so: p Ʌ ⌐p ⌐(p => (q => p)) p <=> ⌐p

Question 15

Kdaj sta izjavna izraza A in B enakovredna?

Answer 15

Izjavna izraza A in B sta enakovredna, če imata pri veh naborih vrednosti izjavnih
spremenljivk enako vrednost. V tem primeru pišemo A ~ B

Question 16

Kaj pravi izrek o enakovrednih izjavnih izrazih?

Answer 16

Izjavna izraza A in B sta enakovredna natanko tedaj, ko je izraz A <=> B tavtologija. Za
enakovrednost izjavnih izrazov veljajo naslednje zveze:
a. A ~ A
b. Če A ~ B, potem B ~ A
c. Če A ~ B in B ~ C potem A ~ C

Question 17

Kaj so zakoni izjavnega računa?

Answer 17

Nekateri pari enakovrednih izjavnih izrazov imajo posebna imena. Takim izjavnim izrazom pravimo zakoni izjavnega računa.

Question 18

Kako pokažemo, da sta izjavna izraza enakovredna?

Answer 18

Dovolj je da pokažemo da imata izraza pri vsakem logičnem naboru vrednosti spremenljivk isto logično vrednost. Sestavimo resničnostno tabelo in pogledamo, če je v vseh vrsticah ista logična vrednost.

Question 19

Kako pokažemo, da sta izjavna izraza neenakovredna?

Answer 19

Dovolj je da pokažemo, da imata izraza pri vsaj enem (lahko tudi pri večih) logičnem naboru vrednosti spremenljivk različno logično vrednost. Sestavimo resničnostno tabelo in pogledamo, če se v kateri vrstici logični vrednosti razlikujeta

Question 20

Kaj je disjunktivna normalna oblika?

Answer 20

DNO izjavnega izraza A je izjavni izraz Adno, za katerega velja:
a. A ~ Adno
b. Adno je disjunkcija osnovnih konjunkcij
Osnovna konjunkcija je konjunkcija izjavnih spremenljivk in/ali njihovih negacij.

Question 21

Kako izjavnemu izrazu A določimo izjavni izraz ADNO?

Answer 21

ADNO lahko zgradimo tako, da za vsak nabor pravilnostne tabele, pri katerem je izraz A resničen, pripravimo eno osnovno konjunkcijo. V njej nastopajo v tem naboru resnične spremenljivke in negacije v tem naboru lažnih spremenljivk.

Question 22

Kaj je konjuktivna normalna oblika?

Answer 22

AKNO izjavnega izraza A je izraz AKNO, za katerega velja:
a. A ~ AKNO
b. AKNO je konjunkcija osnovnih disjunkcij
Osnovna disjunkcija je disjunkcija izjavnih spremenljivk in/ali njihovih negacij.

Question 23

Kako izjavnemu izrazu A določimo izjavni izraz AKNO?

Answer 23

AKNO lahko zgradimo tako, da za vsak nabor pravilnostne tabele, pri katerem je izraz A neresničen, pripravimo eno osnovno disjunkcijo. V njej nastopajo v tem naboru lažne spremenljivke in negacije v tem naboru resničnih spremenljivk.

Question 24

Kateri izjavni izrazi imajo DNO?

Answer 24

Vsak izjavni izraz, ki ni protislovje ima DNO.

Question 25

Kateri izjavni izrazi imajo KNO?

Answer 25

Vsak izjavni izraz, ki ni tavtologija, ima KNO.

Question 26

Kaj je posledica izjavnih izrazov DNO in KNO?

Answer 26

Za vsak izjavni izraz A obstaja enakovreden izjavni izraz B, ki vsebuje samo veznike: negacija, konjunkcija, disjunkcija (polni nabori)

Question 27

Ali je DNO enolično določena?

Answer 27

Ne. DNO dobimo na osnovi vrstic, kjer je A resničen. Pri tem pa ni nujno da vrstice izpisujemo po vrsti (na primer: od zgoraj navzdol). Vrstice (ki v DNO nastopajo kot osnovne konjunkcije) pa lahko med seboj tudi pomešamo – pri tem se vrednost izraza ne spremeni. Zaradi tega ne moremo trditi da je DNO enolično določena.

Question 28

Kdaj pravimo, da je družina izjavnih veznikov N poln nabor?

Answer 28

Družina izjavnih veznikov N je poln nabor, če za vsak izjavni izraz A obstaja enakovreden
izjavni izraz B, ki vsebuje samo veznike iz N.

Question 29

Naštej nekaj polnih naborov!

Answer 29

Polni nabori so: {⌐, Ʌ, V} {⌐, Ʌ} {⌐, V} {⌐, =>} {0, =>}

Question 30

Kako v praksi pokažemo, da je nabor izjavnih veznikov N poln?

Answer 30

To pokažemo tako, da naredimo naslednje:

a. Izberemo znan poln nabor izjavnih veznikov Z
b. Vsak veznik iz znanega nabora Z izrazimo samo z uporabno veznikov iz N

Question 31

Navedite oba de Morganova/distributivnostna/absorbcijska zakona izjavnega
računa in enega od njiju dokažite.

Answer 31

a. De morgan:
i. ¬(A ∨ B) ∼ ¬A ∧ ¬B
ii. ¬(A ∧ B) ∼ ¬A ∨ ¬B
b. Distributivnost:
i. (A ∨ B) ∧ C ∼ (A ∧ C) ∨ (B ∧ C)
ii. (A ∧ B) ∨ C ∼ (A ∨ C) ∧ (B ∨ C)
iii. (A ∨ B) ∧ C ∼ (A ∧ C) ∨ (B ∧ C)
c. Absorpcija:
i. A ∧ (A ∨ B) ∼ A
ii. A ∨ (A ∧ B) ∼ A