Autor: Guts A. K.
Editora: O.: Heritage
Ano de publicação: 2003
Páginas: 108
ISBN 5-8239-0126-7
Leitura:
Download: matematicheskayalogika2003.djvu

FACULDADE DE CIÊNCIAS DA COMPUTAÇÃO DA UNIVERSIDADE ESTADUAL DE OMSK
CIBERNÉTICA
AK Culhões
Lógica matemática e teoria dos algoritmos
Omsk 2003
VVK 60 UDC 53:630.11
Guts A. K. Lógica matemática e teoria dos algoritmos: livro didático. -
Omsk: Publicação Patrimonial. Diálogo-Sibéria, 2003. - 108 p.
ISBN 5-8239-0126-7
O livro-texto é dedicado à apresentação dos fundamentos da lógica e teoria matemáticas
algoritmos. A base do manual são os resumos das palestras que foram lidas
alunos do segundo ano do departamento de ciência da computação de Omsk
Universidade Estadual em 2002.
Para alunos que estudam na especialidade 075200 - "Informática
segurança" e especialidade 220100 - "Computadores,
complexos, sistemas e redes".
ISBN 5-8239-0126-7
(c) Universidade Estadual de Omsk, 2003
Índice
Lógica 7
1 Lógica clássica 8
1.1. Lógica das proposições .............................. 8
1.1.1. Provérbios.............................. 8
1.1.2. Leis Básicas da Lógica .................................... 9
1.1.3. Paradoxo lógico de Russell ............... 10
1.1.4. Álgebra (lógica) de proposições ............... 11
1.1.5. Diagramas de escada ......................... 12
1.1.6. Fórmulas equivalentes ....................... 14
1.1.7. Álgebra Boole.............................. 15
1.1.8. Fórmulas verdadeiras e válidas ........... 15
1.1.9. O problema da solubilidade ................... 15
1.1.10. Consequência Lógica .............................. 16
1.1.11. Silogismos .............................. 17
1.2. Lógica de Predicados .............................. 17
1.2.1. Predicados e fórmulas ............... 18
1.2.2. Interpretações .............................. 19
1.2.3. Verdade e satisfatibilidade de fórmulas. modelos,
validade, consequência lógica........ 20
1.2.4. Gottlob Frege....................... 21
1.2.5. Funções do Skolem
e escolemização de fórmulas......................... 22
1.3. Método de resolução .............................. 25
1.3.1. Método de resoluções em lógica
enunciados.................................. 25
1.3.2. Método de resoluções em lógica
predicados.................................. 29
3
4
Índice
2 Teorias formais (cálculo) 31
2.1. Definição de teoria formal, ou cálculo. . 32
2.1.1. Prova. Coerência da teoria.
Completude da teoria .............................. 32
2.2. Cálculo proposicional .............................. 33
2.2.1. Linguagem e regras para a inferência do cálculo proposicional
............................................. 33
2.2.2. Um exemplo da prova do teorema............... 35
2.2.3. Completude e consistência
cálculo proposicional .............................. 36
2.3. Cálculo de predicados.............................. 37
2.3.1. Linguagem e regras de inferência do cálculo de predicados 37
2.3.2. Completude e consistência
cálculo de predicados .............................. 39
2.4. Aritmética formal .............................. 39
2.4.1. Teorias igualitárias .............................. 39
2.4.2. Linguagem e regras para a derivação da aritmética formal
.............................................. 39
2.4.3. Consistência do formalismo
aritmética. Teorema de Gentzen............... 40
2.4.4. Teorema da Incompletude de Gödel.............................. 41
2.4.5. Kurt Gödel......... 42
2.5. Derivação automática de teoremas .............................. 43
2.5.1. S.Yu. Maslov......................... 43
2.6. Programação Lógica .............................. 45
2.6.1. Programa lógico ....................... 46
2.6.2. Linguagens de programação lógica.... 49
3 Lógicas não clássicas 50
3.1. Lógica Intuicionista .............................. 50
3.2. Lógica difusa......................... 51
3.2.1. Subconjuntos difusos .............................. 51
3.2.2. Operações em fuzzy
subconjuntos .............................. 52
3.2.3. Propriedades do conjunto de fuzzy
subconjuntos......................... 53
3.2.4. Lógica Proposicional Fuzzy......................... 54
3.2.5. Diagramas de Escada Difusa ........... 56
3.3. Lógicas modais......................... 56
3.3.1. Tipos de modalidade .............................. 57
Índice
5
3.3.2. Cálculo 1 e T (Feis-von Wright) ........ 57
3.3.3. Cálculo S4, S5
e cálculo de Brouwer.............................. 58
3.3.4. Avaliação da Fórmula .............................. 59
3.3.5. Semântica de Kripke .............................. 60
3.3.6. Outras interpretações de modais
sinais ....................................... 62
3.4. Georg von Wright ................................... 62
3.5. Lógica Temporária .............................. 62
3.5.1. Lógica de temporização de Pryor.............................. 63
3.5.2. Lógica de Tempo de Lemmon......... 64
3.5.3. A lógica temporal de Von Wright ....................... 64
3.5.4. Aplicação de lógica de tempo
para a programação......................... 65
3.5.5. Pnueli Lógica Temporal .............................. 67
3.6. Lógicas algorítmicas .............................. 70
3.6.1. Princípios de construção
1 >

