Logika

Než se vydáme do Athén, jedna věta, jakou můžeš slyšet ve zprávách. Politik prohlásí:

„Platí presumpce neviny. Pro běžného občana je posvátná a nedotknutelná. U politika ale platí presumpce viny.“

Je to jeden výrok? Které části jsou tvrzení, o jejichž pravdě lze rozhodnout, a které jen hodnotí nebo něco přikazují?

Samo slovo logika pochází z řeckého logos – slovo, řeč, rozum, počet. Logika tedy začala jako pravidla pro řeč. To je první stopa k tomu, proč do jejího příběhu později vstoupí lingvisté.

Celá kapitola v jedné větě: logika začala jako pravidla správné řeči, stoici z ní udělali počty s pravdou, Boole z pravdy udělal číslo 1 a ze lži 0 a Shannon z toho postavil obvody. U každého zastavení uvidíš, kde tě ta myšlenka dnes potká v kódu.

„Naopak,“ pokračoval Tydlitýt, „kdyby to tak bylo, mohlo by to být; a kdyby to tak bylo, bylo by to; ale protože to tak není, není to. To je logika.“— Lewis Carroll, Za zrcadlem, 1871

Jak poznat, že závěr opravdu plyne, a ne že jen zní přesvědčivě?

V Athénách 5. a 4. století př. n. l. se o všem rozhodovalo řečí: v lidovém shromáždění, u soudu, kde se člověk hájil sám, a na agoře. Sofisté za peníze učili, jak spor vyhrát, ne jak mít pravdu. Platón jim to vyčítal a jeho žák Aristotelés si položil přesnější otázku: existují pravidla, podle kterých se dá mechanicky poznat, že argument je správný, bez ohledu na to, kdo ho říká a jak hezky?

Aristotelés (384–322 př. n. l.) odpověď sepsal ve spisech, které jeho žáci později nazvali Organon – „nástroj“. Logika pro něj nebyla věda o světě, ale nástroj pro všechny ostatní vědy. Přesně tak ji dnes používá programátor.

Aristotelův objev: správnost úsudku nezávisí na tom, o čem mluvíme, ale na jeho tvaru. Proto začal místo slov psát písmena – je to vůbec první použití proměnných v dějinách logiky, o dvě tisíciletí dřív než v algebře.

// první premisa: pravidlo
  if (clovek(x)) smrtelny(x) = true;
  // druhá premisa: data
  clovek("Sokrates") == true;
  // závěr
  smrtelny("Sokrates") == true;

Létající kočka: pravda není totéž co správnost

Všechny kočky umějí létat. Mourek je kočka. ⟹ Mourek umí létat. Premisa i závěr jsou nesmysl, a přesto je úsudek logicky správný: tvar je stejný jako u Sokrata. Kdyby premisy platily, závěr by platit musel. Logika nehlídá, zda jsou vstupní slova pravdivá, ale zda funguje vnitřní logická struktura.

Garbage in, garbage out: správný program se špatnými daty dá špatný výsledek. A naopak, správný výsledek ještě neznamená, že je program správně:

Zákony, které Aristotelés považoval za nejpevnější

V Metafyzice (kniha IV) Aristotelés tvrdí, že nejjistější ze všech principů je zákon sporu: nic nemůže zároveň být a nebýt v témž smyslu. Hned vedle formuluje zákon vyloučeného třetího: o každé věci je nutné buď něco tvrdit, nebo to popírat, mezi tím nic není. Tyto dva zákony jsou kořenem dvouhodnotové logiky – a tedy i typu boolean, který má přesně dvě hodnoty a nic mezi nimi.

Zajímavost: sám Aristotelés v knize O vyjadřování váhal, zda zákon vyloučeného třetího platí i pro budoucnost. Je výrok „Zítra bude námořní bitva“ už dnes pravdivý, nebo nepravdivý?

„Prší.“ – „Prší?“ – „Ať prší!“ Tři věty o témž. O které z nich má smysl se ptát, zda platí?

Aristotelés pracoval s pojmy (lidé, smrtelní). Stoikové ve 3. století př. n. l., hlavně Chrysippos ze Soloi (asi 279–206 př. n. l.), začali pracovat s celými větami. Zavedli pojem axióma, který odpovídá našemu „výroku“, a definovali ho právě pravdou: výrok je to, co je buď pravdivé, nebo nepravdivé.

