IzjavniRačun Flashcards
Zapišite resničnostno tabelo za izjavni veznik
negacija, konjunkcija, disjunkcija, implikacija, ekvivalenca
Kakšen je prednostni vrstni red izjavnih veznikov ∧, ∨, ⇒, ¬, ⇔?
¬, ∧, ∨, ⇒, ⇔
Naj bo n ∈ N naravno število. Koliko različnih n-mestnih izjavnih veznikov
obstaja? Odgovor dobro utemeljite.
Š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}
Kako so definirani izjavni izrazi? Navedite vse štiri točke definicije.
-Kaj vse so izjavni izrazi..
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
Kaj je izjava?
Izjava je vsak stavek, ki je bodisi resničen, bodisi neresničen
Kako delimo izjave?
a. Po vsebini na: resnične (1), neresnične/lažne (0)
b. Po obliki na: osnovne/enostavne, sestavljene
Naštej nekaj izjavnih veznikov! Po mestnosti.
a. Enomestni: negacija
b. Dvomestni: konjunkcija, disjunkcija, implikacija, ekvivalenca
Kako je definirana ekskluzivna disjunkcija?
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.
Kaj je resničnostna tabela izjavnega izraza?
Resničnostna tabela izjavnega izraza za vsak nabor logičnih vrednosti izjavnih spremenljivk
pove logično vrednost izjavnega izraza.
Kaj je tavtologija?
Tavtologija je izjava, ki je »vedno« resnična.
Kaj je protislovje?
Protislovje je izjava, ki je »vedno« neresnična.
Kdaj je izjavni izraz nevtralen?
Izjavni izraz je nevtralen, če ni ne tavtologija, ne protislovje
Napiši nekaj primerov tavtologije!
Tipične tavtologije so: p V ⌐p p => p p <=> p
Napiši nekaj primerov protislovja!
Tipična protislovja so: p Ʌ ⌐p ⌐(p => (q => p)) p <=> ⌐p
Kdaj sta izjavna izraza A in B enakovredna?
Izjavna izraza A in B sta enakovredna, če imata pri veh naborih vrednosti izjavnih
spremenljivk enako vrednost. V tem primeru pišemo A ~ B
Kaj pravi izrek o enakovrednih izjavnih izrazih?
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
Kaj so zakoni izjavnega računa?
Nekateri pari enakovrednih izjavnih izrazov imajo posebna imena. Takim izjavnim izrazom pravimo zakoni izjavnega računa.
Kako pokažemo, da sta izjavna izraza enakovredna?
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.
Kako pokažemo, da sta izjavna izraza neenakovredna?
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
Kaj je disjunktivna normalna oblika?
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.
Kako izjavnemu izrazu A določimo izjavni izraz ADNO?
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.
Kaj je konjuktivna normalna oblika?
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.
Kako izjavnemu izrazu A določimo izjavni izraz AKNO?
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.
Kateri izjavni izrazi imajo DNO?
Vsak izjavni izraz, ki ni protislovje ima DNO.
Kateri izjavni izrazi imajo KNO?
Vsak izjavni izraz, ki ni tavtologija, ima KNO.
Kaj je posledica izjavnih izrazov DNO in KNO?
Za vsak izjavni izraz A obstaja enakovreden izjavni izraz B, ki vsebuje samo veznike: negacija, konjunkcija, disjunkcija (polni nabori)
Ali je DNO enolično določena?
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.
Kdaj pravimo, da je družina izjavnih veznikov N poln nabor?
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.
Naštej nekaj polnih naborov!
Polni nabori so: {⌐, Ʌ, V} {⌐, Ʌ} {⌐, V} {⌐, =>} {0, =>}
Kako v praksi pokažemo, da je nabor izjavnih veznikov N poln?
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
Navedite oba de Morganova/distributivnostna/absorbcijska zakona izjavnega
računa in enega od njiju dokažite.
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
