Logika

Note	Výroková a predikátová logika, operace, kvantifikátory, syntax. Sémantika, pravdivost, splnitelnost, dokazatelnost. Normální formy formulí (konjunktivní a disjunktivní, prenexní, Hornovy klauzule). IB000, IB101

Matematická logika se zabývá zkoumáním a formalizováním filozofické logiky, hlavně těch částí, na kterých matematika stojí.

Výroková logika

Zabývá se pravdivostí a dokazatelností tvrzení — výroků.

Syntax

Syntax popisuje, jak tvořit výroky ze znaků abecedy. Abeceda výrokové logiky obsahuje

spočetně mnoho znaků pro výrokové proměnné: $X_{1}, X_{2}, X_{3}, ...$ ,
logické spojky: $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$ ,
závorky: $(,)$ .

Note	Pro odlišení symbolů abecedy od logických operací, jsou symboly zelené.

Formule je ve výrokové logice

každá výroková proměnná $X_{i}$ ,
pro formuli $F$ : $\neg F$ ,
pro formule $F_{1}$ a $F_{2}$ : $(F_{1} \land F_{2})$ , $(F_{1} \lor F_{2})$ , $(F_{1} \Rightarrow F_{2})$ , $(F_{1} \Leftrightarrow F_{2})$ .

Sémantika

Sémantika popisuje, jaký význam formule mají.

Pravdivostní ohodnocení (valuace) $v$

Zobrazení, které každé výrokové proměnné přiřadí hodnotu 0 nebo 1. Lze ji rozšířit na formule intuitivním způsobem.

Pravdivá formule

Formule $φ$ je pravdivá při valuaci $v$ , pokud $v (φ) = 1$ .

Splnitelná formule

Formule $φ$ je splnitelná, jestliže existuje valuace, při níž je pravdivá.

Tautologie

Formule, které je pravdivá při každé valuaci.

Ekvivalentní formule

Formule $φ, ψ$ jsou ekvivalentní, psáno $φ \approx ψ$ , jestliže pro každou valuaci $v$ platí $v (φ) = v (ψ)$ .

Splnitelný soubor $T$

Soubor $T$ obsahující výrokové formule je splnitelný, jestliže existuje valuace $v$ taková, že $v (φ) = 1$ pro každé $φ \in T$ .

Věta o kompaktnosti

Soubor formulí $T$ je splnitelný, právě když každá konečná část $T$ je splnitelná.

Odvozovací systém

Konečný soubor pravidel, která umožňují z daného souboru formulí odvodit další formuli.

Lukasiewiczův odvozovací systém

Systém pro $L (\Rightarrow, \neg)$ s axiomy tvaru:

$φ \Rightarrow (ψ \Rightarrow φ)$
$(φ \Rightarrow (ψ \Rightarrow ξ)) \Rightarrow ((φ \Rightarrow ψ) \Rightarrow (φ \Rightarrow ξ))$
$(\neg φ \Rightarrow \neg ψ) \Rightarrow (ψ \Rightarrow φ)$

a odvozovacím pravidlem modus ponens: Z $φ$ a $φ \Rightarrow ψ$ odvoď $ψ$ .

Důkaz

Důkaz formule $ψ$ z předpokladů $T$ je konečná posloupnost formulí $φ_{1}, φ_{2}, ..., φ_{k}$ , kde $φ_{k}$ je $ψ$ a každá formule $φ_{i}$ , kde $1 \leq i \leq k$ , je

prvek $T$ , nebo
axiom,
vznikne aplikací odvozovacího pravidla na dříve odvozené formule.

Dokazatelná formule

Formule $ψ$ je dokazatelná z předpokladů $T$ , psáno $T ⊢ ψ$ , jestliže existuje důkaz $ψ$ z předpokladů $T$ .

Predikátová logika

Zabývá se pravdivostí a dokazetelností vlastností objektů — predikátů.

Syntax

Jazyk (predikátové logiky) je systém predikátových a funkčních symbolů. Každý symbol má danou aritu, což je přirozené číslo.

Abecedu predikátové logiky pro jazyk $L$ tvoří

spočetně mnoho znaků pro proměnné: $x_{1}, x_{2}, ...$ ,
mimologické symboly, t.j. predikátové a funkční symboly $L$ ,
logické spojky,
kvantifikátory: $\forall, \exists$ ,
závorky a čárka.

