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 11:43] – [Sémantika výrokové logiky] 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 10: Line 10:
  
 ==== Sémantika výrokové logiky ==== ==== 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: Výroková formule vzniká pomocí spojek a závorek podle přesné syntaxe. Spojky dělíme na:
Line 25: Line 40:
   * $u(α ⇒ β) = 0$ právě když $u(α) = 1$ a $u(β) = 0$   * $u(α ⇒ β) = 0$ právě když $u(α) = 1$ a $u(β) = 0$
   * $u(α ⇔ β) = 1$ právě když $u(α) = u(β)$   * $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** – pravdivá ve všech ohodnoceních +  * **Tautologie** – formule, která je pravdivá ve všech ohodnoceních.   
-  * **kontradikce** – nepravdivá 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.   
-  * **splnitelná** – pravdivá alespoň v jednom ohodnocení+    * Příklad: $(a \lor \neg a)$ je tautologie – vždy pravda.
  
-**Booleovské operace** (pro hodnoty $\{0,1\}$): +  * **Kontradikce** – formule, která je nepravdivá ve všech ohodnoceních.   
-  * $x \cdot y = \min(x, y)$ +    * Tedy pro žádné přiřazení hodnot logickým proměnným není formule pravdivá – vždy je rovna 0.   
-  * $x + y = \max(x, y)$ +    * Příklad: $(a \land \neg a)$ je kontradikce – nikdy není pravda.
-  * $\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$.+  * **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$.
  
  
Line 60: Line 84:
  
 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 79: Line 113:
  
 **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 90: Line 124:
 **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 95: Line 136:
 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 104: 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 128: 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 144: 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 187: 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 206: 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 228: 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:

Navigation

Playground

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