Libro Logica Matematica UES

8/19/2019 Libro Logica Matematica UES

1/171

Índice general

1. Cálculo Proposicional 1

1.1. Proposiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.2. Conectivos Lógicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.1. Conjunción, Disyunción y Negación . . . . . . . . . . . . . . . . 4

1.2.2. Condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.3. Bicondicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3. Tablas de Verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4. Tautoloǵıas y Contradicciones . . . . . . . . . . . . . . . . . . . . . . . 17

1.5. Equivalencias Lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.6. Validez Lógica de Argumentos . . . . . . . . . . . . . . . . . . . . . . . 25

2. Cálculo de Predicados 29

2.1. Predicados y Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . 302.2. Traducción del lenguaje natural . . . . . . . . . . . . . . . . . . . . . . . 31

2.3. Propiedades de los cuantificadores . . . . . . . . . . . . . . . . . . . . . 40

2.3.1. Negación de Proposiciones con Cuantificadores . . . . . . . . . . 42

2.4. Validez lógica de argumentos con predicados . . . . . . . . . . . . . . . 46

3. Teorı́a de Conjuntos 51

3.1. Definiciones y Notaciones Básicas . . . . . . . . . . . . . . . . . . . . . 52

3.2. Operaciones con Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.3. Diagramas de Venn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.4. Álgebra de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.5. Familias de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4. Métodos de Demostración 85

4.1. Conceptos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.2. Demostrando Condicionales . . . . . . . . . . . . . . . . . . . . . . . . 88

4.3. Demostrando Bicondicionales . . . . . . . . . . . . . . . . . . . . . . . 97

4.4. Demostración por casos . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.5. Demostraciones por Contradicción . . . . . . . . . . . . . . . . . . . . . 104


2/171

U E S ÍNDICE GENERAL

4.6. El Principio de Inducción Matemá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. Representación Gráfica de las Relaciones . . . . . . . . . . . . . . . . . 133

5.5. Relación de Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

5.6. Relaciones de Equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . 147

6. Funciones 157

6.1. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

6.2. Clasificación de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . 160

6.3. Composición de Funciones . . . . . . . . . . . . . . . . . . . . . . . . . 164

6.4. Funciones invertibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166


3/171

ÍNDICE GENERAL E Ḿ


4/171

Ć 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 través del espejo”

Según nuestras mejores estimaciones, el len-guaje humano ha sido una manera eficiente de

comunicarnos por alrededor de 100,000 añ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 época del año diferente depen-

diendo si se encuentra en el hemisferio norte

o sur, o en áreas, como la nuestra, que cuenta

únicamente con dos estaciones. “Tengo hambre”

significa que yo, Humberto Sermeño, tiene ham-

bre, y tiene un significado diferente si usted di-

ce las mismas palabras. Las siguientes sentencias

son tambié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 tendrá 10 en

la materia”.

4. “Todo salvadoreño tiene un sueño”.

¿Qué 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, ¿tendrá 10 en la materia? ¿Puede tener 10

aún cuando no pueda resolver alguno de los pro-

blemas? ¿Implica la última sentencia que todos

los salvadoreños tienen el mismo sueño o puede

cada uno tener un sueño diferente?

Algo de incerteza es tolerable en la conver-

sación normal. Desafortunadamente, cuando se

necesita formular ideas de manera precisa -como

en matemáticas- estas ambigü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 matemático,

debemos investigar el problema de cómo hablar

matemáticamente.

En este capı́tulo se inicia definiendo los ti-

pos de sentencias del lenguaje natural que son

útiles en el lenguaje matemático, dándole un sig-

nificado preciso a palabras como “y”, “o”, “no”,

“implica” y “equivale”, los cambios lógicos que

estas palabras traen al unir dos o más sentencias,y los sı́mbolos matemáticos utilizados para re-

presentarlas1. Finalmente, se introducirá la for-

malización de dichos conceptos y las propieda-

des inherentes en ellos en la forma del álgebra

proposicional.

1Mucho de este trabajo fue iniciado por los Griegos hace más de 2,000 años.

1


5/171

1.1 P E Ḿ

1.1 Proposiciones.......................................................................................................

Coinsidere las sentencias matemáticas “2 + 5 = 7” y “7 < 5”. De aritmética básica,

sabemos que la primera es cierta, mientras que la segunda es falsa. Pero, ¿qué 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-

ció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 designación de verdadero o falso, de los cuales sólo uno es asignable a una propo-

sición, es llamado el valor de verdad de la proposición.

EJEMPLO 1.1

Las siguientes son todas proposiciones:

a) Parı́s es la capital de Canadá.

b) El 15 de abril de 2009 es un miércoles.

c) La tierra es plana.

d) 3 + 5 = 8

e) 2893015674434 + 1 es un número primo

f) Todo entero par mayor que 2 es la suma de dos nú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 ú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 cuál es el valor de verdad de una sentencia para

poder clasificarla como proposición. Es suficiente con que sea posible en algún momento

asignarle uno de los dos valores.

EJEMPLO 1.2

Las siguientes sentencias no son proposiciones:

a) ¿Regresamos el martes o el miércoles?

b) ¡Ayúdeme por favor!c) X − Y = Y − X .d) Esta proposición es falsa.

En general, las preguntas y las órdenes no son proposiciones, por lo que (a) y (b) no

pueden ser clasificadas como tales. Por otra parte (c) no es proposición porque no especı́fi-

2Esta es la conjetura de Goldbach, que data de 1742.

2


6/171

U E S 1. Ć P

ca qué clase de objetos son X e Y . Finalmente, (d), aunque pareciera a primera vista ser

una proposición, es en realidad una paradoja: Si la proposición fuera verdadera, entonces

deberı́a ser falsa; si la proposició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 ón

de proposición.

Se deben evitar frases ambiguas como las siguientes:

a) Los médicos son ricos.

b) Las matemáticas son divertidas.

c) La computación es más interesante que la matemática.

Donde el valor de verdad depende de preferencias o percepciones subjetivas. Ası́ mis-

mo, nótese que hay proposiciones cuyo valor de verdad depende del contexto en la que

son expresadas. En términos estrictos, una sentencia como “hoy es lunes” puede no con-

siderarse como una proposición dado que “hoy” es variable. Lo mismo puede ser dicho

