Asociatividad de $\iff$

Question

En esta respuesta, user18921 escribió que la operación de $\iff$ es asociativa, en el sentido que

• $(A\iff B) \iff C$
• $A\iff (B\iff C)$

son declaraciones equivalentes.

Uno puede fuerza bruta una prueba bastante fácilmente (sólo escriba la tabla de verdad). Pero hay una razón más intuitiva ¿por qué debe celebrar esta asociatividad?

Answer 1

Me gustaría decir que yo personalmente no siento que esta equivalencia es intuitivo. (Tal vez es porque he estado pensando demasiado en forma constructiva en estos días.) En la lógica clásica, tenemos el isomorfismo con el álgebra de boole, y que hace posible pensar $A \leftrightarrow B$ como $a \oplus B \oplus 1$ donde $\oplus$ es el or exclusivo. Esto hace una breve prueba de la asociatividad de la bicondicional. Para mí, esta es la manera más intuitiva que se me ocurre para justificar la asociatividad.

Pero como J Marcos mencionado, la equivalencia no es cierto en intuitionistic lógica. Esto puede servir como una explicación de por qué la equivalencia no se supone que para ser tan intuitiva.

(Es sencillo encontrar un contraejemplo utilizando el modelo topológico. Me voy a trabajar fuera de los tediosos detalles para usted. Se asume que $\mathbb R$ es el espacio topológico de interés con la topología usual. Definir la valoración de $[\![\cdot]\!]$ por $[\![Un]\!] = (-1, 1)$, $[\![B]\!] = (0, \infty)$ y $[\![C]\!] = (-\infty, -1) \cup (0, 1)$. De ello se sigue que $$\begin{align*} [\![A \leftrightarrow B]\!] & = [\![A \rightarrow B]\!] \cap [\![B \rightarrow a]\!] = \text{int}([\![A]\!]^c \copa [\![B]\!]) \cap \text{int}([\![B]\!]^c \copa [\![A]\!]) \\ y = (-\infty, -1) \cap (0, 1) = [\![C]\!] \\ [\![(A \leftrightarrow B) \leftrightarrow C]\!] y = [\![(A \leftrightarrow B) \C]\!] \cap [\![C \(a \leftrightarrow B)]\!]\\ & = \text{int}([\![A \leftrightarrow B]\!]^c \copa [\![C]\!]) \cap \text{int}([\![C]\!]^c \copa [\![A \leftrightarrow B]\!]) = \mathbb R \\ [\![B \leftrightarrow C]\!] & = [\![B \rightarrow C]\!] \cap [\![C \rightarrow B]\!] = \text{int}([\![B]\!]^c \copa [\![C]\!]) \cap \text{int}([\![C]\!]^c \copa [\![B]\!]) \\ y = (-\infty, 1) \cap (-1, \infty) = \mathbb R\\ [\![A \leftrightarrow (B \leftrightarrow C)]\!] y = [\![B \leftrightarrow C) \a]\!] \cap [\![A \(B \leftrightarrow C)]\!] \\ & = \text{int}([\![B \leftrightarrow C]\!]^c \copa [\![A]\!]) \cap \text{int}([\![A]\!]^c \copa [\![B \leftrightarrow C]\!]) \\ y = [\![A]\!] \cap \mathbb R = (-1, 1) \ne \mathbb R \end{align*}$$ donde int es el interior y $^c$ es el complemento.)

Answer 2

Esta podría ser una de las situaciones donde más general (y por lo tanto más fuerte) el resultado es más intuitivo (dependiendo de cómo su intuición funciona). El resultado que tengo en mente es que, si se combinan de cualquier lista de $\mathcal L$ de fórmulas (no sólo tres, como el $A,B,C$ en la pregunta) por $\ffi$, entonces no importa la forma de poner el paréntesis para hacer inequívoca, la fórmula resultante es verdadera si y sólo si a un número de las fórmulas en la lista de $\mathcal L$ son falsas. En otras palabras, reiteró $\ffi$ equivale a una paridad conectivo, independientemente de la colocación de paréntesis.

Answer 3

¿Te resulta intuitivo que además modulo 2 califica como asociativo? ¿Te resulta intuitivo que dos valores de negación N puede calificar como un isomorfismo entre el concreto álgebras ({0, 1}, X) y ({0, 1}, Y) donde X e y indican las operaciones binarias? Bueno, si la respuesta es que sí a ambas preguntas, entonces si vamos a E-2 indican lógica de la equivalencia, a partir de la asociatividad de la suma módulo 2 de la negación isomorfismo da que E-2 asociados también.

