Teoria da Computacao

aula 14: Predicados recursivos primitivos

1 Introducao

Na aula passada, nos mostramos como definir algumas funcoes aritmeticas simples no formalismoPR. O desenvolvimento natural, a seguir, seria mostrar como essas funcoes podem ser utilizadaspara definir funcoes mais complexas. Mas, antes disso, nos precisamos introduzir algumasferramentas uteis.

Um elemento essencial para a construcao de funcoes complexas consiste em testar condicoes efazer a funcao se comportar de maneiras diferentes em situacoes diferentes. Por exemplo, umafuncao que e capaz de distinguir se o seu argumento x e par ou mpar, retornando x + 2 noprimeiro caso e x + 1 no segundo caso, calcula o sucessor par do numero x, o que talvez sejautil algum dia.

Para isso, hoje nos vamos mostrar como trabalhar com predicados e conectivos logicos no for-malismo PR. Um predicado e simplesmente uma funcao que retorna apenas os valores 0 ou 1.Informalmente, assumimos que o numero 0 corresponde ao valor logico Falso, e que o numero1 corresponde ao valor logico Verdadeiro.

2 Alguns predicados uteis

A seguir, temos alguns exemplos de predicados simples que podem ser definidos utilizando oformalismo das funcoes recursivas primitivas.

a. Nosso primeiro predicado e a funcao Sg1 definida por

Sg(x) =

{0 , se x = 0

1 , caso contrario

Informalmente, nos podemos imaginar que a funcao Sg (signal, em ingles) retorna o sinalde um numero natural. Isto e, ela indica se o numero e diferente de zero (positivo) ou iguala zero (negativo).

Vamos definir o predicado Sg utilizando a regra de recursao primitiva. O caso base e facil,e, para o caso geral, podemos utilizar qualquer funcao aritmetica que sempre retorne o valor1. Isso nos da algo como:{

Sg(0) = z(x)

Sg(x+ 1) = 1(x) = 1(u21(x, Sg(x))

)

b. O predicado Z(x) se comporta de maneira inversa ao anterior, e indica se o argumento xe igual a zero. Esse exemplo tambem poderia ser definido por meio da recursao primitiva,mas podemos escrever simplesmente

Z(x) = 1 Sg(x)

1Para distingu-los das funcoes aritmeticas, nos vamos utilizar letras maiusculas para denotar os predicados

1

c. A seguir, nos vamos definir o predicado Evev(x), que indica se o argumento x e um numeropar.

A ideia e utilizar a regra da recursao primitiva. O caso base e simples, pois sabemos que 0e um numero par. Assim, vamos definir Even(0) = 1(x). Para o caso geral, basta observarque x e um numero par se e somente se x 1 nao e par. Portanto, se temos o valor deEven(x), basta inverte-lo para obter o valor de Even(x + 1). A definicao completa ficaassim:{

Even(0) = 1(x)

Even(x+ 1) = 1 Even(x) = sub(1(u11(x,Even(x))), u2

2(x,Ev(x)))

d. Uma vez que temos o predicado Even, e facil definir o predicado Odd(x), que indica se oargumento x e um numero mpar, como

Odd(x) = 1 Even(x)

e. O predicado Gt(x, y) (greater than) indica se o argumento x e maior do que o argumento y.

Como ja mostramos na aula passada a definicao da operacao de subtracao no formalismoPR, basta utilizar o predicado Sg para verificar se o resultado da subtracao x y e diferentede zero:

Gt(x, y) = Sg(x y)

f. O predicado Eq(x, y) indica se o argumento x e igual ao argumento y.

Utilizando uma ideia semelhante ao exemplo anterior, nos podemos escrever:

Eq(x, y) = Z(|x y|)

onde a funcao |x y| foi definida na aula passada.

2.1 Conectivos booleanos

Da mesma maneira que as funcoes aritmeticas complexas sao obtidas pela combinacao de funcoesaritmeticas mais simples, os predicados complexos correspondem a proposicoes logicas que com-binam predicados simples utilizando os conectivos de negacao (), conjuncao () e disjuncao().

Antes de colocar essa ideia em pratica, e preciso mostrar que essas operacoes logicas basicascorrespondem a funcoes recursivas primitivas.

Teorema 1: Suponha que P e Q sao predicados recursivos primitivos. Entao, os predicadosP , P Q e P Q tambem sao recursivos primitivos.

Prova: Para ver que P e P Q sao recursivos primitivos, observe que

P (x) = 1 P (x) e(P Q

)(x) = P (x) Q(x)

Finalmente, para ver que P Q tambem e recursivo primitivo, basta aplicar a lei de Morgan:(P Q

)(x) =

(P Q

)(x)

2

Agora que temos os conectivos logicos, e facil mostrar que os seguintes predicados tambem saorecursivos primitivos:

g. Neq(x, y): indica se x e diferente de y.

Neq(x, y) = Eq(x, y)

h. Gte(x, y): indica se x e maior ou igual a y.

Gte(x, y) = Gt(x, y) Eq(x, y)

3 Esquema de definicao por casos

Um recurso bastante util quando especificamos uma funcao consiste em utilizar expressoesdiferentes para descrever o seu comportamento em diferentes partes do domnio. Por exemplo,a funcao sucessor par mencionada na Introducao:

sp(x) =

{x+ 2 , se x e par

x+ 1 , se x e mpar

Esse esquema e conhecido como definicao por casos, e temos o seguinte resultado:

Teorema 2: Suponha que g, h PR, e que P e um predicado recursivo primitivo. Entao, afuncao

f(x1, . . . , xn) =

{g(x1, . . . , xn) , se P (x1, . . . , xn)

h(x1, . . . , xn) , caso contrario

tambem e recursiva primitiva.

Prova: Basta observar quef = g P + h P

Exemplo

i. Agora, a funcao sucessor par pode ser obtida como uma aplicacao direta desse resultado:

sp(x) =

{x+ 2 , se Ev(x)

x+ 1 , caso contrario

3.1 Aplicacao: a operacao de divisao em PR

Quando nos apresentamos, na aula passada, as definicoes em PR para diversas operacoes ar-itmeticas, uma notavel omissao foi a operacao de divisao. A seguir, nos veremos que essaoperacao de fato requer um pouco mais de recursos para ser definida.

Vamos comecar com o caso mais simples da divisao por 2.

3

j. d2(x) = x2

Essa funcao pode ser definida pela regra de recursao primitiva, incrementando o valor dafuncao uma vez a cada duas iteracoes da recursao. Essa ideia pode ser implementada uti-lizando o predicado Ev(x) e o esquema de definicao por casos que acabamos de apresentar.{

d2(0) = 0

d2(x+ 1) = g(x, d2(x))

onde

g(a, b) =

{b+ 1 , se a e mpar

b , se a e par

A ideia aqui e que, se x e mpar entao (x + 1) e par e da que d2(x + 1) = d2(x) + 1. Porexemplo, 6

2

= 3 = 2 + 1 =

52

+ 1

No caso em que x e par temos que (x + 1) e mpar, e portanto d2(x + 1) = d2(x). Porexemplo, 7

2

= 3 =

62

Nao e difcil ver que essa ideia tambem pode ser utilizada para calcular a divisao por 3. Mas,para isso, e preciso definir mod3(x), que calcula o resto da divisao por 3. Essa funcao tem umalogica muito parecida com o predicado Ev(x).

l. mod3(x) : calcula o resto da divisao de x por 3

Se examinarmos a definicao do predicado Ev(x), podemos ver que ela efetivamente calculauma sequencia da forma:

1, 0, 1, 0, 1, 0, 1, 0, . . .

onde o ultimo elemento da sequencia e igual a 1 se e somente se o numero x e par.

Essa observacao nos da a ideia de que, para calcular o resto da divisao por 3, basta calcularuma sequencia da forma:

0, 1, 2, 0, 1, 2, 0, 1, . . .

onde o ultimo elemento da sequencia e o resultado que desejamos.

Isso pode ser feito da seguinte maneira:{mod3(0) = 0

mod3(x+ 1) = g(x,mod3(x))

onde

g(a, b) =

{z(b) , se b = 2

s(b) , caso contrario

Uma vez que a funcao mod3(x) esteja definida obtemos imediatamente o predicado que indicase o argumento e divisvel por 3:

Div3(x) = Z(mod3(x))

e tambem a operacao de divisao por 3:

4

m. d3(x) = x3

{d3(0) = z(x)

d3(x+ 1) = g(x, d3(x))

onde

g(a, b) =

{b+ 1 , se mod3(a) = 2

b , caso contrario

Exerccios

1. Generalize o resultado da Secao 4 definindo, para k N fixo, a funcao dk(x) = x/k.

2. Apresente uma definicao no formalismo PR para a operacao de divisao: div(x, y) = xy

5