Autor: Guts A.K.
Vydavateľstvo: O.: Dedičstvo
Rok vydania: 2003
Stránky: 108
ISBN 5-8239-0126-7
Čítať:
Stiahnuť ▼: matematicheskayalogika2003.djvu

ŠTÁTNA UNIVERZITA OMSK FAKULTA POČÍTAČOV KATEDRA
KYBERNETIKA
A.K. Črevá
Matematická logika a teória algoritmov
Omsk 2003
VVK 60 MDT 53:630,11
Guts A.K. Matematická logika a teória algoritmov: Učebnica. -
Omsk: Heritage Publishing. Dialog-Siberia, 2003. - 108 s.
ISBN 5-8239-0126-7
Učebnica je venovaná prezentácii základov matematickej logiky a teórie
algoritmy. Základom manuálu sú abstrakty prečítaných prednášok
študenti druhého ročníka katedry informatiky v Omsku
Štátna univerzita v roku 2002.
Pre študentov študujúcich v odbore 075200 - „Počítač
bezpečnosť“ a špecialita 220100 – „Počítače,
komplexy, systémy a siete“.
ISBN 5-8239-0126-7
c) Štátna univerzita v Omsku, 2003
Obsah
Ja logika 7
1 klasická logika 8
1.1. Logika výrokov ................................ 8
1.1.1. Výroky ................................. 8
1.1.2. Základné logické zákony ................................... 9
1.1.3. Russellov logický paradox ............... 10
1.1.4. Algebra (logika) výrokov ............... 11
1.1.5. Rebríkové diagramy ................................... 12
1.1.6. Ekvivalentné vzorce ...................... 14
1.1.7. Booleova algebra ............................. 15
1.1.8. Pravdivé a platné vzorce ............. 15
1.1.9. Problém riešiteľnosti ................... 15
1.1.10. Logický dôsledok................................... 16
1.1.11. Sylogizmy................................... 17
1.2. Predikátová logika................................................ 17
1.2.1. Predikáty a vzorce ............... 18
1.2.2. Výklady ................................. 19
1.2.3. Pravdivosť a splniteľnosť vzorcov. modely,
platnosť, logický dôsledok....... 20
1.2.4. Gottlob Frege.......................... 21
1.2.5. Skolem funkcie
a skolemizácia vzorcov...................... 22
1.3. Metóda rozlíšenia................................................ 25
1.3.1. Metóda rozlíšenia v logike
výroky................................. 25
1.3.2. Metóda rozlíšenia v logike
predikáty................................. 29
3
4
Obsah
2 Formálne teórie (kalkul) 31
2.1. Definícia formálnej teórie alebo kalkulu. . 32
2.1.1. Dôkaz. Konzistentnosť teórie.
Úplnosť teórie................................ 32
2.2. Výrokový počet................................. 33
2.2.1. Jazyk a pravidlá pre odvodenie výrokového počtu
............................................. 33
2.2.2. Ukážka dôkazu vety........................ 35
2.2.3. Úplnosť a konzistentnosť
výrokový počet ........................ 36
2.3. Predikátová kalkulácia ................................ 37
2.3.1. Jazyk a pravidlá inferencie predikátového počtu 37
2.3.2. Úplnosť a konzistentnosť
predikátový počet ........................ 39
2.4. Formálna aritmetika ................................ 39
2.4.1. Rovnostárske teórie................................ 39
2.4.2. Jazyk a pravidlá odvodzovania formálnej aritmetiky
.............................................. 39
2.4.3. Dôslednosť formálneho
aritmetika. Gentzenova veta............ 40
2.4.4. Gödelova veta o neúplnosti................................... 41
2.4.5. Kurt Gödel...................... 42
2.5. Automatické odvodenie vety ........................ 43
2.5.1. S.Yu Maslov................................. 43
2.6. Logické programovanie ................................ 45
2.6.1. Logický program ........................ 46
2.6.2. Logické programovacie jazyky.... 49
3 Neklasická logika 50
3.1. Intuicionistická logika ................................. 50
3.2. Fuzzy logika................................................ 51
3.2.1. Fuzzy podmnožiny ................................... 51
3.2.2. Operácie na fuzzy
podmnožiny ............................. 52
3.2.3. Vlastnosti množiny fuzzy
podmnožiny................................. 53
3.2.4. Fuzzy výroková logika...................... 54
3.2.5. Fuzzy rebríkové diagramy ........... 56
3.3. Modálna logika................................................ 56
3.3.1. Druhy modality.................................. 57
Obsah
5
3.3.2. Počet 1 a T (Feis-von Wright) ........ 57
3.3.3. Počet S4, S5
a Brouwerov kalkul.................................. 58
3.3.4. Ocenenie vzorca .................................. 59
3.3.5. Kripkeho sémantika ........................ 60
3.3.6. Iné interpretácie modálov
znamenia ................................................. 62
3.4. Georg von Wright ................................... 62
3.5. Dočasná logika ............................. 62
3.5.1. Pryorova logika načasovania.................................. 63
3.5.2. Lemmonova logika načasovania................... 64
3.5.3. Von Wrightova časová logika...................... 64
3.5.4. Aplikácia logiky časovania
k programovaniu ............................. 65
3.5.5. Pnueli Temporal Logic ............................. 67
3.6. Algoritmická logika ........................ 70
3.6.1. Konštrukčné princípy
1 >

