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)) xy(s( x) s( y) x y) ((0) x(( x) (s( x)))) y( y) x((x 0) x) xy((x s( y)) s( x y)) x((x.0) 0) xy((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 ,...,hp1 F g(h0 (n), h1 (n),...,hp1 (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!
Download
