Considerando o conjunto de números naturais na notação de Peano (Definição 2), desenvolva as seguintes operações:
Desenvolva uma função eq: N N B, que a partir de dois números naturais na notação de Peano, retorne T se estes forem iguais e F caso contrário.

Passo 1

Beleza, vamos lá! O exercício pede para a gente desenvolver uma função de igualdade, chamada eq, que recebe dois números naturais na notação de Peano e retorna T se eles forem iguais ou F 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 0, e cada número seguinte é o sucessor do anterior. Ou seja:
  • 0 é um número natural.
  • Se n é um número natural, então S(n) também é, onde S representa o “sucessor” de n.
Então, os primeiros números naturais na notação de Peano são:
  • 0
  • S(0), que é 1
  • S(S(0)), que é 2
  • 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:
  1. Se ambos os números forem 0, eles são iguais.
  2. Se um deles for 0 e o outro não, eles são diferentes.
  3. Se ambos forem sucessores de algum número, então precisamos comparar os números anteriores.
Com base nisso, podemos definir a função eq de forma recursiva.

Passo 4

Vamos definir a função eq formalmente. Ela vai receber dois números naturais, digamos a e b, e retornar T se a for igual a b, ou F caso contrário. A definição fica assim:
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)

Passo 5

Vamos entender cada caso da definição:
  1. Primeiro caso: Se ambos a e b são 0, então eles são iguais, então retornamos T.
  2. 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.
  3. 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.
  4. 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)

Exercícios relacionados