MLO

Question 1

Výroková logika

Answer 1

Výroková logika je vyjadřovací prostředek matematiky. Základem výrokové logiky je výrok.

Question 2

Prvotní výrok

Answer 2

jednoduchá oznamovací věta, u které má smysl se ptát, zda je či není pravdivá

Question 3

prvotní formule

Answer 3

označenie prvotného výroku veľkými písmenami - A, B, …

Question 4

Formule výrokové logiky

Answer 4

Formule výrokové logiky Je posloupnost symbolů z jazyka výrokové logiky – viz syntaxe.

Question 5

Syntaxe fráze výrokové logiky

Answer 5

symboly pre prvotné formule, symboly pre logické spojky, zátvorky, opakované v konečne mnoho korkoch

Question 6

Sémantika výrokové logiky

Answer 6

čo vytvorené frázy znamenajú

Question 7

Pravdivostní ohodnocení

Answer 7

funkce z množiny prvotných formulí do množiny {0,1}, v(A) = 1 - pravidivý výrok, 0 - nepravdivý výrok

Question 8

Negace

Answer 8

Nie je pravda, že A

Question 9

Konjunkcia

Answer 9

A a B

Question 10

Disjunkcia

Answer 10

A alebo B

Question 11

Implikácia

Answer 11

Ak A, tak B

Question 12

Ekvivalencia

Answer 12

A práve vtedy, keď B

Question 13

Tautologie

Answer 13

Výroková formula je tautologia (T), ak pre všetky kombinácie ohodnotenia prvotných formulí je jej hodnota 1, tj. pravdivá

Question 14

Kontradikce

Answer 14

Výroková formula je kontradikce (opračné T, hehe), ak pre všetky kombinácie ohodnotenia prvotných formulí je jej hodnota 0, tj. nepravdivá

Question 15

Splniteľná formule

Answer 15

Výroková formula je splniteľný, ak pre nejakú kombináciu ohodnotenia prvotných formulí je jej hodnota 1, tj. pravdivá

Question 16

Logický dôsledok

Answer 16

Formula B je logickým dôsledkom A, práve vtedy, keď pre každé ohodnotenie v, pre ktoré v(A) = 1 je aj v(B) = 0. Hovoríme: B vyplýva z A, tj ak A => B je tautologie

Question 17

Logická ekvivalencia

Answer 17

Formule A a B sú logicky ekvivalentné práve vtedy, keď pre každé ohodnotenie v je v(A) = v(B), tj. ak A <=> B je tautlogie

Question 18

Univerzálny systém logických spojek

Answer 18

Množina logických spojek S tvorý univerzálny systém, ak je možné previesť každú formulu výrokové logiky do logicky ekvivalentného tvaru, v ktorom sa vyskytujú len spojky z S, príklad: {¬, ∨}, {¬, ∧}, {¬, =>}, {↑}, {↓}

Question 19

Shefferuv symbol

Answer 19

NAND - A ↑ B = ¬(A ∧ B)

Question 20

Piercova šípka

Answer 20

NOR - A ↓ B = ¬(A ∨ B)

Question 21

Disjunktivní normální tvar (DNT)

Answer 21

Literál je prvotní formule alebo jej negace (A, not A, B,…), Implikant je konjunkce literálu (A ∧ B, not A ∧ B, not C) alebo literál. Minterm je implikant, ktorý obsahuje všetky prvotné formule. Formule je v DNT, ak je implikant alebo disjunkciou niekoľkých implikantov - (A ∧ B ∧ C) ∨ (¬A ∧ ¬C). Fromule je v úplnom DNT, ak je v DNT a je disjunkciou mintermov

Question 22

Konjunktívny normálny tvar (KNT)

Answer 22

Literál je prvotní formule alebo jej negace (A, not A, B,…), Klausule je disjunkce literálu (¬A ∨ B, ¬C) alebo literál. Maxterm je klausule, ktorá obsahuje všetky prvotné formule. Formule je v KNT, práve vtedy, keď je konjunkciou klausulí. Formule je v úplnom KNT, ak je konjunkciou maxtermov.

Question 23

Minimalizace

Answer 23

Minimalizáciu provádime pomocou Karnaughových máp nad DNT. DNT je minimálny, práve keď žiadny iný ekvivalentný DNT nemá menej mintermov alebo menej literálov. KNT minimalizujeme prevodom na DNT. Mintermy odpovı́dajı́ ohodnocenı́m, pro něž je formule pravdivá. Negace maxtermů odpovı́dajı́ ohodnocenı́m, pro něž je formule nepravdivá.

