2026.01 Lista09 Recursao Teste

O documento é uma lista de exercícios da disciplina de Lógica Computacional da UFMG, focando em definições recursivas, indução estrutural e algoritmos recursivos. Os exercícios incluem perguntas sobre definições recursivas, cálculos de sequências e conjuntos de pares ordenados, além de problemas que requerem indução para demonstração. Também é solicitado o desenvolvimento de um algoritmo recursivo para encontrar o mínimo em um conjunto de números inteiros.

Enviado por

alexandregfc86

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

0% acharam este documento útil (0 voto)

0 visualizações2 páginas

2026.01 Lista09 Recursao Teste

Enviado por

alexandregfc86

Direitos autorais

Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.

Formatos disponíveis

Baixe no formato PDF, TXT ou leia on-line no Scribd

Área de Teoria DCC/UFMG Introdução à Lógica Computacional 2026/01

LISTA DE EXERCÍCIOS
Lista 09
(Definições Recursivas e Indução Estrutural, Algoritmos Recursivos)

Revisão.

1. Responda formalmente as seguintes perguntas:

(a) O que é uma definição recursiva? Quais os elementos essenciais de uma definição recursiva?

Exercı́cios.

2. (Rosen 4.3.3) Encontre f (2), f (3), f (4) e f (5) se f (n) for definido recursivamente por f (0) = −1,
f (1) = 2 e para n = 0, 1, 2, . . .:

(a) f (n + 1) = f (n)2 f (n − 1)
(b) f (n + 1) = 3f (n)2 − 4f (n − 1)2

3. (Rosen 4.3.7) Dê uma definição recursiva para a sequência {an }, n = 1, 2, 3, ... se

(a) an = 10n .
(b) an = 5.

4. (Rosen 4.3.8) Dê uma definição recursiva para a sequência {an }, n = 1, 2, 3, ... se

(a) an = 4n − 2.
(b) an = n(n + 1).

5. Nesta questão vamos generalizar os operadores de conjunção (∧) e de disjunção (∨) para um número
qualquer de operandos. Isto é feito de maneira similar como generalizamos
P a operação de soma (+)
de dois operandos para um número qualquer usando somatórios ( ).
Para isto, complete as seguintes definições recursivas, onde cada pi , com i ≥ 1, é uma proposição.
(V
0
pi =?,
(a) Generalização da conjunção: Vni=1
i=1 pi =?, n ≥ 1
(W
0
pi =?,
(b) Generalização da disjunção: Wi=1
n
i=1 pi =?, n ≥ 1

6. (Rosen 4.3.26) Seja S um subconjunto dos pares ordenados de inteiros, definido recursivamente por
Passo base: (0, 0) ∈ S,
Passo recursivo: Se (a, b) ∈ S, então (a + 2, b + 3) ∈ S e (a + 3, b + 2) ∈ S.

(a) Liste os elementos de S produzidos pelas 5 primeiras aplicações da definição recursiva.

(b) Utilize indução forte no número de aplicações do passo recursivo para mostrar que 5 | a+b quando
(a, b) ∈ S.
(c) Utilize indução estrutural para mostrar que 5 | (a, b) quando (a, b) ∈ S.

1
7. (Rosen 4.3.28) Dê uma definição recursiva para cada um dos conjuntos de pares ordenados de in-
teiros positivos. (Dica: Plote os pontos no plano e procure por linhas que contenham os pontos do
conjunto.)

(a) S = {(a, b) | a, b ∈ Z+ , a + b é ı́mpar}

(b) S = {(a, b) | a, b ∈ Z+ , a | b}

8. (Rosen 4.3.44) Use indução estrutural para mostrar que l(T ), o número de folhas de uma árvore binária
completa T , é 1 mais i(T ), o número de vértices internos de T .
(Lembre-se de que uma folha é um vértice conectado a no máximo um outro vértice da árvore, e um
vértice interno é um vértice conectado a dois ou mais vértices da árvore.)

9. (Rosen 4.4.11) Dê um algoritmo recursivo para encontrar o mı́nimo de um conjunto finito de números
inteiros, considerando o fato de que o mı́nimo de n números inteiros é o menor entre o último inteiro
da lista e o mı́nimo dos primeiros n − 1 elementos da lista. Exiba como seu algoritmo encontra o
mı́nimo elemento do conjunto {3, 5, 1, 2, 4}.

2026.01 Lista09 Recursao Teste

Enviado por

2026.01 Lista09 Recursao Teste

Enviado por

Área de Teoria DCC/UFMG Introdução à Lógica Computacional 2026/01

1. Responda formalmente as seguintes perguntas:

(a) Liste os elementos de S produzidos pelas 5 primeiras aplicações da definição recursiva.

(a) S = {(a, b) | a, b ∈ Z+ , a + b é ı́mpar}

Você também pode gostar