Lógica (ou Cálculo) de Predicados


Principais diferenças em relação à lógica proposicional

Fórmulas bem Formadas


Linguagem Natural
Cálculo de Predicados
O pai de Jonas, além de professor, era músico. Professor(Pai(Jonas)) ^ Músico(Pai(Jonas))
* Pai(x) é uma função e não um predicado
Se o clima de Campo Grande estiver quente Eva vai nadar ou mergulhar Clima(Cgr,Quente) -> (Nadar(Eva) v Mergulhar(Eva))
Eu vou somente se você não for Vai(Eu) -> ~Vai(Você)
Rapadura é doce mas não é mole não Doce(Rapadura) ^ (~Mole(Rapadura))

Linguagem Natural
Cálculo de Predicados
Todos são culpados Vx Culpado(x)
Existe um culpado Ex Culpado(x)
Tudo o que sobe desce Vx ( Sobe(x) -> Desce(x))
Nem tudo que reluz é ouro Ex Reluz(x) ^ (~Ouro())
Nem só de pão vive o homem Vx Homem(x) -> (Ey Necessita(x,y) ^ ~Pão(y))
Todas as amigas de Maria moram em Santos Vx Amiga(Maria,x) -> Mora(x,Santos)

Exemplo de uma prova direta na lógica de predicados

Em linguagem natural: Todos os alunos da UCDB moram no MS. O Presidente do CA da UCDB é aluno da UCDB. João é presidente do CA. Logo, João mora no MS.

Premissas:
Vx ( AlunoUCDB(x) -> MoraMS(x) )
Vx ( PresidenteCA(x) -> AlunoUCDB(x) )
PresidenteCA(Joao)

Conclusão:
MoraMS(Joao)

Prova Direta:
 
1 Vx ( PresidenteCA(x) -> AlunoUCDB(x) P
2 PresidenteCA(Joao) P
3 PresidenteCA(Joao)->AlunoUCDB(Joao) IU 1
4 AlunoUCDB(Joao) MP 2,3
5 Vx( AlunoUCDB(x) -> MoraMS(x)) P
6 AlunoUCDB(Joao) -> MoraMS(Joao) IU 5
7 MoraMS(Joao) MP 4,6

Instanciação Universal (IU) = Retirada do quantificador universal através da substituição de uma variável por uma constante.

Expressar a seguinte prova usando lógica de predicados:

Todas as linguagens de programação são importantes. Nenhuma linguagem de programação importante será dispensada. Prolog é uma linguagem de programação. Logo, há linguagens de programação que não serão dispensadas.
 
1 Vx (Linguagem(x) -> Importante(x)) P
2 Vx (Linguagem(x) ^ Importante(x) -> ~Dispensada(x) P
3 Linguagem(Prolog) P
4 Linguagem(Prolog) -> Importante(Prolog) IU 1
5 Importante(Prolog) MP 4,3
6 Linguagem(Prolog) ^ Importante(Prolog) U 3,5
7 Linguagem(Prolog) ^ Importante(Prolog) -> ~Dispensada(Prolog) IU 2 
8 ~Dispensada(Prolog) MP 6,7
9 Linguagem(Prolog) ^ ~Dispensada(Prolog)) U 3,8
10 Ex (Linguagem(x) ^ ~Dispensada(x)) QE 9
Inferindo uma quantificação existencial: Sabendo que existe pelo menos uma constante que satisfaz uma determinada fórmula, podemos quantificar 'existencialmente' essa fórmula. No exemplo, sabemos que prolog não será dispensada, por isto, concluimos que existe pelo menos alguma coisa que não será dispensada.

Obs: No texto em linguagem natural usei cores para evidenciar os predicados e itálico para evidenciar as constantes (objetos). Usei cores também na primeira aparição do predicado na representação usando lógica de predicados.

Outros Exemlos

1. Provar que Marco Antônio odiava César
 
Linguagem Natural
Premissas em Lógica de Predicados
Marco era homem H(Marco)
Marco era um Pompeiano P(Marco)
Todos os pompeianos eram romanos Vx( P(x) -> R(x))
César era um soberano. S(Cesar)
Todos os romanos ou eram 
leais a César ou o odiavam
Vx (R(x) -> L(x,Cesar) V O(x,Cesar))
Cada um de nós é leal a alguém Vx ( Ey L(x,y) )
Os homens apenas tentam assassinar
soberanos a quem não sejam leais
VxVy (H(x) ^ S(y) ^ T(x,y) -> ~L(x,y))
Marco tentou assassinar César T(Marco,Cesar)
Teorema: O(Marco,Cesar)

Demonstração Direta:
 
1 Vx( P(x) -> R(x)) P
2 P(Marco)->R(Marco) IU 1
3 P(Marco) P
4 R(Marco) MP 2,3
5 Vx (R(x) -> L(x,Cesar) V O(x,Cesar)) P
6 R(Marco) -> L(Marco,Cesar) V O(Marco,Cesar) IU 5
7 L(Marco,Cesar) V O(Marco,Cesar) MP 4,6
8 VxVy (H(x) ^ S(y) ^ T(x,y) -> ~L(x,y)) P
9 H(Marco)^S(Cesar)^T(Marco,Cesar)->~L(Marco,Cesar) IU 8
10 H(Marco) P
11 S(Cesar) P
12 T(Marco,Cesar) P
13 H(Marco)^S(Cesar)^T(Marco,Cesar) U 10,11,12
14 ~L(Marco,Cesar) MP 9,13
15 O(Marco,Cesar) SD 7,14


2. Provar que Pedro gosta de Laranja

Resposta: Prova Direta
 
1 Vx,y Come(x,y) ^ ~Morto(x) -> Alimento(y) P
2 Come(Paulo,Laranja)^~Morto(Paulo)->Alimento(Laranja) IU 1
3 Come(Paulo,Laranja)^Vivo(Paulo) P
4 Vivo(Paulo) S 3
5 Vx (Vivo(x)->~Morto(x)) P
6 Vivo(Paulo)->~Morto(Paulo) IU 5
7 ~Morto(Paulo) MP 4,6
8 Come(Paulo,Laranja) S 3
9 Come(Paulo,Laranja)^~Morto(Paulo) U 8,7
10 Alimento(Laranja) MP 2,9
11 Vx(Alimento(x) -> Gosta(Pedro,x)) P
12 Alimento(Laranja) -> Gosta(Pedro,Laranja) IU 11
13 Gosta(Pedro,Laranja) MP 10,12

3. Candidatos

Luís, Paulo e Mário são candidatos a um mesmo cargo
Sabe-se que estes candidatos são oportunistas, ladrões ou ambos
Nenhum ladrão gosta de debates
Todos os oportunistas gostam de comícios
Paulo não gosta de nada que luís gosta e gosta de tudo que luís não gosta
luís gosta de comícios e debates
Existe algum candidato que seja ladrão, mas não seja oportunista?
Qual candidato é ladrão e não é oportunista?

Premissas em cálculo de predicados:

01- C(Lu)
02- C(Pa)
03- C(Ma)
04- Vx (C(x) -> L(x) \/ O(x))
05- Vx (L(x) -> ~ G(x,De))
06- Vx (O(x) -> G(x,Co))
07- G(Lu,x) -> ~ G(Pa,x)
08- ~ G(Lu,x) -> G(Pa,x)
09- G(Lu,Co)
10- G(Lu,De)

Teorema: Ex (C(x) ^ L(x) ^ ~O(x))
Usando Prova Direta

11- G(Lu,Co) P
12- Vx (G(Lu,x) -> ~ G(Pa,x)) P
13- Vx (G(Lu,Co) -> ~ G(Pa,Co)) IU 12
14- ~ G(Pa,Co) MP 11,13
15- Vx (O(x) -> G(x,Co)) P
16- O(Pa) -> G(Pa,Co) IU 15
17- ~ O(Pa) MT 14,16
18- Vx (C(x) -> L(x) \/ O(x)) P
19- C(Pa) -> L(Pa) \/ O(Pa) IU 18
20- C(Pa) P
21- L(Pa) \/ O(Pa) MP 19,20
22- L(Pa) SD 17,21
23- C(Pa) ^ L(Pa) ^ O(Pa) U17,20,22
24-Ex (C(x) ^ L(x) ^ ~O(x)) PD


4. Exercícios

. Provar os exercícios anteriores usando redução ao absurdo