Teoria Tema 1 GCED

GCED.
Curso 2023–2024
Tema 1
Razonamiento Lógico
Recuerda que estas notas son, únicamente, parte del material de trabajo de los profesores de esta
asignatura. Los contenidos de este tema se pueden ver en los siguientes libros:
• K.H. Rosen, Matemática Discreta y sus aplicaciones (5 ed.): capítulo 1 (secciones 1.1 hasta
1.5, incluidas) y capítulo 3 (secciones 3.1, 3.2 y 3.3).
• R.P. Grimaldi, Matemática Discreta y combinatoria (3 ed.): capítulo 2 y capítulo 4 (sección

4.1).
Cuando se plantea qué matemáticas va a necesitar un informático, la primera respuesta es:

lógica y matemática discreta puesto que la computación básicamente trata con cantidades que
no varían de forma continua, es decir, que son discretas. Las razones por las que un informático
necesita estudiar lógica son fuertes: en ella se encuentran las raíces de la ciencia de la computación
(los trabajos de Church y Turing estaban motivados por el problema de decisión para la lógica de
primer orden) y, de forma recíproca, la informática ha generado una explosión de interés en lógica,
desde la búsqueda de métodos de automatización del razonamiento hasta la verificación de la
corrección de un software. Esto es el equivalente al test de prueba de un producto de ingeniería;
Área de Álgebra
pero, dado que el software es un producto matemático, el test va más allá: es preciso demostrar
que no tiene errores y que realiza lo especificado.
La lógica trata de la formalización del lenguaje y los métodos correctos de razonamiento, reglas
y técnicas para determinar si un argumento dado es válido o no. En su forma tradicional, la lógica
tiene una historia mucho más larga que la computación, remontándose al siglo IV a.C. con la
codificación del silogismo, por Aristóteles (384–322 a.C.). Con ello se determinaban las formas
del razonamiento válidas, frente a las no válidas de los sofistas. Ello, junto con el estudio de la
estructura de los lenguajes naturales, sigue siendo objeto de la lógica y es relevante en inteligencia
artificial (para representación del conocimiento), en la construcción de programas informáticos y
en la verificación de la corrección de ellos.
En el siglo XVII, el filósofo alemán Leibniz (1646–1716) sugirió incorporar símbolos matemáticos
1
2 TEMA 1. RAZONAMIENTO LÓGICO
a la lógica con el fin de mecanizar el proceso de razonamiento deductivo. Durante el XIX estas ideas
se materializan en los trabajos de De Morgan (1806–1871), Frege (1848–1925) y, en especial, de
G. Boole (1815–1864) en su libro “Las leyes del pensamiento” (1854), donde desarrolla un sistema
de reglas que le permitan expresar, manipular y simplificar problemas lógicos mediante cálculo
simbólico.
1.1 Lógica Proposicional

1.1.1 Proposiciones
Los objetos básicos de la lógica son las proposiciones, que se definen de la forma siguiente.
Definición 1. Una proposición es una oración declarativa que es verdadera o falsa, pero no ambas
cosas a la vez. Le asignaremos uno, y solo uno, de los valores de verdad: verdadero (1) o falso
(0).
Ejemplo 1. Los siguientes enunciados son proposiciones:
• Los triángulos tienen cuatro vértices. (0)

• Ronaldo Del Carmen es uno de los codirectores de “Inside Out” (1)
• 2 + 2 = 4. (1)
• 2 × 4 = 7. (0)
Ejemplo 2. Los siguientes enunciados no son proposiciones:
• Ojalá no llueva.
• ¿A qué hora salimos de clase?
• ¡Prohibido!
• x + 3 = 4.
Las tres primeras frases no son proposiciones porque no son declarativas; la primera es
Área de Álgebra
desiderativa, la segunda interrogativa y la tercera es imperativa. La cuarta frase tampoco es

es proposición porque no es ni verdadera ni falsa, puesto que su valor de verdad depende del
valor que le asignemos a x. Este tipo de frases se estudiarán en la sección 1.3.
1.1.2 Operadores lógicos. Sintaxis
Las proposiciones primitivas (simples o atómicas) son aquellas proposiciones que no se pueden
descomponer en otras más simples (como las que aparecen en el ejemplo 1); suelen designarse
con letras minúsculas p, q, r , etc. Para obtener nuevas proposiciones, llamadas compuestas, se
utilizan los conectivos u operadores lógicos siguientes: ¬, ∧, ∨, → y ↔.
1.1. LÓGICA PROPOSICIONAL 3
• Negación (¬) Si p es una proposición, la negación de p se denota por ¬p y se lee:
“no p” “no ocurre p” “no es cierto p”
• Conjunción (∧) Si p y q son proposiciones, la conjunción de p y q se denota por p ∧ q y

se lee:
“p y q” “p, no obstante q” “p, pero q”

“p, sin embargo q” “p, q” “p, aunque q”
• Disyunción (∨) Si p y q son proposiciones, la disyunción de p y q se denota por p ∨ q y se

lee:
“p o q (o ambos)” “al menos p o q” “como mínimo p o q”
• Condicional (→) Si p y q son proposiciones, el condicional p → q se lee:
“Si p, entonces q”
“Si p, q” “q si p”
“p solo si q” “q siempre que p”
“cuando p, entonces q” “q cuando p”
“p es suficiente para q” “q es necesario para p”
• Bicondicional (↔) Si p y q son proposiciones, el bicondicional p ↔ q se lee:
“p si, y solo si, q” “p es suficiente y necesario para q”
Definición 2. Al conectar entre sí las proposiciones mediante los operadores lógicos, se obtienen
expresiones o fórmulas bien formadas (f.b.f.). Las reglas para construir una expresión bien
formada son:
Área de Álgebra
i) Las proposiciones primitivas o atómicas son f.b.f.
ii) Si P es una f.b.f., ¬P es una f.b.f.
iii) Si P y Q son f.b.f., entonces P ∧ Q, P ∨ Q, P → Q y P ↔ Q son f.b.f.
iv) No hay más reglas.
Como símbolos auxiliares se utilizan paréntesis o corchetes, que sirven para agrupar y evitar
ambigüedades. Además, cuando hay más de una conectiva en una fórmula, entenderemos que
cada conectiva afecta a la letra proposicional inmediata o al conjunto de proposiciones inmediatas
encerradas entre paréntesis.
Ejemplo 3. La expresión p → (¬q) es una f.b.f., mientras que p → (∧q) no lo es.
Se establece una jerarquía de prioridades entre las conectivas, que permitirá suprimir paréntesis.
En el primer nivel se sitúa la negación, en el segundo nivel la conjunción, le sigue la disyunción, a
continuación el condicional y, en último nivel, el bicondicional. Así, p → (q ∧ r ) puede escribirse
como p → q ∧ r , y p → q ∧ ¬r es p → (q ∧ (¬r )).
Ejemplo 4. En la proposición compuesta ¬p ∧ (r → t) no podemos eliminar paréntesis ya que, si

los suprimimos, quedaría la secuencia ¬p ∧ r → t que representa a (¬p ∧ r ) → t. En ¬p ∧ (q ∨ r )
tampoco se pueden suprimir los paréntesis, ya que la conjunción tiene prioridad sobre la disyunción
y ¬p ∧ q ∨ r se corresponde con (¬p ∧ q) ∨ r
Ejemplo 5. Para formalizar la frase “Si Juan va al cine pero no compra palomitas, ahorra 2 euros”,
consideramos las proposiciones atómicas:
p: Juan va al cine, q: Juan compra palomitas y r : Juan ahorra 2 euros.
El enunciado dado se corresponde con p ∧ ¬q → r .
1.1.3 Operadores lógicos. Semántica

Al igual que a las proposiciones primitivas, a las proposiciones compuestas se les asigna un valor
de verdad. Los valores de verdad de estas dependen de los valores de verdad de las proposiciones
primitivas que las componen.
Dadas las proposiciones p y q,
• La negación ¬p es verdadera únicamente cuando p es falsa.
• La conjunción p ∧q es verdadera cuando tanto p como q son verdaderas, y falsa en cualquier

otro caso.
• La disyunción p ∨ q es falsa cuando tanto p como q son falsas, y verdadera en cualquier

otro caso.
• El condicional p → q es falso cuando p es verdadera y q es falsa, y verdadero en cualquier

Área de Álgebra
otro caso.
• El bicondicional p ↔ q es verdadero cuando p y q tienen los mismos valores de verdad, y

falso en los otros casos.
A continuación se muestran en unas tablas (llamadas tablas de verdad) los valores de las
proposiciones anteriores:
p ¬p p q p∧q p∨q p→q p↔q

