Syntaxe a sémantika výrokové a predikátové logiky. Základní pojmy teorie grafů.

B0B01LGR Webové stránky předmětu Manuál 101

• Syntax výrokové logiky – sémantika výrokové logiky, důkazový systém přirozená dedukce. Významová (sémantická) ekvivalence formulı́ výrokové logiky, normálnı́ formy formulı́, důsledek ve výrokové logice. Úplné systémy logických spojek. Schopnost formalisace a řešení logických úloh s využitím výrokové logiky.
• Syntax predikátové logiky – sémantika predikátové logiky, významová (sémantická) ekvivalence formulı́ predikátové logiky, normálnı́ formy formulı́, důsledek v predikátové logice. Schopnost formalisace a řešení logických úloh s využitím predikátové logiky.
• Základnı́ pojmy a definice teorie grafů – schopnost formálnı́ práce s těmito pojmy. Stromy a jejich vlastnosti, minimálnı́ kostry a algoritmy na jejich hledánı́. Komponenty silné souvislosti a algoritmus na jejich hledánı́. Schopnost modelovánı́ praktických problémů s využitím grafů.

Definice výrokové formule:

Máme danou neprázdnou množinu $A$ tzv. *atomických výroků* (logických proměnných). Výroková formule (zkráceně jen *formule*) je konečná posloupnost prvků z množiny $A$, logických spojek a závorek, která vzniká podle těchto pravidel:

• Každá logická proměnná $a \in A$ (atomický výrok) je výroková formule.
• Jsou-li $\alpha$, $\beta$ výrokové formule, pak i následující jsou výrokové formule:
  • $\neg\alpha$
  • $(\alpha \land \beta)$
  • $(\alpha \lor \beta)$
  • $(\alpha \Rightarrow \beta)$
  • $(\alpha \Leftrightarrow \beta)$
• Nic jiného než to, co vzniklo konečným použitím pravidel 1 a 2, není výroková formule.

Množinu všech výrokových formulí vytvořených z proměnných v $A$ značíme jako $P(A)$.

Výroková formule vzniká pomocí spojek a závorek podle přesné syntaxe. Spojky dělíme na:

• unární ¬
• binární ∧, ∨, ⇒, ⇔ (a případně další jako ↑ (NAND), ↓ (NOR), ⊕ (XOR))

Formule lze znázornit jako syntaktický strom, kde uzly odpovídají spojkám a listy logickým proměnným. Strom odhaluje strukturu a podformule.

Ohodnocení: zobrazení $u: P(A) \to \{0, 1\}$ určuje, které formule jsou pravdivé (1) a které nepravdivé (0). Pravidla:

• $u(¬α) = 1$ právě když $u(α) = 0$
• $u(α ∧ β) = 1$ právě když $u(α) = 1$ a $u(β) = 1$
• $u(α ∨ β) = 0$ právě když $u(α) = u(β) = 0$
• $u(α ⇒ β) = 0$ právě když $u(α) = 1$ a $u(β) = 0$
• $u(α ⇔ β) = 1$ právě když $u(α) = u(β)$

Věta: Každé zobrazení $u_0: A \to \{0, 1\}$ jednoznačně určuje ohodnocení $u: P(A) \to \{0, 1\}$ takové, že $u_0(a) = u(a)$ pro všechna $a \in A$.

Důsledek: Dvě ohodnocení $u, v: P(A) \to \{0, 1\}$ jsou shodná právě tehdy, když pro všechny logické proměnné $x \in A$ platí $u(x) = v(x)$.

Typy formulí: Typy formulí:

• Tautologie – formule, která je pravdivá ve všech ohodnoceních.
  • To znamená, že bez ohledu na to, jaké hodnoty (0 nebo 1) přiřadíme jednotlivým logickým proměnným, výsledná pravdivostní hodnota formule bude vždy 1.
  • Příklad: $(a \lor \neg a)$ je tautologie – vždy pravda.

• Kontradikce – formule, která je nepravdivá ve všech ohodnoceních.
  • Tedy pro žádné přiřazení hodnot logickým proměnným není formule pravdivá – vždy je rovna 0.
  • Příklad: $(a \land \neg a)$ je kontradikce – nikdy není pravda.

• Splnitelná formule – formule, která je pravdivá alespoň v jednom ohodnocení.
  • To znamená, že existuje přiřazení hodnot logickým proměnným, pro které má formule pravdivostní hodnotu 1.
  • Příklad: $(a \land b)$ je splnitelná, například když $a = 1$ a $b = 1$.