Agência Federal de Educação

UNIVERSIDADE ESTADUAL DE SISTEMAS DE CONTROLE E RÁDIO ELETRÔNICA DE TOMSK (TUSUR)

Departamento de Automação de Processamento de Informação

Eu aprovo:

Cabeça cafeteria AOI

Professor

Sim. Ekhlakov

"__" _____________2007

Diretrizes

para a realização de trabalhos práticos na disciplina

"Lógica Matemática e Teoria dos Algoritmos"

para estudantes de especialidade 230102 -

"Sistemas automatizados para processamento e controle de informações"

Desenvolvedores:

Arte. professor do departamento AOI

ENTÃO. Peremitina

Tomsk - 2007

Aula prática nº 1 "Fórmulas de Álgebra Proposicional" 3

Aula prática nº 2 "Transformações equivalentes de fórmulas de álgebra proposicional" 10

Aula prática nº 3 "Formas normais de fórmulas" 12

Aula prática nº 4 "Raciocínio lógico" 14

Aula prática nº 5 "Fórmulas da lógica de predicados" 18

Prática #6 Funções Booleanas 23

Prática #7 Funções Parcialmente Recursivas 28

Prática #8 Máquinas de Turing 34

Aula prática nº 1 "Fórmulas de Álgebra Proposicional"

A doutrina das proposições - a álgebra das proposições, ou a álgebra da lógica - é a teoria lógica mais simples. A noção atômica da álgebra proposicional é demonstração - uma sentença declarativa em relação à qual a afirmação sobre sua verdade ou falsidade faz sentido.

Um exemplo de uma afirmação verdadeira: "A terra gira em torno do sol." Um exemplo de uma declaração falsa: "3 > 5". Nem toda frase é uma declaração; as declarações não incluem frases interrogativas e exclamativas. A frase: “Mingau é um prato delicioso” não é uma afirmação, pois não pode haver consenso sobre se é verdade ou mentira. A frase "Há vida em Marte" deve ser considerada uma afirmação, pois objetivamente é verdadeira ou falsa, embora ninguém ainda saiba qual.

Como o assunto do estudo da lógica é apenas os valores de verdade das proposições, as designações de letras A, B, ... ou X, Y ... são introduzidas para elas.

Cada afirmação é considerada verdadeira ou falsa. Para abreviar, escreveremos 1 em vez do valor verdadeiro e 0 em vez do valor falso. Por exemplo, X= "A Terra gira em torno do Sol" e Y= "3 > 5", e X=1 e Y= 0. A afirmação não pode ser verdadeira e falsa.

As declarações podem ser simples ou compostas. As afirmações "a terra gira em torno do sol" e "3 > 5" são simples. Declarações compostas são formadas a partir de simples com a ajuda de conectivos de linguagem natural (russa) NOT, AND, OR, IF-THEN, THEN-AND-ONLY-THEN. Ao usar a notação alfabética para declarações, esses conectivos são substituídos por símbolos matemáticos especiais, que podem ser considerados símbolos de operações lógicas.

Abaixo, na tabela 1, existem variantes de símbolos para designar conectivos e os nomes das operações lógicas correspondentes.

Negação (inversão) declarações Xé uma afirmação que é verdadeira se e somente se X falso (indicado ou , lê-se “não X” ou “não é verdade que X”).

conjunção
de duas proposições é chamada uma proposição que é verdadeira se e somente se ambas as proposições são verdadeiras X e S. Essa operação lógica corresponde à conexão de declarações com a união "e".