0 1 0 0 0 0 1 1
1 0 0 1 0 1 1 0
1 0 0 1 0 0
1 1 1 1 1 1
Comprender el significado (la semántica) del condicional es muy importante, para ello veamos
el siguiente ejemplo.
Ejemplo 6. El padre de Juan le dice a este: “Si apruebas Matemática Discreta, te compro un
ordenador”. En este caso, lo simbolizaríamos como p → q, donde
p : “Apruebas Matemática Discreta” q : “Te compro un ordenador”
Se pueden distinguir cuatro casos:
i) p y q son ambas verdaderas, es decir Juan aprueba Matemática Discreta y su padre le compra
el ordenador. Se cumple la promesa y el valor de verdad del condicional es 1.
ii) p es verdadera (Juan aprueba Matemática Discreta) pero q es falsa (su padre no le compra
el ordenador). Entonces, la promesa se ha roto y el valor de verdad de p → q es 0.
iii) p y q son ambas falsas (Juan suspende Matemática Discreta y su padre no le compra el
ordenador). La promesa no se ha roto ya que Juan no ha cumplido su parte, por lo que el
valor de verdad de p → q es 1.
iv) p es falsa (Juan suspende) y q es verdadera (su padre le compra el ordenador). Aunque el
padre le compra el ordenador a Juan, tampoco, en este caso, se rompe la promesa y el valor
de verdad del condicional es 1.
Es decir, el padre rompe su promesa únicamente cuando Juan aprueba y, sin embargo, no
le compra el ordenador. Es decir, el valor del condicional p → q es 0 únicamente cuando p es
verdadera y q es falsa.
Ejemplo 7. Fijémonos en la diferencia entre el argumento anterior y el siguiente. El padre de Juan

le dice a este: “Te compro un ordenador si, y solamente si, apruebas Matemática Discreta". En
este caso, lo simbolizaríamos como q ↔ p. Veamos aquí los cuatro casos posibles:
i) p y q son ambas verdaderas, es decir Juan aprueba Matemática Discreta y su padre le compra
Área de Álgebra
el ordenador. Se cumple la promesa y el valor de verdad de la bicondicional es 1.
ii) p es verdadera (Juan aprueba Matemática Discreta) pero q es falsa (su padre no le compra
el ordenador). Entonces, la promesa se ha roto y el valor de verdad de p ↔ q es 0.
iii) p y q son ambas falsas (Juan suspende Matemática Discreta y su padre no le compra el
ordenador). La promesa no se ha roto ya que Juan no ha cumplido su parte, por lo que el
valor de verdad de p ↔ q es 1.
iv) p es falsa (Juan suspende) y q es verdadera (su padre le compra el ordenador). Como el
padre dejó claro que solamente le compraría el ordenador a Juan si aprobaba, el valor de
verdad de p ↔ q es 0.
Definición 3. Una tabla de verdad para una proposición compuesta es un método que proporciona
los valores de verdad de la proposición dada, a partir de los valores de verdad de las proposiciones
atómicas que la conforman.
Para construirla se determinan los valores de verdad de sus subproposiciones componentes,

desde las más sencillas hasta las más complejas.
Ejemplo 8. La tabla de verdad de (p ∨ q) ∧ (p → ¬q) es:
p q p∨q ¬q p → ¬q (p ∨ q) ∧ (p → ¬q)
0 0 0 1 1 0 ⇝ contraejemplo
0 1 1 0 1 1 ⇝ modelo
1 0 1 1 1 1 ⇝ modelo
1 1 1 0 0 0 ⇝ contraejemplo
Una interpretación de una fórmula P es una asignación de verdad de las proposiciones atómicas
que aparecen en P. Cada fila de la tabla de verdad de P se corresponde con una interpretación
de P. Si en P intervienen n proposiciones primitivas, hay 2n posibles interpretaciones de P (lo
cual muestra que es un procedimiento de complejidad exponencial). También se puede definir una
interpretación de P como una aplicación del conjunto de átomos que intervienen en P al conjunto
{0, 1}.
Si para una interpretación de P, el valor de P es 1 se dice que esa interpretación es un modelo;
si, por el contrario, el valor de P es 0 se dice que esa interpretación es un contraejemplo. En el
caso anterior, la primera y la última fila se corresponden con contraejemplos y las otras dos son
modelos. Es decir, {¬p, q} y {p, ¬q} son modelos de (p ∨ q) ∧ (p → ¬q), mientras que {¬p, ¬q}
y {p, q} son contraejemplos.
Se puede obtener la tabla de verdad de una proposición P utilizando otra forma de disponer
sus subproposiciones. Para el ejemplo anterior, quedaría:
Área de Álgebra
p q p∨q (p ∨ q) ∧ (p → ¬q) p → ¬q ¬q
0 0 0 0 1 1
0 1 1 1 1 0
1 0 1 1 1 1
1 1 1 0 0 0
Paso 1 2 5 4 3
El valor de verdad de cada paso queda determinado por los valores de verdad de los pasos ante-
riores, como vemos en la siguiente tabla donde se calculan los valores de verdad de la proposición
(p ∧ q) ∨ ¬p → ¬q:
p q p∧q ¬p (p ∧ q) ∨ ¬p (p ∧ q) ∨ ¬p → ¬q ¬q
0 0 0 1 1 1 1
0 1 0 1 1 0 0
1 0 0 0 0 1 1
1 1 1 0 1 0 0
Paso 1 2 3 4 6 5
Se dice que {¬p, ¬q} y {p, ¬q} son modelos de (p ∧ q) ∨ ¬p → ¬q, mientras que {¬p, q} y {p, q}
son contraejemplos.
Definición 4. Una fórmula que solamente admite modelos se denomina tautología, y se denotará
⊤. Una fórmula que solamente admite contraejemplos se denomina contradicción, y se denotará
⊥. Finalmente, una fórmula que no es ni una tautología ni una contradicción se llama contingencia.
Una fórmula es satisfacible si admite al menos un modelo (no es una contradicción). Una fórmula
que no admite modelos se denomina contradicción o fórmula insatisfacible.
Ejemplo 9.
• p ∨ ¬(p ∧ q) es una tautología. • ¬(p → q) es satisfacible.
• (p ∧ q) ∧ ¬(p ∨ ¬q) es una contradicción. • ¬p → q es una contingencia.

p q p ∨ ¬(p ∧ q) (p ∧ q) ∧ ¬(p ∨ ¬q) ¬(p → q) ¬p → q
0 0 1 0 0 0
0 1 1 0 0 1
1 0 1 0 1 1
1 1 1 0 0 1
Definición 5. Un conjunto de proposiciones {P1 , P2 , . . . , Pn } se dice que es consistente (o

satisfacible) si la conjunción de todas ellas P1 ∧ P2 ∧ · · · ∧ Pn admite al menos un modelo1 .
En caso contrario, es decir, si P1 ∧ P2 ∧ · · · ∧ Pn es una contradicción, el conjunto {P1 , P2 , . . . , Pn }
se dice inconsistente.
El problema de decidir si un conjunto de proposiciones es satisfacible se denomina problema SAT.
Área de Álgebra
No se sabe cómo resolverlo en tiempo polinomial, y constituye uno de los retos más importantes
en informática teórica.
Ejemplo 10.
• El conjunto {p → q, p ∧ q} es consistente ya que, cuando p y q son verdaderas, las fórmulas
p → q y p ∧ q son verdaderas, es decir, (p → q) ∧ (p ∧ q) admite un modelo (cuando p y q
son verdaderas, {p, q}).
• El conjunto {p → q, p ∧ ¬q} es inconsistente ya que (p → q) ∧ (p ∧ ¬q) no admite ningún

modelo (el único modelo de p ∧ ¬q es un contraejemplo de p → q).
1
Esto indica que hay una interpretación que es modelo de todas las proposiciones P1 , P2 , . . . , Pn .
p q p→q p∧q (p → q) ∧ (p ∧ q) p q p→q p ∧ ¬q (p → q) ∧ (p ∧ ¬q)

0 0 1 0 0 0 0 1 0 0
0 1 1 0 0 0 1 1 0 0
1 0 0 0 0 1 0 0 1 0
1 1 1 1 1 1 1 1 0 0
En la sección 1.1.5 veremos otro método, el de las tablas semánticas, para estudiar si un
conjunto de fórmulas es consistente o no.
1.1.4 Implicaciones y Equivalencias lógicas

Consideremos las dos afirmaciones siguientes: “Marta es estudiante y juega al tenis” y “Marta
juega al tenis y es estudiante”. Obviamente, ambas tienen siempre los mismos valores de verdad.
Para hacer más precisa esta idea, sea p la proposición “Marta es estudiante” y sea q la proposición
“Marta juega al tenis”, entonces la primera de las dos afirmaciones se traduce en p ∧ q, mientras
que la segunda se traduce en q ∧ p. Mediante las tablas de verdad se puede comprobar que estas
dos expresiones tienen los mismos valores de verdad para todas las asignaciones posibles; esto es,
(q ∧ p) ↔ (p ∧ q) es una tautología.
Definición 6. Dos proposiciones compuestas P y Q se dicen lógicamente equivalentes si ambas
tienen los mismos valores de verdad para cada interpretación de los valores de verdad de sus
proposiciones componentes (es decir, la fórmula P ↔ Q es una tautología). Esta situación se
representa por
P≡Q
También puede denotarse por P ⇐⇒ Q. Es importante diferenciar “⇐⇒” de “↔”:
P ⇐⇒ Q indica que la fórmula P ↔ Q es una tautología, mientras que cuando se escribe P ↔ Q
simplemente se está dando una proposición compuesta. Nótese que P ⇐⇒ Q no es una f.b.f.
Ejemplo 11. Las proposiciones ¬(p ∧ q) y ¬p ∨ ¬q son lógicamente equivalentes:
p q ¬(p ∧ q) ¬p ∨ ¬q ¬(p ∧ q) ↔ (¬p ∨ ¬q)

