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 11:08] – [Syntaxe a sémantika výrokové a predikátové logiky. Základní pojmy teorie grafů.] 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 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 16: Line 31:
  
 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. 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: Ohodnocení: zobrazení $u: P(A) \to \{0, 1\}$ určuje, které formule jsou pravdivé (1) a které nepravdivé (0). Pravidla:
Line 23: 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 +**Typy formulí:** 
-  * **kontradikce** – nepravdivá ve všech ohodnoceních +  * **Tautologie** – formule, která je pravdivá ve všech ohodnoceních.   
-  * **splnitelná** – pravdivá alespoň v jednom ohodnocení+    * 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.
  
-**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 49: Line 76:
  
 **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$. **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). Alternativa: **Hilbertův systém** (axiomy + modus ponens).
Line 55: 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$ 
 + 
 +**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)
  
-**Základní pravidla**: +Formule $\varphi ≡ \psi$ právě tehdy, když $(\varphi ⇔ \psi)$ je **tautologie** – tedy vždy pravdivá.
-  * $\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.+**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 74: 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 85: 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 90: 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 99: 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 123: 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 139: 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 182: 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 201: 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 223: 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)