TODO

Výroková logika

Syntaxe výrokové logiky

Jazyk výrokové logiky obsahuje symboly:

• logické proměnné - A = {a, b, c}
• logické spojky - $\neg$ (not), $\wedge$ (and), $\vee$ (or), $\Rightarrow$ (if … than), $\iff$ (if and only if), $|$ (nand), $\downarrow$ (nor), $\oplus$ (xor)
• závorky

Formule výrokové logiky:

1. Logická proměnná je Atomická formule
2. Formule $\alpha$, $\beta$, pak $(\neg \alpha )$, $(\alpha \wedge \beta )$, $(\alpha \vee \beta )$, $(\alpha \Rightarrow \beta )$, $(\alpha \iff \beta )$ jsou formule
3. Každá formule vznikla použitím konečně mnoha kroků 1. a 2. Množina všech formulí s proměnnými z A označíme $Fle(A)$

Relaxace

• Nebudeme psát vnější závorky kolem formule
• Nebudeme psát závorky kolem negace $\phi =(((\neg b)\Rightarrow a)\vee c)$ relaxuji na $\phi =(\neg b\Rightarrow a)\vee c$

Syntaktický strom formule

Rovnost formulí

Sémantika výrokové logiky

pravda - 1 nepravda - 0

Implikace $\alpha \Rightarrow \beta$ lze chápat jako slib: Nastane-li $\alpha$, tak udělám $\beta$. Implikace je nepravdivá pouze tehdy, když jsme slib nesplnili.

Pravdivostní ohodnocení u

Splnitelná formule Tautologie Kontradikce

Příklad: $\phi =(\neg b\Rightarrow a)\vee c$ je splnitelná, protože je pravdivá v například: $u$ daném $u(a)=u(b)=u(c)=1$. Toto je svědek splnitelnosti formule $\phi$

Tautologicky ekvivalentní formule

Řekneme, ze formule $\phi$ a $\psi$ jsou tautologicky ekvivalentní (sémanticky ekvivalentní), jestliže pro každé ohodnocení $u$ plat: $u(\phi )=u(\psi )$. Značme $\phi |=|\psi$

Libovolná funkce $n$ proměnných z $\{0,1{\}}^n$ do $\{0,1\}$ se nazývá booleovská funkce

Klíčová slova

• Přednáška 1:
  • Logické spojky
  • Logické proměnné
  • Závorky
  • Formule výrokové logiky
  • Atomická formule
  • Relaxace
  • Syntaktický strom formule
  • Rovnost formulí
  • Pravdivostní ohodnocení u
  • Ne/Pravdivá formule v ohodnocení u
  • Splnitelná formule
  • Tautologie
  • Kontradikce
  • Tautologicky ekvivalentní
  • Booleovská funkce
• Přednáška 2:
  • Úplný systém logických spojek
  • Booleova algebra
  • Normální forma
  • Literál
  • Minterm
  • Maxterm
  • Klausule
  • DNF
  • CNF
  • Úplná DNF
  • Úplná CNF
  • Ireducibilní DNF
  • Ireducibilní CNF
• Přednáška 3:
  • Ne/Splnitelná množina formulí
  • Sémantický důsledek
  • Resoluční metoda
  • Klausální tvar
  • Resolventa
  • Ekvisplnitelné
• Přednáška 4:
  • Přirozená dedukce
  • Základní odvozovací pravidla
  • Odvození
  • Logický důsledek
  • Logicky ekvivalentní
  • Věta
• Přednáška 5:
  • Jazyk predikátové logiky
  • Logické symboly
  • Speciální symboly
  • Pomocné symboly
  • Predikátová logika s rovností
  • Term
  • Formule
  • Atomická formule
  • Relaxace
  • Syntaktický strom formule
  • Podformule
  • Vázaný výskyt
  • Volný výskyt
  • Vázaná proměnná
  • Volná proměnná
  • Legální přejmenování vázané proměnné
  • Rovnost formulí
  • Sentence
  • Otevřená formule
  • Interpretace jazyka
  • Univerzum
  • Kontext proměnných
  • Update kontextu
  • Interpretace termu
  • Pravdivá formule v interpretaci při kontextu
  • Pravdivá sentence v intepretaci
  • Model sentence
• Přednáška 6:
  • Sentence splnitelná
  • Sentence tautologie
  • Sentence kontradikce
  • Ne/Splnitelná množina sentencí
  • Model množiny sentencí
  • Sémantický důsledek
  • Tautologicky ekvivalentní
  • Tautologicky ekvivalentní úpravy
  • Přehození pořadí kvantifikátorů
  • Vytýkání kvantifikátorů před konjunkci a disjunkci
  • Prenexní tvar
  • Převod do prenexního tvaru
• Přednáška 7:
  • Resoluční metoda
  • Převedení na problém (ne)splnitelnosti
  • Klausule
  • Literál
  • Převedení sentence na klausální tvar
  • Ekvisplnitelné
  • Skolemizace
  • Unifikační algoritmus
  • Resloventa
• Přednáška 8:
  • Neorientovaný graf
  • Vrchol
  • Hrana
  • Úplný graf
  • Diskrétní graf
  • Bipartitní graf
  • Úplný bipartitní graf
  • Neorientovaná hrana
  • Vztah incidence
  • Prostý graf
  • Obyčejný graf
  • Stupeň vrcholu
  • Regulární graf
  • Skóre grafu
  • Podgraf
  • Faktor grafu
  • Podgraf indukovaný množinou
  • Isomorfní graf
  • Cesta
  • Kružnice
  • Triviální cesta
  • Sled
  • Uzavřený sled
  • Triviální sled
  • Tah
  • Uzavřený tah
  • Cesta
  • Kružnice
  • Souvislý graf
  • Doplněk obyčejného grafu
  • Vzdálenost vrcholů
  • Komponenta souvislosti
  • Relace dostupnosti
• Přednáška 9:
  • Matice sousednosti
  • Matice incidence
  • Eulerovský graf
  • Eulerovský tah
• Přednáška 10:
  • Strom
  • Most
  • Les
  • Kostra grafu
  • Minimální kostra
• Přednáška 11:
  • Orientovaný graf
  • Vrchol
  • Orientovaná hrana
  • Smyčka
  • Antiparalelní hrana
  • Vztah incidence
  • Vstupní stupeň vrcholu
  • Výstupní stupeň vrcholu
  • Stupeň vrcholu
  • Orientovaný sled
  • Uzavřený orientovaný sled
  • Orientovaný tah
  • Orientovaná cesta
  • Cyklus
  • Orientovaně dostupný vrchol
  • Silně souvislý graf
  • Komponenta silné souvislosti
  • Eulerovský tah
  • Eulerovský orientovaný graf
  • Kořen
  • Kořenový strom
  • Acyklický graf
  • Topologické očíslování vrcholů
  • Jádro orientovaného grafu
• Přednáška 12:
  • Silně souvislý graf
  • Komponenta silné souvislosti
  • Kondenzace grafu
  • DSF
  • BFS
  • Hledání komponent souvislosti
• Přednáška 13:
  • Obarvení vrcholů grafu
  • K-barevný graf
  • Barevnost grafu
  • Klikovost grafu
  • Nezávislá množina
  • Maximální nezávislá množina
  • Nezávislost grafu
  • Sekvenční barvení grafu
• Přednáška 14:
  • Rovinný graf
  • Nakreslení neorientovaného grafu
  • Rovinné nakreslení grafu
  • Sférické nakreslení grafu
  • Topologický rovinný graf
  • Stěna topologického rovinného grafu
  • Stupeň stěny
  • Duální graf
  • Platónská tělesa

---

---