Á (384-322 AC) nació en la ciudad de Estagira, no lejos del actual monte Athos, en la Calc ı́dicaentonces perteneciente al reino de Macedonia. Su padre, Nicómaco, fue el médico personal del rey Amyntas III

de Macedonia, por lo que Aristóteles fue entrenado y educado como miembro de la aristocracia.

Alrededor de los dieciocho años, viajó a Atenas para continuar su educación en la Academia de Platón,

donde continuó por cerca de veinte años hasta la muerte de su mentor en 347 AC. Luego viajó a la corte del

rey Hermias de Atarneos, en Asia Menor, junto a su condisc ı́pulo Xenócrates, desposándose de Pythias, la hija

(o sobrina) de Hermias. Poco después de la muerte del rey, Aristó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 educó a sus alumnos en amplios temas por los

próximos doce años. Durante este perı́odo murió su esposa Pythias, por lo que se involucró con Herpyllis de

Estagira. De acuerdo a la Suda, también tuvo un erómeno llamado Palaephatus de Abidos.

Es durante este perı́odo en Atenas que se cree que Aristóteles compuso muchos de sus trabajos. Escri-

bió muchos diálogos, de los cuales sólo fragmentos han sobrevivido. Los trabajos que sobreviven se encuentran

en forma de tratados y, en su mayorı́a, no estaban pensados para amplia publicación, ya que se piensa que

serı́an textos de apoyo para sus estudiantes. Se cree que s ólo cerca de un tercio de sus trabajos originales han

sobrevivido.

Aristóteles (junto con Sócrates y Platón) es una de las figuras fundadoras más importantes de la filosof ́ıa

occidental. Fue el primero en crear un sistema filosófico completo, abarcando moral y estética, lógica y ciencia,

polı́tica y metafı́sica. Los puntos de vista de Aristóteles sobre las ciencias fı́sicas dieron forma a las enseñanzas

medievales, y su influencia se extendió hasta el Renacimiento, cuando fueron finalmente reemplazadas por la

fı́sica moderna. En las ciencias biológicas, algunas de sus observaciones fueron confirmadas hasta finales del

siglo XIX. Sus trabajos contienen el estudio formal más antiguo conocido sobre la lógica, lo que fue incorporado

a finales del siglo XIX en la lógica formal moderna. En metaf ́ısica, Aristóteles tuvo una influencia profunda

en el pensamiento filosófico y teológico de las tradiciones Islámicas y Judı́as en la Edad Media, y continúa

influenciando la teologı́a Cristiana, especialmente la teologı́a ortodoxa oriental, y la tradición escolástica de la

iglesia Católica Romana.

Luego de la muerte de Alejandro, se encendió nuevamente un ambiente anti-macedónico en Atenas.

Eurimedón denunció a Aristóteles de no rendir honor a los dioses, por lo que Aristóteles huyó de la ciudad a las

propiedades de la familia de su madre en Calcis explicando: “No dejaré que los Atenienses cometan otro pecado

contra la filosofı́a”, refiriéndose al juicio y ejecución de Sócrates en Atenas. Sin embargo, murió a menos de un

año de haber llegado a Eubea de causas naturales. Dejó un testamento en el cual pedı́a ser enterrado junto a su

esposa.

3


7/171

1.2 C Ĺ E Ḿ

de “está lloviendo”. Sin embargo, en la prá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 serán

consideradas como proposiciones.

1.2 Conectivos Ló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

más proposiciones unidas por uno o más conectivos l´ ogicos, siendo “y”, “o”, “no”, “im-

plica” y “equivale” las más comunes de ellas. Por ejemplo, podemos combinar tres propo-

siciones:

Si los humanos son mortales y todos los salvadoreños son humanos, entonces todos lossalvadoreños son mortales.

En la discusión siguiente, no nos preocupará mucho el significado de las proposicio-

nes simples -ya sea que hablen de matemática o de la mortalidad de los salvadoreños- pero

sı́ de cómo las proposiciones son combinadas y relacionadas. Es por esto que usualmente

se utilizarán variables como p o q en lugar de proposiciones especı́ficas como “Todos los

humanos son mortales” y “2+3=5”. Se entenderá que estas variables, como las proposi-

ciones, pueden tomar uno de dos valores: verdadero o falso.

1.2.1. Conjunción, Disyunción y Negación

Primero analizamos el uso del conectivo y, que expresa que dos eventos son ciertos

simultáneamente. Es decir, si p y q son dos proposiciones, la proposición compuesta “ p y

q”, simbolizada por p ∧ q y llamada conjunci´ on, será verdadera solamente en el caso enque ambas proposiciones lo sean.

Los siguientes ejemplos muestran el uso de la conjunción.

EJEMPLO 1.3

La proposición “Son las 4 PM y está lloviendo” está compuesta por las proposiciones

p =“Son las 4 PM” y q =“Está lloviendo” unidas por el conectivo “ y” para indicar que

ambos se cumplen al mismo tiempo. Se simboliza como p ∧ q.

EJEMPLO 1.4

La proposició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”. Simbólicamente, podemos representar a

s como π > 3 y a t como π < 3.2, por lo que la proposición compuesta puede ser escrita

como

(π > 3) ∧ (π


8/171

U E S 1. Ć P

Una observación importante es que en el lenguaje matemático, una conjunció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 proposició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 proposición, no es posible utilizar

el sı́mbolo ∧ para representar la palabra “ y” ya que no está siendo usada para unir dos

proposiciones.El siguiente conectivo lógico que analizaremos es la palabra “o”, que, a diferencia

del “y”, sı́ introduce ambigüedad en el lenguaje comú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 proposició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 proposición “La clase de mañana a las 10 será en el aula 1 o en el aula 3”, está for-mada por las proposiciones “La clase de mañana a las 10 será en el aula 1” y “La clase

de mañana a las 10 serán en el aula 3”.

b) La proposición “3 es un entero par ó 7 un primo” se representa con p ∨ q, donde p =“3 es un entero par”, q = “7 es un número primo”.

c) La proposicion “Esta noche comeré pollo o vegetales” está compuesta por las proposi-

ciones r=“Esta noche comeré pollo” y s=“Esta noche comeré vegetales”.

Note que la definición de disyunción nos dice que la proposición compuesta disyuntiva

será falsa únicamente cuando ambas proposiciones son falsas. Esto introduce una diferen-

