Cálculo I

1 Introducción
1.2 Lógica Proposicional

Araceli Guzmán y Guillermo Garro

Julio, 2020

Facultad de ciencias, UNAM

Referencias
Introducción: Lógica Proposicional Cálculo I

Referencias básicas
1. M. Delgado y M. J. Múñoz. Lenguaje matemático, conjuntos y números, 2010.
2. Armando O. Rojo. Álgebra I, 1978.
3. A. Bravo, H. Rincón, C. Rincón. Álgebra superior, 2006.
4. Carmen Gómez. Álgebra superior, 2014.
5. Álvaro Pérez Raposo. Lógica, conjuntos, relaciones y funciones, 2010.
6. Max Fernández de Castro y Luis Miguel Villegas. Lógica Matemática I, 2011.

Otras referencias
1. M. O’Leary. A first course in mathematical logic and set theory, 2016.
2. Willard Van Orman Quine. Mathematical Logic, 1981.
3. D. Hilbert y W. Ackerman. Principles of Mathematical Logic, 1950.
4. H.B. Enderton. A Mathematical Introduction to Logic, 2ed, 2001.
5. E. Meldenson. Introduction to Mathematical Logic, 2015.
6. E. Schechter. Classical and Nonclassical Logics, 2005.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 2

Índice
Introducción: Lógica Proposicional Cálculo I
Lógica Proposicional
Conectivos lógicos
Tabla de valores de verdad
Un juego divertido
Leyes Lógicas: Tautologı́as
Leyes Lógicas: Equivalencias
Leyes Lógicas: el bicondicional
Leyes Lógicas: negación del Bicondicional
Modus Ponens. Reglas de Inferencia
Reglas de Inferencia: Transitividad del condicional
Reglas de Inferencia: Eliminación del bicondicional
Leyes Conmutativas
Leyes Asociativas
Leyes de De Morgan
Equivalencias del condicional
Ley del Contrarecı́proco

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 3

Lógica Proposicional
Proposiciones y conectivos Cálculo I

¿Qué es la Lógica Proposicional?

La lógica proposicional es un sistema formal cuyos elementos más simples representan
proposiciones, y cuyas constantes lógicas llamadas conectivas lógicas, representan opera-
ciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.
Fuente: Wikipedia, Internet Encyclopedia of Philosophy

Proposiciones
Una proposición es un enunciado del que puede decirse que es verdadero (con valor de
verdad V ó 1) o falso (con valor de verdad F ó 0) pero no ambas cosas. Por ello se
dice que la lógica proposicional es binaria (porque solo admite dos valores de verdad).
Gereralmente las proposiciones son denotadas con las letras minúsculas p, q, r,... o bien,
para proposiciones compuestas usamos mayúsculas P , Q, R,...

Los conectivos lógicos

Los conectivos lógicos son relaciones (funciones de “verdad”) con las cuales podemos
combinar proposiciones para formar otras proposiciones:

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 4

Conectivos Lógicos
Los Conectivos usuales Cálculo I

Conectivos Lógicos (usuales)

CONECTIVO NOMBRE OPERACIÓN INTERPRETACIÓN

No p
¬ Negación ¬p No sucede p
No es cierto que p
∧ Conjunción p∧q pyq
∨ Disyunción p∨q p ó q
Y Disyunción excluyente pYq p ó q pero no ambas
p implica q
Si p entonces q
Condicional q si p
⇒ p⇒q
(o implicación) p sólo si q
p es condición suficiente para q
q es condición necesaria para p
p si, y sólo si, q
Bicondicional q es condición necesaria y suficiente para p
⇔ p⇔q
(o doble implicación) p es condición necesaria y suficiente para q
p es equivalente a q

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 5

Tablas de Valores de Verdad
Conectivos unarios y binarios Cálculo I

Tablas de Valores de Verdad

Los conectivos se definen formalmente mediante tablas de valores de verdad:

Para la negación (que es un conectivo unario):

p ¬p
V F
F V

Para el resto de los conectivos (binarios) tı́picos:

p q p∧q p∨q pYq p⇒q p⇔q

V V V V F V V
V F F V V F F
F V F V V V F
F F F F F V V

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 6

Un Juego Divertido
Proposiciones autorreferentes y otras bestias Cálculo I

Asigna un valor de verdad y responde la pregunta

1. Sean p y q las proposiciones

p : p y q son falsos.
q : q es verdadero.

¿Cuáles son los valores de verdad de p y q?

2. Sean p, q y r las proposiciones

p : q es falsa.
q : p si y sólo si r.
r : La humanidad llegó a la Luna.

¿La humanidad llegó a la luna?

3. Sean p y q las proposiciones

p : p es falsa o q es verdadera.
q : Habrá una invasión extraterrestre mañana.

¿Habrá una invasión extraterrestre mañana?

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 7
Leyes Lógicas
Proposiciones tautológicas. Lógica Formal. Cálculo I
Leyes Lógicas
Una proposición compuesta (i.e., formada mediante conectivos a partir de otras propo-
siciones, llamadas componentes) cuya tabla de valores de verdad continetiene solo el
valor V, independientemente de los valores de verdad de sus componentes, es llamada
Tautologı́a o Ley Lógica. Las leyes lógicas integran los que llamamos Lógica Formal, la
cual constituye la base de la argumentación matemática.

