The wiki page is under active construction, expect bugs.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b0b01lgr [2025/05/19 12:10] – [Sémantika výrokové logiky] zapleka3statnice:bakalar:b0b01lgr [2025/06/01 11:45] (current) – zapleka3
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://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]] [[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]]
Line 52: Line 52:
 **Typy formulí:** **Typy formulí:**
   * **Tautologie** – formule, která je pravdivá ve všech ohodnoceních.     * **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.   +    * 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.+    * Příklad: $(a \lor \neg a)$ je tautologie – vždy pravda.
  
   * **Kontradikce** – formule, která je nepravdivá ve všech ohodnoceních.     * **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.   +    * 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.+    * Příklad: $(a \land \neg a)$ je kontradikce – nikdy není pravda.
  
   * **Splnitelná formule** – formule, která je pravdivá alespoň v jednom ohodnocení.     * **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.   +    * 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$. +    * Příklad: $(a \land b)$ je splnitelná, například když $a = 1$ a $b = 1$.
- +
-**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$.+
  
  
Line 92: Line 85:
  
 Formule $\varphi$ a $\psi$ jsou **sémanticky (tautologicky) ekvivalentní**, pokud mají ve všech ohodnoceních stejnou pravdivostní hodnotu:   Formule $\varphi$ a $\psi$ jsou **sémanticky (tautologicky) ekvivalentní**, pokud mají ve všech ohodnoceních stejnou pravdivostní hodnotu:  
-$\varphi ≡ \psi$ značíme jako $\varphi \models \models \psi$+Zapisujeme jako: $\varphi \models\models \psi$ nebo také $\varphi ≡ \psi$
  
-**Základní pravidla**: +**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.
-  * $\varphi ≡ \varphi$ +
-  * Je-li $\varphi ≡ \psi$, pak i $\psi ≡ \varphi$ +
-  * Je-li $\varphi ≡ \psi$ a $\psi ≡ \chi$, pak i $\varphi ≡ \chi$+
  
-Formule $\varphi ≡ \psi$ právě tehdy, když $(\varphi ⇔ \psi)$ je tautologie.+**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í ==== ==== Normální formy formulí ====
Line 111: Line 114:
  
 **Disjunktivní normální forma (DNF)**: **Disjunktivní normální forma (DNF)**:
-  * formule tvořená disjunkcí mintermů+  * 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í   * vhodná pro přímé zápisy splnitelných funkcí
  
 **Konjunktivní normální forma (CNF)**: **Konjunktivní normální forma (CNF)**:
-  * formule tvořená konjunkcí maxtermů+  * 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)   * vhodná pro důkaz nesplnitelnosti (např. rezoluční metodou)
  
Line 122: Line 125:
 **Booleovy funkce**: **Booleovy funkce**:
 Každé zobrazení $f: \{0,1\}^n \to \{0,1\}$ lze vyjádřit jako výrokovou formuli v CNF i DNF. 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 ==== ==== Důsledek ve výrokové logice ====
Line 127: Line 137:
 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$. 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$.
  
-**Důležitá tvrzení:** +**Syntaktický důsledek vs. sémantický důsledek**: 
-  * $\varphi \models \psi$ právě tehdy, když $(\varphi ⇒ \psi)$ je tautologie +  * $\varphi \vdash \psi$ znamená, že $\psi$ lze **formálně odvodit** z $\varphi$ pomocí pravidel dedukce (např. přirozené dedukce nebo Hilbertova systému). 
-  * Množina $S \models \varphi$ právě tehdy, když $S ∪ \{\neg \varphi\}$ je nesplnitelná +  * $\varphi \models \psi$ znamená, že ve **všech ohodnoceních**, kde je $\varphi$ pravdivá, je pravdivá i $\psi$. 
-  * $S ∪ \{\varphi\} \models \psi \iff S \models (\varphi ⇒ \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:** **Příklady:**
Line 136: Line 165:
   * $\{ \alpha ⇒ \beta, \beta ⇒ \gamma \} \models (\alpha ⇒ \gamma)$   * $\{ \alpha ⇒ \beta, \beta ⇒ \gamma \} \models (\alpha ⇒ \gamma)$
  
-**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) 
  
 ==== Úplné systémy logických spojek ==== ==== Úplné systémy logických spojek ====
Line 160: Line 182:
   * $(a ∨ b) ≡ (\neg a ⇒ b)$   * $(a ∨ b) ≡ (\neg a ⇒ b)$
   * $(a ∧ b) ≡ \neg(a ⇒ \neg b)$   * $(a ∧ b) ≡ \neg(a ⇒ \neg b)$
- 
-**Booleova algebra**: 
-  * Základní operace: $x \cdot y$, $x + y$, $\bar{x}$ 
-  * Každá Booleova funkce má ekvivalentní formuli v DNF i CNF 
  
 ==== Schopnost formalisace a řešení logických úloh ==== ==== Schopnost formalisace a řešení logických úloh ====
Line 176: Line 194:
  
 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), nebo $F$ (nesplnitelnost)
 +
  
 {{:statnice:bakalar:pasted:20250517-191116.png}} {{:statnice:bakalar:pasted:20250517-191116.png}}
Line 219: Line 244:
  
 **Platí**: **Platí**:
-  * $\varphi \models\!\models \psi$ právě když $(\varphi \Leftrightarrow \psi)$ je tautologie.+  * $\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 238: Line 263:
   * Zachovává **ekvisplnitelnost**, ale ne tautologickou ekvivalenci.   * Zachovává **ekvisplnitelnost**, ale ne tautologickou ekvivalenci.
  
-{{:statnice:bakalar:pasted:20250517-201056.png}} 
  
 ==== Důsledek v predikátové logice ==== ==== Důsledek v predikátové logice ====
Line 260: Line 284:
   * 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$
 +
 +{{:statnice:bakalar:pasted:20250517-201056.png}}
  
 **Věta o úplnosti**: **Věta o úplnosti**:

Trace:

Navigation

Playground

QR Code
QR Code statnice:bakalar:b0b01lgr (generated for current page)