8/19/2019 Libro Logica Matematica UES
1/171
Índice general
1. Cálculo Proposicional 1
1.1. Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2. Conectivos Lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.1. Conjunción, Disyunción y Negación . . . . . . . . . . . . . . . . 4
1.2.2. Condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3. Bicondicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3. Tablas de Verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4. Tautoloǵıas y Contradicciones . . . . . . . . . . . . . . . . . . . . . . . 17
1.5. Equivalencias Lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.6. Validez Lógica de Argumentos . . . . . . . . . . . . . . . . . . . . . . . 25
2. Cálculo de Predicados 29
2.1. Predicados y Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . 302.2. Traducción del lenguaje natural . . . . . . . . . . . . . . . . . . . . . . . 31
2.3. Propiedades de los cuantificadores . . . . . . . . . . . . . . . . . . . . . 40
2.3.1. Negación de Proposiciones con Cuantificadores . . . . . . . . . . 42
2.4. Validez lógica de argumentos con predicados . . . . . . . . . . . . . . . 46
3. Teorı́a de Conjuntos 51
3.1. Definiciones y Notaciones Básicas . . . . . . . . . . . . . . . . . . . . . 52
3.2. Operaciones con Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3. Diagramas de Venn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.4. Álgebra de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5. Familias de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4. Métodos de Demostración 85
4.1. Conceptos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.2. Demostrando Condicionales . . . . . . . . . . . . . . . . . . . . . . . . 88
4.3. Demostrando Bicondicionales . . . . . . . . . . . . . . . . . . . . . . . 97
4.4. Demostración por casos . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.5. Demostraciones por Contradicción . . . . . . . . . . . . . . . . . . . . . 104
8/19/2019 Libro Logica Matematica UES
2/171
U E S ÍNDICE GENERAL
4.6. El Principio de Inducción Matemática . . . . . . . . . . . . . . . . . . . 109
5. Relaciones 121
5.1. Tuplas ordenadas y producto cartesiano . . . . . . . . . . . . . . . . . . 122
5.2. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1225.3. Propiedades de las Relaciones . . . . . . . . . . . . . . . . . . . . . . . 127
5.4. Representación Gráfica de las Relaciones . . . . . . . . . . . . . . . . . 133
5.5. Relación de Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.6. Relaciones de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . 147
6. Funciones 157
6.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.2. Clasificación de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . 160
6.3. Composición de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . 164
6.4. Funciones invertibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
8/19/2019 Libro Logica Matematica UES
3/171
ÍNDICE GENERAL E Ḿ
8/19/2019 Libro Logica Matematica UES
4/171
Ć P1 C A P I T U L O
“Al contrario”, continu´ o Tweedledee, “Si ası́ fue,
ası́ pudo ser; si ası́ fuera, ası́ podrı́a ser; pero
como no es, no es. Es cuesti´ on de l´ ogica”
-Lewis Carroll
“Alicia a través del espejo”
Según nuestras mejores estimaciones, el len-guaje humano ha sido una manera eficiente de
comunicarnos por alrededor de 100,000 años.
Mucha de dicha eficiencia se debe al hecho que
el significado de lo que decimos o escribimos de-
pende tanto del contexto en el cual decimos o es-
cribimos las cosas como del contexto en el que
son escuchadas o leidas. Por ejemplo, “Invierno”
representa una época del año diferente depen-
diendo si se encuentra en el hemisferio norte
o sur, o en áreas, como la nuestra, que cuenta
únicamente con dos estaciones. “Tengo hambre”
significa que yo, Humberto Sermeño, tiene ham-
bre, y tiene un significado diferente si usted di-
ce las mismas palabras. Las siguientes sentencias
son también ejemplos del lenguaje cotidiano:
1. “Puede comer pastel o comer sorbete”.
2. “Si las vacas vuelan, entonces puede en-
tender la teorı́a de la relatividad”.
3. “Si puede resolver todos los problemas
que se nos ocurran, entonces tendrá 10 en
la materia”.
4. “Todo salvadoreño tiene un sueño”.
¿Qué significan exactamente estas senten-
cias? ¿Puedo comer tanto pastel como sorbete o
debo elegir un solo postre? Si la segunda senten-
cia es cierta, ¿significa que la teorı́a de la relati-
vidad es incomprensible? Si puede resolver algu-nos de los problemas que se nos ocurran, pero no
todos, ¿tendrá 10 en la materia? ¿Puede tener 10
aún cuando no pueda resolver alguno de los pro-
blemas? ¿Implica la última sentencia que todos
los salvadoreños tienen el mismo sueño o puede
cada uno tener un sueño diferente?
Algo de incerteza es tolerable en la conver-
sación normal. Desafortunadamente, cuando se
necesita formular ideas de manera precisa -como
en matemáticas- estas ambigüedades inherentes
en el lenguaje del dı́a a dı́a se convierten en un
problema. No es posible realizar un argumento
exacto si no estamos completamente seguros de
lo que significan las palabras. Es por esto que
antes de comenzar nuestro estudio matemático,
debemos investigar el problema de cómo hablar
matemáticamente.
En este capı́tulo se inicia definiendo los ti-
pos de sentencias del lenguaje natural que son
útiles en el lenguaje matemático, dándole un sig-
nificado preciso a palabras como “y”, “o”, “no”,
“implica” y “equivale”, los cambios lógicos que
estas palabras traen al unir dos o más sentencias,y los sı́mbolos matemáticos utilizados para re-
presentarlas1. Finalmente, se introducirá la for-
malización de dichos conceptos y las propieda-
des inherentes en ellos en la forma del álgebra
proposicional.
1Mucho de este trabajo fue iniciado por los Griegos hace más de 2,000 años.
1
8/19/2019 Libro Logica Matematica UES
5/171
1.1 P E Ḿ
1.1 Proposiciones.......................................................................................................
Coinsidere las sentencias matemáticas “2 + 5 = 7” y “7 < 5”. De aritmética básica,
sabemos que la primera es cierta, mientras que la segunda es falsa. Pero, ¿qué pasa con las
sentencias como “2 + 5 = 7 y 7 < 5” o “Si 2 + 5 = 7 entonces 7 < 5”? En realidad, laverdad o falsedad de estas sentencias compuestas depende de la falsedad o veracidad de
sus componentes simples y de las caracterı́sticas de los conectivos usados en la composi-
ción. Para comenzar a estudiar la naturaleza precisa de esta dependencia debemos primero
definir dichos componentes simples o proposiciones. Definiremos a una proposici´ on como
cualquier sentencia declarativa que es verdadera o falsa, pero no ambas al mismo tiempo.
La designación de verdadero o falso, de los cuales sólo uno es asignable a una propo-
sición, es llamado el valor de verdad de la proposición.
EJEMPLO 1.1
Las siguientes son todas proposiciones:
a) Parı́s es la capital de Canadá.
b) El 15 de abril de 2009 es un miércoles.
c) La tierra es plana.
d) 3 + 5 = 8
e) 2893015674434 + 1 es un número primo
f) Todo entero par mayor que 2 es la suma de dos números primos.2
Las proposiciones (a) y (c) son claramente falsas (es decir, tienen un valor de verdad
de falso), mientras que las proposiciones (b) y (d) son verdaderas. Por otro lado, a ún no
es posible determinar si las proposiciones (e) y (f) son verdaderas o falsas, pero es impor-
tante entender que no es necesario saber cuál es el valor de verdad de una sentencia para
poder clasificarla como proposición. Es suficiente con que sea posible en algún momento
asignarle uno de los dos valores.
EJEMPLO 1.2
Las siguientes sentencias no son proposiciones:
a) ¿Regresamos el martes o el miércoles?
b) ¡Ayúdeme por favor!c) X − Y = Y − X .d) Esta proposición es falsa.
En general, las preguntas y las órdenes no son proposiciones, por lo que (a) y (b) no
pueden ser clasificadas como tales. Por otra parte (c) no es proposición porque no especı́fi-
2Esta es la conjetura de Goldbach, que data de 1742.
2
8/19/2019 Libro Logica Matematica UES
6/171
U E S 1. Ć P
ca qué clase de objetos son X e Y . Finalmente, (d), aunque pareciera a primera vista ser
una proposición, es en realidad una paradoja: Si la proposición fuera verdadera, entonces
deberı́a ser falsa; si la proposición es falsa, deberı́a ser verdadera. En otras palabras, la sen-
tencia toma al mismo tiempo el valor de falso y verdadero, lo que contradice la definici ón
de proposición.
Se deben evitar frases ambiguas como las siguientes:
a) Los médicos son ricos.
b) Las matemáticas son divertidas.
c) La computación es más interesante que la matemática.
Donde el valor de verdad depende de preferencias o percepciones subjetivas. Ası́ mis-
mo, nótese que hay proposiciones cuyo valor de verdad depende del contexto en la que
son expresadas. En términos estrictos, una sentencia como “hoy es lunes” puede no con-
siderarse como una proposición dado que “hoy” es variable. Lo mismo puede ser dicho
Á (384-322 AC) nació en la ciudad de Estagira, no lejos del actual monte Athos, en la Calc ı́dicaentonces perteneciente al reino de Macedonia. Su padre, Nicómaco, fue el médico personal del rey Amyntas III
de Macedonia, por lo que Aristóteles fue entrenado y educado como miembro de la aristocracia.
Alrededor de los dieciocho años, viajó a Atenas para continuar su educación en la Academia de Platón,
donde continuó por cerca de veinte años hasta la muerte de su mentor en 347 AC. Luego viajó a la corte del
rey Hermias de Atarneos, en Asia Menor, junto a su condisc ı́pulo Xenócrates, desposándose de Pythias, la hija
(o sobrina) de Hermias. Poco después de la muerte del rey, Aristóteles fue invitado por Filipo II de Macedonia
para convertirse en tutor de Alejandro Magno.
Para 335 AC, habı́a regresado a Atenas y establecido una escuela llamada “liceo” (ası́ llamado por estar
situado dentro de un recinto dedicado a Apolo Likeios), donde educó a sus alumnos en amplios temas por los
próximos doce años. Durante este perı́odo murió su esposa Pythias, por lo que se involucró con Herpyllis de
Estagira. De acuerdo a la Suda, también tuvo un erómeno llamado Palaephatus de Abidos.
Es durante este perı́odo en Atenas que se cree que Aristóteles compuso muchos de sus trabajos. Escri-
bió muchos diálogos, de los cuales sólo fragmentos han sobrevivido. Los trabajos que sobreviven se encuentran
en forma de tratados y, en su mayorı́a, no estaban pensados para amplia publicación, ya que se piensa que
serı́an textos de apoyo para sus estudiantes. Se cree que s ólo cerca de un tercio de sus trabajos originales han
sobrevivido.
Aristóteles (junto con Sócrates y Platón) es una de las figuras fundadoras más importantes de la filosof ́ıa
occidental. Fue el primero en crear un sistema filosófico completo, abarcando moral y estética, lógica y ciencia,
polı́tica y metafı́sica. Los puntos de vista de Aristóteles sobre las ciencias fı́sicas dieron forma a las enseñanzas
medievales, y su influencia se extendió hasta el Renacimiento, cuando fueron finalmente reemplazadas por la
fı́sica moderna. En las ciencias biológicas, algunas de sus observaciones fueron confirmadas hasta finales del
siglo XIX. Sus trabajos contienen el estudio formal más antiguo conocido sobre la lógica, lo que fue incorporado
a finales del siglo XIX en la lógica formal moderna. En metaf ́ısica, Aristóteles tuvo una influencia profunda
en el pensamiento filosófico y teológico de las tradiciones Islámicas y Judı́as en la Edad Media, y continúa
influenciando la teologı́a Cristiana, especialmente la teologı́a ortodoxa oriental, y la tradición escolástica de la
iglesia Católica Romana.
Luego de la muerte de Alejandro, se encendió nuevamente un ambiente anti-macedónico en Atenas.
Eurimedón denunció a Aristóteles de no rendir honor a los dioses, por lo que Aristóteles huyó de la ciudad a las
propiedades de la familia de su madre en Calcis explicando: “No dejaré que los Atenienses cometan otro pecado
contra la filosofı́a”, refiriéndose al juicio y ejecución de Sócrates en Atenas. Sin embargo, murió a menos de un
año de haber llegado a Eubea de causas naturales. Dejó un testamento en el cual pedı́a ser enterrado junto a su
esposa.
3
8/19/2019 Libro Logica Matematica UES
7/171
1.2 C Ĺ E Ḿ
de “está lloviendo”. Sin embargo, en la práctica, cuando estas sentencias son usadas en
el dı́a a dı́a, hay una gran cantidad de material de respaldo (contexto) que hacen que di-
chas sentencias sean verdaderas o falsas en un tiempo y lugar especı́ficos, por lo que serán
consideradas como proposiciones.
1.2 Conectivos Lógicos.......................................................................................................
Todas las proposiciones en el ejemplo 1 son proposiciones simples. Sin embargo, es
usual en el lenguaje cotidiano utilizar proposiciones compuestas que consisten de dos o
más proposiciones unidas por uno o más conectivos l´ ogicos, siendo “y”, “o”, “no”, “im-
plica” y “equivale” las más comunes de ellas. Por ejemplo, podemos combinar tres propo-
siciones:
Si los humanos son mortales y todos los salvadoreños son humanos, entonces todos lossalvadoreños son mortales.
En la discusión siguiente, no nos preocupará mucho el significado de las proposicio-
nes simples -ya sea que hablen de matemática o de la mortalidad de los salvadoreños- pero
sı́ de cómo las proposiciones son combinadas y relacionadas. Es por esto que usualmente
se utilizarán variables como p o q en lugar de proposiciones especı́ficas como “Todos los
humanos son mortales” y “2+3=5”. Se entenderá que estas variables, como las proposi-
ciones, pueden tomar uno de dos valores: verdadero o falso.
1.2.1. Conjunción, Disyunción y Negación
Primero analizamos el uso del conectivo y, que expresa que dos eventos son ciertos
simultáneamente. Es decir, si p y q son dos proposiciones, la proposición compuesta “ p y
q”, simbolizada por p ∧ q y llamada conjunci´ on, será verdadera solamente en el caso enque ambas proposiciones lo sean.
Los siguientes ejemplos muestran el uso de la conjunción.
EJEMPLO 1.3
La proposición “Son las 4 PM y está lloviendo” está compuesta por las proposiciones
p =“Son las 4 PM” y q =“Está lloviendo” unidas por el conectivo “ y” para indicar que
ambos se cumplen al mismo tiempo. Se simboliza como p ∧ q.
EJEMPLO 1.4
La proposición “π es mayor que 3 y π es menor que 3.2” indica que debe cumplirse tanto
“π es mayor que 3” como “π es menor que 3.2”. Simbólicamente, podemos representar a
s como π > 3 y a t como π < 3.2, por lo que la proposición compuesta puede ser escrita
como
(π > 3) ∧ (π
8/19/2019 Libro Logica Matematica UES
8/171
U E S 1. Ć P
Una observación importante es que en el lenguaje matemático, una conjunción es in-
dependiente del orden de sus partes: p ∧ q significa lo mismo que q ∧ p. Esto no siemprees cierto en el lenguaje cotidiano. Por ejemplo, la proposición
Jos´ e pate´ o el tiro libre y la pelota entr´ o en la porterı́a.
no significa lo mismo que
La pelota entr´ o en la porterı́a y Jos´ e pate´ o el tiro libre.
Otra diferencia importante con el uso de “y” en el lenguaje natural se puede observar
en frases como “Juan y Pedro son amigos”. En esta proposición, no es posible utilizar
el sı́mbolo ∧ para representar la palabra “ y” ya que no está siendo usada para unir dos
proposiciones.El siguiente conectivo lógico que analizaremos es la palabra “o”, que, a diferencia
del “y”, sı́ introduce ambigüedad en el lenguaje común. Utilizamos “o” cuando queremos
expresar que el evento A es cierto o el evento B es cierto. Es decir, dadas dos proposiciones
p y q, la proposición compuesta “ p o q”, simbolizada como p ∨ q, es verdadera cuando almenos una de las proposiciones componentes lo es. Las proposiciones de la forma p ∨ qson llamadas disyunciones.
EJEMPLO 1.5
Las siguientes proposiciones son ejemplos de disyunciones.
a) La proposición “La clase de mañana a las 10 será en el aula 1 o en el aula 3”, está for-mada por las proposiciones “La clase de mañana a las 10 será en el aula 1” y “La clase
de mañana a las 10 serán en el aula 3”.
b) La proposición “3 es un entero par ó 7 un primo” se representa con p ∨ q, donde p =“3 es un entero par”, q = “7 es un número primo”.
c) La proposicion “Esta noche comeré pollo o vegetales” está compuesta por las proposi-
ciones r=“Esta noche comeré pollo” y s=“Esta noche comeré vegetales”.
Note que la definición de disyunción nos dice que la proposición compuesta disyuntiva
será falsa únicamente cuando ambas proposiciones son falsas. Esto introduce una diferen-
cia importante con el lenguaje cotidiano, donde la proposición p ∨ q normalmente indicaque o p es verdadera, o q es verdadera, pero no ambas. Las proposiciones (a) y (b) del
ejemplo 5 siguen este razonamiento exclusivo. Sin embargo, para la proposición (c) tanto
r como s pueden ser ciertas simultáneamente. Este significado inclusivo de la palabra o es
el que utilizaremos de aquı́ en adelante.
La siguiente definición surge de la necesidad de negar sentencias, expresando que una
proposición es falsa. Dada una proposición p cualquiera, la proposición compuesta “no
p”, simbolizada por ¬ p, es verdadera si p es falsa, y es falsa si p es verdadera.
5
8/19/2019 Libro Logica Matematica UES
9/171
1.2 C Ĺ E Ḿ
Como se muestra en los siguientes ejemplos, los tres conectivos lógicos presentados
hasta ahora nos permiten analizar la forma lógica de proposiciones complejas.
EJEMPLO 1.6
Analice la forma lógica de “José se irá de casa y no volverá”.Soluci´ on. Sea p la proposición “José se irá de casa” y q la proposición “José no volverá”,
entonces podemos representar esta expresión simbólicamente como p ∧ q. Sin embargo,este análisis no considera que q es en realidad una expresión negativa. Podrı́amos obtener
un mejor resultado si consideramos a r como “José volverá” y reescribimos a q como ¬r .Reemplazando a q en nuestro análisis original tenemos p ∧ ¬r .
EJEMPLO 1.7
Analice la forma lógica de “O Elisa entró a clases y Gabriela no, o Gabriela entró a clases
y Elisa no”.
Soluci´ on. Sea e la proposición “Elisa entró a clases” y sea g la proposición “Gabrielaentró a clases”. La primera parte de la proposición, es decir “O Elisa entró a clases y
Gabriela no”, puede ser escrita como e ∧ ¬g. Similarmente, la segunda mitad puede serrepresentada por g ∧ ¬e. Para representar toda la proposición, utilizamos la disyunciónpara combinar estas dos partes para formar (e ∧ ¬g) ∨ (g ∧ ¬e).
Note que al analizar la proposición compuesta del ejemplo anterior, agregamos parénte-
sis cuando formamos la disjunción de e ∧ ¬g y g ∧ ¬e para indicar sin ambigüedadesqué proposiciones estaban siendo combinadas. Esto es similar al uso de paréntesis en álge-
bra, en donde, por ejemplo, el producto de a+b y a−b serı́a escrito como (a+b)·(a−b), conlos paréntesis indicando qué cantidades están siendo multiplicadas. Como en el álgebra, en
lógica es conveniente omitir algunos paréntesis para hacer más cortas y más legibles nues-tras expresiones. Sin embargo, es necesario establecer las reglas para leer dichas expresio-
nes sin que esto introduzca ambigüedades. Una primera convención que adoptaremos es
que la negación (¬) se aplica únicamente a la proposición que viene inmediatamente des-pués de ella. Por ejemplo, ¬ p ∧ q significa (¬ p) ∧ q en lugar de ¬( p ∧ q). En el transcursodel libro, se presentarán más convenciones sobre los paréntesis.
También es importante tomar en cuenta que los sı́mbolos ∧ y ∨ únicamente pueden serusados entre dos proposiciones para formar su conjunción o disyunción, y el sı́mbolo ¬sólo puede ser usado antes de una proposici´ on para negarlo. Esto quiere decir que ciertas
cadenas de sı́mbolos y variables no son válidas, como p¬ ∧ q, p ∨ ∧q, y p¬q. Una vezmás, puede ser útil pensar en una analogı́a con el álgebra, donde los sı́mbolos +,
−, ×
y
÷ pueden ser usados entre dos números, como operadores, y el sı́mbolo − puede tambiénser usado antes de un número para negarlo. Estas son las únicas formas en los que estos
sı́mbolos pueden ser usados en álgebra, por lo que expresiones como x − ÷ y no tienensentido alguno.
Algunas veces, palabras diferentes a “ y”, “o” y “no” son usadas para expresar el signi-
ficado representado por ∧, ∨ y ¬. Por ejemplo, considere la predicción del tiempo “vientoy lluvia son las únicas posibilidades para el clima de mañana”. Esta es simplemente otra
manera de decir que o hará viento o lloverá mañana, por lo que, aún cuando se utilizó la
6
8/19/2019 Libro Logica Matematica UES
10/171
U E S 1. Ć P
palabra “ y” en la proposición, ésta es en realidad una disyunción. El mensaje de estos
ejemplos es que para determinar la forma lógica de las proposiciones debe pensarse en el
significado de las mismas y no en simplemente traducirlas palabra por palabra. Como otro
ejemplo, considere la proposición “tengo hambre pero tengo que ir a clase”. En este caso,
la palabra pero es utilizada para representar a la conjunción.
Finalmente, algunas veces hay conectivos ocultos en la notación matemática. Por ejem-
plo, considere la proposición 3 ≤ π. Aunque a primera vista parezca una proposición sinconectivos lógicos, al leerla en voz alta se escuchará la palabra o. Si representamos a 3 < π
como p y a 3 = π como q, entonces la proposición 3 ≤ π puede ser escrita como p ∨ q.Como un ejemplo ligeramente más complicado, considere la proposición 3 ≤ π
8/19/2019 Libro Logica Matematica UES
11/171
1.2 C Ĺ E Ḿ
1.2.2. Condicional
La cuarta noción que investigaremos es una de las que causa la mayor confusión ini-
cial: implicaci´ on. En matemáticas frecuentemente utilizamos expresiones de la forma “ p
implica q”, simbolizada “ p → q”. De hecho, la implicación provee el medio por el cualdemostramos proposiciones, comenzando con observaciones iniciales o axiomas. Por lo
tanto, serı́a razonable asumir que cuando se tiene una proposición de la forma p → q, si pes verdadera, entonces q debe ser también verdadera.
Pero suponga que p es la proposición verdadera “√
2 es irracional” y q es “0 < 1”.
¿Será verdadera p → q en este caso? En otras palabras, ¿será cierto que la irracionalidadde
√ 2 implica que 0 es menor que 1? Desde luego que no. No existe conexión real entre
las proposiciones p y q.
Más dramáticamente, considere la implicación
“Que el emperador Julio César esté vivo implica que 1 + 1 = 2”.
En este caso, ¿Qué puede decirse de p → q si p es falso? ¿Tienen sentido este tipo deexpresiones?
El problema con los ejemplos anteriores es que el concepto de implicación no sólo
tiene que ver con el valor de verdad de la proposición (como es el caso de la conjunción,
disyunción y negación), sino también con causalidad . Cuando escribimos “ p implica q”,
queremos decir que de alguna manera q es causada o provocada por p. Para los propósitos
de este capı́tulo, no consideraremos el complejo problema de la causalidad y utilizaremos
únicamente el valor de verdad de las implicaciones. A cualquier expresión de la forma p →q se le llamará la expresi´ on condicional o simplemente el condicional. Nos referiremos a
p como el antecedente y a q como consecuente. La verdad o falsedad de un condicionalserá definido completamente por la verdad o falsedad del antecedente y del consecuente, y
no se considerará en absoluto si existe o no una conexión significativa entre p y q.
Como se esperarı́a, esta definición que ignora un aspecto altamente significativo de
la noción de la implicación puede tener consecuencias que son contraintuitivas e incluso
absurdas. Sin embargo, en todos los casos donde sı́ existe una implicación genuina y sig-
nificativa de la forma “ p implica q”, el condicional p → q concuerda con esa implicación.Dicho de otra manera, al definir el condicional de esta forma, no tenemos caso alguno
en que se contradiga la noción de la implicación genuina. En lugar de ello, obtenemos
una noción que extiende a la implicación genuina para cubrir los casos donde se tiene una
implicación sin sentido, como en los casos donde el antecedente es falso o donde no hay
conexión real entre el antecedente y el consecuente.
Ahora que ignoramos toda causalidad, el valor de verdad de una implicación es intui-
tivo cuando el antecedente es verdadero. Si p es verdadero y “ p implica q” es una proposi-
ción válida, entonces q debe ser verdadera. Es decir, el condicional p → q será verdaderocuando tanto el antecedente como el consecuente sean verdaderos.
Para manejar el caso en el que el antecedente es falso, no consideraremos la noción de
implicación sino más bien la de su negación. Extraeremos la parte del valor de verdad y sin
causalidad de la proposición “ p no implica q”, que escribiremos como p q, y dejaremos
8
8/19/2019 Libro Logica Matematica UES
12/171
U E S 1. Ć P
de lado cualquier tipo de relación entre p y q. Con esto en mente, podemos ver que p no
implicar´ a q si tenemos que aunque p sea verdadera, q es falsa 5 . Por lo tanto, diremos que
p q es verdadera precisamente cuando p es verdadera y q es falsa.
Habiendo definido la verdad o falsedad de p q, obtenemos el valor de verdad de
p → q utilizando la negación. De aquı́ que p → q será verdadera exactamente cuando p q sea falsa, llevando a los siguientes casos donde la expresión condicional p → q esverdadera:
(1) p y q son ambas verdaderas.
(2) p y q son ambas falsas.
(3) p es falsa y q es verdadera.
Obervando estos casos, vemos que la expresión condicional es falsa únicamente cuan-
do el antecedente es verdadero pero el consecuente es falso.
Para explorar aún más el condicional, considere la siguiente proposición:
“Si la conjetura de Goldbach es verdadera, entonces x2 ≥ 0 para todo número real x”
Como mencionamos anteriormente, no se ha podido determinar aún si la conjetura de
5Formalmente escribimos esto como p ∧ ¬q, lo que sugiere que esta expresión y ¬( p → q) significan lomismo (son equivalentes).
A D M (1806-1871) fue el quinto hijo de John De Morgan, un Teniente-Coronel inglésestacionado en India al momento del nacimiento de Augustus. De Morgan perdió su vista en el ojo derecho
poco después de su nacimiento y, a los siete meses de edad, regresó a Inglaterra con su familia. John De Morganmurió cuando Augustus tenı́a 10 años.
De Morgan no sobresalió en la escuela y, debido a su condición f ́ısica, no jugaba deportes e incluso fue
vı́ctima de crueles bromas por parte de sus compañeros.
Ingresó al Trinity College de Cambridge en 1823 a los 16 años, donde fue alumno de Peacock y Whe-
well, con quienes entabló amistad de por vida. Recibió su licenciatura pero, dado que un exámen teológico era
requerido para la Maestrı́a, algo a lo que De Morgan objetaba a pesar de ser miembro de la Iglesia de Inglaterra,
el no pudo seguir en Cambridge ya que no era elegible para una beca sin una Maestŕıa.
En 1826 regresó a su hogar en Londres e ingresó al Licoln’s Inn a estudiar para los exámenes de abogacı́a.
En 1827 (a los 21 años), aplicó a la dirección de matemática en el nuevo University College London y, a pesar
de no tener publicaciones matemáticas, fue contratado. Por cuestión de principios, renunció a su posición en
1831, siendo contratado nuevamente 1836.
Además de sus famosas leyes y de ser recordado como el reformador de la l ógica matemática, De Morgan
también contribuyó a otras áreas de la matemática. En 1838, en su artı́culo Induction (Mathematics) de la Penny
Cyclopedia, definió e intodujo el término inducci´ on matem´ atica (ver sección ??), un proceso que habı́a sido
utilizado anteriormente sin claridad o base rigurosa. Otras publicaciones incluyen Elementos de ´ Algebra (1837),
Elementos de aritm´ etica (1840), Calculo Diferencial e Integral y Trigonometrı́a (1849).
En 1866, a los 60 años, renunció por segunda vez a su puesto en University College por cuestión de
principios, por lo que sus pupilos le aseguraron una pension de £500. Ese mismo año fue co-fundador y primer
presidente de la Sociedad Londinense de Matemática. Sin embargo, dos años más tarde, muere su hijo George,
un hábil matemático por sı́ mismo, seguido por otra de sus hijas. Cinco años después de su renuncia, De Morgan
muere el 18 de marzo de 1871.
De Morgan siempre se interesó por hechos numéricos raros, escribiendo en 1864 que habı́a tenido la
distinción de tener x años en el año x2.
9
8/19/2019 Libro Logica Matematica UES
13/171
1.2 C Ĺ E Ḿ
Goldbach es cierta o falsa. Sin embargo, eso no evita que podamos determinar el valor de
verdad de la proposición compuesta. Esta proposición tiene la forma p → q, donde p=“Laconjetura de Goldbach es verdadera” y q=“ x2 ≥ 0 para todo número real x”. Ya que q esverdadera, entonces estamos en el caso (1) o el caso (3) de la veracidad de la condicional,
por lo que la proposición compuesta es verdadera.
La siguiente proposición demuestra el lado contraintuitivo de las implicaciones:
“Si los cerdos vuelan, entonces puedes entender la teoŕıa de la relatividad”
Curiosamente, el valor de verdad de esta proposición no tiene relación alguna con el
hecho de que se pueda o no entender la teoŕıa de la relatividad. Los cerdos no vuelan,
ası́ que estamos en el caso (2) o (3) de la veracidad del condicional. En ambos casos, la
proposición es verdadera.
En contraste, considere la siguiente proposición:
“Si la luna parece blanca, entonces la luna está hecha de queso blanco”
Sı́, la luna parece blanca, pero no, no está hecha de queso blanco. Ya que la combina-
ción de estos valores de verdad no se encuentra en ninguno de los casos de la veracidad
del condicional, la proposición debe ser falsa.
Estos ejemplos muestran que la definición del condicional puede resumirse de la si-
guiente manera:
Una expresi´ on condicional es verdadera si el antecedente es falso o si el consecuente es
verdadero.
La escritura formal de la observación anterior sugiere que p → q y ¬ p ∨ q significanlo mismo.
Además de los valores de verdad que hemos visto hasta ahora, el condicional (y m ás
generalmente, la implicación) posee terminologı́a asociada a la que el lector debe acos-
tumbrarse. Una proposición “ p → q” puede leerse de las siguientes maneras:(1) p implica q
(2) Si p entonces q
(3) p es suficiente para q
(4) p sólo si q
(5) q si p
(6) q cuando p
(7) q es necesario para p
Las primeras cuatro formas mencionan a p antes de q, y de estas las primeras 3 son
relativamente f ́aciles de entender. Pero (4) requiere un poco de atención. Note el contraste
entre (4) y (5) con respecto al orden entre p y q. Con mucha frecuencia quienes estudian
estos conceptos por primera vez encuentran dificultad en apreciar la distinción entre si y
s´ olo si.
10
8/19/2019 Libro Logica Matematica UES
14/171
U E S 1. Ć P
De la misma manera, el uso de la palabra necesario en (7) usualmente causa confusión.
Note que decir que q es una condición necesaria para p no significa que q por sı́ sola es
suficiente para garantizar p. Más bien, lo que dice es que q debe ser verdadera antes que
pueda darse cualquier pregunta si p es verdadera.
Contrapositiva y Conversa
A la expresión condicional p → q puede asociársele la proposición ¬q → ¬ p, llamadala contrapositiva o contrarecı́proca de p → q. Note que en la contrapositiva, la intro-ducción del signo de negación es acompañada de un cambio en la dirección de la flecha.
Por ejemplo, la contrapositiva de la expresión “si está lloviendo, entonces hay nubes en el
cielo” es “si no hay nubes en el cielo, no está lloviendo”. De la misma manera, la contra-
positiva de la proposición “si 2n − 1 es primo, entonces n es primo” es “si n es compuesto(es decir, no es primo), entonces 2n − 1 es compuesto”.
Más adelante veremos que una expresión condicional y su contrapositiva son lógica-mente equivalentes. Sin embargo, es importante no confundir a la contrapositiva con el
condicional q → p, llamada la conversa o recı́proca de p → q. En general, no existe co-nexión entre los valores de verdad de un condicional y su conversa. Esto es ilustrado con
la conversa de la expresión “si está lloviendo, entonces hay nubes en el cielo”, la cual es
“si hay nubes en el cielo, entonces está lloviendo”.
1.2.3. Bicondicional
Cercanamente ligada a la implicación es la noción de equivalencia. Se dice que dos
proposiciones p y q son (l ´ ogicamente) equivalentes si cada una implica a la otra. Ası́ como
en la sección anterior la implicación fue desprovista de causalidad, el estudio de equivalen-
cia será igualmente desprovista de causalidad en esta sección y estudiaremos únicamente la
parte concerniente al valor de verdad de la equivalencia: el bicondicional. Dadas dos pro-
posiciones p y q, la proposición bicondicional “ p si y sólo si q”, simbolizada por p ↔ q,es definida como ( p → q) ∧ (q → p).
De esta definición y como se verá más claramente podemos ver que el bicondicional
será verdadero si p y q son ambos verdaderos o ambos falsos; de lo contrario, el bicon-
dicional es falso. En otras palabras, para que p ↔ q sea verdadero, p y q deben tener elmismo valor de verdad.
Al igual que con el condicional (y la implicación), el bicondicional (y la equivalen-
cia) posee terminologı́a asociada con la que es necesario familiarizarse. Una proposición p ↔ q puede leerse de las siguientes maneras:(1) p es equivalente a q
(2) p es necesario y suficiente para q
(3) p si y sólo si q
Es necesario tener en cuenta que en el lenguaje cotidiano algunas veces utilizamos
proposiciones condicionales cuando en realidad queremos expresar un bicondicional. Por
11
8/19/2019 Libro Logica Matematica UES
15/171
1.2 C Ĺ E Ḿ
ejemplo, probablemente no se dirı́a algo como “la clase se impartirá si hay al menos diez
personas en el salón” a menos que también sea el caso que si hubiera al menos de diez
personas en el salón, la clase se impartirı́a. Por lo tanto, la proposición sugiere que la clase
será impartida si y sólo si hay al menos diez personas en el salón. Como otro ejemplo,
suponga que los padres le dicen a un niño, “Si no te comes todo, no tendrás postre”. El niño
ciertamente espera que si termina su comida tendrá su postre, aunque no sea literalmente lo
que sus padres dijeron. En otras palabras, el niño interpreta el significado de la proposición
como “que termines tu comida es una condición necesaria y suficiente para obtener postre”.
Tal confunsión entre “si” y “si y s´ olo si” nunca es aceptable en matemáticas. En el resto
del libro (y en el lenguaje matemático) se utilizarán siempre expresiones como “es nece-
sario y suficiente” o “si y sólo si” para expresar el bicondicional. No deberá interpretar
una proposición de la forma “si-entonces” como una proposición bicondicional.
Ejercicios.......................................................................................................
1. Exprese las siguientes proposiciones com-
puestas en forma simbólica:
a) No irás a jugar fútbol, o irás y nadie es-
tará ahi.
b) O Juan y Beto están ambos diciendo la
verdad, o ninguno la está diciendo.
c) Comeré pescado o pollo, pero no co-
meré pescado y puré de papas.
d) Tendremos ya sea lectura o tarea para la
siguiente clase, pero no tendremos tarea y
examen al mismo tiempo.
e) 3 es un divisor común de 6, 9 y 15.
f) Alicia y Carlos no están ambos en el cuar-
to.
g) Alicia y Carlos están ambos fuera del
cuarto.
h) O Alicia o Carlos no están en el cuarto.
i) Ni Alicia ni Carlos están en el cuarto.
2. ¿Cuáles de las siguientes expresiones lógicas
no son válidas?
a) ¬(¬ p ∨ ¬¬r )b) ¬( p, q, ∧r )c) p ∧ ¬ pd) ( p ∧ q)( p ∨ r )
3. Si p representa a la proposición “com-
praré los pantalones” y s a la proposición
“compraré la camisa”. ¿Qué oraciones en Es-
pañol son representadas por las siguientes ex-
presiones lógicas?
a) ¬ p ∧ ¬sb)
¬ p
∨ ¬s
c) ¬( p ∧ ¬s)4. Si a representa a la proposición “Alfonso
está feliz” y g representa a “Gabriel está fe-
liz”. ¿Qué oraciones en Español son represen-
tadas por las siguientes expresiones lógicas?
a) (a ∨ g) ∧ (¬a ∨ ¬g)b) [a ∨ (g ∧ ¬a)] ∨ ¬gc) a ∨ [g ∧ (¬a ∨ ¬g)]
5. Sean p, q, r las proposiciones: p = “Está llo-
viendo”, q = “El sol está brillando”, r = “Hay
nubes en el cielo”. Traduzca las siguientes
frases a notación lógica usando p, q, r y los
conectivos lógicos:
a) Está lloviendo y el sol está brillando
b) Si está lloviendo, entonces el sol no
está brillando
12
8/19/2019 Libro Logica Matematica UES
16/171
U E S 1. Ć P
c) Si no está lloviendo, entonces el sol no
está brillando y no hay nubes en el cielo
d) El sol está brillando si y sólo si no está llo-
viendo
e) Si no hay nubes en el cielo, entonces el
sol está brillando
6. Sean p, q, r las proposiciones del ejercicio 5,
traduzca las siguientes proposiciones al cas-
tellano:
a) ( p ∧ q) → r c) ( p → r ) → qe) ¬( p ∨ q) ∧ r
b) ¬ p ↔ (q ∨ r )d) ¬( p ↔ (q ∨ r ))
7. Identifique al antecedente y al consecuente en
cada una de las siguientes expresiones condi-
cionales:a) Si las manzanas son rojas, entonces las
naranjas son verdes.
b) La diferenciabilidad de una función f es
suficiente para que f sea contı́nua.
c) Una función f es acotada si f es integra-
ble.
d) Una secuencia s es acotable cuando s es
convergente.
e) Es necesario que n sea primo para que
2
n
− 1 sea primo.f) El equipo gana sólo cuando Carlos juega.
g) Cuando Carlos juega el equipo gana.
h) El equipo gana cuando Carlos juega.
8. Escriba la conversa y la contrapositiva de ca-
da condicional del ejercicio anterior.
9. Determine el valor de verdad de los siguien-
tes enunciados:
a) Si 5 < 3 entonces −3
8/19/2019 Libro Logica Matematica UES
17/171
1.3 T V E Ḿ
verdad de:
a) p ∧ q b) p ∨ q c) q → pObservación: las proposiciones p, q son las
mismas en las cuatro proposiciones compues-
tas.
1.3 Tablas de Verdad.......................................................................................................
Ya que hemos definido a los conectivos lógicos ∧, ∨, ¬, → y ↔ únicamente en térmi-nos de sus valores de verdad, es posible definirlos usando una tabla de verdad 6, donde
representamos al valor verdadero con una V o un 1, y al valor falso con una F o un 0. Por
ejemplo, si p denota una proposición cualquiera, entonces la veracidad de la proposición
“no p” puede ser ilustrada con la siguiente tabla:
p ¬ pF V
V Fo bien
p ¬ p0 1
1 0
La primera fila de la tabla indica que cuando la proposición p es falsa, la proposición
¬ p es verdadera. La segunda fila indica que cuando p es verdadera, ¬ p es falsa.En general, una tabla de verdad indica la veracidad o falsedad de una proposición para
todas las posibles combinaciones de los valores de las proposiciones simples. Por ejemplo,
la tabla de verdad para la proposición p ∧ q tiene cuatro filas: p q p ∧ q
0 0 00 1 0
1 0 0
1 1 1
En las primeras dos columnas aparecen todas las posibles combinaciones de los valores
de 1 y 0 que las proposiciones p y q pueden tener. La tercera columna muestra el valor de
verdad de p ∧ q por cada una de las combinaciones. De aquı́ se puede ver que p ∧ q esverdadero únicamente cuando tanto p como q son verdaderos.
Para p ∨ q y para p → q tenemos las tablas: p q p
∨q
0 0 0
0 1 1
1 0 1
1 1 1
p q p →
q
0 0 1
0 1 1
1 0 0
1 1 1
6Aunque las tablas de verdad habı́an sido utilizadas en la literatura desde 1920, fue la influencia del Tractatus
Logico-Philosophicus de Wittgenstein (ver pág. 15) que popularizó su uso. Sin embargo, Lewis Carroll (ver pág.
47), autor de Alicia en el Paı́s de las Maravillas, habı́a formulado tablas de verdad en 1894 para resolver ciertos
problemas, pero los manuscritos que contenian ese trabajo no fueron descubiertos sino hasta 1977.
14
8/19/2019 Libro Logica Matematica UES
18/171
U E S 1. Ć P
Es posible construir tablas de verdad para expresiones más complicadas. Considere,
por ejemplo, la tabla de verdad para p ↔ q, la cual fue definida como ( p → q) ∧ (q → p). p q p → q q → p ( p → q) ∧ (q → p)0 0 1 1 10 1 1 0 0
1 0 0 1 0
1 1 1 1 1
Pasos 1 1 2 3 4
La última fila de la tabla anterior muestra el orden en que fueron llenados los valores
de las columnas. Se inicia con una columna por cada una de las variables de la expresión
de tal manera que cada fila tenga una combinación diferente de los valores de verdad de las
variables, cubriendo todas las combinaciones posibles. Luego, por cada fila, se calcula el
L J J W (1889-1951) fue un filósofo Austrı́aco que trabajó principalmente enlos fundamentos de la lógica, la filosof ́ıa de la matemática, la filosof ́ıa de la mente, y la filosof ́ıa del lenguaje.
Nació en Viena el 26 de abril de 1889, siendo el m ás joven de ocho hijos nacidos en una de las más prominentes
y adineradas familias del imperio Austro-Húngaro. Su familia era visitada por músicos como Johannes Brahms
y Gustav Mahler. Ludwig y sus hermanos fueron educados tanto intelectual como art ı́sticamente, por lo que
Ludwig poseı́a una devoción a la música que siguió siendo importante por el resto de su vida.
Ludwig fue educado en casa hasta 1903, cuando inició tres años de estudio en la Realschule de Linz,
donde Adolfo Hitler fue estudiante al mismo tiempo. Wittgenstein hablaba Alemán altamente puro y educado,
aunque ocasionalmente tartamudeaba, vestı́a ropas elegantes, y era increı́blemente sensitivo y antisocial. Se
referı́a a sus compañeros formalmente, demandando que hicieran lo mismo con él. Odió la escuela y mantuvo
únicamente calificaciones promedio.
En 1906, inició sus estudios de ingenierı́a mecánica en Berlin, y en 1908, comenzó su doctorado eningenierı́a en la Universidad de Manchester. Sin embargo, el estudio del Principia Matematica de Russell (ver
biograf ́ıa en la pag. ??) como parte de su investigación despertó un interés que lo llevó a visitar a Frege (ver
biografı́a la pag. 43), quien le aconsejó que ingresara a la Universidad de Cambridge como alumno de Russell.
Éste luego escribió que ser profesor de Wittgenstein fue “. . . una de las aventuras intelectuales más interesantes
[de su vida].. . [Wittgenstein tenı́a] pureza intelectual a un grado extraordinario. . . [El] pronto sabı́a todo lo que
podı́a enseñarle.” Ambos pronto comenzaron a trabajar en los fundamentos de la lógica y en lógica matemática.
Sin embargo, durante su perı́do en Cambridge Ludwig sufrió depresión y amenazó con suicidarse en repetidas
ocasiones. En 1913, partió hacia una remota población en Noruega ya que pensaba que no podrı́a llegar al
corazón de sus preguntas más fundamentales mientras estuviese rodeado de académicos. Durante este perı́odo,
que luego consideró como uno de los más apasionados y productivos de su vida, escribió Logik , libro predecesor
de su Tractatus Logico-Philosophicus que serı́a su trabajo más famoso.
Durante la Primera Guerra Mundial, se unió voluntariamente al ejército Austro-Húngaro, ganando meda-
llas por valentı́a y cayendo como prisionero de guerra en noviembre de 1918. Durante su cautiverio, refinó su
trabajo en el Tractatus, para el cual Russell escribió su introducción. Después de un perı́odo de cerca de 7 años
desde 1922 en los que trabajó como profesor de escuela primaria, asistente de jardinero en un monasterio y
ayudante de arquitecto, Ludwig regresó a Cambridge en 1929 donde descubrió con horror que era uno de los
filósofos más famosos del mundo. Sin embargo, antes de optar a una posición en Cambridge debió completar
su doctorado, para lo que presentó al Tractatus como tesis, con Russell y G. Moore como sus jueces. Al final de
su presentación, Ludwig se dirigió a ellos dándoles una palmada en la espalda y diciéndoles: “no se preocupen,
sé que nunca lo entenderán”.
Wittgenstein renunció a su puesto en Cambridge en 1947 para concentrarse en sus escritos. Muri ó de
cáncer de próstata en Cambridge en 1951. Sus últimas palabras fueron: “Dı́ganles que tuve una vida maravillo-
sa”.
15
8/19/2019 Libro Logica Matematica UES
19/171
1.3 T V E Ḿ
valor de verdad de las expresiones p → q y q → p por separado, mostrando sus resultadosen las columnas 3 y 4 (en los pasos 2 y 3) de la tabla. Finalmente, se utilizan los resultados
de los pasos 2 y 3 para calcular los valores de verdad de la última columna utilizando las
reglas para los valores de verdad de
∧.
Los siguientes dos ejemplos muestran más construcciones de tablas de verdad:
EJEMPLO 1.8
Elaborar la tabla de verdad para la proposición ( p ∧ q) ∨ ¬( p → q)Soluci´ on
p q p ∧ q p → q ¬( p → q) ( p ∧ q) ∨ ¬( p → q)0 0 0 1 0 0
0 1 0 1 0 0
1 0 0 0 1 11 1 1 1 0 1
Pasos 1 1 2 3 4 5
Es posible escribir una tabla de verdad equivalente a la anterior de una manera m ás
compacta. En lugar de utilizar columnas separadas para listar los valores de verdad de
las partes componentes de la expresión, puede listarse esos los valores de verdad bajo los
conectivos correspondientes en la f ́ormula original. Esto es ilustrado en la siguiente tabla:
p q ( p ∧ q) ∨ ¬ ( p → q)0 0 0 0 0 1
0 1 0 0 0 1
1 0 0 1 1 0
1 1 1 1 0 1
Pasos 1 1 2 5 4 3
Al igual que en la tabla original, en el primer paso se han listado los valores de las
variables de la expresión. En el segundo paso, los valores de ( p ∧ q) han sido escritosbajo el sı́mbolo ∧. Igualmente, en el paso 3 se escriben bajo → los valores de verdadde ( p
→ q). Los resultados del paso 3 se utilizan para obtener los valores en el paso 4,
escribiendo el resultado bajo ¬. Finalmente, se utilizan los resultados de los pasos 2 y 4para calcular los valores de la expresión completa, escritos bajo ∨. Note que los valores deverdad escritos en el paso 5 de esta tabla coinciden con los escritos en el paso 5 de la tabla
original y que las expresiones son evaluadas en el mismo orden en ambas tablas.
EJEMPLO 1.9
Escriba la tabla de verdad de ( p → q) ∧ [(q ∧ ¬r ) → ( p ∨ r )].Soluci´ on.
16
8/19/2019 Libro Logica Matematica UES
20/171
U E S 1. Ć P
p q r p → q ∧ [(q∧ ¬r ) → ( p ∨ r )0 0 0 1 1 0 1 1 0
0 0 1 1 1 0 0 1 1
0 1 0 1 0 1 1 0 0
0 1 1 1 1 0 0 1 11 0 0 0 0 0 1 1 1
1 0 1 0 0 0 0 1 1
1 1 0 1 1 1 1 1 1
1 1 1 1 1 0 0 1 1
Pasos 1 1 1 2 5 3 2 4 2
Note que ya que la expresión del ejemplo anterior contiene tres variables, son nece-
sarias ocho filas para listar todos las posibles combinaciones para los valores de verdad
de dichas variables. En general, si una expresión contiene n variables, la tabla de verdadresultante deberá tener 2n filas (¿Por qué?).
Dado que nuestra definición de equivalencia depende únicamente del valor de verdad
de la expresión, dos proposiciones serán equivalentes si tienen la misma tabla de verdad.
Por ejemplo, podemos demostrar que p → q es lógicamente equivalente7 a ¬q → ¬ pconstruyendo la tabla de verdad:
* *
p q p → q ¬q ¬ p ¬q → ¬ p0 0 1 1 1 1
0 1 1 0 1 1
1 0 0 1 0 0
1 1 1 0 0 1
1.4 Tautologı́as y Contradicciones.......................................................................................................
Se llama tautologı́a a toda proposición cuyo valor de verdad es siempre verdadero, sin
importar el valor de verdad de las proposiciones componentes.
EJEMPLO 1.10Muestre la tabla de verdad de la tautologı́a clásica p → p:Soluci´ on
p p → p0 1
1 1
7La definición de equivalencia l ´ ogica se estudiará más detalladamente en la sección 1.5.
17
8/19/2019 Libro Logica Matematica UES
21/171
1.4 Tı́ C E Ḿ
EJEMPLO 1.11
Muestre que la proposición [ p∧
( p →
q)] →
q es una tautologı́a.
Soluci´ on
p q [ p∧ ( p → q)] → q0 0 0 1 1
0 1 0 1 1
1 0 0 0 1
1 1 1 1 1
Pasos 1 1 3 2 4
EJEMPLO 1.12Muestre que ¬( p ∨ q) ↔ (¬ p ∧ ¬q) es una tautologı́a.Soluci´ on
p q ¬ ( p ∨ q) ↔ (¬ p ∧ ¬q)0 0 1 0 1 1 1 1
0 1 0 1 1 1 0 0
1 0 0 1 1 0 0 1
1 1 0 1 1 0 0 0
Pasos 1 1 3 2 4 2 3 2
Por otro lado, una proposición compuesta que siempre es falsa, sin importar el valor
de verdad de sus componentes, es llamada una contradicci´ on.
EJEMPLO 1.13
Construya la tabla de verdad de la contradicción clásica p ∧ ¬ p.Soluci´ on
p ∧ ¬ p0 0 1
1 0 0
Pasos 1 3 2
Observe que una proposición compuesta P es una contradicción si y sólo si ¬P es unatautologı́a. Es decir, la negación de una tautologı́a es una contradicción y viceversa.
18
8/19/2019 Libro Logica Matematica UES
22/171
U E S 1. Ć P
Ejercicios.......................................................................................................
1. Construya las tablas de verdad de:a) p ∧ ¬ p b) p ∨ ¬ pc) ¬( p ∧ q) d ) ¬( p ∨ q)e) p ↔ ¬ p f ) ¬¬ pg) ¬ p ∧ ¬q h) ¬ p ∨ ¬q
2. Construya las tablas de verdad de:
a) ( p → q) → [( p ∨ ¬q) → ( p ∧ q)]b) [( p ∨ q) ∧ r ] → ( p ∧ ¬q)c) [( p ↔ q) ∨ ( p → r )] → (¬q ∧ p)d )
¬( p
∨q)
→ r
e) ¬(( p ∨ q) → r )3. Pruebe o refute lo siguiente usando tablas de
verdad:
a) (q → p) ↔ ( p ∧ q) es una tautologı́ab) ( p ∧ ¬q) → ( p → q) es una tautologı́ac) ( p ∧ q) → ( p ∨ q) es una tautologı́aObservación: Basta una lı́nea de la tabla de
verdad para mostrar que una proposición no
es una tautologı́a.4. Encuentre una proposición compuesta con
los conectivos ∧, ∨ y ¬ para cada una de lassiguientes tablas de verdad:
a)
p q ???
0 0 1
0 1 0
1 0 1
1 1 1
b)
p q ???
0 0 0
0 1 1
1 0 1
1 1 0
5. a) Escriba una proposición compuesta que
sea verdadera cuando exactamente una de
las proposiciones p, q y r sea verdadera.
b) Escriba una proposición compuesta que
sea verdadera cuando exactamente dos de
las tres proposiciones p, q y r sean verda-
deras.
1.5 Equivalencias Lógicas.......................................................................................................
Hasta ahora hemos tomado cinco palabras comunes, y, o, no, implica y equivalente,
y les hemos dado un significado preciso en el lenguaje común. Obtuvimos la precisión
deseada al basar nuestras definiciones únicamente en el valor de verdad de las proposi-
ciones, sin tomar en cuenta cualquier relación causal u otras conexiones que las palabras
puedan expresar. En el caso de las primeras tres, y, o y no, las definiciones precisas de la
conjunci´ on, disyunci´ on y negaci´ on, respectivamente, se ajustan razonablemente bien con
el uso común de esas palabras fuera de las matemáticas. En el caso de las últimas dos,
implica y equivale, definimos contrapartes precisas y formales llamadas condiconal y bi-
condicional, respectivamente, que tienen algunas propiedades comunes con el significado
común de implica y equivale pero es diferente en otras maneras. Es especialmente esta
última la que tendrá nuestra atención en esta sección.
Como se observó en la sección anterior, es posible utilizar tablas de verdad para com-
probar que dos expresiones p y q son l ´ ogicamente equivalentes al observar que ambas
19
8/19/2019 Libro Logica Matematica UES
23/171
1.5 E Ĺ E Ḿ
# Equivalencia Lógica Nombre
1 ¬¬ p ⇔ p Doble negación2 a) ( p ∨ q) ⇔ (q ∨ p) Leyes conmutativas
b) ( p
∧q)
⇔ (q
∧ p)
c) ( p ↔ q) ⇔ (q ↔ p)3 a) [( p ∨ q) ∨ r ] ⇔ [ p ∨ (q ∨ r )] Leyes asociativas
b) [( p ∧ q) ∧ r ] ⇔ [ p ∧ (q ∧ r )]4 a) [ p ∨ (q ∧ r )] ⇔ [( p ∨ q) ∧ ( p ∨ r )] Leyes distributivas
b) [ p ∧ (q ∨ r )] ⇔ [( p ∧ q) ∨ ( p ∧ r )]5 a) ( p ∨ p) ⇔ p Leyes de idempotencia
b) ( p ∧ p) ⇔ p6 a) ( p ∨ c) ⇔ p Leyes de identidad
b) ( p ∧ t ) ⇔ p7 a) ( p
∨t )
⇔ t Leyes de dominación
b) ( p ∧ c) ⇔ c8 a) ( p ∨ ¬ p) ⇔ t Leyes de negación
b) ( p ∧ ¬ p) ⇔ c9 a) ¬( p ∨ q) ⇔ (¬ p ∧ ¬q) Leyes de De Morgan
b) ¬( p ∧ q) ⇔ (¬ p ∨ ¬q)c) p ∨ q ⇔ ¬(¬ p ∧ ¬q)d) p ∧ q ⇔ ¬(¬ p ∨ ¬q)
10 ( p → q) ⇔ (¬q → ¬ p) Contrarrecı́proca (o contrapositiva)11 a) ( p → q) ⇔ (¬ p ∨ q) Implicación
b) ( p → q) ⇔ ¬( p ∧ ¬q)c) ( p ∨ q) ⇔ (¬ p → q)d) ( p ∧ q) ⇔ ¬( p → ¬q)
12 ( p ↔ q) ⇔ [( p → q) ∧ (q → p)] Equivalencia
Tabla 1.1: Algunas equivalencias lógicas. En esta tabla una contradicción es representada
por la letra c y una tautologı́a por la letra t .
obtienen los mismos valores de verdad para todas las combinaciones posibles de los va-
lores de verdad de las proposiciones simples que las componen. En tal caso escribimos
p ⇔ q, que se lee “ p es lógicamente equivalente a q”.En nuestra discusión de los conectivos lógicos introdujimos ya algunas equivalencias.
Por ejemplo, observamos que ¬(¬ p) es equivalente a p, que p → q es equivalente a ¬ p∨qy que ¬( p ∨ q) es equivalente a ¬ p ∧ ¬q. Estas y otras equivalencias útiles son listadas enla tabla 1.1.
Muchas de las equivalencias en la lista deberı́an recordarle a reglas similares con los
operadores +, − y · en álgebra. Como en el álgebra, estas reglas pueden ser aplicadas aexpresiones más complejas, y pueden ser combinadas para simplificar equivalencias más
20
8/19/2019 Libro Logica Matematica UES
24/171
U E S 1. Ć P
complicadas. Cualquiera de las letras en estas equivalencias pueden ser reemplazadas por
expresiones complicadas y la equivalencia resultante seguirá siendo verdadera. Por ejem-
plo, reemplazando p en la ley de doble negación con la fórmula q ∨ ¬r es posible ver que
¬¬(q
∨ ¬r ) es equivalente a q
∨ ¬r . Esta observación es importante dado que las equiva-
lencias listadas muestran la forma de las mismas, por lo que más que memorizarlas, es útil
entender su significado.
Por ejemplo, las leyes conmutativas nos dicen que con los conectivos ∧, ∨ y ↔, elorden de las proposiciones involucradas no es importante. Las leyes distributivas nos dicen
que, ası́ como en el álgebra la multiplicación puede ser distribuida sobre la suma (es por
esto que x · ( y +w) = x · y + x · w), el conectivo ∧ puede ser distribuido sobre ∨, y ∨ puedeser distribuido sobre ∧8.
Las leyes de identidad y dominación nos muestran el comportamiento de las propo-
siciones cuando son combinadas en disyunción o conjunción con una tautologı́a o una
contradicción. Note que estas leyes son similares al comportamiento de las expresiones
algebraicas cuando se les suma o se les multiplica por cero o por uno. Por ejemplo, de lamisma manera en que x · 1 es igual a x y que x · 0 es igual a 0, p ∧ t es equivalente a py p ∧ c es equivalente a c. Ası́ mismo, las leyes de idempotencia y negación describen elcomportamiento de las proposiciones cuando son combinadas mediante los operadores ∧y ∨ consigo mismas y con su negación.
Note que, aunque muchas de las leyes de la tabla 1.1 tienen contrapartes en el álgebra
al que está acostumbrado el lector, no deben tomarse las leyes del álgebra para el cálculo
proposicional. Por ejemplo, cuando se tiene una expresión como −( x − y) en álgebra, esposible “meter el signo menos en el paréntesis” aplicándolo a ambos términos para obtener
− x − (− y) = − x+ y. Sin embargo, en el álgebra proposicional a una expresión como ¬(q ∧¬ p) no puede aplicársele una ley parecida a la anterior para obtener (¬ p ∧ ¬¬q), que esequivalente a (¬ p∧q). Para poder “meter la negación en el paréntesis” cuando el conectivoprincipal dentro del paréntesis es una conjunción o disyunción, es necesario utilizar la ley
de De Morgan que nos dice que, aparte de negar cada una de las proposiciones conectadas,
también debe cambiarse la disyunción por conjunción o la conjunción por disyunción.
Como muestran los siguientes ejemplos, las equivalencias de la tabla 1.1 nos permiten
simplificar expresiones lógicas o encontrar otras expresiones que, aunque con mayor o
menor complejidad, tengan el mismo significado.
EJEMPLO 1.14
Demostrar la equivalencia lógica
[( p ∨ q) ∨ ( p ∨ r )] ⇔ ( p ∨ q) ∨ r
sustituyendo sucesivamente proposiciones equivalentes.
8Note aquı́ una diferencia con las leyes distributivas del álgebra: aunque la multiplicación puede ser distri-
buida sobre la suma, la suma no puede ser distribuida sobre la multiplicación. Es decir, en general, x + y · w ( x + y) · ( x + w).
21
8/19/2019 Libro Logica Matematica UES
25/171
1.5 E Ĺ E Ḿ
Soluci´ on.
( p ∨ q) ∨ ( p ∨ r ) ⇔ [( p ∨ q) ∨ p] ∨ r ley asociativa
⇔ [ p ∨ (q ∨ p)] ∨ r ley asociativa⇔ [ p ∨ ( p ∨ q)] ∨ r ley conmutativa⇔ [( p ∨ p) ∨ q] ∨ r ley asociativa⇔ ( p ∨ q) ∨ r ley idempotencia
EJEMPLO 1.15
Encontrar una proposición lógicamente equivalente a
( p ∧ q) → (¬ p ∧ q)
que no utilice el conectivo ∧.Soluci´ on.
( p ∧ q) → (¬ p ∧ q) ⇔ ¬(¬ p ∨ ¬q) → (¬ p ∧ q) De Morgan⇔ ¬(¬ p ∨ ¬q) → ¬(¬¬ p ∨ ¬q) De Morgan
⇔ ¬(
¬ p
∨ ¬q)
→ ¬( p
∨ ¬q) Doble negación
Esta última proposición no usa el conectivo ∧.
EJEMPLO 1.16
Simplificar cada una de las proposiciones siguientes:
a) ( p ∨ q) ∧ ¬ p
( p ∨ q) ∧ ¬ p ⇔ ¬ p ∧ ( p ∨ q) Conmutativa⇔ (¬ p ∧ p) ∨ (¬ p ∧ q) Distributiva⇔ c ∨ (¬ p ∧ q) Negación⇔ (¬ p ∧ q) ∨ c Conmutativa⇔ (¬ p ∧ q) Identidad
22
8/19/2019 Libro Logica Matematica UES
26/171
U E S 1. Ć P
b) p ∨ ( p ∧ q)
p ∨ ( p ∧ q) ⇔ ( p ∧ t ) ∨ ( p ∧ q) Identidad
⇔ p
∧(t
∨q) Distributiva
⇔ p ∧ t Dominación⇔ p Identidad
c) ¬( p ∨ q) ∨ (¬ p ∧ q)
¬( p ∨ q) ∨ (¬ p ∧ q) ⇔ (¬ p ∧ ¬q) ∨ (¬ p ∧ q) De Morgan⇔ ¬ p ∧ (¬q ∨ q) Distributiva
⇔ ¬ p
∧t Negación
⇔ ¬ p Identidad
Como se mostró en la sección anterior, todos los resultados de los ejemplos anteriores
pueden ser comprobados a través de tablas de verdad, asegurándonos que las columnas de
las expresiones dadas tengan los mismos valores de verdad para los mismos valores de las
variables lógicas.
Ejercicios.......................................................................................................
1. Verifique las siguientes equivalencias lógicas
(tabla 1.1) utilizando tablas de verdad:
a) Las leyes distributivas
b) Las leyes de identidad
c) La contrarrećıproca
d) La regla 9-c y 9-d
2. Demuestre utilizando equivalencias lógicas
que:
a) ( p → ¬q) ⇔ (q → ¬ p)b) [( p ∧ q) → r ] ⇔ [( p → r ) ∨ (q → r )]c) [ p → (q → r )] ⇔ [( p ∧ q) → r ]d) [( p ∨ r ) ∧ (q → r )] ⇔ [( p → q) → r ]
e) [ p ∧ ( p ∨ q)] ⇔ pf) ¬( p ∨ (¬ p ∧ q)) ⇔ (¬ p ∧ ¬q)
3. Demuestre, por medio de equivalencias lógi-
cas, que las siguientes proposiciones son tau-
tologı́as:
a) ( p ∨ q) ∧ (¬ p ∨ r ) → (q ∨ r )b) [( p → q) ∧ (q → r )] → ( p → r )c) ( p ∧ q) → ( p ∨ q)d) ¬q → [( p ∧ q) → r ]
4. Simplifique (escriba con un mı́nimo de co-
nectivos):a) ¬( p ∨ ¬q)b) ¬(¬ p → q)
c) ¬( p ∧ ¬q)d) ¬(¬ p ∧ ¬q)
23
8/19/2019 Libro Logica Matematica UES
27/171
1.5 E Ĺ E Ḿ
e) ¬(¬ p ↔ q)f) ¬(¬ p → ¬q)
5. Dadas dos proposiciones p y q, el conectivo
“ó excluible”, simbolizado por p
⊕q, es ver-
dadero cuando únicamente p es verdadera ocuando únicamente q es verdadera.
a) Construya la tabla de verdad de p ⊕ q.b) Muestre que p ⊕ q tiene la misma tabla de
verdad que ¬( p ↔ q).c) Construya una tabla de verdad para p ⊕ p,
( p ⊕ q) ⊕ r y ( p ⊕ p) ⊕ p.6. Muestre que ( p ⊕ q) ⇔ [( p ∨ q) ∧ ¬( p ∧ q)],
donde ⊕ es el “o excluible” introducido en elejercicio 5.
7. Demuestre o refute que
a) [ p → (q → r )] ⇔ [( p → q) → ( p → r )]b) [ p ⊕ (q → r )] ⇔ [( p ⊕ q) → ( p ⊕ r )]
8. Toda proposición compuesta se puede escri-
bir utilizando únicamente los conectivos ¬ y∨. Esto resulta de las equivalencias:
( p → q) ⇔ (¬ p ∨ q)( p ∧ q) ⇔ ¬(¬ p ∨ ¬q)
( p ↔ q) ⇔ [( p → q) ∧ (q → p)]
Encuentre proposiciones lógicamente equiva-
lentes a las siguientes, utilizando solamente
los conectivos ¬ y ∨.a) p
↔ q
c) ( p → q) ∧ (q ∨ r )b) ( p
∧q)
→ (
¬q
∧r )
d) p ⊕ q9. La raya de She ff er es el conectivo | definido
por la tabla de verdad:
C S P (1839-1914) fue un lógico, matemático, filósofo y cient́ıfico nacido en Cambridge,Massachusetts, E.E. U.U. Hijo de Sarah Hunt y Benjamin Peirce, un profesor de astronom ı́a y matemática en la
Universidad de Harvard. A los 12 años, Charles leyó una copia del libro Elementos de L ´ ogica, para ese entonces
el libro de texto lı́der en la materia, lo que comenzó su fascinación con la lógica y el razonamiento. Obtuvo su
Licenciatura y Maestrı́a en Harvard y una Maestrı́a en quı́mica de la Lawrence Scientific School.
Entre 1859 y 1891, Charles se empleó intermitentemente en el Servicio Costero Estadounidense, don-
de trabajó principalmente en geodesia y gravimetrı́a, refinando el uso de péndulos para determinar pequeñas
variaciones locales en la fuerza de gravedad terrestre. Este trabajo lo libró de tomar parte de la guerra civil
estadounidense. De 1869 a 1872, trabajó como asistente en el observatorio astronómico de Harvard, realizando
importantes avances en la determinación de la brillantez de las estrellas y la forma de la Vı́a Láctea. En 1878,
fue el primero en definir el metro en t érminos de la longitud de onda de la luz a cierta frecuencia, definición
utilizada hasta 1983. En 1891, Peirce fue obligado a renunciar a su puesto en el Servicio.
De 1879 a 1883, Peirce fue nombrado profesor de l ógica en la Universidad John Hopkins, el cual fue
el único puesto académico que ocupó durante su vida. En los últimos años de su vida, Peirce vivió con du-
ras limitaciones económicas debido al desempleo, viviendo principalmente de consultoŕıas mal pagadas y de
donaciones de amigos, especialmente de William James, quien desde 1898 hasta 1910 escribi ó a sus amigos
académicos, pidiéndoles hacer contribuciones económicas para mantener a Peirce.
Peirce realizó una serie de admirables descubrimientos en matemáticas, que casi en su totalidad fueron
apreciados únicamente después de su muerte. Entre otros aportes, mostró que lo que ahora llamamos ´ Algebra
Booleana podı́a ser expresada por medio de una sola operación binaria, anticipándose por 33 años a Sheff er.
Además, se anticipó por más de 50 años a la observación que cálculos booleanos pueden ser realizados con
dispositivos eléctricos, idea que se utilizó años más tarde para producir computadoras digitales. Sentó las bases
para la teorı́a axiomática de conjuntos, anticipándose a Zermelo por casi dos décadas. Descubrió la axiomati-
zación de la aritmética de los números naturales unos cuantos años antes que Dedekind y Peano. Descubrió,
independientemente de Dedekind, la importante definición formal de un conjunto infinito.
Aunque descrito por Bertrand Russell como “sin lugar a dudas [. . . ] fue una de las mentes más originales
de finales de siglo diecinueve, y ciertamente el más grande pensador Estadounidense de todos los tiempos”,
Peirce fue en gran parte ignorado durante su vida, y la literatura acerca de él fue escasa hasta después de la
Segunda Guerra Mundial. Después de su muerte se descubrieron cerca de 1650 manuscritos, totalizando cerca
de 100,000 páginas, muchos de los cuales siguen sin publicarse hasta este dı́a.
24
8/19/2019 Libro Logica Matematica UES
28/171
U E S 1. Ć P
p q p | q0 0 1
0 1 1
1 0 1
1 1 0
Todas las proposiciones compuestas pueden
escribirse utilizando únicamente este conec-
tivo.
a) Muestre que ¬ p ⇔ p | pb) Muestre que p ∨ q ⇔ ( p | p) | (q | q)c) Encuentre una proposición equivalente a
p ∧ q utilizando únicamente la raya deSheff er.
d) Haga lo mismo para p → qe) Haga lo mismo para p ⊕ q
10. Algunos matemáticos utilizan el sı́mbolo ↓como la negación de la disyunción. Es decir, p ↓ q significa “ni p ni q”.a) Construya la tabla de verdad para p ↓ q.b) Encuentre una f ́ormula utilizando sólo los
conectivos ∧, ∨ y ¬ que sea equivalentea p ↓ q. Verifique su respuesta utilizandotablas de verdad.
c) Encuentre fórmulas usando el conectivo ↓que sean equivalentes a ¬ p, p ∨ q y p ∧ q.
1.6 Validez Lógica de Argumentos.......................................................................................................
Una aplicación interesante y útil del cálculo proposicional es el análisis de ciertos
tipos de argumentos para verificar su validez lógica. Un argumento consiste de una serie
de proposiciones “dadas”, cuya conjunción constituye la premisa del argumento y juntas
deben llevar a una conclusi´ on.
Formalmente, un argumento que consiste de la premisa p1 ∧ p2 ∧ p3 ∧ . . . ∧ pn (cadauna de las pi que conforman a la premisa puede ser llamada una premisa parcial) y de laconclusión q es un argumento v´ alido si y sólo si la proposición p1 ∧ p2 ∧ p3 ∧ . . . ∧ pn →q es una tautologı́a. El requisito para la validez de un argumento es, por lo tanto, que
la conclusión sea verdadera en todos los casos en que todas las premisas parciales sean
verdaderas.
El siguiente ejemplo muestra el formato estándar en que las premisas y la conclusión
son presentadas:
EJEMPLO 1.17
Verifique la validez del argumento
p
p → q¬q ∨ r
∴ r
Soluci´ on. Las proposiciones sobre la lı́nea horizontal son las premisas parciales, mientras
que la que se encuentra bajo la lı́nea es la conclusión. El sı́mbolo ∴ se lee “por lo tanto”.
Para verificar la validez del argumento, es necesario comprobar que [ p ∧ ( p → q) ∧ (¬q ∨r )] → r es una tautologı́a. Usando una tabla de verdad, el lector deberı́a verificar que enefecto, el argumento dado es lógicamente válido.
25
8/19/2019 Libro Logica Matematica UES
29/171
1.6 V Ĺ A E Ḿ
EJEMPLO 1.18
Exprese simbólicamente y analice la validez del argumento “Si las tasas de interés bajan,
la economı́a mejora. Si la economı́a mejora, el desempleo baja. Para que las autoridades
actuales sean reelegidas, el desempleo debe bajar. Por lo tanto, una condición suficiente
para que las autoridades actuales sean reelectas es que la tasa de interés baje”.
Soluci´ on. Primero simbolizamos cada proposición simple en el argumento.
p : las tasas de intereses bajan
q : la economı́a mejora
r : el desempleo baja
s : las autoridades actuales son reelectas
De aquı́ que las premisas parciales tienen la forma p → q, q → r y s → r . Laconclusión tiene la forma p → s. Por lo tanto, el argumento en forma simbólica es:
p → qq → r s → r
∴ p → sEl lector deberá verificar construyendo una tabla de verdad, que el argumento no es
lógicamente válido.
Las tautologı́as [ p ∧ ( p → q)] → q (modus ponens), [( p → q) ∧ (q → r )] → ( p → r )(transitividad de la implicació n ) y [ p → (q → r )] ↔ [( p∧q) → r ], proveen un método paraconcluir la validez de un argumento (o de sospechar la invalidez) que nos permite evitar
escribir repetidamente tablas de verdad extensas. Modus ponens nos indica que podemos
concluir q cuando tengamos p y p → q. La transitividad de las implicaciones dice quepodemos reemplazar dos hipótesis de la forma ( p
→ q) y (q
→ r ) por la hipótesis ( p
→ r ),
si hacerlo resulta ventajoso. La tercera implicación nos dice que si nuestra conclusión tiene
la forma q → r , podemos agregar q a la lista de premisas parciales y deducir r en lugar deq → r , a partir de esta lista expandida. Finalmente, recuerde la utilidad de la equivalencialógica: una proposición puede ser reemplazada por cualquier proposición equivalente. Este
procedimiento se ilustra en los siguientes ejemplos.
EJEMPLO 1.19
Analice el argumento del ejemplo 17 sin utilizar tablas de verdad.
Soluci´ on. La pregunta se reduce a si es posible o no deducir de manera válida a r de la
presunta veracidad de cada una de las tres premisas parciales p, p
→ q y
¬q
∨r . Primero,
utilizamos la equivalencia de la forma ( p → q) ⇔ (¬ p ∨ q) (tabla 1.1, equivalencia 11a),para sustituir a ¬q∨r por q → r para que las premisa se convierta en p∧( p → q)∧(q → r ).De p ∧ ( p → q) podemos concluir q, por modus ponens. De q y q → r podemos concluirr nuevamente utilizando modus ponens. Por lo tanto, este análisis muestra que r puede ser
deducido lógicamente a partir de la premisa, por lo que el argumento es válido.
26
8/19/2019 Libro Logica Matematica UES
30/171
U E S 1. Ć P
EJEMPLO 1.20
Analice el argumento del ejemplo 18 sin utilizar tablas de verdad.
Soluci´ on. La pregunta es si podemos derivar s de p dadas las hipótesis p → q, q → r y s
→ r . Primero, agregamos p a la lista de hipótesis. La pregunta es ahora si podemos
derivar s de la lista expandida de premisas parciales. De p y p → q, tenemos q. De q y q →r , obtenemos r . Ahora tenemos r y s → r . En este punto, la cadena de razonamientos sedetiene. No tenemos manera alguna de concluir s a partir de r ∧ (s → r ) (puede comprobarque [r ∧ (s → r )] → s no es una tautologı́a). Por lo tanto existe razón para dudar dela validez del argumento. Para demostrar la invalidez, debemos proveer una combinación
de valores de verdad para la cual la implicación en cuestión es falsa. Esto también puede
realizarse sin necesidad de escribir una tabla de verdad completa.
El razonamiento sigue la siguiente lı́nea: queremos encontrar valores de verdad para
p, q, r y s tal que la conjunción ( p → q) ∧ (q → r ) ∧ (s → r ) de las premisas parcialessea verdadera mientras que la conclusión p
→ s sea falsa. Claramente, para que p
→ s
sea falsa, p debe ser verdadera y s debe ser falsa. En ese caso, para que p → q seaverdadera, entonces q debe ser verdadera. Pero entonces r debe también ser verdadera
para que q → r sea verdadera. Note que si s es falsa y r es verdadera, la premisa parcials → r es verdadera. Por lo tanto, hemos encontrado una combinación de valores de verdadpara las cuales la premisa del argumento es verdadera mientras que la conclusión es falsa.
Esto prueba concluyentemente la invalidez del argumento.
Los ejercicios de esta sección pueden realizarse tanto utilizando tablas de verdad co-
mo el razonamiento de los ejemplos anteriores. Aún cuando el procedimiento mecánico
de construcción de tablas de verdad parezca más sencillo de realizar, es más provechoso
para su formación el intentar utilizar el razonamiento lógico anterior. A continuación se
presenta un último ejemplo utilizando este razonamiento.
EJEMPLO 1.21
Determine si el siguiente argumento lógico es válido. “Si estudio o soy un genio, entonces
aprobaré el curso. Si apruebo el curso, entonces me permitirán tomar el siguiente curso.
Por lo tanto, si no me permiten tomar el siguiente curso, entonces no soy un genio”.
Soluci´ on. Si nombramos a las proposiciones de la siguiente manera:
s = “estudio”
g = “soy un genio”
p = “aprobaré el curso”
a = “me permitirán tomar el curso siguiente”entonces el argumento puede ser representado simbólicamente de la siguiente manera:
s ∨ g → p p → a
∴ ¬a → ¬gYa que la conclusión es una implicación, utilizamos la táctica presentada anteriormente
de modificar el problema suponiendo que el antecedente es una de las premisas y tratando
de demostrar
27
8/19/2019 Libro Logica Matematica UES
31/171
1.6 V Ĺ A E Ḿ
1. s ∨ g → p hipótesis2. p → a hipótesis3. g → g ∨ s Regla 12 (adición)4. g
→ s
∨g Por 3 y ley conmutativa 2-a
5. g → p Por 4, 1 y silogismo hipotético (regla 33)6. g → a Por 5, 2 y silogismo hipotético (regla 33)7. ¬a → ¬g Por 6 y contrarecı́proca (regla 9)
Ejercicios.......................................................................................................
1. Que haga buen clima es necesario para tener
un jardı́n bonito. El jardı́n es bonito. Por lo
tanto, el clima fue bueno.
2. Si hoy es lunes, entonces mañana es martes.
Pero hoy no es lunes. Por lo tanto, mañana no
es martes.
3. Hoy es lunes o martes. Pero hoy no es lunes.
Por lo tanto, hoy es martes.
4. Perderé mi trabajo a menos que Sandra siga
trabajando. Sandra será despedida sólo si us-
ted lo recomienda. Por lo tanto, retendré mi
trabajo si no recomienda que Sandra sea des-
pedida.5. Si 5+7 = 12, entonces 6 > 8. Si 5+7 = 7+5,
entonces 5 + 7 = 12. Pero 5 + 7 = 7 + 5. Por
lo tanto, podemos concluir que 6 > 8.
6. Si el dólar sube de valor, las exportaciones
se reducen. El desempleo aumentará a menos
que se detenga la reducción en las exporta-
ciones. Una baja en las tasas de interés es ne-
cesaria para debilitar el precio del dólar. Por
lo tanto, una baja en las tasas de interés es
suficiente para causar disminución en el des-
empleo.7. Claudia pasará el examen si entiende el tema.
Si Claudia pasa el examen, entonces apro-
bará la materia. Por lo tanto, si Claudia en-
tiende el tema, entonces aprobará la materia.
8. Si estudio toda la noche para el examen de
lógica matemática, estaré cansado. Si estoy
cansado, no haré la tarea de Geometrı́a. Por
lo tanto, para pasar el examen de Lógica Ma-
temática y hacer la tarea de Geometrı́a, es ne-
cesario que no estudie toda la noche.
9. Dado que p → q es una tautologı́a, para queq → p sea una tautologı́a es necesario y su-ficiente que p ↔ q sea una tautologı́a. Sabe-mos que p
→ q es una tautologı́a y que p
↔ q
no es una tautologı́a. Por lo tanto q → p noes una tautologı́a.
10. Si Mercedes no se encontró con Mirna ano-
che, entonces o Mercedes es la asesina o Mir-
na estaba fuera de la ciudad. Si Mercedes
no fue la asesina, entonces Mirna no se en-
contró con Mercedes anoche y el asesinato
ocurrió en un hotel. Si el asesinato ocurrió en
un hotel, entonces o Mercedes fue la asesina
o Mirna estaba fuera de la ciudad. Pero Mer-
cedes se encontró con Mirna anoche y Mir-
na no estaba fuera de la ciudad. Por lo tanto,
Mercedes fue la asesina.
28
8/19/2019 Libro Logica Matematica UES
32/171
Ć P2 C A P I T U L O
Los humanos tienden a confundir la fuerza de su
sentimiento con la fuerza de su argumento. La
mente exacerbada resiente siempre el frı́o tacto y
el implacable escrutinio de la l´ ogica.
-William Gladstone
Existen muchos tipos de sentencias tanto en
el lenguaje matemático como en el común que
no pueden ser representadas usando el cálcu-
lo proposicional. Además del factor externo de
tener que enlazar proposiciones a través de co-
nectivos lógicos, existe un factor interno en pro-
posiciones que contienen palabras como “todos”
o “algunos” que requiere un análisis lógico más
allá del posible con el cálculo proposicional, co-
mo lo muestra el siguiente famoso argumento:
Todos los hombres son mortales
S´ ocrates es un hombre
Por lo tanto, S´ ocrates es mortal
Es posible expresar este argumento como
tres proposiciones simples:
p: Todos los hombres son mortalesq: S ´ ocrates es un hombre
r : S ´ ocrates es mortal
pero dicho argumento tendrı́a la forma:
p
q
∴ r
el cual no es un argumento válido dentro del
cálculo proposicional. Es claro que en este caso
Top Related