Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Státnice > LGR > Flashcards

LGR Flashcards

1
Q

Atomicka formule

A

Zakladni prvek vyrokove logiky

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Mnozina At

A

Je mnozina atomickych formuli

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Jazyk vyrokove logiky

A

Je mnozina vsech formuli nad mnozinou At a je definovana jako

F(at) ::= a | T | F | (~F) | (F1 ^ F2)

kde:
a - atomicke formule
T, F - logicke konstanty
~ - negace, unarni log. spojky
^, U, =>, <=>… - binarni log. spojky

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Syntakticky strom formule

A

Rozbijim formuli podle operatoru a skladam strom na rekurzivni mensi podstromy

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Hloubka syntaktickeho stromu

A

Jestli narazil na at. promennou, T,F => vrat 0
Jestli narazil na negaci podformule => vrat 1+hl(podformule)
Jestli narazil na podformuli => vrat 1+max(hl(leva), hl(prava))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Mnozina podformuli formule F

A

Mejme formuli Fle(At). Mnozina vsech podmnozin (vzpomen si na Cantorovu vetu) je dana jako P(Fle(At)) a je to mnozina vsech moznych podformuli, ktere jsem schopen sestavit z puvodni formule.

Patri tam i ona sama, pak vsechny atomicke promenne a vsechny jejich podkombinace ktere vidim ve stromu

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Definice prirozene dedukce ve vyrokove logice VL

A

Je to dukazovy system

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Semantika vyrokove logiky

A

Prirazuje vyznam syntaktckym objektum,
napr Booleonovka logika prirazuje {0,1} jako pravda/nepravda

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Pravdivostni ohodnoceni formule Fle(At)

A

Je zobrazeni z Fle(At) do Bool, splnujici podminky
1. T = 1, F = 0
2. a^b = 1 <=> a=1 ^ b=1
3. a U b = 0 <=> a=0 ^ b=0
3. a=>b = 0 <=> a=1 ^ b=0 (z pravdy plyne lez)
4. a<=>b = 1 <=> a=b (ekvivalence jsou stejne)
5. ~a = 1 <=> a=0

Ja toto zobrazeni je jednoznacny - jakmile ohodnotim vstupni atomicke promenne -> pa ihned se cela formule ohodnoti sama jednoznacne

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Jak zjistit pravdivostni ohodnoceni zadane formule s ohodoncenymi at. prvky?

A

Sestavim strom a jdu nahoru od at. prvku a ohodnocuju kazdou operaci zvlast az dojdu k vyslednemu ohodnoceni nahore

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Pravidlo vylouceneho tretiho

A

Bez zadnych predpokladu mohu prohlasit, ze plati A nebo negace A

neco bude plati nebo neplati, nic jinyho nejde, nepotrebuje to zadny predpokald

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Logicky ekvivalentni formule f1 -||- f2

A

Jsou takove f1 a f2 pro ktere plati

f1 |- f2
f2 |- f2 // tedy z jedne plyne druha a naopak

„Je pátek nebo sobota.“
„Není pravda, že není pátek a zároveň není sobota.“

existuje obostranny dukaz

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Semanticka ekvivalence dvou formuli

A

Je to relace ekvivalence
Pro vsechny formule A,B,C plati:
1. a |=| a //reflexivita
2. (a|=|b) => (b|=|a) //symetrie
3. tranzitivita… podobne

Kdyz a|=|b pak a -||- b

Rika mi to neco jako ze tyto formule rikaji v podstate totez - tj pokud plati jedna, tak plati i druha, a pokud neplati jedna, tak enplati ani druha. Jsou pravdivostne ohodnoceny stejne za vsech okolnosti.

Priklad: kazdy clovek ma matku
neexistuje clovek, co nema matku

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Formule f je Semanticky dusledek mnoziny formuli S…

A

Pokud pro kazde ohodnoceni U, v nemz jsou pravdive vsechny formule z S, je pravdiva i f ve stejnem ohodnoceni U.

Znacime S|= f //f je semantickym dusledkem S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Postup dukazu/vyvraceni, ze formule f je semanticky dusledek mnoziny formuli S

A

Mam mnozinu S{nejake formule… s at. prvky}

Sestavim tabulku vsech at. prvku a vsech formuli z S do sloupcu.
Pak ohodnotim vsechny mozne kombinace at. prvku jako 00,01,10,11 atd do radku

