Un repaso de lógica

Proposiciones Lógicas (Sentencias, Statements)

(i) Por facilidad (conveniencia, estrategia) empezamos con las

sentencias mas simples, que son las proposiciones lógicas.

(ii) En general, se puede decir que una proposición lógica es algo

de lo que podemos afirmar si es verdadero o falso, por ejemplo
a. Febrero tiene 30 dı́as.
b. El número 2 es mayor que el número 4.

(iii) Las siguientes oraciones no son proposiciones lógicas

a. ¡Haz tus deberes!
b. ¿Qué hora es?
Notación e Hipótesis
En lo sucesivo, nos referiremos a una proposición lógica en general
con letras, e.g., p, q, r , . . ., sin meternos a reflexionar en su
contenido, también asumimos las dos siguientes hipótesis.

Hipótesis
(i) Toda proposición es verdadera o falsa.
(ii) Ninguna proposición puede ser verdadera y falsa a la vez.
Proposiciones Compuestas
(i) La matemática se interesa en proposiciones
considerablemente más complejas que los ejemplos dados.
Para lograr estudiarlas, un primer paso es analizar proposiciones
compuestas por dos o mas proposiciones y conectores lógicos.
(ii) El valor de verdad de la proposición compuesta dependerá del
valor de verdad de las proposiciones que la componen y del
conector que las une, es decir depende de sus elementos y de
su estructura.
(iii) Los conectores lógicos que analizaremos son
a. Conjunción (y, ∧).
b. Disyunción (o, ∨).
c. Negación (no, ¬ o ∼).
d. Condicional o Implicación (si, ... , entonces, ... →).
e. Bicondicional o Equivalencia (..., si y solo si, ... ⇔).
Conjunción

La composición más natural es la conjunción (conector

y), denotada p ∧ q. Su valor de verdad viene dada por la
siguiente tabla
p q p∧q
V V V
V F F
F V F
F F F
Table: Tabla de verdad de la Conjunción p ∧ q.
Disyunción

La segunda composición es la disyunción (conector o), denotada

p ∨ q. Su valor de verdad viene dada por la siguiente tabla

p q p∨q
V V V
V F V
F V V
F F F
Table: Tabla de verdad de la Disyunción p ∨ q.
Negación
La tercera composición es la negación, denotada ¬p o ∼ p. Su valor
de verdad viene dada por la siguiente tabla

p ¬p
V F
F V
Table: Tabla de verdad de la Negación ¬p .
Equivalencia Lógica

Diremos que dos proposiciones lógicas son equivalentes si es que

sus tablas de verdad son iguales. Denotaremos la equivalencia
entre proposiciones lógicas con el sı́mbolo ≡.

Estrategia
En muchas instancias del discurso matemático, se busca probar
la veracidad o falsedad de una proposición lógica. Dicha tarea
puede ser bastante difı́cil en su forma original, pero es posible
que sea más facil probar la veracidad de una construcción
lógica equivalente.
Ejemplo
La estructura de doble negación es equivalente a la proposición original como
se ve en la tabla a continuación
p ¬p ¬¬p
V F V
F V F
Como se ve en la tabla p es equivalente a ¬¬p; que en lo sucesivo denotaremos
por p 𠪪p.

Ejemplo
Leyes de Morgan: Negación de la conjunción y de la disyunción
∼ (p ∧ q) ≡∼ p∨ ∼ q
∼ (p ∨ q) ≡∼ p∧ ∼ q
Condicional o Implicación

La cuarta composición es el condicional (conector entonces),

denotada p → q. Su valor de verdad viene dada por la siguiente tabla

p q p→q
V V V
V F F
F V V
F F V
Table: Tabla de verdad de la Implicación p → q.
Bicondicional o Equivalencia
La quinta composición es el bicondicional (conector si y solo si),
denotada p ⇔ q. Su valor de verdad viene dada por la siguiente tabla

p q p⇔q
V V V
V F F
F V F
F F V
Table: Tabla de verdad del Bicondicional p ⇔ q.
Negación del Condicional.

Las estructuras ¬(p → q) y p ∧ ¬q son equivalentes como se ve en

las tablas a continuación.

p q p→q ¬(p → q) p q ¬q p ∧ ¬q
V V V F V V F F
V F F V V F V V
F V V F F V F F
F F V F F F V F
Tautologı́as y contradicciones
Una tautologı́a es una proposición lógica que siempre es verdadera,
independientemente de los valores de verdad de las proposiciones simples
que la componen. Denotaremos por t a una proposición lógica tautológica.

Ejemplo
▶ p∨ ∼ p ≡ t
▶ p∧t≡p

Una contradicción es una proposición lógica que siempre es falsa,

independientemente de los valores de verdad de las proposiciones simples
que la componen. Denotaremos por c a una proposición lógica
contradictoria.

