Autor: Guts A.K.
Editura: O.: Heritage
Anul publicării: 2003
Pagini: 108
ISBN 5-8239-0126-7
Citit:
Descarca: matematicheskayalogika2003.djvu

UNIVERSITATEA DE STAT OMSK DEPARTAMENTUL FACULTATEA DE INFORMATICĂ
CIBERNETICĂ
A.K. Curaj
Logica matematică și teoria algoritmilor
Omsk 2003
VVK 60 UDC 53:630.11
Curaj A.K. Logica matematică și teoria algoritmilor: Manual. -
Omsk: Editura Heritage. Dialog-Siberia, 2003. - 108 p.
ISBN 5-8239-0126-7
Manualul este dedicat prezentării fundamentelor logicii și teoriei matematice
algoritmi. Baza manualului este rezumatele prelegerilor care au fost citite
studenții din anul II ai departamentului de informatică din Omsk
Universitatea de Stat în 2002.
Pentru studenții care studiază la specialitatea 075200 - „Computer
securitate" și specialitatea 220100 - "Computere,
complexe, sisteme și rețele”.
ISBN 5-8239-0126-7
(c) Universitatea de Stat din Omsk, 2003
Cuprins
I logica 7
1 Logica clasică 8
1.1. Logica propozițiilor.................................. 8
1.1.1. Proverbe................................. 8
1.1.2. Legile de bază ale logicii .................................. 9
1.1.3. Paradoxul logic al lui Russell ............... 10
1.1.4. Algebra (logica) propozițiilor ............... 11
1.1.5. Diagrame cu scară .................................. 12
1.1.6. Formule echivalente ....................... 14
1.1.7. Algebră Boole................................. 15
1.1.8. Formule adevărate și valide ........... 15
1.1.9. Problema solubilității ................. 15
1.1.10. Consecință logică................................. 16
1.1.11. Silogisme.................................... 17
1.2. Logica predicatului................................... 17
1.2.1. Predicate și formule ............... 18
1.2.2. Interpretări................................. 19
1.2.3. Adevărul și satisfacabilitatea formulelor. modele,
validitate, consecință logică........ 20
1.2.4. Gottlob Frege....................... 21
1.2.5. Funcții Skolem
și skolemizarea formulelor....................... 22
1.3. Metoda de rezoluție................................... 25
1.3.1. Metoda rezoluțiilor în logică
enunţuri................................. 25
1.3.2. Metoda rezoluțiilor în logică
predicate................................. 29
3
4
Cuprins
2 Teorii formale (calcul) 31
2.1. Definiția teoriei formale sau a calculului. . 32
2.1.1. Dovada. Consistența teoriei.
Completitudinea teoriei................................. 32
2.2. Calcul propozițional................................. 33
2.2.1. Limbajul și regulile pentru inferența calculului propozițional
............................................. 33
2.2.2. Un exemplu de demonstrare a teoremei............... 35
2.2.3. Completitudine și consecvență
calculul propozițional ........................... 36
2.3. Calcul de predicate................................. 37
2.3.1. Limbajul și regulile de inferență ale calculului predicatului 37
2.3.2. Completitudine și consecvență
calculul predicatului................................. 39
2.4. Aritmetică formală................................. 39
2.4.1. Teoriile egalitare.................................. 39
2.4.2. Limbajul și regulile pentru derivarea aritmeticii formale
.............................................. 39
2.4.3. Consecvența formalului
aritmetic. Teorema lui Gentzen .............. 40
2.4.4. Teorema de incompletitudine a lui Gödel................................... 41
2.4.5. Kurt Gödel................... 42
2.5. Derivarea teoremei automate ................................. 43
2.5.1. S.Yu. Maslov................................. 43
2.6. Programare logică................................. 45
2.6.1. Program logic ............................. 46
2.6.2. Limbaje logice de programare.... 49
3 Logica neclasică 50
3.1. Logica intuiționistă................................. 50
3.2. Logica neclară................................... 51
3.2.1. Subseturi fuzzy ............................... 51
3.2.2. Operații pe fuzzy
submulțimi.............................. 52
3.2.3. Proprietățile setului de fuzzy
submultimile.................................. 53
3.2.4. Logica propozițională fuzzy................... 54
3.2.5. Diagrame cu scară neclară ........... 56
3.3. Logica modală................................... 56
3.3.1. Tipuri de modalitate.................................. 57
Cuprins
5
3.3.2. Calcul 1 și T (Feis-von Wright) ........ 57
3.3.3. Calcul S4, S5
și calculul lui Brouwer................................. 58
3.3.4. Evaluarea formulei ................................. 59
3.3.5. Semantica lui Kripke ................................. 60
3.3.6. Alte interpretări ale modalelor
semne........................................... 62
3.4. Georg von Wright ................................... 62
3.5. Logica temporară ................................. 62
3.5.1. Logica de sincronizare a lui Pryor ................................. 63
3.5.2. Logica de sincronizare a lui Lemmon.................. 64
3.5.3. Logica temporală a lui Von Wright....................... 64
3.5.4. Aplicarea logicii de sincronizare
la programare................................. 65
3.5.5. Pnueli Temporal Logic .............................. 67
3.6. Logica algoritmică.................................. 70
3.6.1. Principii de construcție
1 >