cia importante con el lenguaje cotidiano, donde la proposició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 proposición (c) tanto

r como s pueden ser ciertas simultáneamente. Este significado inclusivo de la palabra o es

el que utilizaremos de aquı́ en adelante.

La siguiente definición surge de la necesidad de negar sentencias, expresando que una

proposición es falsa. Dada una proposición p cualquiera, la proposición compuesta “no

p”, simbolizada por ¬ p, es verdadera si p es falsa, y es falsa si p es verdadera.

5


9/171

1.2 C Ĺ E Ḿ

Como se muestra en los siguientes ejemplos, los tres conectivos lógicos presentados

hasta ahora nos permiten analizar la forma lógica de proposiciones complejas.

EJEMPLO 1.6

Analice la forma lógica de “José se irá de casa y no volverá”.Soluci´ on. Sea p la proposición “José se irá de casa” y q la proposición “José no volverá”,

entonces podemos representar esta expresión simbólicamente como p ∧ q. Sin embargo,este análisis no considera que q es en realidad una expresión negativa. Podrı́amos obtener

un mejor resultado si consideramos a r como “José volverá” y reescribimos a q como ¬r .Reemplazando a q en nuestro análisis original tenemos p ∧ ¬r .

EJEMPLO 1.7

Analice la forma lógica de “O Elisa entró a clases y Gabriela no, o Gabriela entró a clases

y Elisa no”.

Soluci´ on. Sea e la proposición “Elisa entró a clases” y sea g la proposición “Gabrielaentró a clases”. La primera parte de la proposición, es decir “O Elisa entró a clases y

Gabriela no”, puede ser escrita como e ∧ ¬g. Similarmente, la segunda mitad puede serrepresentada por g ∧ ¬e. Para representar toda la proposición, utilizamos la disyunciónpara combinar estas dos partes para formar (e ∧ ¬g) ∨ (g ∧ ¬e).

Note que al analizar la proposición compuesta del ejemplo anterior, agregamos parénte-

sis cuando formamos la disjunción de e ∧ ¬g y g ∧ ¬e para indicar sin ambigüedadesqué proposiciones estaban siendo combinadas. Esto es similar al uso de paréntesis en álge-

bra, en donde, por ejemplo, el producto de a+b y a−b serı́a escrito como (a+b)·(a−b), conlos paréntesis indicando qué cantidades están siendo multiplicadas. Como en el álgebra, en

lógica es conveniente omitir algunos paréntesis para hacer más cortas y más legibles nues-tras expresiones. Sin embargo, es necesario establecer las reglas para leer dichas expresio-

nes sin que esto introduzca ambigüedades. Una primera convención que adoptaremos es

que la negación (¬) se aplica únicamente a la proposición que viene inmediatamente des-pués de ella. Por ejemplo, ¬ p ∧ q significa (¬ p) ∧ q en lugar de ¬( p ∧ q). En el transcursodel libro, se presentarán más convenciones sobre los paréntesis.

También es importante tomar en cuenta que los sı́mbolos ∧ y ∨ únicamente pueden serusados entre dos proposiciones para formar su conjunción o disyunción, y el sı́mbolo ¬sólo puede ser usado antes de una proposici´ on para negarlo. Esto quiere decir que ciertas

cadenas de sı́mbolos y variables no son válidas, como p¬ ∧ q, p ∨ ∧q, y p¬q. Una vezmás, puede ser útil pensar en una analogı́a con el álgebra, donde los sı́mbolos +,

−, ×

y

÷ pueden ser usados entre dos números, como operadores, y el sı́mbolo − puede tambiénser usado antes de un número para negarlo. Estas son las únicas formas en los que estos

sı́mbolos pueden ser usados en á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 predicción del tiempo “vientoy lluvia son las únicas posibilidades para el clima de mañana”. Esta es simplemente otra

manera de decir que o hará viento o lloverá mañana, por lo que, aún cuando se utilizó la

6


10/171

U E S 1. Ć P

palabra “ y” en la proposición, ésta es en realidad una disyunción. El mensaje de estos

ejemplos es que para determinar la forma ló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 proposición “tengo hambre pero tengo que ir a clase”. En este caso,

la palabra pero es utilizada para representar a la conjunción.

Finalmente, algunas veces hay conectivos ocultos en la notación matemática. Por ejem-

plo, considere la proposición 3 ≤ π. Aunque a primera vista parezca una proposición sinconectivos lógicos, al leerla en voz alta se escuchará la palabra o. Si representamos a 3 < π

como p y a 3 = π como q, entonces la proposición 3 ≤ π puede ser escrita como p ∨ q.Como un ejemplo ligeramente más complicado, considere la proposición 3 ≤ π


11/171

1.2 C Ĺ E Ḿ

1.2.2. Condicional

La cuarta noción que investigaremos es una de las que causa la mayor confusión ini-

cial: implicaci´ on. En matemáticas frecuentemente utilizamos expresiones de la forma “ p

implica q”, simbolizada “ p → q”. De hecho, la implicació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 proposición de la forma p → q, si pes verdadera, entonces q debe ser también verdadera.

Pero suponga que p es la proposición verdadera “√

2 es irracional” y q es “0 < 1”.

¿Será verdadera p → q en este caso? En otras palabras, ¿será cierto que la irracionalidadde

√ 2 implica que 0 es menor que 1? Desde luego que no. No existe conexión real entre

las proposiciones p y q.

Más dramáticamente, considere la implicación

“Que el emperador Julio César esté vivo implica que 1 + 1 = 2”.

En este caso, ¿Qué 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 implicación no sólo

tiene que ver con el valor de verdad de la proposición (como es el caso de la conjunción,

disyunción y negación), sino también con causalidad . Cuando escribimos “ p implica q”,

queremos decir que de alguna manera q es causada o provocada por p. Para los propósitos

de este capı́tulo, no consideraremos el complejo problema de la causalidad y utilizaremos

únicamente el valor de verdad de las implicaciones. A cualquier expresión de la forma p →q se le llamará 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 condicionalserá definido completamente por la verdad o falsedad del antecedente y del consecuente, y

no se considerará en absoluto si existe o no una conexión significativa entre p y q.

Como se esperarı́a, esta definición que ignora un aspecto altamente significativo de

la noción de la implicación puede tener consecuencias que son contraintuitivas e incluso

absurdas. Sin embargo, en todos los casos donde sı́ existe una implicación genuina y sig-