Pro kazdy radek ohodnotim i formule z S.
Najdu takove radky, kde jsou formule z S pravdive VSECHNY. Pokud ve stejnych radcich je pravdiva i moje zadana formule, pak je semantickym dusledkem S. Pokud radek S=1, ale f ve stejnem radku=0, pak neni sem. dusledkem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Pro formuli s n atomickymi promennymi kolik existuje pravdivostnich ohodnoceni (variant, jak ji ohodnotit)

A

Pro kazdou z n promennych muzeme pridelit 2 moynosti - 0,1.
Tedy je to 2 ohodnoceni pro 1. prvek * 2 ohodnoceni pro 2. prvek * 2 ohodnoceni pro 3. prvek * … n-krat

tedy je to 2^n ohodnoceni celkem

Tedy je to 2^n radku v tabulce pravdivostniho ohodnoceni

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Definice splnitelne formule

A

Formule je splnitelna, pokud existuje alespon jedno pravdivostni ohodnoceni atomickych prvku tak, ze je formule v tomto ohodnoceni pravdia, tedy staci najit pouze jeden radek abych prohlasil ze je splnitelna.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Definice tautologie

A

Formule je tautologie p.t.k je splnitelna pro vsechna pravdivostni ohodnoceni jeji atomickych prvku

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Definice kontradikce

A

Formule je kontradikce p.t.k neni splnena v zadnem pr. ohodnoceni jeji atomickych prvku

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Definice splnitelna mnoziny formuli S

A

Mnozina formuli S je splnitelna, pokud existuje alespon jedno takove pravdivostni ohodnoceni, ve kterem jsou splneny vsechny formule z S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Vztah mezi semantickou ekvivalenci a pravdivostnim ohodnocenim dvou formuli

A

Dve formule jsou semanticky ekvivalentni pokud rikaji totez, tedy pro jakekoliv pr. ohodnoceni maji stejnou pravdivostni hodnu obe.

Takze udelam tabulku kam do sloupcu dam obe formule a pak jejich aatomicke prvky. Pro vsechny kombinace pr. hodnoceni at. prvku spocitam pr. ohodnoceni formuli a ve vsech radcich musi vyjit stejne

Nebo jiny pohled:

Dve formule jsou sem. ekv. p.t.k. implikace mezi nimi je tautologie

Jeste jiny pohled
Dve formule jsou sem. ekv. p.t.k. druha je sem. dusledkem prvni a naopak

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Pokud mnozina formuli S je prazdna mnozina, pak formule f je jejim semantickym dusledkem p.t.k.

A

f je tautologie

Tedy f je pravdiva vdzy, takze i ve vsech pripadech, kdy prazdna mnozina je pravdiva (coz ale je splneno vzdy, protoze predpoklad z prazdne mnoziny je vzdy pravda…, protoze nenajdu protipriklad)
Takze S vdzdy/nikdy je pravdiva a f je vzdy pravdiva => f je dusledkem S.

23
Q

Semanticky dusledek nesplnitelne mnoziny je…

A

Jakakoliv formule,
protoze nesplnitelna mnozina NIKDY NEMA PRAVDIVY RADEK, tedy nemam co overovat, takze jakakoliv formule je dusledkem nesplnitelne

24
Q

Pokud formule je semantickym dusledkem pravdy True, pak je tato formule…

A

tautologie

25
Q

Veta o dedukci (asi ne moc podstatna)

A

Psi je sem. dusledkem mnoziny formuli sjednoceno s formuli fi p.t.k. implikace q->psi je sem. dusledkem mnoziny formuli

S U f |= psi p.t.l S |= (fi =>psi)

26
Q

Mnozina vsech sem. dusledku mnoziny formuli S

A

Je mnozina Cos(S) // consequences
Je to mnozina vsech formuli, ktere jsou sem. dusledkem S

Plati:
1. S je podmnozina Con(s)
2. S je podmnozina T, pak Con(s) je podmnozina Con(t)
3. Con(Con(S)) = Con(S)

27
Q

Vztah semantickeho a logickeho dusledku

A

S |- fi p.t.l S |= fi

Tedy fi mohu odvodit z S p.t.k. fi je sem. dusledkem mnoziny formuli S
Pokud je otazka polozena jako “dokazte, ze fi plyne z S” => pouziju S|-fi.

Pokud je otazka “ rozhodnete, za fi je dusledkem S…” => Pouziju S|=fi

28
Q

Uplny/Adekvatni system spojek v logice

A

Je takova mnozina symbolu/spojek, ze s jejcih pomoci muzeme poskladat jakoukoliv formuli a mohou nahradit jina vyjadreni, treba rozsirenejsich systemu.

