Cómo es $((X\to Y)\to X)\to X$ una tautología?

Question

$((X \rightarrow Y ) \rightarrow X) \rightarrow X$ convertido a su forma normal disyuntiva es $X' + X$.

¿Por qué/cómo hace este show me de por qué esta fórmula una tautología?

Answer 1

La fórmula en cuestión se llama de Peirce de la ley. Es notable en el caso de que su prueba requiere (en una u otra forma) de la ley de medio excluido, que dice que cada afirmación es verdadera o falsa. Así que usted puede argumentar de la siguiente manera:

Cualquiera de las $X$ es verdadero, en cuyo caso..., o $X$ es falso, en cuyo caso..., y en cualquier caso se sigue que $(((X \to Y)\to X)\to X)$ es cierto.

EDIT: acabo de darme cuenta de que la pregunta de cómo mirar la forma normal disyuntiva , en particular, muestra que de Peirce, la ley es una tautología. Así, la disyuntiva forma normal como usted ha escrito que dice "no-$X$ o $X$", que es una instancia de la ley del medio excluido.

Answer 2

$X' + X$ es una tautología, porque sabemos que $X' + X$ significa que, o $X$ o no $X$, que es siempre verdadera, independientemente del valor de verdad de $X$.

Si $X$ es verdadera, entonces también lo es $X \lor \lnot X.\;$ Si $X$ es falsa, entonces la $\lnot X = X'$ es verdadero, y por lo tanto, también lo es $\;\lnot X \lor X$. Y por favor, tenga en cuenta que, de hecho, $$\text{True}\;\equiv X' + X \equiv X' + X + Y \equiv X' + X + Y' \equiv ((X \rightarrow Y) \rightarrow X)\rightarrow X \equiv \text{ TRUE}$$

Así tenemos que la expresión original no depende de la verdad-los valores de $X$ o de $Y$. La cada de equivalencia anterior es cierto para cualquier valor de verdad de la asignación que le damos a $X$$Y$.

Answer 3

$X + X' = \top$. (o tal vez el uso de $1$ en lugar de $\top$)

Me han dicho que $\top$ es también un DNF... pero la definición en la wikipedia excluye vacía productos, y yo estaría unsurprised si esta es la norma. :(

Answer 4

Sobre qué base se puede convertir (((X→Y)→X)→X) a (X'+X)? Lo que hace que sea un proceso válido, en primer lugar? Qué utilizar al realizar un proceso de conversión?

Vamos a ver cómo podemos hacerlo. Podemos comenzar con

(((X→Y)→X)→X)

y obtener

(((X'+Y)→X)→X).

Esto lo hicimos sobre la base de la equivalencia que dice que para todo X, para todo Y, [(X→Y)==(X'+Y)]. El uso de un par de veces más a continuación, podemos obtener:

(((X'+Y)'+X)'+X).

A continuación, utilizando otra lógica de la equivalencia que dice que para todo X, para todo Y, [(X+Y)'==(X'$\land$S')], podemos obtener:

(((X"$\land$Y')+X)'+X).

Ahora, en el fin de responder a por qué este proceso de conversión que se va a trabajar, no tenemos que sentir interés por el hecho de ver que la conversión tenga lugar. Podríamos haber ido, pero al darse cuenta de que más de una equivalencia en el trabajo aquí creo que es suficiente. Ahora, debo señalar que dicha conversión, ya sea implica equivalencias o viene como equivalente a la de un proceso en el que intervienen, tales equivalencias.

¿Por qué estas equivalencias trabajo? Debido a la equivalencia, en el contexto de la lógica clásica, implica que cualquiera sea el valor de verdad de la fórmula original ha, la fórmula final se tiene que el valor de verdad también. Del mismo modo, porque nosotros sólo utiliza las equivalencias o utiliza un proceso que se presenta como equivalente a usar esas equivalencias, cualquiera sea el valor de verdad de la final de la fórmula, la fórmula original también. En consecuencia, dicha conversión se muestra por qué una fórmula como (((X→Y)→X)→X) califica como una tautología, porque en cada paso del proceso de conversión se asegura de que usted no hace los pasos que se traducen en fórmulas que tienen un distinto valor de verdad, y que terminó con una tautología. En otras palabras,

Empezamos con

(((X→Y)→X)→X), que tiene una desconocida valor de verdad en {True, False}.

Nosotros, a continuación, algunas de equivalencia que se asegura de que todo lo que obtener la siguiente N tendrá el mismo valor de verdad como (((X→Y)→X)→X). Ya que sólo el uso de las equivalencias, y, finalmente, obtener una fórmula que siempre tiene un valor de verdad de verdad, entonces sabemos que la segunda a la última fórmula tiene el mismo valor de verdad como la última fórmula obtenida. Ya hemos utilizado una equivalencia para llegar desde la tercera a la última fórmula de la segunda a la última fórmula, sabemos que la segunda a la última de las fórmulas tiene el mismo valor de verdad como la tercera a la última fórmula. Por transitividad, la tercera a la última fórmula tiene el mismo valor de verdad como la última fórmula. Finalmente, podemos decir que si la última fórmula que tiene valor de verdad de la realidad, y que sólo se utilizan las equivalencias para obtener la última fórmula de la primera, luego la primera fórmula también tiene valor de verdad de Verdad.

Para ver cómo funciona en más detalle, se había

(((X"$\land$Y')+X)'+X), que no sabemos su valor de verdad. Tenemos la equivalencia de X"==X, la cual nos da

(((X$\land$Y')+X)'+X), como si tuvieran el mismo valor de verdad como la fórmula original. Entonces ya tenemos la equivalencia ((X$\land$Y')+X)==X obtenemos

(X'+X).

Ahora ya sabemos que (X'+X) califica como una tautología por la última equivalencia, sabemos

(((X$\land$Y')+X)'+X) califica como una tautología. Luego por la segunda a la última equivalencia, sabemos

(((X"$\land$Y')+X)'+X) califica como una tautología. Y podemos razonar exactamente como esta, hasta que la primera fórmula, que fue

(((X→Y)→X)→X). Por lo tanto, (((X→Y)→X)→X) califica como una tautología.

Answer 5

Si ya ha definido el operador de implicación esto es fácil de demostrar. $X\rightarrow Y$ sólo es falsa cuando $X$ es verdadera y $Y$ no lo es.

Si $X$ es cierto esto da $((X\rightarrow Y)\rightarrow X)\rightarrow X\equiv \text{___}\rightarrow\top$ que no es falso, es verdadero.

Si $X$ es falsa la expresión es equivalente a $((\bot\rightarrow Y)\rightarrow\bot)\rightarrow\bot\equiv(\top\rightarrow\bot)\rightarrow\bot\equiv\bot\rightarrow\bot\equiv\top$, por lo que se mantiene cuando se $X$ no es cierto.