nificativa de la forma “ p implica q”, el condicional p → q concuerda con esa implicación.Dicho de otra manera, al definir el condicional de esta forma, no tenemos caso alguno

en que se contradiga la noción de la implicación genuina. En lugar de ello, obtenemos

una noción que extiende a la implicación genuina para cubrir los casos donde se tiene una

implicación sin sentido, como en los casos donde el antecedente es falso o donde no hay

conexión real entre el antecedente y el consecuente.

Ahora que ignoramos toda causalidad, el valor de verdad de una implicación es intui-

tivo cuando el antecedente es verdadero. Si p es verdadero y “ p implica q” es una proposi-

ción válida, entonces q debe ser verdadera. Es decir, el condicional p → q será verdaderocuando tanto el antecedente como el consecuente sean verdaderos.

Para manejar el caso en el que el antecedente es falso, no consideraremos la noción de

implicación sino más bien la de su negación. Extraeremos la parte del valor de verdad y sin

causalidad de la proposición “ p no implica q”, que escribiremos como p q, y dejaremos

8


12/171

U E S 1. Ć P

de lado cualquier tipo de relació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 negación. De aquı́ que p → q será verdadera exactamente cuando p q sea falsa, llevando a los siguientes casos donde la expresió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 expresión condicional es falsa únicamente cuan-

do el antecedente es verdadero pero el consecuente es falso.

Para explorar aún más el condicional, considere la siguiente proposición:

“Si la conjetura de Goldbach es verdadera, entonces x2 ≥ 0 para todo número real x”

Como mencionamos anteriormente, no se ha podido determinar aún si la conjetura de

5Formalmente escribimos esto como p ∧ ¬q, lo que sugiere que esta expresión y ¬( p → q) significan lomismo (son equivalentes).

A D M (1806-1871) fue el quinto hijo de John De Morgan, un Teniente-Coronel inglésestacionado en India al momento del nacimiento de Augustus. De Morgan perdió su vista en el ojo derecho

poco después de su nacimiento y, a los siete meses de edad, regresó a Inglaterra con su familia. John De Morganmurió cuando Augustus tenı́a 10 años.

De Morgan no sobresalió en la escuela y, debido a su condición f ́ısica, no jugaba deportes e incluso fue

vı́ctima de crueles bromas por parte de sus compañeros.

Ingresó al Trinity College de Cambridge en 1823 a los 16 años, donde fue alumno de Peacock y Whe-

well, con quienes entabló amistad de por vida. Recibió su licenciatura pero, dado que un exámen teoló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 Maestŕıa.

En 1826 regresó a su hogar en Londres e ingresó al Licoln’s Inn a estudiar para los exámenes de abogacı́a.

En 1827 (a los 21 años), aplicó a la dirección de matemática en el nuevo University College London y, a pesar

de no tener publicaciones matemáticas, fue contratado. Por cuestión de principios, renunció a su posición en

1831, siendo contratado nuevamente 1836.

Además de sus famosas leyes y de ser recordado como el reformador de la l ógica matemática, De Morgan

también contribuyó a otras áreas de la matemática. En 1838, en su artı́culo Induction (Mathematics) de la Penny

Cyclopedia, definió e intodujo el término inducci´ on matem´ atica (ver secció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 años, renunció por segunda vez a su puesto en University College por cuestión de

principios, por lo que sus pupilos le aseguraron una pension de £500. Ese mismo año fue co-fundador y primer

presidente de la Sociedad Londinense de Matemática. Sin embargo, dos años más tarde, muere su hijo George,

un hábil matemático por sı́ mismo, seguido por otra de sus hijas. Cinco años después de su renuncia, De Morgan

muere el 18 de marzo de 1871.

De Morgan siempre se interesó por hechos numéricos raros, escribiendo en 1864 que habı́a tenido la

distinción de tener x años en el año x2.

9


13/171

1.2 C Ĺ E Ḿ

Goldbach es cierta o falsa. Sin embargo, eso no evita que podamos determinar el valor de

verdad de la proposición compuesta. Esta proposición tiene la forma p → q, donde p=“Laconjetura de Goldbach es verdadera” y q=“ x2 ≥ 0 para todo nú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 proposición compuesta es verdadera.

La siguiente proposición demuestra el lado contraintuitivo de las implicaciones:

“Si los cerdos vuelan, entonces puedes entender la teoŕıa de la relatividad”

Curiosamente, el valor de verdad de esta proposición no tiene relación alguna con el

hecho de que se pueda o no entender la teoŕı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

proposición es verdadera.

En contraste, considere la siguiente proposición:

“Si la luna parece blanca, entonces la luna está hecha de queso blanco”

Sı́, la luna parece blanca, pero no, no está hecha de queso blanco. Ya que la combina-

ción de estos valores de verdad no se encuentra en ninguno de los casos de la veracidad

del condicional, la proposición debe ser falsa.

Estos ejemplos muestran que la definició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 observación anterior sugiere que p → q y ¬ p ∨ q significanlo mismo.

Además de los valores de verdad que hemos visto hasta ahora, el condicional (y m ás

generalmente, la implicación) posee terminologı́a asociada a la que el lector debe acos-

tumbrarse. Una proposició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 só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 atenció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 distinción entre si y

s´ olo si.

10


14/171

U E S 1. Ć P

De la misma manera, el uso de la palabra necesario en (7) usualmente causa confusión.

Note que decir que q es una condición necesaria para p no significa que q por sı́ sola es

suficiente para garantizar p. Má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 expresión condicional p → q puede asociársele la proposición ¬q → ¬ p, llamadala contrapositiva o contrarecı́proca de p → q. Note que en la contrapositiva, la intro-ducción del signo de negación es acompañada de un cambio en la dirección de la flecha.

Por ejemplo, la contrapositiva de la expresión “si está lloviendo, entonces hay nubes en el

cielo” es “si no hay nubes en el cielo, no está lloviendo”. De la misma manera, la contra-

positiva de la proposició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”.

Más adelante veremos que una expresión condicional y su contrapositiva son ló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-nexión entre los valores de verdad de un condicional y su conversa. Esto es ilustrado con

la conversa de la expresión “si está lloviendo, entonces hay nubes en el cielo”, la cual es

“si hay nubes en el cielo, entonces está lloviendo”.

1.2.3. Bicondicional

Cercanamente ligada a la implicación es la noció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 sección anterior la implicación fue desprovista de causalidad, el estudio de equivalen-

cia será igualmente desprovista de causalidad en esta sección y estudiaremos únicamente la

parte concerniente al valor de verdad de la equivalencia: el bicondicional. Dadas dos pro-

posiciones p y q, la proposición bicondicional “ p si y sólo si q”, simbolizada por p ↔ q,es definida como ( p → q) ∧ (q → p).

De esta definición y como se verá más claramente podemos ver que el bicondicional

será 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 implicación), el bicondicional (y la equivalen-

cia) posee terminologı́a asociada con la que es necesario familiarizarse. Una proposició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 só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