disjunção
duas frases X e S Diz-se que uma afirmação é falsa se e somente se ambas as afirmações X e S falso. No discurso coloquial, essa operação lógica corresponde à união "ou" (não exclusiva "ou").

implicação duas frases X e Sé uma afirmação falsa se e somente se X verdade, e S- falso (indicado
; lê " X implica S", "E se X, então S"). Os operandos desta operação têm nomes especiais: X- pacote, S- conclusão.

Equivalência duas frases X e Sé chamado de uma afirmação que é verdadeira se e somente se os valores de verdade X e S são iguais (símbolo:
).

Tabela 1. Operações lógicas

Os operandos das operações lógicas podem assumir apenas dois valores: 1 ou 0. Portanto, cada operação lógica , &, , ,  pode ser facilmente especificada usando a tabela, indicando o valor do resultado da operação dependendo dos valores dos operandos. Tal tabela é chamada tabela verdade (Mesa 2).

Tabela 2. Tabela verdade de operações lógicas

Com a ajuda das operações lógicas definidas acima, é possível construir a partir de proposições simples fórmulas de lógica proposicional representando diferentes declarações compostas. O significado lógico de uma declaração composta depende da estrutura da declaração, expressa pela fórmula, e dos valores lógicos das declarações elementares que a formam.

Para o estudo sistemático de fórmulas que expressam declarações, declarações variáveis ​​são introduzidas P, P 1 , P 2 , ..., P N, tomando valores do conjunto (0, 1).

Fórmula lógica proposicional F (P 1 , P 2 ,..., P N) é chamado de tautologia ou identicamente verdadeiro se seu valor para quaisquer valores P 1 , P 2 ,..., P Né 1 (verdadeiro). Fórmulas que são avaliadas como verdadeiras para pelo menos um conjunto de listas de variáveis ​​são chamadas factível . Fórmulas que assumem o valor “falso” para quaisquer valores das variáveis ​​são chamadas contradições (identicamente falso, impossível).

O livro proposto (2ª ed., estereótipo) forma a base de um conjunto para o curso de lógica matemática e teoria dos algoritmos, que também inclui uma coleção de problemas (Igoshin V.I. Tarefas e exercícios de lógica matemática e teoria dos algoritmos) .

Os fundamentos da teoria são descritos em detalhes, as direções de penetração da lógica nos fundamentos da álgebra, análise, geometria são mostradas, o material do curso de matemática escolar é usado para sua análise lógica, a relação da lógica matemática com computadores, informática e sistemas de inteligência artificial.

