03 Abril, 2020, 07:30 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a aladan
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Probar que es una tautología  (Leído 827 veces)
0 Usuarios y 1 Visitante están viendo este tema.
energy
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 561



Ver Perfil
« : 08 Octubre, 2016, 15:16 »

Probar que dado una formula de logica proposicional, y solo usando el símbolo [texx]\Leftrightarrow{}[/texx] 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!
En línea
Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 9.091


Ver Perfil WWW
« Respuesta #1 : 08 Octubre, 2016, 18:11 »

Qué cosa más curiosa.

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

Define recurrentemente:

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

Así, por ejemplo,

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

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

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

Esto sale por inducción sobre [texx]n[/texx]. Claramente se cumple para [texx]n=1, 2[/texx]. Supuesto cierto para [texx]n\geq 2[/texx], usa que

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

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

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

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

[texx][[p_1, \ldots, \hat p_i,\ldots, p_n], p_i, p_{n+1}][/texx]

que equivale a

[texx][[p_1, \ldots, \hat p_i,\ldots, p_n], p_{n+1}, p_i][/texx]

que equivale a

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

que por hipótesis de inducción equivale a

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

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

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

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

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

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

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 [texx]A=B\leftrightarrow C[/texx], aplica la hipótesis de inducción a B y C.

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

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

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 [texx]A[/texx] es equivalente a [texx][q_1,\ldots, q_s][/texx], donde las [texx]q_i[/texx] son las variables (distintas dos a dos) que aparecen un número impar de veces, por lo que A no es una tautología.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!