Výroková logika

Zobrazit kapitoly článku
  1. Výroková logika
  2. Pravdivost formulí
  3. 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 \wedge q\) je konjunkce výroků, čteme „výrok p a (zároveň) výrok q“
  • \(p \vee 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 \Leftrightarrow 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 \wedge B)\), \((A \vee B)\), \((A \Rightarrow B)\), \((A \Leftrightarrow 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 \wedge B\): (V centru Opavy svítí slunce nebo prší) a zároveň (je vidět duha).
  • \(A \vee 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 \Leftrightarrow 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í.