You are currently browsing the monthly archive for septiembre 2015.

   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)).

Anuncios

   Revisando unos comentarios me topé con un ejercicio interesante.

Ejercicio 1. Sea {n} un número natural. Se quiere mostrar que

\displaystyle \left\lfloor\frac{n}{1}\right\rfloor+\left\lfloor\frac{n}{2}\right\rfloor+\dotsb+\left\lfloor\frac{n}{n}\right\rfloor+\left\lfloor{\sqrt{n}}\right\rfloor

es par.

Demostración. Si

\displaystyle  S = \{\,(a,b)\in\mathbf N^2\mid ab\le n\,\}

y

\displaystyle  T=\{\,(a,a)\in\mathbf N^2\mid a^2\le n\,\},

entonces

\displaystyle  |S|=\sum_{b\ge 1}|\{\,a\in\mathbf N\mid a\le\tfrac nb\,\}|=\sum_{b\ge 1}\lfloor \tfrac nb\rfloor =\left\lfloor \frac n1\right\rfloor+\left\lfloor \frac n2\right\rfloor+\ldots +\left\lfloor \frac nn\right \rfloor

y

\displaystyle |T|=\lfloor \sqrt n\rfloor.

La función {(a,b)\mapsto (b,a)} es un punto fijo libre de involución de {S\setminus T}, por lo tanto {|S\setminus T|} es par, y ya que

\displaystyle  \left\lfloor \frac n1\right\rfloor+\left\lfloor \frac n2\right\rfloor+\ldots +\left\lfloor \frac nn\right \rfloor+\lfloor\sqrt n\rfloor = |S\setminus T|+2|T|,

se prueba la afirmación. \Box

   Veamos ahora una segunda demostración:

Demostración. Usando el siguiente hecho:

\displaystyle  \sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor=\sum_{i=1}^n d(i)

donde {d(\ )} es la función divisor (LD: hay {d(i)} números que dividen a {i}, LI: hay {\left\lfloor\frac{n}{i}\right\rfloor} números a lo más {n} divisible por {i}). Todos los números tiene un número par de divisores, excepto para los cuadrados, y hay {\lfloor\sqrt{n}\rfloor} de aquellos; así

\displaystyle  \lfloor\sqrt{n}\rfloor+\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor=\sum_{i=1}^n d(i)+1\{\exists k\in\mathbf{N}:i=k^2\}

y todos los términos en la suma del LD son pares. \Box