Výroková logika

Výroková logika, také známá jako propoziční logika nebo boolovská logika, je oblast matematiky, která se zabývá logickými vztahy mezi výroky nebo prohlášeními. Je to jednoduchá, ale mocná forma logiky, kterou lze použít k řešení a analýze široké škály problémů. Je základem pro mnoho oblastí matematiky a hlavně informatiky, včetně programování, návrhu hardware a umělé inteligence.

Podporuje schopnost lidského myšlení zazývanou dedukce. Děduktivní uvažování znamená mít schopnost z určitých předpokladů odvodit korektní závěr. Dedukce je jednou ze základních komponent kritického myšlení.

Základem je výrok (propozice) za který považujeme každou větu, u které má smysl se ptát, zda je, či není pravdivá. Tyto výroky považujeme za nedělitelné prvky a je možné s nimi pracovat jako s prvky nějaké množiny.

Ve výrokové logice používáme spojky, kterými formalizujeme některé spojky přirozeného jazyka.

Základní logické spojky ve výrokové logice jsou:

• Konjunkce ∧: Výsledek je pravdivý, pokud jsou obě propozice pravdivé.
• Disjunkce (∨): Výsledek je pravdivý, pokud alespoň jedna propozice je pravdivá.
• Negace (¬): Výsledek je pravdivý, pokud je původní propozice nepravdivá.
• Implikace (⇒ IF...THEN): Výsledek je pravdivý, pokud je první propozice nepravdivá nebo obě propozice jsou pravdivé.
• Ekvivalence (⇔IFF, IF AND ONLY IF): Výsledek je pravdivý, pokud jsou obě propozice buď obě pravdivé nebo obě nepravdivé.

Můžete narazit

• Shefferův symbol ↑ (NAND) má význam ¬(A∧B)
• Peircův symbol ↓ (NOR) má význam ¬(A∨B)

Formule výrokové logiky

Stavební kameny výrokové logiky jsou výroky. Prvotní formule - neobsahuje kvantifikátor nebo logickou spojku.

Prvotní formule

Nechť P je neprázdná množina, jejímiž prvky jsou slova nějakého jazyka, případně jen písmena $p, q, r, p_1, p_2, ...$ Prvky této množiny budeme nazývat prvotní formule.

Formule výrokové logiky

Je posloupnost symbolů z jazyka výrokové logiky, která vznikne aplikací následujících pravidel:

• Prvotní formule je formule
• Jsou-li A a B formule, pak i ¬A, (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) jsou formule.

Pravdivostní ohodnocení

Je libovolná funkce $v: P → \{0, 1\}$ se nazývá pravdivostní ohodnocení.

Formule A je

• pravdivá při ohodnocení v, právě když $v(A) = 1$
• formule je nepravdivá při ohodnocení v, právě když $v(A) = 0$

Abstraktně lze na binární výrokovou spojku pohlížet jako na nějaké zobrazení z ${0, 1} × {0, 1} -> {0, 1}$. Takových „spojek“ potom existuje tolik, kolik je všech zobrazení z $2^2$ do 2, tedy $2^{2^2} = 16$.