Exercícios de Lógica Aplicada à Computação

Prévia do material em texto

Lista de Exerc´ıcios Preparato´ria para o Exame do dia 27 de fevereiro de 2014
Lo´gica Aplicada a` Computac¸a˜o
Vivek Nigam
Exerc´ıcio 2
Exerc´ıcio 2-1. (dado em sala de aula!) Prove usando induc¸a˜o que para qualquer termo t e
substituic¸o˜es σ e τ temos que (tσ)τ = t(στ).
Exerc´ıcio 2-2. Um nu´mero primo e´ um nu´mero natural n tal que na˜o existem dois nu´mero
naturais diferentes de 1 cujo produto e´ igual a n. Defina uma interpretac¸a˜o I e uma fo´rmula F tal
que a fo´rmula abaixo e´ verdadeira:
∀x.(p(x)⇔ F )
onde pI = {n | n e´ primo}.
Exerc´ıcio 2-3. Construa um alfabeto da lo´gica de primeira ordem e um conjunto de formulas
que formalizam o problema da colorac¸a˜o de um grafo com no ma´ximo n no´s, grau de conexa˜o do
grafo ≤ m e com menos de k + 1 cores, onde:
• O grau um no´ e´ o nu´mero de no´s adjacentes;
• O grau de conexa˜o de um grafo e´ o ma´ximo dentre todos os graus de seus no´s;
• O problema de colorac¸a˜o de um grafo: dado um grafo (na˜o direcionado), associe uma cor a
cada no´ de tal forma que nenhum par de no´s adjacentes tem a mesma cor.
Mais sobre este problema veja http://pt.wikipedia.org/wiki/Colora%C3%A7%C3%A3o_de_grafos.
Exerc´ıcio 2-4. Prove (ou deˆ um contra-exemplo) usando as definic¸o˜es dadas em aula sobre a
teoria de modelos da lo´gica de primeira ordem que:
• � (∃x.p(x)⇒ ∀x.q(x))⇒ ∀x.(p(x)⇒ q(x));
• � (p(x)⇒ q(y))⇒ (∃x.p(x)⇒ ∃y.q(y));
Exerc´ıcio 2-5. Prove que as regras ∀R (e ∃L) na˜o sa˜o corretas se a varia´vel usada no lugar da
varia´vel quantificada na˜o for nova, i.e., aparecer na conclusa˜o da regra.
Exerc´ıcio 2-6. Prove por induc¸a˜o no tamanho de provas que se existe uma prova no sistema
de ca´lculo de sequentes da fo´rmula de primeira ordem A[c/x] onde c e´ uma constante nova, enta˜o
existe tambe´m uma prova sistema de deduc¸a˜o natural da fo´rmula de primeira ordem A[f(a)/x]
onde f e´ um s´ımbolo do conjunto de func¸o˜es e a um s´ımbolo do conjunto de constantes.
Exerc´ıcio Boˆnus. Existem va´rios sistemas de provas para diferentes lo´gicas. Investigue os
sistemas de provas para a lo´gica cla´ssica e para a lo´gica intuicionista. Discuta as suas diferenc¸as.
Veja http://pt.wikipedia.org/wiki/L%C3%B3gica_intuicionista e
http://pt.wikipedia.org/wiki/L%C3%B3gica_cl%C3%A1ssica