Question 24

Predikátová logika

Answer 24

Rozšírenie výrokovej logiky pre vyjadrenie zložitejších výrazov. Premenné (x,y,z), logické spojky, kvantifikátory (obecný,existenčný), pomocné symboly (zátvorky), symboly pre konštanty (K,L,…), symboly pre predikáty (p,q,r), funkce (f,g)

Question 25

Term predikátovej logiky

Answer 25

postupnosť jazyka L predikátovej logiky, pre ktorú platí: a) každá premenná a konštnanta je term b) ak sú t1,..., tn termy a f je n-ární funkcný symbol jazyka L, potom f(t1,...,tn) je term c) každý term vznikne použitím a) a b) v konečne mnoho korkoch

Question 26

Formule predikátovej logiky

Answer 26

posloupnost symbolů, která vznikne aplikacı́ následujı́cı́ch pravidel v konečně mnoha krocı́ch: a) Je-li p n-árnı́ predikátový symbol a t1 , . . . , tn jsou termy, pak p(t1 , ..., tn ) je formule. Takto vzniklou formuli nazýváme atomická formule. b) Jsou-li A a B formule, pak ¬A, (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) jsou formule. c) Je-li x proměnná a A formule, pak (∀x)A a (∃x)A jsou formule.

Question 27

Viazaná/Voľná premenná

Answer 27

Viazaná premenná je viazaná nejakým kvantifikátorom (∀x)B(x). Voľná je opak viazanej

Question 28

Uzavrená/otvorená formula

Answer 28

Uzavrená - neobsahuje voľný výskyt žiadnej premennej (všetky premenné majú kvantifikátor). Otvorená - Všetky premenné majú voľný výskyt

Question 29

Interpretace (realizace) jazyka L = {K , . . . , p . . . , f , . . . }: konstanty, predikáty, funkce

Answer 29

Interpretace (realizace, struktura) jazyka L obsahuje i) neprázdnou množinu M , kterou nazýváme universum interpretace, ii) je-li K konstanta, pak jejı́ interpretaci KM ∈ M, iii) je-li p n-árnı́ predikát, pak n-árnı́ relaci pM ⊆ M n jako jeho interpretaci, iv) je-li f funkce majı́cı́ n argumentů, pak funkci fM : M n → M jako jejı́ interpretaci.

Question 30

Pravdivosť formulí predikátovej logiky

Answer 30

Necht’ L je jazyk a M je jeho interpretace • Ohodnocenı́ proměnných je funkce e z množiny proměnných, která každé proměnné přiřazuje nějaký prvek universa M , e(x) ∈ M. • Výrazem t[e] označujeme hodnotu termu t při ohodnocenı́ e, tj. t[e] ∈ M. - Je-li term t proměnná x, pak t[e] = e(x). - Je-li f n-árnı́ funkčnı́ symbol a term t je f (t1 , . . . , tn ), pak t[e] = f (t1 [e], . . . , tn [e]). • Výrazem e(x/m) označujeme nové ohodnocenı́, které všem proměnným přiřadı́ stejnou hodnotu jako e, jenom e(x) = m, kde m ∈ M.

Question 31

Platnosť (pravdivosť) formule

Answer 31

Formule A je pravdivá v interpretaci M, práve vtedy, keď pre každé ohodnotenie e je pravdivá, tj. M |= A[e]. Pı́šeme M |= A

Question 32

Logicky pravdivá formule

Answer 32

Formule A je logicky pravdivá (platná), právě když pro každou interpretaci M platı́ M |= A. Značı́me |= A. Každá tautologie výrokové logiky, kde prvotnı́ formule jsou nahrazeny formulemi predikátové logiky, je logicky pravdivá formule.

Question 33

Splniteľná formule pred. l.

Answer 33

Formule A je splnitelná, právě když v nějaké interpretaci M pro nějaké ohodnocenı́ e platı́ M |= A[e].

Question 34

Kontradikce formule pred. l.

Answer 34

Formule ja kontradikce práve vtedy, keď nie je splniteľná

Question 35

Logický dôsledok a logická ekv. pred. l.

Answer 35

A a B jsou logicky ekvivalentnı́, A |=| B, právě když pro každou interpretaci M a pro každé ohodnocenı́ e platı́: M |= A[e], právě když M |= B[e]. B je logickým důsledkem A, A |= B, právě když pro každou interpretaci M a pro každé ohodnocenı́ e platı́: jestliže M |= A[e], pak i M |= B[e]

Question 36