Ejemplo
▶ p∧ ∼ p ≡ c
▶ p∨c≡p
Teorema: Equivalencias lógicas
Sean p, q y r proposiciones simples, con una tautologı́a t y una contradicción c, se cumple

Ejemplo
Utilice el teorema para comprobar la equivalencia lógica

(p ∧ (∼ (∼ p ∨ q))) ∨ (p ∧ q) ≡ p

∼ (p∨ ∼ q) ∨ (∼ p∧ ∼ q) ≡∼ p
Recı́proco, contrarecı́proco e inverso
En una proposición condicional p → q diremos que p es la hipótesis
o antecedente y que q es la conclusión o consecuente.

Dada una proposición condicional p → q

▶ la proposición q → p es conocida como su recı́proco o su
converso,
▶ la proposición ∼ q →∼ p es conocida como su contrarecı́proco
o su contrapositivo,
▶ la proposición ∼ p →∼ q es conocida como su inverso o su
contrario o su negación.

Comentario
▶ p → q ≡∼ q →∼ p
▶ q → p ≡∼ p →∼ q
Proposiciones con Cuantificadores
Existen proposiciones que contienen implı́citamente cuantificadores lógicos dentro de su
estrúctura. El uso de cuantificadores permite ampliar aún mas el espectro de proposiciones que
podemos construir y estudiar.

Ejemplo
N R
(i) “Todos los números naturales son números reales”.
En lenguaje formal-simbólico ∀n ∈ , n ∈ .

R N
(ii) “Todos los números reales son números naturales”.
En lenguaje formal-simbólico ∀x ∈ , x ∈ .

En lenguaje formal-simbólico ∃x ∈ R : x ∈ / N.
(iii) “Existe un número real que no es un número natural”.

En lenguaje formal-simbólico ∃n ∈ N : n ∈ / R.
(iv) “Existe un número natural que no es un número real”.

Discusión
(i) En el primer y segundo enunciado la palabra “Todos” es el cuantificador universal, en adelante representado por el
sı́mbolo ∀. En la tercera y cuarta proposición la palabra “Hay” es el cuantificador existencial, en adelante denotado
por ∃.
(ii) Es importante notar la validez de las proposiciones en función a los conjuntos de referencia. Ası́, la primera y tercera
proposición son verdaderas, mientras que la segunda y cuarta son falsas.
Negación de Cuantificadores
La negación de los cuantificadores se hace como sigue
I. La negación del cuantificador universal es el existencial, i.e.

¬(∀x)p(x) = (∃x)¬p(x)

II. La negación del cuanficador existencial es el universal, i.e.,

¬(∃y)q(y) = (∀y)¬q(y)

Ejemplo
Negar los siguientes enunciados
(i) (∀x) p(x) ∧ (∃x) q(x).



(ii) (∀y ) p(y ) → (∀x) q(x) .
 Métodos de demostración
Un poco de teorı́a de números
▶ Definiremos y discutiremos varias propiedades básicas de los
números naturales N Z
y enteros , que son frecuentes en el
discurso matemático.
▶ La suma, diferencia y producto de dos números enteros es un
entero. La división de dos enteros, en cambio, no
necesariamente es un entero.

Definición (Número par, impar, racional e irracional)

(i) Un número entero n es par si y solo si existe un número entero k tal que n = 2k .
(ii) Un número entero m es impar si y solo si existe un número entero j tal que
m = 2j + 1.
(iii) Un número real es llamado racional si puede expresarse en la forma m/n donde m y n
son números enteros y n ̸= 0. Un número real es llamado irracional si no es racional.

Q Z)(∃n ∈ Z)
 
