Definición inductiva de una fórmula mediante inducción estructural

Question

Si me dan una fórmula bien formada $\varphi$ que sólo tiene los símbolos lógicos $\land,\lor,\neg$ . Quiero definir una fórmula $\varphi^*$ que resulta de cambiar cada signo $\land$ a $\lor$ y cada $\lor$ a $\land$ y cada átomo a su negación en $\varphi$ .

Así que pensé en definir $\varphi^*$ será :

Escalón base : $\varphi$ es un átomo, entonces $\varphi^*=\neg{\varphi}$ .

Paso de inducción : Aquí no estoy teniendo un pensamiento claro acerca de la definición de este así que estaba pensando en dejar que $\alpha,\beta\in{WFF}$ que satisfagan $\varphi$ .entonces me puse algunos ejemplos y vi que necesitaba aplicar la negación a las fórmulas $\alpha,\beta$ que construyen $\varphi$ basado en el recuento $\land$ , $\lor$ .

Mis ejemplos:

$\varphi=(p_1\land p_2)\implies \varphi^*=\neg\varphi$ .

$\varphi=(p_1\land p_2)\lor p_3 \implies\varphi^*=\neg\neg\varphi$

¿Es correcto?

Answer 1

Nota terminológica: en realidad no existe tal cosa como una "definición inductiva". Más bien, lo que se intenta es llegar a una definición recursiva .

Sin embargo, una vez establecida dicha definición recursiva, se puede utilizar inducción estructural para probar cosas al respecto.

Por ejemplo, utilizando la definición recursiva dada por @Taroccoesbrocco, podemos demostrar por inducción estructural que $\varphi^* \Leftrightarrow \neg \varphi$ (Yo no diría $\varphi^* = \neg \varphi$ ya que en el contexto de la metalogía el $=$ ' se utiliza para indicar que las dos fórmulas son sintáctica/simbólicamente la misma cadena de símbolos, mientras que, por supuesto, usted sólo quiere demostrar la equivalencia lógica, para lo cual utilizamos $\Leftrightarrow$ )

Bien, aquí va esa prueba:

Base: $\varphi$ es atómica. Entonces, por definición, $\varphi^* = \neg \varphi$

Paso: Hay que tener en cuenta tres casos:

Supongamos que $\varphi = \neg \varphi_1$ . Por hipótesis inductiva podemos suponer $\varphi_1^* \Leftrightarrow \neg \varphi_1$ . Pero eso significa que $\varphi^* = (\neg \varphi_1)^* = \neg \varphi_1* \Leftrightarrow \neg \neg \varphi_1 = \neg \varphi$

Supongamos que $\varphi = \varphi_1 \land \varphi_2$ . Por hipótesis inductiva podemos suponer $\varphi_1^* \Leftrightarrow \neg \varphi_1$ y $\varphi_2^* \Leftrightarrow \neg \varphi_2$ . Por lo tanto: $\varphi^* = (\varphi_1 \land \varphi_2)^* = \varphi_1^* \lor \varphi_2^* \Leftrightarrow \neg \varphi_1 \lor \neg \varphi_2 \Leftrightarrow \neg (\varphi_1 \land \varphi_2) = \neg \varphi $

Supongamos que $\varphi = \varphi_1 \lor \varphi_2$ . Por hipótesis inductiva podemos suponer $\varphi_1^* \Leftrightarrow \neg \varphi_1$ y $\varphi_2^* \Leftrightarrow \neg \varphi_2$ . Por lo tanto: $\varphi^* = (\varphi_1 \lor \varphi_2)^* = \varphi_1^* \land \varphi_2^* \Leftrightarrow \neg \varphi_1 \land \neg \varphi_2 \Leftrightarrow \neg (\varphi_1 \lor \varphi_2) = \neg \varphi $

Answer 2

La etapa de inducción corresponde a los casos $\varphi = \lnot \varphi_1$ , $\varphi = \varphi_1 \lor \varphi_2$ y $\varphi = \varphi_1 \land \varphi_2$ donde $\varphi_1$ y $\varphi_2$ son fórmulas bien formadas que sólo tienen los símbolos lógicos $\lnot$ , $\lor$ y $\land$ . Por hipótesis de inducción, $\varphi_1^*$ y $\varphi_2^*$ ya está definida (éste es el aspecto "mágico" de las definiciones por inducción), por lo que sólo hay que establecer:

1. $\varphi^* := \lnot (\varphi_1^*)$ si $\varphi = \lnot \varphi_1$ ,
2. $\varphi^* := \varphi_1^* \land \varphi_2^*$ si $\varphi = \varphi_1 \lor \varphi_2$ ,
3. $\varphi^* := \varphi_1^* \lor \varphi_2^*$ si $\varphi = \varphi_1 \land \varphi_2$ .