Área de Álgebra
0 0 1 1 1
0 1 1 1 1
1 0 1 1 1
1 1 0 0 1
Ejemplo 12. La proposición compuesta p∧q ↔ q no es una tautología, por lo que las proposiciones
p ∧ q y q no son lógicamente equivalentes.
p q p∧q q p∧q ↔q
0 0 0 0 1
0 1 0 1 0
1 0 0 0 1
1 1 1 1 1
Para cualesquiera fórmulas P, Q, R, se verifica que:

• P≡P
• si P ≡ Q, entonces Q ≡ P
• si P ≡ Q y Q ≡ R, entonces P ≡ R
Al final de esta sección, la tabla 1.1 recoge algunas equivalencias lógicas.

Las equivalencias lógicas de la tabla, así como cualquier otra que se haya probado, permiten
construir otras equivalencias lógicas. Ello se debe a que una proposición en una fórmula se puede
substituir por otra que sea lógicamente equivalente sin alterar el valor de la fórmula:
Sea P una proposición compuesta, de la cual forma parte una proposición Q, y sea Q∗ una proposi-
ción lógicamente equivalente a Q. Si se substituye alguna ocurrencia de Q en P por Q∗ , se obtiene
una proposición P ∗ lógicamente equivalente a P (regla de sustitución).
Ejemplo 13. Sea P la fórmula ¬(p ∨ q) → r . Puesto que la subfórmula ¬(p ∨ q) es lógicamente
equivalente a ¬p ∧ ¬q, se tiene que P ≡ P ∗ , siendo P ∗ la fórmula ¬p ∧ ¬q → r .
Ejemplo 14. Estas equivalencias permiten simplificar la fórmula (p ∨ q) ∧ ¬(¬p ∧ q) de la forma
siguiente:
(p ∨ q) ∧ ¬(¬p ∧ q) ≡ (p ∨ q) ∧ (p ∨ ¬q) Leyes de De Morgan y Doble negación
≡ p ∨ (q ∧ ¬q) Ley distributiva
≡ p∨⊥ Contradicción
≡ p Ley Identidad
Definición 7. Dadas dos proposiciones P y Q, se dice que P implica lógicamente Q, o que de P
se deduce Q, cuando la proposición P → Q es una tautología. Es decir, cuando P es verdadera,
también Q es verdadera y que cuando Q es falsa, P es falsa. En este caso, se escribe
P |= Q
También se denota por P =⇒ Q. De nuevo, es importante diferenciar “=⇒” y “→” :
mientras P =⇒ Q quiere decir que la fórmula P → Q es una tautología, cuando se escribe P → Q
simplemente se está dando una proposición compuesta. Nótese que P =⇒ Q no es una f.b.f.
Área de Álgebra
Ejemplo 15. Para demostrar que (p → q) ∧ p |= q es suficiente probar que la fórmula

[(p → q) ∧ p] → q es una tautología. Si se construye su tabla de verdad, se observa que todos sus
valores son 1:
p q p→q (p → q) ∧ p [(p → q) ∧ p] → q q
0 0 1 0 1 0
0 1 1 0 1 1
1 0 0 0 1 0
1 1 1 1 1 1
Paso 1 2 3 4 1
Al final de esta sección, la tabla 1.2 recoge algunas implicaciones lógicas.

Principales equivalencias lógicas

p∨q ≡q∨p
Leyes Conmutativas
p∧q ≡q∧p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r )
Leyes Asociativas
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r )
p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r )
Leyes Distributivas
p ∧ (q ∨ r ) ≡ (p ∧ q) ∨ (p ∧ r )
Ley de la Doble Negación ¬¬p ≡ p
¬(p ∨ q) ≡ (¬p ∧ ¬q)
Leyes de De Morgan
¬(p ∧ q) ≡ (¬p ∨ ¬q)
p∨⊤≡⊤
Leyes de Dominación
p∧⊥≡⊥
p∧⊤≡p
Leyes de Identidad
p∨⊥≡p
p ∨ ¬p ≡ ⊤
Leyes de la Negación
p ∧ ¬p ≡ ⊥
Ley de la Contraposición (p → q) ≡ (¬q → ¬p)
(p → q) ≡ (¬p ∨ q)
Leyes de la Implicación
¬(p → q) ≡ (p ∧ ¬q)
(p ↔ q) ≡ [(p → q) ∧ (q → p)]
Leyes de la Equivalencia
(p ↔ q) ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
p ≡ (p ∧ p)
Leyes Idempotentes
p ≡ (p ∨ p)
p ∧ (p ∨ q) ≡ p
Leyes de Absorción
p ∨ (p ∧ q) ≡ p
Ley de la Reducción al absurdo (p → q) ≡ [(p ∧ ¬q) → ⊥]
Table 1.1: Tabla de equivalencias
Principales implicaciones lógicas

Modus Ponens [(p → q) ∧ p] |= q
Modus Tollens [(p → q) ∧ ¬q] |= ¬p
Área de Álgebra
Silogismo [(p → q) ∧ (q → r )] |= (p → r )
(p ∧ q) |= p
Leyes de Simplificación
(p ∧ q) |= q
p |= (p ∨ q)
Leyes de Adición
q |= (p ∨ q)
((p ∨ q) ∧ ¬p) |= q
Silogismo Disyuntivo
((p ∨ q) ∧ ¬q) |= p
Ley de Casos [(p → q) ∧ (¬p → q)] |= q
Ley de Inconsistencia [p ∧ ¬p] |= q
Table 1.2: Tabla de implicaciones

1.1.5 Tablas semánticas

El método de las tablas semánticas2 o árbol semántico fue descubierto a mediados del siglo
pasado por Beth y Hintikka, independientemente uno del otro, y permite demostrar si un conjunto
de fórmulas es consistente o no. Para ello, se construye un árbol donde los nodos (finitos) son las
proposiciones, el conectivo ∧ se representa por un arista vertical,
p∧q
q
y el conectivo ∨ por un par de aristas en la forma
p∨q
p q
El resto de los conectivos se traducen a esa forma. Así, el condicional p → q se representa
como
p→q
¬p q
ya que p → q ≡ ¬p ∨ q. Por otro lado, como p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q), el bicondicional se
representará por
p↔q
p ¬p
Área de Álgebra
q ¬q
Para comprobar si un conjunto de proposiciones {P1 , P2 , . . . , Pn } es consistente, se construye la

tabla semántica de P1 ∧ P2 ∧ · · · ∧ Pn y se van descomponiendo, una a una, todas las proposiciones
compuestas, de acuerdo con las reglas anteriores, marcando las proposiciones ya utilizadas. Si en
una sucesión de nodos del árbol (camino) aparece una proposición y su negación, se dice que es
un camino cerrado y se marca con ∗ el nodo (vértice) final.
Si al final del proceso todos los caminos se cierran, la fómula P1 ∧ P2 ∧ · · · ∧ Pn es una
contradicción (el conjunto {P1 , P2 , . . . , Pn } es inconsistente); en caso contrario, cada camino
abierto representa un modelo de P1 ∧ P2 ∧ · · · ∧ Pn (es decir, {P1 , P2 , . . . , Pn } es consistente).
2
O tableaux, del inglés “cuadro escénico”.
Ejemplo 16. Para comprobar si el conjunto {p → ¬r, ¬q → r, p ∨ ¬q} es o no consistente, se

construye el árbol semántico de (p → ¬r ) ∧ (¬q → r ) ∧ (p ∨ ¬q)
p → ¬r
¬q → r
p ∨ ¬q
Se descompone cada una de las fórmulas compuestas, sin importar el orden, pero una vez des-
compuesta una fórmula se marca (✓), y se van señalando las ramas que se cierran (∗):
p → ¬r ✓
¬q → r ✓
p ∨ ¬q ✓
¬p ¬r apli cando p → ¬r ≡ ¬p ∨ ¬r
p ¬q p ¬q
∗
q r q r q r apli cando ¬q → r ≡ q ∨ r
∗ ∗ ∗ ∗
Las ramas abiertas, {¬p, ¬q, r } y {p, q, ¬r }, proporcionan los modelos de
(p → ¬r ) ∧ (¬q → r ) ∧ (p ∨ ¬q).
Es decir, cuando p y q son falsas y r verdadera, o bien cuando p y q son verdaderas y r falsa, la
proposición (p → ¬r ) ∧ (¬q → r ) ∧ (p ∨ ¬q) es verdadera o, lo que es lo mismo, todas las fórmulas
del conjunto {p → ¬r, ¬q → r, p ∨ ¬q} tienen valor de verdad 1.
Ejemplo 17. Consideremos ahora el conjunto de fórmulas {p → ¬r, ¬q → r, p ∧ ¬q}. El árbol
semántico correspondiente a (p → ¬r ) ∧ (¬q → r ) ∧ (p ∧ ¬q) es:
Área de Álgebra
p → ¬r ✓
¬q → r ✓
¬q
¬p ¬r apli cando p → ¬r ≡ ¬p ∨ ¬r
∗
q r apli cando ¬q → r ≡ q ∨ r
∗ ∗
Como todos los caminos se cierran, el conjunto de fórmulas dado es inconsistente, es decir,
(p → ¬r ) ∧ (¬q → r ) ∧ (p ∧ ¬q) no tiene ningún modelo (es una contradicción).
1.1.6 Argumentos y métodos de demostración