15/171

1.2 C Ĺ E Ḿ

ejemplo, probablemente no se dirı́a algo como “la clase se impartirá si hay al menos diez

personas en el salón” a menos que también sea el caso que si hubiera al menos de diez

personas en el salón, la clase se impartirı́a. Por lo tanto, la proposición sugiere que la clase

será impartida si y sólo si hay al menos diez personas en el salón. Como otro ejemplo,

suponga que los padres le dicen a un niño, “Si no te comes todo, no tendrás postre”. El niño

ciertamente espera que si termina su comida tendrá su postre, aunque no sea literalmente lo

que sus padres dijeron. En otras palabras, el niño interpreta el significado de la proposición

como “que termines tu comida es una condición necesaria y suficiente para obtener postre”.

Tal confunsión entre “si” y “si y s´ olo si” nunca es aceptable en matemáticas. En el resto

del libro (y en el lenguaje matemático) se utilizarán siempre expresiones como “es nece-

sario y suficiente” o “si y sólo si” para expresar el bicondicional. No deberá interpretar

una proposición de la forma “si-entonces” como una proposición bicondicional.

Ejercicios.......................................................................................................

1. Exprese las siguientes proposiciones com-

puestas en forma simbólica:

a) No irás a jugar fútbol, o irás y nadie es-

tará ahi.

b) O Juan y Beto están ambos diciendo la

verdad, o ninguno la está diciendo.

c) Comeré pescado o pollo, pero no co-

meré pescado y puré 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 común de 6, 9 y 15.

f) Alicia y Carlos no están ambos en el cuar-

to.

g) Alicia y Carlos están ambos fuera del

cuarto.

h) O Alicia o Carlos no están en el cuarto.

i) Ni Alicia ni Carlos están en el cuarto.

2. ¿Cuáles de las siguientes expresiones lógicas

no son válidas?

a) ¬(¬ p ∨ ¬¬r )b) ¬( p, q, ∧r )c) p ∧ ¬ pd) ( p ∧ q)( p ∨ r )

3. Si p representa a la proposición “com-

praré los pantalones” y s a la proposición

“compraré la camisa”. ¿Qué oraciones en Es-

pañol son representadas por las siguientes ex-

presiones lógicas?

a) ¬ p ∧ ¬sb)

¬ p

∨ ¬s

c) ¬( p ∧ ¬s)4. Si a representa a la proposición “Alfonso

está feliz” y g representa a “Gabriel está fe-

liz”. ¿Qué oraciones en Español son represen-

tadas por las siguientes expresiones lógicas?

a) (a ∨ g) ∧ (¬a ∨ ¬g)b) [a ∨ (g ∧ ¬a)] ∨ ¬gc) a ∨ [g ∧ (¬a ∨ ¬g)]

5. Sean p, q, r las proposiciones: p = “Está llo-

viendo”, q = “El sol está brillando”, r = “Hay

nubes en el cielo”. Traduzca las siguientes

frases a notación lógica usando p, q, r y los

conectivos lógicos:

a) Está lloviendo y el sol está brillando

b) Si está lloviendo, entonces el sol no

está brillando

12


16/171

U E S 1. Ć P

c) Si no está lloviendo, entonces el sol no

está brillando y no hay nubes en el cielo

d) El sol está brillando si y sólo si no está llo-

viendo

e) Si no hay nubes en el cielo, entonces el

sol está 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 función f es

suficiente para que f sea contı́nua.

c) Una funció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 só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


17/171

1.3 T V E Ḿ

verdad de:

a) p ∧ q b) p ∨ q c) q → pObservació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 lógicos ∧, ∨, ¬, → y ↔ únicamente en té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 proposición cualquiera, entonces la veracidad de la proposició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 proposición p es falsa, la proposició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 proposición para

todas las posibles combinaciones de los valores de las proposiciones simples. Por ejemplo,