Termem jazyka $L$ je slovo $t$ nad abecedou predikátové logiky pro $L$ tvaru

libovolné proměnné,
$f (t_{1}, ..., t_{n})$ , kde $t_{i}$ jsou termy, $f$ je funkční symbol s aritou $n$ .

Formule jazyka $L$ je slovo $φ$ nad abecedou predikátové logiky pro $L$ tvaru:

$P (t_{1}, ..., t_{n})$ , kde $P$ je predikátový symbol jazyka $L$ arity $n$ a $t_{i}$ jsou termy jazyka $L$ .
$\neg ψ$ , kde $ψ$ je formule,
$(ψ_{1} \circ ψ_{2})$ , kde $ψ_{1}, ψ_{2}$ jsou formule a $\circ$ je symbol logické spojky,
$\forall ψ$ nebo $\exists ψ$ , kde $ψ$ je formule.

Sémantika

Realizace $M$ jazyka $L$ je zadána

neprázdným souborem $M$ — univerzem (nosičem), jehož prvky jsou individua,
přiřazením, které každému $n$ -árnímu predikátovém symbolu $P$ přiřadí relaci $P_{M} \subseteq M^{n}$ ,
přiřazením, které každému $m$ -árnímu funkčnímu symbolu $f$ přiřadí funkci $f_{M} : M^{m} \to M$ .

Ohodnocení

Ohodnocení $e$ je zobrazení přiřazující proměnným prvky univerza $M$ .

Realizace termu $t$ při ohodnocení $e$ v realizaci $M$

Psáno $t^{M} [e]$ (případně jen $t [e]$ , je-li $M$ jasné z kontextu), definujeme induktivně

$x [e] = e (x)$ ,
$f (t_{1}, t_{2}, ..., t_{n}) = f_{M} (t_{1} [e], t_{2} [e], ..., t_{n} [e])$ .

Pravdivost formule

Formule $φ$ je pravdivá v realizaci $M$ při ohodnocení $e$ , jestliže $M ⊨ φ [e]$ .

Dokazatelná formule

Formule $φ$ je dokazatelná v teorii $T$ (soubor formulí), píšeme $T ⊢ φ$ , jestliže existuje důkaz $φ$ v $T$ .

Normální formy

Tvar formulí, které jsou naschvál omezené, protože v některých oblastech je jejich použití efektivnější.

Konjunktivní normální forma

Konjunkce klauzulí obsahujících disjunkce.

Příklad: $\neg A \land (B \lor C) \land (D \lor \neg E)$

Disjunktivní normální forma

Disjunkce klauzulí obsahujících konjunkce.

Příklad: $(D \land E) \lor (B \land C) \lor \neg A$

Úplná konjunktivní/disjunktivní forma

Každá klazule obsahuje všechny proměnné.

Prenexní normální forma

Kvantifikátory má pouze na začátku a vnitřek je v KNF (resp. DNF).

Eliminuj zbytečné kvantifikátory.
Přejmenuj proměnné tak, aby u každé kvantifikátoru byla jiná.
Eliminuj spojky jiné než $\land, \lor, \neg$ .
Přesuň negace dovnitř.
- Zaměň $\neg\forall x φ$ za $\exists x \neg φ$ .
- Zaměň $\neg (φ_{1} \land φ_{2})$ za $(\neg φ_{1} \lor \neg φ_{2})$ .
Přesuň kvantifikátory na začátek.
- Zaměň $φ_{1} \lor \exists x φ_{2}$ za $\exists x (φ_{1} \lor φ_{2})$ .
- Zaměň $\exists x φ_{1} \lor φ_{2}$ za $\exists x (φ_{1} \lor φ_{2})$ .
- Analogicky pro $\forall$ a $\land$ .
Převeď nekvantifikované podformule do KNF (nebo DNF).

Příklad: $\forall x \forall y \exists z \forall w ((P (x, y) \lor \neg Q (z)) \land (R (v, w) \lor R (y, w)))$

Hornovy klauzule

Disjunkce literálů s nejvýše jedním pozitivním literálem.

Příklad: $(P \lor \neg Q \lor \neg R)$ je ${P, \neg Q, \neg R}$

Dělíme je na

fakta — max jeden positivní literál,
pravidla — právě jeden pozitivní a alespoň jeden negativní literál, a
cíle — bez pozitivních literálů.