Definición 8. Dado un conjunto de proposiciones {H1 , H2 , . . . , Hn }, se dice que una proposición
C es consecuencia de ellas si H1 ∧ H2 ∧ . . . ∧ Hn |= C (también se dice que este es un argumento
válido, y se puede representar por {H1 , H2 , . . . , Hn } |= C).
Las proposiciones H1 , H2 , . . . , Hn se llaman hipótesis o premisas y C se llama conclusión. El
argumento es válido si, siempre que todas las hipótesis son verdaderas, también lo es la conclusión.
Se puede realizar una demostración directa de la validez de un argumento mediante tablas de

verdad.
Ejemplo 18. Para demostrar la implicación lógica “Modus Tollens”, es decir,
{p → q, ¬q} |= ¬p
se prueba que (p → q) ∧ ¬q → ¬p es una tautología:
p q p→q (p → q) ∧ ¬q (p → q) ∧ ¬q → ¬p
0 0 1 1 1
0 1 1 0 1
1 0 0 0 1
1 1 1 0 1
Ejemplo 19. Si queremos demostrar que
{p → r, q → r } |= p ∨ q → r
llamamos
Área de Álgebra
H1 : p → r H2 : q → r C : p∨q →r
y construimos la tabla de verdad de H1 ∧ H2 → C para comprobar que es una tautología:
p q r H1 : p → r H2 : q → r H1 ∧ H2 H1 ∧ H2 → C C : p∨q →r
0 0 0 1 1 1 1 1
0 0 1 1 1 1 1 1
0 1 0 1 0 0 1 0
0 1 1 1 1 1 1 1
1 0 0 0 1 0 1 0
1 0 1 1 1 1 1 1
1 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1
Teniendo en cuenta que el condicional H1 ∧ H2 → C es falso únicamente cuando la conjunción

H1 ∧ H2 es verdadera (esto es, si las hipótesis, H1 y H2 , son ambas verdaderas) y la conclusión C
es falsa, para estudiar si
H1 ∧ H2 |= C
es un argumento válido, basta calcular únicamente los valores de verdad de H1 ∧ H2 en los casos en
los que C tiene valor de verdad 0. Esto es, en la tabla del ejemplo anterior los cálculos se reducen
a las filas tercera, quinta y séptima. Incluso en esas filas, si una de las hipótesis es falsa ya no será
necesario hallar el valor de verdad de las demás (pues la conjunción de las hipótesis ya es falsa):
p q r H1 : p → r H2 : q → r H1 ∧ H2 H1 ∧ H2 → C C
0 0 0 - - - 1 1
0 0 1 - - - 1 1
0 1 0 1 0 0 1 0
0 1 1 - - - 1 1
1 0 0 0 - 0 1 0
1 0 1 - - - 1 1
1 1 0 0 - 0 1 0
1 1 1 - - - 1 1
Una segunda opción para realizar una demostración directa es mediante una sucesión de
proposiciones, que terminan con la conclusión C, y que se consideran válidas por alguna de las
siguientes razones:
i) Es una de las hipótesis.
ii) Es una tautología conocida.
iii) Es lógicamente equivalente a una proposición anterior.
iv) Se deriva de alguna de las proposiciones anteriores por reglas de sustitución.
v) Se puede inferir de proposiciones anteriores mediante reglas de inferencia.

Área de Álgebra
Las reglas de inferencia son técnicas que nos ayudan en las demostraciones de los teoremas.
Cada regla de inferencia tiene su origen en una implicación lógica.
Ejemplo 20. Utilizando reglas de inferencia, probaremos cómo de las hipótesis “Si no llueve o
no hay niebla, entonces se celebrará la competición de barcos y se hará una demostración de los
salvavidas”, “Si se celebra la competición de barcos, se entregará un trofeo” y “El trofeo no se
entregó” se deduce que “Llovió”.
En primer lugar, consideramos las proposiciones primitivas siguientes:
p: “Llueve”; n: “Hay niebla”; b: “Se celebra competición de barcos”;
s: “Se hace demostración de salvavidas”; t: “Se entrega un trofeo”.
Las hipótesis y la conclusión del argumento dado son:

H1 : ¬p ∨ ¬n → b ∧ s
H2 : b → t
H3 : ¬t
C: p
Teniendo presente que el objetivo es deducir p, aplicamos reglas de inferencia de la forma
siguiente:
(1) ¬p ∨ ¬n → b ∧ s es una hipótesis
(2) b → t es una hipótesis
(3) ¬t es una hipótesis
(4) ¬b aplicando Modus Tollens a (2) y (3)
(5) ¬b ∨ ¬s aplicando ley de adición a (4)
(6) ¬(b ∧ s) aplicando ley de De Morgan a (5)
(7) ¬(¬p ∨ ¬n) aplicando Modus Tollens a (1) y (6)
(8) p ∧ n aplicando las leyes de De Morgan y la doble negación a (7)
(9) p aplicando la ley de simplificación a (8)
Un tipo de demostración indirecta es la contraposición. Este tipo de demostración está
basada en la equivalencia (p → q) ≡ (¬q → ¬p). En nuestro caso, demostrar
H1 ∧ H2 ∧ · · · ∧ Hn |= C
equivale a demostrar que
¬C |= ¬(H1 ∧ H2 ∧ · · · ∧ Hn ), esto es, ¬C |= ¬H1 ∨ ¬H2 ∨ · · · ∨ ¬Hn
Ejemplo 21. Si a y b son números naturales y a + b ≥ 25, entonces a ≥ 13 o b ≥ 13.

Consideramos las proposiciones primitivas:
p : a ≥ 13 q : b ≥ 13 r : a + b ≥ 25
Queremos demostrar que r |= p ∨ q. Para ello veremos que ¬(p ∨ q) |= ¬r . Tengamos en

Área de Álgebra
cuenta que, por las leyes de De Morgan,
¬(p ∨ q) ≡ (¬p ∧ ¬q).
Ahora bien, si a ≤ 12 (¬p) y b ≤ 12 (¬q), entonces a + b ≤ 24, es decir, la proposición r es

falsa, entonces r |= p ∨ q.
Otro tipo de demostración indirecta es la demostración por contradicción o reducción al

absurdo, que consiste en probar que:
H1 ∧ H2 ∧ · · · ∧ Hn ∧ ¬C |= ⊥
Hay que tener en cuenta que el argumento H1 ∧ H2 ∧ . . . ∧ Hn |= C es válido si, y solo, si

H1 ∧ H2 ∧ · · · ∧ Hn → C es una tautología
es decir, que su negación
H1 ∧ H2 ∧ · · · ∧ Hn ∧ ¬C es una contradicción3
o que {H1 , H2 , . . . , Hn , ¬C} es un conjunto inconsistente.
El argumento {H1 , H2 , . . . , Hn } |= C es válido si, y solo si,

el conjunto {H1 , H2 , . . . , Hn , ¬C} es inconsistente.
Este método de demostración por contradicción o reducción al absurdo nos permite utilizar las
tablas semánticas para comprobar si un argumento es o no válido. Si queremos demostrar, o refutar,
un argumento H1 ∧ H2 ∧ · · · ∧ Hn |= C calculamos la tabla semántica de H1 ∧ H2 ∧ · · · ∧ Hn ∧ ¬C. Si,
al finalizar, todos los caminos se cierran, tenemos que H1 ∧ H2 ∧ · · · ∧ Hn ∧ ¬C es una contradicción,
es decir, el argumento H1 ∧ H2 ∧ · · · ∧ Hn |= C es válido. Por el contrario, la existencia de una rama
abierta en el árbol de H1 ∧ H2 ∧ · · · ∧ Hn ∧ ¬C nos da un modelo de H1 ∧ H2 ∧ · · · ∧ Hn ∧ ¬C, es decir,
un contraejemplo de H1 ∧ H2 ∧ · · · ∧ Hn → C y nos indica que el argumento H1 ∧ H2 ∧ · · · ∧ Hn |= C
no es válido.
Ejemplo 22. i) Demostrar el “modus tollens”, ((p → q) ∧ ¬q) |= ¬p, equivale a probar que
el conjunto {p → q, ¬q, ¬¬p} es inconsistente, es decir, que todas las ramas de la tabla
semántica de (p → q) ∧ ¬q ∧ p se cierran.
p→q
¬q
¬p q
∗ ∗
Área de Álgebra
ii) Si llueve o hace viento, Manuel no corta el césped. Siempre que no hay nubes en el cielo, no
llueve. Hoy no hace viento y no hay nubes en cielo. Entonces, Manuel corta el césped.
Llamemos:
3
Téngase en cuenta que, al aplicar la segunda ley de la implicación, se obtiene que
¬(H1 ∧ H2 ∧ · · · ∧ Hn → C) ≡ H1 ∧ H2 ∧ · · · ∧ Hn ∧ ¬C.
p: “Llueve” n: “Hay nubes en el cielo”

