Logika a dôkazy: pravidlá, podľa ktorých sa v AI uvažuje

Výroky, spojky a pravdivostné tabuľky, pasca s implikáciou, kvantifikátory a druhy dôkazov — a prečo XOR zastavil prvé neurónové siete.

14 minút Matěj Žalmánek 2026-10-15

Séria Základy AI Diel 7 z 52

1. Mapa umelej inteligencie: čo je čo a ako to do seba zapadá
2. Stručná história umelej inteligencie: od Turinga po jazykové modely
3. Dáta, model, tréning, inferencia: základné pojmy na jednom príklade
4. Ako čítať matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relácie: stavebnica, z ktorej sa skladajú definície v AI
6. Funkcie a zobrazenia: prečo je každý model v AI funkcia
7. Logika a dôkazy: pravidlá, podľa ktorých sa v AI uvažuje
8. Grafy a stromy: štruktúra, na ktorej stojí hľadanie aj neurónové siete
9. Lineárna algebra pre strojové učenie: vektory, matice a prečo AI hlavne násobí
10. Derivácie, gradient a reťazové pravidlo: ako model zistí, ktorým smerom sa učiť
11. Gradientný zostup: ako sa model učí
12. Čo je pravdepodobnosť: od hodu kockou ku Kolmogorovovým axiómam
13. Podmienená pravdepodobnosť a Bayesova veta: ako zmeniť odhad, keď sa dozviete niečo nové
14. Náhodná premenná a distribučná funkcia: jedna funkcia, ktorá o rozdelení povie všetko
15. Funkcia hustoty a pravdepodobnostná funkcia: prečo má spojitá premenná v bode pravdepodobnosť nula
16. Stredná hodnota, rozptyl a kovariancia: kde rozdelenie leží, aké je široké a čo s čím súvisí
17. Prehľad pravdepodobnostných rozdelení: Bernoulliho, binomické, Poissonovo, rovnomerné, normálne a exponenciálne
18. Zákon veľkých čísel a centrálna limitná veta: prečo sa priemery správajú tak predvídateľne
19. Štatistika a odhady parametrov: maximálna vierohodnosť, MAP a intervaly spoľahlivosti
20. Teória informácie: entropia, krížová entropia a KL divergencia — odkiaľ sa berú stratové funkcie
21. Prehľadávanie stavového priestoru: BFS, DFS, UCS a A* s animáciami
22. Hry a protivník: minimax, alfa-beta orezávanie a Monte Carlo tree search
23. Splňovanie obmedzujúcich podmienok: backtracking, propagácia obmedzení a AC-3 na sudoku a mape krajov
24. Logika a znalostné systémy: dopredné a spätné reťazenie, rezolúcia a expertné systémy
25. Plánovanie: STRIPS, svet kociek, heuristiky z relaxácie a plánovanie v AI agentoch
26. Lokálne hľadanie a simulované žíhanie: obchodný cestujúci cez krajské mestá
27. Genetické algoritmy: populácia, kríženie, mutácia a výber na batohu na výlet
28. Evolučné stratégie a genetické programovanie: od pravidla jednej pätiny po Keplerov zákon
29. Optimalizácia mravčou kolóniou: ako feromónová stopa nájde krátku cestu
30. Optimalizácia rojom častíc: zotrvačnosť, vlastná skúsenosť a skúsenosť roja
31. Neuroevolúcia: evolúcia váh aj tvaru neurónových sietí a algoritmus NEAT
32. Fuzzy množiny a funkcie príslušnosti: ako zapísať „trochu teplo“
33. Fuzzy logika a pravdepodobnosť: prečo „trochu teplo“ neznamená „pravdepodobne teplo“
34. Fuzzy logika: t-normy, implikácie a pravidlá AK–TAK
35. Fuzzy riadenie: Mamdani a Sugeno od ventilátora po kyvadlo na vozíku
36. Fuzzy zhlukovanie: algoritmus fuzzy c-means a body medzi zhlukmi
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidlá, ktoré sa učia z dát
38. Markovove reťazce: prechodová matica, stacionárne rozdelenie a PageRank
39. Skryté Markovove modely: Viterbiho algoritmus a nepoctivé kasíno
40. Bayesovské siete: prečo je tráva mokrá a čo z toho vyplýva pre postrekovač
41. Kalmanov filter: ako z nepresných meraní odhadnúť, kde auto je a ako rýchlo ide
42. Druhy strojového učenia: s učiteľom, bez učiteľa, s čiastočným učiteľom a ďalšie
43. Prompty, kontext a RAG: ako modelu dať správne informácie
44. Variačné autoenkodéry (VAE): nové obrázky zo spojitého latentného priestoru
45. Generatívne adversariálne siete (GAN): falšovateľ proti detektívovi
46. Difúzne modely: ako sa z čistého šumu stane obrázok
47. Markovove rozhodovacie procesy: stavy, akcie, odmeny a Bellmanove rovnice
48. Q-learning a DQN: učenie hodnoty akcií od tabuľky po neurónovú sieť
49. Policy gradient a PPO: učenie priamo stratégie
50. Ako funguje AI agent: jazykový model v slučke s nástrojmi
51. Programovanie s AI agentmi: zadanie, testy a kontrola
52. Vyhodnocovanie a bezpečnosť AI systémov: ako merať a ako strážiť

Celá osnova série Hotovo: 52 z 83 tém

Každá definícia v tejto sérii je logická veta a každé „preto“ za ňou je kúsok dôkazu. Logika sú pravidlá hry: hovorí, kedy je tvrdenie pravdivé a ako z pravdivých tvrdení správne odvodiť ďalšie. A v umelej inteligencii je dvakrát — ako jazyk, ktorým sa o algoritmoch hovorí, aj ako samostatný odbor, z ktorého vyrástli prvé „mysliace“ programy.

Symboly ¬, ∧, ∨, ⇒, ∀ a ∃ sme prvýkrát stretli v diele o matematickom zápise. Tu zistíme, ako presne fungujú, kde sa v nich najčastejšie chybuje a ako sa z nich skladá dôkaz.

1. Výroky a pravdivostné hodnoty

Definícia — výrok

Výrok je tvrdenie (oznamovacia veta alebo matematický zápis), o ktorom má zmysel povedať, či je pravdivé, alebo nepravdivé, a platí práve jedna z tých dvoch možností. Je to východiskový pojem, ktorý logika ďalej nerozkladá. 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 (aj P, Q, R, …) sú výrokové premenné — jednoduché výroky, ktorých hodnotu nechávame otvorenú. Zložené výroky (formuly) sú práve tie, ktoré vzniknú konečným použitím pravidiel:

1. každá výroková premenná je zložený výrok;
2. ak je A zložený výrok, je aj ¬A zložený výrok;
3. ak sú A, B zložené výroky, sú aj (A ∧ B), (A ∨ B), (A ⇒ B), (A ⇔ B) a (A ⊕ B) zložené výroky.

Ohodnotenie premenných je funkcia v : {P₁, …, P_n} → {0, 1}. Hodnota zloženého výroku pri ohodnotení v je jednoznačne určená hodnotami jeho častí podľa pravdivostných tabuliek logických spojok ¬, ∧, ∨, ⇒, ⇔, ⊕ (ďalšia kapitola) — pravdivosť zloženého výroku teda závisí len od pravdivosti jeho častí.

2. Spojky a pravdivostné tabuľky

Ako spojka funguje, sa najlepšie ukáže pravdivostnou tabuľkou: pre každú kombináciu hodnôt P a Q jeden riadok. Dve premenné majú 2 · 2 = 4 kombinácie, n premenných 2ⁿ.

• Negácia ¬P obráti hodnotu.
• Konjunkcia P ∧ Q („a“) platí, len keď platia obe časti.
• Disjunkcia P ∨ Q („alebo“) platí, keď platí aspoň jedna — aj obe.
• Implikácia P ⇒ Q („ak, tak“) neplatí len v jedinom prípade: P platí a Q nie.
• Ekvivalencia P ⇔ Q platí, keď majú obe časti rovnakú hodnotu.
• Vylučovacie alebo P ⊕ Q (XOR) platí, keď platí práve jedna z nich.

Definícia — spojka ako funkcia

Nech n ∈ ℕ, n ≥ 1, a {0, 1}ⁿ = {(p₁, …, p_n) : p_i ∈ {0, 1} pre i = 1, …, n} je množina všetkých n-tíc núl a jednotiek. n-miestna logická spojka (booleovská funkcia) je funkcia

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

Pravdivostná tabuľka je celý jej predpis: pre každý z 2ⁿ vstupov jedna hodnota. Spojka ¬ je jednomiestna, spojky ∧, ∨, ⇒, ⇔, ⊕ sú dvojmiestne (n = 2, 4 vstupy).

Každý zo 4 riadkov môže dopadnúť dvoma spôsobmi, takže dvojmiestnych spojok je presne 2⁴ = 16 — a všeobecne n-miestnych 2²ⁿ (počet funkcií z 2ⁿ-prvkovej množiny do dvojprvkovej, pozri diel Funkcie a zobrazenia). Šesť z tabuľky vyššie sú len tie, ktoré majú vlastné meno.

S hodnotami 0 a 1 sa dá počítať ako s číslami: pre všetky 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ždú rovnosť možno overiť dosadením všetkých štyroch dvojíc (p, q) a porovnaním s tabuľkou.

Aritmetický zápis „alebo“ stojí za rozobratie, pretože vysvetľuje, prečo je „alebo“ v logike vrátane oboch:

p ∨ q = p + q − p · q

p

keď platí P, prispeje jednotkou — stačí na pravdivosť celku

q

to isté za Q; „alebo“ je spokojné s ktoroukoľvek časťou

p · q

je 1 len vtedy, keď platia obe; bez odčítania by vyšlo 1 + 1 = 2, čo nie je pravdivostná hodnota — odčítame prípad započítaný dvakrát

3. Implikácia: najčastejšia pasca

Definícia — obrátená implikácia a obmena

Nech P, Q sú výroky. K implikácii P ⇒ Q definujeme

1. obrátenú implikáciu Q ⇒ P,
2. obmenu (kontrapozíciu) ¬Q ⇒ ¬P.

Veta. Nech P, Q sú výrokové premenné. Potom (P ⇒ Q) ≡ (¬Q ⇒ ¬P), ale neplatí (P ⇒ Q) ≡ (Q ⇒ P): implikácia má pri každom ohodnotení rovnakú hodnotu ako jej obmena, ale existuje ohodnotenie, pri ktorom sa líši od obrátenej implikácie (logickú ekvivalenciu ≡ definujeme v kapitole o tautológiách).

Tabuľka to ukáže bez debaty: stĺpec implikácie a obmeny je rovnaký, obrátená implikácia sa líši v dvoch riadkoch.

Druhá pasca je prvý riadok s P = 0: keď predpoklad neplatí, je implikácia pravdivá, nech je Q čokoľvek. „Ak je 7 párne, som pápež“ je pravdivý výrok. Znie to čudne, ale dáva to zmysel — implikácia sľubuje len niečo o situácii, keď P platí, a ten sľub sa nedá porušiť, keď P neplatí.

Obe pasce zmiznú, keď implikáciu prepíšeme pomocou „nie“ a „alebo“:

P ⇒ Q ≡ ¬P ∨ Q

P ⇒ Q

sľub „keď P, tak Q“ — chceme vedieť, kedy je dodržaný

¬P

keď predpoklad neplatí, sľub sa danej situácie netýka, a je teda dodržaný sám od seba — odtiaľ riadky s P = 0

Q

keď predpoklad platí, sľub je dodržaný len vtedy, keď naozaj nastane Q

Veta — implikácia je ekvivalentná s obmenou (dôkaz bez tabuľky)

Veta. Nech P, Q sú výrokové premenné. Potom (¬Q ⇒ ¬P) ≡ (P ⇒ Q) a (Q ⇒ P) ≢ (P ⇒ Q).

Dôkaz. Podľa prepisu A ⇒ B ≡ ¬A ∨ B (rozbor vyššie):

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

Použili sme len prepis implikácie (dvakrát), dvojitú negáciu ¬¬Q ≡ Q a to, že pri „alebo“ nezáleží na poradí. Obrátená implikácia Q ⇒ P ≡ ¬Q ∨ P je iný výraz — pre P = 0, Q = 1 dáva 0, zatiaľ čo P ⇒ Q dáva 1. ∎

4. Tautológie a ekvivalentné výroky

Definícia — tautológia, kontradikcia, ekvivalencia

Nech A, B sú zložené výroky vo výrokových premenných P₁, …, P_n a pre ohodnotenie v : {P₁, …, P_n} → {0, 1} označuje v(A) ∈ {0, 1} hodnotu výroku A pri tomto ohodnotení.

1. A je tautológia (napr. P ∨ ¬P) práve vtedy, keď v(A) = 1 pre každé ohodnotenie v;
2. A je kontradikcia (napr. P ∧ ¬P) práve vtedy, keď v(A) = 0 pre každé ohodnotenie v;
3. A a B sú logicky ekvivalentné, píšeme A ≡ B, práve vtedy, keď v(A) = v(B) pre každé ohodnotenie v, t. j. práve vtedy, keď A ⇔ B je tautológia.

Ekvivalentné výroky teda majú v pravdivostnej tabuľke rovnaký stĺpec. Píšeme A ≢ B, keď ekvivalentné nie sú.

Tak sa dajú overiť De Morganove zákony z dielu o množinách: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. Stĺpce sú rovnaké:

Overenie tabuľkou je jednoduchý algoritmus — prejdi všetky ohodnotenia a hľadaj to, ktoré výrok zhodí:

from itertools import product

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

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

Overiť tautológiu tabuľkou je spoľahlivé, ale pre n premenných to znamená 2ⁿ riadkov. Pre 20 premenných je to 2²⁰ = 1 048 576 riadkov, na čo počítaču stačí zlomok sekundy. Pre 300 premenných je to 2³⁰⁰ ≈ 2,04 · 10⁹⁰ riadkov — viac, ako je atómov vo vesmíre (asi 10⁸⁰). Aj pri miliarde riadkov za sekundu by to trvalo 2 · 10⁸¹ s, zatiaľ čo vesmír je starý asi 4 · 10¹⁷ s. Otázka, či sa dá výrok vôbec splniť (problém SAT), je jedným z najslávnejších ťažkých problémov informatiky.

5. Prečo XOR zastavil prvé neurónové siete

Nakreslime si štyri kombinácie P a Q ako body v rovine a zafarbime ich podľa výsledku. Pri „a“ aj „alebo“ sa dajú zelené body oddeliť od oranžových jednou priamkou. Pri XOR to nejde — zelené body ležia na jednej uhlopriečke a oranžové na druhej:

P ∧ Q

P ∨ Q

P ⊕ Q

Perceptrón, najjednoduchšia neurónová sieť, vie rozdeliť body len priamkou. V roku 1969 Minsky a Papert ukázali, že preto nezvládne ani takú jednoduchú funkciu ako XOR, a záujem o neurónové siete na roky opadol. Riešenie je pridať vrstvu: XOR sa dá zložiť z jednoduchších funkcií, (P ∨ Q) ∧ ¬(P ∧ Q), a dvojvrstvová sieť to zvládne. Tu sa začína príbeh hlbokého učenia.

Definícia — perceptrón s dvoma vstupmi

Nech w₁, w₂ ∈ ℝ sú váhy a b ∈ ℝ prah (bias). Perceptrón s dvoma vstupmi s parametrami w₁, w₂, b je funkcia f_{w1, w2, b} : {0, 1}² → {0, 1},

f_{w1, w2, b}(p, q) = 1 práve vtedy, keď w₁p + w₂q + b > 0; inak f_{w1, w2, b}(p, q) = 0.

Pre (w₁, w₂) ≠ (0, 0) je množina {(p, q) ∈ ℝ² : w₁p + w₂q + b = 0} priamka — tá rozdeľuje rovinu na časť „1“ a časť „0“.

Funkcia g : {0, 1}² → {0, 1} je lineárne oddeliteľná práve vtedy, keď ju vie vypočítať nejaký perceptrón:

∃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 alebo 1 — perceptrón má dať rovnakú hodnotu ako logická spojka

w₁p + w₂q

vážený súčet vstupov: váha hovorí, ako veľmi daný vstup „hlasuje“ za jednotku

b

prah posúva priamku — určuje, koľko hlasov je potrebných; bez neho by priamka musela viesť začiatkom

> 0

rozhodnutie áno/nie: na ktorej strane priamky bod leží

Veta — XOR nie je lineárne oddeliteľný (dôkaz sporom)

Veta. Nech XOR : {0, 1}² → {0, 1}, XOR(p, q) = p ⊕ q. Potom XOR nie je lineárne oddeliteľná, t. j. neexistujú w₁, w₂, b ∈ ℝ, pre ktoré by f_{w1, w2, b} = XOR.

Dôkaz. Predpokladajme pre spor, že perceptrón s w₁, w₂, b počíta XOR. Štyri riadky tabuľky dávajú štyri 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.

Sčítaním prostredných dvoch: w₁ + w₂ + 2b > 0, teda w₁ + w₂ + b > −b ≥ 0. To odporuje štvrtej nerovnosti. Spor — taký perceptrón neexistuje. ∎

Druhá vrstva spor obíde. Skrytý neurón h₁ počíta OR (váhy 1, 1, prah −0,5), h₂ počíta AND (váhy 1, 1, prah −1,5) a výstup y = [h₁ − h₂ − 0,5 > 0] hovorí „OR, ale nie AND“. Každý z troch neurónov je perceptrón; farby v záhlaví tabuľky zodpovedajú členom jeho vzorca vyššie:

6. Predikáty a kvantifikátory

Definícia — predikát a kvantifikátory

Nech M je neprázdna množina (obor premennej). Predikát (výroková forma) na M je predpis P, ktorý každému x ∈ M priradí výrok P(x) — výrok s premennou, ktorý sa po dosadení prvku M stane výrokom (napr. na M = ℤ: P(x) = „x je párne“). Ekvivalentne je to funkcia P : M → {0, 1}, x ↦ v(P(x)).

1. Všeobecný kvantifikátor: výrok ∀x ∈ M : P(x) je pravdivý práve vtedy, keď P(x) je pravdivý pre každé x ∈ M, t. j. práve vtedy, keď {x ∈ M : P(x)} = M.
2. Existenčný kvantifikátor: výrok ∃x ∈ M : P(x) je pravdivý práve vtedy, keď P(x) je pravdivý pre aspoň jedno x ∈ M, t. j. práve vtedy, keď {x ∈ M : P(x)} ≠ ∅.

Na poradí rôznych kvantifikátorov záleží: nech M, N sú neprázdne množiny a P(x, y) predikát na M × N. Potom vždy platí

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

ale opačná implikácia vo všeobecnosti neplatí (protipríklad v rámčeku nižšie).

Definície v AI sú plné kvantifikátorov. Prípustná heuristika z dielu o prehľadávaní je „∀n : h(n) ≤ h*(n)“ — a vyvrátiť ju stačí jediným stavom, kde odhad prestrelí.

Prečo stačí jeden stav, hovorí pravidlo pre negáciu kvantifikátora — De Morganov zákon pre „všetky“ a „existuje“:

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

¬

negácia „prejde“ dovnútra — z popretia celého tvrdenia sa stane popretie vlastnosti pri jednom prvku

∀x / ∃x

pri prechode negácie sa kvantifikátor otočí: „nie pri všetkých“ znamená „aspoň pri jednom nie“ — to je ten protipríklad

P(x)

vlastnosť sama zostáva rovnaká; mení sa len to, koľkých prvkov sa týka

Na konečnej množine sú kvantifikátory len dlhé spojky: pre M = {1, 2, 3} je ∀x : P(x) to isté čo P(1) ∧ P(2) ∧ P(3) a ∃x : P(x) to isté čo P(1) ∨ P(2) ∨ P(3). Pravidlo hore je potom obyčajný De Morganov zákon, len pre tri členy namiesto dvoch.

7. Čo je dôkaz

Definícia — dôkaz a modus ponens

Nech Γ je množina výrokov — predpokladov (axiómy, skôr dokázané vety, predpoklady tvrdenia) — a T je výrok. Dôkaz tvrdenia T z Γ je konečná postupnosť výrokov V₁, V₂, …, V_k (k ≥ 1) taká, že

1. V_k = T (postupnosť končí dokazovaným tvrdením);
2. pre každé i = 1, …, k platí V_i ∈ Γ, alebo V_i vznikne z niektorých výrokov V_j s j < i použitím odvodzovacieho pravidla.

Základné odvodzovacie pravidlo je modus ponens: pre ľubovoľné výroky A, B platí

z A a A ⇒ B sa smie odvodiť B.

Pravidlo je správne (z pravdivých výrokov odvodí len pravdivý výrok), pretože (A ∧ (A ⇒ B)) ⇒ B je tautológia.

Príklad — dôkaz ako postupnosť riadkov

Predpoklady: P („prší“), P ⇒ Q („keď prší, je mokro“), Q ⇒ R („keď je mokro, šmýka sa to“). Tvrdenie: R.

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

Každý riadok má zdôvodnenie, ktoré sa dá overiť mechanicky: buď je v zozname predpokladov, alebo odkazuje na dva skoršie riadky tvaru A a A ⇒ B.

8. Druhy dôkazov

Priamy dôkaz

Z predpokladov krok za krokom dôjdeme k tvrdeniu. Tvrdenie: súčet dvoch párnych čísel je párny (celé číslo m je párne práve vtedy, keď ∃a ∈ ℤ : m = 2a). Dôkaz: párne čísla sú 2a a 2b pre celé a, b. Ich súčet je 2a + 2b = 2(a + b), teda dvojnásobok celého čísla — párne číslo. ∎

Dôkaz obmenou a sporom

Namiesto P ⇒ Q dokážeme ekvivalentné ¬Q ⇒ ¬P — alebo predpokladáme, že tvrdenie neplatí, a dôjdeme k nezmyslu. Tvrdenie: prvočísel je nekonečne veľa. Dôkaz sporom (Euklides): keby ich bolo konečne veľa, p₁, …, p_k, vezmeme N = p₁ · … · p_k + 1. Žiadne p_i nedelí N — vždy zostane 1. N teda má prvočíselného deliteľa, ktorý v zozname chýba. Spor. ∎

Príklad — Euklidovo číslo s konkrétnymi prvočíslami

Pre zoznam 2, 3, 5, 7: N = 2 · 3 · 5 · 7 + 1 = 211. Delenie 2, 3, 5 aj 7 dá zvyšok 1 a 211 je samo prvočíslo, ktoré v zozname nebolo.

Pre zoznam 2, 3, 5, 7, 11, 13: N = 30 030 + 1 = 30 031 = 59 · 509. Tu N prvočíslo nie je — ale jeho prvočíselní delitelia 59 a 509 v zozname chýbajú. Dôkaz netvrdí, že N je prvočíslo, len že má nového prvočíselného deliteľa.

Protipríklad

Tvrdenie „pre všetky“ sa vyvracia jediným príkladom. „Každé nepárne číslo väčšie ako 1 je prvočíslo“ platí pre 3, 5 a 7 — a padá na 9 = 3 · 3. Tri príklady nič nedokazujú, jeden protipríklad vyvracia.

Matematická indukcia

Definícia — princíp matematickej indukcie

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

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

potom

∀n ∈ ℕ : P(n).

Princíp je jednou zo základných vlastností prirodzených čísel (v Peanovej aritmetike axióma). Rovnako funguje so základom v ľubovoľnom n₀ ∈ ℤ: z P(n₀) a ∀n ≥ n₀ : P(n) ⇒ P(n + 1) vyplýva P(n) pre všetky celé n ≥ n₀.

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

P(1)

základ — prvá kocka naozaj spadne; bez neho by krok nemal odkiaľ začať

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

indukčný krok — jedna implikácia, dokázaná pre všeobecné n, nahradí nekonečne veľa jednotlivých overení; je to „reťaz modus ponens“ 1 → 2 → 3 → …

∀n : P(n)

to, čo chceme: tvrdenie pre všetky prirodzené čísla naraz

Tvrdenie: pre všetky n ∈ ℕ je 1 + 2 + … + n = n(n + 1)/2. Farby zodpovedajú častiam princípu indukcie vyššie. Základ P(1): pre n = 1 je vľavo 1 a vpravo 1 · 2/2 = 1. Krok P(n) ⇒ P(n + 1): ak platí vzorec pre n, potom 1 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = n(n + 1) + 2(n + 1)/2 = (n + 1)(n + 2)/2, čo je vzorec pre n + 1. Podľa princípu indukcie teda ∀n ∈ ℕ : P(n). ∎ Rovnaký výsledok ukazuje aj obrázok: dve schodiská z bodiek dajú dohromady obdĺžnik n × (n + 1).

Pre n = 100 dáva vzorec 100 · 101/2 = 5050 — výsledok, ktorý podľa legendy vypočítal malý Gauss tak, že sčítal dvojice 1 + 100, 2 + 99, …, 50 + 51: päťdesiat dvojíc po 101.

Definícia — invariant cyklu

Nech cyklus v programe prebehne k ≥ 0-krát a pre j = 0, 1, …, k je I(j) tvrdenie o hodnotách premenných programu po j prechodoch (I(0) hovorí o stave pred prvým prechodom). I je invariant cyklu práve vtedy, keď

1. I(0) platí (invariant platí pred prvým prechodom) a
2. ∀j ∈ {0, 1, …, k − 1} : I(j) ⇒ I(j + 1) (každý prechod ho zachová).

Indukciou podľa počtu prechodov j (so základom j = 0) potom I(j) platí pre všetky j = 0, …, k, špeciálne I(k) po skončení cyklu — z neho vyčítame výsledok.

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 poslednom prechode i == n: s == n * (n + 1) // 2

Indukciou sa v informatike dokazuje správnosť algoritmov: „po k krokoch cyklu platí…“. Takto sa dokazuje napríklad to, že UCS rozbaľuje stavy v neklesajúcom poradí ceny — a preto nájde najlacnejšiu cestu.

9. Logika v umelej inteligencii

• Symbolická AI — prvé systémy umelej inteligencie boli logické: znalosti zapísané ako pravidlá „ak–tak“ a odvodzovanie modus ponens. Na tom stáli expertné systémy osemdesiatych rokov.
• SAT solvery riešia úlohu „dá sa tento výrok splniť?“ pre milióny premenných — plánujú, overujú hardvér a hľadajú chyby v programoch.
• Overovanie AI — logikou sa dokazujú vlastnosti systémov: že autopilot nikdy nedá dva protichodné povely, alebo že neurónová sieť nezmení rozhodnutie kvôli neviditeľnému šumu.
• Jazykové modely a dôkazy — dnešné modely vedia písať dôkazy, a tie sa potom kontrolujú formálnymi nástrojmi, ktoré každý krok overia mechanicky.

Odvodzovanie v expertnom systéme je modus ponens opakovaný, kým pribúdajú nové fakty — dopredné reťazenie. Pravidlo je dvojica (predpoklady, záver), teda implikácia A₁ ∧ … ∧ A_k ⇒ B:

def dopredne_retezeni(fakta, pravidla):
    fakta = set(fakta)
    zmena = True
    while zmena:                                    # kým niečo pribudlo
        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"}, "šmýka sa"), ({"šmýka sa", "ponáhľam sa"}, "pozor")]
dopredne_retezeni({"prší", "ponáhľam sa"}, pravidla)    # {prší, ponáhľam sa, mokro, šmýka sa, pozor}

Cyklus skončí vždy: každý prechod so zmenou pridá aspoň jeden záver a záverov je len toľko, koľko je pravidiel. Na príklade pribudnú všetky tri nové fakty už v prvom prechode, pretože pravidlá sú zoradené tak, ako na seba nadväzujú; druhý prechod len overí, že nič nepribudlo. V opačnom poradí pravidiel by prechody so zmenou boli tri.

10. Zhrnutie

• Výrok je pravda, alebo nepravda; spojky ¬ ∧ ∨ ⇒ ⇔ ⊕ sú presne definované pravdivostnou tabuľkou.
• Implikácia je ekvivalentná s obmenou, nie s obrátenou implikáciou — a s nepravdivým predpokladom je vždy pravdivá.
• XOR sa nedá rozdeliť jednou priamkou, a preto potrebuje neurónová sieť viac vrstiev.
• Na poradí kvantifikátorov záleží; tvrdenie „pre všetky“ vyvracia jeden protipríklad.
• Dôkaz je reťaz overiteľných krokov: priamy, obmenou, sporom alebo indukciou.

Máte na to iný názor? Napíšte na support@coden-app.com.