Výroková logika (VL)

Výroková logika označuje formální odvozovací systém, který analyzuje způsob skladby jednoduchých výroků do výroků složených pomocí logických spojek. Strukturu elementárních výroků již dále nezkoumá.

Výrok

Výrok je tvrzení, o němž má smysl prohlásit, zda je pravdivé či nepravdivé.

  • Jednoduchý výrok – je dále nedělitelný na další výroky a může nabývat pouze dvou hodnot (1- pravda) / (0-nepravda)

Př. Bill Gates byl nejbohatší člověk na světě.

  • Složený výrok – když se spojí jednoduché výroky dohromady pomocí logických spojek vznikne složený výrok.Pravdivostní hodnota složeného výroku jednoznačně určena jen pravdivostními hodnotami jeho složeka povahou spojení těchto složek. Výroková logika je proto algebrou pravdivostních hodnot.

Př: Dnes jsem udělal zkoušku a šel na pivo.     ... spojka a rozděluje 2 atomické výroky

Definice formálního jazyka výrokové logiky

Formální jazyk je zadán abecedou (množina výchozích symbolů) a gramatikou (množina pravidel, která udávají, jak vytvářet „Dobře utvořené formule“ - DUF)

Abeceda jazyka výrokové logiky je množina následujících symbolů:

– Výrokové symboly:  p, q, r, ...   

– Pomocné symboly (závorky): (, ), [, ], {, }

– Symboly logických spojek (funktorů):  ¬, ∨, ∧, ⇒, ⇔

  • ¬p                    - je negace výroku p, jestliže bude výrok "prší" pak jeho negací získáme "neprší"
  • 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 / p É q     - je implikace, čteme „jestliže výrok p, pak (z toho vyplývá) výrok q“
  • p ⇔q / p ≡ q    - je ekvivalence, čteme „výrok p právě tehdy když výrok q“

Jazyk výrokové logiky je množina všech dobře utvořených formulí výrokové logiky. 

 

Pravdivostní ohodnocení (valuace) výrokových symbolů je zobrazení v, které ke každému výrokovému symbolu přiřazuje pravdivostní hodnotu, tj. hodnotu z množiny {1,0}. 

Pravdivostní funkce formule výrokové logiky je funkce w, která ke každému pravdivostnímu ohodnocení výrokových symbolů přiřazuje pravdivostní hodnotu celé formule. Tato hodnota je určena takto:

(1)    Pravdivostní hodnota elementární formule je rovna pravdivostní hodnotě výrokového symbolu, tj.

                    w(p)v = v(p) pro všechny výrokové proměnné p

(2)    Jsou-li dány pravdivostní funkce formulí A, B, pak pravdivostní funkce formulí ¬A, A ∧ B, A ∨ B, A ⇒ B, A ⇔ B jsou dány následující tabulkou pravdivostních hodnot:

A

B

¬A

A ∧ B

A Ú B

A É B

A ≡ B

1

1

0

1

1

1

1

1

0

0

0

1

0

0

0

1

1

0

1

1

0

0

0

1

0

0

1

1

Splnitelnost formulí, tautologie, kontradikce a logické vyplývání

Problém rozhodování, zdali určitá formule A vyplývá z množiny formulí (předpokladů) , se nazývá problém dedukce a je jedním ze základních problémů logiky. Dříve, než si přesně řekneme, co to je logický důsledek, ukážeme si, co to je model množiny formulí.

  • Model formule A: ohodnocení výrokově logických proměnných p, q, r … (valuace) takové, že formule A je v tomto ohodnocení v pravdivá w(A)v = 1.
  • Formule je splnitelná, má-li alespoň jeden model
  • Formule je nesplnitelná (kontradikce), nemá-li žádný model
  • Formule je tautologie, je-li každé ohodnocení jejím modelem.
  • Množina formulí {A1,…,An} je splnitelná, existuje-li ohodnocení, které je modelem každé formule A1,...,An.
  • Formule Z logicky vyplývá z množiny {A1,…,An}, platí-li pro všechny modely množiny formulí {A1,…,An}, že formule Z je v nich splněna (pokud jsou jedničky u všech předpokladů musí být i v závěru).

Příklad u důkazu pomocí tabulkové metody.

Převod z přirozeného jazyka do symbolického jazyka výrokové logiky:

V dané větě označíme jednotlivé elementární výroky různými výrokovými symboly a místo spojek přirozeného jazyka použijeme odpovídající výrokové symboly pro spojky.

Příklad:

Je doma nebo šel na pivo.

Je-li doma, pak nás očekává.

⇒ Jestliže nás neočekává, pak šel na pivo.


Výroky můžeme převést do následujícího tvaru, kde symbol d = "je doma", p = "šel na pivo", o = "očekává nás" 

(d ∨ p), (d É o) ⇒(¬o É p)

 

Nyní můžeme zjistit zda-li je množina formulí splnitelná. Důkaz, že formule je tautologie, nebo že závěr Z logicky vyplývá z předpokladů můžeme dokázat pomocí následujících důkazových metod.

Důkazové metody VL

Důkazové metody se dělí do 2 základních skupin:

  1. Sémantické metody - pracují přímo s pravdivostními hodnotami formule  - patří sem: tabulková metoda, metoda sporem
  2. Syntaktické metody - pracuje pouze se syntaktickou skladbou formule – s tvarem podformulí, umístěním logických spojek a s kvantifikátory  - patří sem: přirozená dedukce, metoda ekvivalentích úprav, sémantické tablo, rezoluční metoda

Důkaz pomocí pravdivostní tabulky

