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:31] – [Normální formy formulí] zapleka3statnice: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://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 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 133: Line 132:
 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$. 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.
  
-==== Důsledek ve výrokové logice ====+**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$.
  
-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í**: 
 +  * $\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)$.
  
-**Důležitá tvrzení:** +**Příklad**: 
-  * $\varphi \models \psi$ právě tehdy, když $(\varphi ⇒ \psi)$ je tautologie +Mějme $S := \{a, a ⇒ b\}$ a $M := b$.   
-  * Množina $S \models \varphi$ právě tehdy, když $S ∪ \{\neg \varphi\}$ je nesplnitelná +Všechna ohodnocení, která splňují $S$, splňují i $b$. Proto $S \models M$.
-  * $S ∪ \{\varphi\} \models \psi \iff S \models (\varphi ⇒ \psi)$+
  
 **Příklady:** **Příklady:**
Line 150: Line 164:
   * $\{ \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 174: Line 181:
   * $(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 190: 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), nebo $F$ (nesplnitelnost)
 +
  
 {{:statnice:bakalar:pasted:20250517-191116.png}} {{:statnice:bakalar:pasted:20250517-191116.png}}
Line 233: Line 243:
  
 **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 252: Line 262:
   * 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 274: 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$
 +
 +{{:statnice:bakalar:pasted:20250517-201056.png}}
  
 **Věta o úplnosti**: **Věta o úplnosti**:

Trace: • b0b01ma2

Navigation

Playground

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