Representação de Sentenças em Fórmulas Interpretação de Fórmulas na Lógica de Predicados Exemplo 1: Simbolize as seguintes sentenças: Na lógica propos icional, uma interpretação é uma atribuição de valores verdade aos átomos. (a ) Todo número racional é um número real. (b) Exis te um núme ro que é primo. (c ) Para todo número x, existe um número y tal que x < y. Na lógica de predicados, uma vez que exis tem variáveis envolvidas, temse algo mais. Representando "x é um número primo" por P(x), "x é um número racional" por Q(x), "x é um número real" por R (x) e "x é menor que y" por M (x,y): (a') ∀x(Q(x) → R (x)) (b') ∃x(P(x)) (c') ∀x∃y(M (x,y)) Definição: Uma inte rpretação de uma fórmula α na lógica de predicados consis te de um domínio D, não vazio, e uma atribuição de valores para cada constante, função e predicado ocorrendo na fórmula, como segue: Exemplo 2: Trans forme a sentença "Todo homem é mortal. Confúcio é um homem. Portanto Confúcio é mor tal" em uma fórmula. Representando "x é um homem" por HOM EM (x) e "x é mortal" por MOR TAL(x). Então: "Todo homem é mortal": ∀x(HOM EM(x)→MOR TAL(x)), "Confúcio é um homem": HOM EM (Confúcio) e "Confúcio é mortal": MOR TAL(Confúcio) MOR TAL(x)) ∧ HOM EM (Confúcio) → Exemplo 3: Os axiomas básicos dos números naturais são os seguintes: A1: Para todo número, existe um e somente um sucessor imediato. A2: Não exis te nenhum número para o qual 0 seja o seu sucessor imediato. A3: Pa ra todo núme ro diferente de 0, existe um e somente um predecessor imediato. Fazendo f(x) e g(x) representar o s ucessor imediato de x e o predecessor imediato de x, respectivamente e I(x,y) representar "x é igual a y". Então os axiomas podem ser representados pelas seguintes fórmulas: A1': ∀x∃y( I(y,f(x)) ∧ ∀z( I(z,f(x)) → I(y,z ))) A2': ~(∃x(I(0,f(x)))) A3': ∀x(~I(x,0) → (∃y( I(y,g(x)) ∧ ∀z( I(z,g(x)) → I(y,z))))) 1. Pa ra cada constante, atribui-se um elemento em D. 2. Pa ra cada função n-arg, atribui-se um mapeamento de Dn para D. (Observe que Dn = {(x1, ... , xn) | x1 ∈D, ... , xn ∈D}). 3. Pa ra cada predicado n-ário, atribui-se um mapeamento de Dn para {V, F}. Algumas vezes, para enfatizar o domínio D, fala-se de uma interpretação de uma fórmula sobre D. Portanto a sentença completa pode ser representada por: ∀x(HOM EM (x) → MOR TAL(Confúcio) Pa ra definir uma interpretação para uma fórmula na lógica de predicados, tem-se que especificar duas coisas: o domínio e uma atribuição de valores para as constantes, funções e predicados ocorrendo na fórmula. Quando se avalia o valor verdade de uma fórmula em uma interpretação sobre o domínio D, (∀x) será interpretado como "para todos os elementos de D" e (∃x) como "existe um elemento em D". Pa ra toda inte rpretação de uma fórmula sobre um domínio D, a fórmula pode ser avaliada V ou F de acordo com as seguintes regras : 1. Se os valores verdade das fórmulas α e β são avaliados, então os valores verdade das fórmulas ~(α ), (α ∨ β), (α ∧ β), (α → β), (α ↔ β) são avaliados utilizando-se a tabela verdade. 2. ∀x(α ) é avaliado V se o valor de α é avaliado V para todo x em D, caso contrário é avaliado F. 3. ∃x(α ) é avaliado V se o valor de α é V para, no mínimo, um x em D, caso contrário é avaliado F. Note que qualquer fórmula contendo variáveis livres não pode ser avaliada. A partir deste ponto, vai-se assumir que, ou as fórmulas não contêm variáveis livres ou as variáveis livres são tratadas como constantes. Exemplo 6: Considere a fórmula α : ∀x(P(x) → Q(f(x),a)). Exis te uma constante a, uma função f, 1-ário, um predicado P, 1-ário e um predicado Q, 2-ário. Uma interpretação I de α pode ser descrita como segue: Exemplo 4: Considere as fórmulas: ∀x(P(x)) e ∃x(~P(x)) e uma interpretação como segue: Domínio: D = { 1 , 2 } Atribuição para a: Domínio: D = { 1 , 2 } a 1 Atribuição para P: P(1) V P(2) F Atribuição para f: f(1) 2 f(2) 1 Fica fácil confirmar que ∀x(P(x)) é F nessa interpretação, pois P(x) não é V para x = 2. Por outro lado, uma vez que ~P(2) é V nessa interpretação ∃x(~P(x)) também é V. Atribuição para P e Q: Exemplo 5: Cons idere a fórmula: ∀x∃y(P(x,y)) e uma interpretação como segue: Se x = 1, então: P(x) → Q(f(x),a ) = P(1) → Q(f(1),a) = P(1) → Q(2,1) = F → F = V Domínio: D = { 1 , 2 } Se x = 2, então: P(x) → Q(f(x),a ) = P(2) → Q(f(2),a) = P(2) → Q(1,1) = V → V = V Atribuição para P: Uma vez que P(x) → Q(f(x),a) é V para todos os valores de x no domínio D, a fórmula ∀x(P(x) → Q(f(x),a)) é verdadeira na inte rpretação I. P(1,1) V P(1,2) F P(2,1) F P(2,2) V Se x = 1, pode-se ver que existe um y, de valor 1, tal que P(1,y) é V. Se x = 2, também exis te um y, de valor 2, tal que P(2,y) é V. Portanto, na interpretação acima, para todo x em D, existe um y tal que P(x,y) é V, isto é, ∀x∃y(P(x,y)) é V nessa interpretação. P(1) F P(2) V Q(1,1) V Q(1,2) V Q(2,1) F Q(2,2) V Exemplo 7: Encontre os valores verdade para as seguintes fórmulas, considerando a interpretação dada no exemplo 6. (a ) ∃x(P(f(x)) ∧ Q(x,f(a ))) (b) ∃x(P(x) ∧ Q(x,a)) (c ) ∀x∃y(P(x) ∧ Q(x,y)) Uma vez que as interpretações são definidas, todos os conceitos, tais como validade, inconsistência e conseqüência lógica, definidos na 1a unidade, podem ser definidos de forma análoga para as fórmulas da lógica de predicados. Definição: Uma fórmula α é consistente se e somente se existe uma interpretação I tal que α é avaliada V em I. Se a fórmula α é V na interpretação I, diz-se que I é um modelo de α e I satis faz α. Definição: Uma fórmula α é inconsis tente se e somente se não existe nenhuma interpretação que satis faça α. Definição: Uma fórmula α é válida se e somente se toda inte rpretação de α satis faz α. Definição: Uma fórmula α é conseqüência lógica das fórmulas F1, ... , Fn se e somente se para toda interpretação: se F1 ∧ F2 ∧ ... ∧ Fn é V em I, α também é V em I. As relações entre validade (inconsistência) e conseqüência lógica são também verdadeiras para a lógica de predicados. De fato, a lógica de predicados pode ser considerada uma extensão da lógica propos icional. Quando uma fórmula da lógica de predicados não contém variáveis, nem quantificadores, ela pode ser tratada como uma fórmula da lógica propos icional. Exemplo 8: Prove os seguintes exemplos: (1) ∀x(P(x)) ∧ ∃y(~P(y)) é inconsistente. (2) ∀x(P(x)) → ∃y(P(y)) é válida. (3) P(a ) → ~(∃x(P(x))) é cons istente. (2) ∀x(P(x)) ∨ (∃y(~P(y))) é válida. Exemplo 9: Considere as fórmulas: F1: ∀x(P(x) → Q(x)) F2: P(a ) Quer-se provar que a fórmula Q(a) é conseqüência lógica de F1 e F2. Considere qualquer interpretação I que satis faça ∀x(P(x) → Q(x)) ∧ P(a). Certamente, nessa interpretação P(a ) é V. Assuma que Q(a) não é V nessa interpretação; então ~P(a) ∨ Q(a), isto é P(a ) → Q(a) é F em I. Isto significa que ∀x(P(x) → Q(x)) é F em I, o que é impossível. Portanto, Q(a) deve ser V em toda a interpretação que satis faz ∀x(P(x) → Q(x)) ∧ P(a). Is to significa que Q(a) é conseqüência lógica de F1 e F2. Na lógica de predicados, uma vez que há um núme ro infinito de domínios, em geral, exis te um núme ro infinito de interpretações de uma fórmula. Portanto, de maneira diferente da lógica propos icional, não é possível verificar a validade ou inconsistência de uma fórmula avaliando-a sobre todas as suas possíveis interpretações. Se rão vis tos pos teriormente procedimentos para verificar inconsistências na lógica de predicados.