Brainscape's Knowledge GenomeTM

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


See full index

Statnice - spolocne > MLO > Flashcards

MLO Flashcards

1
Q

Výroková logika

A

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

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

Prvotní výrok

A

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

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

prvotní formule

A

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

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

Formule výrokové logiky

A

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

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

Syntaxe fráze výrokové logiky

A

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

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

Sémantika výrokové logiky

A

čo vytvorené frázy znamenajú

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

Pravdivostní ohodnocení

A

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

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

Negace

A

Nie je pravda, že A

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

Konjunkcia

A

A a B

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

Disjunkcia

A

A alebo B

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

Implikácia

A

Ak A, tak B

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

Ekvivalencia

A

A práve vtedy, keď B

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

Tautologie

A

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

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

Kontradikce

A

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á

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

Splniteľná formule

A

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

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

Logický dôsledok

A

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

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

Logická ekvivalencia

A

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

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

Univerzálny systém logických spojek

A

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: {¬, ∨}, {¬, ∧}, {¬, =>}, {↑}, {↓}

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

Shefferuv symbol

A

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

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

Piercova šípka

A

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

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

Disjunktivní normální tvar (DNT)

A

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

22
Q

Konjunktívny normálny tvar (KNT)

A

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.

23
Q

Minimalizace

A

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á.

24
Q

Predikátová logika

A

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)

25
Q

Term predikátovej logiky

A

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

26
Q

Formule predikátovej logiky

A

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.

27
Q

Viazaná/Voľná premenná

A

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

28
Q

Uzavrená/otvorená formula

A

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

29
Q

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

A

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.

30
Q

Pravdivosť formulí predikátovej logiky

A

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.

31
Q

Platnosť (pravdivosť) formule

A

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

32
Q

Logicky pravdivá formule

A

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.

33
Q

Splniteľná formule pred. l.

A

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

34
Q

Kontradikce formule pred. l.

A

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

35
Q

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

A

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]

36
Q

Negace kvantifikátorú

A

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

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

37
Q

Všechny kočky jsou šelmy

A

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

38
Q

Některé kočky jsou šelmy

A

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

39
Q

Žádné kočky nejsou šelmy

A

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

40
Q

Některé kočky nejsou šelmy

A

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

41
Q

Teorie

A

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

42
Q

Model teorie

A

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

43
Q

Logický dôsledok teorie

A

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.

44
Q

Splniteľnosť teorie

A

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

45
Q

Teorie rovnosti

A

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é.

46
Q

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

A

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.
47
Q

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

A

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,
48
Q

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

A

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
49
Q

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

A

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

50
Q

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

A

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

51
Q

Teorie grup

A

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)

Statnice - spolocne (10 decks)

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