Výroková 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.

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ů:

• Venku prší.
• 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 zítra pršet?
• 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.

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:

• Venku prší.
• 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.

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 ⇒ 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:

• Prší a zároveň svítí slunce. (konjunkce)
• 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' nebo pomocí symbolu ¬p.

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 „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 „Prší a zároveň svítí slunce“, ve druhém případě jsme použili „nebo“ a dostali jsme formuli „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 ¬A, (A ∧ B), (A ∨ B), (A ⇒ 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 „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:

• Prší a zároveň svítí slunce.
• Prší nebo svítí slunce.
• Svítí slunce nebo prší.
• Jestliže svítí slunce, pak prší.
• Slunce 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 = „Svítí slunce nebo prší.“ (už víme, že to je formule) a B = „je vidět duha“, 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: (Svítí slunce nebo prší) a zároveň je vidět duha.
• A ∨ B: Svítí slunce nebo prší nebo je vidět duha.
• A ⇒ B: Jestliže svítí slunce nebo prší, pak je vidět duha.
• A ⇔ B: 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 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í.