You are currently browsing the category archive for the ‘math.LO’ category.

   En lógica proposicional clásica podemos probar que la siguiente proposición es válida:

\displaystyle  (A \iff B) \lor (A \iff C) \lor (B \iff C),

donde {A}, {B} y {C} representan proposiciones, cada una de la cuales puede ser verdadera o falsa. El punto de la cuestión es que, no importa qué son esas proposiciones o cuáles de ellas (si las hay) son ciertas: la proposición mostrada es verdadera sin importar qué.

   Podemos probar esta proposición mediante una tabla de verdad. Sin embargo, de hecho no es necesario usarla. La proposición {(A\iff B)\lor(A\iff C)\lor(B\iff C)} es verdadera si, y sólo si, al menos uno de los disyuntos {A\iff B}, {A\iff C} y {B\iff C} es verdadero. Así, sabemos que la proposición {A\iff B} es verdadera exactamente cuando {A} y {B} tienen el mismo valor de verdad: ambos son verdaderos o ambos son falsos. Análogamente, la proposición {A\iff C} es verdadera exactamente cuando {A} y {C} tienen el mismo valor de verdad, y {B\iff C} es verdadera exactamente cuando {B} y {C} tienen el mismo valor de verdad.

   Ya que sólo hay dos valores de verdad en la lógica proposicional clásica, no importa como asignemos los valores de verdad a las proposiciones {A}, {B} y {C}, dos de las cuales tiene el mismo valor de verdad. Esto quiere decir que bajo cualquier asignación de valores de verdad a {A}, {B}, y {C}, al menos uno de los tres disyuntos tiene que ser verdadero, y, por lo tanto, toda la proposición también debe ser verdadera.

   Consideremos las dos siguientes afirmaciones: la primera, “si {x} es par, entonces {x} no es divisible por {5}”, y la segunda, “todo entero par no es divisible por {5}”. La idea es determinar un contraejemplo para mostrar que son falsas; por ejemplo, para la primera afirmación se puede usar {x=10}. ¿Es posible usar el mismo contraejemplo para la segunda afirmación? (Ya que aparentemente se refieren al mismo conjunto de números.) Ahora trataremos de entender porqué ambas afirmaciones son lógicamente equivalentes.

   Si estamos de acuerdo en formalizar el primero como

\displaystyle  Par(x) \rightarrow \lnot Div_5(x)

y, el segundo, como

\displaystyle  \forall x (Par(x) \rightarrow \lnot Div_5(x)),

tenemos que tener cierto cuidado cuando hablamos de equivalencia lógica.

   De acuerdo con Dirk van Dalen, Lógica y Estructura (5ta De. – 2013, página 67), la definición de verdad de una fórmula {\varphi} en un estructura {\mathfrak A} se define principalmente por oraciones (i.e., fórmulas “cerradas”) y luego se expanden mediante su “cerradura”:

\displaystyle  \mathfrak A \vDash \varphi \text{ syss } \mathfrak A \vDash Cl(\varphi).

   Sabiendo que {\varphi} es una consecuencia semántica de {\Gamma} si {\Gamma \vDash \varphi}, es decir, cuando {\varphi} se sostiene en cada modelo de {\Gamma}, las afirmaciones se implican mutuamente, consecuencias una de otra, y así, son lógicamente equivalentes.

   Por otro lado, si en su lugar los definimos como en Herbert Enderton, A Mathematical Introduction to Logic (2da Ed. – 2001, page 8):

   Sea {\Gamma} un conjunto de fbfs, y {\varphi} una fbf. Entonces {\Gamma} implica lógicamente {\varphi} (escrito {\Gamma \vDash \varphi}) si, y sólo si, para cada estructura {\mathfrak A} para el lenguaje y toda función {s\colon Var \rightarrow |\mathfrak A|} tales que {\mathfrak A} satisface que todo miembro de {\Gamma} con {s, \mathfrak A} también satisface {\varphi} con {s} (i.e., para todo {\mathfrak A} y {s}, si {\mathfrak A \vDash \psi[s]}, para cada {\psi \in \Gamma}, entonces {\mathfrak A \vDash \varphi[s]}),

tenemos que afirmación 1 {\nvDash} afirmación 2.

   Para mostrar esto, consideremos una función variable de asignación {s} tal que {s(x)=11}; claramente {Par(11) \rightarrow \lnot Div_5(11)} es verdadero (porque {F \rightarrow T} es {T}), y así {\mathbb N \vDash (Even(x) \rightarrow \lnot Div_5(x)[s]}, mientras que por supuesto {\mathbb N \nvDash \forall x (Par(x) \rightarrow \lnot Div_5(x))[s]}, es decir

\displaystyle  (Par(x) \rightarrow \lnot Div_5(x) \nvDash \forall x (Par(x) \rightarrow \lnot Div_5(x)).