Výroková logika

Na tento článek je přesměrováno heslo Výroková formule. Tento článek pojednává o pojmu matematické logiky. Další významy jsou uvedeny v článku Formule.

Na tento článek je přesměrováno heslo Výroková formule. Tento článek pojednává o pojetí formule ve výrokové logice. O pojetí formule v predikátové logice pojednává článek Formule (logika).

V matematice a logice se pojmem výroková logika označuje formální odvozovací systém, ve kterém atomické formule tvoří výrokové proměnné (na rozdíl od predikátové logiky).

Výroková logika se skládá ze

syntaktických pravidel - určují, kdy je formule správně utvořená,
odvozovacích pravidel - určují, jak z jedněch formulí správně odvozovat další stále validní důsledkové formule,
(nejvýše spočetné) množiny axiomů a axiomatických schémat.

Výroková formule[editovat]

Nechť P je neprázdná množina symbolů nazývaných atomické výrokové formule. Abecedou jazyka výrokové logiky L_P jsou prvky množiny P, symbol ¬ pro negaci a → pro implikaci. Výrokové formule jazyka L_P definujeme následovně:

Každá atomická výroková formule je též výroková formule.
Jestliže A je výroková formule, je i (¬A) výroková formule.
Jsou-li A, B výrokové formule, je i (A → B) výroková formule.
Nic jiného není výroková formule.

Pro zkrácení zápisu dále používáme označení

konjunkce: $A \and B$ pro $\neg(A \Rightarrow \neg B)$
disjunkce: $A \vee B$ pro $\neg A \Rightarrow B$
ekvivalence: $A \Leftrightarrow B$ pro $(A \Rightarrow B) \and (B \Rightarrow A)$
implikace

Pravdivost[editovat]

Pravdivostní ohodnocení atomických formulí je zobrazení v : P → {0,1}. Rozšíření w na výrokové formule definujeme takto:

w(A) = v(A) je-li A atomická formule
w(¬A) = 1 je-li w(A) = 0
w(¬A) = 0 je-li w(A) = 1
w(A → B) = 0 pokud w(A) = 1 a w(B) = 0
w(A → B) = 1 pokud w(A) = 0 nebo w(B) = 1

Odvozování[editovat]

Axiomy[editovat]

A → (B → A)
(A → (B → C)) → ((A → B) → (A → C))
(¬B → ¬A) → (A → B)

Odvozovací pravidlo[editovat]

(pravidlo Modus ponens) Jestliže A platí a A → B platí, pak B platí.

Důkaz[editovat]

Důkazem nazveme konečnou posloupnost $A_1,\ldots,A_n$ , jestliže pro každé $i \leq n$ je $A_i$ buď závěr odvozovacího pravidla, jehož předpoklady jsou mezi $A_1$ a $A_{i-1}$ , nebo axiom.