Una es una proposición fórmula que contiene sólo el fib. A es una tautología iff cada proposición atómica en Una aparece un número par de veces.

Question

Acabo de empezar el estudio de la Lógica Matemática y estoy teniendo problemas para encontrar una simple prueba del siguiente ejercicio.
Dejar que Un ser de una fórmula proposicional que contiene sólo el $\equiv$ conectivo. Para aquellos que no están familiarizados con ella $f_\equiv(T,T)=f_\equiv(F,F)=T$$f_\equiv(F,T)=f_\equiv(T,F)=F$.
Demostrar que Una es una tautología si y sólo si cada proposición atómica que aparece en Una aparece un número par de veces.
He logrado encontrar una complicada prueba mediante inducciones y el hecho de que $\equiv$ es tanto conmutativa y asociativa, pero no creo que este fue el punto del ejercicio. Cualquier ayuda se agradece.

Answer 1

Creo que estás en el camino correcto. Puede utilizar la inducción para demostrar los siguientes:

Lema

Cualquier declaración de $\phi$ acumulado desde atómica declaraciones y $\equiv$'s solo es verdadera si y sólo si contiene un número par de casos de falsos atómica declaraciones

Prueba por inducción estructural sobre sintáctica formación de $\phi$:

Base: $\phi = A$ para algunos atómica A. por Lo que sería Cierto si a es Verdadero, es decir, iff $\phi$ contiene un número par (0) de casos de falsos atómica declaraciones. Comprobar!

Paso: Considerar cualquier declaración de $\phi \equiv \psi$. Asumir la hipótesis inductiva se tiene para $\phi$$\psi$. Ahora: $\phi \equiv \psi$ es verdadero si cualquiera de los dos $\phi$ $\psi$ son verdaderas o ambas son falsas iff (inductivo hypothses) de cualquiera de los dos $\phi$ $\psi$ contiene un número par de casos de falsos atómica declaraciones o ambas $\phi$ $\psi$ contienen un número impar de casos de falsos atómica declaraciones iff $\phi \equiv \psi$ contiene un número par de casos de falsos atómica declaraciones. Comprobar!

OK, así que ahora podemos probar lo que usted necesita para probar:

Teorema de

Cualquier declaración de $\phi$ acumulado desde atómica declaraciones y $\equiv$'s solo es una tautología si y sólo si cada proposición atómica que aparece en $\phi$ aparece un número par de veces.

Prueba:

'si': Si cada proposición atómica que aparece en $\phi$ aparece un número par de veces, luego de lo $\phi$ contiene un número par de casos de falsos atómica declaraciones, independientemente de que se configure cualquiera de las proposiciones atómicas a Verdadero o Falso. Por lo tanto, por el Lema, $\phi$ siempre será verdad, es decir, $\phi$ es una tautología.

'sólo si' Prueba por contradicción: Supongamos $A$ es atómica declaración en la que se produce un número impar de veces en $\phi$. Entonces si partimos $A$ a False, y todos los otros atómica declaraciones en $\phi$ a Verdad, que acabaría con un número impar de casos de falsos atómica declaraciones en $\phi$, por tanto, por el Lema de esta amuma que $\phi$ es Falso, y por lo tanto no es una tautología. Por lo tanto, si $\phi$ es una tautología, cualquier proposición atómica que aparece en $\phi$ debe aparecer un número par de veces.

Answer 2

Me gustaría probar la propiedad conmutativa, la asociativa de la propiedad, ($\alpha$ fib $\alpha$) = T, y ($\alpha$ fib T) = $\alpha$.

A continuación, se sigue que cualquier fórmula con un número de instancias de una atómica frases, que usted puede utilizar la conmutación y de la asociación para eliminar a los dos en una T. por Lo tanto, cualquier fórmula con un número de instancias de atómica penas tiene valor de verdad de T.

Por el contrario, cada fórmula puede obtener construido a partir de T, que a decir (p iff p), entonces ((q iff q) iff p) y así sucesivamente y, a continuación, el uso de la conmutación y de la asociación para la construcción de la fórmula.