q: “Hace viento” c: “Manuel corta el césped”
Se trata de ver si, del conjunto de hipótesis {(p ∨ q) → ¬c, ¬n → ¬p, ¬q, ¬n} se puede
deducir c, es decir, queremos comprobar si
{p ∨ q → ¬c, ¬n → ¬p, ¬q, ¬n} |= c es un argumento válido.
Haciendo una demostración por reducción al absurdo, tendremos que ver si

(p ∨ q → ¬c) ∧ (¬n → ¬p) ∧ ¬q ∧ ¬n ∧ ¬c es una contradicción.
Para ello construimos el árbol semántico de la proposición
(p ∨ q → ¬c) ∧ (¬n → ¬p) ∧ ¬q ∧ ¬n ∧ ¬c
¬q
¬n
Donde hemos utilizado que:
n∗ ¬p
¬n → ¬p ≡ n ∨ ¬p
¬p ¬c p ∨ q → ¬c ≡ (¬p ∧ ¬q) ∨ ¬c
¬q ¬c
¬c
Como vemos, {¬p, ¬q, ¬n, ¬c} es un modelo de H1 ∧ H2 ∧ H3 ∧ H4 ∧ ¬C, donde

H1 : p ∨ q → ¬c, H2 : ¬n → ¬p, H3 : ¬q, H4 : ¬n, C : c,
por lo que es un contraejemplo de su negación ¬(H1 ∧ H2 ∧ H3 ∧ H4 ∧ ¬C), es decir, de
H1 ∧ H2 ∧ H3 ∧ H4 −→ C. Se obtiene así un contraejemplo del argumento dado y se concluye
Área de Álgebra
que este no es válido.
Las principales ventajas de las tablas semánticas respecto a las tablas de verdad son:
i) Son menos costosas de aplicar.
ii) Constituyen una buena base para programar demostradores automáticos.
iii) Pueden extenderse a otras lógicas, para las cuales el método de las tablas de verdad deja de
tener sentido.
iv) En el caso de que el argumento no sea válido las tablas semánticas nos muestran explícita-
mente un contraejemplo.
1.2 Formas normales

1.2.1 Forma normal disyuntiva y Forma normal conjuntiva
Definición 9. Un literal es un símbolo proposicional (literal positivo: p) o su negación (literal
negativo: ¬p).
Dado un literal l, su literal complementario l c se define como:

c p si l = ¬p
l =
¬p si l = p
Un par de literales complementarios es cualquier conjunto {l, l c } siendo l un literal cualquiera.
Definición 10. Una fórmula está en forma normal conjuntiva (FNC)4 cuando es una conjunción
de disyunciones de literales.
Definición 11. Una fórmula está en forma normal disyuntiva (FND)5 cuando es una disyunción
de conjunciones de literales.
Ejemplo 23. (p ∨ ¬q) ∧ (¬p ∨ r ) está en forma normal conjuntiva y (q ∧ ¬r ) ∨ (p ∧ r ) en forma

normal disyuntiva.
Teorema 1. Toda fórmula proposicional es equivalente a una fórmula en forma normal conjuntiva
y a una fórmula en forma normal disyuntiva.
Demostración. Para pasar una fórmula a forma normal conjuntiva aplicaremos:
i) Traducir → y ↔ en términos de ∨, ∧ y ¬, es decir:
p → q ≡ ¬p ∨ q, p ↔ q ≡ (¬p ∨ q) ∧ (¬q ∨ p) y/o p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
Nótese que ¬p ∨ q es una FND y una FNC de p → q. Por otro lado, con respecto a p ↔ q,
tenemos que (¬p ∨ q) ∧ (¬q ∨ p) es una FNC y (p ∧ q) ∨ (¬p ∧ ¬q) es una FND.
Área de Álgebra
ii) Trasladar las negaciones hasta que aparezcan asociadas a literales (usando las leyes de De
Morgan)
iii) Eliminar dobles negaciones (usando ¬¬p ≡ p)
iv) Aplicar la distributividad de ∨ respecto de ∧ hasta obtener una fórmula en forma normal
conjuntiva
4
En inglés conjuctive normal form (CNF)
5
En inglés disjunctive normal form (DNF)
1.2. FORMAS NORMALES 19
Para obtener una forma normal disyuntiva aplicaremos los pasos anteriores utilizando en el
último paso la distributividad de ∧ respecto de ∨:
Ejemplo 24. Calculemos una FNC de ¬(p ∧ (q → r )).
¬(p ∧ (q → r )) ≡ ¬(p ∧ (¬q ∨ r )) Ley de la implicación

≡ ¬p ∨ ¬(¬q ∨ r ) Leyes de Morgan
≡ ¬p ∨ (¬¬q ∧ ¬r ) Leyes de Morgan
≡ ¬p ∨ (q ∧ ¬r ) Ley doble negación
≡ (¬p ∨ q) ∧ (¬p ∨ ¬r ) Leyes distributivas
Nótese que también hemos obtenido una FND que es ¬p ∨ (q ∧ ¬r )
Ejemplo 25. Calculemos una FNC de (p ↔ q) → r .
(p ↔ q) → r ≡ [(p ∧ q) ∨ (¬p ∧ ¬q)] → r Ley de la equivalencia

≡ ¬[(p ∧ q) ∨ (¬p ∧ ¬q)] ∨ r Ley de la implicación
≡ [¬(p ∧ q) ∧ ¬(¬p ∧ ¬q)] ∨ r Leyes de Morgan
≡ [(¬p ∨ ¬q) ∧ (¬¬p ∨ ¬¬q)] ∨ r Leyes de Morgan
≡ [(¬p ∨ ¬q) ∧ (p ∨ q)] ∨ r Ley de la doble negación
≡ (¬p ∨ ¬q ∨ r ) ∧ (p ∨ q ∨ r ) Leyes distributivas
Para obtener una FND:
(p ↔ q) → r ≡ [(¬p ∨ q) ∧ (¬q ∨ p)] → r Ley de la equivalencia

≡ ¬[(¬p ∨ q) ∧ (¬q ∨ p)] ∨ r Ley de la implicación
≡ [¬(¬p ∨ q) ∨ ¬(¬q ∨ p)] ∨ r Leyes de Morgan
≡ [(¬¬p ∧ ¬q) ∨ (¬¬q ∧ ¬p)] ∨ r Leyes de Morgan
≡ (p ∧ ¬q) ∨ (q ∧ ¬p) ∨ r Ley de la doble negación
1.2.2 Calculo de la forma normal disyuntiva y conjuntiva mediante tablas

semánticas
Área de Álgebra
• Si F es una fórmula y {L1,1 , . . . , L1,n1 }, . . . , {Lm,1 , . . . , Lm,nm } son las ramas abiertas en una
tabla semántica de F , entonces:
(L1,1 ∧ · · · ∧ L1,n1 ) ∨ · · · ∨ (Lm,1 ∧ · · · ∧ Lm,nm )
es una forma normal disyuntiva de F .

Nótese que, si no quedasen ramas abiertas en la tabla de F , entonces F sería una contradic-
ción.
• Si F es una fórmula y {L1,1 , . . . , L1,n1 }, . . . , {Lm,1 , . . . , Lm,nm } son las ramas abiertas en una
tabla semántica de ¬F , entonces:
Lc1,1 ∨ · · · ∨ Lc1,n1 ∧ · · · ∧ Lcm,1 ∨ · · · ∨ Lcm,nm

es una forma normal conjuntiva de F .6

Nótese que, si no quedasen ramas abiertas en la tabla de ¬F , entonces F sería una tautología.
Ejemplo 26.
• Puesto que las ramas abiertas en una tabla semántica de F = ¬(p ∨ q → p ∧ q) son {p, ¬q}
y {q, ¬p}, podemos decir que una FND de F es (p ∧ ¬q) ∨ (q ∧ ¬p)
¬(p ∨ q → p ∧ q) ≡ (p ∨ q) ∧ ¬(p ∧ q) ✓
p∨q ✓
¬(p ∧ q) ≡ ¬p ∨ ¬q ✓
p q
¬p ¬q ¬p ¬q
∗ ∗
• Una FNC de p ∨ q → p ∧ q es (¬p ∨ q) ∧ (¬q ∨ p)
• En el ejemplo 22 vimos que la tabla semántica de F : (p → q) ∧ ¬q ∧ p solo contenía caminos

cerrados. Teniendo en cuenta que
F ≡ ¬[(p → q) ∧ ¬q → ¬p],
podemos concluir que (p → q) ∧ ¬q → ¬p es una tautología ( Modus Tollens).