Stoici také zkoumali, jak pravdivost složené věty závisí na pravdivosti jejích částí: „a“, „nebo“, „jestliže… pak“. O implikaci se přeli tak urputně, že básník Kallimachos prý napsal, že i vrány na střechách krákají o tom, která implikace je správná. Vyhrála definice Filóna z Megary: věta „jestliže A, pak B“ je nepravdivá jedině tehdy, když A platí a B neplatí. Je to přesně třetí sloupec dnešní tabulky, o 2200 let starší než tabulka sama.

Výrok o Kallimachových vránách známe jen z pozdějších autorů (Sextus Empiricus). Stoické logické spisy se nedochovaly; o Chrysippovi víme hlavně z Diógena Laertia (Životy filozofů, kniha VII).

Chrysippos navíc sepsal pět základních odvozovacích pravidel. Nejslavnější z nich dnes známe jako modus ponens: Jestliže A, pak B. Platí A. ⟹ Platí B.

Paradox lháře: když výrok nemá pravdivostní hodnotu

Už ve 4. století př. n. l. připisovali Eubúlidovi z Mílétu paradox „Toto tvrzení je nepravdivé.“ Je-li pravdivé, je nepravdivé; je-li nepravdivé, je pravdivé. Chrysippos o něm prý napsal několik spisů. Paradox ukazuje hranici definice výroku: ne každá oznamovací věta je výrok.

function lhar() {
    if (zastavi(lhar)) while (true) {}  // mám doběhnout? tak nedoběhnu
    else return;                        // nemám doběhnout? tak doběhnu
  }

Dají se zákony správného uvažování zapsat jako algebra?

Gottfried Wilhelm Leibniz (1646–1716) snil o characteristica universalis, jazyku, ve kterém by se pojmy zapisovaly znaky, a o calculus ratiocinator, počtu pro usuzování. Spory by se pak nevedly hádkou: dva učenci by si sedli a řekli Calculemus! – „počítejme!“. Leibniz také podrobně popsal dvojkovou soustavu (1703) se dvěma číslicemi 0 a 1. Logiku a dvojkovou soustavu ale ještě nespojil. To udělal až o půldruhého století později samouk z Lincolnu.

George Boole (1815–1864) byl syn obuvníka z Lincolnu, matematiku se naučil sám a od 16 let učil, aby uživil rodinu. Bez univerzitního titulu se stal profesorem v irském Corku. Roku 1847 vydal útlou knihu The Mathematical Analysis of Logic a roku 1854 hlavní dílo An Investigation of the Laws of Thought – „Zkoumání zákonů myšlení“. Odtud letopočet 1854 u této kapitoly.

Boole neměl za cíl postavit počítač. Chtěl popsat, jak lidé myslí, stejně přesně, jako Newton popsal pohyb. Zjistil, že úsudky se dají zapisovat a upravovat jako rovnice.

George Boole 1815–1864, Lincoln – Cork

1. 1815Narodil se v Lincolnu v rodině obuvníka.
2. 1831V 16 letech začíná učit, aby uživil rodinu.
3. 1847The Mathematical Analysis of Logic.
4. 1849Profesor matematiky na Queen's College v Corku.
5. 1854An Investigation of the Laws of Thought.
6. 1864Umírá na zápal plic ve 49 letech.

Souběžně s Boolem pracoval Augustus De Morgan (1806–1871), po kterém nesou jméno zákony ¬(A ∧ B) ⇔ (¬A ∨ ¬B) a ¬(A ∨ B) ⇔ (¬A ∧ ¬B) – ty, které programátor používá pokaždé, když přepisuje !(a && b) na !a || !b.

Boole neuvažoval o výrocích, ale o třídách věcí. Písmeno x pro něj znamenalo třeba „bílé věci“, y „ovce“. Součin xy pak byl průnik: „bílé ovce“. 1 byla celá úvaha, všechno, o čem mluvíme (universe), 0 prázdná třída, nic.

Pak si všiml zvláštnosti. Bílé bílé věci jsou pořád jen bílé věci, takže platí xx = x, tedy

x² = x.

V obyčejné algebře má tahle rovnice jen dvě řešení: x = 0 a x = 1. Boole z toho udělal závěr, který změnil dějiny: algebra myšlení je obyčejná algebra omezená na čísla 0 a 1. Ve druhé knize pak 1 vyložil jako „vždy“, tedy pravdu, a 0 jako „nikdy“, tedy nepravdu.