la tabla de verdad para la proposició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 ú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 pág. 15) que popularizó su uso. Sin embargo, Lewis Carroll (ver pá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


18/171

U E S 1. Ć P

Es posible construir tablas de verdad para expresiones má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 ú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 expresión

de tal manera que cada fila tenga una combinació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 filósofo Austrı́aco que trabajó principalmente enlos fundamentos de la lógica, la filosof ́ıa de la matemática, la filosof ́ıa de la mente, y la filosof ́ıa del lenguaje.

Nació en Viena el 26 de abril de 1889, siendo el m ás joven de ocho hijos nacidos en una de las más prominentes

y adineradas familias del imperio Austro-Húngaro. Su familia era visitada por mú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 devoción a la música que siguió siendo importante por el resto de su vida.

Ludwig fue educado en casa hasta 1903, cuando inició tres años de estudio en la Realschule de Linz,

donde Adolfo Hitler fue estudiante al mismo tiempo. Wittgenstein hablaba Alemán altamente puro y educado,

aunque ocasionalmente tartamudeaba, vestı́a ropas elegantes, y era increı́blemente sensitivo y antisocial. Se

referı́a a sus compañeros formalmente, demandando que hicieran lo mismo con él. Odió la escuela y mantuvo

únicamente calificaciones promedio.

En 1906, inició sus estudios de ingenierı́a mecánica en Berlin, y en 1908, comenzó 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 investigación despertó un interés que lo llevó a visitar a Frege (ver

biografı́a la pag. 43), quien le aconsejó que ingresara a la Universidad de Cambridge como alumno de Russell.

Éste luego escribió que ser profesor de Wittgenstein fue “. . . una de las aventuras intelectuales más interesantes

[de su vida].. . [Wittgenstein tenı́a] pureza intelectual a un grado extraordinario. . . [El] pronto sabı́a todo lo que

podı́a enseñarle.” Ambos pronto comenzaron a trabajar en los fundamentos de la lógica y en lógica matemática.

Sin embargo, durante su perı́do en Cambridge Ludwig sufrió depresión y amenazó con suicidarse en repetidas

ocasiones. En 1913, partió hacia una remota población en Noruega ya que pensaba que no podrı́a llegar al

corazón de sus preguntas más fundamentales mientras estuviese rodeado de académicos. Durante este perı́odo,

que luego consideró como uno de los más apasionados y productivos de su vida, escribió Logik , libro predecesor

de su Tractatus Logico-Philosophicus que serı́a su trabajo más famoso.

Durante la Primera Guerra Mundial, se unió voluntariamente al ejército Austro-Húngaro, ganando meda-

llas por valentı́a y cayendo como prisionero de guerra en noviembre de 1918. Durante su cautiverio, refinó su

trabajo en el Tractatus, para el cual Russell escribió su introducción. Después de un perı́odo de cerca de 7 años

desde 1922 en los que trabajó como profesor de escuela primaria, asistente de jardinero en un monasterio y

ayudante de arquitecto, Ludwig regresó a Cambridge en 1929 donde descubrió con horror que era uno de los

filósofos más famosos del mundo. Sin embargo, antes de optar a una posición en Cambridge debió completar

su doctorado, para lo que presentó al Tractatus como tesis, con Russell y G. Moore como sus jueces. Al final de

su presentación, Ludwig se dirigió a ellos dándoles una palmada en la espalda y diciéndoles: “no se preocupen,

sé que nunca lo entenderán”.

Wittgenstein renunció a su puesto en Cambridge en 1947 para concentrarse en sus escritos. Muri ó de

cáncer de próstata en Cambridge en 1951. Sus últimas palabras fueron: “Dı́ganles que tuve una vida maravillo-

sa”.

15


19/171

1.3 T V E Ḿ

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 última columna utilizando las

reglas para los valores de verdad de

∧.

Los siguientes dos ejemplos muestran más construcciones de tablas de verdad:

EJEMPLO 1.8

Elaborar la tabla de verdad para la proposició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 ás

compacta. En lugar de utilizar columnas separadas para listar los valores de verdad de

las partes componentes de la expresió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 expresió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 expresió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


20/171

U E S 1. Ć 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 expresió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 expresión contiene n variables, la tabla de verdadresultante deberá tener 2n filas (¿Por qué?).

Dado que nuestra definición de equivalencia depende únicamente del valor de verdad

de la expresión, dos proposiciones serán equivalentes si tienen la misma tabla de verdad.

Por ejemplo, podemos demostrar que p → q es ló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 proposició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 clásica p → p:Soluci´ on

p p → p0 1

1 1

7La definición de equivalencia l ´ ogica se estudiará más detalladamente en la sección 1.5.

17


21/171

1.4 Tı́ C E Ḿ

EJEMPLO 1.11

Muestre que la proposició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 proposició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 contradicción clásica p ∧ ¬ p.Soluci´ on

p ∧ ¬ p0 0 1

1 0 0

Pasos 1 3 2

Observe que una proposición compuesta P es una contradicción si y sólo si ¬P es unatautologı́a. Es decir, la negación de una tautologı́a es una contradicción y viceversa.

18


22/171

U E S 1. Ć 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ı́aObservación: Basta una lı́nea de la tabla de

verdad para mostrar que una proposición no

es una tautologı́a.4. Encuentre una proposició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 proposición compuesta que

sea verdadera cuando exactamente una de

las proposiciones p, q y r sea verdadera.

b) Escriba una proposición compuesta que

sea verdadera cuando exactamente dos de

las tres proposiciones p, q y r sean verda-

deras.

1.5 Equivalencias Lógicas.......................................................................................................

Hasta ahora hemos tomado cinco palabras comunes, y, o, no, implica y equivalente,

y les hemos dado un significado preciso en el lenguaje común. Obtuvimos la precisión

deseada al basar nuestras definiciones únicamente en el valor de verdad de las proposi-

ciones, sin tomar en cuenta cualquier relació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 común de esas palabras fuera de las matemáticas. En el caso de las últimas dos,

implica y equivale, definimos contrapartes precisas y formales llamadas condiconal y bi-

condicional, respectivamente, que tienen algunas propiedades comunes con el significado

común de implica y equivale pero es diferente en otras maneras. Es especialmente esta

última la que tendrá nuestra atención en esta sección.

Como se observó en la secció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


23/171

1.5 E Ĺ E Ḿ

# Equivalencia Lógica Nombre

1 ¬¬ p ⇔ p Doble negació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 dominación

b) ( p ∧ c) ⇔ c8 a) ( p ∨ ¬ p) ⇔ t Leyes de negació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) Implicació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 lógicas. En esta tabla una contradicció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 lógicamente equivalente a q”.En nuestra discusión de los conectivos ló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 ú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 álgebra. Como en el álgebra, estas reglas pueden ser aplicadas aexpresiones más complejas, y pueden ser combinadas para simplificar equivalencias más

20


24/171

U E S 1. Ć P

complicadas. Cualquiera de las letras en estas equivalencias pueden ser reemplazadas por

expresiones complicadas y la equivalencia resultante seguirá siendo verdadera. Por ejem-

plo, reemplazando p en la ley de doble negación con la fórmula q ∨ ¬r es posible ver que

¬¬(q

∨ ¬r ) es equivalente a q

∨ ¬r . Esta observación es importante dado que las equiva-

lencias listadas muestran la forma de las mismas, por lo que más que memorizarlas, es ú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 álgebra la multiplicació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 dominación nos muestran el comportamiento de las propo-

siciones cuando son combinadas en disyunción o conjunción con una tautologı́a o una

contradicció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 negación describen elcomportamiento de las proposiciones cuando son combinadas mediante los operadores ∧y ∨ consigo mismas y con su negación.

Note que, aunque muchas de las leyes de la tabla 1.1 tienen contrapartes en el álgebra

al que está acostumbrado el lector, no deben tomarse las leyes del álgebra para el cálculo

proposicional. Por ejemplo, cuando se tiene una expresión como −( x − y) en álgebra, esposible “meter el signo menos en el paréntesis” aplicándolo a ambos términos para obtener

