Asociatividad de las conectivas lógicas

Question

Según la precedencia de las conectivas lógicas , operador $\rightarrow$ tiene mayor prioridad que $\leftrightarrow$ operador. Pero ¿qué pasa con la asociatividad de $\rightarrow$ ¿operador?

El operador implícito ( $\rightarrow$ ) no tiene la propiedad asociativa. Esto significa que $(p \rightarrow q) \rightarrow r$ no es equivalente a $p \rightarrow (q \rightarrow r)$ . Por ello, se plantea la cuestión de cómo $p \rightarrow q \rightarrow r$ debe interpretarse.

La propuesta $p \rightarrow q \rightarrow r$ puede definirse de múltiples maneras que tengan sentido:

• $(p \rightarrow q) \rightarrow r$ (asociatividad izquierda)
• $p \rightarrow (q \rightarrow r)$ (asociatividad derecha)
• $(p \rightarrow q) \land (q \rightarrow r)$

¿Cuál de estas definiciones se utiliza?

No he podido localizar ningún libro/página web que mencione la asociatividad de los operadores lógicos en la matemática discreta.

Por favor, cite también la referencia (libro/página web fiable) que utiliza para responder a mi pregunta (ya que estoy planeando añadir esto a la página de wikipedia sobre 'conectivos lógicos').

Gracias.

PD: Me surgió esta pregunta al ver este problema: Comprueba si la siguiente proposición compuesta es una tautología o no:

$$ \mathrm{p} \leftrightarrow (\mathrm{q} \wedge \mathrm{r}) \rightarrow \neg\mathrm{r} \rightarrow \neg\mathrm{p}$$

Answer 1

Al entrar $p \Rightarrow q \Rightarrow r$ en Mathematica (con p \[Implies] q \[Implies] r ), muestra $p \Rightarrow (q \Rightarrow r)$ .

Eso hace plausible que el $\rightarrow$ es generalmente aceptado como asociativo a la derecha.

Answer 2

Algunos operadores lógicos son asociativos: tanto $\wedge$ y $\vee$ son asociativos, como lo verifica una simple comprobación de las tablas de verdad. Asimismo, el bicondicional $\leftrightarrow$ es asociativo.

Sin embargo, la implicación $\rightarrow$ es no asociativo. Compárese con $(p\rightarrow q)\rightarrow r$ y $p\rightarrow(q\rightarrow r)$ . Si todos los $p$ , $q$ y $r$ son falsas, entonces $p\rightarrow (q\rightarrow r)$ es verdadera, porque el antecedente es falso; pero $(p\rightarrow q\rightarrow r$ es falso, porque $r$ es falso, pero $p\rightarrow q$ es cierto. También están en desacuerdo con $p$ y $r$ son falsas pero $q$ es verdadero: entonces $p\rightarrow(q\rightarrow r)$ es verdadera porque el antecedente es falso, pero $(p\rightarrow q)$ es cierto, $r$ falso, por lo que $(p\rightarrow q)\rightarrow r$ es falso.

Dado que toman valores diferentes en algunas asignaciones de verdad, las dos proposiciones no son equivalentes, por lo que $\to$ no es asociativo.

Answer 3

Ejemplo de contador: Supongamos que p, q, r son todos falsos. Entonces (p=>q)=>r es falso, y p=>(q=>r) es verdadero.

Answer 4

Presumiblemente $p \Rightarrow q \Rightarrow r$ significa $(p \Rightarrow q) \Rightarrow r$ ya que la otra opción $p \Rightarrow (q \Rightarrow r)$ equivale a $(p \land q) \Rightarrow r$ . Eso es similar a las leyes de poder $p^{q^r} = p^{\left(q^r\right)}$ desde $\left(p^q\right)^r = p^{qr}$ .

La mejor práctica es simplemente no poner al lector en un estado de ambigüedad. A algunos escritores matemáticos les disgusta la puntuación, pero eso no es excusa para que el resto nos aprovechemos de ella.

Desde $\land$ y $\lor$ son asociativos, no hay ninguna ambigüedad, y tiene sentido no poner paréntesis. A veces incluso se piensa en una expresión como $p \land q \land r$ como conjunción $\land(p,q,r)$ .

Esta última convención es el caso de la complejidad de las pruebas cuando se mide la profundidad de una fórmula. Si una fórmula de primer orden cuantificado se traduce a la lógica proposicional, entonces $\forall$ corresponderá a una conjunción, y $\exists$ a una disyunción; tiene sentido no penalizar la fórmula por el tamaño del universo subyacente.

Una "convención" aún más atrevida es tener infinitas conjunciones/disyunciones - esto no tendría ningún sentido para $\Rightarrow$ . Así que los autores de sus libros de texto tienen la culpa (aunque teniendo la $\Leftrightarrow$ bind weakly es una convención razonable si no se usa en exceso).

Answer 5

Nótese que al no ser un operador binario, sino una relación binaria, la asociatividad no siempre produce la misma semántica, de reducir los emparejamientos de composición a una cola. Supongamos que $p \implies q \implies r.$ Pero si $r$ es falso, $p \implies q$ ser cierto no implica $r$ es cierto. Igualmente, $p \implies q$ puede ser falso mientras que $p \implies (r \implies q)$ es verdadera, por lo que $(p \implies (q \implies r)) \implies (p \implies q), (q \implies r)$ no es necesariamente cierto. Por último, si $(p \implies q) \implies r$ y $p \implies (q \implies r),$ y $p \equiv F,$ no tenemos ninguna razón para pensar $q \implies r$ y $p \implies q$ puede seguir siendo cierto, lo que significaría $r$ es verdadera independientemente de que $p \implies r$ .