Baixe o app para aproveitar ainda mais
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.
Compartilhar