Introdução. Lógica matemática no sistema de educação moderna.
Lógica e intuição. Lógica lógica tradicional e matemática. Um pouco de história. Lógica matemática - lógica ou matemática? Lógica matemática no ensino de matemática. Lógica matemática e computadores modernos.
Capítulo I. Álgebra de afirmações.
§ 1. Demonstrações e operações sobre eles.
O conceito de enunciado. Negação da declaração. Conjunção de duas frases. Disjunção de duas afirmações. Implicação de duas declarações. Equivalência de duas afirmações. Uniões da linguagem e operações lógicas (linguagem e lógica). Visão geral das operações lógicas.
§2. Fórmulas de álgebra proposicional.
Construção de frases complexas. O conceito de uma fórmula de álgebra proposicional. O significado lógico de uma instrução composta. Compilação de tabelas verdade para fórmulas. Classificação de fórmulas de álgebra proposicional. Pensamento e lógica matemática
§ 3. Tautologias da Álgebra Proposicional.
Sobre o significado das tautologias. tautologias básicas. Regras básicas para obter uma tautologia.
§ 4. Equivalência lógica de fórmulas.
O conceito de equivalência de fórmulas. Sinal de equivalência de fórmulas. Exemplos de fórmulas equivalentes. Transformações equivalentes de fórmulas. Equivalências em lógica e identidades em álgebra.
§ 5. Formas Normais para Fórmulas de Álgebra Proposicional.
O conceito de formas normais. Formas normais perfeitas. Representação de fórmulas de álgebra proposicional por formas normais disjuntivas perfeitas (CDN). Representação de fórmulas de álgebra proposicional por formas normais conjuntivas perfeitas (SKN). Duas maneiras de reduzir uma fórmula de álgebra proposicional à forma normal perfeita
§ 6. Seguimento lógico de fórmulas.
O conceito de uma consequência lógica. Sinais de uma consequência lógica. Duas propriedades de consequência lógica. Seguimento e equivalência de fórmulas. Regras de raciocínio lógico. Outra maneira de verificar o seguinte lógico. Encontrar consequências a partir dessas premissas. Encontrar premissas para esta investigação.
§ 7. Aplicação da álgebra proposicional à prática lógico-matemática.
Teoremas diretos e inversos. Condições necessárias e suficientes. Oposto e inverso do teorema oposto. A lei da contraposição. Modificação da estrutura do teorema matemático. Métodos de prova de teoremas matemáticos. Raciocínio dedutivo e indutivo. Raciocínio dedutivo correto e incorreto. Resolvendo problemas lógicos. O princípio da disjunção completa. Uma generalização do princípio da disjunção completa.
Capítulo II. Funções booleanas.
§oito. Conjuntos, relações, funções.
O conceito de conjunto. Inclusão e igualdade de conjuntos. Operações em conjuntos. Relações binárias e funções. O conceito de um relacionamento lar.
§ 9. Funções booleanas de um e dois argumentos.
Origem das funções booleanas. Funções booleanas de um argumento. Funções booleanas de dois argumentos. Propriedades de disjunção, conjunção e negação. Propriedades de equivalência, implicação e negação. Expressando algumas funções booleanas em termos de outras
§ 10. Funções booleanas de n argumentos.
O conceito de uma função booleana. O número de funções booleanas. Expressão de funções booleanas por conjunção, disjunção e negação. Funções booleanas e fórmulas da álgebra proposicional. Formas normais de funções booleanas.
§ 11. Sistemas de funções booleanas.
Sistemas completos de funções booleanas. Classes especiais de funções booleanas. Teorema de Post sobre a completude de um sistema de funções booleanas
§ 12. Aplicação de funções booleanas a circuitos de contato relé.
Ideia de aplicação. Duas tarefas principais da teoria de circuitos de contato de relé.
§ 13. Circuitos de contato relé em computadores.
Meio somador binário. Somador binário de bit único. codificador e decodificador.
§ 14. Sobre algumas outras aplicações da teoria das funções booleanas.
Diagnóstico (reconhecimento) de doenças. Reconhecimento de padrões.
Capítulo III. Cálculo proposicional formalizado.
§ 15. O sistema de axiomas e a teoria da inferência formal.
O início da teoria proposicional axiomática: conceitos iniciais, sistema de axiomas, regra de inferência. O conceito de inferência e suas propriedades. O teorema da dedução e suas consequências. Aplicação do teorema da dedução. Regras de inferência derivadas
§ 16. Completude e outras propriedades do cálculo proposicional formalizado
Provabilidade de uma fórmula e sua verdade idêntica (sintaxe e semântica). Lema da Derivabilidade. Completude do cálculo proposicional formalizado. O teorema da adequação. Consistência do cálculo proposicional formalizado. Decidibilidade do cálculo proposicional formalizado
§ 17. Independência do sistema de axiomas do cálculo proposicional formalizado.
O conceito de independência. Independência do axioma (A1). Independência do axioma (A2). Independência de axiomas (A3). Independência do sistema de axiomas
Capítulo IV. Lógica de predicado.
§ 18. Conceitos básicos relacionados a predicados.
O conceito de predicado. Classificação de predicados. O conjunto verdade do predicado. Equivalência e seguintes predicados
§ 19. Operações lógicas sobre predicados.
Negação de predicado. Conjunção de dois predicados. Design para ir para a página dicat. Propriedades de negação, conjunção e disjunção. Implicação e equivalência de dois predicados.
§ 20. Operações de quantificador em predicados.
Quantificador geral. Quantificador de existência. Quantificadores numéricos. Quantificadores limitados. Quadrado lógico
§ 21. Fórmulas de lógica de predicados.
O conceito de uma fórmula lógica de predicados. Classificação de fórmulas lógicas de predicados. Tautologias da Lógica de Predicados
§ 22. Transformações equivalentes de fórmulas e consequência lógica de fórmulas de lógica de predicados
O conceito de equivalência de fórmulas. Forma reduzida para fórmulas de lógica de predicados. Prenex forma normal para fórmulas lógicas de predicados. Seguimento lógico de fórmulas lógicas de predicados
§ 23. Resolução de problemas de validade e satisfatibilidade de fórmulas.
Declaração do problema e sua insolubilidade em geral. Solução do problema para fórmulas em conjuntos finitos. Um exemplo de uma fórmula que é viável em um conjunto infinito e não viável em qualquer conjunto finito. Problema de resolução de satisfatibilidade: influência da cardinalidade do conjunto e da estrutura da fórmula. Resolvendo o problema para fórmulas contendo apenas variáveis ​​de predicado de um lugar. O problema de resolver a validade e a cardinalidade do conjunto no qual a fórmula é considerada. Resolução de problemas para fórmulas V e 3 fórmulas
§ 24. Aplicação da lógica de predicados à prática lógico-matemática.
Gravação na linguagem de predicados lógicos de várias frases. Comparação entre lógica de predicados e lógica proposicional. A estrutura dos teoremas matemáticos. Métodos de raciocínio: a silogística aristotélica. A silogística aristotélica e a lógica dos predicados. Interpretação da teoria dos conjuntos da silogística aristotélica. Sobre outros métodos de raciocínio. O princípio da disjunção completa em forma de predicado. Método de indução matemática (completa) Condições necessárias e suficientes. Lógica de predicados e álgebra de conjuntos.
§ 25. Cálculo de predicados formalizado.
Conceitos primários (linguagem do cálculo de predicados formalizado). O sistema de axiomas de cálculo de predicados. regras de retirada. Teoria da inferência formal.
Capítulo V. Teorias axiomáticas informais.
§ 26. Método axiomático em matemática e teorias axiomáticas.
O conceito de teoria axiomática. Como surgem as teorias axiomáticas. Exemplos de teorias axiomáticas. Interpretações e modelos da teoria axiomática.
§ 27. Propriedades das teorias axiomáticas.
Consistência. Categórico. Independência do sistema de axiomas. Completude.
Capítulo VI. Teorias axiomáticas formais.
§ 28. Sobre teorias axiomáticas formais.
Sobre a história da ideia de uma teoria axiomática formal. O conceito de teoria axiomática formal. Linguagem e metalinguagem, teoremas e metateoremas da teoria formal. Interpretações e modelos da teoria formal. saída semântica. Metamatemática (propriedades das teorias axiomáticas formais). Cálculo proposicional formalizado como teoria axiomática formal.Formalização da teoria dos silogismos aristotélicos.
§ 29. Propriedades do cálculo de predicados formalizado.
Justificativa da axiomatização Consistência do cálculo de predicados formalizado. Teorema de Gödel sobre a existência de um modelo. Completude e adequação do cálculo de predicados formalizado. Incompletude do cálculo de predicados formalizado nos sentidos absoluto e estrito Teorema da compacidade.
§ 30. Teorias formais de primeira ordem.
Teorias de primeira ordem com igualdade. Sobre teorias formais dos conjuntos. Na aritmética formal. Sobre teorias formais de sistemas numéricos Sobre geometria formal. Sobre a análise matemática formal. Visão geral sobre o processo de formalização da teoria matemática Sobre os limites do método axiomático, o método de formalização e a lógica.
Capítulo VII. Elementos da teoria dos algoritmos.
§31. Compreensão intuitiva de algoritmos.
Algoritmos ao nosso redor. Uma noção informal de um algoritmo. A necessidade de esclarecer o conceito de um algoritmo.
§ 32. Máquinas de Turing.
Definição de máquina de Turing Aplicação das máquinas de Turing às palavras. Projeto de máquina de Turing. Funções Turing-computáveis. Computabilidade correta de funções em uma máquina de Turing. Composição de máquinas de Turing. A tese de Turing (uma conjectura básica na teoria dos algoritmos). Máquinas de Turing e computadores eletrônicos modernos.
§ 33. Funções recursivas.
Origem das funções recursivas. Conceitos básicos da teoria das funções recursivas e tese de Church. Funções recursivas primitivas. Recursividade primitiva de predicados. Computabilidade de Turing de funções recursivas primitivas. Funções de Ackerman. operador de minimização. Funções recursivas gerais e parcialmente recursivas. Computabilidade de Turing de funções parcialmente recursivas. Recursividade parcial de funções computáveis ​​por Turing.
§34. Algoritmos normais de Markov.
Substituições de Markov. Algoritmos normais e sua aplicação às palavras. Funções normalmente computáveis ​​e o princípio de normalização de Markov. Coincidência da classe de todas as funções normalmente computáveis ​​com a classe de todas as funções de Turing computáveis. Equivalência de várias teorias de algoritmos.
§ 35. Decidibilidade e enumerabilidade de conjuntos.
§ 36. Problemas algorítmicos insolúveis.
Numeração do algoritmo. Numeração da máquina de Turing. Existência de funções Turing não computáveis. Problemas de reconhecimento de auto-aplicabilidade e aplicabilidade. Problemas algoritmicamente insolúveis na teoria geral dos algoritmos. Teorema de Rice. Outros exemplos de indecidibilidade algorítmica.
§ 37. Teorema de Gõdel sobre a incompletude da aritmética formal.
Teorias axiomáticas formais e números naturais. Aritmética formal e suas propriedades. Teorema da incompletude de Gödel. Gödel e seu papel na lógica matemática do século XX. .
Capítulo VIII. Lógica matemática e computadores, informática, inteligência artificial.
* § 38. Lógica matemática e software de computador.
A teoria dos algoritmos e da lógica matemática é a base fundamental da programação. Descrição de programas de computador usando lógica matemática. Descrição da programação e análise dos seus conceitos utilizando lógica matemática. Verificação (prova de correção) de programas usando lógica matemática.
§ 39. Aplicação de computadores para prova de teoremas de lógica matemática.
O programa "Teórico-lógico" e programas próximos a ele. Método de resolução para provar teoremas em cálculo proposicional e cálculo de predicados.
§ 40. Da lógica matemática à programação lógica.
O surgimento da linguagem PROLOG e seu desenvolvimento. Características gerais da linguagem PROLOG. Breve descrição da linguagem PROLOG e exemplos. Esferas de aplicação da linguagem PROLOG.
§41. Lógica matemática e informática.
Conceito geral do banco de dados. Banco de dados relacional e lógica de consulta nele.
§ 42. Lógica matemática e sistemas de inteligência artificial A história do desenvolvimento e o tema da inteligência artificial como ciência. Representação do conhecimento em sistemas de inteligência artificial. Sistemas especializados. Linguagem PROLOG em sistemas de inteligência artificial. Uma máquina pode pensar.
Conclusão: A lógica é onipotente no conhecimento das leis do pensamento?
Bibliografia.