Área de Álgebra
1.2.3 Decisión de tautología mediante una forma normal conjuntiva

• Si F1 , F2 , . . . , Fn son fórmulas, sabemos que F1 ∧ F2 ∧ · · · ∧ Fn es una tautología si, y solo
si, Fi es una tautología, para todo i .
• Si L1 , L2 , . . . , Ln son literales, L1 ∨L2 ∨· · ·∨Ln es una tautología si, y solo si, {L1 , L2 , . . . , Ln }
contiene algún par de literales complementarios (es decir, existen i, j tales que Lci = Lj ).
Dadas dos fórmulas F y G, G es una forma normal conjuntiva (respectivamente disyuntiva) de F si, y solo si, ¬G
6
es una forma normal disyuntiva (respectivamente conjuntiva) de ¬F

1.2. FORMAS NORMALES 21
Hay que tener en cuenta que, si {L1 , L2 , . . . , Ln } no contiene ningún par de literales complemen-
tarios, podemos definir una interpretación v :
0 si p ∈ {L1 , L2 , . . . , Ln }

v (p) =
1 si ¬p ∈ {L1 , L2 , . . . , Ln }
v puede tomar cualquier valor en aquellos átomos q tales que q y ¬q no pertenecen a {L1 , L2 , . . . , Ln }.
Se puede probar que v es un contraejemplo de L1 ∨ L2 ∨ · · · ∨ Ln .
Para determinar si una fórmula P es una tautología, podemos utilizar su FNC:
• Calculamos una FNC de P: F1 ∧ F2 ∧ · · · ∧ Fn
• Analizamos si cada Fi (que es una disyunción de literales) es o no una tautología.
Ejemplo 27. Anteriormente hemos visto que una FNC de ¬(p ∧ (q → r )) es (¬p ∨ q) ∧ (¬p ∨
¬r ). A continuación, observamos que (¬p ∨ q) y (¬p ∨ ¬r ) no contienen ningún par de literales
complementarios por lo que ninguna de ellas es una tautología. Además las interpretaciones v1 (p) =
1, v1 (q) = 0 y v2 (p) = v2 (r ) = 1 7 son ambas contraejemplos de la fórmula ¬(p ∧ (q → r )).
Ejemplo 28. La fórmula (p → q) ∨ (q → p) es una tautología ya que:
(p → q) ∨ (q → p) ≡ (¬p ∨ q) ∨ (¬q ∨ p) Ley de la implicación

≡ (¬p ∨ p ∨ ¬q ∨ q)
1.2.4 Decisión de satisfacibilidad mediante forma normal disyuntiva

• Si F1 , F2 , . . . , Fn son fórmulas, sabemos que F1 ∨ F2 ∨ · · · ∨ Fn es satisfacible si, y solo si,
alguna de las fórmulas Fi lo es.
• Si L1 , L2 , . . . , Ln son literales, L1 ∧ L2 ∧ · · · ∧ Ln es satisfacible si, y solo si, {L1 , L2 , . . . , Ln }

no contiene ningún par de literales complementarios.
Hay que tener en cuenta que, si {L1 , L2 , . . . , Ln } no contiene ningún par de literales complemen-
tarios, podemos definir una interpretación v :
Área de Álgebra
1 si p ∈ {L1 , L2 , . . . , Ln }

v (p) =
0 si ¬p ∈ {L1 , L2 , . . . , Ln }
v puede tomar cualquier valor en aquellos átomos q tales que q y ¬q no pertenecen a {L1 , L2 , . . . , Ln }.
Se puede probar que v es un modelo de L1 ∧ L2 ∧ · · · ∧ Ln .
Para determinar si una fórmula P es satisfacible podemos utilizar su FND:
• Calculamos una FND de P: F1 ∨ F2 ∨ · · · ∨ Fn
• Analizamos si alguna Fi (que es una conjunción de literales) es o no satisfacible.

7
En los demás átomos v1 (respectivamente v2 ) pueden tomar cualquier valor.
Ejemplo 29. Anteriormente hemos visto que una FND de ¬(p ∧ (q → r )) es ¬p ∨ (q ∧ ¬r ). Puesto
que ¬p y q ∧¬r no contienen ningún par de literales complementarios, ambas son satisfacibles. Las
interpretaciones v1 (p) = 0 y v2 (q) = 1, v2 (r ) = 08 son ambas modelos de la fórmula ¬(p∧(q → r )).
Ejemplo 30. Veamos que la fórmula ¬[p → (q → p)] es insatisfacible. Para ello, calculamos
primero una FND:
¬[p → (q → p)] ≡ p ∧ ¬(q → p)] Ley de la implicación

≡ p ∧ q ∧ ¬p Ley de la implicación
Puesto que la conjunción obtenida contiene un par de literales complementarios, es insatisfacible
y, en consecuencia, la fórmula ¬[p → (q → p)] también lo es.
1.3 Lógica de Predicados

Como hemos comentado al inicio del tema, un enunciado del tipo “x + 2 es un número par ” no es
una proposición porque no es ni verdadero ni falso si no se especifican los valores de la variable.
Por ejemplo, si x = 1, entonces el enunciado es falso; mientras que si x = 2, el enunciado es
verdadero.
Este sería un ejemplo de predicado (afirmación que expresa una propiedad de un objeto o una
relación entre objetos) y su valor de verdad depende del valor que tome una variable (o varias
variables) en un cierto conjunto llamado dominio o universo. Por ejemplo, si consideramos el
predicado Q(x, y ) : x + y = 5 en el universo de los números enteros positivos, Q(x, y ) se
convierte en una proposición verdadera cuando asignamos los valores x = 1, y = 4; x = 2, y = 3;
x = 3, y = 2; o bien x = 4, y = 1 a las variables x e y ; Q(x, y ) es una proposición falsa en los
demás casos.
De hecho, un predicado se transforma en una proposición sustituyendo todas las variables por
los elementos del dominio o utilizando cuantificadores. A continuación veremos el cuantificador
universal y el cuantificador existencial.
El cuantificador universal “∀” se utiliza para construir proposiciones del tipo siguiente:
Área de Álgebra
• ∀x p(x)
Se lee “para todo x, p(x)”, o bien, “para cada x, p(x)”, o bien, “para cualquier x, p(x)”.
Este tipo de proposición es verdadera cuando p(a) es verdadera para cualquier valor a del
dominio U, y es falsa si p(a) es falsa para algún valor de U.
Por ejemplo: “Todos los alumnos de esta Facultad tienen más de 16 años”, es una proposición
verdadera. “Todos los alumnos de esta Facultad nacieron en Coruña” es una proposición falsa.
El cuantificador existencial “∃” se utiliza para proposiciones del tipo siguiente:

8
En los demás átomos v1 (respectivamente v2 ) pueden tomar cualquier valor.
1.3. LÓGICA DE PREDICADOS 23
• ∃x p(x)
Se lee “existe x que verifica p(x)” o, también, “para algún x se cumple p(x)”
Esta proposición es verdadera cuando p(a) es verdadera para, al menos, un valor a de U. Es
falsa cuando, para todo valor a de U, la proposición p(a) es falsa.
Por ejemplo: “Existe un entero x que sumado con 1 nos da 0” es verdadera. “Existe un entero
x que sumado con 1 nos da x” es una proposición falsa.
Las leyes de De Morgan generalizadas son ciertas cualquiera que sea el universo del discurso
y cualquiera que sea el valor de las proposiciones. Son las siguientes:
¬ [∀x p(x)] ≡ ∃x ¬p(x) ¬ [∃x p(x)] ≡ ∀x ¬p(x)
Ejemplo 31. Escribamos la negación de la siguiente proposición cuantificada:
∀x ∃y [p(x) ∧ ¬q(x) → r (x, y )]

Aplicando las reglas anteriores, tenemos:
¬ [∀x ∃y p(x) ∧ ¬q(x) → r (x, y )]

≡ ∃x ¬ [∃y p(x) ∧ ¬q(x) → r (x, y )]
≡ ∃x ∀y ¬ [p(x) ∧ ¬q(x) → r (x, y )]
≡ ∃x ∀y ¬ [¬(p(x) ∧ ¬q(x)) ∨ r (x, y )]
≡ ∃x ∀y [p(x) ∧ ¬q(x) ∧ ¬r (x, y )]
Ejemplo 32. Consideremos los predicados A(x): “x es estudiante de informática” y B(x): “x tiene
un ordenador” en el universo de los estudiantes de la universidad de A Coruña.
La frase “todos los estudiantes de informática tienen ordenador” se formaliza como:
∀x (A(x) → B(x))
Área de Álgebra
mientras que la frase “algún estudiante de informática tiene ordenador” se formaliza como:
∃x (A(x) ∧ B(x))
1.3.1 Argumentos en lógica de predicados

Formalicemos el siguiente argumento: “Todo el que tiene los ojos azules no es moreno. Pepe tiene
los ojos azules. Entonces Pepe no es moreno”. Sobre el universo de los humanos construimos los
siguientes predicados:
A(x): “x tiene los ojos azules” M(x): “x es moreno”

