|
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.
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.
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 leaisVxVy (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
Linguagem Natural |
Premissas em Lógica de Predicados |
Pedro gosta de todos os tipos de alimento | Vx(Alimento(x) -> Gosta(Pedro,x)) |
Maçãs são alimentos | Alimento(Maca) |
Galinha é alimento | Alimento(Galinha) |
Qualquer coisa que qualquer um coma e não morra é alimento | Vx,y (Come(x,y) ^ ~Morto(x) -> Alimento(y)) |
Paulo come laranja e ainda está vivo | Come(Paulo,Laranja) ^ Vivo(Paulo) |
Maria come tudo o que Paulo come | Vx (Come(Paulo,x) -> Come(Maria,x)) |
Vx (Vivo(x) -> ~Morto(x)) |
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