Lógica e intuição.
A atividade mental humana é um processo complexo e multifacetado que ocorre tanto no nível consciente quanto no inconsciente (subconsciente). Este é o nível mais alto do conhecimento humano, a capacidade de refletir adequadamente objetos e fenômenos da realidade, ou seja, para encontrar a verdade.

Lógica e intuição são duas propriedades opostas e inextricavelmente ligadas do pensamento humano. O pensamento lógico (dedutivo) difere porque sempre leva a uma conclusão verdadeira a partir de premissas verdadeiras, sem depender da experiência, intuição e outros fatores externos. Intuição (do latim intuitio - “olhar de perto”) é a capacidade de compreender a verdade pela observação direta dela sem fundamentação com a ajuda de provas logicamente rigorosas. Assim, a intuição é uma espécie de antípoda, um contrapeso à lógica e ao rigor.

A parte lógica do processo de pensamento ocorre no nível da consciência, a parte intuitiva - no nível subconsciente.
O desenvolvimento da ciência e especialmente da matemática é impensável sem intuição. Existem dois tipos de intuição no conhecimento científico1: intuição-julgamento e intuição-suposição. A intuição-julgamento (ou intuição-juízo filosófico) é caracterizada pelo fato de que, neste caso, a percepção direta da verdade, a conexão objetiva das coisas, é realizada não apenas sem prova logicamente rigorosa, mas tal prova não existe para essa verdade e não pode existir em princípio. A intuição-julgamento é realizado como um ato holístico sintético único (uma vez) de natureza generalizante. É essa natureza de afirmações logicamente improváveis ​​que as teses de Turing, Church e Markov consideradas na teoria dos algoritmos têm.