Treba {negace, sjednoceni, disjunkce, implikace, ekvivalence}
Ale mohou byt i mensi, treba jenom {negace, disjunkce} je nejmensi, ostatni jsou syntactic sugars jakoby. Ale vsechny formule se daji napsat pouze pomoci {negace, disjunkce}

Negace vzdy musi byt soucasti uplneho systemu spojek, bez ni s eneobejdeme

29
Q

S |= fi p.t.k [S spolu s (negace fi)] je…

A

nesplnitelna

Pokud formule je dusledkem, pak negace nemuze byt dusledkem

Dukaz primitivni:
V tabulce kde jsou radky S=1 a fi=1 z predpokladu
Pak negace fi ma 0 a tim padem rozsirena mnozina nema ani jeden radek samych 0

30
Q

Predikatova logika

A

Obsahuje predikaty (vlastnosti) a argumenty (vstupy do predikatu)

Byt mladsi nez:
M(pavel, jirka) - M je predikat/vlastnost a ma dva argumenty

31
Q

Termy a formule predikatove logiky

A

Termy jsou objekty (neco jako atomicke formule) a nedaji se ohodnotit.
Formule popisuji uz vlastnosti objektu a daji se ohodnotit

Treba term Pavel a mit maminku M(Pavel).
Pavel nejde ohodnotit. Pavel ma maminku jde ohodnotit

32
Q

Syntakticky strom predikatove logikt

A

Delam stejne jako vyrokove. Postupne podle priority stepim formule na dalsi podformule az dojdu k termum. Po ceste mam jako binarni operatory tak i predikaty/funkce, ktere berou termy

33
Q

Volny/vazany vyskyt promenne ve formuli

A

Promenna je vazana p.t.k v syntaktickem strome od jejich prvniho vyskytu dole jdu nahoru a cestou narazim na obecny/kvantovy kvantifikator s touto promennou.

Pokud na takovy kvantifikator nenarazim, pak je tato promenna volna.

Pak pisi bud:
bound(fi) = promenna1
free(fi) = promenna2

34
Q

Jazyk L predikatove logiky je zadan mnozinami…

A

Var - promenne (clovek)
Pred - predikaty (vlatnost, byt studentem, mladsim nez…)
Func - funkce (m(x) - matka cloveka, vraci nam novy objekt - term)
Kons - konstanty (treba jeden vybrany clovek, Pavel)
Specifikace arity vsech funkci

35
Q

Jak se definuji termy a formule

A

t ::= promenna | konstanta | vysledek funkce(x,y,z…)
f ::= false | true | t1=t2 | Predikat(termy…) | negace f | spojeni formuli | kvantifikatory

36
Q

Substituce ve formuli

A

Nech f je formule a ma volnou promennou x.

Pak definujeme f[t/x] jako substituci. Vznikla z formule f narhazenim volne promenne termem t.

37
Q

Cemu se vyhnout pri substituci

A

Aby novy term se nestal vazanym, protoze se zmeni smysl formule.
Nahrazuju POUZE VOLNE promenne a tak aby ZUSTALY VOLNE (tzn vetsinou novy nazev uplne)

38
Q

Definice volneho termu

A

Term t je volny pro promennou x ve formuli fi p.t.k. pro jakoukoliv substituci x za t se nezmeni “volnost” na tomto miste substituce NEBO pokud je puvodni x vazane (protoze substituju pouze za volne promenne, tj pokud je puvodni promenna vazana, tak se neda substituovat, takze nemam co overovat pro jeji substituci, takze je term t pro ni volny)

39
Q

Prirozena dedukce predikatove logiky

A

Je to dukazovy system

40
Q

Definice Sentence

A

Formule je sentence, pokud nema volne promenne, vsechny jsou vazane nejakym kvantifikatorem

41
Q

Deklarovana promenna

A

Je to takova promenna, ktera byla nejak zavedena v postupu dukazu nebo odvozovani. Nemuze se z niceho nic random objevit nova promenna

stejny princip jako v kodu - pokud chci pouzivat promennou, musim ji predem zavest nejak

42
Q

Interpretace jazyka L definice

A

Interpretace ma 2 casti:
1. Mnozinu, kterou popisuje - universum
2. Prirazeni [||] vsech predikatu, funkci, konstant, ktere vezme ten prvek a priradi mu podmozinu univerzu podle arity prvku.

43
Q

Priklad interpretace jazyka L

A

Necht je jazyk L zadan jako:
Pred = {S, M}, ar(S)=1, ar(M)=2,
Func = {f}, ar(f)=2,
Konst = {a}

