Lógica de Predicados
Slides da disciplina Lógica para Computação
ministrada pelo Prof. Celso Antônio Alves Kaestner, Dr. Eng.
([email protected]) entre 2007 e 2008.
Alterações feitas em 2009 pelo Prof. Adolfo Neto
([email protected])
Versão original disponível em
http://www.dainf.ct.utfpr.edu.br/~kaestner/Logica/LogicaPredicativa.ppt
Lógica de Predicados
•
•
•
•
A Lógica de Predicados (ou lógica de 1ª ordem) é
uma extensão da lógica proposicional que aumenta
sua expressividade, permitindo que se façam
afirmações sobre propriedades – ou predicados –
inerentes a conjuntos de elementos individuais;
Tipicamente as fórmulas envolvem os
quantificadores “para todo” (∀) e “existe” (∃ );
Uma fórmula típica é: ∀x(homem(x)→mortal(x)).
Obs.: para representar o mesmo em Lógica Proposicional seria
necessário utilizar uma fórmula para cada indivíduo, por exemplo:
(homem_joão → mortal_joão), (homem_josé → mortal_josé), etc.
16/09/09
Prof. Celso A A Kaestner
2
Mais exemplos de Fórmulas com Predicados
●
Predicados unários:
–
●
●
brasileiro(João)
Predicados binários:
–
maior(3,4)
–
matou(João,Maria)
Predicados ternários:
–
deu(Maria,livro,João)
Gottlob Frege
Lógica Predicativa
•
A linguagem (sintaxe) da Lógica Predicativa LPRED é
mais complexa que a da Lógica Proposicional;
•
Para a definição de LPRED necessita-se de:
–
–
–
–
16/09/09
Conjuntos de predicados: Ri = { ri1, ri2,... rin,...} onde
o sobrescrito i indica a aridade do predicado (o seu
nº de argumentos);
Um conjunto de constantes: C = {c1,c2, ...};
Conjuntos de funções: Fi = { fi1, fi2,... fin,...} onde o
sobrescrito i também indica a aridade da função;
Um conjunto de variáveis: V = {x1,x2, ...}.
Prof. Celso A A Kaestner
5
Exemplos
●
●
Predicados:
–
R1={homem1,mortal1,brasileiro1,...}
–
R2={maior2,matou2, ...}
–
R3={deu3,...}
–
...
Constantes:
–
C={maria,joão,livro,3,4,...}
Funções
●
+(3,4)
●
pai_de(João)
●
divisao(5.5,3.2)
●
salario(João)
Lógica de Predicados
●
●
Para definir o que são fórmulas bemformadas na Lógica de Predicados
precisaremos definir dois conceitos:
–
Assinatura e
–
Termos
O conjunto de fórmulas bem-formadas
será relativo a uma assinatura.
Lógica Predicativa
•
Uma assinatura de LPRED é a uma tupla do tipo
Σ = [R1,R2, ..., RM,C,V,F1,F2,...,FN] onde M e N são
números naturais conhecidos.
•
O conjunto dos termos de LPRED é T(Σ) definido
recursivamente por:
– Se x∈V então x ∈ T(Σ);
– Se c∈C então c ∈ T(Σ);
– Se f∈Fj e se t1,...tj ∈ T(Σ) então f(t1,...tj )∈ T(Σ).
16/09/09
Prof. Celso A A Kaestner
9
Lógica Predicativa
•
O conjunto das fórmulas bem formadas (fbf) de
LPRED é Fbf(Σ) definido recursivamente como sendo o
menor conjunto que atenda ao seguinte:
– Se t1,...tj ∈ T(Σ) e se rj ∈ Rj então rj(t1,...tj) ∈ Fbf(Σ);
–
–
–
16/09/09
Se t1, t2 ∈ T(Σ) então t1= t2 ∈ Fbf(Σ);
Estas fbf são chamadas de fórmulas atômicas;
Se ϕ, ψ ∈ Fbf(Σ) então ¬ϕ, ϕ∧ψ, ϕ∨ψ, ϕ→ψ
∈Fbf(Σ);
Se ϕ ∈ Fbf(Σ) e se x∈V então ∀x(ϕ) e ∃ x(ϕ) ∈
Fbf(Σ).
Prof. Celso A A Kaestner
10
Exemplos
●
●
Assinaturas
–
Termos
–
Fórmulas bem-formadas
Σ=[R1={filho_unico},R2={pai},C={joao,jose,1,...,120},V=
{x,y},F1={idade},F2={soma}]
Representação de
Conhecimento
●
●
Representar frases em língua natural
como fórmulas em lógica de predicados
Há um conjunto de regras que podem ser
utilizadas na tradução
Exercícios Resolvidos
●
Escreva fórmulas para representar as frases abaixo:
–
–
A média de a e b é igual a c
●
Igual(media(a,b),c) - para lógicas sem igualdade
●
media(a,b)=c
Todo professor é funcionário
●
–
Alguns alunos são funcionários
●
–
∃x.(Aluno(x)∧Funcionario(x))
Se alguém matou Maria, este alguém também matou João
●
–
∀x.(Professor(x)→Funcionario(x))
∀x.(Matou(x,Maria)→Matou(x,João))
Todo número primo maior do que 2 é ímpar
●
∀x.( (Primo(x)∧Maior_que(x,2)) → Impar(x) )
Exercícios Resolvidos
●
Escreva fórmulas para representar as frases abaixo:
–
A média de quaisquer dois números é maior ou igual do que um
dos dois
●
–
∨
Não é verdade que a soma de dois números pares seja
um número ímpar
●
–
∀x∀y. ( Maior_igual(media(x,y),x)
Maior_igual(media(x,y),y) )
!(∀x∀y.[ (Par(x)∧Par(y))Impar(soma(x,y)) ])
Se um número é par, ele não é ímpar
●
∀x.( Par(x)
(!(Impar(x)) ) )
Exercícios
●
Escreva fórmulas para representar as frases abaixo:
–
O resultado da multiplicação de a por b é c
–
Alguns políticos são ladrões
–
Todo múltiplo de 4 é múltiplo de 2
–
A média de quaisquer três números é maior ou igual do que um
dos três
–
Se um número é divisível por outro, não igual a zero, então
dizemos que ele é múltiplo desse outro
–
Se uma pessoa é pai de outra que tem um filho, então aquela
pessoa é avô deste último
LP Monádicos vs. LP Poliádicos
●
●
Lógica de Predicados Monádicos: apenas
predicados unários.
–
Limitada
–
A satisfazibilidade é decidível
Lógica de Predicados Poliádicos
–
Sem limite na aridade dos predicados
–
A satisfazibilidade é indecidível
Fim da Primeira Parte
●
Ver exercícios resolvidos de
representação de conhecimento
Lógica Predicativa
O conjunto das variáveis livres VLIVRES (ϕ) em uma
fórmula ϕ é definido por:
•
•
–
Se ϕ = rj(t1,...tj) com rj ∈ Rj e os ti ∈ T(Σ) então todas as
variáveis em ϕ pertencem a VLIVRES (ϕ);
–
Se ϕ = (t1=t2) com os ti ∈ T(Σ) então todas as variáveis em ϕ
pertencem a VLIVRES (ϕ);
–
–
Se ϕ=¬ψ então VLIVRES (ϕ)= VLIVRES (ψ);
–
Se ϕ= ∀x(ψ) ou ∃ x(ψ) então VLIVRES (ϕ)= VLIVRES (ψ) – {x}.
Se ϕ= ξ∧ψ, ξ∨ψ, ou ξ→ψ então
VLIVRES (ϕ)= VLIVRES (ξ) ∪ VLIVRES (ψ);
Exemplo: Se ϕ = ∀x (r(x) ∧q(y) → ∃ z (s(z,y))) então
VLIVRES (ϕ) = { y }.
16/09/09
Prof. Celso A A Kaestner
18
Exemplos
Lógica Predicativa
•
•
•
Uma fórmula ϕ tal que VLIVRES (ϕ) = φ (sem variáveis
livres) é denominada uma sentença.
Uma subfórmula de uma fórmula ϕ é uma
subseqüência dos símbolos de ϕ que também
pertence a Fbf(Σ).
Exemplo: se ϕ = ∀x (r(x) ∧q(y) → ∃ z (s(z,y))) então
r(x) ∧q(y) → ∃ z (s(z,y)) , r(x) ∧q(y), ∃ z (s(z,y)) ,
r(x) e q(y) são subfórmulas de ϕ.
16/09/09
Prof. Celso A A Kaestner
20
Lógica Predicativa
•
Exemplos:
16/09/09
Prof. Celso A A Kaestner
21
Lógica Predicativa
•
•
•
A semântica da Lógica Predicativa é definida sobre um
par A(Σ)=[A, vA(Σ)] denominado sistema algébrico da
assinatura Σ, tal que:
A é um conjunto denominado domínio (ou portador)
do sistema algébrico;
vA(Σ) é uma interpretação, que mapeia os elementos
dos conjuntos em Σ em relações sobre A (para os
predicados), em funções sobre A (para as funções) e
em elementos de A (para as constantes).
16/09/09
Prof. Celso A A Kaestner
22
Lógica Predicativa
•
Desta forma para uma interpretação vA(Σ) tem-se:
•
Se rj ∈ Rj então vA(Σ) (rj) ⊆ Aj = A × A × ... A (j
vezes);
Se f∈Fj então existe uma função vA(Σ) (fj): Aj →A;
Se c ∈ C então vA(Σ) (c) ∈ A;
Para um conjunto de variáveis X ⊆ V existe ainda
uma função γ : X → A denominada interpretação
das variáveis X em A .
•
•
•
16/09/09
Prof. Celso A A Kaestner
23
Lógica Predicativa
•
O valor de um termo t ∈ T (Σ) em um sistema
algébrico A(Σ) e para uma interpretação de variáveis γ
é definido indutivamente por:
•
•
•
Se t = x ∈ X então tA(Σ) [γ ] = γ (x);
Se t = c ∈ C então tA(Σ) [γ ] = vA(Σ) (c);
Se f∈Fj , t1,..., tj são termos e t=f(t1,..., tj) então
tA(Σ) [γ ]= vA(Σ) (fj)(t1A(Σ)[γ ],..., tjA(Σ)[γ ]).
16/09/09
Prof. Celso A A Kaestner
24
Lógica Predicativa
•
•
Finalmente é possível se definir quando uma fórmula
ϕ é verdadeira para um sistema algébrico A(Σ) e uma
interpretação de variáveis γ ;
Denota-se por A(Σ) |= ϕ[γ ];
•
Se ϕ = rj(t1,...tj) ∈ Fbf(Σ) então A(Σ) |= ϕ[γ ] é equivalente a [t1A(Σ)
[γ ],..., tjA(Σ)[γ ]] ∈ vA(Σ) (rj);
•
Se ϕ = (t1=t2) com t1, t2 ∈ T(Σ) então A(Σ) |= ϕ[γ ] é equivalente a
t1A(Σ)[γ ] = t2A(Σ)[γ ];
•
Se ϕ= ¬ψ e ψ∈Fbf(Σ) então A(Σ) |= ϕ[γ ] se e somente se não for
verdade que A(Σ) |= ψ [γ ];
16/09/09
Prof. Celso A A Kaestner
25
Lógica Predicativa
•
•
•
•
•
Se ϕ = ξ∧ψ, com ξ, ψ ∈ Fbf(Σ) então A(Σ) |= ϕ[γ ] se e somente
se A(Σ) |= ξ[γ ] e A(Σ) |= ψ[γ ];
Se ϕ = ξ∨ψ, com ξ, ψ ∈ Fbf(Σ) então A(Σ) |= ϕ[γ ] se e somente
se A(Σ) |= ξ[γ ] ou A(Σ) |= ψ[γ ];
Se ϕ = ξ→ψ, com ξ, ψ ∈ Fbf(Σ) então A(Σ) |= ϕ[γ ] se e somente
se quando A(Σ) |= ψ[γ ] necessariamente também ocorre A(Σ) |=
ξ[γ ];
Se ϕ = ∃ x(ψ) com ψ ∈ Fbf(Σ) então A(Σ) |= ϕ[γ ] se e somente se
existir pelo menos uma interpretação de variáveis γ : X → A que,
restrita às variáveis de ϕ, seja tal que A(Σ) |= ϕ[γ ];
Se ϕ = ∀x(ψ) com ψ ∈ Fbf(Σ) então A(Σ) |= ϕ[γ ] se e somente se
para todas as interpretações de variáveis γ : X → A , quando
restritas às variáveis de ϕ, sejam tais que A(Σ) |= ϕ[γ ].
16/09/09
Prof. Celso A A Kaestner
26
Lógica Predicativa
•
Exemplos:
16/09/09
Prof. Celso A A Kaestner
27
Lógica Predicativa
•
•
•
•
Uma teoria Γ em LPRED é um conjunto de sentenças;
Um sistema algébrico A(Σ) é um modelo para uma
teoria Γ se A(Σ) |= ϕ para toda ϕ ∈ Γ;
Se Γ tiver ao menos um modelo diz-se que Γ é
satisfazível;
Se Γ não tiver modelos é dita insatisfazível.
16/09/09
Prof. Celso A A Kaestner
28
Lógica Predicativa
Substituição de variáveis:
Seja ϕ uma fórmula, x ∈ VLIVRES (ϕ) uma variável livre
•
em ϕ e t ∈ T(Σ) um termo;
•
Neste caso a variável x pode ser substituída pelo
termo t em ϕ, gerando uma nova fórmula ϕ[x:=t];
•
Exemplo: se
ϕ = ∀x(r(x) →s(x,y)),
y∈VLIVRES (ϕ) e t=f(a,z)
então
ϕ[y:=f(a,z)] = ∀x(r(x) →s(x,f(a,z))).
16/09/09
Prof. Celso A A Kaestner
29
Lógica Predicativa
•
•
•
•
Intuitivamente uma substituição gera um “caso particular” de
uma fórmula;
As substituições só podem ser feitas sobre as variáveis livres de
ϕ, e de forma a não introduzir restrições na fórmula gerada que
já não estivessem presentes na fórmula original;
Várias substituições podem ser feitas simultaneamente, desde
que não introduzam restrições.
Exemplo:
Se
ϕ = ∀x(r(x) →s(x,y) ∧r(z))
y, z∈VLIVRES (ϕ) e t1=f(a,w), t2=b
então
ϕ[y:=f(a,w), z:=b]=∀x(r(x)→s(x,f(a,z))∧r(b)))
16/09/09
Prof. Celso A A Kaestner
30
Lógica Predicativa
Sistemas Dedutivos em Lógica Predicativa:
1. Método axiomático: ver item 4.5 pg. 128;
2. Dedução natural: ver item 4.4 pg. 122, e
também a ferramenta JAPE;
3. Método dos tableaux analíticos: ver item 5.6
pg. 147.
16/09/09
Prof. Celso A A Kaestner
31
Lógica Predicativa
Exemplo do método dos tableaux analíticos:
1.
2.
3.
4.
5.
6.
7.
8.
∀x(r(x) → s(x)) |- ∀x r(x) → ∀x s(x)
T ∀x(r(x) → s(x))
de 1
F ∀x r(x) → ∀x s(x)
de 1
T ∀x r(x)
de 3
F ∀x s(x)
de 3
F s(a)
de 5
T r(a)
de 4
T r(a) → s(a)
de 2
1.
F r(a)
X (7,9)
16/09/09
T s(a)
X (6,9)
de 8
Prof. Celso A A Kaestner
32