REVISÃO PROVA 2 Monitoria de Lógica. T EOREMA DE H ERBRAND Seja S um conjunto de cláusulas. S é...

REVISÃO PROVA 2Monitoria 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

))()(( yxysxsyx

))(0( xsx

)())))(()(()0(( yyxsxx

))0(( xxx

))())((( yxsysxyx

)0)0.(( xx

)).())(.(( xyxysxyx

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

mnnnnC kkm ),...,,,( 1210

1)( nnS

ikki nnnnP ),...,,( 110 )( ki

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 Se , onde

Fhhhg p 110 ,...,,, Fnhnhnhg p ))(),...,(),(( 110

FfFhg ,

),,),((),1(

)(),0(

mnnmfhnmf

ngnf

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 = 0n + 1 se m = 0

A(m-1, 1) se m > 0 e n = 0A(m-1, 1) se m > 0 e n = 0

A(m-1, A(m, n-1)) se m > 0 e n > A(m-1, A(m, n-1)) se m > 0 e n > 00

FUNÇÃO DE ACKERMANN

Cresce rapidamente: Ex.: valor de A(4, 2)

É computável Não é recursiva primitiva

FUNÇÃO DE ACKERMANN

FUNÇÕES CALCULÁVEIS

FUNÇÕES REC. PRIMITIVAS

FUNÇÕES SOBRE N

A(m, n)

3. FUNÇÕES RECURSIVAS PARCIAIS

São as funções RECURSIVAS PRIMITIVAS estendidas com o operador μ:

: representa o menor tal que),() ( yxRy

y ),( yxR

3. FUNÇÕES RECURSIVAS PARCIAIS

Se não existir tal que seja verdadeiro? A função não para (loop infinito).

As funções recursivas parciais correspondem ao conjunto de funções computáveis.

),( yxRy

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 CALCULÁVEIS = PARCIAIS

FUNÇÕES REC. PRIMITIVAS

FUNÇÕES SOBRE N

A(m, n)

FUNÇÕES TOTAIS

S, C, P

CORRETUDE/COMPLETUDE

Corretude Se toda sentença demonstrável é verdadeira

Completude 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 2Obrigado!