Je sémantickou přímou důkazovou metodou, která je vhodná pouze pro formule s malým počtem výrokových proměnných, protože má 2n řádků. 

Postup je takový, že do prvních sloupců vypíšeme n výrokových symbolů se kterými formule pracuje (d, p, o) a do dalších rozepíšeme dílčí formule. Poté vyplníme všechny kombinace ohodnocení symbolů (první 3 sloupce) na jejichž základě dopočteme i zbytek jedniček a nul podle předchozí tabulky. 

Příklad tabulkové metody:

d

p

o

d Ú p

d É o

¬o É p

1

1

1

1

1

1

1

1

0

1

0

1

1

0

1

1

1

1

1

0

0

1

0

0

0

1

1

1

1

1

0

1

0

1

1

1

0

0

1

0

1

1

0

0

0

0

1

0

⇒Množina formulí d Ú p, d É o je splnitelná, protože má alespoň jeden model. Model tvoří ohodnocení, kde jsou obě formule pravdivé. Konkrétně mají formule 4 následující modely: (1, 1, 1) (1,0,1) (0,1,1) (0,1,0) označené tučně.

⇒Závěr  ¬o É p je pravdivý ve všech čtyřech modelech předpokladů (všude kde jsou jedničky v předpokladech jsou i jedničky v závěrečné formuli), z čehož vyplývá že formule je splnitelná, úsudek je platný, a že závěr logicky vyplývá z předpokladů.

 

Pozn.: Formule by byla tautologií - kdyby formule ¬o É p vyšla vždy 1. Kontradikcí kdyby vyšla pokaždé 0. Závěr by byl neplatný kdyby se našel jediný model předpokladu pro který by byla formule ¬o É p nepravdivá.

Důkaz sporem

K efektivnějším sémantickým metodám patří důkaz sporem, který se řadí k nepřímým důkazovým metodám. Důkaz sporem je metoda používaná zejména pro ověřování tautologií ve tvaru implikace. U důkazu sporem předpodkládáme, že úsudek není správný. Vychází se z toho že implikace je nepravdivá pouze v jednom případě - když je antecedent (část před implikací) pravdivý a konsekvent (formule za amplikací) nepravdivý  1 É 0. Prověříme tedy všechny valuace, pro něž je konsekvent nepravdivý a jestliže alespoň pro jednu z těchto valuací nastane případ, že by byl antecedent pravdivý, nemůže být daná formule tautologie a naopak, jestliže pro žádnou z těchto valuací není antecedent pravdivý, je uvažovaná formule tautologie.

Příklad metody sporem:

... u jedné z premis jsme došli ke sporu (protože d É u mělo ohodnoceno 1 ale vyšlo to 0) ⇒ formule je splnitelná , ale není to tautologie (museli bychom ke sporu dojít u všech antecedentů), pokud bychom nedošli k žádnému sporu jednalo by se o kontradikci 

 

Důkaz pomocí ekvivalentních úprav

Pro rozhodnutí zda-li je formule tautologie můžeme použít metodu ekvivalentních úprav s využitím těchto logických zákonů.

Příklad ekvivalentních úprav:

 ... formule je tautologie

 

Důkaz pomocí sémantického tabla

Při tomto důkazu je důležité vědět jak vypadá formule v konjunktivní a disjunktivní formě. 

  • Disjunktivní tablo - strom jehož listy jsou konjunkce literálů, používá se pro důkaz kontradikce
  • Konjunktivní tablo - strom jehož listy jsou disjunkce literálů, používá se pro důkaz tautologie

Postup je následující:

  1. Formuli upravíme tak, aby negace byla všude „uvnitř“, tj. u jednotlivých proměnných.
  2. Tam, kde je nějaká podformule ve tvaru implikace nebo ekvivalence, převedeme na disjunkci / konjunkci s využitím logických zákonů.
  3. Konstruujeme tablo uplatňováním distributivního zákona. 

⇒Pro důkaz, že formule F je tautologie:

Zkonstruujeme konjunktivní tablo. Pokud se všechny větve uzavřely, tj. každý list sémantického stromu tvoří elementární disjunkce s dvojicí literálů s opačným znaménkem (např. p, ¬p, což znamená p ∨ ¬p), je formule F tautologie.

⇒Důkaz, že formule F je kontradikce:

Zkonstruujeme disjunktivní tablo. Pokud se všechny větve uzavřely, tj. každý list sémantického stromu tvoří elementární konjunkce s dvojicí literálů s opačným znaménkem (např. p, ¬p, což znamená p ∧ ¬p), je formule F kontradikce.

Příklad konjunktivního tabla - přímé dokazování tautologie:

Formuli máme v DNF a ověřujeme jestli je tautologie. Větvení znamená konjunkci, čárka znamená disjunkci. Postupujeme zleva a jakmile narazíme na konjunkci, rozvětvíme. Levý konjunkt do levé větve + zbytek formule oddělený čárkami, zatímco pravý konjunkt do pravé větve + zbytek. Větvíme tak dlouho dokud nerozepíšeme všechny konjunkce nebo dokud neuzavřeme všechny větve. Uzavření znamená, že jsme narazili na opačný pár literálů (např. p, ¬p). V příkladu jsme uzavřeli všechny větve a formule je tudíž tautologie.

U disjunktivního tabla postupujeme obdobně s tím rozdílem, že větvení znamená disjunkce a čárka konjunkce.

Důkaz pomocí rezoluční metody

Viz přechozí kapitola.

 

 Čerpáno ze skript Logika pro Informatiky (Doc. RNDr. Marie Duží)