m
x ∈ ⇐⇒ (∃m ∈ x = ∧ n ̸= 0
n
Divisibilidad

Definición (Divisibilidad)
Sean a y b enteros. Decimos que a divide a b si existe un entero c tal que b = ac. Cuando
a divide a b, lo simbolizamos como a|b. En esta situación también se dice que a es un
divisor de b.

A continuación simbolizamos la definición de divisibilidad y su negación

a|b ⇐⇒ (∃c ∈ Z)(b = ac)

a∤b ⇐⇒ (∀c ∈ Z)(b ̸= ac)

Comentario
Note que
(i) 1 divide a cualquier entero pues 1 · n = n.
(ii) Cualquier entero, se divide a sı́ mismo.
(iii) Los divisores positivos de un entero positivo n están entre 1 y n, aunque no
necesariamente todos dividen a n.
(iv) Todo entero divide a 0.
Números Primos

Definición (Números Primos)

Un número natural p se dice número primo si y solo si p > 1 y los únicos divisores
positivos de p son 1 y p.

Ejemplo
(i) Los números 2, 3, 5, 7, 11, 13, 17, . . . son primos.
(ii) Los números pares mayores a 2 no son primos.
(iii) El número 24 se puede factorizar como sigue 24 = 23 · 3. Note que todos los factores
son o bien números primos o potencias de números primos. Dicha factorización es
conocida como factorización prima de 24. Note también que se puede factorizar
24 = 2 · 12 pero ésta no es una factorización prima de 24 pues 12 no es un número
primo.

Teorema (Teorema Fundamental de la Aritmética)

Todo entero mayor a uno es o bien un número primo o puede ser factorizado en números primos
de una manera única salvo por el orden de los factores primos.
Congruencia o Aritmética Modular

Definición
Sean a, b, y n enteros. Decimos que a es congruente con b módulo n si n divide a a − b. Se
simboliza esto mediante a ≡ b(mod n).

La simbolización de la congruencia y su negación son como sigue:

a ≡ b (mod n) ⇐⇒ n|(a − b)
⇐⇒ (∃c ∈ Z)(a − b = nc)
a ̸≡ b (mod n)) ⇐⇒ (∀c ∈ Z)(a − b ̸= nc)

Ejemplo
(i) 37 ≡ 73 mod 12
(ii) Para todo k, n ∈ Z se cumple que 2n + 1 ≡ 2k + 1 mod 2
(iii) 12 no es congruente a 5 módulo 3
Métodos de demostración
Un teorema es una proposición matemática que es verdadera y que además tiene una
demostración.
Usualmente, un teorema se expresa como una proposición condicional de la forma
“si P, entonces Q”
En tal caso la proposición P es llamada la hipótesis del teorema y Q es llamada la
tesis.
Hay otras palabras usadas en matemáticas que significan esencialmente lo mismo que
teorema.
▶ Teorema. Proposición significativa o importante que tiene una demostración.
▶ Proposición. Proposición verdadera con demostración, pero no tan significativa
o importante como para llamarla teorema.
▶ Lema. Proposición verdadera con demostración, que ayuda en la demostración
de un teorema.
▶ Corolario. Proposición verdadera que es consecuencia inmediata de un
teorema o una proposición.
Una demostración es una verificación escrita que muestra de manera
irrefutable que un teorema es verdadero. Usualmente, en una demostración,
se realiza una serie de deducciones partiendo de las hipótesis del teorema
y valiéndose de las definiciones, ası́ como de otros teoremas previamente
demostrados y las reglas de la lógica, se concluye la tesis del teorema.

Demostración directa
La demostración directa es un método que se utiliza para demostrar
teoremas con forma condicional p → q.

Sean n, m, a, b números enteros. Demostrar:

▶ Si n es impar entonces n2 + n es par.
▶ Si n|m y a ≡ b (mod m) entonces a ≡ b (mod n).
Demostración por contrarrecı́proco

La demostración por contrarrecı́proco se utiliza para demostrar

teoremas con forma condicional p → q. Se basa en la equivalencia
(p → q) ⇐⇒ (¬q → ¬p); es decir, en en lugar de demostrar
directamente que p implica q, se demuestra que la negación de q
implica la negación de p.

Sea n un número entero. Demostrar:

▶ Si 5n − 7 es impar entonces n es par.
▶ Si n2 es par entonces n es par.
Reducción al absurdo
Cuando nuestros argumentos son deductivos y en algún momento
concluimos algo falso, es porque alguna de las premisas tiene que
ser falsa. En esto se basa el método de reducción al absurdo, o
contradicción. Para demostrar un teorema por reducción al absurdo,
se toma como premisa que lo que afirma el teorema es falso. Si
razonamos deductivamente hasta llegar a una conclusión falsa o
contradictoria, concluimos que lo que afirma el teorema en realidad
es verdadero.
√
▶ El número 2 es irracional.
√ √
▶ El número 2 + 3 es irracional.
Otros tipos de demostración

▶ Demostración bicondicionales p ⇔ q

p⇔q ⇐⇒ (p → q) ∨ (q → p)

Un entero n es impar si y solo si n2 es impar.

▶ Demostración por casos (p ∨ q) → r

(p ∨ q) → r ⇐⇒ (p → r ) ∧ (q → r )

Sea n es un entero. Si n ≡ 1 (mod 4) o n ≡ 3 (mod 4) entonces n2 ≡ 1 (mod 8)

▶ Teorema de la forma p → (q ∨ r )

p → (q ∨ r ) ⇐⇒ (p ∧ ¬q) → r

Sean a y b enteros. Si ab es par entonces a es par o b es par.

▶ Teorema de la forma p → (q ∧ r )

p → (q ∧ r ) ⇐⇒ (p → q) ∧ (p → r )

Sea n impar entonces 3n + 1 es par y 5n + 2 es impar.