Upload
internet
View
124
Download
2
Embed Size (px)
Citation preview
LÓGICA
LÓGICA BÁSICA
Por: Thais Lima Machado.
Lógica
Cálculo Proposicional
Cálculo de Predicados
Prova de Teoremas
Lógica
Cálculo Proposicional
Lógica - Cálculo Proposicional
Cálculo interessado pelas sentenças declarativas (proposições).
Proposições podem ser verdadeiras ou falsas.
Lógica - Cálculo Proposicional
Vocabulário: Operadores lógicos:
Negação: ~(Não é o caso que)Conjunção: &(e)Disjunção: v (ou) Condicional: -> (se..então)Bicondicional: (se e somente se)
Lógica - Cálculo Proposicional
Vocabulário: Letras Sentenciais:
Letras maiúsculas seguidas ou não de números.
Parênteses:( , )
Lógica - Cálculo Proposicional
Regras de Formação: Qualquer letra sentencial é uma fbf. Se x é uma fbf, então ~x também o é. Se x e y são fbfs, então (x & y), (x v y),
(x y) e (x y) também são.
fbf: Fórmula bem formada.
Lógica - Cálculo Proposicional
Definições: Fórmula Válida: Se e somente se for verdadeira
para todas as interpretações possíveis. Fórmula Inválida: Caso existir alguma
interpretação em que for falsa. Fórmula Inconsistente (Insatisfatível): Se e
somente se for falsa para todas as suas interpretações.
Fórmula Consistente: Se existir alguma interpretação onde ela for verdadeira.
Tautologia: Proposição que é sempre verdade, independente dos valores de seus componentes.
Lógica - Cálculo Proposicional
Regras de Inferências:
São regras hipotéticas ou não que geram as formas de argumentos numa série de etapas simples e precisas de raciocínio, chamadas de derivação ou prova.
Lógica - Cálculo Proposicional
Regras de Inferências: Regras Básicas:
Modus Poneuns (MP): De um condicional e seu antecedente podemos inferir o seu conseqüente.
Eliminação de Negação (~E): De um fbf da forma ~~x, podemos inferir x.
Introdução de Conjunção (&I): De quaisquer fbfs x e y, podemos inferir a conjunção x & y.
Lógica - Cálculo Proposicional
Regras de Inferências: Regras Básicas:
Eliminação de Conjunção (&E): De um conjunção podemos inferir qualquer um dos seus conjuntos (são cada uma das sentenças ligadas pela conjunção).
Introdução de Disjunção (vI): De uma fbf x, podemos inferir a disjunção de x com qualquer fbf.
Eliminação de Disjunção (vE): De fbfs da forma xvy, x z e yz, podemos inferir a fbf z.
Lógica - Cálculo Proposicional
Regras de Inferências: Regras Básicas:
Introdução do Bicondicional ( I): De quaisquer fbfs de formas (xy) e (yx) podemos inferir xy.
Eliminação do Bicondicional ( E): De quaisquer fbfs de formas (xy), podemos inferir (xy) ou (yx).
Lógica - Cálculo Proposicional
Regras de Inferências: Regras Básicas:
Prova do Condicional (PC): Dada uma derivação de uma fbf x a partir de uma hipótese y, podemos descartar a hipótese e inferir yx.
Redução ao Absurdo (RAA): Dada uma derivação de uma contradição a partir de uma hipótese x, podemos descartar a hipótese e inferir ~x.
Lógica - Cálculo Proposicional
Tabela Verdade Negação
x ~xV FF V
Lógica - Cálculo Proposicional
Tabela Verdade Conjunção
x y x & yV V VV F FF V FF F F
Lógica - Cálculo Proposicional
Tabela Verdade Disjunção
x y x v yV V VV F VF V VF F F
Lógica - Cálculo Proposicional
Tabela Verdade Condicional ‘P Q = ~(P & Q)’
x y x yV V VV F FF V VF F V
Lógica - Cálculo Proposicional
Tabela Verdade Bicondicional P Q = (P Q) & (Q P)
x y x yV V VV F FF V FF F V
Lógica
Cálculo dos Predicados
Lógica- Cálculo dos Predicados
Introduz noções lógicas para expressar qualquer conjunto.
Expressa através de três tipos de expressões: termos, predicados, quantificadores.
Lógica- Cálculo dos Predicados
Definições: Classe de Atributo: São representadas
pelos substantivos comuns, locuções nominais, adjetivos, locuções adjetivas, verbos, e locuções verbais.
Quantificadores: São operadores lógicosque expressam relações entre os conjuntos designados pelas classes de atributos lógicos. Eles são classificados de universais e existenciais.
Lógica- Cálculo dos Predicados
Definições: Quantificador Universal (): Esse tipo de
quantificador é formado pelas expressões “todo” e “nenhum”.
Quantificador Existencial (): Esse tipo de quantificador é formado pela expressão “algum”.
Predicados: Serão denotados por letras maiúsculas.
Lógica- Cálculo dos Predicados
Vocabulário Símbolos lógicos:
Operadores lógicos: ~, &, v, , .Quantificadores: , .Parênteses: ( , ).
Lógica- Cálculo dos Predicados
Vocabulário Símbolos não-lógicos:
Letras Normais: letras minúsculas de “a” a “t”.
Variaveis: letras minúsculas de “u” a “z”.Letras Predicativas: letras minúsculas.
Lógica- Cálculo dos Predicados
Regras de Formação: Toda fórmula atômica é uma fbf. Se x é uma fbf, então ~x também o é. Se x e y são fbfs, então (x & y), (x v y),
(x y) e (x y) também o são.
Lógica- Cálculo dos Predicados
Regras de Inferência:
Todas as regras definidas na lógica proposicional são utilizadas para o cálculo de predicados, apenas referenciando-se para os quantificadores.
Lógica- Cálculo dos Predicados
Regras de Inferência: Regras Básicas:
Eliminação Universal (EU): De uma fbf quantificadora universalmente, x, infere-se qualquer fbf da forma x/, a qual resulta de se substituir cada ocorrência da variável em x por uma letra nominal .
Lógica- Cálculo dos Predicados
Regras de Inferência: Regras Básicas:
Introdução Universal (IU): De uma fbf x contendo uma letra nominal , que não corre em qualquer premissa ou em qualquer hipótese vigente na linha em que x ocorre, infere-se uma fbf da forma x/, onde x/ é resultado de se substituir todas as ocorrências de em x por uma variável que não ocorra em x.
Lógica- Cálculo dos Predicados
Regras de Inferência: Regras Básicas:
Introdução Existencial (IE): Dada um fbf x contendo uma letra nominal , infere-se uma fbf da forma x/, onde x/ é resultado de se substituir uma ou mais ocorrências de em x por uma variável que não ocorra em x.
Lógica- Cálculo dos Predicados
Regras de Inferência: Regras Básicas:
Eliminação Existencial (EE): Dada uma fbf quantificada existencialmente, x e uma derivação de uma conclusão y a partir da hipótese do tipo x/ (o resultado de se substituir cada ocorrência da variável em x por uma letra nominal que não ocorra em x), descarta-se x/ e afirma-se y.
Lógica
Prova de Teoremas
Lógica- Prova de Teoremas
Provar teoremas faz parte da inteligência humana.
Técnica levada para a IA.Na IA, a área que mais utiliza é SE’sObjetivo: provar que uma forma é
conseqüência lógica de outras formulas.
Lógica- Prova de Teoremas
Definições: Prova: É a demonstração que um
teorema (ou formula) é verdadeiro. Forma Normal Conjuntiva: É quando
uma formula F for composta de umas conjunções de outras formulas.
Lógica- Prova de Teoremas
Definições: Forma Normal Disjuntivas: É quando
uma formula F for composta de umas disjunções de outras formulas.
Forma Normal Prenex: É quando uma formula F, na lógica da primeira ordem, são retirados todos os quantificadores existentes que prefixem a fórmula.
Lógica- Prova de Teoremas
Universo de Herbrand Serve para demostrar que um conjunto
de cláusulas S é insatisfatível. Conjunto de cláusulas é dito
insatisfatível quando for falsa para todas as interpretações em todos os domínios.
Lógica- Prova de Teoremas
Principio da Resolução: Nesse princípio usamos um mecanismo
de substituição que permite a verificação da validade de um fórmula, além de empregar uma única regra de inferência e não necessitar de axiomas lógicos.
Definição:É um método algorítmico que permite verificar a insatisfatibilidade de qualquer conjunto de cláusulas.
Lógica- Prova de Teoremas
Termos importantes para o uso do Princípio da Resolução: Profundidade: Se a cláusulas vazia
sempre é produzida, o conjunto original deve Ter sido insatisfatível.
Completude: Se o conjunto original é insatisfatível, a cláusulas vazia eventualmente será produzida.