Výroková logika

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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

Výroková formule[editovat | editovat zdroj]

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

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

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

Pravdivost[editovat | editovat zdroj]

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

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

Odvozování[editovat | editovat zdroj]

Axiomy[editovat | editovat zdroj]

  1. A → (B → A)
  2. (A → (B → C)) → ((A → B) → (A → C))
  3. (¬B → ¬A) → (A → B)

Odvozovací pravidlo[editovat | editovat zdroj]

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

Důkaz[editovat | editovat zdroj]

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.

Jestliže existuje důkaz výrokové formule A, říkáme o této formuli, že je dokazatelná.

Externí odkazy[editovat | editovat zdroj]