REVISÃO PROVA 2
Monitoria de Lógica
TEOREMA DE HERBRAND

Seja S um conjunto de cláusulas. S é
INSATISFATÍVEL se e somente se EXISTE
UM CONJUNTO FINITO DE INSTÂCIAS
BÁSICAS das cláusulas de S que é
INSATISFATÍVEL.
TEOREMA DA COMPACCIDADE

Seja G um conjunto de fórmulas da lógica
proposicional. G é SATISFATÍVEL se e somente
se TODO SUBCONJUNTO FINITO DE G É
SATISFATÍVEL. O teorema é válido mesmo
que G seja infinito.
TEOREMA DE LÖWENHEIM-SKOLEM

Para toda assinatura σ, toda σ-estrutura infinita
M e todo cardinal infinito k > |σ| existe uma σestrutura N tal que |N| = k e
Se k < |M| então N é uma subestrutura de M
 Se k > |M| então N é uma extensão de M

SISTEMAS AXIOMÁTICOS

É um conjunto qualquer de axiomas, que podem
ser usados, todos ou só alguns, para a derivação
lógica de teoremas.
AXIOMAS DE EUCLIDES





Axioma I: Pode-se traçar uma única reta ligando
quaisquer dois pontos.
Axioma II: Pode-se continuar (de uma maneira única)
qualquer reta finita continuamente em uma reta.
Axioma III: Pode-se traçar um círculo com qualquer
centro e com qualquer raio.
Axioma IV: Todos os ângulos retos são iguais.
Axioma V: Se uma reta, ao cortar outras duas, forma
ângulos internos, no mesmo lado, cuja soma é menor
do que dois ângulos retos, então estas duas retas
encontrar-se-ão no lado onde estão os ângulos cuja
soma é menor do que dois ângulos retos.
AXIOMAS DE HILBERT
Termos Indefinidos
 Axiomas de Incidência
 Axiomas de Ordem
 Axiomas de Congruência
 Axioma das Paralelas
 Axiomas de Continuidade
 Axiomas sobre Planos

FUNÇÕES RECURSIVAS

Motivação

Limites da computação


O que é possível resolver com um computador?
Todos os problemas, mais cedo ou mais tarde, se renderão aos
computadores?
ARITMÉTICA DE PEANO
x(0  s( x))
xy(s( x)  s( y)  x  y)
((0)  x(( x)  (s( x))))  y( y)
x((x  0)  x)
xy((x  s( y))  s( x  y))
x((x.0)  0)
xy((x.s( y))  ( x. y  x))
Soma
Multiplicação
FUNÇÕES COMPUTÁVEIS

Como definir / delimitar o conjunto das funções
naturais que sejam calculáveis por um algoritmo
baseado nas operações aritméticas?
FUNÇÕES SOBRE N
FUNÇÕES CALCULÁVEIS
TIPOS DE FUNÇÕES
1. Iniciais
 2. Recursivas Primitivas
 3. Recursivas Parciais
 4. Recursivas

1. FUNÇÕES INICIAIS

3 tipos:

Constante

Sucessor

Projeção
Cmk (n0 , n1 , n2 ,...,nk 1 )  m
S(n)  n  1
Pik (n0 , n1 ,...,nk 1 )  ni
(i  k )
2. RECURSIVAS PRIMITIVAS

É o menor conjunto de funções que:

Contém as funções iniciais

É fechado por
Substituição
 Recursão primitiva

2. RECURSIVAS PRIMITIVAS

Substituição

Recursão primitiva



g , h0 , h1 ,...,hp1  F  g(h0 (n), h1 (n),...,hp1 (n))  F

Se
g , h  F  f  F, onde


f (0, n)  g(n)

 
f (m  1, n)  h( f (m, n), n, m)
2. RECURSIVAS PRIMITIVAS

Será que as funções recursivas primitivas contém
todas as funções computáveis?

Não! Ex.: Função de Ackermann
FUNÇÃO DE ACKERMANN

A(m,n) =
n + 1 se m = 0
A(m-1, 1) se m > 0 e n = 0
A(m-1, A(m, n-1)) se m > 0 e n > 0
FUNÇÃO DE ACKERMANN

Cresce rapidamente:

Ex.: valor de A(4, 2)
É computável
 Não é recursiva primitiva

FUNÇÃO DE ACKERMANN
FUNÇÕES SOBRE N
FUNÇÕES CALCULÁVEIS
FUNÇÕES REC. PRIMITIVAS
A(m, n)
3. FUNÇÕES RECURSIVAS PARCIAIS

São as funções RECURSIVAS PRIMITIVAS
estendidas com o operador μ:

 (  y)R( x , y) : representa o menor y

tal que R( x, y)
3. FUNÇÕES RECURSIVAS PARCIAIS

y
 Se não existir
tal queR( x, y) seja verdadeiro?


A função não para (loop infinito).
As funções recursivas parciais correspondem ao
conjunto de funções computáveis.
4. FUNÇÕES TOTAIS / RECURSIVAS


Dada uma função recursiva PARCIAL f.
 Se f sempre para, dizemos que f é uma FUNÇÃO
TOTAL.
Ou então, dizemos que f é uma FUNÇÃO
RECURSIVA.
4. FUNÇÕES TOTAIS / RECURSIVAS


Toda função recursiva primitiva é TOTAL /
RECURSIVA.
A função de Ackermann é TOTAL /
RECURSIVA.
RESUMO
FUNÇÕES SOBRE N
FUNÇÕES CALCULÁVEIS = PARCIAIS
FUNÇÕES TOTAIS
FUNÇÕES REC. PRIMITIVAS
A(m, n)
S, C, P
CORRETUDE/COMPLETUDE

Corretude


Completude


Se toda sentença demonstrável é verdadeira
Se toda sentença verdadeira é demonstrável
Existe Sistema Axiomático Correto e Completo?
MÉTODO DA DIAGONALIZAÇÃO

Gera Paradoxos

Paradoxos de Russel
Paradoxo do mentiroso
 Paradoxo do condenado
 The “Salting” Problem
 Paradoxo do Barbeiro

TEOREMA DA INCOMPLETUDE DE GÖDEL

Não existe Sistema Axiomático Correto e
Completo
Seja ᵩ uma sentença de PROP definida como
ᵩ = eu não sou demonstrável
 Se é verdadeiro então é falso
 Se é falso então é verdadeiro

REVISÃO PROVA 2
Obrigado!