Buscar

pf-2013.1

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

UFPE / CIn/ Engenharia da Computação 
Lógica para Computação / Prova Final - 2013.1 - 24/09/2013 
Parte 1 – Lógica Proposicional 
1. (3,0) Escolha três dentre os métodos de prova estudados, para provar que: 
 
B C ⊢ (A B) (A C) 
 
2. (2,0) Prove por indução que para toda fórmula da lógica proposicional, o número de 
parênteses de é o dobro do número de conectivos de (os conectivos são , , e ). 
Defina formalmente as funções necessárias para a formalização do problema e depois faça a 
prova usando indução. 
 
Parte 2 – Lógica de Predicados 
 
3. (2,0) Use o princípio da resolução para provar se o seguinte argumento é válido no mundo de 
Tarski. 
 
 yTriângulo(y) 
É consequência lógica de : 
1. Pequeno(a) ( xQuadrado(x) y Triângulo(y)) 
2. Pequeno(a) xQuadrado(x) 
 
 
4. (3,0) Seja A a estrutura: 
(I) Domínio: O conjunto dos números inteiros; 
(II) Elementos de Destaque: os números 2 e 3; 
(III) Predicados e Relações: É-Par(unária), É-Primo(unária), Maior-Que(binária) 
(IV) Funções: soma (binária), subtração (binária), potência(binária). 
 
Obs(1): Para a relação “Maior-Que(a,b)”, deseja-se saber se a é maior do que b 
Obs(2): A função “potência(a,b)” retorna a exponenciação de b sobre a, isto é, a elevado a b 
 
4.1 Defina a assinatura de A, com suas respectivas interpretações e, usando tal assinatura, 
escreva as afirmações abaixo: 
(I) “Todo número elevado a 1 é igual a ele mesmo” ; 
(II) Conjectura de Goldbach: “Todo número par maior que 2 é igual à soma de dois números 
primos.” 
(III) Trio pitagórico: “Algum número quadrado perfeito pode ser escrito como a soma dos quadrados 
de dois números.” 
(IV) “O único número par que é primo é o número 2” 
4.2 Defina o diagrama positivo de A, usando todas as funções e, o predicado igualdade e cada 
símbolo de relação no mínimo duas vezes.

Outros materiais