Výroková logika

Kapitoly: Výroková logika, Pravdivost formulí, Příklady na výrokovou logiku

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í.