Dedukce

Výroková logika by jako model lidského vnímání světa a myšlení o něm neměla valnou cenu, kdyby se v ní nedalo vyjádřit, co z čeho vyplývá. Jde o schopnost, která se v případě skutečného lidského myšlení nazývá schopnost dedukce.

Dedukce ve výrokové logice

Logický důsledek

Problém rozhodování, zdali určitá formula A vyplývá z množiny formulí U, se nazývá problém dedukce a je jedním ze základních problémů logiky. Ve výrokové logice hovoříme o formuli A vyplývající z množiny formulí U jako (tauto)logickém důsledku U. Množina formulí U je v tomto pojetí speciální množinou předpokladů (speciálních axiomů), na níž je postavena určitá teorie.

Tvrzení, že formule A je logickým důsledkem dané množiny formulí U obvykle vyjadřujeme U |= A.

Formule množiny předpokladů U nemusí být nutně tautologiemi. Je-li však U nesplnitelná množina, pak nemá žádný model, a proto jejím logickým důsledkem je libovolná formule (tj. lze získat formuli A i její negaci A). Nesplnitelná množina předpokladů tedy vede ke sporným důsledkům.

Logickým důsledkem prázdné množiny formulí může být pouze tautologie (označuje se |=A).

Teorie a její axiomy z hlediska sémantiky

Pro matematické teorie je typické, že vycházejí vždy z nějaké množiny základních tvrzení - axiomů a dále, že platná tvrzení teorie jsou důsledky této zvolené množiny axiomů.

Teorii lze definovat takto:

1. je dána množina U výchozích formulí - speciálních axiomů (předpokladů) teorie,

2. množina T(U) se nazývá teorií vybudovanou na U, je-li každý prvek množiny T(U) formulí, která je logickým důsledkem U, platí-li tedy T(U) = {A / U |= A}.

Je zřejmé, že uvažujeme-li o dedukci, tedy o vyplývání výroků z jiných výroků, je třeba vzít v úvahu to, aby naše závěry byly platné v rámci daného způsobu interpretace.

Předpoklady a závěr dedukce

Problém dedukce bývá zpravidla formulován tak, že z množiny hypotéz {H₁, H_2, ..., H_n} vyplývá závěr Z. Množina hypotéz U = {H₁, H_2, ..., H_n} tedy tvoří speciální axiomy teorie a Z je jejím tautologickým důsledkem ( {H₁, H_2, ..., H_n} |= Z ).

Je-li  U |= Z, hovoříme o platnosti formule Z ve všech modelech množiny formulí U.

Příklad: (aplikace principu dedukce)

Zadání: Brown, James a Smith jsou podezřelí z daňového podvodu. Svědčili pod přísahou takto:

Brown: Jones je vinen a Smith je nevinen.

Jones: Je-li vinen Brown, pak je vinen i Smith.

Smith: Já jsem nevinen, ale nejméně jeden ze zbývajících je vinen.

Řešení:

Označme postupně b, j, s výroky. Výpovědi všech tří podezřelých budou nyní vypadat takto:

Brown: j s.

Jones: b s.

Smith: s ( b j).

 

Vinen je zřejmě Jones.

TABULKOVOU metodu lze nahradit REZOLUČNÍ metodou.

Pravidla přirozené dedukce

Již od dob klasické logiky jsou známa některá pravidla, podle nichž probíhá deduktivní uvažování. Jestliže platí

A₁₁, ..., A_1n |= B₁,

...  ...        ...

A_k1, ..., A_kn |= B_k, pak platí C₁, ..., C_n |= D.

Sémanticky se tato implikace vyjadřuje ve tvaru zlomku tak, že nad čarou jsou uvedeny výchozí dedukce, pod ní dedukce odvozená z těchto výchozích dedukcí.

Pravidla přirozené dedukce se dělí do dvou skupin. První z nich zahrnuje pravidla strukturální (pravidlo oslabení, o permutaci, o redukci), druhou skupinu odvozovacích pravidel tvoří pravidla operační (pravidlo dodání konjunkce, odnětí konjunkce, dodání implikace, odnětí implikace, dodání disjunkce sukcedentu, dodání negace, pravidlo dvojí negace).