Federálna agentúra pre vzdelávanie

ŠTÁTNA UNIVERZITA RIADIACEHO SYSTÉMU A RÁDIOVEJ ELEKTRONIKY TOMSK (TUSUR)

Katedra automatizácie spracovania informácií

Súhlasím:

Hlava kaviareň AOI

profesor

Áno. Ekhlakov

"__" ______________2007

Smernice

k realizácii praktických prác na disciplíne

"Matematická logika a teória algoritmov"

pre študentov špecializácie 230102 -

"Automatizované systémy na spracovanie a riadenie informácií"

Vývojári:

čl. lektor na katedre AOI

POTOM Peremitina

Tomsk - 2007

Praktická lekcia č.1 „Vzorce výrokovej algebry“ 3

Praktická lekcia č.2 "Ekvivalentné transformácie vzorcov výrokovej algebry" 10

Praktická lekcia č.3 "Normálne formy vzorcov" 12

Praktická lekcia č.4 "Logické uvažovanie" 14

Praktická lekcia č.5 "Vzorce predikátovej logiky" 18

Cvičenie č. 6 Booleovské funkcie 23

Cvičenie č. 7 Čiastočne rekurzívne funkcie 28

Cvičenie č. 8 Turingove stroje 34

Praktická lekcia č. 1 "Vzorce výrokovej algebry"

Doktrína výrokov – algebra výrokov alebo algebra logiky – je najjednoduchšia logická teória. Atómový pojem výrokovej algebry je vyhlásenie - oznamovacia veta, vo vzťahu ku ktorej dáva zmysel tvrdenie o jej pravdivosti alebo nepravdivosti.

Príklad pravdivého tvrdenia: "Zem sa točí okolo Slnka." Príklad nepravdivého tvrdenia: „3 > 5“. Nie každá veta je výrok, výroky neobsahujú opytovacie a zvolacie vety. Veta: „Kaša je chutné jedlo“ nie je tvrdenie, pretože neexistuje konsenzus o tom, či je pravdivý alebo nepravdivý. Veta „Na Marse je život“ by sa mala považovať za tvrdenie, keďže objektívne je buď pravdivé, alebo nepravdivé, hoci zatiaľ nikto nevie, ktorý.

Keďže predmetom štúdia logiky sú iba pravdivostné hodnoty výrokov, zavádzajú sa pre ne písmenové označenia A, B, ... alebo X, Y ....

Každé vyhlásenie sa považuje za pravdivé alebo nepravdivé. Kvôli stručnosti napíšeme namiesto skutočnej hodnoty 1 a namiesto falošnej hodnoty 0. Napríklad X= „Zem sa točí okolo Slnka“ a Y= „3 > 5“ a X=1 a Y= 0. Výrok nemôže byť súčasne pravdivý aj nepravdivý.