Agenția Federală pentru Educație

UNIVERSITATEA DE STAT DE SISTEME DE CONTROL ȘI RADIO ELECTRONICĂ TOMSK (TUSUR)

Departamentul de Automatizare a Prelucrării Informaţiei

Sunt de acord:

Cap cafenea AOI

Profesor

Da. Ekhlakov

„__” ____________2007

Instrucțiuni

la implementarea lucrărilor practice pe disciplină

„Logica matematică și teoria algoritmilor”

pentru studenții specialității 230102 -

„Sisteme automate pentru prelucrarea și controlul informațiilor”

Dezvoltatori:

Artă. lector la catedra AOI

APOI. Peremitina

Tomsk - 2007

Lecția practică nr. 1 „Formulele de algebră propozițională” 3

Lecția practică nr. 2 „Transformări echivalente ale formulelor de algebră propozițională” 10

Lecția practică nr. 3 „Forme normale de formule” 12

Lecția practică nr. 4 „Raționament logic” 14

Lecția practică nr. 5 „Formulele logicii predicatelor” 18

Practica #6 Funcții booleene 23

Practica #7 Funcții parțial recursive 28

Practica #8 Mașini Turing 34

Lecția practică nr. 1 „Formulele de algebră propozițională”

Doctrina propozițiilor - algebra propozițiilor sau algebra logicii - este cea mai simplă teorie logică. Noțiunea atomică a algebrei propoziționale este afirmație - o propoziție declarativă în raport cu care afirmația despre adevărul sau falsitatea sa are sens.

Un exemplu de afirmație adevărată: „Pământul se învârte în jurul soarelui”. Un exemplu de afirmație falsă: „3 > 5”. Nu orice propoziție este o afirmație; enunțurile nu includ propoziții interogative și exclamative. Propoziția: „Triciul este un fel de mâncare delicios” nu este o afirmație, deoarece nu poate exista un consens asupra faptului că este adevărat sau fals. Propoziția „Există viață pe Marte” ar trebui considerată o afirmație, deoarece în mod obiectiv este fie adevărată, fie falsă, deși nimeni nu știe încă care dintre ele.

Întrucât subiectul de studiu al logicii este doar valorile de adevăr ale propozițiilor, pentru acestea sunt introduse denumirile de litere A, B, ... sau X, Y ....

Fiecare afirmație este considerată a fi adevărată sau falsă. Pentru concizie, vom scrie 1 în loc de valoarea adevărată și 0 în loc de valoarea falsă. De exemplu, X= „Pământul se învârte în jurul Soarelui” și Y= „3\u003e 5”, iar X=1 și Y = 0. Afirmația nu poate fi atât adevărată, cât și falsă.