Ejemplo
La siguiente proposición es una tautologı́a:

p ∨ (p ⇒ q)
Prueba:

p q p⇒q p ∨ (p ⇒ q)
V V V V
V F F V
F V V V
F F V V

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 8

Leyes Lógicas
Equivalencias Cálculo I

Leyes Lógicas
Una proposición compuesta (i.e., formada mediante conectivos a partir de otras propo-
siciones, llamadas componentes) cuya tabla de valores de verdad continetiene solo el
valor V, independientemente de los valores de verdad de sus componentes, es llamada
Tautologı́a o Ley Lógica. Las leyes lógicas integran los que llamamos la Lógica Formal,
la cual constituye la base de la argumentación matemática.

Equivalencias Lógicas
En particular, si P y Q son proposiciones compuestas tales que el bicondicional

P ⇔Q

es tautologı́a, entonces decimos que P y Q son lógicamente equivalentes o para abreviar

sólo equivalentes. Una equivalencia es un caso particular de ley lógica.

Las proposiciones P y Q son equivalentes si y sólo si, tienen la misma

tabla de valores de verdad

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 9

Leyes Lógicas
El bicondicional es equivalente a dos condicionales Cálculo I
Una equivalencia esperada

El bicondicional es equivalente a dos bicondicionales. Es tautologı́a:

(p ⇔ q) ⇔ ((p ⇒ q) ∧ (q ⇒ p)) (1)

Prueba:

p q p⇒q q⇒q p⇔q (p ⇒ q) ∧ (q ⇒ p) (p ⇔ q) ⇔ ((p ⇒ q) ∧ (q ⇒ p))

V V V V V V V
V F F V F F V
F V V F F F V
F F V V V V V

La tabla confirma que (1) es siempre V, independientemente de los valores de verdad de

sus proposiciones componentes. Por lo tanto, el bicondicional (p ⇔ q) es (lógicamente)
equivalente a la conjunción de los condicionales (p ⇒ q) y (q ⇒ p), que llamaremos
condicionales componentes del bicondicional.

Probar que un bicondicional (P ⇔ Q) es V es equivalente a probar

que (P ⇒ Q) y (Q ⇒ P ) son V, conjuntamente.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 10

Leyes Lógicas
La disyunción excluyente es la negación del bicondicional Cálculo I

Negación del Bicondicional

Negar el bicondicional es equivalente a la disyunción excluyente. Es tautologı́a:

(p Y q) ⇔ ¬(p ⇔ q) (2)

Prueba:

p q (p ⇔ q) (p Y q) ¬(p ⇔ q) (p Y q) ⇔ ¬(p ⇔ q)
V V V F F V
V F F V V V
F V F V V V
F F V F F V

La tabla confirma que (2) es siempre V, independientemente de los valores de verdad

de sus proposiciones componentes.

Probar que (P ⇔ Q) es F, es probar que P y Q son excluyentes (i.e.

si P es V entonces Q es F; o bien, si Q es V, P es F.)

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 11

Modus Ponens
Reglas de Inferencia Cálculo I
Modus Ponens

Si p, y q se sigue de p, entonces q. Es tautologı́a:

(p ∧ (p ⇒ q)) ⇒ q (3)

Prueba:
p q p⇒q p ∧ (p ⇒ q) (p ∧ (p ⇒ q)) ⇒ q
V V V V V
V F F F V
F V V F V
F F V F V

La tabla confirma que (3) es tautologı́a.

Deducibilidad
Decimos que una proposición Q se deduce ó infiere de otra proposición P , si el
condicional (P ⇒ Q) es tautológico (ley lógica). En tal caso, decimos que (P ⇒ Q)
es una regla de inferencia. El Modus Ponens (ó Modus Ponendo Ponens), literal-
mente del latı́n: el modo que afirmando afirma, es una de las reglas de inferencia
más usadas en la argumentación (demostración) matemática.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 12

Reglas de Inferencia
El condicional es transitivo Cálculo I

Transitividad de ⇒

Si q se sigue de p y r se sigue de q, entonces r se sigue de p. Es tautologı́a:

((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r) (4)

Prueba:
p q r ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r)
V V V V V V V V
V V F V F F V F
V F V F F V V V
V F F F F V V F
F V V V V V V V
F V F V F F V V
F F V V V V V V
F F F V V V V V

La tabla confirma que (4) es tautologı́a.

Tradicionalmente, esta regla de inferencia es conocida como Silogismo Hipotético.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 13
Reglas de Inferencia
Eliminación del condicional Cálculo I

Eliminación del bicondicional

Es tautologı́a:
(p ⇔ q) ⇒ (p ⇒ q) (5)

Prueba:
p q (p ⇔ q) ⇒ (p ⇒ q)
V V V V V
V F F V F
F V F V V
F F V V V

La tabla confirma que (5) es tautologı́a.