En este argumento, las premisas o hipótesis son ∀x [A(x) → ¬M(x)] y A(P epe); mientras que
la conclusión es ¬M(P epe).
Para demostrar argumentos expresados en lógica de predicados, se utilizan las reglas siguientes:
i) Especificación universal (EU)

Si la proposición ∀x F (x) es verdadera, entonces se puede deducir que la proposición F (a)
es verdadera para cualquier elemento a del universo del dominio. Esta regla la podemos
representar en las tablas semánticas de la forma
∀ x F (x) Donde F (a) significa sustituir simultáneamente cada aparición de x

en F por la constante a.
F (a)
ii) Generalización universal

Si la proposición F (a) es verdadera para cualquier elemento a del universo del discurso,
entonces se concluye que ∀x F (x) es verdadera.
iii) Especificación existencial (EE)

Si la proposición ∃x F (x) es verdadera, entonces existe un elemento a en el universo del
discurso tal que F (a) es verdadera. Esta regla la podemos representar en las tablas semánticas
de la forma:
Con a en el universo U y distinto de todos los nombres

∃x F (x) ✓
pertenecientes a U que aparecen en la misma rama donde va a
estar F (a).
F (a)
iv) Generalización existencial Si F (a) es verdadera para algún elemento a del universo del
discurso, entonces la proposición ∃x F (x) es verdadera.
Área de Álgebra
Debe notarse que en la especificación universal no se marca como utilizada la fórmula, puesto
que se puede volver a utilizar. La justificación es que si la sentencia ∀x F (x) es parte de un
conjunto consistente, añadir uno o más casos de F al conjunto no cambiaría ese carácter. Sin
embargo, en la especificación existencial sí se marca la fórmula al ser utilizada (con el símbolo ✓)
y tiene como restricción que el nombre de la variable debe ser nuevo en cada rama. Ello garantiza
que el nombre está escogido en forma completamente arbitraria del contexto, lo que concuerda
con la semántica: se conoce que es verdad al menos en un caso, aunque no sepamos en cuál.
Por lo tanto, se debe aplicar la Especificación existencial antes de utilizar la Especificación
universal. Es decir, mientras que en el cálculo proposicional no importa el orden de aparición de
las reglas para probar que un conjunto es inconsistente, en el cálculo de predicados sí influye.
Ejemplo 33. Demostrar el argumento dado al inicio de la sección,
{∀x (A(x) → ¬M(x)), A(P epe)} |= ¬M(P epe),
equivale a probar que el conjunto {∀x (A(x) → ¬M(x)), A(P epe), ¬¬M(P epe)} es inconsistente.
Para ello construimos una tabla semántica de
∀x (A(x) → ¬M(x)) ∧ A(P epe) ∧ M(P epe)
y veamos que todas las ramas se cierran:
(1) (∀x [A(x) → ¬M(x)]) ∧ A(P epe) (premisas)
(2) ¬(¬M(P epe)) (¬ conclusión)
(3) A(P epe) ✓ (de 1)
(4) ∀x [A(x) → ¬M(x)] (de 1)
(5) A(P epe) → ¬M(P epe) ✓ (de 4 y EU)
(6) ¬A(P epe) ∗ ¬M(P epe)∗ (de 5)
Ejemplo 34. Consideremos el argumento: “Todo el mundo grita o llora. No todo el mundo llora.
Así que algunas personas gritan y no lloran”. Para formalizarlo definimos, sobre el universo de los
humanos, los predicados
Área de Álgebra
G(x): “x grita” L(x): “x llora”
Las premisas del argumento son ∀x [G(x) ∨ L(x)] y ¬∀x L(x); mientras que la conclusión es
∃x [G(x) ∧ ¬L(x)].
Para comprobar que el argumento {∀x [G(x) ∨ L(x)], ¬∀x L(x)} |= ∃x [G(x) ∧ ¬L(x)] es válido,
comprobamos que se cierran todas las ramas de la tabla semántica de:
∀x [G(x) ∨ L(x)] ∧ ¬∀x L(x) ∧ ¬ ∃x [G(x) ∧ ¬L(x)]

(1) (∀x [G(x) ∨ L(x)]) ∧ ¬∀x L(x) (premisas)
(2) ¬(∃x [G(x) ∧ ¬L(x)] ≡ ∀x [¬G(x) ∨ L(x)] (¬ conclusión)
(3) ¬∀x L(x) ≡ ∃x ¬L(x) ✓ (de 1)
(4) ¬L(c) (de 3 y EE)
(5) ∀x [G(x) ∨ L(x)] (de 1)
(6) G(c) ∨ L(c) ✓ (de 5 y EU)
(7) G(c) L(c) (de 6)

∗
(8) ¬G(c) ∨ L(c) ✓ (de 2 y EU)
(9) ¬G(c) ¬(¬L(c)) (de 8)

∗ ∗
Es importante destacar que es necesario usar la Especificación existencial en la segunda premisa
(paso (3) a (4)) antes de utilizar la Especificación universal en la primera premisa (paso (5) a (6)).
En el ejemplo siguiente vemos que no se puede intercambiar este orden; es decir, siempre hay
que utilizar las especificaciones existenciales antes que las universales.
Ejemplo 35. Consideremos el argumento “Algunos poetas fueron románticos. Algunos románticos
se suicidaron. Por lo tanto, algunos poetas se suicidaron”. Si definimos, sobre el universo de los
humanos, los predicados siguientes:
P (x): “x es poeta” R(x): “x es romántico” S(x): “x se suicida”,
el argumento dado es: [∃x (P (x) ∧ R(x))] ∧ [∃x (R(x) ∧ S(x))] |= [∃x (P (x) ∧ S(x))].
Área de Álgebra
Teniendo en cuenta que ¬[∃x (P (x) ∧ S(x))] ≡ ∀x (¬P (x) ∨ ¬S(x)), si representamos
{P (x) ∧ R(x), R(x) ∧ S(x), ¬P (x) ∨ ¬S(x)}
se tiene que
P (x)
R(x)
R(x)
S(x)
¬P (x) ¬S(x)
∗ ∗
Obviamente, esta representación no es correcta (nos hemos olvidado de los cuantificadores y
hemos representado los predicados para una variable arbitraria x).
Hagamos la tabla semántica de forma correcta y veamos que el argumento no es válido. La
tabla comienza de la forma siguiente
(1) ∃x (P (x) ∧ R(x)) (premisa)
(2) ∃x (R(x) ∧ S(x)) (premisa)
(3) ¬[∃x (P (x) ∧ S(x))] (¬ conclusión)
Para continuar, haremos primero la especificación existencial de (1)
∃x (P (x) ∧ R(x)) ✓
P (a) ∧ R(a) ✓
P (a)
R(a)
Área de Álgebra
Continuamos con la especificación existencial de (2)
∃x (R(x) ∧ S(x)) ✓
R(b) ∧ S(b) ✓
R(b)
S(b)
y, por último, aplicando la especificación universal de (3) a cada una de las variables, teniendo en
cuenta que ¬[∃x (P (x) ∧ S(x))] ≡ ∀x [¬P (x) ∨ ¬S(x)], se obtiene la tabla siguiente:
P (a) ∧ R(a) ✓
P (a)
R(a)
R(b) ∧ S(b) ✓
R(b)
S(b)
¬P (a) ∨ ¬S(a)
¬P (a) ¬S(a)
∗
¬P (b) ∨ ¬S(b)✓
¬P (b) ¬S(b) ∗
De la tabla semántica anterior, se deduce que el argumento no es válido y un contraejemplo se

obtiene siguiendo la rama que queda abierta: así a es un poeta romántico que no se suicidó (pues
en dicha rama aparecen P (a), R(a) y ¬S(a)) y b es un romántico que se suicida y que no es poeta
(¬P (b), R(b) y S(b)).
1.3.2 Demostración por inducción

Un predicado básico en muchas teorías es la igualdad “=”, que verifica dos axiomas
Área de Álgebra
y ∀x ∀y (x = y ) ∧ P (x) → P (y ) .

∀x (x = x)
Además, en los números naturales, existe una regla de demostración específica, conocida como
Principio de inducción: {P (1), ∀x (P (x) → P (x + 1))} |= ∀x P (x). Este principio se basa en una
característica fundamental de los números naturales: que cualquiera de ellos puede ser obtenido a
partir del uno mediante una suma reiterada de este.
Es decir, para demostrar, en el universo N de los números naturales, que ∀n P (n) es una
proposición verdadera, usamos el principio de inducción que se enuncia del siguiente modo: Si
• (Base inductiva) P (1) es cierta, y
• (Paso inductivo) ∀k (P (k) |= P (k + 1))

entonces, ∀n P (n) es una proposición verdadera.

Por lo tanto, si P (1) es verdadera y, además se cumple que la propiedad P se transmite de
cualquier número natural k a su sucesor, k + 1, entonces todos los números naturales satisfacen
la propiedad P .
Hay muchos tipos de imágenes gráficas que pueden ayudar a comprender el principio anterior.
Por ejemplo, usando fichas de dominó. Si las colocamos en fila una tras otra, de tal modo que
si una ficha cae empuja, y hace caer, a la siguiente (paso inductivo) y tiramos la primera (base
inductiva), todas las fichas caerán. Hay que tener en cuenta que una sola de estas condiciones no
es suficiente para que todas las fichas caigan.
Ejemplo 36.
n
X n(n+1)
i) Para todo natural n, se verifica que 1 + 2 + · · · + n = i= 2 .
i=1
1(1 + 1)
• Base inductiva n = 1: 1 =
2
• Paso inductivo: Sea k ∈ N cualquiera y supongamos que el resultado es cierto para k,
k
X k(k + 1)
i = 1 + 2 + ··· + k = ,
i=1
2
y comprobemos si se cumple para k + 1