Toto je pouze KOSTRA jazyka, nic nam nerika absolutne, dokud tomu nedame vyznam - interpretaci. Je to pouze sablona, na kterou muzeme vytvaret ruzne interpretace.

Interpretace I=(U, [||]) ma dve casti:
1. Univerzum - prirozena cisla
2. [|S|] = {2k | k je prirozene} // byt sude
[|M|] = {m,n | m < n} // byt mensi nez
[|f|] = (m,n) -> m+n // funkce soucet
[|a|] = 1 // a neni ale 1, je to pouze symbol, ale neni to primo objekt 1.

Tedy interpretace bere KOSTRU/sablonu/abstrakne zadany jazyk a pridava tomu vyznam podle syntaxe. Podobnych interperataci muze byt mnoho

44
Q

Kontext promennych ro pro interpretaci I

A

Kontext promennych je parcialni zobrazeni (bere prvek a posila ho na nejaky prvek, ale nemusim definovat pro vsechny, treba deleni je parcialni zobrazeni, protoze neni definovano pro 0).

Je to jakasi look-up tabulka nebo slovnik, ktery udrzuje informaci o tom, jaka hondota je ulozena pro jakou promennou. Kontext mi uklada hodnoty promennych.

ro: x -> 2, y->4 // prirazeni hodnot promennym

45
Q

Update kontextu promennych ro interpretace I

A

Update je obycejna zamena puvodni hodnoty promenne na novou hodnotu - jako kdybych proste priradil novou hodnotu ALE U TOHO SE VYTBORI UPLNE NOVY OBJEKT SLOVNIKU JAKO DEEP COPY a původní kontext ale nezanikne

ro[x:=d] znamena, ze vezmu puvodni kontext ro: x->2, y->4 a vytvorim novy ro:x->d, y->4, puvodni ale stale existuje

46
Q

Interpretace termu t v kontextu ro a interpretaci I

A
  1. Mam zadany jazyk jako prazdnou kostru/sablonu bez vyznamu.
  2. Mam zadanou interpretaci, ktera dodava vyznam symbolum jazyka.
  3. Kontext promennych mi stanovuje hodnoty promennych.

Je to jako 1. syntax programovaciho jazyka, 2. semantika prog. jazyka a 3. samotne promenne. Pak jsem vybaven tremi nastroji na zodpovidani ruznych dotazu do meho systemu/kodu.

Nekdo mi zadal tyto tri veci a chci vyhodnotit vystup programu pro nejake formule nebo kod.

