Výroková 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 je, stejně jako fuzzy logika, podoborem matematické 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.

Syntaxe

Nechť ${\displaystyle P}$ je neprázdná množina symbolů nazývaných atomické výrokové formule (též výrokové proměnné). Abecedou jazyka výrokové logiky ${\displaystyle L_{P}}$ jsou prvky množiny ${\displaystyle P}$, symbol ${\displaystyle \neg }$ pro negaci a ${\displaystyle \Rightarrow }$ pro implikaci. Výrokové formule jazyka ${\displaystyle L_{P}}$ definujeme následovně:

1. Každá atomická výroková formule je též výroková formule.
2. Jestliže ${\displaystyle A}$ je výroková formule, je i ${\displaystyle \neg A}$ výroková formule.
3. Jsou-li ${\displaystyle A,B}$ výrokové formule, je i ${\displaystyle A\Rightarrow B}$ výroková formule.
4. Formule vznikne konečným počtem užití pravidel 2 a 3.

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

• Konjunkce: ${\displaystyle A\land B}$ pro ${\displaystyle \neg (A\Rightarrow \neg B)}$
• Disjunkce: ${\displaystyle A\vee B}$ pro ${\displaystyle \neg A\Rightarrow B}$
• Ekvivalence: ${\displaystyle A\Leftrightarrow B}$ pro ${\displaystyle (A\Rightarrow B)\land (B\Rightarrow A)}$
• Exkluzivní disjunkce: ${\displaystyle A\oplus B}$ pro ${\displaystyle \neg (A\Leftrightarrow B)}$
• Tautologie: ${\displaystyle \top }$ pro ${\displaystyle A\Rightarrow A}$
• Kontradikce: ${\displaystyle \bot }$ pro ${\displaystyle \neg (A\Rightarrow A)}$
• NAND: ${\displaystyle A\uparrow B}$ pro ${\displaystyle \neg (A\land B)}$
• NOR: ${\displaystyle A\downarrow B}$ pro ${\displaystyle \neg (A\vee B)}$
• Obrácená implikace: ${\displaystyle A\Leftarrow B}$ pro ${\displaystyle B\Rightarrow A}$

Sémantika

Pravdivostní ohodnocení (též interpretace) atomických formulí je jakékoliv zobrazení ${\displaystyle v:P\to \{0,1\}}$. Rozšíření ${\displaystyle w}$ na výrokové formule definujeme induktivně takto:

1. ${\displaystyle w(A)=v(A)}$ je-li ${\displaystyle A}$ atomická formule
2. ${\displaystyle w(\neg A)=1-w(A)}$
3. ${\displaystyle w(A\Rightarrow B)=\max\{w(\neg A),w(B)\}}$

Pokud pro formuli ${\displaystyle A}$ a ohodnocení ${\displaystyle w}$ platí, že ${\displaystyle w(A)=1}$, říkáme, že formule ${\displaystyle A}$ je v ohodnocení ${\displaystyle w}$ pravdivá, což značíme též jako ${\displaystyle w\models A}$. V opačném případě říkáme, že formule ${\displaystyle A}$ je v ohodnocení ${\displaystyle w}$ nepravdivá.

O formuli ${\displaystyle A}$ říkáme, že je splnitelná, pokud existuje takové ${\displaystyle w}$, že platí ${\displaystyle w(A)=1}$ (též značeno ${\displaystyle w\models A}$). V opačném případě o formuli ${\displaystyle A}$ říkáme, že je nesplnitelná.

O formuli ${\displaystyle B}$ říkáme, že je sémantickým důsledkem formule ${\displaystyle A}$, značeno ${\displaystyle A\models B}$ pokud pro každé ${\displaystyle w}$, takové že ${\displaystyle w\models B}$ platí i ${\displaystyle w\models A}$. Tato relace je částečným uspořádáním výrokových formulí.

Odvozování

Pro výrokovou logiku můžeme definovat jednoduchý deduktivní dokazovací systém sestávající ze tří schémat pro tvorbu axiomů a jediného odvozovacího pravidla.

Hilbertův axiomatický systém

Pro jakékoliv formule ${\displaystyle A,B,C}$ jsou následující formule axiomy:

1. ${\displaystyle A\Rightarrow (B\Rightarrow A)}$
2. ${\displaystyle (A\Rightarrow (B\Rightarrow C))\Rightarrow ((A\Rightarrow B)\Rightarrow (A\Rightarrow C))}$
3. ${\displaystyle (\neg B\Rightarrow \neg A)\Rightarrow (A\Rightarrow B)}$

Odvozovací pravidlo

Stačí nám jediné pravidlo, tzv. Modus ponens: Jestliže ${\displaystyle A}$ platí a ${\displaystyle A\Rightarrow B}$ platí, pak ${\displaystyle B}$ platí.

Důkaz

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

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

Úplnost

Výroková logika je úplná a konzistentní v tom smyslu, že dokazatelné formule jsou právě ty, které jsou pravdivé v každém ohodnocení.

Externí odkazy

• Obrázky, zvuky či videa k tématu výroková logika na Wikimedia Commons
• Volně stažitelná skripta z předmětu Výroková a predikátová logika na MFF UK od Petra Štěpánka