exercicio-1

Prévia do material em texto

Lista de Exerc´ıcios Preparato´ria para o Exame do dia 22 de maio de 2014
Lo´gica Aplicada a` Computac¸a˜o
Vivek Nigam
Exerc´ıcio 1
Exerc´ıcio 1-1. Prove que o conjunto de todos os subconjuntos finitos dos nu´meros naturais e´
conta´vel
Exerc´ıcio 1-2. Cada um dos n cientistas famosos que se encontram em uma confereˆncia (onde
n ≥ 2) querem apertar a ma˜o dos outros cientistas famosos. Descubra quantos apertos de ma˜o
havera˜o e prove por induc¸a˜o que a sua descoberta esta´ correta.
Exerc´ıcio 1-3. (dado em sala de aula!) Prove o teorema da consequeˆncia lo´gica: Teorema:
Para quaisquer fo´rmulas G,F1, . . . , Fn, temos que F1, . . . , Fn � G se e somente se � (F1 ∧ F2 ∧
· · · ∧ Fn)⇒ G.
Exerc´ıcio 1-4. (dado em sala de aula!) Prove o teorema da substituic¸a˜o por induc¸a˜o: Se
G ≡ H, enta˜o F [G] ≡ F [H].
Exerc´ıcio 1-5. (dado em sala de aula!) Explique com as suas pro´prias palavras corretude e
completude. Qual e´ melhor?
Exerc´ıcio 1-6. Defina recursivamente o conjunto de a´rvores bina´rias contendo um nu´mero na-
tural qualquer em cada um dos seus no´s. Dizemos que uma a´rvore bina´ria tem a propriedade Heap
se o valor em qualquer no´ X tem valor maior ou igual aos valores nas suas crianc¸as, i.e., seus
descendentes imediatos. Por exemplo, a seguinte a´rvore tem a propriedade Heap:
32
uu ))
19
zz ##
12
{{ ##
18 8 9 1
Prove por induc¸a˜o que o valor na raiz de qualquer a´rvore bina´ria com a propriedade Heap tem
valor maior ou igual a qualquer no´ na a´rvore.
Exerc´ıcio 1-7. Questa˜o Boˆnus (1 ponto) No dia do exame, quem quiser pode-se candida-
tar a responder esta questa˜o. Se responder corretamente, recebera´ 2 pontos na pro´xima lista de
exerc´ıcios:
Prove que existem conjuntos inconta´veis, quer dizer, que na˜o tem um isomorfismo com o
conjunto dos nu´meros naturais.
Dica: Veja a argumento de diagonalizac¸a˜o de Cantor descrito no link abaixo:
http://en.wikipedia.org/wiki/Cantor’s_diagonal_argument