Considerando o conjunto de números naturais na notação de Peano (Definição 2), desenvolva as seguintes operações:
Desenvolva uma função leq:
, que a partir de dois números naturais na notação de Peano, retorne
se o primeiro for menor ou igual ao segundo e
, caso contrário.
Desenvolva uma função leq:
Passo 1
Beleza, vamos lá! O exercício pede para a gente trabalhar com números naturais na notação de Peano. Basicamente, isso significa que a gente vai representar os números naturais (0, 1, 2, …) usando o método de Peano, que começa com o zero e usa a função sucessor para chegar nos outros números.
A tarefa aqui é desenvolver uma função chamada leq que recebe dois números naturais nessa notação e retorna T (verdadeiro) se o primeiro número for menor ou igual ao segundo, e F (falso) se não for. Para resolver isso, vamos precisar entender bem como os números são representados na notação de Peano e como comparar dois números usando essa representação.
Passo 2
Primeiro, vamos relembrar como funciona a notação de Peano para os números naturais. Na notação de Peano:
- 0 é o primeiro número natural.
- Cada número natural tem um sucessor. Por exemplo, o sucessor de 0 é 1, o sucessor de 1 é 2, e assim por diante.
Então, podemos representar os números assim:
- 0
- S(0) = 1
- S(S(0)) = 2
- S(S(S(0))) = 3
- E por aí vai…
Essa forma de representar os números é útil porque permite definir operações como igualdade, adição e, no nosso caso, a função leq de maneira recursiva.
Passo 3
Agora, vamos pensar em como comparar dois números nessa notação. A ideia é que vamos comparar dois números naturais chamando-os de x e y.
A função leq(x, y) deve retornar T se x for menor ou igual a y, e F caso contrário. Para isso, vamos definir a função de forma recursiva, ou seja, ela vai se auto chamar com números menores até chegar a um caso base.
Aqui estão os casos que vamos considerar:
-
Caso Base 1: Se x for 0, então x é sempre menor ou igual a y, independentemente de y. Logo, leq(0, y) = T.
-
Caso Base 2: Se y for 0 e x não for 0, então x não pode ser menor ou igual a y. Logo, leq(S(x’), 0) = F, onde x’ é um número natural qualquer.
-
Caso Recursivo: Se ambos x e y forem sucessores, ou seja, x = S(x’) e y = S(y’), então leq(S(x’), S(y’)) depende de leq(x’, y’). Isso significa que para comparar S(x’) e S(y’), a gente compara x’ com y’.
Passo 4
Agora, vamos formalizar a definição da função leq usando o que discutimos:
Vamos explicar cada parte:
-
Se x = 0: Como vimos, 0 é sempre menor ou igual a qualquer número natural, então retornamos T.
-
Se y = 0 e x ≠ 0: Se y for 0 mas x não for, então x não pode ser menor ou igual a y, então retornamos F.
-
Se x = S(x’) e y = S(y’): Se ambos os números são sucessores, a gente simplifica a comparação removendo o sufixo S e chama a função novamente para comparar os números anteriores (x’ e y’).
Passo 5
Vamos ver um exemplo para entender melhor:
Vamos comparar 2 e 3 usando a notação de Peano:
- 2 é representado como S(S(0))
- 3 é representado como S(S(S(0)))
Aplicando a função leq:
-
leq(S(S(0)), S(S(S(0))))
Como ambos são sucessores, vamos comparar leq(S(0), S(S(0))) -
leq(S(0), S(S(0)))
Novamente, ambos são sucessores, então comparamos leq(0, S(0)) -
leq(0, S(0))
Quando x = 0, retornamos T
Então, leq(2, 3) = T, o que faz sentido porque 2 é menor que 3.
Resposta
A função leq definida na notação de Peano é:
Essa função compara dois números naturais na notação de Peano e retorna T se o primeiro for menor ou igual ao segundo, e F caso contrário.