Logika a důkazy: pravidla, podle kterých se v AI uvažuje

Výroky, spojky a pravdivostní tabulky, past s implikací, kvantifikátory a druhy důkazů — a proč XOR zastavil první neuronové sítě.

14 minut Matěj Žalmánek 2026-10-15

Série Základy AI Díl 7 z 83

1. Mapa umělé inteligence: co je co a jak to do sebe zapadá
2. Stručná historie umělé inteligence: od Turinga po jazykové modely
3. Data, model, trénink, inference: základní pojmy na jednom příkladu
4. Jak číst matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relace: stavebnice, ze které se skládají definice v AI
6. Funkce a zobrazení: proč je každý model v AI funkce
7. Logika a důkazy: pravidla, podle kterých se v AI uvažuje
8. Grafy a stromy: struktura, na které stojí hledání i neuronové sítě
9. Lineární algebra pro strojové učení: vektory, matice a proč AI hlavně násobí
10. Derivace, gradient a řetízkové pravidlo: jak model zjistí, kterým směrem se učit
11. Gradientní sestup: jak se model učí
12. Co je pravděpodobnost: od hodu kostkou ke Kolmogorovovým axiomům
13. Podmíněná pravděpodobnost a Bayesova věta: jak změnit odhad, když se dozvíte něco nového
14. Náhodná veličina a distribuční funkce: jedna funkce, která o rozdělení řekne všechno
15. Funkce hustoty a pravděpodobnostní funkce: proč má spojitá veličina v bodě pravděpodobnost nula
16. Střední hodnota, rozptyl a kovariance: kde rozdělení leží, jak je široké a co s čím souvisí
17. Přehled pravděpodobnostních rozdělení: Bernoulli, binomické, Poisson, rovnoměrné, normální a exponenciální
18. Zákon velkých čísel a centrální limitní věta: proč se průměry chovají tak předvídatelně
19. Statistika a odhady parametrů: maximální věrohodnost, MAP a intervaly spolehlivosti
20. Teorie informace: entropie, křížová entropie a KL divergence — odkud se berou ztrátové funkce
21. Prohledávání stavového prostoru: BFS, DFS, UCS a A* s animacemi
22. Hry a protivník: minimax, alfa-beta ořezávání a Monte Carlo tree search
23. Splňování omezujících podmínek: backtracking, propagace omezení a AC-3 na sudoku a mapě krajů
24. Logika a znalostní systémy: dopředné a zpětné řetězení, rezoluce a expertní systémy
25. Plánování: STRIPS, svět kostek, heuristiky z relaxace a plánování v AI agentech
26. Lokální hledání a simulované žíhání: obchodní cestující přes krajská města
27. Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet
28. Evoluční strategie a genetické programování: od pravidla jedné pětiny po Keplerův zákon
29. Optimalizace mravenčí kolonií: jak feromonová stopa najde krátkou cestu
30. Optimalizace hejnem částic: setrvačnost, vlastní zkušenost a zkušenost hejna
31. Neuroevoluce: evoluce vah i tvaru neuronových sítí a algoritmus NEAT
32. Fuzzy množiny a funkce příslušnosti: jak zapsat „trochu teplo“
33. Fuzzy logika a pravděpodobnost: proč „trochu teplo“ neznamená „pravděpodobně teplo“
34. Fuzzy logika: t-normy, implikace a pravidla KDYŽ–PAK
35. Fuzzy řízení: Mamdani a Sugeno od ventilátoru po kyvadlo na vozíku
36. Fuzzy shlukování: algoritmus fuzzy c-means a body mezi shluky
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidla, která se učí z dat
38. Markovovy řetězce: přechodová matice, stacionární rozdělení a PageRank
39. Skryté Markovovy modely: Viterbiho algoritmus a nepoctivé kasino
40. Bayesovské sítě: proč je tráva mokrá a co z toho plyne pro postřikovač
41. Kalmanův filtr: jak z nepřesných měření odhadnout, kde auto je a jak rychle jede
42. Druhy strojového učení: s učitelem, bez učitele, s částečným učitelem a další
43. Přeučení a regularizace: proč model, který zná data nazpaměť, selže
44. Vyhodnocení modelu: křížová validace, F1 a křivka ROC
45. Shlukování a snížení dimenze: k-means, PCA a t-SNE
46. Klasifikace a regrese: dvě úlohy učení s učitelem
47. Lineární regrese: nejmenší čtverce geometricky i maticově
48. Polynomiální a nelineární regrese: jak přímku ohnout
49. Logistická regrese: sigmoida, šance a křížová entropie
50. Vícetřídní klasifikace a softmax: od dvou tříd k mnoha
51. Naivní Bayesův klasifikátor: spamový filtr, který funguje lépe, než by měl
52. Ztrátové funkce: co přesně model minimalizuje
53. Rozhodovací stromy a k nejbližších sousedů: modely bez vzorců
54. Ansámbly: náhodný les a gradient boosting
55. SVM a jádrový trik: nejširší hranice a jak ji ohnout
56. Signál a vzorkování: proč platí Nyquistův teorém
57. Fourierova transformace: rozklad signálu na frekvence
58. Filtry a konvoluce: vyhlazení, hrany a odstranění šumu
59. Zvuk a řeč: spektrogram, melová škála a MFCC
60. Obraz jako signál: pixely, barvy, konvoluce a hrany
61. Perceptron a umělý neuron: nejjednodušší neuronová síť a co neumí
62. Neuronová síť od nuly: zpětné šíření chyby krok za krokem
63. Aktivace, inicializace a normalizace: drobnosti, na kterých hluboká síť stojí
64. Konvoluční sítě: jak síť poznává obrázky
65. Rekurentní sítě: paměť pro posloupnosti a mizející gradient
66. LSTM a GRU: brány, které rozhodují, co si síť zapamatuje
67. Autoenkodéry: síť, která se učí data stlačit a zase rozbalit
68. Embeddingy a word2vec: jak se slovo stane vektorem
69. Mechanismus pozornosti: jak se model naučí, kam se dívat
70. Transformery a velké jazykové modely: architektura krok za krokem
71. Tokenizace: jak se text rozseká na kousky pro model
72. Předtrénování a škálování: proč větší model a víc dat funguje
73. Doladění a RLHF: jak se z doplňovače textu stane asistent
74. Prompty, kontext a RAG: jak modelu dát správné informace
75. Variační autoenkodéry (VAE): nové obrázky ze spojitého latentního prostoru
76. Generativní adversariální sítě (GAN): padělatel proti detektivovi
77. Difúzní modely: jak se z čistého šumu stane obrázek
78. Markovovy rozhodovací procesy: stavy, akce, odměny a Bellmanovy rovnice
79. Q-learning a DQN: učení hodnoty akcí od tabulky po neuronovou síť
80. Policy gradient a PPO: učení přímo strategie
81. Jak funguje AI agent: jazykový model ve smyčce s nástroji
82. Programování s AI agenty: zadání, testy a kontrola
83. Vyhodnocení a bezpečnost AI systémů: jak měřit a jak hlídat

Celá osnova série 83 z 83 témat hotovo

Každá definice v téhle sérii je logická věta a každé „proto“ za ní je kousek důkazu. Logika je pravidla hry: říká, kdy je tvrzení pravdivé a jak z pravdivých tvrzení správně odvodit další. A v umělé inteligenci je dvakrát — jako jazyk, ve kterém se o algoritmech mluví, i jako samostatný obor, ze kterého vyrostly první „myslící“ programy.

Symboly ¬, ∧, ∨, ⇒, ∀ a ∃ jsme poprvé potkali v dílu o matematickém zápisu. Tady zjistíme, jak přesně fungují, kde se v nich nejčastěji chybuje a jak se z nich skládá důkaz.

1. Výroky a pravdivostní hodnoty

Definice — výrok

Výrok je tvrzení (oznamovací věta nebo matematický zápis), o kterém má smysl říct, zda je pravdivé, nebo nepravdivé, a platí právě jedna z těch dvou možností. Je to výchozí pojem, který logika dál nerozkládá. Pravdivostní hodnota výroku A je číslo

v(A) ∈ {0, 1},   v(A) = 1 ⇔ A je pravdivý,   v(A) = 0 ⇔ A je nepravdivý.

Nechť P₁, …, P_n (také P, Q, R, …) jsou výrokové proměnné — jednoduché výroky, jejichž hodnotu necháváme otevřenou. Složené výroky (formule) jsou právě ty, které vzniknou konečným použitím pravidel:

1. každá výroková proměnná je složený výrok;
2. je-li A složený výrok, je i ¬A složený výrok;
3. jsou-li A, B složené výroky, jsou i (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) a (A ⊕ B) složené výroky.

Ohodnocení proměnných je funkce v : {P₁, …, P_n} → {0, 1}. Hodnota složeného výroku při ohodnocení v je jednoznačně určena hodnotami jeho částí podle pravdivostních tabulek logických spojek ¬, ∧, ∨, ⇒, ⇔, ⊕ (další kapitola) — pravdivost složeného výroku tedy závisí jen na pravdivosti jeho částí.

2. Spojky a pravdivostní tabulky

Jak spojka funguje, se nejlépe ukáže pravdivostní tabulkou: pro každou kombinaci hodnot P a Q jeden řádek. Dvě proměnné mají 2 · 2 = 4 kombinace, n proměnných 2ⁿ.

• Negace ¬P obrátí hodnotu.
• Konjunkce P ∧ Q („a“) platí, jen když platí obě části.
• Disjunkce P ∨ Q („nebo“) platí, když platí aspoň jedna — i obě.
• Implikace P ⇒ Q („jestliže, pak“) neplatí jen v jediném případě: P platí a Q ne.
• Ekvivalence P ⇔ Q platí, když mají obě části stejnou hodnotu.
• Vylučovací nebo P ⊕ Q (XOR) platí, když platí právě jedna z nich.

Definice — spojka jako funkce

Nechť n ∈ ℕ, n ≥ 1, a {0, 1}ⁿ = {(p₁, …, p_n) : p_i ∈ {0, 1} pro i = 1, …, n} je množina všech n-tic nul a jedniček. n-místná logická spojka (booleovská funkce) je funkce

f : {0, 1}ⁿ → {0, 1}.

Pravdivostní tabulka je celý její předpis: pro každý z 2ⁿ vstupů jedna hodnota. Spojka ¬ je jednomístná, spojky ∧, ∨, ⇒, ⇔, ⊕ jsou dvojmístné (n = 2, 4 vstupy).

Každý ze 4 řádků může dopadnout dvojím způsobem, takže dvojmístných spojek je přesně 2⁴ = 16 — a obecně n-místných 2²ⁿ (počet funkcí z 2ⁿprvkové množiny do dvouprvkové, viz díl Funkce a zobrazení). Šest z tabulky výše jsou jen ty, které mají vlastní jméno.

S hodnotami 0 a 1 se dá počítat jako s čísly: pro všechna p, q ∈ {0, 1} platí

1. ¬p = 1 − p,
2. p ∧ q = p · q,
3. p ∨ q = p + q − pq,
4. p ⇒ q = 1 − p + pq,
5. p ⇔ q = 1 − p − q + 2pq,
6. p ⊕ q = p + q − 2pq.

Každou rovnost lze ověřit dosazením všech čtyř dvojic (p, q) a porovnáním s tabulkou.

Aritmetický zápis „nebo“ stojí za rozebrání, protože vysvětluje, proč je „nebo“ v logice včetně obou:

p ∨ q = p + q − p · q

p

když platí P, přispěje jedničkou — stačí k pravdivosti celku

q

totéž za Q; „nebo“ je spokojené s kteroukoliv částí

p · q

je 1 jen tehdy, když platí obě; bez odečtení by vyšlo 1 + 1 = 2, což není pravdivostní hodnota — odečítáme případ započítaný dvakrát

3. Implikace: nejčastější past

Definice — obrácená implikace a obměna

Nechť P, Q jsou výroky. K implikaci P ⇒ Q definujeme

1. obrácenou implikaci Q ⇒ P,
2. obměnu (kontrapozici) ¬Q ⇒ ¬P.

Věta. Nechť P, Q jsou výrokové proměnné. Pak (P ⇒ Q) ≡ (¬Q ⇒ ¬P), ale neplatí (P ⇒ Q) ≡ (Q ⇒ P): implikace má při každém ohodnocení stejnou hodnotu jako její obměna, ale existuje ohodnocení, při kterém se liší od obrácené implikace (logickou ekvivalenci ≡ definujeme v kapitole o tautologiích).

Tabulka to ukáže bez debaty: sloupec implikace a obměny je stejný, obrácená implikace se liší ve dvou řádcích.

Druhá past je první řádek s P = 0: když předpoklad neplatí, je implikace pravdivá, ať je Q cokoliv. „Jestli je 7 sudé, jsem papež“ je pravdivý výrok. Zní to divně, ale dává to smysl — implikace slibuje jen něco o situaci, kdy P platí, a ten slib se nedá porušit, když P neplatí.

Obě pasti zmizí, když implikaci přepíšeme pomocí „ne“ a „nebo“:

P ⇒ Q ≡ ¬P ∨ Q

P ⇒ Q

slib „když P, tak Q“ — chceme vědět, kdy je dodržen

¬P

když předpoklad neplatí, slib se netýká dané situace, a je tedy dodržen sám od sebe — odtud řádky s P = 0

Q

když předpoklad platí, slib je dodržen jen tehdy, když opravdu nastane Q

Věta — implikace je ekvivalentní s obměnou (důkaz bez tabulky)

Věta. Nechť P, Q jsou výrokové proměnné. Pak (¬Q ⇒ ¬P) ≡ (P ⇒ Q) a (Q ⇒ P) ≢ (P ⇒ Q).

Důkaz. Podle přepisu A ⇒ B ≡ ¬A ∨ B (rozbor výše):

¬Q ⇒ ¬P ≡ ¬(¬Q) ∨ ¬P ≡ Q ∨ ¬P ≡ ¬P ∨ Q ≡ P ⇒ Q.

Použili jsme jen přepis implikace (dvakrát), dvojí negaci ¬¬Q ≡ Q a to, že u „nebo“ nezáleží na pořadí. Obrácená implikace Q ⇒ P ≡ ¬Q ∨ P je jiný výraz — pro P = 0, Q = 1 dává 0, zatímco P ⇒ Q dává 1. ∎

4. Tautologie a ekvivalentní výroky

Definice — tautologie, kontradikce, ekvivalence

Nechť A, B jsou složené výroky ve výrokových proměnných P₁, …, P_n a pro ohodnocení v : {P₁, …, P_n} → {0, 1} značí v(A) ∈ {0, 1} hodnotu výroku A při tomto ohodnocení.

1. A je tautologie (např. P ∨ ¬P), právě když v(A) = 1 pro každé ohodnocení v;
2. A je kontradikce (např. P ∧ ¬P), právě když v(A) = 0 pro každé ohodnocení v;
3. A a B jsou logicky ekvivalentní, píšeme A ≡ B, právě když v(A) = v(B) pro každé ohodnocení v, tj. právě když A ⇔ B je tautologie.

Ekvivalentní výroky tedy mají v pravdivostní tabulce stejný sloupec. Píšeme A ≢ B, když ekvivalentní nejsou.

Tak se dají ověřit De Morganovy zákony z dílu o množinách: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. Sloupce jsou stejné:

Ověření tabulkou je jednoduchý algoritmus — projdi všechna ohodnocení a hledej to, které výrok shodí:

from itertools import product

def je_tautologie(vyrok, n):
    for hodnoty in product([True, False], repeat=n):   # 2**n ohodnocení
        if not vyrok(*hodnoty):
            return False                               # našli jsme protipříklad
    return True

je_tautologie(lambda p, q: (not (p and q)) == ((not p) or (not q)), 2)   # True: De Morgan

Ověřit tautologii tabulkou je spolehlivé, ale pro n proměnných to znamená 2ⁿ řádků. Pro 20 proměnných je to 2²⁰ = 1 048 576 řádků, na což počítači stačí zlomek sekundy. Pro 300 proměnných je to 2³⁰⁰ ≈ 2,04 · 10⁹⁰ řádků — víc, než je atomů ve vesmíru (asi 10⁸⁰). I při miliardě řádků za sekundu by to trvalo 2 · 10⁸¹ s, zatímco vesmír je starý asi 4 · 10¹⁷ s. Otázka, jestli se dá výrok vůbec splnit (problém SAT), je jedním z nejslavnějších těžkých problémů informatiky.

5. Proč XOR zastavil první neuronové sítě

Nakresleme si čtyři kombinace P a Q jako body v rovině a obarvěme je podle výsledku. U „a“ i „nebo“ jde zelené body oddělit od oranžových jednou přímkou. U XOR to nejde — zelené body leží na úhlopříčce a oranžové na té druhé:

P ∧ Q

P ∨ Q

P ⊕ Q

Perceptron, nejjednodušší neuronová síť, umí rozdělit body jen přímkou. V roce 1969 Minsky a Papert ukázali, že proto nezvládne ani tak jednoduchou funkci jako XOR, a zájem o neuronové sítě na roky opadl. Řešení je přidat vrstvu: XOR se dá složit z jednodušších funkcí, (P ∨ Q) ∧ ¬(P ∧ Q), a dvouvrstvá síť to umí. Tady začíná příběh hlubokého učení.

Definice — perceptron se dvěma vstupy

Nechť w₁, w₂ ∈ ℝ jsou váhy a b ∈ ℝ práh (bias). Perceptron se dvěma vstupy s parametry w₁, w₂, b je funkce f_{w1, w2, b} : {0, 1}² → {0, 1},

f_{w1, w2, b}(p, q) = 1, právě když w₁p + w₂q + b > 0; jinak f_{w1, w2, b}(p, q) = 0.

Pro (w₁, w₂) ≠ (0, 0) je množina {(p, q) ∈ ℝ² : w₁p + w₂q + b = 0} přímka — ta rozděluje rovinu na část „1“ a část „0“.

Funkce g : {0, 1}² → {0, 1} je lineárně oddělitelná, právě když ji umí spočítat nějaký perceptron:

∃w₁, w₂, b ∈ ℝ ∀(p, q) ∈ {0, 1}² : g(p, q) = f_{w1, w2, b}(p, q).

y = [ w₁p + w₂q + b > 0 ]

y

výstup 0 nebo 1 — perceptron má dát stejnou hodnotu jako logická spojka

w₁p + w₂q

vážený součet vstupů: váha říká, jak moc daný vstup „hlasuje“ pro jedničku

b

práh posouvá přímku — určuje, kolik hlasů je potřeba; bez něj by přímka musela vést počátkem

> 0

rozhodnutí ano/ne: na které straně přímky bod leží

Věta — XOR není lineárně oddělitelný (důkaz sporem)

Věta. Nechť XOR : {0, 1}² → {0, 1}, XOR(p, q) = p ⊕ q. Pak XOR není lineárně oddělitelná, tj. neexistují w₁, w₂, b ∈ ℝ, pro která by f_{w1, w2, b} = XOR.

Důkaz. Předpokládejme pro spor, že perceptron s w₁, w₂, b počítá XOR. Čtyři řádky tabulky dávají čtyři nerovnosti:

(0, 0) ↦ 0: b ≤ 0;   (1, 0) ↦ 1: w₁ + b > 0;   (0, 1) ↦ 1: w₂ + b > 0;   (1, 1) ↦ 0: w₁ + w₂ + b ≤ 0.

Sečtením prostředních dvou: w₁ + w₂ + 2b > 0, tedy w₁ + w₂ + b > −b ≥ 0. To odporuje čtvrté nerovnosti. Spor — takový perceptron neexistuje. ∎

Druhá vrstva spor obejde. Skrytý neuron h₁ počítá OR (váhy 1, 1, práh −0,5), h₂ počítá AND (váhy 1, 1, práh −1,5) a výstup y = [h₁ − h₂ − 0,5 > 0] říká „OR, ale ne AND“. Každý ze tří neuronů je perceptron; barvy v záhlaví tabulky odpovídají členům jeho vzorce výše:

6. Predikáty a kvantifikátory

Definice — predikát a kvantifikátory

Nechť M je neprázdná množina (obor proměnné). Predikát (výroková forma) na M je předpis P, který každému x ∈ M přiřadí výrok P(x) — výrok s proměnnou, který se po dosazení prvku M stane výrokem (např. na M = ℤ: P(x) = „x je sudé“). Ekvivalentně je to funkce P : M → {0, 1}, x ↦ v(P(x)).

1. Obecný kvantifikátor: výrok ∀x ∈ M : P(x) je pravdivý, právě když P(x) je pravdivý pro každé x ∈ M, tj. právě když {x ∈ M : P(x)} = M.
2. Existenční kvantifikátor: výrok ∃x ∈ M : P(x) je pravdivý, právě když P(x) je pravdivý pro aspoň jedno x ∈ M, tj. právě když {x ∈ M : P(x)} ≠ ∅.

Na pořadí různých kvantifikátorů záleží: nechť M, N jsou neprázdné množiny a P(x, y) predikát na M × N. Pak vždy platí

(∃y ∈ N ∀x ∈ M : P(x, y)) ⇒ (∀x ∈ M ∃y ∈ N : P(x, y)),

ale opačná implikace obecně neplatí (protipříklad v rámečku níže).

Definice v AI jsou plné kvantifikátorů. Přípustná heuristika z dílu o prohledávání je „∀n : h(n) ≤ h*(n)“ — a vyvrátit ji stačí jediným stavem, kde odhad přestřelí.

Proč stačí jeden stav, říká pravidlo pro negaci kvantifikátoru — De Morganův zákon pro „všechna“ a „existuje“:

¬∀x : P(x)  ≡  ∃x : ¬P(x)

¬

negace „projde“ dovnitř — z popření celého tvrzení se stane popření vlastnosti u jednoho prvku

∀x / ∃x

při průchodu negace se kvantifikátor otočí: „ne u všech“ znamená „aspoň u jednoho ne“ — to je ten protipříklad

P(x)

vlastnost sama zůstává stejná; mění se jen to, kolika prvků se týká

Na konečné množině jsou kvantifikátory jen dlouhé spojky: pro M = {1, 2, 3} je ∀x : P(x) totéž co P(1) ∧ P(2) ∧ P(3) a ∃x : P(x) totéž co P(1) ∨ P(2) ∨ P(3). Pravidlo nahoře je pak obyčejný De Morganův zákon, jen pro tři členy místo dvou.

7. Co je důkaz

Definice — důkaz a modus ponens

Nechť Γ je množina výroků — předpokladů (axiomy, dříve dokázané věty, předpoklady tvrzení) — a T je výrok. Důkaz tvrzení T z Γ je konečná posloupnost výroků V₁, V₂, …, V_k (k ≥ 1) taková, že

1. V_k = T (posloupnost končí dokazovaným tvrzením);
2. pro každé i = 1, …, k platí V_i ∈ Γ, nebo V_i vznikne z některých výroků V_j s j < i použitím odvozovacího pravidla.

Základní odvozovací pravidlo je modus ponens: pro libovolné výroky A, B platí

z A a A ⇒ B se smí odvodit B.

Pravidlo je správné (z pravdivých výroků odvodí jen pravdivý výrok), protože (A ∧ (A ⇒ B)) ⇒ B je tautologie.

Příklad — důkaz jako posloupnost řádků

Předpoklady: P („prší“), P ⇒ Q („když prší, je mokro“), Q ⇒ R („když je mokro, klouže to“). Tvrzení: R.

1. P — předpoklad
2. P ⇒ Q — předpoklad
3. Q — modus ponens z 1 a 2
4. Q ⇒ R — předpoklad
5. R — modus ponens z 3 a 4 ∎

Každý řádek má zdůvodnění, které se dá ověřit mechanicky: buď je v seznamu předpokladů, nebo odkazuje na dva dřívější řádky tvaru A a A ⇒ B.

8. Druhy důkazů

Přímý důkaz

Z předpokladů krok za krokem dojdeme k tvrzení. Tvrzení: součet dvou sudých čísel je sudý (celé číslo m je sudé, právě když ∃a ∈ ℤ : m = 2a). Důkaz: sudá čísla jsou 2a a 2b pro celá a, b. Jejich součet je 2a + 2b = 2(a + b), tedy dvojnásobek celého čísla — sudé číslo. ∎

Důkaz obměnou a sporem

Místo P ⇒ Q dokážeme ekvivalentní ¬Q ⇒ ¬P — nebo předpokládáme, že tvrzení neplatí, a dojdeme k nesmyslu. Tvrzení: prvočísel je nekonečně mnoho. Důkaz sporem (Eukleidés): kdyby jich bylo konečně mnoho, p₁, …, p_k, vezmeme N = p₁ · … · p_k + 1. Žádné p_i nedělí N — vždy zbude 1. N tedy má prvočíselného dělitele, který v seznamu chybí. Spor. ∎

Příklad — Eukleidovo číslo s konkrétními prvočísly

Pro seznam 2, 3, 5, 7: N = 2 · 3 · 5 · 7 + 1 = 211. Dělení 2, 3, 5 i 7 dá zbytek 1 a 211 je samo prvočíslo, které v seznamu nebylo.

Pro seznam 2, 3, 5, 7, 11, 13: N = 30 030 + 1 = 30 031 = 59 · 509. Tady N prvočíslo není — ale jeho prvočíselní dělitelé 59 a 509 v seznamu chybějí. Důkaz netvrdí, že N je prvočíslo, jen že má nového prvočíselného dělitele.

Protipříklad

Tvrzení „pro všechna“ se vyvrací jediným příkladem. „Každé liché číslo větší než 1 je prvočíslo“ platí pro 3, 5 a 7 — a padá na 9 = 3 · 3. Tři příklady nic nedokazují, jeden protipříklad vyvrací.

Matematická indukce

Definice — princip matematické indukce

Nechť ℕ = {1, 2, 3, …} a P(n) je predikát na ℕ. Jestliže platí

1. P(1)   (základ) a
2. ∀n ∈ ℕ : P(n) ⇒ P(n + 1)   (indukční krok),

pak

∀n ∈ ℕ : P(n).

Princip je jednou ze základních vlastností přirozených čísel (v Peanově aritmetice axiom). Stejně funguje se základem v libovolném n₀ ∈ ℤ: z P(n₀) a ∀n ≥ n₀ : P(n) ⇒ P(n + 1) plyne P(n) pro všechna celá n ≥ n₀.

[ P(1) ∧ ∀n ≥ 1 : (P(n) ⇒ P(n + 1)) ] ⇒ ∀n ∈ ℕ : P(n)

P(1)

základ — první kostka opravdu spadne; bez něj by krok neměl odkud začít

∀n : P(n) ⇒ P(n + 1)

indukční krok — jedna implikace, dokázaná pro obecné n, nahradí nekonečně mnoho jednotlivých ověření; je to „řetěz modus ponens“ 1 → 2 → 3 → …

∀n : P(n)

to, co chceme: tvrzení pro všechna přirozená čísla najednou

Tvrzení: pro všechna n ∈ ℕ je 1 + 2 + … + n = n(n + 1)/2. Barvy odpovídají částem principu indukce výše. Základ P(1): pro n = 1 je vlevo 1 a vpravo 1 · 2/2 = 1. Krok P(n) ⇒ P(n + 1): platí-li vzorec pro n, pak 1 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = n(n + 1) + 2(n + 1)/2 = (n + 1)(n + 2)/2, což je vzorec pro n + 1. Podle principu indukce tedy ∀n ∈ ℕ : P(n). ∎ Stejný výsledek ukazuje i obrázek: dvě schodiště z teček dají dohromady obdélník n × (n + 1).

Pro n = 100 dává vzorec 100 · 101/2 = 5050 — výsledek, který podle legendy spočítal malý Gauss tak, že sečetl dvojice 1 + 100, 2 + 99, …, 50 + 51: padesát dvojic po 101.

Definice — invariant cyklu

Nechť cyklus v programu proběhne k ≥ 0krát a pro j = 0, 1, …, k je I(j) tvrzení o hodnotách proměnných programu po j průchodech (I(0) mluví o stavu před prvním průchodem). I je invariant cyklu, právě když

1. I(0) platí (invariant platí před prvním průchodem) a
2. ∀j ∈ {0, 1, …, k − 1} : I(j) ⇒ I(j + 1) (každý průchod ho zachová).

Indukcí podle počtu průchodů j (se základem j = 0) pak I(j) platí pro všechna j = 0, …, k, speciálně I(k) po skončení cyklu — z něj vyčteme výsledek.

def soucet(n):
    s = 0
    for i in range(1, n + 1):
        s = s + i
        # invariant: s == 1 + 2 + … + i == i * (i + 1) // 2
    return s          # po posledním průchodu i == n: s == n * (n + 1) // 2

Indukcí se v informatice dokazuje správnost algoritmů: „po k krocích cyklu platí…“. Takhle se dokazuje třeba to, že UCS rozbaluje stavy v neklesajícím pořadí ceny — a proto najde nejlevnější cestu.

9. Logika v umělé inteligenci

• Symbolická AI — první systémy umělé inteligence byly logické: znalosti zapsané jako pravidla „když–pak“ a odvozování modus ponens. Na tom stály expertní systémy osmdesátých let.
• SAT solvery řeší úlohu „dá se tenhle výrok splnit?“ pro miliony proměnných — plánují, ověřují hardware a hledají chyby v programech.
• Ověřování AI — logikou se dokazují vlastnosti systémů: že autopilot nikdy nedá dva protichůdné povely, nebo že neuronová síť nezmění rozhodnutí kvůli neviditelnému šumu.
• Jazykové modely a důkazy — dnešní modely umějí psát důkazy, a ty se pak kontrolují formálními nástroji, které každý krok ověří mechanicky.

Odvozování v expertním systému je modus ponens opakovaný, dokud přibývají nová fakta — dopředné řetězení. Pravidlo je dvojice (předpoklady, závěr), tedy implikace A₁ ∧ … ∧ A_k ⇒ B:

def dopredne_retezeni(fakta, pravidla):
    fakta = set(fakta)
    zmena = True
    while zmena:                                    # dokud něco přibylo
        zmena = False
        for predpoklady, zaver in pravidla:
            if zaver not in fakta and all(a in fakta for a in predpoklady):
                fakta.add(zaver)                    # modus ponens
                zmena = True
    return fakta

pravidla = [({"prší"}, "mokro"), ({"mokro"}, "klouže"), ({"klouže", "spěchám"}, "pozor")]
dopredne_retezeni({"prší", "spěchám"}, pravidla)    # {prší, spěchám, mokro, klouže, pozor}

Cyklus skončí vždy: každý průchod se změnou přidá aspoň jeden závěr a závěrů je jen tolik, kolik je pravidel. Na příkladu přibudou všechna tři nová fakta už v prvním průchodu, protože pravidla jsou seřazená tak, jak na sebe navazují; druhý průchod jen ověří, že nic nepřibylo. V opačném pořadí pravidel by průchody se změnou byly tři.

10. Shrnutí

• Výrok je pravda, nebo nepravda; spojky ¬ ∧ ∨ ⇒ ⇔ ⊕ jsou přesně definované pravdivostní tabulkou.
• Implikace je ekvivalentní s obměnou, ne s obrácenou implikací — a s nepravdivým předpokladem je vždy pravdivá.
• XOR nejde rozdělit jednou přímkou, a proto potřebuje neuronová síť víc vrstev.
• Na pořadí kvantifikátorů záleží; tvrzení „pro všechna“ vyvrací jeden protipříklad.
• Důkaz je řetěz ověřitelných kroků: přímý, obměnou, sporem nebo indukcí.

Máte na to jiný názor? Napište na support@coden-app.com.