Faça o download gratuito do e-book em um formato conveniente, assista e leia:
Baixe o livro Lógica Matemática e Teoria dos Algoritmos, Igoshin VI, 2008 - fileskachat.com, download rápido e gratuito.

11.1. O conceito de algoritmo e a teoria dos algoritmos

Intuitivamente, um algoritmo é entendido como o processo de resolver sequencialmente um problema que prossegue em tempo discreto de modo que a cada momento seguinte, o sistema de objetos do algoritmo seja obtido de acordo com uma determinada lei do sistema de objetos que estavam disponíveis. no momento anterior. Intuitivo porque, estritamente falando, o conceito de algoritmo é semelhante ao conceito de conjunto, que é indefinível.

De acordo com GOST 19781-74 “Máquinas de computação. Programas. Termos e definições" algoritmoé uma prescrição exata que define o processo computacional que leva dos dados iniciais variáveis ​​ao resultado desejado. Isso pressupõe a presença de um executor de algoritmo - um objeto que "sabe" realizar essas ações.

A palavra "algoritmo" deve vir do nome do matemático da Ásia Central (Uzbeque) do século XIII Al Khorezmi (Abu Abdallah Muhammad ibn Musa al Khorezmi al Medjusi) - "Algoritmo" na transcrição latina, que pela primeira vez formulou as regras (procedimento) para realizar quatro operações aritméticas no sistema de numeração decimal.

