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

[[https://fel.cvut.cz/cz/education/bk/predmety/46/80/p4680706.html|B0B01LGR]] [[https://math.fel.cvut.cz/en/people/gollova/lgr/lgr-prednaska.html|Webové stránky předmětu]] [[https://docs.google.com/document/d/1yGhEceIZR0vuSbkH2nP-3HrXwGxUGZck/edit|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ů.

===== 1. Výroková logika =====

==== Sémantika výrokové logiky ====

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

{{:statnice:bakalar:pasted:20250519-114348.png}}

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(β)$

{{:statnice:bakalar:pasted:20250519-114803.png}}

**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$.


==== Důkazový systém: přirozená dedukce ====

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

==== Významová (sémantická) ekvivalence formulí ====

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)

==== Normální formy formulí ====

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

==== Důsledek ve výrokové logice ====

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)$


==== Úplné systémy logických spojek ====

**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)$

==== Schopnost formalisace a řešení logických úloh ====

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)


{{:statnice:bakalar:pasted:20250517-191116.png}}

===== 2. Predikátová logika =====

==== Sémantika predikátové logiky ====

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.

==== Významová (sémantická) ekvivalence formulí ====

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)$

==== Normální formy formulí ====

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


==== Důsledek v predikátové logice ====

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$

==== Schopnost formalisace a řešení logických úloh ====

**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 v predikátové logice ===

**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$

{{:statnice:bakalar:pasted:20250517-201056.png}}

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


===== 3. Teorie grafů =====

==== Základní pojmy a definice ====

**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

==== Stromy a jejich vlastnosti ====

**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ů

==== Minimální kostry a algoritmy ====

**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)


==== Silně souvislé komponenty ====

**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)

==== Modelování praktických problémů ====

**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$