Enunțurile pot fi simple sau compuse. Afirmațiile „pământul se învârte în jurul soarelui” și „3 > 5” sunt simple. Enunțurile compuse sunt formate din cele simple cu ajutorul conectivelor din limbajul natural (rus) NU, ȘI, SAU, DACĂ-Atunci, ATUNCI-ȘI-NUMAI-Atunci. Când se utilizează notația alfabetică pentru enunțuri, aceste conjunctive sunt înlocuite cu simboluri matematice speciale, care pot fi considerate simboluri ale operațiilor logice.

Mai jos, în tabelul 1, există variante de simboluri pentru desemnarea conexiunilor și denumirile operațiilor logice corespunzătoare.

Negare declarații (inversie). X este o afirmație care este adevărată dacă și numai dacă X fals (notat sau , scrie „nu X” sau „nu este adevărat că X”).

conjuncţie
două propoziții se numesc propoziție care este adevărată dacă și numai dacă ambele propoziții sunt adevărate Xși Y. Această operație logică corespunde conexiunii enunțurilor cu uniunea „și”.

disjuncție
două propoziții Xși Y Se spune că o afirmație este falsă dacă și numai dacă ambele afirmații Xși Y fals. În vorbirea colocvială, această operație logică corespunde uniunii „sau” (nu exclusiv „sau”).

