Trabalho Trabalho

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (337 palavras )
  • Download(s) : 0
  • Publicado : 24 de novembro de 2013
Ler documento completo
Amostra do texto
Lista de Exerc´
ıcios Preparat´ria para o Exame do dia 05 de dezembro de 2013
o

L´gica Aplicada a Computa¸˜o
o
`
ca
Vivek Nigam
Exerc´ 1
ıcio

Exerc´
ıcio 1-1. DefinaSeq(C) como o conjunto de todas as sequˆncias finitas de elementos do
e
conjunto C. Por exemplo, se C = {1, 2, 3}, ent˜o a sequˆncia 1.2.1 ∈ Seq(C). Demonstre que se A
a
e
´ umconjunto cont´vel, ent˜o o conjunto de todas as suas sequˆncias Seq(A) ´ tamb´m cont´vel.
e
a
a
e
e
e
a

Exerc´
ıcio 1-2. (dado em sala de aula!) Prove por indu¸˜o que qualquern´mero natural
ca
u
pode ser representado por uma soma de n´meros Fibonacci distintos. Por exemplo, 10 = 8 + 2;
u
15 = 8 + 5 + 2. Vejahttp://en.wikipedia.org/wiki/Zeckendorf’s_theorem

Exerc´
ıcio 1-3. (dado em sala de aula!) Prove o teorema da consequˆncia l´gica: Teorema:
e
o
Para quaisquer f´rmulas G, F1 , . . . , Fn , temos que F1 , . . . , Fn G se esomente se (F1 ∧ F2 ∧
o
· · · ∧ Fn ) ⇒ G.

Exerc´
ıcio 1-4. (dado em sala de aula!)
G ≡ H, ent˜o F [G] ≡ F [H].
a

Exerc´
ıcio 1-5. (dado em sala de aula!)
e quais as suasconsequˆncias.
e

Exerc´
ıcio 1-6.

Prove o teorema da substitui¸˜o por indu¸˜o: Se
ca
ca

Explique o que diz o teorema de elimina¸˜o de cortes
ca

Explique com as suaspr´prias palavras o que significa corretude e completude.
o

Exerc´
ıcio 1-7. Quest˜o Bˆnus (1 ponto) No dia do exame, quem quiser pode-se candidaa
o
tar a responder estaquest˜o. Se responder corretamente, receber´ 2 pontos na pr´xima lista de
a
a
o
exerc´
ıcios:
Prove que existem conjuntos incont´veis, quer dizer, que n˜o tem um isomorfismo com o
a
aconjunto dos n´meros naturais.
u
Dica: Veja a argumento de diagonaliza¸˜o de Cantor descrito no link abaixo:
ca
http://en.wikipedia.org/wiki/Cantor’s_diagonal_argument

tracking img