Lógica de Predicados

Prévia do material em texto

Lógica de Predicados
Para toda variável , se I[x] = ,
então ∈ U
Para toda função f, n-ária, se I[f] 
 = , então : → U
Para todo predicado p, n-ário, se
I[p] = , então : → {T, F}
Dado um termo f(t1, t2, ... , tn)
então I [f(t1, t2, ... , tn)] = 
Dado um átomo p(t1, t2, ... , tn)
então I [p(t1, t2, ... , tn)] = 
Seja U um conjunto não-vazio. Uma
interpretação I sobre o domínio U é uma
função tal que: 
Definimos o alfabeto da Lógica de
Predicados por:
LINGUAGEM
Maior precedência: ¬
Ordem de precedência:
Pontuação: ( , ) 
Variáveis: x, y, z, w, x1, y1, ...
Funções: f, g, h, f1, ...
Predicados: p, q, r, p1, q1, ...
Conectivos: ¬, ∨, ∀, ∃
OBS: Aridade é o número não negativo k
que indica o número de argumentos de
uma função ou predicado. Se uma função
tem aridade 0, então é constante e
representada por a, b, c, a1, ... . Se um
predicado tem aridade 0, então é um
símbolo proposicional: P, Q, R, ... .
O conjunto dos termos da linguagem da
Lógica de Predicados são construídos com
as regras a seguir:
As variáveis são termos
Se t1, t2 ..., tn são termos então
f(t1, t2, . . . , tn) (função n−ária) é um
termo
O conjunto de átomos da linguagem da
Lógica de Predicados são construídos com
as regras a seguir:
Os símbolos proposicionais são
átomos
Se t1, t2 ..., tn são átomos então
p(t1, t2, ..., tn) (predicado n−ário) é
um átomo
As fórmulas são construídas conforme as
regras a seguir: 
Todo átomo é uma fórmula
Se H é uma fórmula, então (¬H) é
uma fórmula
Se H e G são fórmulas, então H ∨
G é fórmula
Se H é fórmula e x uma variável,
então ((∀x)H) e ((∃x)H) são
fórmulas
Intermediária superior: ∀, ∃
Intermediária inferior: →,↔
Menor precedência: ∧, ∨
O escopo de (∀x)H ou (∃x)H é a
subfórmula H. 
Sejam x uma variável e H uma fórmula:
Uma ocorrência de x em H é
livre se x não está no escopo de
um quantificador (∀x) ou (∃x);
Uma ocorrência de x em H é
ligada se não for livre.
SEMÂNTICA
OBS: Com relação a interpretação das
fórmulas ¬H, H ∨G, H ∧G, H → G e H ↔ G elas
seguem as mesmas regras que nas tabelas-
verdades da lógica proposicional.
Seja I uma interpretação sobre U.
Considere x uma variável qualquer e d um
elemento de U. Uma extensão de I é uma
interpretação sobre U tal que
Exemplo: Seja I uma interpretação sobre N,
tal que I[p(x,y)] = T ⇔ x < y, I[x] = 5, I[y] = 9.
Então, H = p(x, y) é satisfatível. 
Sejam H uma fórmula, x uma variável
qualquer e I uma interpretação sobre o
domínio U:
I [(∀x)H] = T ⇔ ∀d ∈ U; < x ← d >
I[H] = T
I [(∀x)H] = F ⇔ ∃d ∈ U; < x ← d >
I[H] = F
I [(∃x)H] = T ⇔ ∃d ∈ U; < x ← d >
I[H] = T
I [(∃x)H] = F ⇔ ∀d ∈ U; < x ← d >
I[H] = F
PROPRIEDADES SEMÂNTICAS
Valem os mesmos conceitos das
propriedades semânticas da Lógica
Proposicional: tautologia, contradição,
satisfatibilidade, .... O cuidado que devemos
ter aqui é lembrar que quando uma
propriedade vale para toda interpretação (e
agora existem infinitas) precisamos verificar
para uma interpretação qualquer. 
TABLEAUX SEMÂNTICO
Os tableaux semânticos são como árvores
e são expandidos a partir de regras de
inferência.
Regras de inferência:
Se H é tautologia, então existe tableau
fechado associado a H. 
Se H é tautologia, então pode existir
tableau aberto associado a H. 
Se H não é tautologia, então não existe
tableau fechado associado a H.
Se H não é tautologia, então todo tableau
associado a H é aberto.
Se um tableau associado a H é fechado,
então H é tautologia
Se um tableau associado a H é aberto,
então não se pode concluir que H não é
tautologia. 
Se todo tableau associado a H é aberto,
então H não é tautologia.