Negace kvantifikátorú

Answer 36

a) ¬(∀x)A |=| (∃x)¬A | b) ¬(∃x)A = (∀x)¬A

Question 37

Všechny kočky jsou šelmy

Answer 37

(∀x)(k(x) ⇒ s(x))

Question 38

Některé kočky jsou šelmy

Answer 38

(∃x)(k(x) ∧ s(x))

Question 39

Žádné kočky nejsou šelmy

Answer 39

(∀x)(k(x) ⇒ ¬s(x))

Question 40

Některé kočky nejsou šelmy

Answer 40

(∃x)(k(x) ∧ ¬s(x))

Question 41

Teorie

Answer 41

Teorie je množina uzavřených formulı́ T = {A1 , ..., An } jazyka L.

Question 42

Model teorie

Answer 42

Interpetace M jazyka L je modelem teorie T, jestliže každá formule platı́ v M. Pı́šeme M |= T

Question 43

Logický dôsledok teorie

Answer 43

Formule A je logický důsledek teorie T , (A logicky vyplývá z T ), jestliže v každém modelu teorie T platı́ A. Pı́šeme T |= A.

Question 44

Splniteľnosť teorie

Answer 44

Teorie T je splnitelná, právě když má model

Question 45

Teorie rovnosti

Answer 45

Nechť L obsahuje binárnı́ predikát pro rovnosti =. Platı́ pro něj: i) (∀x)(x = x) – reflexivita ii) (∀x)(∀y)(∀z)((x = y ∧ y = z) ⇒ x = z)) – transitivita iii) (∀x)(∀y)(x = y ⇒ y = x) – symetrie iv) Je-li f je n-árnı́ funkčnı́ symbol, pak (∀x1 )···(∀y1 )···(x1 = y1 ∧ ... ∧ xn = yn ) ⇒ f (x1 , ... , xn ) = f (y1 , ... , yn ) v) Je-li p n-árnı́ predikátový symbol, pak (∀x1 )···(∀y1 )···(x1 = y1 ∧ ... ∧ xn = yn ) ⇒ p(x1 , ... , xn ) = p(y1 , ... , yn ) Logika 1. řádu s rovnostı́ – kvantifikátory se užı́vajı́ pouze pro proměnné.

Question 46

Teorie částečného ostrého uspořádání

Answer 46

Teorie T částečného ostrého uspořádánı́ má tyto axiomy: T (∀x)(∀y)(∀z) (((p(x, y) ∧ p(y, z)) ⇒ p(x, z)) – transitivita IR (∀x)¬p(x, x) – ireflexivita Modely: - N,< > (Z,Q,R) - N, x je vlastnı́ dělitel y - Množina všech lidı́, p(x, y) – x je předkem (resp. potomkem) y.

Question 47

Teorie částečného neostrého uspořádánı́

Answer 47

Nechť L = {q(x, y)}. Pro teorii částečného neostrého uspořádánı́ platı́ následujı́cı́ axiomy: R (∀x)q(x, x) – reflexivita T (∀x)(∀y)(∀z)((q(x, y) ∧ q(y, z)) ⇒ q(x, z)) – transitivita As (∀x)(∀y)((q(x, y) ∧ q(y, x)) ⇒ (x = y)) – slabá antisymetrie Modely: - < N, ≤ > (Z,Q,R) - N, x je dělitel y,

Question 48

Teorie lineárnı́ho uspořádánı́

Answer 48

Nechť L = {x < y}. Lineárnı́ uspořádánı́ je částečné uspořádánı́ (ostré), pro které navı́c platı́ • L: (∀x)(∀y) (x < y ∨ x = y ∨ y < x) – linearita Modely: - N,< > (Z,Q,R) - Slova podle abecedy

Question 49

Teorie hustého lineárnı́ho uspořádánı́

Answer 49

Nechť L = { (Q+,R, (0,1), [0,1])

Question 50

Teorie neomezeného hustého lineárnı́ho uspořádánı́

Answer 50

Nechť L = { (R, R\{0})

Question 51

Teorie grup

Answer 51

Nechť L = {e, f }, f – binárnı́ funkčnı́ symbol, e – konstanta (neutrálnı́ prvek). Grupa splňuje tyto axiomy: • A: (∀x)(∀y)(∀z)f (f (x, y), z)) = f (x, f (y, z)) – asociativita • N: (∀x)f (x, e) = x – neutralita • I: (∀x)(∃z)f (x, z) = e – inverznı́ prvek Modely: - {+,0}, {.,1} (aditívna, multiplikatívna)