MLO Flashcards
Výroková logika
Výroková logika je vyjadřovací prostředek matematiky. Základem výrokové logiky je výrok.
Prvotní výrok
jednoduchá oznamovací věta, u které má smysl se ptát, zda je či není pravdivá
prvotní formule
označenie prvotného výroku veľkými písmenami - A, B, …
Formule výrokové logiky
Formule výrokové logiky Je posloupnost symbolů z jazyka výrokové logiky – viz syntaxe.
Syntaxe fráze výrokové logiky
symboly pre prvotné formule, symboly pre logické spojky, zátvorky, opakované v konečne mnoho korkoch
Sémantika výrokové logiky
čo vytvorené frázy znamenajú
Pravdivostní ohodnocení
funkce z množiny prvotných formulí do množiny {0,1}, v(A) = 1 - pravidivý výrok, 0 - nepravdivý výrok
Negace
Nie je pravda, že A
Konjunkcia
A a B
Disjunkcia
A alebo B
Implikácia
Ak A, tak B
Ekvivalencia
A práve vtedy, keď B
Tautologie
Výroková formula je tautologia (T), ak pre všetky kombinácie ohodnotenia prvotných formulí je jej hodnota 1, tj. pravdivá
Kontradikce
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á
Splniteľná formule
Výroková formula je splniteľný, ak pre nejakú kombináciu ohodnotenia prvotných formulí je jej hodnota 1, tj. pravdivá
Logický dôsledok
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
Logická ekvivalencia
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
Univerzálny systém logických spojek
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: {¬, ∨}, {¬, ∧}, {¬, =>}, {↑}, {↓}
Shefferuv symbol
NAND - A ↑ B = ¬(A ∧ B)
Piercova šípka
NOR - A ↓ B = ¬(A ∨ B)
Disjunktivní normální tvar (DNT)
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
Konjunktívny normálny tvar (KNT)
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.
Minimalizace
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á.
Predikátová logika
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)
Term predikátovej logiky
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
Formule predikátovej logiky
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.
Viazaná/Voľná premenná
Viazaná premenná je viazaná nejakým kvantifikátorom (∀x)B(x). Voľná je opak viazanej
Uzavrená/otvorená formula
Uzavrená - neobsahuje voľný výskyt žiadnej premennej (všetky premenné majú kvantifikátor). Otvorená - Všetky premenné majú voľný výskyt
Interpretace (realizace) jazyka L = {K , . . . , p . . . , f , . . . }: konstanty, predikáty, funkce
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.
Pravdivosť formulí predikátovej logiky
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.
Platnosť (pravdivosť) formule
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
Logicky pravdivá formule
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.
Splniteľná formule pred. l.
Formule A je splnitelná, právě když v nějaké interpretaci M pro nějaké ohodnocenı́ e platı́ M |= A[e].
Kontradikce formule pred. l.
Formule ja kontradikce práve vtedy, keď nie je splniteľná
Logický dôsledok a logická ekv. pred. l.
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]
Negace kvantifikátorú
a) ¬(∀x)A |=| (∃x)¬A
b) ¬(∃x)A = (∀x)¬A
Všechny kočky jsou šelmy
(∀x)(k(x) ⇒ s(x))
Některé kočky jsou šelmy
(∃x)(k(x) ∧ s(x))
Žádné kočky nejsou šelmy
(∀x)(k(x) ⇒ ¬s(x))
Některé kočky nejsou šelmy
(∃x)(k(x) ∧ ¬s(x))
Teorie
Teorie je množina uzavřených formulı́ T = {A1 , …, An } jazyka L.
Model teorie
Interpetace M jazyka L je modelem teorie T, jestliže každá formule platı́ v M. Pı́šeme M |= T
Logický dôsledok teorie
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.
Splniteľnosť teorie
Teorie T je splnitelná, právě když má model
Teorie rovnosti
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é.
Teorie částečného ostrého uspořádání
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.
Teorie částečného neostrého uspořádánı́
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,
Teorie lineárnı́ho uspořádánı́
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
Teorie hustého lineárnı́ho uspořádánı́
Nechť L = { (Q+,R, (0,1), [0,1])
Teorie neomezeného hustého lineárnı́ho uspořádánı́
Nechť L = { (R, R{0})
Teorie grup
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)