Cílem je formálně odvodit formuli $\varphi$ z množiny formulí $S$ pomocí pravidel.

Přirozená dedukce:

• Bez axiomů
• Pracuje se základními spojkami (většinou bez ⇔)
• Každá spojka má dvě pravidla:
  • i-rule (introduction): zavádí spojku
  • e-rule (elimination): odstraňuje spojku

Odvození je konečná posloupnost formulí, kde každá vzniká aplikací pravidla na předchozí formule. Pokud existuje odvození $\varphi$ z $S$, zapisujeme $S ⊢ \varphi$.

Příklad jednoduchého odvození:

• $\{A ∧ B\} ⊢ A$ – aplikací pravidla ∧-eliminace.

Alternativa: Hilbertův systém (axiomy + modus ponens).

Formule $\varphi$ a $\psi$ jsou sémanticky (tautologicky) ekvivalentní, pokud mají ve všech ohodnoceních stejnou pravdivostní hodnotu: Zapisujeme jako: $\varphi \models\models \psi$ nebo také $\varphi ≡ \psi$

Definice: Řekněme, že formule $\varphi$ a $\psi$ jsou tautologicky ekvivalentní (také sémanticky ekvivalentní), jestliže pro každé ohodnocení $u$ platí $u(\varphi) = u(\psi)$. Jinými slovy, v každém ohodnocení mají obě formule stejnou pravdivostní hodnotu.

Základní vlastnosti ekvivalence:

• $\varphi ≡ \varphi$ (reflexivita)
• Je-li $\varphi ≡ \psi$, pak i $\psi ≡ \varphi$ (symetrie)
• Je-li $\varphi ≡ \psi$ a $\psi ≡ \chi$, pak i $\varphi ≡ \chi$ (transitivita)

Formule $\varphi ≡ \psi$ právě tehdy, když $(\varphi ⇔ \psi)$ je tautologie – tedy vždy pravdivá.

Příklady ekvivalentních formulí:

• $\neg\neg \alpha ≡ \alpha$
• $\neg(\alpha \land \beta) ≡ (\neg \alpha \lor \neg \beta)$
• $\neg(\alpha \lor \beta) ≡ (\neg \alpha \land \neg \beta)$ (de Morganova pravidla)
• $\alpha \land (\beta \lor \gamma) ≡ (\alpha \land \beta) \lor (\alpha \land \gamma)$
• $\alpha \lor (\beta \land \gamma) ≡ (\alpha \lor \beta) \land (\alpha \lor \gamma)$ (distributivita)
• $(\alpha ⇒ \beta) ≡ (\neg \alpha \lor \beta)$ (ekvivalentní přepis implikace)

Každou výrokovou formuli lze přepsat do konjunktivní (CNF) nebo disjunktivní (DNF) normální formy.

Základní pojmy:

• Literál – logická proměnná nebo její negace
• Minterm – konjunkce literálů
• Maxterm (klausule) – disjunkce literálů

Disjunktivní normální forma (DNF):

• formule tvořená disjunkcí mintermů, minterm je literál nebo konjunkce konečně mnoha literálů
• vhodná pro přímé zápisy splnitelných funkcí

Konjunktivní normální forma (CNF):

• formule tvořená konjunkcí maxtermů, maxterm je literál nebo disjunkce konečně mnoha literálů
• vhodná pro důkaz nesplnitelnosti (např. rezoluční metodou)

Hloubka syntaktického stromu DNF i CNF je maximálně 3 (konjunkce/disjunkce → literály).

Booleovy funkce: Každé zobrazení $f: \{0,1\}^n \to \{0,1\}$ lze vyjádřit jako výrokovou formuli v CNF i DNF.

Booleovské operace (pro hodnoty $\{0,1\}$):

• $x \cdot y = \min(x, y)$
• $x + y = \max(x, y)$
• $\bar{x} = 1 - x$

Ohodnocení formule určuje její pravdivost ve specifickém světě – tedy za konkrétní přiřazení hodnot 0 a 1 jednotlivým proměnným. Například pro formuli $(a \land b)$ je její hodnota 1 pouze tehdy, když $a = 1$ a $b = 1$.

Formule $\psi$ je sémantickým důsledkem formule $\varphi$, značíme $\varphi \models \psi$, pokud každé ohodnocení, které splňuje $\varphi$, splňuje i $\psi$.

Syntaktický důsledek vs. sémantický důsledek:

• $\varphi \vdash \psi$ znamená, že $\psi$ lze formálně odvodit z $\varphi$ pomocí pravidel dedukce (např. přirozené dedukce nebo Hilbertova systému).
• $\varphi \models \psi$ znamená, že ve všech ohodnoceních, kde je $\varphi$ pravdivá, je pravdivá i $\psi$.
• Platí: pokud $\varphi \vdash \psi$, pak $\varphi \models \psi$ (správnost systému); opačně platí v úplných systémech (úplnost).

Formální definice:

• Mějme množinu formulí $S$ a ohodnocení $u: P(A) \to \{0, 1\}$.
  • $S$ je pravdivá v ohodnocení $u$, pokud $u(\varphi) = 1$ pro každou $\varphi \in S$.
  • $S$ je nepravdivá v ohodnocení $u$, pokud existuje alespoň jedna $\varphi \in S$, pro kterou $u(\varphi) = 0$.
  • $S$ je splnitelná, pokud existuje alespoň jedno ohodnocení $u$, ve kterém je všechno z $S$ pravdivé.
  • $S$ je nesplnitelná, pokud žádné takové ohodnocení neexistuje.

Definice důsledku:

• Formule $\varphi$ je důsledkem množiny $S$, značíme $S \models \varphi$, právě tehdy, když každé ohodnocení, které splňuje všechny formule v $S$, splňuje i $\varphi$.

Důležitá tvrzení:

• $\varphi \models \psi$ právě tehdy, když $(\varphi ⇒ \psi)$ je tautologie.
• $S \models \varphi$ právě tehdy, když množina $S ∪ \{\neg \varphi\}$ je nesplnitelná.
• $S ∪ \{\varphi\} \models \psi$ právě tehdy, když $S \models (\varphi ⇒ \psi)$.

Příklad: Mějme $S := \{a, a ⇒ b\}$ a $M := b$. Všechna ohodnocení, která splňují $S$, splňují i $b$. Proto $S \models M$.

Příklady:

• $\{ \alpha, \alpha ⇒ \beta \} \models \beta$
• $\{ \alpha ⇒ \beta, \beta ⇒ \gamma \} \models (\alpha ⇒ \gamma)$

Definice: Množina spojek je úplná, pokud lze pomocí jejích členů vyjádřit libovolnou výrokovou formuli.

Příklady úplných systémů:

• $\{\neg, ∧\}$
• $\{\neg, ∨\}$
• $\{\neg, ⇒\}$
• Jedna spojka: NAND (|), NOR (↓)

Převody mezi spojkami:

• $(a ⇒ b) ≡ (\neg a ∨ b)$
• $(a ∨ b) ≡ \neg(\neg a ∧ \neg b)$
• $(a ∧ b) ≡ \neg(\neg a ∨ \neg b)$
• $(a ∨ b) ≡ (\neg a ⇒ b)$
• $(a ∧ b) ≡ \neg(a ⇒ \neg b)$

Typická úloha: ověřit, zda je formule tautologie, kontradikce nebo splnitelná: Příklad: $((a \land b) \Rightarrow a)$

• Má být nepravdivá, pokud $u((a \land b) \Rightarrow a) = 0$
• To platí jen tehdy, když $u(a \land b) = 1$ a $u(a) = 0$
• Ale $a \land b = 1 \Rightarrow u(a) = 1 \land u(b) = 1$
• Spor: $u(a) = 1$ i $u(a) = 0$ současně nelze → formule je tautologie

Další nástroje:

• Syntaktické důsledky pomocí přirozené dedukce nebo Hilbertova systému
• Rezoluční metoda (alternativa pro důkaz nesplnitelnosti množiny formulí v CNF):
  • Převeď formule na CNF, vytvoř množinu klausulí
  • Opakuj aplikaci rezoluce na dvojice klausulí
  • Pokud vznikne prázdná klausule (označena $F$), množina je nesplnitelná
  • Rezoluční metoda se často používá pro automatizovaný důkaz nesplnitelnosti – například v oblastech jako SAT solving, ověřování softwaru nebo umělá inteligence.

Doporučený postup: Postupně eliminuj proměnné pomocí rezoluce, až zbude buď prázdná množina (splnitelnost), nebo $F$ (nesplnitelnost)

Formule predikátové logiky vyjadřují vlastnosti objektů a vztahy mezi nimi. Interpretace predikátové formule zahrnuje: neprázdnou množinu objektů (univerzum), přiřazení hodnot konstantám, funkcím a predikátům, a ohodnocení proměnných. Výsledná pravdivost závisí na tom, jak interpretace přiřazuje význam jednotlivým symbolům.