− x − (− y) = − x+ y. Sin embargo, en el álgebra proposicional a una expresión como ¬(q ∧¬ p) no puede aplicársele una ley parecida a la anterior para obtener (¬ p ∧ ¬¬q), que esequivalente a (¬ p∧q). Para poder “meter la negación en el paréntesis” cuando el conectivoprincipal dentro del paréntesis es una conjunción o disyunción, es necesario utilizar la ley

de De Morgan que nos dice que, aparte de negar cada una de las proposiciones conectadas,

también debe cambiarse la disyunción por conjunción o la conjunción por disyunción.

Como muestran los siguientes ejemplos, las equivalencias de la tabla 1.1 nos permiten

simplificar expresiones lógicas o encontrar otras expresiones que, aunque con mayor o

menor complejidad, tengan el mismo significado.

EJEMPLO 1.14

Demostrar la equivalencia lógica

[( p ∨ q) ∨ ( p ∨ r )] ⇔ ( p ∨ q) ∨ r

sustituyendo sucesivamente proposiciones equivalentes.

8Note aquı́ una diferencia con las leyes distributivas del álgebra: aunque la multiplicación puede ser distri-

buida sobre la suma, la suma no puede ser distribuida sobre la multiplicación. Es decir, en general, x + y · w ( x + y) · ( x + w).

21


25/171

1.5 E Ĺ E Ḿ

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 proposición ló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 negación

Esta última proposició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) Negación⇔ (¬ p ∧ q) ∨ c Conmutativa⇔ (¬ p ∧ q) Identidad

22


26/171

U E S 1. Ć P

b) p ∨ ( p ∧ q)

p ∨ ( p ∧ q) ⇔ ( p ∧ t ) ∨ ( p ∧ q) Identidad

⇔ p

∧(t

∨q) Distributiva

⇔ p ∧ t Dominación⇔ p Identidad

c) ¬( p ∨ q) ∨ (¬ p ∧ q)

¬( p ∨ q) ∨ (¬ p ∧ q) ⇔ (¬ p ∧ ¬q) ∨ (¬ p ∧ q) De Morgan⇔ ¬ p ∧ (¬q ∨ q) Distributiva

⇔ ¬ p

∧t Negación

⇔ ¬ p Identidad

Como se mostró en la sección anterior, todos los resultados de los ejemplos anteriores

pueden ser comprobados a través de tablas de verdad, asegurándonos que las columnas de

las expresiones dadas tengan los mismos valores de verdad para los mismos valores de las

variables lógicas.

Ejercicios.......................................................................................................

1. Verifique las siguientes equivalencias lógicas

(tabla 1.1) utilizando tablas de verdad:

a) Las leyes distributivas

b) Las leyes de identidad

c) La contrarrećıproca

d) La regla 9-c y 9-d

2. Demuestre utilizando equivalencias ló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 ló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


27/171

1.5 E Ĺ E Ḿ

e) ¬(¬ p ↔ q)f) ¬(¬ p → ¬q)

5. Dadas dos proposiciones p y q, el conectivo

“ó excluible”, simbolizado por p

⊕q, es ver-

dadero cuando únicamente p es verdadera ocuando ú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 proposición compuesta se puede escri-

bir utilizando ú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 ló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 lógico, matemático, filó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 matemática en la

Universidad de Harvard. A los 12 años, Charles leyó una copia del libro Elementos de L ´ ogica, para ese entonces

el libro de texto lı́der en la materia, lo que comenzó su fascinación con la ló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 empleó intermitentemente en el Servicio Costero Estadounidense, don-

de trabajó principalmente en geodesia y gravimetrı́a, refinando el uso de péndulos para determinar pequeñas

variaciones locales en la fuerza de gravedad terrestre. Este trabajo lo libró de tomar parte de la guerra civil

estadounidense. De 1869 a 1872, trabajó como asistente en el observatorio astronómico de Harvard, realizando

importantes avances en la determinación de la brillantez de las estrellas y la forma de la Vı́a Láctea. En 1878,

fue el primero en definir el metro en t érminos de la longitud de onda de la luz a cierta frecuencia, definició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 ógica en la Universidad John Hopkins, el cual fue

el único puesto académico que ocupó durante su vida. En los últimos años de su vida, Peirce vivió con du-

ras limitaciones económicas debido al desempleo, viviendo principalmente de consultoŕıas mal pagadas y de

donaciones de amigos, especialmente de William James, quien desde 1898 hasta 1910 escribi ó a sus amigos

académicos, pidiéndoles hacer contribuciones económicas para mantener a Peirce.

Peirce realizó una serie de admirables descubrimientos en matemáticas, que casi en su totalidad fueron

apreciados únicamente después de su muerte. Entre otros aportes, mostró que lo que ahora llamamos ´ Algebra

Booleana podı́a ser expresada por medio de una sola operación binaria, anticipándose por 33 años a Sheff er.

Además, se anticipó por más de 50 años a la observación que cálculos booleanos pueden ser realizados con

dispositivos eléctricos, idea que se utilizó años más tarde para producir computadoras digitales. Sentó las bases

para la teorı́a axiomática de conjuntos, anticipándose a Zermelo por casi dos décadas. Descubrió la axiomati-

zación de la aritmética de los números naturales unos cuantos años antes que Dedekind y Peano. Descubrió,

independientemente de Dedekind, la importante definición formal de un conjunto infinito.

Aunque descrito por Bertrand Russell como “sin lugar a dudas [. . . ] fue una de las mentes más originales

de finales de siglo diecinueve, y ciertamente el más grande pensador Estadounidense de todos los tiempos”,

Peirce fue en gran parte ignorado durante su vida, y la literatura acerca de él fue escasa hasta después de la

Segunda Guerra Mundial. Después de su muerte se descubrieron cerca de 1650 manuscritos, totalizando cerca

de 100,000 páginas, muchos de los cuales siguen sin publicarse hasta este dı́a.

24


28/171

U E S 1. Ć P

p q p | q0 0 1

0 1 1

1 0 1

1 1 0

Todas las proposiciones compuestas pueden

escribirse utilizando únicamente este conec-

tivo.

a) Muestre que ¬ p ⇔ p | pb) Muestre que p ∨ q ⇔ ( p | p) | (q | q)c) Encuentre una proposición equivalente a

p ∧ q utilizando únicamente la raya deSheff er.

