Exercício 13:
Defina substituição simultânea em uma L-fórmula varphi por indução na complexidade.

Passo 1

Estamos lidando com Lógica de Primeira Ordem: queremos definir a substituição simultânea de termos t1,dots,tn pelas variáveis x1,dots,xn em uma fórmula varphi, usando indução na complexidade da fórmula.
Definimos a medida de complexidade c(varphi) recursivamente:
  • Se varphi é atômica (da forma R(s1,dots,sm)) ou bot, então c(varphi)=0.
  • c(lnotpsi)=c(psi)+1.
  • c(psi1circpsi2)=c(psi1)+c(psi2)+1, onde circinland,lor,to,rightarrow.
  • c(Qy,psi)=c(psi)+1, onde Qinforall,exists.

Passo 2

Fazemos indução em c(varphi). Caso base ( c(varphi)=0):
  • Se varphi=R(s1,dots,sm), definimos
varphi[x1/t1,dots,xn/tn]=Rl(s1[x1/t1,dots,xn/tn],dots,sm[x1/t1,dots,xn/tn]r)
- Se varphi=bot, então
varphi[x1/t1,dots,xn/tn]=bot

Passo 3

Passo indutivo para conectivos ( c(varphi)>0):
  • Se varphi=lnotpsi,
varphi[x1/t1,dots,xn/tn]=lnotl(psi[x1/t1,dots,xn/tn]r)
- Se varphi=psi1circpsi2,
varphi[x1/t1,dots,xn/tn]=l(psi1[x1/t1,dots,xn/tn]r)circl(psi2[x1/t1,dots,xn/tn]r)

Passo 4

Passo indutivo para quantificadores: seja varphi=Qy,psi, com Qinforall,exists.
  • Se ynotinx1,dots,xn e y não ocorre em nenhum ti, então
varphi[x1/t1,dots,xn/tn]=Qyl(psi[x1/t1,dots,xn/tn]r)
- Caso yinx1,dots,xn ou y ocorra em algum ti, primeiro renomeamos y em varphi para uma variável z fresca, obtendo Qz,psi', e então aplicamos o passo anterior.

Passo 5

Dessa forma cobrimos todos os casos na indução sobre a complexidade de varphi.

Resposta

A substituição simultânea de termos t1,dots,tn pelas variáveis x1,dots,xn na fórmula varphi, denotada
varphi[x1/t1,dots,xn/tn],
é definida por indução na complexidade de varphi conforme os casos:
  1. Caso base ( c(varphi)=0):
    • Se varphi=R(s1,dots,sm), então
$$\varphi[x_1/t_1,\dots,x_n/t_n]=R\bigl(s_1[x_1/t_1,\dots,x_n/t_n],\dots,s_m[x_1/t_1,\dots,x_n/t_n]\bigr).
varphi[x1/t1,dots,xn/tn]=Rl(s1[x1/t1,dots,xn/tn],dots,sm[x1/t1,dots,xn/tn]r) ã\varphi[x_1/t_1,\dots,x_n/t_n]=\bot.
$$
  1. Conectivos ( varphi=bot):
    • Se varphi[x1/t1,dots,xn/tn]=bot , então
$$\varphi[x_1/t_1,\dots,x_n/t_n]=\lnot\bigl(\psi[x_1/t_1,\dots,x_n/t_n]\bigr).
c(varphi)>0ã\varphi[x_1/t_1,\dots,x_n/t_n]=\bigl(\psi_1[x_1/t_1,\dots,x_n/t_n]\bigr)\circ\bigl(\psi_2[x_1/t_1,\dots,x_n/t_n]\bigr).
$$
  1. Quantificadores: se varphi=lnotpsi com varphi[x1/t1,dots,xn/tn]=lnotl(psi[x1/t1,dots,xn/tn]r) :
    • Se varphi=psi1circpsi2 e circinland,lor,to,rightarrow não ocorre em nenhum varphi[x1/t1,dots,xn/tn]=l(psi1[x1/t1,dots,xn/tn]r)circl(psi2[x1/t1,dots,xn/tn]r) , então
$$\varphi[x_1/t_1,\dots,x_n/t_n]=Qy\bigl(\psi[x_1/t_1,\dots,x_n/t_n]\bigr).
$$
- Caso contrário, renomeie varphi=Qy,psi para uma variável fresca Qinforall,exists ( ynotinx1,dots,xn-conversão), escreva y e aplique o caso anterior.
Assim temos a definição completa por indução na complexidade de ti.

Exercícios relacionados