Z té samé rovnice Boole odvodil i Aristotelův zákon sporu: x − x² = 0, neboli x(1 − x) = 0. Slovy: nic nemůže zároveň mít vlastnost x a nemít ji (1 − x). Nejstarší zákon logiky vypadl z algebry jako vedlejší produkt.

Když je pravda 1 a nepravda 0, dají se tabulky pro „ne“, „a“, „nebo“ a „jestliže“ spočítat, místo abychom se je učili nazpaměť?

Boole tabulky nekreslil, počítal rovnicemi. Tabulka jako metoda přišla až o několik desetiletí později.

• Gottlob Frege (1879, Begriffsschrift) přesně popsal, kdy je implikace pravdivá, výčtem všech čtyř případů – zatím slovy.
• Charles S. Peirce nakreslil kolem roku 1893 v nepublikovaném rukopise matici, která je dnešní pravdivostní tabulkou implikace. Objevila se až v jeho pozůstalosti.
• Ludwig Wittgenstein (Tractatus, 1921) a nezávisle Emil Post (1921) tabulky zveřejnili a ukázali, že s nimi lze o každé výrokové formuli rozhodnout, zda je tautologií. Wittgenstein vlastně definoval tautologii jako formuli, která má ve výsledném sloupci samé pravdy.

Frege se přirozeného jazyka bál: považoval ho za nepřesný a víceznačný, a proto si vytvořil jazyk vlastní. Jak to s logikou a jazykem bylo dál, vypráví samostatná stránka Jazyk a logika.

Jakmile je pravda 1 a nepravda 0, můžeme se na spojky dívat jako na početní operace: dosadíme dvě čísla 0 nebo 1 a vyjde zase 0 nebo 1. Úkol zní: najdi vzorec, který dává 1 přesně v těch řádcích, kde je složený výrok pravdivý. Krok za krokem:

1. Negace. Hledáme operaci, která z 1 udělá 0 a z 0 udělá 1. Stačí odečíst od jedničky: 1 − 1 = 0 a 1 − 0 = 1. Tedy ¬p = 1 − p.
2. Konjunkce „p a q“. Má platit, jen když platí obě části. Zkusme součin: 1 · 1 = 1, 1 · 0 = 0, 0 · 1 = 0, 0 · 0 = 0. Jediná nula vynuluje celý součin, stejně jako jediná nepravdivá část shodí celé „a“. Tedy p ∧ q = p · q.
3. Disjunkce „p nebo q“. Má platit, když platí aspoň jedna část. První nápad je součet p + q. Funguje ve třech řádcích, ale pro p = q = 1 dá 2, a dvojka v našem světě neexistuje. Opravíme to: společnou část jednou odečteme, p + q − pq. (Boole sám psal jen x + y a myslel jím vylučovací „nebo“; nevylučovací verzi prosadil hlavně W. S. Jevons.)
4. Implikace „jestliže p, pak q“. Podle Filóna je nepravdivá v jediném případě: p = 1 a q = 0. Ten „zakázaný“ případ zapíšeme součinem p(1 − q), který je 1 jen tehdy, když p = 1 a zároveň q = 0. Implikace platí, když zakázaný případ nenastal, takže ho znegujeme: p ⇒ q = 1 − p(1 − q).
5. Ekvivalence „p právě tehdy, když q“. Má platit, když mají p a q stejnou hodnotu. Rozdíl p − q je 0 při shodě a +1 nebo −1 při neshodě. Umocněním zmizí znaménko: (p − q)² je 0 při shodě a 1 při neshodě. Zbývá výsledek obrátit: p ⇔ q = 1 − (p − q)².

Vyšla přesně známá tabulka pravdivostních hodnot, tentokrát ne naučená, ale spočítaná. Tabulka je tedy algoritmus: projdi všech 2ⁿ kombinací a podívej se. Je to první rozhodovací procedura v logice – a hrubá síla (brute force) v čisté podobě.

Booleova algebra byla osmdesát let kuriozitou pro filozofy. Dá se z ní postavit stroj?

Roku 1937 napsal jednadvacetiletý Claude Shannon na MIT diplomovou práci A Symbolic Analysis of Relay and Switching Circuits. Ukázal, že sériově zapojené spínače se chovají jako ∧, paralelně zapojené jako ∨. Zapnuto = 1, vypnuto = 0. Od té chvíle se dá jakýkoli logický úsudek postavit z drátů. Každý procesor je hromada Booleových rovnic.