k+1
X
i = 1 + 2 + · · · + k + (k + 1)
i=1
k(k + 1) k(k + 1) + 2(k + 1) (k + 1)(k + 2)
= + (k + 1) = =
2 2 2
Pn
ii) Probar que para todo natural n, se verifica que 1 + 2 + · · · + 2n = i=0 2i = 2n+1 − 1.
• Base inductiva n = 1: 1 + 2 = 21+1 − 1
Área de Álgebra
• Paso inductivo: Sea k ∈ N cualquiera y supongamos que el resultado es cierto para k,
k
X
2i = 1 + 2 + · · · + 2k = 2k+1 − 1,
i=0
y comprobemos si se cumple para k + 1

k+1 k
!
X X
2i = 2i + 2k+1 = 1 + 2 + · · · + 2k + 2k+1

i=0 i=0
k+1
− 1 + 2k+1 = 2 · 2k+1 − 1 = 2(k+1)+1 − 1

= 2
En ocasiones, para facilitar la demostración, debemos aplicar el llamado principio de inducción

fuerte o completa, que es equivalente al anterior, y que se enuncia como sigue:
Sea P una propiedad definida sobre los naturales tal que
• (Base inductiva) P (1) es cierta, y
• (Paso inductivo completo) para todo natural k se cumple que
{P (1), P (2), . . . , P (k)} |= P (k + 1)
entonces, ∀n P (n) es una proposición verdadera.
Ejemplo 37. Después de transcurrir n meses en un experimento de invernadero, el número pn de
plantas de un tipo particular satisface que p1 = 3, p2 = 7 y
pn = 3pn−1 − 2pn−2
para todo n ≥ 3. Probemos que pn = 2n+1 − 1.
En primer lugar, es claro que para los casos n = 1, 2 se verifica. Además si n ≥ 3 y, se supone
que para todo 1 ≤ k ≤ n se verifica la hipótesis, entonces
pn+1 = 3pn − 2pn−1 = 3(2n+1 − 1) − 2(2n − 1) = 3 · 2n+1 − 2n+1 − 1 = 2n+2 − 1.
con lo que queda probado.
Los principios de inducción simple y fuerte son válidos también para demostrar que una propiedad
es cierta para todos los números enteros mayores que un entero dado n0 , en este caso sin más que
cambiar el universo N por
U = {n ∈ Z | n ≥ n0 }.
Nota 1. Es interesante destacar que tanto la base inductiva como el paso inductivo son necesarios
ya que, en ausencia de alguno de ellos el principio de inducción no es cierto.
Ejemplo 38. Para cada n, sea P (n) la propiedad que afirma que
n 2
X n + 12
i=
i=1
2
Es fácil comprobar que si P (k) es cierta, entonces también es cierta P (k + 1):
Área de Álgebra
k+1 k 2 2
X X k + 21 k + 1 + 21
i= i + (k + 1) = + (k + 1) = .
i=1 i=1
2 2
Es decir, esta propiedad verifica el paso inductivo y parecería que es cierta para todos los naturales.
Sin embargo, no se cumple para n = 1
2
1 + 12
1 ̸= .
2
De hecho, no es cierta para ningún natural n ya que
n 2
X n (n + 1) n (n + 1) n + 12
i= , pero ̸= .
i=1
2 2 2

Teoria Tema 1 GCED

Cargado por

Copyright:

Formatos disponibles

Teoria Tema 1 GCED

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Teoria Tema 1 GCED

Cargado por

Copyright:

Formatos disponibles

GCED.

• R.P. Grimaldi, Matemática Discreta y combinatoria (3 ed.): capítulo 2 y capítulo 4 (sección

Cuando se plantea qué matemáticas va a necesitar un informático, la primera respuesta es:

1.1 Lógica Proposicional

Ejemplo 1. Los siguientes enunciados son proposiciones:

• Los triángulos tienen cuatro vértices. (0)

Ejemplo 2. Los siguientes enunciados no son proposiciones:

desiderativa, la segunda interrogativa y la tercera es imperativa. La cuarta frase tampoco es

1.1.2 Operadores lógicos. Sintaxis

• Negación (¬) Si p es una proposición, la negación de p se denota por ¬p y se lee:

“no p” “no ocurre p” “no es cierto p”

• Conjunción (∧) Si p y q son proposiciones, la conjunción de p y q se denota por p ∧ q y

“p y q” “p, no obstante q” “p, pero q”

• Disyunción (∨) Si p y q son proposiciones, la disyunción de p y q se denota por p ∨ q y se

“p o q (o ambos)” “al menos p o q” “como mínimo p o q”

• Condicional (→) Si p y q son proposiciones, el condicional p → q se lee:

• Bicondicional (↔) Si p y q son proposiciones, el bicondicional p ↔ q se lee:

“p si, y solo si, q” “p es suficiente y necesario para q”

i) Las proposiciones primitivas o atómicas son f.b.f.

ii) Si P es una f.b.f., ¬P es una f.b.f.

iii) Si P y Q son f.b.f., entonces P ∧ Q, P ∨ Q, P → Q y P ↔ Q son f.b.f.

iv) No hay más reglas.

Ejemplo 3. La expresión p → (¬q) es una f.b.f., mientras que p → (∧q) no lo es.

Ejemplo 4. En la proposición compuesta ¬p ∧ (r → t) no podemos eliminar paréntesis ya que, si

1.1.3 Operadores lógicos. Semántica

• La negación ¬p es verdadera únicamente cuando p es falsa.

• La conjunción p ∧q es verdadera cuando tanto p como q son verdaderas, y falsa en cualquier

• La disyunción p ∨ q es falsa cuando tanto p como q son falsas, y verdadera en cualquier

• El condicional p → q es falso cuando p es verdadera y q es falsa, y verdadero en cualquier

• El bicondicional p ↔ q es verdadero cuando p y q tienen los mismos valores de verdad, y

p ¬p p q p∧q p∨q p→q p↔q

p : “Apruebas Matemática Discreta” q : “Te compro un ordenador”

Se pueden distinguir cuatro casos:

Ejemplo 7. Fijémonos en la diferencia entre el argumento anterior y el siguiente. El padre de Juan

el ordenador. Se cumple la promesa y el valor de verdad de la bicondicional es 1.

Para construirla se determinan los valores de verdad de sus subproposiciones componentes,

Ejemplo 8. La tabla de verdad de (p ∨ q) ∧ (p → ¬q) es:

• p ∨ ¬(p ∧ q) es una tautología. • ¬(p → q) es satisfacible.

• (p ∧ q) ∧ ¬(p ∨ ¬q) es una contradicción. • ¬p → q es una contingencia.

Definición 5. Un conjunto de proposiciones {P1 , P2 , . . . , Pn } se dice que es consistente (o

• El conjunto {p → q, p ∧ ¬q} es inconsistente ya que (p → q) ∧ (p ∧ ¬q) no admite ningún

p q p→q p∧q (p → q) ∧ (p ∧ q) p q p→q p ∧ ¬q (p → q) ∧ (p ∧ ¬q)

1.1.4 Implicaciones y Equivalencias lógicas

p q ¬(p ∧ q) ¬p ∨ ¬q ¬(p ∧ q) ↔ (¬p ∨ ¬q)

Para cualesquiera fórmulas P, Q, R, se verifica que:

Al final de esta sección, la tabla 1.1 recoge algunas equivalencias lógicas.

Ejemplo 15. Para demostrar que (p → q) ∧ p |= q es suficiente probar que la fórmula

Al final de esta sección, la tabla 1.2 recoge algunas implicaciones lógicas.

Principales equivalencias lógicas

Table 1.1: Tabla de equivalencias

Principales implicaciones lógicas

Table 1.2: Tabla de implicaciones

1.1.5 Tablas semánticas

Para comprobar si un conjunto de proposiciones {P1 , P2 , . . . , Pn } es consistente, se construye la

Ejemplo 16. Para comprobar si el conjunto {p → ¬r, ¬q → r, p ∨ ¬q} es o no consistente, se

1.1.6 Argumentos y métodos de demostración

Se puede realizar una demostración directa de la validez de un argumento mediante tablas de

Ejemplo 18. Para demostrar la implicación lógica “Modus Tollens”, es decir,

se prueba que (p → q) ∧ ¬q → ¬p es una tautología: