Autor Tema: Probar que es una tautología

0 Usuarios y 1 Visitante están viendo este tema.

08 Octubre, 2016, 08:16 pm
Leído 890 veces

energy

  • Experto
  • Mensajes: 561
  • Karma: +0/-0
  • Sexo: Masculino
Probar que dado una formula de logica proposicional, y solo usando el símbolo \( \Leftrightarrow{} \) es una tautología si y solo si el numero de apariciones de cada variable en la proposición es un numero par.

Pensé en construir una table de la verdad pero claro no es un razonamiento muy valido al no saber el numero de variables, si alguien puede orientarme en como demostrarlo se lo agradecería!

08 Octubre, 2016, 11:11 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,075
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Qué cosa más curiosa.

Se me ocurre este argumento (no sé si habrá otro más corto o más elegante):

Define recurrentemente:

\( [p_1]= p \), \( [p_1,\ldots, p_{n+1}]=[p_1,\ldots, p_n]\leftrightarrow p_{n+1} \).

Así, por ejemplo,

\( [p_1,p_2]=p_1\leftrightarrow p_2 \), \( [p_1,p_2, p_3]=(p_1\leftrightarrow p_2)\leftrightarrow p_3 \), etc.

Demuestra que \( [p,q,r]\leftrightarrow [p,r,q] \) y \( [p,q,r]\leftrightarrow [r,q,p] \) son tautologías.

Demuestra que \( [p_1,\ldots, p_n]\leftrightarrow [p_{\sigma 1},\ldots, p_{\sigma n}] \) es una tautología, para toda permutación \( \sigma \) de los índices.

Esto sale por inducción sobre \( n \). Claramente se cumple para \( n=1, 2 \). Supuesto cierto para \( n\geq 2 \), usa que

\( [p_1,\ldots, p_{n+1}] \) equivale a \( [p_1,\ldots, p_n]\leftrightarrow p_{n+1} \)

si \( \sigma(n+1)=i<n+1 \), por hipótesis de inducción, esto equivale a

\( [p_1, \ldots,\hat p_i,\cdots  p_n, p_i]\leftrightarrow p_{n+1} \)

(donde el circunflejo indica que falta ese término) que a su vez equivale a

\( [[p_1, \ldots, \hat p_i,\ldots, p_n], p_i, p_{n+1}] \)

que equivale a

\( [[p_1, \ldots, \hat p_i,\ldots, p_n], p_{n+1}, p_i] \)

que equivale a

\( [p_1, \ldots, \hat p_i,\ldots, p_n, p_{n+1}]\leftrightarrow  p_i \)

que por hipótesis de inducción equivale a

\( [p_{\sigma 1},\ldots,  p_{\sigma n}]\leftrightarrow  p_i = [p_{\sigma1},\ldots, p_{\sigma(n+1)}] \).

El caso \( \sigma(n+1)=n+1 \) es más fácil.

Prueba de forma similar que \( [p_1,\ldots, p_n]\leftrightarrow [q_1,\ldots, q_m] \) es equivalente a

\( [p_1,\ldots, p_n,q_m]\leftrightarrow [q_1,\ldots, q_{m-1}] \)

Repitiendo y reordenando, resulta que es equivalente a \( [p_1,\ldots, p_n, q_1, \ldots, q_m] \).

Prueba que toda fórmula \( A \) en la que aparezcan las variables \( p_1,\ldots, p_n \) (contando repeticiones) es equivalente a \( [p_1,\ldots, p_n] \).

Razona por inducción sobre la longitud de la fórmula. Si tiene longitud 1 es trivial y, supuesto cierto para fórmulas de longitud menor, tienes que \( A=B\leftrightarrow C \), aplica la hipótesis de inducción a B y C.

Podemos reordenar las variables de A de modo que A es equivalente a \( [p_1, p_1, p_2, p_2, \cdots, p_r, p_r, q_1, \ldots, q_s] \), donde \( q_1, \ldots, q_s \) son las variables (distintas dos a dos) que aparecen un número impar de veces.

Prueba que \( [p,p,q]\leftrightarrow q \). Deduce que \( [p, p, p_1, \ldots, p_n] \) es equivalente a \( [p_1,\ldots, p_n] \).

Concluye que si todas las variables aparecen en A un número par de veces, entonces A es una tautología, y en caso contrario \( A \) es equivalente a \( [q_1,\ldots, q_s] \), donde las \( q_i \) son las variables (distintas dos a dos) que aparecen un número impar de veces, por lo que A no es una tautología.