Príkazy môžu byť jednoduché alebo zložené. Výroky „zem sa točí okolo Slnka“ a „3 > 5“ sú jednoduché. Zložené výroky sa tvoria z jednoduchých pomocou prirodzených (ruských) jazykových spojív NOT, AND, OR, IF-THEN, THEN-AND-ONLY-THEN. Pri použití abecedného zápisu výrokov sa tieto spojky nahrádzajú špeciálnymi matematickými symbolmi, ktoré možno považovať za symboly logických operácií.

Nižšie v tabuľke 1 sú uvedené varianty symbolov na označenie spojovacích prvkov a názvy zodpovedajúcich logických operácií.

Odmietnutie (inverzné) výroky X je tvrdenie, ktoré je pravdivé vtedy a len vtedy X nepravdivé (označené príp , znie „nie X“ alebo „to nie je pravda X”).

konjunkcia
dvoch výrokov sa nazýva výrok, ktorý je pravdivý vtedy a len vtedy, ak sú pravdivé oba výroky X a Y. Tejto logickej operácii zodpovedá spojenie výrokov so spojením „a“.

disjunkcia
dve vety X a Y Výrok sa považuje za nepravdivý vtedy a len vtedy, ak oba výroky X a Y falošné. V hovorovej reči táto logická operácia zodpovedá spojeniu „alebo“ (nie výlučne „alebo“).

