Upload
ledung
View
216
Download
0
Embed Size (px)
Citation preview
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
Versão original disponível em http://www.dainf.ct.utfpr.edu.br/~kaestner/Logica/LogicaPredicativa.ppt
16/09/09 Prof. Celso A A Kaestner 2
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.
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)
16/09/09 Prof. Celso A A Kaestner 5
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:
– Conjuntos de predicados: Ri = { ri1, ri
2,... 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, fi
2,... fin,...} onde o
sobrescrito i também indica a aridade da função;
– Um conjunto de variáveis: V = {x1,x2, ...}.
Exemplos
● Predicados:– R1={homem1,mortal1,brasileiro1,...}
– R2={maior2,matou2, ...}
– R3={deu3,...}
– ...
● Constantes:– C={maria,joão,livro,3,4,...}
Lógica de Predicados
● Para definir o que são fórmulas bem-formadas na Lógica de Predicados precisaremos definir dois conceitos:
– Assinatura e
– Termos
● O conjunto de fórmulas bem-formadas será relativo a uma assinatura.
16/09/09 Prof. Celso A A Kaestner 9
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 10
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(Σ);
– 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(Σ).
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
● ∀x.(Professor(x)→Funcionario(x))– 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.(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
● ∀x∀y. ( Maior_igual(media(x,y),x) ∨ Maior_igual(media(x,y),y) )
– Não é verdade que a soma de dois números pares seja um número ímpar
● !(∀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
16/09/09 Prof. Celso A A Kaestner 18
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 ϕ= ξ∧ψ, ξ∨ψ, ou ξ→ψ então VLIVRES (ϕ)= VLIVRES (ξ) ∪ VLIVRES (ψ);
– Se ϕ= ∀x(ψ) ou ∃x(ψ) então VLIVRES (ϕ)= VLIVRES (ψ) – {x}.
• Exemplo: Se ϕ = ∀x (r(x) ∧ q(y) → ∃z (s(z,y))) então VLIVRES (ϕ) = { y }.
16/09/09 Prof. Celso A A Kaestner 20
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ãor(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 22
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 23
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 24
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(Σ)[γ ],..., tj
A(Σ)[γ ]).
16/09/09 Prof. Celso A A Kaestner 25
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 t1
A(Σ)[γ ] = 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 26
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 28
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 29
Lógica PredicativaSubstituiçã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 30
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 31
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 32
Lógica Predicativa
Exemplo do método dos tableaux analíticos: 1 . ∀x(r(x) → s(x)) |- ∀x r(x) → ∀x s(x) 2. T ∀x(r(x) → s(x)) de 13. F ∀x r(x) → ∀x s(x) de 14. T ∀x r(x) de 3 5. F ∀x s(x) de 36. F s(a) de 57. T r(a) de 48. T r(a) → s(a) de 2
1. F r(a) T s(a) de 8 X (7,9) X (6,9)