Logický obvod je přesným modelem ověřitelného přemýšlení, protože oba jsou lokálně kontrolovatelné: každý krok má pevné pravidlo a celý výsledek lze zpětně vysledovat až ke vstupům.
Mapování:
Hradlo = pravidlo úsudku (AND/OR/NOT ↔ konjunkce/disjunkce/negace, formálně Booleova algebra).
Vodič = tvrzení nesoucí pravdivostní hodnotu (pravda/nepravda).
Zapojení obvodu = důkaz/derivace - posloupnost kroků, kde každý plyne z předchozích.
Determinismus obvodu = reprodukovatelnost - stejné vstupy → stejný výstup, nezávisle na tom, kdo to kontroluje.
Trasovatelnost k chybnému hradlu = falzifikovatelnost - chybu lze izolovat na konkrétní krok.
Kombinační obvod tak odpovídá jednorázovému výroku (výstup jen ze vstupů); sekvenční obvod s pamětí odpovídá úvaze závislé na kontextu/předchozím stavu.
Hranice přirovnání (neschématizuji jako platné):
obvod je čistě propoziční a dvouhodnotový - nepokrývá pravděpodobnostní, nemonotónní ani sémanticky obsahové usuzování, kde závěr může padnout po přidání nové informace.
Kurt Gödel - incompleteness theorem CZ
Logický obvod (a jeho pravdivostní tabulka) je před Gödelem v bezpečí, ale ne proto, že je „úplný". Je v bezpečí proto, že vždycky doběhne k jasné odpovědi a je moc jednoduchý na to, aby mluvil sám o sobě.
Představ si logický obvod jako automat na jídlo/nápoj: hodíš mince (vstupy), vypadne přesně daný produkt (výstup), pokaždé.
Nic nezůstane nejasně „viset", nic není záhada. Když chceš, projedeš celou tabulku a všechno ověříš.
Nic nezůstane nejasně „viset", nic není záhada. Když chceš, projedeš celou tabulku a všechno ověříš.
Kurt Gödel mluví o něčem úplně jiném: o systému, který je tak silný, že umí dělat opravdovou aritmetiku (nejen sčítat, ale i násobit) a umí psát výroky o sobě samém.
Kurt Gödel mluví o systému tak silném, že v něm jde sčítání i násobení dohromady. A to není maličkost.
Kdyby uměl jen sčítat, zůstal by jednoduchý a řešitelný. Existoval by stroj, co o každém tvrzení rozhodne.
Kdyby uměl jen násobit, taky by byl v pohodě.
Teprve když má sčítání a násobení najednou, získá skrytou superschopnost.
Umí zakódovat libovolnou posloupnost čísel do jednoho jediného čísla.
A díky tomu si dokáže „psát vzkazy sám o sobě". Umí každý svůj důkaz převést na číslo a mluvit o něm uvnitř vlastní aritmetiky.
Právě tahle schopnost mluvit o sobě je to, co spustí Gödelovu past.
Kurt Gödel dokázal, že v takovém systému vždycky existuje výrok, který je pravdivý, ale systém ho nikdy nedokáže. Navíc žádný stroj nedokáže obecně rozhodnout, co v takovém systému dokazatelné je, a co ne.
To je Church–Turing.
Kurt Gödel mluví o systému tak silném, že v něm jde sčítání i násobení dohromady. A to není maličkost.
Kdyby uměl jen sčítat, zůstal by jednoduchý a řešitelný. Existoval by stroj, co o každém tvrzení rozhodne.
Kdyby uměl jen násobit, taky by byl v pohodě.
Teprve když má sčítání a násobení najednou, získá skrytou superschopnost.
Umí zakódovat libovolnou posloupnost čísel do jednoho jediného čísla.
A díky tomu si dokáže „psát vzkazy sám o sobě". Umí každý svůj důkaz převést na číslo a mluvit o něm uvnitř vlastní aritmetiky.
Právě tahle schopnost mluvit o sobě je to, co spustí Gödelovu past.
Kurt Gödel dokázal, že v takovém systému vždycky existuje výrok, který je pravdivý, ale systém ho nikdy nedokáže. Navíc žádný stroj nedokáže obecně rozhodnout, co v takovém systému dokazatelné je, a co ne.
To je Church–Turing.
Obvod tohle nedovede: neumí sčítat i násobit „naplno", neumí mluvit o sobě,
a hlavně na každou otázku odpoví ano/ne a skončí.
Proto se u něj gödelovská „pravda, kterou nedokážeš" ani nemůže objevit.
Pozor na časté zjednodušení: to, co obvod chrání, není jeho „úplnost", ale jeho rozhodnutelnost (vždy doběhne) a jeho slabost (neumí dost aritmetiky ani sebereferenci).
a hlavně na každou otázku odpoví ano/ne a skončí.
Proto se u něj gödelovská „pravda, kterou nedokážeš" ani nemůže objevit.
Pozor na časté zjednodušení: to, co obvod chrání, není jeho „úplnost", ale jeho rozhodnutelnost (vždy doběhne) a jeho slabost (neumí dost aritmetiky ani sebereferenci).
Logický obvod je elektronický obvod, který zpracovává binární signály (0/1) podle pravidel Booleovy algebry.
Skládá se z logických hradel (AND, OR, NOT, NAND, NOR, XOR), která na vstupní úrovně napětí (typicky nízká = 0, vysoká = 1) aplikují logickou funkci a dávají definovaný výstup.
Dělí se na dva typy:
Dělí se na dva typy:
Kombinační výstup: závisí jen na aktuálních vstupech (sčítačky, multiplexory, dekodéry).
Sekvenční výstup: závisí i na předchozím stavu, obsahuje paměťové prvky (klopné obvody, registry, čítače), řízené obvykle hodinovým signálem.
Fyzicky se realizuje polovodičovými prvky (dnes tranzistory CMOS) a tvoří základ všech číslicových systémů (procesory, paměti).
What are logic gates? Boolean algebra
Proč je znalost ARITMETIKY tak důležitá?
What are logic gates? Boolean algebra
Proč je znalost ARITMETIKY tak důležitá?
Evidence:
Presburgerova aritmetika (přirozená čísla, jen sčítání) je bezesporná, úplná a rozhodnutelná - existuje algoritmus, který o každém výroku rozhodne, zda platí. Gödel na ni nedopadá.
Skolemova aritmetika (jen násobení, bez sčítání) je rovněž rozhodnutelná.
Samotné násobení tedy taky nestačí.
Samotné násobení tedy taky nestačí.
Teprve obojí naráz (Robinsonovo Q, Peanova aritmetika) umožní zakódovat posloupnosti čísel do jednoho čísla tzv. Gödelovo číslování a β-funkci.
Gödel numbering
To je technický trik, kterým systém začne umět „mluvit o sobě" (kódovat vlastní důkazy jako čísla), a právě tehdy vzniká nedokazatelný pravdivý výrok.
Takže formulace „nejen sčítat, ale i násobit" je věcně správná, ale zamlčuje proč: nejde o „víc početních úkonů", ale o to, že kombinace sčítání a násobení je minimální síla nutná ke kódování syntaxe do aritmetiky.
Ani sčítání samo, ani násobení samo tuto schopnost nedají.
Ani sčítání samo, ani násobení samo tuto schopnost nedají.
Logic Symbols
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ↔ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣
Basic Math Symbols
≠ ± ∓ ÷ × ∙ – √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
https://www.reddit.com/r/math/search/?q=Gödel
Geometry Symbols
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
Algebra Symbols
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘∏ ∐ ∑ ⋀ ⋁ ⋂ ⋃ ⨀ ⨁ ⨂ 𝖕 𝖖 𝖗
Žádné komentáře:
Okomentovat