Na rozdíl od výrokové logiky, kde je pravdivost daná pouze hodnotou proměnných, v predikátové logice je třeba zohlednit i strukturu objektů (univerzum) a význam predikátů – tedy co znamená např. $P(x)$ pro konkrétní $x$.

Termy:

• Proměnná nebo konstantní symbol je term.
• Z termů lze tvořit složené termy pomocí funkčních symbolů: např. $f(x, y)$.

Formule:

• Atomické formule:
  • Rovnost dvou termů: $t_1 = t_2$
  • Aplikace predikátu na termy: $P(t_1, ..., t_n)$
• Složené formule: vznikají pomocí výrokových spojek:
  • $\neg$ (negace)
  • $\land$, $\lor$, $\Rightarrow$, $\Leftrightarrow$
  • Kvantifikátory: $\forall$, $\exists$

Syntaktický strom:

• Kvantifikátory jsou unární, ostatní spojky mají obvyklou aritu.
• Strom lze tvořit i pro termy.
• Podformule odpovídají podstromům.

Volné a vázané proměnné:

• Výskyt proměnné je vázaný, pokud spadá pod odpovídající kvantifikátor.
• Jinak je volný.
• Sentence = formule bez volných výskytů.
• Otevřená formule = alespoň jedna volná proměnná.
• Rovnost formulí: liší se jen přejmenováním vázaných proměnných.

Formule $\varphi$ a $\psi$ jsou sémanticky ekvivalentní, značíme $\varphi \models\!\models \psi$, pokud mají ve všech interpretacích stejnou pravdivostní hodnotu.

Platí:

• $\varphi \models \psi$ právě když $(\varphi \Leftrightarrow \psi)$ je tautologie.
• Např. $\neg \forall x\, P(x) \models\!\models \exists x\, \neg P(x)$

Prenexní tvar:

• Kvantifikátory se vytýkají na začátek formule.
• Možné pomocí přejmenování proměnných a logických pravidel.

Klausule:

• Sentence s pouze obecnými kvantifikátory na začátku a disjunkcí literálů.
• Literál = atomická formule nebo její negace.

Skolemizace:

• Odstranění existenčních kvantifikátorů.
• Nahrazení konstantou ($\exists x \to c$) nebo funkčním symbolem ($\exists y \to f(x)$).
• Například: $\forall x \exists y\, P(x, y)$ lze Skolemizovat jako $\forall x\, P(x, f(x))$, kde $f$ je tzv. Skolemovská funkce závislá na $x$.
• Zachovává ekvisplnitelnost, ale ne tautologickou ekvivalenci.

Formule $\varphi$ je sémantickým důsledkem množiny formulí $S$, značíme $S \models \varphi$, pokud každá interpretace, která splňuje $S$, splňuje i $\varphi$.

Platí:

• $S \models \varphi \iff S \cup \{\neg \varphi\}$ je nesplnitelná
• $\varphi \models \psi \iff \varphi \Rightarrow \psi$ je tautologie
• $\varphi \models \psi \iff \varphi \models \psi \land \psi \models \varphi$

Příklad (vyvrácení důsledku):

• $\forall x \exists y M(x, y) \not\models \exists y \forall x M(x, y)$

(Existuje větší číslo než každé dané ≠ Existuje jedno číslo větší než všechna.)

Přirozená dedukce:

• Odvozovací systém bez axiomů, používá pravidla pro spojky i kvantifikátory
• Dedukce: $S \vdash \varphi$ znamená, že $\varphi$ lze odvodit ze $S$

Věta o úplnosti:

• $S \models \varphi$ právě tehdy, když $S \vdash \varphi$
• To znamená, že každý sémantický důsledek lze skutečně formálně odvodit, což je důkaz toho, že přirozená dedukce je úplný důkazový systém.

Graf G = (V, E, ε)

• V – množina vrcholů
• E – množina hran
• ε – přiřazení hrany k vrcholům (incidence):
• Neorientovaný: ε(e) = {u, v}
• Orientovaný: ε(e) = (u, v)

Typy grafů:

• Prostý graf – bez paralelních hran
• Obyčejný graf – prostý + bez smyček
• Úplný graf (Kₙ) – každé dva vrcholy propojeny; počet hran $\frac{n(n-1)}{2}$
• Diskrétní graf – žádné hrany
• Bipartitní graf – vrcholy lze rozdělit na 2 množiny bez hran uvnitř množin
• Úplný bipartitní graf (K_{m,n}) – všechny možné hrany mezi 2 množinami; počet hran m·n

