NA GRÉCIA ANTIGA
2ª Tentativa: Argumentos Lógicos:
1. Deus é Amor
2. Amor é Cego
3. Steve Wonder é Cego
CONCLUSÃO: Steve Wonder é Deus!
VERDADEIRO OU FALSO?
Ex. da Grécia Antiga - livro “Elementos” de Euclides:
• É possível desenhar um linha reta de um ponto a outro ponto
• É possível prolongar um segmento finito de reta indefinidamente em ambas as direções
• É possível descrever um círculo, dado um centro e um raio
AXIOMAS
Axioma: uma verdade evidente, aceita sem questionamentos
São “peças básicas” para construir verdades mais complexas
TEOREMAS
Teorema: uma verdade deduzida logicamente através de outras verdades
Na Grécia Antiga: ninguém sabia exatamente o que era “deduzir logicamente”
LÓGICA BOOLEANA (≈1847)
Deduções Lógicas = Fazer “contas” com lógica
Álgebra Comum: 2+(3*4)/5
• operadores: +, -, X, /
• operandos: números Álgebra Booleana: (V e F) ou ¬(V ou ¬ V)
• operadores: e, ou, não
• operandos: V, FConstruções com fundações sólidas e boa argamassa
EXEMPLO DE LÓGICA BOOLEANA
Exemplos:•“2 é par” é VERDADEIRO•“3 é par” é FALSO •“2 é par e 3 é par” é FALSO•“2 é par e 4 é par” é VERDADEIRO
Deduzindo verdades graaaaandes:
•“2 é par e 4 é par e 6 é par e 8 é par e 10 é par e 12 é par e 14 é par e 16 é par e 18 é par e 20 é par e22 é par e 24 é par e 26 é par . . .” é VERDADEIRO
LÓGICA DE PREDICADOS (≈1884)
Melhora a lógica booleana:
•Variáveis
•Quantificadores (“para todo”, “existe”)
Exemplo: “𝑝𝑝(𝑥𝑥) : 𝑥𝑥 é par”• 𝑝𝑝(2) é VERDADEIRO• 𝑝𝑝(3) é FALSO
Deduzindo verdades graaaaandes:
• “𝑝𝑝(𝑥𝑥), para todo 𝑥𝑥 = 2𝑘𝑘” é VERDADEIRO
Gottlob Frege
Mais fácil! Mais simples!Mais limpo!
TEORIA DOS CONJUNTOS (≈1870)
Georg Cantor
Estuda “coleções de objetos”:
• Objetos podem ser qualquer coisa
• Intersecção: 𝐴𝐴 ∩ 𝐵𝐵
• União: 𝐴𝐴 ∪ 𝐵𝐵
• Complemento: 𝐴𝐴
objetos = verdades e mentiras
a e b
a ou b
não a
PARADOXO DE RUSSELL (≈1901)
Livros autorreferentes: que contém referências a si mesmos
Christos Papadimitriou explica o paradoxo:
PARADOXO DE RUSSELL (≈1901)
Um pouco mais formal:
“o conjunto de todos os conjuntos que não se contêm a si próprios como membros”
E em “matematiquês”:
{𝐴𝐴 | 𝐴𝐴 ∉ 𝐴𝐴}
BERTRAND RUSSELL (1872 - 1970)
De acordo com Wikipedia:
Quem é: Filósofo, Lógico, Matemático, Historiador, Crítico Social e Ativista Político
O que fez: • Fundou a filosofia analítica• Pacifista nas 1ª e 2ª Guerras Mundiais, e
do Vietnam• Prêmio Nobel de Literatura por escrever
sobre liberdade de pensamento
Legado:• Influenciou lógica, matemática, teoria dos conjuntos, linguística, inteligência artificial,
ciências cognitivas, ciência da computação, filosofia da linguagem, epistemologia e metafísica
• Principia Mathematica• “um dos mais importantes livros em filosofia da matemática escritos da História”• “23º dos 100 mais importantes livros em inglês de não ficção do século XX”
PRINCIPIA MATHEMATICA (≈1912)
Russell (e seu amigo Whitehead) gastou 10 anos para resolver seu paradoxo
O resultado foi o livro “Principia Mathematica”:• Reescreveu toda a base da matemática• Objetivo: provar matematicamente qualquer coisa• Métodos complicados, mas bem fundamentados
Na página 379, eles provaram que 1+1=2, vejam:
NOVAS INDAGAÇÕES... (DÉCADA DE 1920)
Apesar do sucesso, Principia Mathematica levantou questões...
Existe um sistema lógico-formal que seja:
1. Consistente? (não leva a contradições)
2. Completo? (não permite verdades indemonstráveis)
3. Decidível? (existe passo-a-passo para decidir se uma verdade se segue dos axiomas ou não)
INCOMPLETUDE (≈1931)
Esse é John Von Neummann
A frase clássica de Von Neummann “Está tudo acabado” resume a essência da demonstração de Gödel:
• O Teorema da Incompletude significava o fim de um sonho de 2500 anos
INDECIDIBILIDADE (≈1936)
A questão da decidibilidade também teve uma resposta decepcionante...
Lembrando...
A Lógica é Decidível?Ou seja, existe um passo-a-passo para decidir se uma verdade se segue de axiomas ou não?
Alan Turing, em 1936, provou que a lógica era indecidível!
INDECIDIBILIDADE (≈1936)
O que Turing fez?
Formalizou matematicamente os conceitos de:
• “passo-a-passo”: algoritmo
• “verdade seguir-se de axiomas”: computação
Como Turing fez?
• Definiu um modelo matemático que executava algoritmos e realizava computação
• Provou que o Problema da Parada era indecidível
• O modelo ficou conhecido como Máquina de Turing
MÁQUINA DE TURING E COMPUTADORES
OK, agora sabemos que a lógica é limitada
MAS ideias como “algoritmos” e “computação” são interessantes!!!
Legal seria a máquina abstrata se tornar concreta...
ENIAC (1946): 1º dispositivo físico a adotar completamente as ideias da Máquina de Turing