implicare două propoziții X și Y este o afirmație care este falsă dacă și numai dacă X adevărat, și Y- fals (notat
; citeste " X presupune Y", "dacă X, apoi Y”). Operanzii acestei operații au denumiri speciale: X- pachet, Y- concluzie.

Echivalenţă două propoziții Xși Y se numește o afirmație care este adevărată dacă și numai dacă adevărul valorează Xși Y sunt aceleași (simbol:
).

Tabelul 1. Operații logice

Operanzii operațiilor logice pot lua doar două valori: 1 sau 0. Prin urmare, fiecare operație logică , &, , ,  poate fi specificată cu ușurință folosind tabelul, indicând valoarea rezultatului operației în funcție de valori. a operanzilor. O astfel de masă se numește tabelul de adevăr (Masa 2).

Tabelul 2. Tabelul de adevăr al operațiilor logice

Cu ajutorul operațiilor logice definite mai sus, se poate construi din propoziții simple formule logice propoziționale reprezentând diferite enunţuri compuse. Sensul logic al enunțului compus depinde de structura enunțului, exprimat prin formulă, și de valorile logice ale enunțurilor elementare care o formează.

Pentru studiul sistematic al formulelor care exprimă enunţuri se introduc enunţuri variabile P, P 1 , P 2 , ..., P N, luând valori din mulțimea (0, 1).

Formula logică propozițională F (P 1 , P 2 ,..., P N) se numește tautologie sau identic adevărat dacă valoarea sa pentru orice valoare P 1 , P 2 ,..., P N este 1 (adevărat). Sunt apelate formule care se evaluează la adevărat pentru cel puțin un set de liste de variabile realizabil . Sunt numite formule care iau valoarea „falsă” pentru orice valoare a variabilelor contradictii (identic fals, imposibil).

Manualul propus (ed. a II-a, stereotip) formează baza unui set pentru cursul logicii matematice și teoria algoritmilor, care include și o colecție de probleme (Igoshin V.I. Sarcini și exerciții de logică matematică și teoria algoritmilor) .

Bazele teoriei sunt descrise în detaliu, sunt prezentate direcțiile de pătrundere a logicii în fundamentele algebrei, analizei, geometriei, materialul cursului școlar de matematică este folosit pentru analiza lui logică, relația logicii matematice cu calculatoarele, se caracterizează informatica și sistemele de inteligență artificială.

Introducere. Logica matematică în sistemul de învățământ modern.
Logica si intuitia. Logica logica traditionala si logica matematica. Un pic de istorie. Logica matematica - logica sau matematica? Logica matematică în predarea matematicii. Logica matematică și calculatoarele moderne.
Capitolul I. Algebra enunţurilor.
§ 1. Declaraţii şi operaţiuni asupra acestora.
Conceptul de enunț. Negarea afirmației. Conjuncția a două propoziții. Disjuncția a două afirmații. Implicația a două afirmații. Echivalența a două afirmații. Uniri ale limbajului si operatii logice (limbaj si logica). Vedere generală a operațiilor logice.
§2. Formule de algebră propozițională.
Construcția de propoziții complexe. Conceptul unei formule de algebră propozițională. Sensul logic al unei afirmații compuse. Compilare de tabele de adevăr pentru formule. Clasificarea formulelor de algebrei propoziționale. Gândirea și logica matematică
§ 3. Tautologii ale algebrei propoziţionale.
Despre sensul tautologiilor. Tautologii de bază. Reguli de bază pentru obținerea unei tautologie.
§ 4. Echivalenţa logică a formulelor.
Conceptul de echivalență a formulelor. Semnul echivalenței formulelor. Exemple de formule echivalente. Transformări echivalente de formule. Echivalențe în logică și identități în algebră.
§ 5. Forme normale pentru formule de algebră propozițională.
Conceptul de forme normale. Forme normale perfecte. Reprezentarea formulelor de algebră propozițională prin forme normale disjunctive perfecte (CDN). Reprezentarea formulelor de algebrei propoziționale prin forme normale conjunctive perfecte (SKN). Două moduri de a reduce o formulă de algebră propozițională la forma normală perfectă
§ 6. Urmărirea logică a formulelor.
Conceptul de consecință logică. Semne ale unei consecințe logice. Două proprietăți ale consecințelor logice. Urmărirea și echivalența formulelor. Regulile raționamentului logic. O altă modalitate de a verifica urmărirea logică. Găsirea consecințelor din aceste premise. Găsirea premiselor pentru această anchetă.
§ 7. Aplicarea algebrei propoziționale la practica logico-matematică.
Teoreme directe și inverse. Condiții necesare și suficiente. Opusul și inversul teoremei opuse. Legea contrapoziției. Modificarea structurii teoremei matematice. Metode de demonstrare a teoremelor matematice. Raționamentul deductiv și inductiv. Raționament deductiv corect și incorect. Rezolvarea problemelor logice. Principiul disjuncției complete. O generalizare a principiului disjuncției complete.
Capitolul II. Funcții booleene.
§opt. Seturi, relații, funcții.
Conceptul de set. Includerea și egalitatea multimurilor. Operații pe platouri. Relații și funcții binare. Conceptul de relație mare.
§ 9. Funcţii booleene ale unui şi doi argumente.
Originea funcțiilor booleene. Funcții booleene dintr-un singur argument. Funcții booleene a două argumente. Proprietățile disjuncției, conjuncției și negației. Proprietăți de echivalență, implicare și negație. Exprimarea unor funcții booleene în termenii altora
§ 10. Funcţii booleene ale n argumente.
Conceptul de funcție booleană. Numărul de funcții booleene. Exprimarea funcțiilor booleene prin conjuncție, disjuncție și negație. Funcții booleene și formule ale algebrei propoziționale. Forme normale ale funcțiilor booleene.
§ 11. Sisteme de funcţii booleene.
Sisteme complete de funcții booleene. Clase speciale de funcții booleene. Teorema lui Post privind completitudinea unui sistem de funcții booleene
§ 12. Aplicarea funcţiilor booleene la circuitele releu-contact.
Idee de aplicare. Două sarcini principale ale teoriei circuitelor releu-contact.
§ 13. Circuite releu-contact în calculatoare.
Jumătate sumator binar. Adunator binar cu un singur bit. codificator și decodor.
§ 14. Despre alte aplicaţii ale teoriei funcţiilor booleene.
Diagnosticul (recunoașterea) bolilor. Recunoasterea formelor.
Capitolul III. Calcul propozițional formalizat.
§ 15. Sistemul de axiome şi teoria inferenţei formale.
Începutul teoriei propoziționale axiomatice: concepte inițiale, sistem de axiome, regula de inferență. Conceptul de inferență și proprietățile sale. Teorema deducției și consecințele acesteia. Aplicarea teoremei deducerii. Reguli de inferență derivate
§ 16. Completitudine și alte proprietăți ale calculului propozițional formalizat
Provabilitatea unei formule și adevărul ei identic (sintaxă și semantică). Lema de derivabilitate. Completitudinea calculului propozițional formalizat. Teorema de adecvare. Consistența calculului propozițional formalizat. Decidabilitatea calculului propozițional formalizat
§ 17. Independenţa sistemului de axiome ale calculului propoziţional formalizat.
Conceptul de independență. Independenta axiomei (A1). Independenta axiomei (A2). Independența axiomei (A3). Independenta sistemului de axiome
Capitolul IV. Logica predicatelor.
§ 18. Concepte de bază legate de predicate.
Conceptul de predicat. Clasificarea predicatelor. Setul de adevăr al predicatului. Echivalența și următoarele predicate
§ 19. Operaţii logice asupra predicatelor.
Negație de predicat. Conjuncția a două predicate. Design pentru a accesa pagina dicat. Proprietățile negației, conjuncției și disjuncției. Implicația și echivalența a două predicate.
§ 20. Operaţii cuantificatoare asupra predicatelor.
Cuantificator general. Cuantificator de existență. Cuantificatori numerici. Cuantificatori limitati. Pătrat logic
§ 21. Formule ale logicii predicatelor.
Conceptul unei formule logice predicate. Clasificarea formulelor logice predicate. Tautologii ale logicii predicatelor
§ 22. Transformări echivalente ale formulelor și consecință logică a formulelor logicii predicatelor
Conceptul de echivalență a formulelor. Forma redusă pentru formulele logice predicate. Forma normală Prenex pentru formule logice predicate. Urmărirea logică a formulelor logice predicate
§ 23. Probleme de rezolvare pentru validitatea și satisfacabilitatea formulelor.
Enunțarea problemei și imposibilitatea acesteia în general. Rezolvarea problemei pentru formule pe mulțimi finite. Un exemplu de formulă care este fezabilă pe o mulțime infinită și nu este fezabilă pe nicio mulțime finită. Problemă de rezolvare a satisfacției: influența cardinalității setului și a structurii formulei. Rezolvarea problemei pentru formule care conțin doar variabile predicate cu un singur loc. Problema rezolvării validității și cardinalității mulțimii pe care se ia în considerare formula. Rezolvarea problemelor pentru formule V și formule 3
§ 24. Aplicarea logicii predicatelor la practica logico-matematică.
Înregistrarea în limbajul predicatelor logice a diferitelor propoziții. Comparația dintre logica predicatelor și logica propozițională. Structura teoremelor matematice. Metode de raționament: silogistică aristotelică. Silogistica aristotelică și logica predicatelor. Interpretarea teoretică a seturilor a silogisticii aristotelice. Despre alte metode de raționament. Principiul disjuncției complete în formă de predicat. Metoda de inducție (completă) matematică Condiții necesare și suficiente. Logica predicatelor și algebra seturilor.
§ 25. Calcul predicat formalizat.
Concepte primare (limbaj de calcul al predicatelor formalizate). Sistemul de axiome ale calculului de predicate. reguli de retragere. Teoria inferenței formale.
Capitolul V. Teorii axiomatice informale.
§ 26. Metoda axiomatică în matematică şi teorii axiomatice.
Conceptul de teorie axiomatică. Cum apar teoriile axiomatice. Exemple de teorii axiomatice. Interpretări și modele ale teoriei axiomatice.
§ 27. Proprietăţile teoriilor axiomatice.
Consecvență. Categoric. Independenta sistemului de axiome. Completitudine.
Capitolul VI. Teorii axiomatice formale.
§ 28. Despre teoriile axiomatice formale.
Despre istoria ideii unei teorii axiomatice formale. Conceptul de teorie axiomatică formală. Limbaj și metalimbaj, teoreme și metateoreme ale teoriei formale. Interpretări și modele ale teoriei formale. ieșire semantică. Metamatematică (proprietăți ale teoriilor axiomatice formale). Calcul propozițional formalizat ca teorie axiomatică formală Formalizarea teoriei silogismelor aristotelice.
§ 29. Proprietăţi ale calculului predicatului formalizat.
Justificarea axiomatizării.Consistența calculului predicat formalizat. Teorema lui Gödel privind existența unui model. Completitudinea și adecvarea calculului predicatului formalizat. Incompletitudinea calculului predicatului formalizat în sens absolut și în sens restrâns Teorema compactității.
§ 30. Teorii formale de ordinul întâi.
Teorii de ordinul întâi cu egalitate. Despre teoriile formale de mulțimi. Despre aritmetica formală. Despre teoriile formale ale sistemelor de numere.Despre geometria formală. Despre analiza matematică formală. Vedere generală asupra procesului de formalizare a teoriei matematice Despre limitele metodei axiomatice, metoda formalizării și logica.
Capitolul VII. Elemente ale teoriei algoritmilor.
§31. Înțelegerea intuitivă a algoritmilor.
Algoritmi din jurul nostru. O noțiune informală a unui algoritm. Necesitatea de a clarifica conceptul de algoritm.
§ 32. Maşini Turing.
Definiția unei mașini Turing.Aplicarea mașinilor Turing la cuvinte. Proiectarea mașinii Turing. Funcții Turing-calculabile. Calculabilitatea corectă a funcțiilor pe o mașină Turing. Compoziția mașinilor Turing. teza lui Turing (o presupunere de bază în teoria algoritmilor). Mașini Turing și calculatoare electronice moderne.
§ 33. Funcţii recursive.
Originea funcțiilor recursive. Concepte de bază ale teoriei funcțiilor recursive și teza lui Church. Funcții recursive primitive. Recursivitatea primitivă a predicatelor. Calculabilitatea Turing a funcțiilor recursive primitive. Funcții Ackerman. operator de minimizare. Funcții recursive generale și parțial recursive. Calculabilitatea Turing a funcțiilor parțial recursive. Recursivitatea parțială a funcțiilor Turing-computable.
§34. Algoritmi Markov normali.
înlocuiri de Markov. Algoritmi normali și aplicarea lor la cuvinte. Funcții în mod normal calculabile și principiul de normalizare Markov. Coincidența clasei tuturor funcțiilor calculabile în mod normal cu clasa tuturor funcțiilor calculabile Turing. Echivalența diferitelor teorii ale algoritmilor.
§ 35. Decidabilitatea și enumerabilitatea mulțimilor.
§ 36. Probleme algoritmice nerezolvabile.
Algoritm de numerotare. Numerotarea mașinii Turing. Existența funcțiilor Turing necalculabile. Probleme de recunoaștere a autoaplicabilității și aplicabilității. Probleme nerezolvabile din punct de vedere algoritmic în teoria generală a algoritmilor. Teorema lui Rice. Alte exemple de indecizibilitate algoritmică.
§ 37. Teorema lui Godel despre incompletitudinea aritmeticii formale.
Teorii axiomatice formale și numere naturale. Aritmetica formală și proprietățile ei. Teorema de incompletitudine a lui Gödel. Gödel și rolul său în logica matematică a secolului al XX-lea. .
Capitolul VIII. Logica matematica si calculatoare, informatica, inteligenta artificiala.
* § 38. Logica matematică și software de calculator.
Teoria algoritmilor și logica matematică este baza fundamentală a programării. Descrierea programelor de calculator folosind logica matematică. Descrierea programării și analiza conceptelor acesteia folosind logica matematică. Verificarea (dovada corectitudinii) a programelor folosind logica matematică.
§ 39. Aplicarea calculatoarelor pentru demonstrarea teoremelor logicii matematice.
Programul „Logic-teoretician” și programele apropiate acestuia. Metoda de rezoluție pentru demonstrarea teoremelor în calculul propozițional și calculul predicatelor.
§ 40. De la logica matematică la programarea logică.
Apariția limbajului PROLOG și dezvoltarea acestuia. Caracteristici generale ale limbajului PROLOG. Scurtă descriere a limbajului PROLOG și exemple. Sfere de aplicare a limbajului PROLOG.
§41. Logica matematica si informatica.
Conceptul general al bazei de date. Baza de date relațională și logica de interogare în ea.
§ 42. Logica matematică și sisteme de inteligență artificială Istoria dezvoltării și subiectul inteligenței artificiale ca știință. Reprezentarea cunoștințelor în sistemele de inteligență artificială. Sistem expert. Limbajul PROLOG în sistemele de inteligență artificială. Poate o mașină să gândească.
Concluzie: Este logica omnipotentă în cunoaşterea legilor gândirii?
Bibliografie.

Logica si intuitia.
Activitatea mentală umană este un proces complex și cu mai multe fațete care are loc atât la nivel conștient, cât și la nivel inconștient (subconștient). Acesta este cel mai înalt nivel de cunoaștere umană, capacitatea de a reflecta în mod adecvat obiectele și fenomenele realității, adică. la aflarea adevărului.

Logica și intuiția sunt două proprietăți opuse și indisolubil legate ale gândirii umane. Gândirea logică (deductivă) diferă prin aceea că duce întotdeauna la o concluzie adevărată din premise adevărate, fără a se baza pe experiență, intuiție și alți factori externi. Intuiția (din latinescul intuitio - „privind îndeaproape”) este capacitatea de a înțelege adevărul prin observarea directă a acestuia, fără fundamentare, cu ajutorul unei dovezi logic riguroase. Astfel, intuiția este un fel de antipod, un contrabalansat la logica și rigoarea.

Partea logică a procesului de gândire are loc la nivelul conștiinței, partea intuitivă - la nivel subconștient.
Dezvoltarea științei și mai ales a matematicii este de neconceput fără intuiție. Există două tipuri de intuiție în cunoașterea științifică1: intuiția-judecata și intuiția-ghicirea. Intuiția-judecata (sau intuiția-judecata filozofică) se caracterizează prin faptul că în acest caz percepția directă a adevărului, legătura obiectivă a lucrurilor se realizează nu numai fără o demonstrație riguroasă din punct de vedere logic, dar o astfel de dovadă nu există pentru acest adevăr și nu poate exista în principiu. Intuiția-judecata se realizează ca un singur act holistic sintetic (o singură dată) de natură generalizantă. Această natură a afirmațiilor nedemonstrabile din punct de vedere logic o au tezele lui Turing, Church și Markov considerate în teoria algoritmilor.

Descărcați gratuit cărți electronice într-un format convenabil, vizionați și citiți:
Descarcă cartea Logica matematică și teoria algoritmilor, Igoshin VI, 2008 - fileskachat.com, descărcare rapidă și gratuită.

11.1. Conceptul de algoritm și teoria algoritmilor

Intuitiv, un algoritm este înțeles ca procesul de rezolvare secvențială a unei probleme care se desfășoară în timp discret, astfel încât în ​​fiecare moment următor de timp, sistemul de obiecte al algoritmului să fie obținut conform unei anumite legi din sistemul de obiecte care erau disponibile. în momentul anterior de timp. Intuitiv pentru că, strict vorbind, conceptul de algoritm este înrudit cu conceptul de mulțime, care este indefinibil.

În conformitate cu GOST 19781-74 „Mașini de calcul. Software. Termeni și definiții" algoritm este o prescripție exactă care definește procesul de calcul care duce de la datele inițiale variabile la rezultatul dorit. Aceasta presupune prezența unui executor de algoritm - un obiect care „știe” să efectueze aceste acțiuni.

Cuvântul „algoritm” se presupune că provine de la numele matematicianului din Asia Centrală (uzbek) din secolul al XIII-lea Al Khorezmi (Abu Abdallah Muhammad ibn Musa al Khorezmi al Medjusi) - „Algorithmi” în transcriere latină, care pentru prima dată a formulat regulile (procedura) pentru efectuarea a patru operații aritmetice în sistem numeric zecimal.

Atâta timp cât calculele erau simple, nu era nevoie specială de algoritmi. Când a fost nevoie de mai multe proceduri pas cu pas, atunci a apărut teoria algoritmilor. Dar cu o complicație și mai mare a sarcinilor, s-a dovedit că unele dintre ele nu pot fi rezolvate algoritmic. Astfel, de exemplu, sunt multe sarcini rezolvate de „calculatorul de bord” al unei persoane - creierul. Rezolvarea unor astfel de probleme se bazează pe alte principii - aceste principii sunt folosite de o nouă știință - neuromatematica și mijloacele tehnice corespunzătoare - neurocalculatoarele. În acest caz, se aplică procesele de învățare, încercare și eroare – adică ceea ce facem în prezent.

Calitatea unui algoritm este determinată de proprietățile (caracteristicile) acestuia. Principalele proprietăți ale algoritmului sunt:

1. caracter de masă. Se presupune că algoritmul poate fi potrivit pentru rezolvarea tuturor problemelor de acest tip. De exemplu, un algoritm pentru rezolvarea unui sistem de ecuații algebrice liniare ar trebui să fie aplicabil unui sistem format dintr-un număr arbitrar de ecuații.

2. Eficienţă. Această proprietate înseamnă că algoritmul trebuie să conducă la un rezultat într-un număr finit de pași.

3. Certitudine. Instrucțiunile incluse în algoritm trebuie să fie precise și ușor de înțeles. Această caracteristică asigură unicitatea rezultatului procesului de calcul pentru datele inițiale date.

4. discretie. Această proprietate înseamnă că procesul descris de algoritm și algoritmul însuși pot fi împărțite în etape elementare separate, posibilitatea căreia utilizatorul o poate efectua pe un computer este fără îndoială.

Astăzi, „mileniul digital” este în curte și s-ar putea să ai impresia că orice sarcină este supusă algoritmilor. Se pare că multe probleme nu pot fi rezolvate algoritmic. Acestea sunt așa-numitele probleme nerezolvabile din punct de vedere algoritmic.

Pentru a demonstra solubilitatea sau insolubilitatea algoritmică a problemelor, sunt necesare mijloace matematice riguroase și precise. La mijlocul anilor '30 ai secolului trecut, s-au încercat formalizarea conceptului de algoritm și s-au propus diverse modele de algoritmi: funcții recursive; „mașini” - Turing, Post; algoritmi Markov normali.

Ulterior, s-a constatat că acestea și alte modele sunt echivalente în sensul că clasele de probleme pe care le rezolvă coincid. Acest fapt se numește teza Bisericii. Acum acest lucru este în general acceptat. Definiția formală a conceptului de algoritm a creat premisele pentru dezvoltarea teoriei unui algoritm chiar înainte de dezvoltarea primelor calculatoare. Progresul tehnologiei informatice a stimulat dezvoltarea în continuare a teoriei algoritmilor. Pe lângă stabilirea solubilității algoritmice a problemelor, teoria algoritmilor se ocupă și de estimarea complexității algoritmilor în ceea ce privește numărul de pași (complexitatea timpului) și memoria necesară (complexitatea spațiului), și dezvoltă și algoritmi eficienți în acest sens.

Pentru implementarea unor algoritmi, în baza oricăror ipoteze rezonabile din punct de vedere al fizicii cu privire la viteza de efectuare a pașilor elementari, poate dura mai mult timp decât, conform concepțiilor moderne, există Universul sau mai multe celule de memorie decât atomii care alcătuiesc planeta Pământ.

Prin urmare, o altă sarcină a teoriei algoritmilor este de a rezolva problema eliminării enumerării opțiunilor în algoritmii combinatori. Estimarea complexității algoritmilor și crearea așa-numiților algoritmi eficienți este una dintre cele mai importante sarcini ale teoriei algoritmilor moderne.