d) Haga lo mismo para p → qe) Haga lo mismo para p ⊕ q

10. Algunos matemáticos utilizan el sı́mbolo ↓como la negación de la disyunció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 sólo los

conectivos ∧, ∨ y ¬ que sea equivalentea p ↓ q. Verifique su respuesta utilizandotablas de verdad.

c) Encuentre fórmulas usando el conectivo ↓que sean equivalentes a ¬ p, p ∨ q y p ∧ q.

1.6 Validez Lógica de Argumentos.......................................................................................................

Una aplicación interesante y útil del cálculo proposicional es el análisis de ciertos

tipos de argumentos para verificar su validez lógica. Un argumento consiste de una serie

de proposiciones “dadas”, cuya conjunció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 laconclusión q es un argumento v´ alido si y sólo si la proposición p1 ∧ p2 ∧ p3 ∧ . . . ∧ pn →q es una tautologı́a. El requisito para la validez de un argumento es, por lo tanto, que

la conclusión sea verdadera en todos los casos en que todas las premisas parciales sean

verdaderas.

El siguiente ejemplo muestra el formato estándar en que las premisas y la conclusió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 conclusió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 lógicamente válido.

25


29/171

1.6 V Ĺ A E Ḿ

EJEMPLO 1.18

Exprese simbólicamente y analice la validez del argumento “Si las tasas de interé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 condición suficiente

para que las autoridades actuales sean reelectas es que la tasa de interés baje”.

Soluci´ on. Primero simbolizamos cada proposició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 . Laconclusión tiene la forma p → s. Por lo tanto, el argumento en forma simbólica es:

p → qq → r s → r

∴ p → sEl lector deberá verificar construyendo una tabla de verdad, que el argumento no es

lógicamente válido.

Las tautologı́as [ p ∧ ( p → q)] → q (modus ponens), [( p → q) ∧ (q → r )] → ( p → r )(transitividad de la implicació n ) y [ p → (q → r )] ↔ [( p∧q) → r ], proveen un mé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 hipótesis de la forma ( p

→ q) y (q

→ r ) por la hipótesis ( p

→ r ),

si hacerlo resulta ventajoso. La tercera implicación nos dice que si nuestra conclusió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 equivalencialógica: una proposición puede ser reemplazada por cualquier proposició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 vá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 análisis muestra que r puede ser

deducido lógicamente a partir de la premisa, por lo que el argumento es válido.

26


30/171

U E S 1. Ć 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 hipótesis p → q, q → r y s

→ r . Primero, agregamos p a la lista de hipó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 razón para dudar dela validez del argumento. Para demostrar la invalidez, debemos proveer una combinación

de valores de verdad para la cual la implicación en cuestión es falsa. Esto tambié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 conjunción ( p → q) ∧ (q → r ) ∧ (s → r ) de las premisas parcialessea verdadera mientras que la conclusió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 tambié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 combinación de valores de verdadpara las cuales la premisa del argumento es verdadera mientras que la conclusión es falsa.

Esto prueba concluyentemente la invalidez del argumento.

Los ejercicios de esta sección pueden realizarse tanto utilizando tablas de verdad co-

mo el razonamiento de los ejemplos anteriores. Aún cuando el procedimiento mecánico

de construcción de tablas de verdad parezca más sencillo de realizar, es más provechoso

para su formación el intentar utilizar el razonamiento lógico anterior. A continuación se

presenta un último ejemplo utilizando este razonamiento.

EJEMPLO 1.21

Determine si el siguiente argumento lógico es válido. “Si estudio o soy un genio, entonces

aprobaré el curso. Si apruebo el curso, entonces me permitirá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 = “aprobaré el curso”

a = “me permitirán tomar el curso siguiente”entonces el argumento puede ser representado simbólicamente de la siguiente manera:

s ∨ g → p p → a

∴ ¬a → ¬gYa que la conclusión es una implicación, utilizamos la táctica presentada anteriormente

de modificar el problema suponiendo que el antecedente es una de las premisas y tratando

de demostrar

27


31/171

1.6 V Ĺ A E Ḿ

1. s ∨ g → p hipótesis2. p → a hipótesis3. g → g ∨ s Regla 12 (adición)4. g

→ s

∨g Por 3 y ley conmutativa 2-a

5. g → p Por 4, 1 y silogismo hipotético (regla 33)6. g → a Por 5, 2 y silogismo hipoté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 mañana es martes.

Pero hoy no es lunes. Por lo tanto, mañana no

es martes.

3. Hoy es lunes o martes. Pero hoy no es lunes.

Por lo tanto, hoy es martes.

4. Perderé mi trabajo a menos que Sandra siga

trabajando. Sandra será despedida sólo si us-

ted lo recomienda. Por lo tanto, retendré 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 dólar sube de valor, las exportaciones

se reducen. El desempleo aumentará a menos

que se detenga la reducción en las exporta-

ciones. Una baja en las tasas de interés es ne-

cesaria para debilitar el precio del dólar. Por

lo tanto, una baja en las tasas de interés es

suficiente para causar disminución en el des-

empleo.7. Claudia pasará el examen si entiende el tema.

Si Claudia pasa el examen, entonces apro-

bará la materia. Por lo tanto, si Claudia en-

tiende el tema, entonces aprobará la materia.

8. Si estudio toda la noche para el examen de

lógica matemática, estaré cansado. Si estoy

cansado, no haré la tarea de Geometrı́a. Por

lo tanto, para pasar el examen de Lógica Ma-

temá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 encontró 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-

contró con Mercedes anoche y el asesinato

ocurrió en un hotel. Si el asesinato ocurrió en

un hotel, entonces o Mercedes fue la asesina

o Mirna estaba fuera de la ciudad. Pero Mer-

cedes se encontró con Mirna anoche y Mir-

na no estaba fuera de la ciudad. Por lo tanto,

Mercedes fue la asesina.

28


32/171

Ć 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 matemático como en el común que

no pueden ser representadas usando el cálcu-

lo proposicional. Además del factor externo de

tener que enlazar proposiciones a través de co-

nectivos lógicos, existe un factor interno en pro-

posiciones que contienen palabras como “todos”

o “algunos” que requiere un análisis lógico más

allá del posible con el cá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 válido dentro del

cálculo proposicional. Es claro que en este caso

Libro Logica Matematica UES

Documents

Transcript of Libro Logica Matematica UES