32
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 - dainf.ct.utfpr.edu.bradolfo/Disciplinas/LogicaParaComputacao... · 16/09/09 Prof. Celso A A Kaestner 2 Lógica de Predicados • A Lógica de Predicados (ou

  • 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

([email protected])

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,...}

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 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

Fim da Primeira Parte

● Ver exercícios resolvidos de representação de conhecimento

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 }.

Exemplos

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 21

Lógica Predicativa

• Exemplos:

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 27

Lógica Predicativa

• Exemplos:

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)