implikácia dve vety X a Y je tvrdenie, ktoré je nepravdivé vtedy a len vtedy X pravda, a Y- nepravdivý (označený
; číta " X znamená Y“, „ak X, potom Y“). Operandy tejto operácie majú špeciálne názvy: X- balík, Y- záver.

Ekvivalencia dve vety X a Y sa nazýva výrok, ktorý je pravdivý vtedy a len vtedy, ak pravdivosť hodnoty X a Y sú rovnaké (symbol:
).

Tabuľka 1. Logické operácie

Operandy logických operácií môžu nadobúdať iba dve hodnoty: 1 alebo 0. Preto je možné každú logickú operáciu , &, , ,  jednoducho špecifikovať pomocou tabuľky s uvedením hodnoty výsledku operácie v závislosti od hodnôt operandov. Takáto tabuľka je tzv pravdivostná tabuľka (Tabuľka 2).

Tabuľka 2. Pravdivosť tabuľka logických operácií

Pomocou vyššie definovaných logických operácií je možné zostavovať z jednoduchých návrhov výrokové logické vzorce predstavujúce rôzne zložené výroky. Logický význam zloženého príkazu závisí od štruktúry príkazu vyjadrenej vzorcom a logických hodnôt základných príkazov, ktoré ho tvoria.

Pre systematické štúdium vzorcov vyjadrujúcich výroky sa zavádzajú premenné výroky P, P 1 , P 2 , ..., P N, pričom sa preberajú hodnoty z množiny (0, 1).

Vzorec výrokovej logiky F (P 1 , P 2 ,..., P N) sa nazýva tautológia resp rovnako pravdivé ak je jeho hodnota pre nejaké hodnoty P 1 , P 2 ,..., P N je 1 (pravda). Zavolajú sa vzorce, ktoré sa vyhodnotia ako pravdivé pre aspoň jednu množinu zoznamov premenných uskutočniteľné . Zavolajú sa vzorce, ktoré majú hodnotu „false“ pre akékoľvek hodnoty premenných protirečenia (rovnako nepravdivé, nemožné).

Navrhovaná učebnica (2. vydanie, stereotyp) tvorí základ súboru pre kurz matematickej logiky a teórie algoritmov, ktorý obsahuje aj zbierku úloh (Igoshin V.I. Úlohy a cvičenia z matematickej logiky a teórie algoritmov) .

Podrobne sú popísané základy teórie, sú znázornené smery prenikania logiky do základov algebry, analýzy, geometrie, na jej logickú analýzu sa používa materiál školského kurzu matematiky, vzťah matematickej logiky s počítačmi, je charakterizovaná informatika a systémy umelej inteligencie.

Úvod. Matematická logika v systéme moderného vzdelávania.
Logika a intuícia. Tradičná logika a matematická logika. Trochu histórie. Matematická logika – logika alebo matematika? Matematická logika vo vyučovaní matematiky. Matematická logika a moderné počítače.
Kapitola I. Algebra výrokov.
§ 1. Výkazy a operácie na nich.
Pojem výpovede. Negácia výroku. Spojenie dvoch viet. Disjunkcia dvoch výrokov. Implikácia dvoch tvrdení. Rovnocennosť dvoch výrokov. Zjednotenie jazyka a logické operácie (jazyk a logika). Všeobecný pohľad na logické operácie.
§2. Vzorce výrokovej algebry.
Stavba zložitých viet. Koncept výrokovej algebrickej formuly. Logický význam zloženého výroku. Zostavovanie pravdivostných tabuliek pre vzorce. Klasifikácia vzorcov výrokovej algebry. Myslenie a matematická logika
§ 3. Tautológie výrokovej algebry.
O význame tautológií. Základné tautológie. Základné pravidlá pre získanie tautológie.
§ 4. Logická ekvivalencia vzorcov.
Pojem ekvivalencie vzorcov. Znak ekvivalencie vzorcov. Príklady ekvivalentných vzorcov. Ekvivalentné transformácie vzorcov. Ekvivalencie v logike a identitách v algebre.
§ 5. Normálne formy pre vzorce výrokovej algebry.
Koncept normálnych foriem. Perfektné normálne formy. Reprezentácia vzorcov výrokovej algebry dokonalými disjunktívnymi normálnymi (CDN) formami. Znázornenie vzorcov výrokovej algebry dokonalými konjunktívnymi normálnymi (SKN) formami. Dva spôsoby, ako zredukovať vzorec výrokovej algebry do dokonalej normálnej formy
§ 6. Logické nasledovanie vzorcov.
Koncept logického dôsledku. Známky logického dôsledku. Dve vlastnosti logického dôsledku. Nasledovanie a ekvivalencia vzorcov. Pravidlá logického uvažovania. Ďalší spôsob, ako skontrolovať logické nasledovanie. Hľadanie dôsledkov z týchto priestorov. Hľadanie priestorov pre toto vyšetrovanie.
§ 7. Aplikácia výrokovej algebry do logicko-matematickej praxe.
Priame a inverzné vety. Nevyhnutné a postačujúce podmienky. Opačná a inverzná k opačnej vete. Zákon kontrapozície. Úprava štruktúry matematickej vety. Metódy dôkazu matematických viet. Deduktívne a induktívne uvažovanie. Správna a nesprávna deduktívna úvaha. Riešenie logických problémov. Princíp úplnej disjunkcie. Jedno zovšeobecnenie princípu úplnej disjunkcie.
Kapitola II. Booleovské funkcie.
§osem. Množiny, vzťahy, funkcie.
Koncept súboru. Inklúzia a rovnosť množín. Operácie na súpravách. Binárne vzťahy a funkcie. Koncept lar vzťahu.
§ 9. Booleovské funkcie jedného a dvoch argumentov.
Pôvod booleovských funkcií. Booleovské funkcie z jedného argumentu. Booleovské funkcie dvoch argumentov. Vlastnosti disjunkcie, konjunkcie a negácie. Vlastnosti ekvivalencie, implikácie a negácie. Vyjadrenie niektorých booleovských funkcií z hľadiska iných
§ 10. Booleovské funkcie n argumentov.
Koncept booleovskej funkcie. Počet boolovských funkcií. Vyjadrenie boolovských funkcií pomocou konjunkcie, disjunkcie a negácie. Booleovské funkcie a vzorce výrokovej algebry. Normálne formy booleovských funkcií.
§ 11. Systémy booleovských funkcií.
Kompletné systémy booleovských funkcií. Špeciálne triedy booleovských funkcií. Postova veta o úplnosti systému booleovských funkcií
§ 12. Aplikácia booleovských funkcií na reléovo-kontaktné obvody.
Myšlienka aplikácie. Dve hlavné úlohy teórie reléových kontaktných obvodov.
§ 13. Reléové kontaktné obvody v počítačoch.
Binárna polovičná sčítačka. Jednobitová binárna sčítačka. kódovač a dekodér.
§ 14. O niektorých ďalších aplikáciách teórie booleovských funkcií.
Diagnostika (rozpoznanie) chorôb. Rozpoznávanie vzorov.
Kapitola III. Formalizovaný výrokový kalkul.
§ 15. Systém axióm a teória formálnej inferencie.
Začiatky axiomatickej výrokovej teórie: počiatočné pojmy, systém axióm, pravidlo inferencie. Pojem inferencie a jej vlastnosti. Veta o dedukcii a jej dôsledky. Aplikácia vety o dedukcii. Odvodené pravidlá odvodenia
§ 16. Úplnosť a ďalšie vlastnosti formalizovaného výrokového počtu
Dokázateľnosť formuly a jej zhodná pravdivosť (syntax a sémantika). Lemma odvoditeľnosti. Úplnosť formalizovaného výrokového počtu. Veta o primeranosti. Konzistentnosť formalizovaného výrokového počtu. Rozhodnuteľnosť formalizovaného výrokového počtu
§ 17. Nezávislosť systému axióm formalizovaného výrokového počtu.
Koncept nezávislosti. Nezávislosť axiómy (A1). Nezávislosť axiómy (A2). Axiómová nezávislosť (A3). Nezávislosť systému axiómov
Kapitola IV. Predikátová logika.
§ 18. Základné pojmy týkajúce sa predikátov.
Pojem predikátu. Klasifikácia predikátov. Pravdivosť predikátu. Ekvivalencia a nasledujúce predikáty
§ 19. Logické operácie s predikátmi.
Predikátová negácia. Spojenie dvoch predikátov. Navrhnite, aby ste prešli na stránku diktátu. Vlastnosti negácie, konjunkcie a disjunkcie. Implikácia a ekvivalencia dvoch predikátov.
§ 20. Kvantifikátorové operácie na predikátoch.
Všeobecný kvantifikátor. Kvantifikátor existencie. Číselné kvantifikátory. Obmedzené kvantifikátory. Logický štvorec
§ 21. Vzorce predikátovej logiky.
Pojem predikátovej logickej formuly. Klasifikácia vzorcov predikátovej logiky. Tautológie predikátovej logiky
§ 22. Ekvivalentné premeny formúl a logický dôsledok formúl predikátovej logiky
Pojem ekvivalencie vzorcov. Redukovaný tvar pre predikátové logické vzorce. Prenexová normálna forma pre predikátové logické vzorce. Logické nasledovanie vzorcov predikátovej logiky
§ 23. Riešenie problémov platnosti a splniteľnosti formúl.
Vyjadrenie problému a jeho neriešiteľnosť vo všeobecnosti. Riešenie úlohy pre vzorce na konečných množinách. Príklad vzorca, ktorý je realizovateľný na nekonečnej množine a nie je realizovateľný na žiadnej konečnej množine. Problém riešenia splniteľnosti: vplyv kardinality množiny a štruktúry vzorca. Riešenie problému pre vzorce obsahujúce iba jednomiestne predikátové premenné. Problém riešenia platnosti a mohutnosti množiny, na ktorej sa vzorec uvažuje. Riešenie problémov pre V-vzorce a 3-vzorce
§ 24. Aplikácia predikátovej logiky do logicko-matematickej praxe.
Záznam v jazyku logických predikátov rôznych viet. Porovnanie predikátovej logiky a výrokovej logiky. Štruktúra matematických viet. Spôsoby uvažovania: aristotelovská sylogistika. Aristotelovská sylogistika a logika predikátov. Množinovo-teoretický výklad aristotelovskej sylogistiky. O iných spôsoboch uvažovania. Princíp úplnej disjunkcie v predikátovej forme. Metóda (úplnej) matematickej indukcie Nevyhnutné a postačujúce podmienky. Predikátová logika a množinová algebra.
§ 25. Formalizovaný predikátový počet.
Primárne pojmy (jazyk formalizovaného predikátového počtu). Systém axióm predikátového počtu. pravidlá výberu. Teória formálnej inferencie.
Kapitola V. Neformálne axiomatické teórie.
§ 26. Axiomatická metóda v matematike a axiomatických teóriách.
Pojem axiomatickej teórie. Ako vznikajú axiomatické teórie. Príklady axiomatických teórií. Interpretácie a modely axiomatickej teórie.
§ 27. Vlastnosti axiomatických teórií.
Dôslednosť. Kategorický. Nezávislosť systému axióm. Úplnosť.
Kapitola VI. Formálne axiomatické teórie.
§ 28. O formálnych axiomatických teóriách.
O histórii myšlienky formálnej axiomatickej teórie. Pojem formálnej axiomatickej teórie. Jazyk a metajazyk, vety a metateorémy formálnej teórie. Interpretácie a modely formálnej teórie. sémantický výstup. Metamatematika (vlastnosti formálnych axiomatických teórií). Formalizovaný výrokový kalkul ako formálna axiomatická teória Formalizácia teórie aristotelovských sylogizmov.
§ 29. Vlastnosti formalizovaného predikátového počtu.
Zdôvodnenie axiomatizácie Konzistentnosť formalizovaného predikátového počtu. Gödelova veta o existencii modelu. Úplnosť a primeranosť formalizovaného predikátového počtu. Neúplnosť formalizovaného predikátového počtu v absolútnom a úzkom zmysle Veta o kompaktnosti.
§ 30. Formálne teórie prvého rádu.
Teórie prvého poriadku s rovnosťou. O formálnych teóriách množín. O formálnej aritmetike. O formálnych teóriách číselných sústav.O formálnej geometrii. O formálnej matematickej analýze. Všeobecný pohľad na proces formalizácie matematickej teórie Na hraniciach axiomatickej metódy, metódy formalizácie a logiky.
Kapitola VII. Prvky teórie algoritmov.
§31. Intuitívne pochopenie algoritmov.
Algoritmy okolo nás. Neformálna predstava o algoritme. Potreba objasniť pojem algoritmus.
§ 32. Turingove stroje.
Definícia Turingovho stroja Aplikácia Turingovho stroja na slová. Dizajn Turingovho stroja. Turingovo vypočítateľné funkcie. Správna vypočítateľnosť funkcií na Turingovom stroji. Zloženie Turingových strojov. Turingova téza (základná domnienka v teórii algoritmov). Turingove stroje a moderné elektronické počítače.
§ 33. Rekurzívne funkcie.
Pôvod rekurzívnych funkcií. Základné pojmy teórie rekurzívnych funkcií a Churchove tézy. Primitívne rekurzívne funkcie. Primitívna rekurzívnosť predikátov. Turingova vypočítateľnosť primitívnych rekurzívnych funkcií. Ackermanove funkcie. operátor minimalizácie. Všeobecné rekurzívne a čiastočne rekurzívne funkcie. Turingova vypočítateľnosť čiastočne rekurzívnych funkcií. Čiastočná rekurzívnosť Turingovo vypočítateľných funkcií.
§ 34. Normálne Markovove algoritmy.
Markovove striedania. Normálne algoritmy a ich aplikácia na slová. Normálne vyčísliteľné funkcie a princíp Markovovej normalizácie. Zhoda triedy všetkých normálne vypočítateľných funkcií s triedou všetkých Turingových vypočítateľných funkcií. Ekvivalencia rôznych teórií algoritmov.
§ 35. Rozhodnuteľnosť a spočítateľnosť množín.
§ 36. Neriešiteľné algoritmické problémy.
Číslovanie algoritmov. Číslovanie na Turingovom stroji. Existencia Turingových nevypočítateľných funkcií. Problémy rozpoznávania sebauplatnenia a aplikovateľnosti. Algoritmicky neriešiteľné problémy vo všeobecnej teórii algoritmov. Riceova veta. Ďalšie príklady algoritmickej nerozhodnuteľnosti.
§ 37. Godelova veta o neúplnosti formálnej aritmetiky.
Formálne axiomatické teórie a prirodzené čísla. Formálna aritmetika a jej vlastnosti. Gödelova veta o neúplnosti. Gödel a jeho úloha v matematickej logike 20. storočia. .
Kapitola VIII. Matematická logika a počítače, informatika, umelá inteligencia.
* § 38. Matematická logika a počítačový softvér.
Základným základom programovania je teória algoritmov a matematická logika. Popis počítačových programov pomocou matematickej logiky. Popis programovania a analýza jeho konceptov pomocou matematickej logiky. Overovanie (dokazovanie správnosti) programov pomocou matematickej logiky.
§ 39. Aplikácia počítačov na dôkaz viet matematickej logiky.
Program "Logika-teoretik" a programy jemu blízke. Rezolučná metóda na dokazovanie viet vo výrokovom a predikátovom počte.
§ 40. Od matematickej logiky k logickému programovaniu.
Vznik jazyka PROLOG a jeho vývoj. Všeobecná charakteristika jazyka PROLOG. Stručný popis jazyka PROLOG a príklady. Oblasti použitia jazyka PROLOG.
§ 41. Matematická logika a informatika.
Všeobecná koncepcia databázy. Relačná databáza a logika dotazov v nej.
§ 42. Matematická logika a systémy umelej inteligencie História vývoja a predmet umelej inteligencie ako vedy. Reprezentácia znalostí v systémoch umelej inteligencie. Expertné systémy. Jazyk PROLOG v systémoch umelej inteligencie. Dokáže stroj myslieť.
Záver: Je logika všemocná v poznaní zákonitostí myslenia?
Bibliografia.

Logika a intuícia.
Duševná činnosť človeka je komplexný a mnohostranný proces, ktorý sa odohráva na vedomej aj na nevedomej (podvedomej) úrovni. Ide o najvyšší stupeň ľudského poznania, schopnosť adekvátne odrážať predmety a javy reality, t.j. k nájdeniu pravdy.

Logika a intuícia sú dve protikladné a neoddeliteľne spojené vlastnosti ľudského myslenia. Logické (deduktívne) myslenie sa líši v tom, že vždy vedie k pravdivému záveru z pravdivých premís, bez spoliehania sa na skúsenosti, intuíciu a iné vonkajšie faktory. Intuícia (z latinského intuitio - „z blízka“) je schopnosť pochopiť pravdu jej priamym pozorovaním bez zdôvodňovania pomocou logicky dôsledného dôkazu. Intuícia je teda akýmsi antipódom, protiváhou logiky a prísnosti.

Logická časť myšlienkového procesu prebieha na úrovni vedomia, intuitívna časť - na podvedomej úrovni.
Rozvoj vedy a najmä matematiky je nemysliteľný bez intuície. Vo vedeckom poznaní existujú dva typy intuície1: intuícia-úsudok a intuícia-hádanie. Intuícia-úsudok (alebo filozofická intuícia-úsudok) sa vyznačuje tým, že v tomto prípade sa priame vnímanie pravdy, objektívne spojenie vecí uskutočňuje nielen bez logicky rigorózneho dôkazu, ale takýto dôkaz pre túto pravdu neexistuje a v zásade nemôže existovať. Intuícia-úsudok sa uskutočňuje ako jediný (jednorazový) syntetický holistický akt zovšeobecňujúceho charakteru. Práve túto povahu logicky nepreukázateľných tvrdení majú Turingove, Churchove a Markovove tézy zvažované v teórii algoritmov.

Stiahnite si zadarmo e-knihu vo vhodnom formáte, pozerajte a čítajte:
Stiahnite si knihu Mathematical Logic and Theory of Algorithms, Igoshin VI, 2008 - fileskachat.com, rýchle a bezplatné stiahnutie.

11.1. Pojem algoritmus a teória algoritmov

Intuitívne sa algoritmus chápe ako proces postupného riešenia problému, ktorý prebieha v diskrétnom čase tak, že v každom ďalšom časovom okamihu sa systém objektov algoritmu získa podľa určitého zákona zo systému objektov, ktoré boli k dispozícii. v predchádzajúcom časovom okamihu. Intuitívne, pretože, prísne vzaté, pojem algoritmus je podobný pojmu množina, ktorý je nedefinovateľný.

V súlade s GOST 19781-74 „Výpočtové stroje. softvér. Pojmy a definície" algoritmus je presný predpis, ktorý definuje výpočtový proces vedúci od variabilných počiatočných údajov k požadovanému výsledku. To predpokladá prítomnosť vykonávateľa algoritmu - objektu, ktorý "vie, ako" vykonávať tieto akcie.

Slovo „algoritmus“ má pochádzať z mena stredoázijského (uzbeckého) matematika XIII. storočia Al Khorezmi (Abu Abdallah Muhammad ibn Musa al Khorezmi al Medjusi) – „Algorithmi“ v latinskom prepise, ktorý po prvý raz sformuloval pravidlá (postup) na vykonávanie štyroch aritmetických operácií v desiatkovej číselnej sústave.

Pokiaľ boli výpočty jednoduché, neboli potrebné žiadne špeciálne algoritmy. Keď bola potreba viacerých postupných postupov, objavila sa teória algoritmov. Ale s ešte väčšou komplikáciou úloh sa ukázalo, že niektoré z nich nie je možné vyriešiť algoritmicky. Takými sú napríklad mnohé úlohy, ktoré rieši „palubný počítač“ človeka – mozog. Riešenie takýchto problémov je založené na iných princípoch – tieto princípy využíva nová veda – neuromatematika a tomu zodpovedajúce technické prostriedky – neuropočítače. V tomto prípade sa uplatňujú procesy učenia, pokusov a omylov – teda to, čo práve robíme.

Kvalita algoritmu je určená jeho vlastnosťami (charakteristikami). Hlavné vlastnosti algoritmu sú:

1. masový charakter. Predpokladá sa, že algoritmus môže byť vhodný na riešenie všetkých problémov tohto typu. Napríklad algoritmus na riešenie systému lineárnych algebraických rovníc by mal byť použiteľný na systém pozostávajúci z ľubovoľného počtu rovníc.

2. Efektívnosť. Táto vlastnosť znamená, že algoritmus musí viesť k výsledku v konečnom počte krokov.

3. Istota. Pokyny zahrnuté v algoritme musia byť presné a zrozumiteľné. Táto charakteristika zabezpečuje jedinečnosť výsledku výpočtového procesu pre dané počiatočné dáta.

4. diskrétnosť. Táto vlastnosť znamená, že proces opísaný algoritmom a samotný algoritmus možno rozdeliť do samostatných základných etáp, ktorých možnosť používateľ môže vykonať na počítači je nepochybná.

Dnes je „digitálne tisícročie“ vo dvore a môžete mať dojem, že všetky úlohy podliehajú algoritmom. Ukazuje sa, že mnohé problémy nemožno vyriešiť algoritmicky. Ide o takzvané algoritmicky neriešiteľné problémy.

Na preukázanie algoritmickej riešiteľnosti alebo neriešiteľnosti problémov sú potrebné matematicky rigorózne a presné prostriedky. V polovici 30. rokov minulého storočia sa uskutočnili pokusy o formalizáciu konceptu algoritmu a navrhli sa rôzne modely algoritmov: rekurzívne funkcie; "stroje" - Turing, Post; normálne Markovove algoritmy.

Následne sa zistilo, že tieto a ďalšie modely sú ekvivalentné v tom zmysle, že triedy problémov, ktoré riešia, sa zhodujú. Tento fakt sa nazýva Churchova téza. Teraz je to všeobecne akceptované. Formálna definícia pojmu algoritmus vytvorila predpoklady pre rozvoj teórie algoritmu ešte pred vývojom prvých počítačov. Pokrok výpočtovej techniky podnietil ďalší rozvoj teórie algoritmov. Okrem stanovenia algoritmickej riešiteľnosti problémov sa teória algoritmov zaoberá aj odhadom zložitosti algoritmov z hľadiska počtu krokov (časová zložitosť) a potrebnej pamäte (priestorová zložitosť) a tiež vyvíja efektívne algoritmy v tento zmysel.

Implementácia niektorých algoritmov, za akýchkoľvek rozumných predpokladov z hľadiska fyziky o rýchlosti vykonávania elementárnych krokov, môže trvať dlhšie, ako podľa moderných názorov existuje vesmír, alebo viac pamäťových buniek ako atómov, ktoré tvoria planétu Zem.

Ďalšou úlohou teórie algoritmov je preto vyriešiť problém eliminácie enumerácie možností v kombinatorických algoritmoch. Odhad zložitosti algoritmov a vytváranie takzvaných efektívnych algoritmov je jednou z najdôležitejších úloh modernej teórie algoritmov.