No obstante, del tercer renglón de la tabla anterior, podemos concluir que proposición

(p ⇒ q) ⇒ (p ⇔ q)

no es tautologı́a.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 14

Leyes Conmutativas
∨ y ∧ conmutan Cálculo I

Leyes conmutativas

Conmutatividad de ∨: Conmutatividad de ∧:

Es tautologı́a: Es tautologı́a:

p∨q ⇔q∨p p∧q ⇔q∧p

Prueba: Prueba:
p q p∨q ⇔ q∨p p q p∧q ⇔ q∧p
V V V V V V V V V V
V F V V V V F F V F
F V V V V F V F V F
F F F V F F F F V F

Las tablas confirman que los conectivos ∨ y ∧ son conmutativos.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 15

Leyes Asociativas
∨ y ∧ son conectivos asociativos Cálculo I

Leyes Asociativas de ∨ y ∧

Las siguientes proposiciones son equivalencias lógicas:

((p ∨ q) ∨ r) ⇔ (p ∨ (q ∨ r))
((p ∧ q) ∧ r) ⇔ (p ∧ (q ∧ r))

Prueba: Tabla para la Ley Asociativa de ∨:

p q r p∨q q∨r (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)
V V V V V V V V
V V F V V V V V
V F V V V V V V
V F F V F V V V
F V V V V V V V
F V F V V V V V
F F V F V V V V
F F F F F F V F

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 16

Leyes de De Morgan
¿Cómo negar una disyunción y una conjunción? Cálculo I

Las Leyes de De Morgan

Las siguientes proposiciones son equivalencias lógicas:

¬(p ∧ q) ⇔ ¬p ∨ ¬q (LdDM-1)
¬(p ∨ q) ⇔ ¬p ∧ ¬q (LdDM-2)

Prueba: Tabla de la Primera Ley de De Morgan (LdDM-1):

p q ¬p ¬q p∧q ¬(p ∧ q) ⇔ ¬p ∨ ¬q
V V F F V F V F
V F F V F V V V
F V V F F V V V
F F V V F V V V

La Primera Ley de De Morgan (LdDM-1) dice que la negación de una conjunción es

equivalente a la disyunción de las negaciones.
La Segunda Ley de De Morgan (LdDM-2) dice que la negación de una disyunción es
equivalente a la conjunción de las negaciones.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 17

Equivalencias de ⇒
⇒ tiene dos importantes equivalencias Cálculo I

Primera equivalencia de ⇒

Es tautologı́a:
(p ⇒ q) ⇔ ¬(p ∧ ¬q)

Prueba: Hacemos una tabla:

p q ¬q p⇒q p ∧ ¬q ¬(p ∧ ¬q) (p ⇒ q) ⇔ ¬(p ∧ ¬q)
V V F V F V V
V F V F V F V
F V F V F V V
F F V V F V V

¿Cómo entender un condicional?

Podemos entender un condicional de la manera siguiente: Una proposición q se infiere
de otra p, i.e. (p ⇒ q) es V, siempre que no ocurra p conjuntamente con la negación
de q, i.e. siempre que (p ∧ ¬q) es F.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 18

Equivalencias de ⇒
⇒ tiene dos importantes equivalencias Cálculo I
Segunda equivalencia de ⇒

Es tautologı́a:
(p ⇒ q) ⇔ (¬p ∨ q)

Prueba: Para verificar esta equivalencia podemos también usar una tabla. O también
podemos proceder como sigue:
Por la primera de las equivalencias de ⇒ probada en la tabla anterior, la primera ley de
De Morgan e involución, las dobles implicaciones que siguen son tautológicas:

(p ⇒ q) ⇔ ¬(p ∧ ¬q)
⇔ ¬p ∨ ¬¬q
⇔ ¬p ∨ q

Esto es, (p ⇒ q) y (¬p ∨ q) son equivalentes (por transitividad de ⇔).

Probar un condicional (P ⇒ Q), es equivalente a probar la

disyunción (¬P ∨ Q).
Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 19
Ley del Contra-recı́proco
Un condicional es equivalente al condicional recı́proco Cálculo I

Ley del Contra-recı́proco

Un condicional es equivalente al condicional recı́proco:

(p ⇒ q) ⇔ (¬q ⇒ ¬p)

Prueba. Los bicondicionales siguientes son tautológicos:

p ⇒ q ⇔ ¬(p ∧ ¬q) – equiv. (1) de ⇒

⇔ ¬(¬q ∧ p) – conmutatividad de ∧, reemplazo

⇔ ¬(¬q ∧ ¬¬p) – involución, reemplazo

⇔ ¬q ⇒ ¬p – equiv. (1) de ⇒

Por transitividad de ⇔, la proposición (p ⇒ q) ⇔ (¬q ⇒ ¬p) es tautologı́a.

Probar que un condicional (P ⇒ Q) es V es equivalente a probar

que el condicional recı́proco (¬Q ⇒ ¬P ) es V.

Araceli Guzmán y Guillermo Garro 1 Introducción 1.2 Lógica Proposicional 20