En un papel que se llama La Equivalential Cálculo (se puede leer el documento en cualquiera de los volúmenes polaco Lógica 1920-1939 o Jan Lukasiewicz: obra Seleccionada) J. Lukasiewicz escribe "Ahora, yo hace tiempo que señaló que la equivalencia es también asociativa, y en consecuencia he establecido la siguiente tesis en el simbolismo de los Principia p≡.q≡r:≡p≡q.≡r Esta tesis, que en mi simbolismo puede ser expresada por EEpEqrEEpqr, es citado por Tarski en su tesis doctoral de 1923...

A2. p≡.q≡r:≡p≡q.≡r

El segundo axioma [A2] es la ley de asociatividad para la equivalencia, descubierto por mí mismo."

Lamentablemente, a pesar de Lukasiewicz no da ninguna referencia a cualquier tipo de papel donde los primeros en descubrir este. Así que, no tengo idea de cómo él lo descubrió.

A partir de una deducción natural marco, no creo que la asociatividad de la lógica de la equivalencia intuitivo en absoluto, incluso si usted sabe que un determinado sistema de deducción natural bastante bien. Traté de demostrarlo una vez sin ningún derivado de las reglas de inferencia, y luego encontró una menor prueba. La menor prueba tomó 141 líneas. Alguien trató de demostrar con derivados de reglas de inferencia, y demostró ser uno de los condicionales en 47 líneas.

En lo que se llama Lukasiewicz 3 valores de lógica lógica de equivalencia toma el valor de la verdad a lo largo de la diagonal, el valor de la falsedad en las otras esquinas no cubiertos hasta el momento, y el tercer valor de verdad en otros lugares. En otras palabras, donde el 0 indica la falsedad, .5 el tercer valor de verdad, y el 1 de verdad tenemos la siguiente matriz para la lógica de la equivalencia E:

  E   0  .5  1
  0   1  .5  0
  .5  .5  1  .5 
  1   0  .5  1

En la notación polaca inversa la lógica de la equivalencia va pqrEEpqErEE. Por lo tanto, vamos p=.5, p=.5 y r=0. A continuación, se obtiene:

.5 .5 0 E E .5 .5 E 0 E E= .5 .5 E 1 0 E E=1 0 E=0.

Así, en Lukasiewicz 3-valores de la lógica, la asociatividad de la lógica de la equivalencia puede tomar en la falsedad valor "0" y por lo tanto no califica como un cuasi-tautología (una cuasi-tautología nunca toma el valor de la falsedad, de la ley de Clavius CCNppp viene casi como una tautología en la Lukasiewicz 3-valores de la lógica).

Answer 4

La razón es difícil intuir esto es que estamos acostumbrados a pensar en "$(A\Leftrightarrow B)\Leftrightarrow C$" como indica algo acerca de las sentencias "$A\Leftrightarrow B$" y "$C$", pero nada acerca de " $$" (o "$B$") directamente: la conversión de una frase, "$A\Leftrightarrow(B\Leftrightarrow C)$", que habla de "$$ " directamente, es contrario a la intuición.

Así que para entender la equivalencia entre "$(A\Leftrightarrow B)\Leftrightarrow C$" y "$A\Leftrightarrow(B\Leftrightarrow C)$", tenemos que pensar en ellos, no como una frase sobre "$A\Leftrightarrow B$" y "$C$", respectivamente " $$" y "$B\Leftrightarrow C$", pero como frases sobre "$$ ", "$B$", y "$C$" directamente.

¿Qué significa "$(A\Leftrightarrow B)\Leftrightarrow C$" decir acerca de"$$", "$B$", y "$C$"?

1. Si "$C$" y "$$" hold, lo hace "$B$".
2. Si "$B$" y "$C$" hold, lo hace "$$".
3. Si "$$" y "$B$" hold, lo hace "$C$".
4. Si "$$" y "$B$" ambos son false, "$C$" sostiene.

Así que el punto crucial en la comprensión de la equivalencia entre "$(A\Leftrightarrow B)\Leftrightarrow C$" y "$A\Leftrightarrow(B\Leftrightarrow C)$" es la comprensión de la equivalencia entre

4. Si "$$" y "$B$" ambos son false, "$C$" sostiene.

y

4$'$. Si "$B$" y "$C$" ambos son false, "$$" sostiene.

(que es evidente).

El truco aquí se busca sólo en las declaraciones directas (por ejemplo, si "$C$" y " $$" hold, lo hace "$B$"): su contrapositives (por ejemplo, si "$C$" tiene pero "$B$" no, "$$ " es falsa) son menos intuitivos.