Výroková logika

Výroková (matematická) logika je vyjadřovací prostředek matematiky, s nímž se můžeme setkat v různé terminologii a ve všemožných matematických větách.

K čemu je logika

Logika je věda, která se zabývá usuzováním, pravdivostí, dokazatelností a vyvratitelností. Přitom všem jde v logice pouze o formu sdělení, nezajímá nás, co konkrétně je sdělováno, stejně jako nás nezajímají různé psychologické interpretace a podobné věci.

Pokud máme například větu „číslo 2 je sudé a zároveň je liché“, tak můžeme usoudit, celá věta není pravdivá, protože čísla 2 není liché. To jsou věci, které obecně řeší logika.

Výrok

Základem výrokové logiky je pochopitelně výrok. Výrokem je každá oznamovací věta, u které můžeme určit její pravdivostní hodnotu. Příklady jednoduchých výroků:

• Bill Gates byl nejbohatší člověk na světě.
• Přirozené číslo pět je liché číslo.
• HTML je programovací jazyk.
• Dva plus tři je šest.

Toto všechno jsou výroky. Ať už jsou pravdivé (první dva) nebo jsou nepravdivé (poslední dva). Výrokem není například tázací věta nebo věta, u které nemůžeme jednoznačně určit její pravdivostní hodnotu. Opět příklad:

• Bude i příští rok Bill Gates nejbohatší člověk na světě?
• Zelená barva je nejkrásnější.

První věta nemůže být výrok, protože je to tázací věta, u druhé věty zase neurčíme, jestli je to pravdivý výrok nebo nepravdivý. Taková věta se pak nazývá hypotéza (domněnka).

Klasická matematická logika si neumí příliš dobře poradit s vágními větami typu „Honza je vysoký“ nebo „Britney Spears je dobrá zpěvačka“. Tyto výroky se lépe řeší například ve fuzzy logice, která je pro vágnost uzpůsobena.

Atomický výrok

V první kapitole jsme měli příklad výroku „číslo 2 je sudé a zároveň je liché“. Takový výrok můžeme nazvat složený, protože ve skutečnosti spojuje dva kratší výroky: „číslo 2 je sudé“ a „číslo 2 je liché“. Tyto dva výroky jsou pak spojeny výrokovou spojkou „a“ nebo také „a zároveň“.

Atomický výrok je tak výrok, který už dále nemůžeme dělit, jedná se v jistém smyslu o to nejjednodušší konstatování. Předchozí příklady výroků byly ve skutečnosti atomické výroky:

• Bill Gates byl nejbohatší člověk na světě.
• Přirozené číslo pět je liché číslo.
• HTML je programovací jazyk.
• Dva plus tři je šest.

Atomické výroky budeme dále značit malými písmeny abecedy, klasicky p, q, r, … a budeme jim říkat výrokové symboly.

Výrokové spojky

Matematická logika běžně operuje s určitou sadou výrokových spojek. Mezi základní patří čtyři binární spojky:

• p ∧ q je konjunkce výroků, čteme „výrok p a (zároveň) výrok q“
• p ∨ q je disjunkce výroků, čteme „výrok p nebo výrok q“
• $p \Rightarrow q$ je implikace, čteme „jestliže výrok p, pak výrok q“
• p ⇔ q je ekvivalence, čteme „výrok p právě tehdy když výrok q“

Konkrétní příklady výrokových spojek:

• V centru Opavy prší a zároveň svítí slunce. (konjunkce)
• V centru Opavy prší nebo svítí slunce. (disjunkce)
• Apple je nejhustější firma a Steve Jobs je největší týpek. (konjunkce)
• Jestliže si vezmete projímadlo, pak se brzy pose… (implikace)
• Jestliže je číslo x dělitelné čtyřmi, pak je i dělitelné dvěma. (implikace)
• Agáta je hezká a zároveň chytrá. (konjunkce)
• Zpěvačky jsou úspěšné právě tehdy, když jsou hezké. (ekvivalence)
• Nebude-li pršet, nezmokneme. (implikace)
• Pokud umí Leoš Mareš zpívat, pak jsem čínský bůh srandy. (implikace)

Známe ještě jednu běžnou výrokovou spojku: negaci. Negace se značí buď čárkou $p^\prime$ nebo pomocí symbolu $\neg p$.

Formule

Pomocí výrokových symbolů (atomických výroků) a výrokových spojek můžeme složit složitější výrok, kterému budeme říkat formule. Všechny příklady v předchozím seznamu vět byly ve skutečnost formule, protože jsme měli dvě atomické formule, například „V centru Opavy prší“ a „svítí slunce“, a spojili jsme je pomocí výrokových spojek. V prvním případě jsme je spojili spojkou „a zároveň“ a dostali jsme formuli „V centru Opavy prší a zároveň svítí slunce“, ve druhém případě jsme použili „nebo“ a dostali jsme formuli „V centru Opavy prší nebo svítí slunce“.

Formálně nadefinujeme formuli takto:

• Každý výrokový symbol (atomický výrok) je formule (přesněji můžeme říci, že se jedná o atomickou formuli).
• Pokud jsou A i B formule, pak i $\neg A$, (A ∧ B), (A ∨ B), $(A \Rightarrow B)$, (A ⇔ B) jsou formule.

Definice dává smysl: v prvním bodě říkáme, že každý atomický výrok je zároveň formule. Takže máme-li dva atomické výroky, například „V centru Opavy prší“ a „svítí slunce“, pak máme zároveň i dvě formule. V tuto chvíli můžeme aplikovat druhý bod a sestavit složitější formuli třeba takto:

• V centru Opavy prší a zároveň svítí slunce.
• V centru Opavy prší nebo svítí slunce.
• Jestliže v centru Opavy svítí slunce, pak prší.
• Slunce v centru Opavy svítí právě tehdy když prší.

Formule samozřejmě nemusí být nutně pravdivé. V tuto chvíli jsme dostali další sadu formulí, takže můžeme složit ještě složitější formule. Pokud si označíme A=„V centru Opavy svítí slunce nebo prší.“ (už víme, že to je formule) a B=„je vidět duha“ (předpokládejme, že zase v centru Opavy, ať to nemusíme dokola opakovat), pak můžeme vytvořit další formule. Závorky ve větách jen vyznačují, ke kterým částem se spojka vztahuje.

• A ∧ B: (V centru Opavy svítí slunce nebo prší) a zároveň (je vidět duha).
• A ∨ B: (V centru Opavy svítí slunce nebo prší) nebo (je vidět duha).
• $A \Rightarrow B$: (Jestliže v centru Opavy svítí slunce nebo prší), pak (je vidět duha).
• A ⇔ B: (V centru Opavy svítí slunce nebo prší) právě tehdy, když (je vidět duha).

Toto jsou vše formule. Takže opět můžeme vzít jednu z těchto formulí a připojit k ní nějakou další formuli. Můžeme tak vytvořit třeba patvar „Jestliže v centru Opavy svítí slunce nebo prší nebo je vidět duha, pak svítí slunce nebo prší právě tehdy, když je vidět duha.“

V další části budeme zkoumat pravdivost formulí.