Treba jak interpretovat promennou v kontextu ro a interpretaci I jazyka L?
a) [|x|] = x, je to proste hodnota promenne v kontextu
b) [|konst| = konst, kostanty nezavisi na kontextu, nemeni se
c) [|f(t1,…tn)|] = [|f|] ([|t1|], … [|tn|] // interpretace funkce s termy delam postupne po slozkach, nejdriv interpretuju vsechny argumenty a pak na ne poslu interpretaci funkce

47
Q

Priklad interpretace [|f(a, x|] pro

jazyk L:
Pred = {S, M}, ar(S)=1, ar(M)=2,
Func = {f}, ar(f)=2,
Konst = {a}

Interpretaci I:
1. Univerzum - prirozena cisla
2. [|S|] = {2k | k je prirozene} // byt sude
[|M|] = {m,n | m < n} // byt mensi nez
[|f|] = (m,n) -> m+n // funkce soucet
[|a|] = 1 // a neni ale 1, je to pouze symbol, ale neni to primo objekt 1.

Deklarovane promenne:
{x,y}

A kontext promennych ro:
x -> 2,
y->3

A

Nekdo mi zadal abecedu/syntax pouzivanych symbolu, jejich vyznam, pouzivane promenne, jejich hodnoty.

Chce po me, abych v tomto prostredi vyhodnotil vyraz:
[|f(a,x)|]. Tedy jaka bude v tomto prostredi hodnota funkce f aplikovana na konstatnu 1 a x.

Interpretuju po slozkach:
f -> soucet prvku uvnitr.
Hodnota a je ulozena v interpretaci = 1.
Hodnota x je ulozena v kontextu promennych = 2

Tedy je to 1+2=3.

48
Q

Definice pravdivosti at. formule fi v interpretaci I a kontextu ro

A

Znazcime I |= fi, tedy fi je pravdiva v interpretaci I a kontextu ro.

  1. I |= True vzdy // pravda plati za vsech podminek
  2. | !|= False vzdy // nepravda nikdy neplati
  3. I |= A, pokud interpretace termu A = 1
  4. I |= t1=t2 pokud jejich interpretace se rovnaji
  5. I |= P(t1,…tn), pokud interpretace vsech termu jsou splneny v predikatu
  6. I |= (negace fi), pokud I !|= fi (plati bud fi nebo negace fi)
  7. I |= (fi a psi) p.t.k. (I |= fi a I |= psi)
  8. I !|= (fi nebo psi) p.t.k. (I !|= fi a I !|= psi)
  9. implikace a ekvivalnece pdoobne…

Tedy se vzdy podivam, jestli pro dany jazyk a interpretaci je prava strana ohodnocena jako 1 (znacky plati jak u vyrokove lopgiky), tj jestli prava strana vyplyva z kontextu leve (sem. dusledek jakoby).

Priklad: I |= S(y)? V nasi predchozi interpretaci.
Tedy je y sude? Y = 4 => ano.

49
Q

Pravdivost formuli s kvantifikatory

A

Jak zjistit, zd formule tvaru (ProVsechna x plati fi) je pravida pro interpretaci s kontextem?

I |= PrVs x: fi p.t.k I |= fi (pro jakykoliv update x) // tj musi to platit pro uplne vsechny updaty promennych, postupne tedy kontext promennych menim a bud hledam protipriklad, nebo se snazim dokazat inducki pravdivost

Analogicky pro to, abych dokazal Existenci, tak musim najit alespon jeden update aby to platilo.

Priklad. Je pravda, ze pro vsechna x v mem jazyku a interpretaci plati, ze soucet x,a je mensi nez 5? NEPLATI, PROTOZE MOHU X PRIRADIT HODNOTU 4, PAK X+A = 4+1 !<5. tedy nasel jsem takovy update kontextu promennych, ze neplati ProVs.

Ale plati, ze takove x alespon jedno existuje (treba x=1..3)

50
Q

Sentence fi je pravdiva v I p.t.k…

A

Je pravida nezavisle na kontextu promennych, tedy v prazdnem kontextu. Znacime I |= fi. Tedy sentenci je jedno, jaky je kontext, protoze stejne bude updatovan.

51
Q

Interpretace I je modelem sentence fi p.t.k.

A

Sentece fi je pravida v I ve vsech updatech, tedy v prazdnem kontextu

52
Q

Splnitelna sentece/kontradicke/tautologie

A

Sentence je
1. splnitelna p.t.k ma model (tedy interpretaci, ve ktere je fi splnena)
2. kontradikce p.t.k nema model (nejde splnit za zadnych interpretaci)
3. tautolgie p.t.k kazda I je jejim modelem

Interpretace tady vystupuje jako ve vyrokove logice pravdivostni ohodnoceni atomickych prvku
Formule je splnitla p.t.k existuje pr. ohodnoceni takove, ze je f splnena. Ve vyrokove logice funkci takoveho ohodnoceni hraje Interpretace a kontext promennych.

Abych dokazal splnitelnost, tak staci najit Interpretaci takovou, aby formule platila. Priklad
PrVs x plati: M(x, f(x,a)). Chci toto dokazat, ze je splnitelna -> hledam nejakou interpretaci tak, aby formule platila.
Treba ze M=> byt mensi, f(x.a) = x + 1. Tedy PrVs x plati: x < x +1. SPLNENO => SPLNITELNA
Uz vim ze to neni kontradikce.
Je to ale tautologie? Hledam protipriklad Interpretace. Treba M-> je vetsi nez. Pak formule PrVs x plati: x > x +1 NEPLATI => neni tautologie…

53
Q

Mnozina sentenci je splnitelna/nesplnitelna

A

P0okud existuje interpretace I takova, ze kazda sentence z mnoziny je splnena v teto interpretaci, tj I je modelem vsech sentenci

Pokud mnozina nema model, pak je nesplnitelna

54
Q

Semanticky dusledek v predikatove logice

A

Rekneme, ze sentence fi je sem. dusledek mnoziny sentenci S p.t.k kazdy model mnoziny S je zaroven i modelem fi.

// analogie s vyrokovou logikou:
formule byla sem. dusledkem mnoziny p.t.k. pro vsechna ohodnoceni mnoziny, kde S=1 i formule fi=1. V predikatove logice misto ohodnoceni mame interpretace, tedy pro kazdou interpretaci S, ve ktere jsou vsechny sentence S splneny, musi byt splnena i nova sentence fi

Dokazuju bud induktivne pres modely, nebo normalni dedukci jako dukaz ze z predpokladu S mohu odvodit fi

Státnice (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions