Výroková logika
Splnitelnost formulí, logická ekvivalence a důsledek, universální systémy spojek, disjunktivní a konjunktivní normální tvary, úplné normální tvary a jejich vztah k pravdivostní tabulce.
🔤 Jazyk a syntaxe výrokové logiky
Induktivní definice formule:
- Každá prvotní formule (A, B, …) je výroková formule.
- Jsou-li E a F výrokové formule, pak ¬E, (E ∧ F), (E ∨ F), (E ⇒ F), (E ⇔ F) jsou výrokové formule.
- Nic jiného výroková formule není.
Podformule je podřetězec formule F, který je sám formulí. Formační strom zobrazuje strukturu formule — kořen je celá formule, listy jsou prvotní formule, vnitřní uzly jsou spojky.
| 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 |
Klíčová „past": implikace A ⇒ B je nepravdivá pouze při A=1 a B=0. Ve všech ostatních případech (včetně A=0) je pravdivá!
Pravdivostní ohodnocení v přiřazuje každé prvotní formuli hodnotu 0 nebo 1. Pravdivost složené formule v(F) se určí rekurzivně dle tabulky. Formule s n prvotními formulemi má 2ⁿ různých ohodnocení a pravdivostní tabulka má 2ⁿ řádků.
Nutná a postačující podmínka: E ⇒ F je tautologie → E je postačující podmínka pro F; F je nutná podmínka pro E. E ⇔ F je tautologie → E je nutná a postačující podmínka pro F.
✅ Splnitelnost, tautologie a kontradikce
- Negace tautologie je kontradikce a naopak.
- Každá tautologie je splnitelná; žádná kontradikce není splnitelná.
- F = ⊤ ⟺ F je tautologie; F = ⊥ ⟺ F je kontradikce.
Klasické příklady tautologií:
- A ∨ ¬A — zákon vyloučeného třetího
- ¬(A ∧ ¬A) — zákon vyloučení sporu
- (A ⇒ B) ⇔ (¬B ⇒ ¬A) — zákon kontrapozice
- ¬(A ⇒ B) ⇔ (A ∧ ¬B) — negace implikace
- ((A ⇒ B) ∧ A) ⇒ B — modus ponens
SAT problém: rozhodnutí, zda je zadaná formule splnitelná, je NP-úplný problém klíčový pro informatiku, kryptografii a AI. Řešit jej lze pravdivostní tabulkou nebo převedením na ÚDNT/ÚKNT.
⟺ Logická ekvivalence a logický důsledek
- E = F ⟺ E ⇔ F je tautologie
- E ⊨ F ⟺ E ⇒ F je tautologie
- E ⊨ F ⟺ E ∧ ¬F je kontradikce
To znamená: místo tabulky pro E ⊨ F stačí zkontrolovat, zda E ∧ ¬F je kontradikce.
Základní vlastnosti = a ⊨: logická ekvivalence je relace ekvivalence (reflexivní, symetrická, tranzitivní); logický důsledek je tranzitivní a reflexivní; E = F ⟺ E ⊨ F a F ⊨ E současně.
Řetězec logických důsledků (od nejsilnějšího k nejslabšímu): ⊥ ⊨ A∧B ⊨ A ⊨ A∨B ⊨ ⊤. Důsledek: kontradikce implikuje vše; vše implikuje tautologii.
Nahrazení podformule: Tvrzení 2.3 — pokud G = G', pak nahrazením G za G' ve formuli F dostaneme formuli F' splňující F = F'. To umožňuje krok-po-kroku zjednodušování formulí.
📐 Logické zákony
Logické zákony jsou předem dokázané tautologie. Umožňují manipulaci s formulemi bez pravdivostní tabulky. Každý zákon je tautologie tvaru E = F nebo E ⊨ F.
- Zákon vyloučení sporu: A ∧ ¬A = ⊥
- Zákon vyloučeného třetího: A ∨ ¬A = ⊤
- Zákon dvojí negace: ¬¬A = A
- Vlastnosti ⊤,⊥: A ∧ ⊤ = A; A ∨ ⊥ = A; A ∧ ⊥ = ⊥; A ∨ ⊤ = ⊤
- Komutativita: A ∧ B = B ∧ A; A ∨ B = B ∨ A
- Asociativita: (A ∧ B) ∧ C = A ∧ (B ∧ C); totéž pro ∨
- Idempotence: A ∧ A = A; A ∨ A = A
- Absorpce: A ∧ (A ∨ B) = A; A ∨ (A ∧ B) = A
- Distributivita: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) a obráceně
- De Morganovy zákony: ¬(A ∧ B) = ¬A ∨ ¬B; ¬(A ∨ B) = ¬A ∧ ¬B
- Kontrapozice: (A ⇒ B) = (¬B ⇒ ¬A)
- Převod ⇒ na ∨: (A ⇒ B) = (¬A ∨ B)
- Negace ⇒: ¬(A ⇒ B) = (A ∧ ¬B)
- Rozklad ⇔: A ⇔ B = (A ⇒ B) ∧ (B ⇒ A) = (A ∧ B) ∨ (¬A ∧ ¬B)
- Negace ⇔: ¬(A ⇔ B) = (A ⇔ ¬B) = (¬A ⇔ B)
- A ⇔ ⊤ = A; A ⇔ ⊥ = ¬A
- Modus ponens: (A ⇒ B) ∧ A ⊨ B
- Modus tollens: (A ⇒ B) ∧ ¬B ⊨ ¬A
- Disjunktivní syllogismus: (A ∨ B) ∧ ¬A ⊨ B
- Hypotetický sylogismus: (A ⇒ B) ∧ (B ⇒ C) ⊨ (A ⇒ C)
- Konstruktivní dilema: (A ⇒ B) ∧ (C ⇒ D) ∧ (A ∨ C) ⊨ (B ∨ D)
- Destruktivní dilema: (A ⇒ B) ∧ (C ⇒ D) ∧ (¬B ∨ ¬D) ⊨ ¬A ∨ ¬C
Proč se to učit? Místo pracné pravdivostní tabulky (2ⁿ řádků) lze formulemi manipulovat krok-po-kroku pomocí zákonů — jako algebra. Například: ¬(A ⇒ B) = ¬(¬A ∨ B) = ¬¬A ∧ ¬B = A ∧ ¬B — bez jediné tabulky.
🔧 Universální systémy logických spojek (USS)
Motivace: V hardwaru nebo při formálních metodách chceme co nejmenší základ spojek, ze kterého lze vyjádřit cokoliv.
- 5-prvkové USS (triviální): {¬, ∧, ∨, ⇒, ⇔}
- 3-prvkové USS: {¬, ∧, ∨} — eliminujeme ⇒ a ⇔
- 2-prvkové USS: {¬, ∨}, {¬, ∧}, {¬, ⇒}
- 1-prvkové USS: pouze NAND (↑) nebo NOR (↓)
A ↑ B = ¬(A ∧ B) (NAND: „ne oba"). A ↓ B = ¬(A ∨ B) (NOR: „ani jeden").
Vyjádření vše pomocí NAND ↑:
- ¬A = A ↑ A
- A ∧ B = (A ↑ B) ↑ (A ↑ B)
- A ∨ B = (A ↑ A) ↑ (B ↑ B)
- A ⇒ B = A ↑ (B ↑ B)
Věta: NAND a NOR jsou jediné dvě jednoprvkové USS!
{∧, ∨, ⇒} bez negace — tyto spojky neumí z tautologie vyrobit kontradikci (zachovávají „pravdivost"). Totéž platí pro jakoukoli množinu bez ¬, NAND nebo NOR.
{¬, ⇔} — ekvivalence sama o sobě neumí vyjádřit konjunkci ani disjunkci pro více proměnných.
Jak dokázat, že {¬, ∨} je USS? Stačí ukázat, že ∧ a ⇔ lze vyjádřit: A ∧ B = ¬(¬A ∨ ¬B) (De Morgan); A ⇒ B = ¬A ∨ B; A ⇔ B = (A ⇒ B) ∧ (B ⇒ A) — první dvě pak dosadíme do posledního. Každou formuli tak převedeme na ekvivalentní s jen ¬ a ∨.
📝 Disjunktivní normální tvar (DNT) a Konjunktivní normální tvar (KNT)
Věta: Ke každé výrokové formuli existuje logicky ekvivalentní formule v DNT i v KNT.
Proč jsou DNT/KNT užitečné? DNT odhaluje splňující ohodnocení na první pohled (stačí, aby byl pravdivý alespoň jeden implikant). KNT je základ pro rezoluční metodu dokazování.
- Eliminuj ⇔: A ⇔ B = (A ⇒ B) ∧ (B ⇒ A)
- Eliminuj ⇒: A ⇒ B = ¬A ∨ B
- Posuň ¬ dovnitř: De Morgan (¬(A∧B) = ¬A∨¬B; ¬(A∨B) = ¬A∧¬B), dvojitá negace (¬¬A = A)
- Pro DNT: distribuuj ∧ přes ∨: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
- Pro KNT: distribuuj ∨ přes ∧: A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
- Zjednodušuj: odstraň kontradiktorické implikanty (A ∧ ¬A) a tautologické klauzule (A ∨ ¬A), použij absorpci.
Příklad: A ⇒ (¬B ∧ C) = ¬A ∨ (¬B ∧ C) — DNT. Distribucí: = (¬A ∨ ¬B) ∧ (¬A ∨ C) — KNT.
Pozor: DNT ani KNT nejsou jednoznačně určeny — ke každé formuli existuje obecně více různých DNT a KNT!
Přechod DNT ↔ KNT přes negaci: Znegujeme formuli v DNT (De Morgan každý implikant) → dostaneme KNT formule ¬F. A naopak.
🗺️ Úplné normální tvary (ÚDNT, ÚKNT)
Věta: Ke každé formuli existuje ekvivalentní formule v ÚDNT i ÚKNT. Na rozdíl od obecného DNT/KNT jsou ÚDNT i ÚKNT jednoznačně určeny (až na pořadí mintermů/maxtermů a literálů).
ÚDNT ↔ řádky s hodnotou 1:
- Každý minterm odpovídá přesně jednomu řádku tabulky s hodnotou 1.
- Každý minterm je pravdivý pro právě jedno ohodnocení.
- Počet mintermů = počet splňujících ohodnocení.
ÚKNT ↔ řádky s hodnotou 0:
- Každý maxterm odpovídá přesně jednomu řádku tabulky s hodnotou 0.
- Každý maxterm je nepravdivý pro právě jedno ohodnocení.
- Počet maxtermů = počet nesplňujících ohodnocení.
Důsledek: počet mintermů + počet maxtermů = 2ⁿ (kde n = počet prvotních formulí).
A = B právě když ÚDNT(A) a ÚDNT(B) mají stejné mintermy (nebo ÚKNT stejné maxtermy).
A ⊨ B právě když každý minterm ÚDNT(A) je obsažen v ÚDNT(B). Ekvivalentně: každý maxterm ÚKNT(B) je obsažen v ÚKNT(A).
Praktické: porovnáme ÚKNT (méně maxtermů = více tautologičtější formule) nebo ÚDNT (více mintermů = více splnitelnějsí).
Jak přejít z ÚDNT na ÚKNT? Znegujeme formuli (De Morgan), mintermy negace jsou maxtermy původní formule. ÚKNT(F) obsahuje všechny maxtermy, které neodpovídají mintermům ÚDNT(F).
📚 Shrnutí a kontrolní otázky – Výroková logika
- Pravdivost formule se určí rekurzivně dle tabulky; implikace je nepravdivá jen pro (1, 0).
- E = F ⟺ E ⇔ F je tautologie; E ⊨ F ⟺ E ⇒ F je tautologie ⟺ E ∧ ¬F je kontradikce.
- Logické zákony umožňují manipulaci bez tabulek; klíčové: De Morgan, kontrapozice, distributivita.
- NAND a NOR jsou jediné jednoprvkové USS; {¬, ∨} a {¬, ∧} jsou nejmenší „běžné" USS.
- ÚDNT/ÚKNT jsou jednoznačné; minterm odpovídá řádku pravdivostní tabulky s hodnotou 1, maxterm s hodnotou 0.
Q: Co je logická ekvivalence a jak ji ověříme?
A: E = F, pokud pro každé ohodnocení v(E) = v(F). Ověříme: (a) pravdivostní tabulkou, (b) ukážeme, že E ⇔ F je tautologie, nebo (c) ukážeme E ⊨ F a F ⊨ E.
Q: Uveďte a vysvětlete jednoprvkový USS.
A: NAND ↑ (Sheafferův symbol): A ↑ B = ¬(A ∧ B). Je to USS, protože: ¬A = A ↑ A; A ∧ B = (A ↑ B) ↑ (A ↑ B); A ∨ B = (A ↑ A) ↑ (B ↑ B). Analogicky NOR ↓. Jsou to jediné dvě spojky tvořící jednoprvkový USS.
Q: Co je DNT a KNT? Jaký je rozdíl?
A: DNT = disjunkce implikantů (konjunkcí literálů); KNT = konjunkce klauzulí (disjunkcí literálů). DNT odhaluje splňující ohodnocení; KNT je základ pro rezoluci. Každou formuli lze do obou převést.
Q: Jaký je vztah mezi ÚDNT a pravdivostní tabulkou?
A: Každý minterm v ÚDNT odpovídá jednomu řádku tabulky s hodnotou 1, a naopak. Počet mintermů = počet splňujících ohodnocení. Analogicky maxtermy ÚKNT ↔ řádky s hodnotou 0.
Q: Jak pomocí ÚDNT/ÚKNT rozhodout o logickém důsledku?
A: A ⊨ B právě když každý minterm ÚDNT(A) je obsažen i v ÚDNT(B). Ekvivalentně: každý maxterm ÚKNT(B) je obsažen i v ÚKNT(A).
Základy teorie čísel
Dělitelnost, REA a diofantické rovnice, prvočísla a ZVA, modulární aritmetika, Malá Fermatova a Eulerova věta, lineární kongruence, Čínská věta o zbytcích.
➗ Dělitelnost a základní vlastnosti
Platí: 1 | n a n | 0 pro každé n ∈ ℤ. Pokud a | b a b ≠ 0, pak |a| ≤ |b|.
- a|b ∧ a|c ⟹ a|(b+c)
- a|b ⟹ a|(nb) pro všechna n ∈ ℤ
- a|(b+c) ∧ a|b ⟹ a|c
- a|b ∧ a|c ⟺ a|(mb+nc) pro všechna m,n ∈ ℤ (lineární kombinace)
Důležitý vztah: gcd(a,b) · lcm(a,b) = |a| · |b|. (Stačí spočítat gcd, lcm dostaneme zadarmo.)
Nesoudělná čísla: a, b jsou nesoudělná, pokud gcd(a,b) = 1.
gcd(a, 0) = a pro a ≠ 0 — tímto EA končí. gcd(0, 0) = 0.
🧮 Eukleidův algoritmus (EA) a Rozšířený EA (REA)
EA efektivně počítá gcd opakovaným dělením se zbytkem. Jeden z nejstarších algoritmů (~300 př. n. l., Eukleidovy Základy).
254 = 1·158 + 96 → 158 = 1·96 + 62 → 96 = 1·62 + 34 → 62 = 1·34 + 28 → 34 = 1·28 + 6 → 28 = 4·6 + 4 → 6 = 1·4 + 2 → 4 = 2·2 + 0 → gcd = 2
Vlastnost gcd jako nejmenší lin. kombinace: gcd(a,b) je nejmenší kladné celé číslo, které lze vyjádřit jako m·a + n·b pro m, n ∈ ℤ.
Tabulka se sloupci: rᵢ (zbytky), αᵢ, βᵢ, qᵢ (podíl). Inicializace: řádek 1: (a, 1, 0, –); řádek 2: (b, 0, 1, ⌊a/b⌋). Pro každý další řádek i ≥ 3:
- rᵢ = rᵢ₋₂ − qᵢ₋₁ · rᵢ₋₁ (zbytek)
- αᵢ = αᵢ₋₂ − qᵢ₋₁ · αᵢ₋₁
- βᵢ = βᵢ₋₂ − qᵢ₋₁ · βᵢ₋₁
Skončíme, kdy rᵢ = 0. Výsledek je v předposledním řádku: gcd = rₖ, α = αₖ, β = βₖ.
Příklad: gcd(254, 158): poslední nenulový řádek dá α = 28, β = −45; tedy 2 = 28·254 + (−45)·158.
REA maticově: Upravujeme matici 2×3 postupnými eliminacemi (podobně jako GEM z LA1). Výsledek je v prvním řádku finální matice.
🔢 Lineární diofantické rovnice (LDR)
Věta o řešitelnosti: LDR ax + by = c má řešení ⟺ gcd(a,b) | c.
- Spočítáme d = gcd(a, b). Pokud d ∤ c, řešení neexistuje. Stop.
- REA na gcd(a, b): najdeme α, β splňující gcd(a,b) = α·a + β·b.
- Partikulární řešení: x₀ = α · (c/d), y₀ = β · (c/d).
- Všechna řešení: x = x₀ + (b/d)·k, y = y₀ − (a/d)·k, pro k ∈ ℤ.
Alternativní zápis: (x, y) = (x₀, y₀) + k · (b/d, −a/d). Dvojice (b/d, −a/d) je řešením přidružené homogenní rovnice ax + by = 0.
Analogie s LA1: Struktura množiny řešení je stejná jako pro SLR (partikulární řešení + řešení homogenní soustavy). Ovšem pracujeme nad ℤ, ne nad tělesem!
Praktický příklad: 7x + 13y = 125. d = gcd(7,13) = 1, 1 | 125 ✓. REA: 1 = 2·7 + (−1)·13. Partikulární: x₀ = 250, y₀ = −125. Všechna: x = 250 + 13k, y = −125 − 7k. Pro k = −18: x = 16, y = 1 (platíme 16×7 + 1×13 = 125 piastrů bez vracení).
🔵 Prvočísla a Základní věta aritmetiky
Předpokládejme, že jsou jen konečná prvočísla p₁, …, pₖ. Uvažme P = p₁·p₂·…·pₖ + 1. P je buď prvočíslo (spor — není v seznamu) nebo dělitelné nějakým pⱼ, ale pak pⱼ | 1, spor. ⟹ prvočísel je nekonečně mnoho. ∎
Buď p prvočíslo. Pak: p | ab ⟹ p | a nebo p | b. Obecněji: p | a₁·a₂·…·aₖ ⟹ p | aⱼ pro nějaké j.
Bez tohoto lemmatu bychom nedokázali jednoznačnost faktorizace. Plyne z Lemmatu 6.2: pokud gcd(a,b) = 1 a a | bc, pak a | c.
gcd a lcm z faktorizace: a = ∏pᵢ^αᵢ, b = ∏pᵢ^βᵢ. Pak gcd(a,b) = ∏pᵢ^min(αᵢ,βᵢ) a lcm(a,b) = ∏pᵢ^max(αᵢ,βᵢ).
Prakticky: pro výpočet gcd je EA mnohem rychlejší než faktorizace. Faktorizace velkých čísel je výpočetně náročná — na tom stojí bezpečnost RSA.
⏰ Modulární aritmetika a kongruence
Číslo m se nazývá modulus. Obvykle m ≥ 2. Kongruence je relace ekvivalence (reflexivní, symetrická, tranzitivní).
Pokud a ≡ b (mod m) a c ≡ d (mod m), pak:
- a + c ≡ b + d (mod m)
- a − c ≡ b − d (mod m)
- a · c ≡ b · d (mod m)
- aⁿ ≡ bⁿ (mod m) pro každé n ∈ ℕ
Důsledek: Při sčítání, odčítání a násobení (i mocnění) můžeme kdykoli nahradit číslo jeho zbytkem mod m. To výrazně usnadňuje výpočty!
Množina Zₘ = {0, 1, …, m−1} s operacemi +ₘ, ·ₘ (sčítání/násobení mod m) tvoří komutativní okruh. Splňuje: uzavřenost, komutativitu, asociativitu, distributivitu, existence 0 a 1 a aditivní inverze.
Definice: a⁻¹ je prvek Zₘ splňující a · a⁻¹ ≡ 1 (mod m).
Věta: Inverze k a existuje v Zₘ ⟺ gcd(a, m) = 1. Pokud existuje, je jediná.
Výpočet: REA na rovnici ax + my = 1 → x₀ je hledaná inverze (redukujeme mod m).
Kdy existují všechny inverze v Zₘ? Právě tehdy, když m je prvočíslo — pak (Zₘ, +ₘ, ·ₘ) je konečné těleso (jako v LA1!).
Věta: ac ≡ bc (mod m) ⟺ a ≡ b (mod m/gcd(m,c)). Modulo se při krácení změní!
Příklad: 3·3 ≡ 3·8 (mod 15), ale 3 ≢ 8 (mod 15). Správně: 3 ≡ 8 (mod 15/gcd(15,3)) = (mod 5). Platí: 3 ≡ 8 (mod 5)? 5 | (3−8) = −5. ✓
Speciální případ: Pokud gcd(c, m) = 1, pak krácení číslem c mění modulo, ale výsledek je v původním modulu (krácení je ekvivalentní úprava).
💡 Malá Fermatova věta (MFV) a Eulerova věta (EV)
- Pro prvočíslo p: φ(p) = p − 1 (a naopak!)
- Pro mocninu prvočísla: φ(pᵅ) = pᵅ − pᵅ⁻¹ = pᵅ(1 − 1/p)
- φ je multiplikativní: gcd(m,n)=1 ⟹ φ(mn) = φ(m)·φ(n)
- Pro n = p₁^α₁ · … · pₖ^αₖ: φ(n) = n · ∏(1 − 1/pᵢ)
Příklady: φ(100) = 100·(1−½)·(1−⅕) = 40. φ(360) = 360·½·⅔·⅘ = 96.
Algoritmus:
- Ověříme gcd(a, m) = 1 (nutné pro MFV/EV).
- Spočítáme φ(m) nebo p−1 (pro prvočíselný m).
- Rozložíme exponent: e = q · φ(m) + r, kde 0 ≤ r < φ(m).
- Výsledek: aᵉ = (aᵠ⁽ᵐ⁾)ᵠ · aʳ ≡ 1ᵠ · aʳ = aʳ (mod m).
Příklad: 5²⁰³ mod 101. gcd(101,5)=1, p=101 je prvočíslo, φ(101)=100. 203 = 2·100 + 3. Tedy 5²⁰³ = (5¹⁰⁰)² · 5³ ≡ 1² · 125 ≡ 24 (mod 101).
- Pro prvočíslo p: a⁻¹ ≡ aᵖ⁻² (mod p). Z MFV: a · aᵖ⁻² = aᵖ⁻¹ ≡ 1 (mod p).
- Pro obecné m: a⁻¹ ≡ aᵠ⁽ᵐ⁾⁻¹ (mod m). Z EV: a · aᵠ⁽ᵐ⁾⁻¹ = aᵠ⁽ᵐ⁾ ≡ 1 (mod m).
Příklad: 2⁻¹ mod 7. φ(7)=6. 2⁵ = 32 ≡ 4 (mod 7). Tedy 2⁻¹ ≡ 4 (mod 7). Ověření: 2·4 = 8 ≡ 1 (mod 7) ✓
Chceme bᴺ mod m. Vyjádříme N binárně, napočítáme b, b², b⁴, b⁸,… (každý krok: umocníme na druhou a zredukujeme mod m), vynásobíme jen pro jedničkové bity.
Příklad: 3⁶⁴⁴ mod 645. 644 = (1010000100)₂. 3⁴ ≡ 81, 3¹²⁸ ≡ 396, 3⁵¹² ≡ 111 (mod 645). Výsledek: 3⁶⁴⁴ = 3⁵¹²⁺¹²⁸⁺⁴ ≡ 111·396·81 ≡ 36 (mod 645).
🔎 Lineární kongruence
ax ≡ b (mod m) má řešení ⟺ gcd(a, m) | b.
Jak najít řešení:
- Převedeme na LDR: ax + my = b (kongruence m | (ax−b) = LDR).
- Partikulární řešení: x₀ (z REA).
- Všechna řešení v ℤ: x = x₀ + k · m/gcd(a,m), pro k ∈ ℤ.
- Počet řešení v Zₘ: přesně gcd(a, m) kusů.
Množina řešení v Zₘ: {x₀ + k · m/gcd(a,m) mod m | k = 0, 1, …, gcd(a,m)−1}.
Příklad: 9x ≡ 12 (mod 15). gcd(9,15)=3, 3 | 12 ✓. REA na 9x+15y=12: x₀=8. Všechna řešení: x = 8 + 5k. V Z₁₅: tři řešení {3, 8, 13} (3 = gcd(9,15) = 3 řešení).
Vztah s inverzí: Pokud gcd(a,m)=1, řešení je jediné: x ≡ a⁻¹·b (mod m). Inverzi najdeme REA nebo MFV/EV. Toto je analogie k lineární rovnici ax = b ⟹ x = a⁻¹b.
ax ≡ b (mod m) ⟺ ∃y ∈ ℤ: ax + my = b. Hledáme jen složku x, y nás nezajímá. Modulo m hraje roli koeficientu u y.
Pozor na záměnu: u LDR ax + by = c jsou oba parametry a, b „symetrické"; u kongruence ax ≡ b (mod m) je m modulus, ne koeficient u proměnné!
🇨🇳 Čínská věta o zbytcích (ČVOZ)
Řeší soustavu lineárních kongruencí s různými moduly. Klíčový podmínka: moduly jsou navzájem nesoudělná.
- M = m₁·m₂·…·mₙ
- Pro každé i: Mᵢ = M/mᵢ
- Pro každé i: najdeme Xᵢ splňující MᵢXᵢ ≡ 1 (mod mᵢ) — gcd(Mᵢ, mᵢ) = 1 zaručeno nesoudělností, tedy inverze existuje.
- Řešení: x ≡ a₁M₁X₁ + a₂M₂X₂ + … + aₙMₙXₙ (mod M)
Proč to funguje? MᵢXᵢ ≡ 1 (mod mᵢ) a MᵢXᵢ ≡ 0 (mod mⱼ) pro j ≠ i (protože mⱼ | Mᵢ). Takže v součtu každý sčítanec „vidí" jen svůj modul.
Příklad: x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5). M=30. M₁=15, M₂=10, M₃=6. 15X₁≡1 (mod 2) → X₁=1; 10X₂≡1 (mod 3) → X₂=1; 6X₃≡1 (mod 5) → X₃=1. x = 1·15·1 + 2·10·1 + 3·6·1 = 15+20+18 = 53 ≡ 23 (mod 30). Ověření: 23 mod 2 = 1 ✓, 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓.
Vyřešíme první kongruenci (x = a₁ + m₁·t), dosadíme do druhé, vyřešíme pro t, opět dosadíme atd. Pro ZČVOZ je toto jediná metoda.
Příklad ZČVOZ: x≡5 (mod 6), x≡3 (mod 10), x≡8 (mod 15). Ověříme podmínku: gcd(6,10)=2 | (5−3)=2 ✓; gcd(6,15)=3 | (5−8)=−3 ✓; gcd(10,15)=5 | (3−8)=−5 ✓. Řešíme: z první x=5+6t → dosadíme do druhé: 5+6t≡3 (mod 10) → 6t≡−2≡8 (mod 10) → 3t≡4 (mod 5) → t≡3 (mod 5) → t=3+5u → x=23+30u. Ověříme třetí: 23+30u≡8 (mod 15) → 23≡8 (mod 15): 8 mod 15 = 8, 23 mod 15 = 8 ✓. Výsledek: x ≡ 23 (mod 30).
Aplikace: Paralelní výpočty s velkými čísly (každý procesor počítá mod mᵢ, kombinujeme ČVOZ). Kryptosystém RSA (efektivní implementace). Kódová teorie.
📚 Shrnutí a kontrolní otázky – Základy teorie čísel
- gcd spočítáme EA (rychle!); Bézoutovy koeficienty dá REA. Platí gcd · lcm = |a|·|b|.
- LDR ax+by=c má řešení ⟺ gcd(a,b)|c. Všechna: partikulární + k·(b/d, −a/d).
- ZVA: jednoznačný prvočíselný rozklad. Eukleidovo lemma: p | ab ⟹ p|a nebo p|b.
- Kongruence zachovává +,−,·,mocnění; krácení mění modulo na m/gcd(m,c).
- MFV: aᵖ⁻¹ ≡ 1 (mod p) pro prvočíslo p, gcd(a,p)=1. EV: aᵠ⁽ᵐ⁾ ≡ 1 (mod m) pro gcd(a,m)=1.
- ČVOZ: nesoudělné moduly → jednoznačné řešení mod M=∏mᵢ. ZČVOZ: podmínka gcd(mᵢ,mⱼ)|aᵢ−aⱼ.
Q: Definujte dělitelnost a uveďte klíčové vlastnosti.
A: a | b ⟺ ∃k ∈ ℤ: a·k = b. Klíčové: a|b ∧ a|c ⟹ a|(mb+nc) pro všechna m,n ∈ ℤ. Dělitelnost je na ℕ reflexivní, antisymetrická a tranzitivní (uspořádání).
Q: Vysvětlete REA a co vrátí.
A: Rozšíří EA o sledování koeficientů. Invariant: rᵢ = αᵢ·a + βᵢ·b. Na výstupu: gcd(a,b) a Bézoutovy koeficienty α, β splňující gcd(a,b) = α·a + β·b.
Q: Kdy má LDR řešení a jak vypadají všechna?
A: ax+by=c má řešení ⟺ gcd(a,b)|c. Všechna řešení: x = x₀ + (b/d)·k, y = y₀ − (a/d)·k, d = gcd(a,b), k ∈ ℤ.
Q: Formulujte MFV, EV. Jak redukujeme velké mocniny?
A: MFV: p prvočíslo, gcd(a,p)=1 ⟹ aᵖ⁻¹ ≡ 1 (mod p). EV: gcd(a,m)=1 ⟹ aᵠ⁽ᵐ⁾ ≡ 1 (mod m). Redukce: e = q·φ(m)+r ⟹ aᵉ ≡ aʳ (mod m).
Q: Kdy existuje multiplikativní inverze mod m a jak ji spočítáme?
A: Inverze a⁻¹ mod m existuje ⟺ gcd(a,m)=1. Výpočet: (1) REA na ax+my=1; (2) pro prvočíslo p: a⁻¹ ≡ aᵖ⁻² (mod p); (3) obecně: a⁻¹ ≡ aᵠ⁽ᵐ⁾⁻¹ (mod m).
Q: Formulujte ČVOZ. Co říká ZČVOZ?
A: ČVOZ: soustava x≡aᵢ (mod mᵢ) s navzájem nesoudělnými moduly má vždy jednoznačné řešení mod M=∏mᵢ. ZČVOZ: soustava je řešitelná ⟺ gcd(mᵢ,mⱼ) | (aᵢ−aⱼ) pro všechna i≠j. Řešení je jednoznačné mod lcm(m₁,…,mₙ).
Q: Proč je prvočíselná faktorizace důležitá pro bezpečnost RSA?
A: Faktorizace velkých čísel je výpočetně velmi náročná (neznáme efektivní algoritmus). RSA stojí na faktu, že součin dvou velkých prvočísel snadno vytvoříme, ale zpětně rozložit je prakticky nemožné.