Considerando o conjunto de números naturais na notação de Peano (Definição 2), desenvolva as seguintes operações:
Desenvolva uma função , que a partir de dois números naturais na notação de Peano, retorne se estes forem iguais e caso contrário.
Passo 1
Beleza, vamos lá! O exercício pede para a gente desenvolver uma função de igualdade, chamada , que recebe dois números naturais na notação de Peano e retorna se eles forem iguais ou se não forem. Para resolver isso, vamos precisar entender um pouco sobre os números naturais na notação de Peano e como comparar dois desses números passo a passo.
Passo 2
Primeiro, vamos relembrar o que é a notação de Peano. Na definição de Peano, os números naturais começam com , e cada número seguinte é o sucessor do anterior. Ou seja:
é um número natural.
Se é um número natural, então também é, onde representa o “sucessor” de .
Então, os primeiros números naturais na notação de Peano são:
, que é
, que é
E assim por diante.
Passo 3
Agora, para comparar dois números naturais na notação de Peano, precisamos verificar passo a passo se eles são iguais. Vamos pensar em como isso funciona:
Se ambos os números forem , eles são iguais.
Se um deles for e o outro não, eles são diferentes.
Se ambos forem sucessores de algum número, então precisamos comparar os números anteriores.
Com base nisso, podemos definir a função de forma recursiva.
Passo 4
Vamos definir a função formalmente. Ela vai receber dois números naturais, digamos e , e retornar se for igual a , ou caso contrário. A definição fica assim:
Passo 5
Vamos entender cada caso da definição:
Primeiro caso: Se ambos a e b são 0, então eles são iguais, então retornamos T.
Segundo caso: Se a é 0 e b é um sucessor de algum número (S(n)), então eles não são iguais, então retornamos F.
Terceiro caso: Se a é um sucessor de algum número (S(m)) e b é 0, novamente eles não são iguais, então retornamos F.
Quarto caso: Se ambos a e b são sucessores de algum número (S(m) e S(n) respectivamente), então precisamos comparar os números anteriores m e n.
Essa abordagem recursiva garante que, se todos os predecessores forem iguais, os números também serão iguais.
Resposta
Portanto, a função eq que compara dois números naturais na notação de Peano é definida por:
eq(a, b) = T & se a = 0 e b = 0 F & se a = 0 e b = S(n) para algum n F & se a = S(m) para algum m e b = 0 eq(m, n) & se a = S(m) e b = S(n)