Stupeň vrcholu:

• Neorientovaný: počet incidentních hran $d(v)$
• Orientovaný: $d_{in}(v)$ a $d_{out}(v)$
• Smyčka se počítá dvakrát

Další pojmy:

• Paralelní hrany – různé hrany se stejnými vrcholy
• Regulární graf – každý vrchol má stejný stupeň r
• Faktor grafu – podgraf obsahující všechny vrcholy
• Isomorfismus grafů – existuje bijekce mezi vrcholy, zachovávající hrany

Sledy, cesty, tahy, kružnice:

• Sled – posloupnost vrcholů a hran ($v_0, e_1, v_1, ..., e_k, v_k$)
  • Uzavřený sled: $v_0 = v_k$
  • Triviální: jeden vrchol, žádná hrana
• Tah – sled bez opakujících se hran
• Cesta – tah bez opakujících se vrcholů
• Kružnice – uzavřená cesta s $v_0 = v_k$, žádný jiný vrchol se neopakuje

Strom

• Souvislý graf bez kružnic
• Počet hran: $n - 1$ (pro $n$ vrcholů)
• Obsahuje alespoň 2 listy (vrcholy stupně 1)
• Vlastnosti:
• Mezi každými dvěma vrcholy vede právě jedna cesta
• Odebrání libovolné hrany naruší souvislost
• Přidání hrany vytvoří kružnici

Kořenový strom:

• Orientovaný strom s kořenem
• Z kořene existuje cesta do všech vrcholů
• List = vrchol bez následníků

Kostra grafu

• Faktor grafu, který je strom
• Obsahuje všechny vrcholy, je souvislý a neobsahuje kružnici

Minimální kostra

• Kostra s nejnižším součtem ohodnocení hran

Kruskalův algoritmus:

• Hrany seřazeny podle ceny
• Přidává hrany, které nespojují již propojené komponenty, netvoří cyklus
• Složitost: O(m log n)

Primův algoritmus:

• Začíná z jednoho vrcholu a rozšiřuje strom o nejlevnější incidentní hranu
• Složitost: O(n²) nebo O(m log n)

Souvislý graf:

• Mezi každou dvojicí vrcholů existuje cesta

Silně souvislý graf:

• Orientovaný graf, kde existuje orientovaná cesta mezi každými dvěma vrcholy

Silně souvislá komponenta:

• Maximální množina vrcholů se silnou souvislostí

Kosarajův algoritmus:

• DFS na původním grafu (uložení pořadí opuštění vrcholů)
• Obrácení hran (transpozice grafu)
• DFS podle uloženého pořadí
• Každý DFS určí jednu komponentu
• Složitost: O(m + n)

Grafy modelují např.:

• Dopravní sítě, plánování tras
• Vztahy a závislosti (např. úkoly v projektovém řízení)
• Komunikační sítě, návrh obvodů

Reprezentace grafu:

• Seznam sousedů
• Matice sousednosti
• Matice incidence

Barevnost grafu (χ(G)):

• Nejmenší počet barev potřebných pro obarvení vrcholů
• Sekvenční barvení: χ(G) ≤ ∆ + 1 (∆ = max stupeň)

Nezávislá množina (α(G)):

• Množina vrcholů bez vnitřních hran
• Tvrzení: α(G) + χ(G) ≤ n + 1

Klika (ω(G)):

• Úplný podgraf – největší množina navzájem propojených vrcholů
• Tvrzení: ω(G) ≤ χ(G)

Eulerovský tah:

• Tah přes všechny hrany právě jednou
• Uzavřený - začíná a končí ve stejném vrcholu
• Podmínky:
  • Neorientovaný: všechny vrcholy mají sudý stupeň
  • Orientovaný: $d_{in}(v) = d_{out}(v)$ pro každý vrchol

Hamiltonovské cesty a cykly:

• Hamiltonovská cesta: Cesta, která prochází každým vrcholem grafu právě jednou (ne nutně každou hranou)
• Hamiltonovský cyklus (kružnice): Uzavřená hamiltonovská cesta – začíná a končí ve stejném vrcholu

Tvrzení:

• $\alpha(G) \cdot \chi(G) \geq n$
• $\omega(G) \leq \chi(G)$
• $\alpha(G) + \chi(G) \leq n + 1$