Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| statnice:bakalar:b0b01lgr [2025/05/19 13:17] – [Důsledek ve výrokové logice] zapleka3 | statnice:bakalar:b0b01lgr [2026/06/13 16:50] (current) – [Sémantika výrokové logiky] badinmic | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ==== Syntaxe a sémantika výrokové a predikátové logiky. Základní pojmy teorie grafů. ==== | + | ====== Syntaxe a sémantika výrokové a predikátové logiky. Základní pojmy teorie grafů. |
| [[https:// | [[https:// | ||
| Line 49: | Line 49: | ||
| 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)$. | 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í:** | **Typy formulí:** | ||
| * **Tautologie** – formule, která je pravdivá ve všech ohodnoceních. | * **Tautologie** – formule, která je pravdivá ve všech ohodnoceních. | ||
| Line 194: | Line 193: | ||
| Další nástroje: | Další nástroje: | ||
| - | * **Rezoluční metoda** pro ověření splnitelnosti množiny klausulí (v CNF) | ||
| * **Syntaktické důsledky** pomocí přirozené dedukce nebo Hilbertova systému | * **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), | ||
| + | |||
| {{: | {{: | ||
| Line 237: | Line 243: | ||
| **Platí**: | **Platí**: | ||
| - | * $\varphi | + | * $\varphi \models \psi$ právě když $(\varphi \Leftrightarrow \psi)$ je tautologie. |
| * Např. $\neg \forall x\, P(x) \models\!\models \exists x\, \neg P(x)$ | * Např. $\neg \forall x\, P(x) \models\!\models \exists x\, \neg P(x)$ | ||
| Line 256: | Line 262: | ||
| * Zachovává **ekvisplnitelnost**, | * Zachovává **ekvisplnitelnost**, | ||
| - | {{: | ||
| ==== Důsledek v predikátové logice ==== | ==== Důsledek v predikátové logice ==== | ||
| Line 278: | Line 283: | ||
| * Odvozovací systém bez axiomů, používá pravidla pro spojky i kvantifikátory | * Odvozovací systém bez axiomů, používá pravidla pro spojky i kvantifikátory | ||
| * Dedukce: $S \vdash \varphi$ znamená, že $\varphi$ lze odvodit ze $S$ | * Dedukce: $S \vdash \varphi$ znamená, že $\varphi$ lze odvodit ze $S$ | ||
| + | |||
| + | {{: | ||
| **Věta o úplnosti**: | **Věta o úplnosti**: | ||