Desde que os cálculos fossem simples, não havia necessidade especial de algoritmos. Quando houve a necessidade de vários procedimentos passo a passo, surgiu a teoria dos algoritmos. Mas com a complicação ainda maior das tarefas, descobriu-se que algumas delas não podem ser resolvidas algoritmicamente. Tais, por exemplo, são muitas tarefas resolvidas pelo "computador de bordo" de uma pessoa - o cérebro. A solução de tais problemas é baseada em outros princípios - esses princípios são usados ​​por uma nova ciência - neuromatemática e os meios técnicos correspondentes - neurocomputadores. Nesse caso, são aplicados os processos de aprendizado, tentativa e erro - ou seja, o que estamos fazendo atualmente.

A qualidade de um algoritmo é determinada por suas propriedades (características). As principais propriedades do algoritmo são:

1. personagem de massa. Assume-se que o algoritmo pode ser adequado para resolver todos os problemas deste tipo. Por exemplo, um algoritmo para resolver um sistema de equações algébricas lineares deve ser aplicável a um sistema que consiste em um número arbitrário de equações.

2. Eficiência. Esta propriedade significa que o algoritmo deve levar a um resultado em um número finito de passos.

3. Certeza. As instruções incluídas no algoritmo devem ser precisas e compreensíveis. Essa característica garante a unicidade do resultado do processo computacional para dados iniciais dados.

4. discrição. Essa propriedade significa que o processo descrito pelo algoritmo e o próprio algoritmo podem ser divididos em etapas elementares separadas, cuja possibilidade o usuário pode realizar em um computador é inquestionável.

Hoje, o “milênio digital” está chegando, e você pode ter a impressão de que qualquer tarefa está sujeita a algoritmos. Acontece que muitos problemas não podem ser resolvidos algoritmicamente. Estes são os chamados problemas algorítmicos insolúveis.

Para provar a solubilidade algorítmica ou insolubilidade de problemas, são necessários meios matematicamente rigorosos e precisos. Em meados dos anos 30 do século passado, foram feitas tentativas para formalizar o conceito de algoritmo e vários modelos de algoritmos foram propostos: funções recursivas; "máquinas" - Turing, Post; algoritmos normais de Markov.

Posteriormente, verificou-se que estes e outros modelos são equivalentes no sentido de que as classes de problemas que resolvem coincidem. Esse fato é chamado de tese de Church. Agora, isso é geralmente aceito. A definição formal do conceito de algoritmo criou os pré-requisitos para o desenvolvimento da teoria de um algoritmo antes mesmo do desenvolvimento dos primeiros computadores. O progresso da tecnologia de computador estimulou o desenvolvimento da teoria dos algoritmos. Além de estabelecer a solubilidade algorítmica dos problemas, a teoria dos algoritmos também trata da estimativa da complexidade dos algoritmos em termos do número de passos (complexidade do tempo) e da memória necessária (complexidade do espaço), e também desenvolve algoritmos eficientes em este sentido.

Para a implementação de alguns algoritmos, sob quaisquer suposições razoáveis ​​do ponto de vista da física sobre a velocidade de execução de etapas elementares, pode levar mais tempo do que, segundo visões modernas, o Universo existe, ou mais células de memória do que os átomos que compõem o planeta Terra.

Portanto, outra tarefa da teoria dos algoritmos é resolver o problema de eliminar a enumeração de opções em algoritmos combinatórios. Estimar a complexidade dos algoritmos e criar os chamados algoritmos eficientes é uma das tarefas mais importantes da moderna teoria dos algoritmos.