Ciencias computacionales

Propedeútico: Matemáticas Discretas

Lógica
INAOE

Contenido
1 Introducción 4
1.1 Términos esenciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Proposición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Inferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 Argumento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.4 Premisa-conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 Sintáxis y semática de la lógica proposicional 6

2.1 Fundamentos de lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Conectivas básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Tablas de verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.3 Tautologı́a y contradicción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.4 Precedencia de los operadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.5 Equivalencia lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.6 Leyes de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.7 Reglas de inferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.8 Cuantificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Sintáxis de la lógica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Fórmulas proposicionales (BNF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 Definiciones por recursión sobre fórmulas . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Demostración por inducción sobre fórmulas . . . . . . . . . . . . . . . . . . . . . . 17
2.2.4 Criterio de reducción de paréntesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.5 Subfórmulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Sémantica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Valores y funciones de verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Modelos y satisfacibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Tautologı́as y contradicciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1
 2.3.4 Satisfacibilidad y validéz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.5 Selección de tautologı́as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.6 Fórmulas equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 Modelo de conjuntos de fórmulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.8 Conjunto consistente de fórmulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.9 Consecuencia lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.10 Argumentaciones y problemas lógicos . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Deducción en lógica proposicional 25

3.1 Reglas de deducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Reglas de la conjunción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2 Reglas de la doble negación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.3 Reglas de eliminación del condicional . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.4 Regla derivada de modus tollens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.5 Regla de introducción del condicional . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.6 Reglas de la disyunción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1.7 Reglas de la negación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.8 Regla del bicondicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Reglas derivadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.1 Regla del modus tollens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 Regla de introducción de la doble negación . . . . . . . . . . . . . . . . . . . . . . 31
3.2.3 Regla de reducción al absurdo (RAA) . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.4 Ley del tercio exluido (LEM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4 Sintáxis y semántica de primer orden 32

4.1 Representación del conocimiento en lógica de primer orden . . . . . . . . . . . . . . . . . 32
4.1.1 Limitación expresiva de la lógica proposicional . . . . . . . . . . . . . . . . . . . . 32
4.1.2 Representación del mundo de los bloques . . . . . . . . . . . . . . . . . . . . . . . 33
4.1.3 Representación del mundo de los bloques con funciones e igualdad . . . . . . . . . 33
4.1.4 Representación de conocimiento astronómico . . . . . . . . . . . . . . . . . . . . . 34
4.2 Sintaxis de la lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.1 Lenguaje de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.2 Términos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2.3 Fórmulas atómicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2.4 Subfórmulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.5 Criterios de reducción de paréntesis . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.6 Conjuntos de variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.7 Variables libres y ligadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2.8 Fórmulas cerradas y abiertas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Semántica de la lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3.1 Estructuras, asignaciones e interpretaciones . . . . . . . . . . . . . . . . . . . . . . 40
4.3.2 Evaluación de términos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3.3 Evaluación de fórmulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3.4 Conceptos auxilares para la evaluación de fórmulas . . . . . . . . . . . . . . . . . . 42
4.3.5 Evaluación y variables libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.6 Modelo de una fórmula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.7 Satisfacibilidad y validez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3.8 Modelo de un conjunto de fórmulas . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.9 Consistencia de un conjunto de fórmulas . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.10 Consecuencia lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.11 Consecuencia lógica e inconsistencia . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.12 Equivalencia lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

2
5 Formas normales 46
5.1 Forma normal conjuntiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.1.1 Definición de forma normal conjuntiva . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.2 Forma normal disyuntiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2.1 Definición de forma normal disyuntiva . . . . . . . . . . . . . . . . . . . . . . . . . 47

3
 Material multimedia recomendado:

• [Link]
• [Link]
• [Link]
• [Link]
• [Link]

1 Introducción
¿Qué es la lógica?

• La ciencia del razonamiento. Gracias al razonamiento se resuelve un problema, a través de un

proceso que extrae conclusiones a partir de premisas. Este proceso es extremandamente complejo,
emotivo, compuesto de un ciclo de prueba-error, ”iluminado” por momentos de comprensión o
intuición.
• Es el estudio de los métodos y principios que se usan para distinguir el razonamiento bueno (correcto)
del malo (incorrecto).
– ¿Un arte o una ciencia?
∗ La práctica llevará al perfeccionamiento
∗ Análisis de las falacias
∗ Errores frecuentes del razonamiento

En lógica se plantean preguntas como ¿tiene solución el problema? o ¿Se sigue la conclusión de las
permisas que se han afirmado o supuesto?. Si el problema queda resuelto, si las premisas proporcionan
las bases adecuadas para afirmar la verdad de la conclusión, entonces el razonamiento es correcto. De lo
contrario es incorrecto.
La distinción entre razonamiento correcto e incorrecto es el problema central con el que
trata la lógica

1.1 Términos esenciales

1.1.1 Proposición
Proposición es el contenido de una oración el cual puede ser verdadero o falso. Difieren de las preguntas,
órdenes y exclamaciones debido a que éstas no pueden ser verdaderas o falsas.
Dos oraciones pueden emplearse para afirmar la misma proposición, por ejemplo:

• Juan ama a Marı́a

• Marı́a es amada por Juan

Usamos el término proposición para referirnos al contenido que ambas oraciones afirman.
Una proposición se interpreta en un contexto, por ejemplo
• El presidente actual es priista
Dependiendo del momento, esta oración corresponde a un enunciado verdadero (Enrique Peña) o a
un enunciado falso (Vicente Fox). Los términos enunciado y proposición no son exactamente sinónimos.

1.1.2 Inferencia
Inferencia es el proceso por el cual se llega a una proposición y se afirma sobre ella en base de una o
más proposiciones aceptadas como punto inicial del proceso.

4
1.1.3 Argumento
En correspondencia a cada inferencia existe un argumento. Un argumento es cualquier conjunto de
proposiciones de las cuales se dice que una se sigue de las otras, que pretenden apoyar o fundamentar su
verdad.

1.1.4 Premisa-conclusión
Un argumento tiene una estructura: premisa-conclusión
La conclusión de un argumento es la proposición que se afirma con base en las otras proposiciones
del argumento.
Las otras proposiciones afirmadas o supuestas para aceptar la conclusión son las premisas del argu-
mento.

Ejemplo 1

Como las sensaciones son esencialmente privadas, no podemos saber cómo es el mundo para otras
personas.

Ejemplo 2

Una superficie gris se ve roja si antes hemos visto una azul verdosa; una hoja de papel se siente
muy suave si hemos tocado antes una lija, o rugosa si antes hemos tocado una suave superficie de
cristal; el agua de la llave sabe dulce si hemos comido antes alcachofas. Por tanto, una parte de lo
que llamamos rojo, suave o dulce debe estar en los ojos, los dedos o la lengua del que ve, toca o
prueba.

Ejemplo 3

Enfriar los átomos equivale a retardar su movimiento, puesto que la temperatura es una medida
de qué tan rápido se están moviendo los átomos o las moléculas (el cero absoluto es la inmovilidad
total).

IMPORTANTE:
 Ninguna proposición por sı́ misma, en forma aislada, es una premisa o una conclusión.
 Una premisa solamente aparece como supuesto en un argumento.
 Una conclusión solamente aparece en un argumento y se fundamenta en las otras proposiciones del
argumento.
 Son términos relativos. Como ”empleador” y ”empleado”: depende de un contexto.
 El orden no es relevante.
Ejemplo 4

Puesto que la libertad y el bienestar son las condiciones necesarias de la acción y en general de
la acción exitosa, cada agente debe reconocer estas condiciones como bienes necesarios para sı́
mismo, puesto que sin ellas no serı́a capaz de actuar para conseguir un propósito determinado,
sea en absoluto o con las oportunidades generales de lograr el éxito.

5
2 Sintáxis y semática de la lógica proposicional
2.1 Fundamentos de lógica
En el desarrollo de cualquier teorı́a matemática se hacen afirmaciones en forma de frases. Tales afirma-
ciones, verbales o escritas, denominadas enunciados o proposiciones, son frases declarativas verdaderas
o falsas.
Las proposiciones se representan con letras minpusculas:
p: Matemáticas Discretas es un curso propedeúico de la Maestrı́a en Ciencias Computacionales
q: Juan Rulfo escribió ”Pedro Páramo”
Las proposiciones más sencillas posibles se denominan atómicas.

Definición

Las proposiciones constituidas por proposiciones atómicas y otras partı́culas que sirven de nexos se
llaman compuestas.

2.1.1 Conectivas básicas

Estas proposiciones pueden considerarse como primitivas, ya que en realidad no se pueden descomponer en
partes más simples. Las proposiciones primitivas se utilizan con conectivos lógicos para formar enunciados
compuestos.

Definición

Un conectivo lógico es una partı́cula que se utiliza para formar las proposiciones compuestas,
es decir, es un elemento de lenguaje que permite construir proposiciones nuevas a partir de las
existentes, obteniendo ası́ nuevos significados.

Las conectivas lógicas son:

¬ negación
∧ conjunción
∨ disyunción
Y disyunción mutuamente exclusiva
→ implicación
↔ doble implicación

• Negación. La negación de una proposición p se denota se denota por p o ¬p, y se lee ”no p”.

Ejemplo 1

Para p : Combinatoria es un curso obligatorio

¬p es la proposición ”Combinatoria no es un curso obligatorio”.

• Conjunción. la conjunción de p, q se denota por p ∧ q, y se lee ”p y q”.

Ejemplo 2

Para
∗ p : Combinatoria es un curso obligatorio
∗ q : Estudio la especialidad de computación

6
 Se lee:
”Combinatoria es un curso obligatorio y yo estudio la especialidad de computación”.

• Disyunción. La expresión p ∨ q denota la disyunción de p, q, y se lee ”p o q”.

Ejemplo 3

Para
∗ p : Combinatoria es un curso obligatorio
∗ q : Estudio la especialidad de computación
Se lee:
”Combinatoria es un curso obligatorio o yo estudio la especialidad de computación”.

Aquı́ se utiliza la conjunción ”o” en sentido inclusivo. En consecuencia, p ∨ q es verdadera si una o

la otra, o ambas proposiciones p, q son verdaderas. Esto suele indicase escribiendo ”y/o”.
• Disyunción mutuamente exclusiva. El ”o” exclusivo se denota mediante p Y q. La proposición
compuesta p Y q es verdadera si una u otra, pero no ambas proposiciones p, q son verdaderas.

Ejemplo 4

Para
∗ p : Combinatoria es un curso obligatorio
∗ q : Estudio la especialidad de computación
Se lee:
”Combinatoria es un curso obligatorio o yo estudio la especialidad de computación, pero no
ambas”.

• Implicación. Se dice que ”p implica q” y se escribe p → q para designar la implicación de q por

p. Opcionalmente, se puede decir:
a) si p, entonces q
b) p es suficiente para q
c) p sólo si q
d) q es necesario para p
Una traducción verbal de p → q para el ejemplo es: ”Si combinatoria es un curso obligatorio,
entonces yo estudio la especialidad de computación”.
La proposición p se denomina hipótesis de la implicación y q se denomina conclusión.
• Doble implicación. La doble implicación de dos preposiciones p, q se denota por p ↔ q, y se lee:
a) p es equivalente a q
b) p si, y sólo si q
c) es necesario y suficiente para q
Para las p, q anteriores, ”Combinatoria es un curso obligatorio si, y sólo si, yo estudio la especial-
idad de computación” expresa el significado de p ↔ q.
En las proposiciones de la lógica proposicional pueden incluirse signos que agrupen proposiciones, por
ejemplo:
¬p ∨ (q ↔ r)
¬(p → r) ∧ (q ↔ r)
(p ∧ q) → (q ∨ ¬r)

7
2.1.2 Tablas de verdad
Los valores de verdad de las proposiciones compuestas pueden ser descritos por tablas de verdad. Las
tablas de verdad expresan las circunstancias en las que una proposición de la lógica proposicional es
verdadera (1) o falsa (0):

Definición

Una tabla de verdad de una proposición presenta los valores de verdad de la proposición para todas
las asignaciones posibles de la proposiciones atómicas

p ¬p
0 1
1 0

p q p∧q p∨q pYq p→q p↔q

0 0 0 0 0 1 1
0 1 0 1 1 1 0
1 0 0 1 1 0 0
1 1 1 1 0 1 1

• Una conjunción es verdadera cuando p y q, ambas, son verdaderas.

p q p∧q
1 1 1
1 0 0
0 1 0
0 0 0

• Una disyunción exclusiva es verdadera cuando p es verdadera y q falsa o bien cuando p es falsa y q
verdadera.

p q pYq
1 1 0
1 0 1
0 1 1
0 0 0

• Una implicación es verdadera cuando p y q son verdaderas o cuando p es falsa.

p q p→q
1 1 1
1 0 0
0 1 1
0 0 1

2.1.3 Tautologı́a y contradicción

Definición

8
 Una proposición de la lógica proposicional es una tautologı́a, denotada como T0 , si es verdadera
para todas las asignaciones de verdad de sus proposiciones componentes.

p q p→p∨q
1 1 1
1 0 1
0 1 1
0 0 1

Si para las proposiciones s1 , s2 , resulta que s1 ⇔ s2 es una tautologı́a, entonces s1 y s2 deben tener
la misma tabla de verdad, de modo que s1 ⇔ s2 .

Definición

Una proposición de la lógica proposicional es una contradicción, denotada como F0 , si es falsa

para todas las asignaciones de verdad de sus proposiciones componentes.

p p ∧ (¬p)
1 0
0 1

2.1.4 Precedencia de los operadores

En proposiciones compuestas como r ∨ p → q, ¿cuál es el orden de la aplicación de los operadores lógicos?.
Se usan parentesis para especificar el orden:

r ∨ (p → q)

Si no se emplean paréntensis, se emplea la lista de precedencia

Operador Precedencia
¬ 1
∧ 2
∨ 3
→ 4
↔ 5

2.1.5 Equivalencia lógica

Definición

Dos proposiciones s1 y s2 son lógicamente equivalentes, denotado como s1 ⇔ s2 , si y sólo si la

proposición s1 es verdadera cuando s2 es verdadera, y s1 es falsa cuando s2 es falsa.

Dos proposiciones son equivalentes lógicamente si y solo si sus valores de verdad (tablas de verdad)
son idénticos.

Ejemplo 5

Probar que q ∧ (¬r → p) ⇔ (r ∧ q) ∨ (p ∧ q)

9
 p q r ¬r ¬r → p q ∧ (¬r → p) r∧q p∧q (r ∧ q) ∨ (p ∧ q)
F F F T F F F F F
F F T F T F F F F
F T F T F F F F F
F T T F T T T F T
T F F T T F F F F
T F T F T F F F F
T T F T T T F T T
T T T F T T T T T

Table 1: Donde F = false y T = true

De acuerdo con la tabla de verdad q ∧ (¬r → p) y (r ∧ q) ∨ (p ∧ q) son proposiciones equivalentes.

2.1.6 Leyes de equivalencia

Otra forma de com probar si dos proposiciones son lógicamente equivalentes es aplicando las leyes de la
lógica. En general, las leyes de la lógica son útiles para simplificar una proposición.
Para cualesquiera proposiciones lógicas p, q y r:

¬¬p ⇔ p Doble negación

¬(p ∨ q) ⇔ ¬p ∧ ¬q DeMorgan
¬(p ∧ q) ⇔ ¬p ∨ ¬q
p ∨ q ⇔ ∨p Conmutativas
p∧q ⇔q∧p
p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r Asociativas
p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) Distributivas
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
p∨p⇔p Idempotentes
p∧p⇔p
p ∨ F0 ⇔ p Identidad
p ∧ T0 ⇔ p
p ∨ ¬p ⇔ T0 Inversas
p ∧ ¬p ⇔ F0
p ∨ T0 ⇔ T0 Dominación
p ∧ F0 ⇔ F0
p ∨ (p ∧ q) ⇔ p Absorción
p ∧ (p ∨ q) ⇔ p

Definición

Sea s una proposición de la lógica proposicional. Si s sólo contiene conectivas lógicas conjuntivas y
disyuntivas, entonces el dual de s, denotado como sd , es la proposición que se obtiene al reemplazar
cada ocurrencia de ∧ y ∨ por ∨ y ∧, respectivamente, y cada ocurrencia de T0 y F0 por F0 y T0 ,
respectivamente.

Ejemplo 6

Los siguientes pares de proposiciones son duales.

a) s1 : p ∨ T0 , sd1 : p ∧ F0

10
 b) s2 : (p ∧ ¬q) ∨ (r ∧ T0 ), sd2 : (p ∨ ¬q) ∧ (r ∨ F0 )

Definición

Teoremoa del principio de la dualidad.

Sean s y t proposiciones de la lógica proposicional, si s ⇔ t entonces sd ⇔ td

Analicem os los valores de verdad de las proposiciones p → q, ¬q → ¬p, q → p y ¬p → ¬q

p q p→q ¬q → ¬p q→p ¬p → ¬q
0 0 1 1 1 1
0 1 1 1 0 0
1 0 0 0 1 1
1 1 1 1 1 1

De acuerdo a la tabla previa, podemos afirmar que (p → q) ⇔ (¬q → ¬p) y (q → p) ⇔ (¬p → ¬q).
La proposición ¬q → ¬p se conoce como la contrapositiva de la implicación p → q. La proposición
q → p se denomina la recı́proca de p → q y ¬q → ¬p se conoce como la inversa de p → q. Nótese que

(p → q) 6⇔ (q → p) y
(¬p → ¬q) 6⇔ (¬q → ¬p)

Ejemplo 7

Se tiene en 1a una red con un interruptor, 1b y 1c tienen dos interruptores (independientes) cada
una. En la red de 1b, la corriente fluye de T1 a T2 si cualquiera de los dos interruptores p, q está
cerrado. Esta red se denomina paralela y se representa por p ∨ q. La red 1c necesita que los dos
interruptores p, q estén cerrados para que la corriente fluya de T1 a T2 . Aquı́, los interruptores
están en serie y esta red se representa por p ∧ q.

(a) (b) (c)

Figura 1: Red 1

Ejemplo 8

Suponga que tenemos la red ilustrada en la Figura 2, en la cual los interruptores no son indepen-
dientes entre sı́. Esta red puede representarse como la proposición lógica:

(p ∨ q ∨ r) ∧ (p ∨ t ∨ ¬q) ∧ (p ∨ ¬t ∨ r)

11
 Figura 2: Red 2

y suponga también que deseamos simplificar esta red. Para simplificar la expresión, debemos buscar
la equivalencia lógica de la proposición original y proposiciones más simples.

Simplificación Razones
(p ∨ q ∨ r) ∧ (p ∨ t ∨ ¬q) ∧ (p ∨ ¬t ∨ r)
⇔ p ∨ [(q ∨ r) ∧ (t ∨ ¬q) ∧ (¬t ∨ r)] Ley distributiva
⇔ p ∨ [((q ∨ r) ∧ t) ∨ ((q ∨ r) ∧ ¬q)) ∧ (¬t ∨ r)] Ley distributiva
⇔ p ∨ [(((q ∨ r) ∧ t) ∨ ((q ∧ ¬q) ∨ (r ∧ ¬q))) ∧ (¬t ∨ r)] Ley distributiva
⇔ p ∨ [(((q ∨ r) ∧ t) ∨ (F0 ∨ (r∧ → q))) ∧ (¬t ∨ r)] Ley inversa
⇔ p ∨ [(((q ∨ r) ∧ t) ∨ (r ∧ ¬q)) ∧ (¬t ∨ r)] Ley del elemento neutro
⇔ p ∨ [(((q ∨ r) ∧ t) ∧ (¬t ∨ r)) ∨ ((r ∧ ¬q) ∧ (¬t ∨ r))] Ley distributiva
⇔ p ∨ [((q ∨ r) ∧ (t ∧ (¬t ∨ r))) ∨ ((r ∧ ¬q) ∧ (¬t ∨ r))] Ley asociativa
⇔ p ∨ [((q ∨ r) ∧ ((t ∧ ¬t) ∨ (t ∧ r))) ∨ ((r ∧ q) ∧ (¬t ∨ r))] Ley distributiva
⇔ p ∨ [((q ∨ r) ∧ (F0 ∨ (t ∧ r))) ∨ ((r ∧ ¬q) ∧ (¬t ∨ r))] Ley inversa
⇔ p ∨ [((q ∨ r) ∧ (t ∧ r)) ∨ ((r ∧ ¬q) ∧ (¬t ∨ r))] Ley del elemento neutro
⇔ p ∨ [((q ∨ r) ∧ (t ∧ r)) ∨ (((r ∧ ¬q) ∧ ¬t) ∨ ((r ∧ ¬q) ∧ r))] Ley distributiva
⇔ p ∨ [((q ∨ r) ∧ (t ∧ r)) ∨ ((r ∧ ¬q ∧ ¬t) ∨ (r ∧ ¬q ∧ r))] Ley asociativa
⇔ p ∨ [((q ∨ r) ∧ (t ∧ r)) ∨ ((r ∧ ¬q ∧ ¬t) ∨ (r ∧ ¬q))] Ley idempotente
⇔ p ∨ [((q ∨ r) ∧ (t ∧ r)) ∨ (r ∧ ¬q)] Ley absorción
⇔ p ∨ [((q ∧ (t ∧ r)) ∨ (r ∧ (t ∧ r))) ∨ (r ∧ ¬q)] Ley distributiva
⇔ p ∨ [((q ∧ (t ∧ r)) ∨ (t ∧ r)) ∨ (r ∧ ¬q)] Leyes asociativa e idempotente
⇔ p ∨ [(t ∧ r) ∨ (r ∧ ¬q)] Ley de absorción
⇔ p ∨ [(r ∧ t) ∨ (r ∧ ¬q)] Ley conmutativa
⇔ p ∨ [r ∧ (t ∨ ¬q)] Ley distributiva

Ası́ (p ∨ q ∨ r) ∧ (p ∨ t ∨ ¬q) ∧ (p ∨ ¬t ∨ r) ⇔ p ∨ [r ∧ (t ∨ ¬q)], y la red de la Figura 3 es equivalente

a la red original, pero esta red tiene 4 interruptores, 5 menos que la original.

Figura 3: Red simplificada

2.1.7 Reglas de inferencia

Una demostración es un argumento correcto (bien razonado, lógicamente válido) y completo (claro,
detallado) que rigurosamente establece la veracidad de una proposición matemática.
Una regla de inferencia es un patrón que establece que si se conocen un conjunto de proposiciones
antecedentes verdaderas, entonces se puede deducir que cierta proposición consecuente relacionada es

12
verdadera. Es decir, permiten determinar la validez de un argumento para demostrar un teorema.
(p1 ∧ p2 ∧ p3 ∧ · · · ∧ pn ) → q
p1 , p2 , p3 , . . . , pn se conocen como las premisas del argumento, y q se conoce como la conclusión del
argumento.
Una manera de inferir la conclusión es dem ostrar que la proposición correspondiente a las premisas
es una tautologı́a.

Definición

Si p y q son proposiciones arbitrarias, y p → q es una tautologı́a, decimos que p implica lógicamente

a q y escribimos p ⇒ q.

Ejemplo 9

Sean p1 : p, p2 : (p ∧ r) → s y q : r → s Verifique con una tabla de verdad que (p1 ∧ p2 ) implica

lógicamente a q. Es decir, tenemos que demostrar (p1 ∧ p2 ) → q es una tautologı́a.

p1 p2 q (p1 ∧ p2 ) (p1 ∧ p2 ) → q
p r s p∧r (p ∧ r) → s r→s [p ∧ ((p ∧ r) → s)]] [p ∧ ((p ∧ r) → s)]] → (r → s)
0 0 0 0 1 1 0 1
0 0 1 0 1 1 0 1
0 1 0 0 1 0 0 1
0 1 1 0 1 1 0 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 1 0 0 0 1
1 1 1 1 1 1 1 1

Las reglas de inferencia postulan asociaciones conocidas y probadas de implicación lógica. Con las
tablas de verdad correspondientes, que son tautologı́as, puede dem ostrarse que estas reglas son implica-
ciones lógicas.

p Regla de adición ∴p∨q

p∧q Regla de simplificación ∴p
p Regla de conjunción q ∴p∧q

• Modus Ponens

p | premisas
p→q | (1)
∴q conclusión
• Ley del silogismo

p→q
q→r (2)
∴p→r
• Modus Tollens

p→q
¬q (3)
∴ ¬p

13
 • Regla de la conjunción

p
q (4)
∴p∧q

• Regla del silogismo disyuntivo

p∨q
¬p (5)
∴q

• Regla de la contradicción

¬p → F0
(6)
∴p

• Regla de simplificación conjuntiva

p∧q
(7)
∴p

• Regla de simplificación disyuntiva

p
(8)
∴p∨q

• Regla de demostración condicional

p∧q
p → (q → r) (9)
∴r

• Regla de demostración por casos

p→r
q→r (10)
∴ (p ∨ q) → r

• Regla del dilema constructivo

p→q
r→s
(11)
p∨r
∴q∨s

• Regla del dilema destructivo

p→q
r→s
(12)
¬q ∨ ¬s
∴ ¬p ∨ ¬r

Ejemplo 10

14
 Aplique las reglas de inferencia modus ponens, modus tollens y regla del silogismo para demostrar
la validez del siguiente argumento.

p→r
r→s
t ∨ ¬s
¬t ∨ u
¬u
∴ ¬p

Pasos Justificación
1) p → r, r → s Premisas
2) p → s 1) + Ley del silogismo
3) t ∨ ¬s Premisa
4) ¬s ∨ t 3) + Comnutativa de disyunción
5) s → t 4) + ¬s ∨ t ⇒ s → t
6) p → t 2) + 5) + Ley del silogismo
7) ¬t ∨ u Premisa
8) t → u 7) + ¬t ∨ u ⇒ t → u
9) p → u 6) + 8) + Ley del silogismo
10) ¬u Premisa
11) ∴ ¬p 9) + 10) + modus tollens

2.1.8 Cuantificadores
Considere las siguiente afirmaciones:

• Todos los gatos tienen cola.

• A algunas personas les gusta la carne cruda.
• Todos conseguimos un descanso de vez en cuando.

Todas estas afirmaciones indican qué tan frecuentemente ciertas cosas son verdaderas. En cálculo de
predicados se usan cuantificadores en este contexto.

Definición

Sea A una expresión, y sea x una variable. Si queremos indicar que A es verdadera para todos
los valores posibles de x, escribimos ∀xA. Aquı́ ∀x es llamado el cuantificador universal,
y A se llama el ámbito o alcance del cuantificador. La variable x se dice que está ligada al
cuantificador. El sı́mbolo ∀ se pronuncia ”para todo”.

El cuantificador y la variable ligada que la sigue tienen que ser tratados como una unidad, y esta
unidad actúa como una conectiva unaria. Oraciones que contienen palabras como cada, cada uno, y todos
usualmente indican cuantificación universal. Tales oraciones deben ser reescritas de tal forma que
empiecen con ”para cada x”, lo cual se traduce como ∀x.

Ejemplo 11

Exprese ”Todos conseguimos un descanso de vez en cuando” en cálculo de predicados.

Definimos B de tal forma que signifique ”conseguir un descanso de vez en cuando”. Por tanto B(x)
significa que x consigue un descanso de vez en cuando. La palabra ”Todos” indica que esto es
verdadero para toda x. Esto lleva a la traducción ∀xB(x).

15
 Definición

Si A representa una expresión, y x representa a una variable. Si queremos indicar que A es verdadero
para al menos un valor de x, escribimos ∃x A. Esto se pronuncia ”existe una x tal que A”. Aquı́
∃x es llamado el cuantificador existencial, y A se llama el alcance o ámbito del cuantificador
existencial. La variable x se dice que está ligada al cuantificador.

Afirmaciones que contienen frases como algunos, al menos uno sugieren cuantificación existencial. Y
deben ser reescritos como ”Hay un x tal que”, lo cual se traduce en ∃x.

Ejemplo 12

Sea P la propiedad ”le gusta la carne cruda”. Entonces ∃x P (x) se puede traducir como ”Hay
personas a las que les gusta la carne cruda” o ”A algunas personas les gusta la carne cruda”.

Los cuantificadores se pueden anidar, como se muestra en los siguientes ejemplos:

Ejemplo 13

Traducir la oración ”Hay alguien que conoce a todos” en lenguaje de cálculo de predicados.
Para hacer esto, use C(x, y) para expresar el hecho de que x conoce a y. Escribimos informalmente
∃x(x conoce a todos). Aquı́ ”x conoce a todos” está todavı́a en español y significa que para todo
y es verdad que x conoce a y. Por tanto x conoce a todos = ∀yC(x, y). Finalmente se añade el
cuantificador existencial y obtenemos ∃x∀yC(x, y).

Ejemplo 14

Traducir ”Cualquiera tiene alguien quien es su madre” en cálculo de predicados.

Definimos M como el predicado ”madre”; esto es, M (x, y) significa que ”x es la madre de y”. La
oración ”Alguien es la madre de y” se traduce como ∃xM (x, y). Para expresar que esto debe ser
verdad para toda y, agregamos el cuantificador universal, lo cual queda como ∀y∃xM (x, y)

La oración ”Nadie es perfecto” también incluye un cuantificador, ”Nadie”, el cual es la ausencia de un

individuo con una cierta propiedad. En cálculo de predicados el hecho de que nadie tenga una propiedad
P , no puede ser expresada directamente. Para expresar el hecho de que no hay x para la cual una
expresión A es verdadera, uno puede usar ¬∃xA o ∀x¬P (x), indica que nadie es perfecto. En el primer
caso, decimos, en traducción verbal, ”No se da el caso de que exista alguien quien sea perfecto”, mientras
que en el segundo caso decimos ”Para cualquiera, no se da el caso de que sea perfecto”. Los dos métodos
para expresar que nadie es A deben por supuesto ser lógicamente equivalentes; esto es:

¬∃xA ≡ ∀x¬P (x)

2.2 Sintáxis de la lógica proposicional

El alfabeto proposicional esta conformado por:
• variables proposicionales: p0 , p1 , . . . ; p, q, r
• conectivas lógicas:

– monaria: ¬ (negación)
– binarias: ∧ (conjunción), ∨ (disyunción), → (condicional), ↔ (bicondicional)
• sı́mbolos auxiliares: ”(” y ”)”

16
 Las variables proposicionales son fórmulas (fórmulas atómicas). Si F y G son fórmulas entonces
también lo son:
¬F, (F ∧ G), (F ∨ G), (F → G) y (F ↔ G)

Ejemplo 1

• Fórmulas: p, (p ∨ ¬q), ¬(p ∨ p), ((p → q) ∨ (q → p))

• No fórmulas: (p), p ∨ ¬p, (p ∨ ∧q)

2.2.1 Fórmulas proposicionales (BNF)

Notaciones:
• p, q, r, . . . representarán variables proposicionales.
• F, G, H, . . . representarán fórmulas.
• V P representa el conjunto de los variables proposicionales.
• P rop representa el conjunto de las fórmulas.
• * representa una conectiva binaria.
La forma de Backus Naur (BNF) de las fórmulas proposicionales es:
F ::= p|¬G|(F ∧ G)|(F ∨ G)|(F → G)|(F ↔ G)

2.2.2 Definiciones por recursión sobre fórmulas

El número de paréntesis de una fórmula F se defina recursivamente por:

0,
 si F es atómica;
np(F ) = np(G), si F es ¬G;

2 + np(G) + np(H), si F es (G ∗ H)


Ejemplo 2

El número de paréntesis de las siguientes proposiciones es:

• np(p) = 0
• np(q) = 0
• np(¬q) = 0
• np((¬q ∨ p)) = 2
• np((p → (¬q ∨ p))) = 4

2.2.3 Demostración por inducción sobre fórmulas

Sea P una propiedad sobre las fórmulas que verifica las siguientes condiciones:
• Todas las fórmulas atómicas tiene la propiedad P .
• Si F y G tienen la propiedad P .
• Si F y G tiene la propiedad P , entonces ¬F , (F ∧ G), (F ∨ G), (F → G) y (F ↔ G), tienen la
propiedad P
Entonces todas las fórmulas proposicionales tienen la propiedad P .
 Propiedad . Todas las fórmulas proposicionales tienen un número par de paréntesis.
17
2.2.4 Criterio de reducción de paréntesis
Algunas forma de reducir los paréntesis son:

• Eliminar los paréntesis externos

– F ∧ G es una abreviatura de (F ∧ G)
• Por precedencia de asociacón de conectivas: ¬, ∧, ∨, →, ↔.

– F ∧ G → ¬F ∨ G es una abreviatura de ((F ∧ G) → (¬F ∨ G)).

• Si una conectiva se usa repetidamenente, se asocia por la derecha

F ∨G∨H abrevia (F ∨ (G ∨ H))

F ∧ G ∧ H → ¬F ∨ G abrevia ((F ∧ (G ∧ H)) → (¬F ∨ G))

2.2.5 Subfórmulas

Definición

El conjunto Subf(F) de las subfórmulas de una fórmula F se define recursivamente por:


{F },
 si F es atómica;
subf (F ) = {F } ∪ Subf (G), si F es ¬G;

{F } ∪ Subf (G) ∪ Subf (H), si F es (G ∗ H)


Ejemplo 3

• Subf (p) = {p}

• Subf (q) = {q}
• Subf (¬q) = {¬q, q}

• Subf (¬q ∨ p) = {¬q ∨ r, ¬q, q, p}

• Subf (p → ¬q ∨ p) = {p → ¬q ∨ p, p, ¬q ∨ p, ¬q, q}

2.3 Sémantica proposicional

2.3.1 Valores y funciones de verdad
Los valores de verdad (B) son 1 es para verdadero y 0 es para falso. Ası́, las funciones de verdad son las
siguientes:
(
1, si i = 0;
H¬ : {0, 1} → {0, 1} t.q (tal que) H¬ (i) =
0, si i = 1
(
1, si i = j = 1;
H∧ : {0, 1}2 → {0, 1} t.q H∧ (i, j) =
0, en otro caso.
(
2 0, si i = j = 0;
H∨ : {0, 1} → {0, 1} t.q H∨ (i, j) =
1, en otro caso.

18
 (
2 0, si i = 1, j = 0;
H→ : {0, 1} → {0, 1} t.q H→ (i, j) =
1, en otro caso.
(
1, si i = j;
H↔ : {0, 1}2 ↔ {0, 1} t.q H↔ (i, j) =
0, en otro caso.
Las funciones de verdad también se representan mediante tablas de verdad (ver sub-sección 2.1.2).

Definición

Una interpretación es una aplicación I : V P → B.

Para cada interpretación I existe una única aplicación I 0 : P rop → B tal que:

I(F ),
 si F es atómica;
I 0 (F ) = H¬ (I 0 (G)), siF = ¬G;
H¬ (I 0 (G), I 0 (H)),

si F = G ∗ H


Se dice que I 0 (F ) es el valor de verdad de F respecto de I.

Ejemplo 1

Sea F = (p ∨ q) ∧ (¬q ∨ r).

– Donde el valor de F en una interpretación I1 tal que I1 (p) = I1 (r) = 1, I1 (q) = 0.
Sustituyendo los valores, la interpretación queda de la siguiente manera:

(p ∨ q) ∧ (¬q ∨ r)
(1 ∨ 0) ∧ (¬0 ∨ 1)
1 ∧ (1 ∨ 1)
1 ∧ 1
1

– Donde el valor de F en una interpretación I2 tal que I2 (r) = 1, I2 (p) = I2 (q) = 0

Sustituyendo los valores, la interpretación queda de la siguiente manera:

(p ∨ q) ∧ (¬q ∨ r)
(0 ∨ 0) ∧ (¬0 ∨ 1)
0 ∧ (1 ∨ 1)
0 ∧ 1
0

 Propiedad . Sea F una fórmula y I1 , I2 dos interpretaciones. Si I1 (p) = I2 (p) para todas las
variables proposicionales de F , entonces I10 (F ) = I20 (F ).

2.3.2 Modelos y satisfacibilidad

Definición

I es modelo F si I(F ) = 1.
I |= F

19
 Ejemplo 2

continuando con el ejemplo anterior (1):

– Si I1 (p) = I1 (r) = 1, I1 (q) = 0, entonces I1 |= (p ∨ q) ∧ (¬q ∨ r).

– Si I2 (r) = 1, I2 (p) = I2 (q) = 0, entonces I2 6|= (p ∨ q) ∧ (¬q ∨ r).

Definición

F es satisfacible si F tiene algún modelo.

Ejemplo 3

(p → q) ∧ (q → r) es satisfacible para I(p) = I(q) = I(r) = 0

(p → q) ∧ (q → r)
(0 → 0) ∧ (0 → 0)
1 ∧ 1
1

Definición

F es insatisfacible si F NO tiene algún modelo.

Ejemplo 4

p ∧ ¬p es insatisfacible, debido a que no hay un modelo para cualquier valor de I.

p ¬p p ∧ ¬p
1 0 0
0 1 0

2.3.3 Tautologı́as y contradicciones

Definición

F es una tautologı́a (o válida) si TODA interpretación es modelo de F .

|= F

Definición

F es una contradicción si NINGUNA interpretación es modelo de F

|= F

20
 Definición

F es contingente si no es tautologı́a ni contradicción

|= F

Ejemplo 5

De acuerdo con la siguiente tabla de verdad:

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

1 1 1 1 1 0 0
1 0 0 1 1 1 0
0 1 1 0 1 0 0
0 0 1 1 1 0 0

1. (p → q) ∨ (q → p) es una tautologı́a
2. (p → q) ∧ ¬(p → q) es una contradicción
3. p → q es contingente

La clasificación de las fórmulas es la siguiente:

Todas las fórmulas

Tautologı́as Contingentes Contradicciones
Verdadera en todas las in- Verdadera en algunas in- Falsa en todas las inter-
terpretaciones terpretaciones y falsa en pretaciones
otras
Satisfacibles Insatisfacibles
Todas las fórmulas

2.3.4 Satisfacibilidad y validéz

Un problema SAT es: dada una F determinar si es satisfacible. Mientras que un problema TAUT
es: dada F determinar si es tautologı́a.
Las siguientes son relaciones entre satisfacibilidad y tautologicidad:
• F es tautologı́a ⇔ ¬F es insatisfacible.

• F es tautologı́a ⇒ F es satisfacible.
• F es satisfacible 6⇒ ¬F es insatisfacible.

Ejemplo 6

p → q es satisfacible para I(p) = I(q) = 1

¬(p → q) es satisfacible para I(p) = 1, I(q) = 0

21
2.3.5 Selección de tautologı́as

1 F →F Ley de identidad
2 F ∨ ¬F Ley del tercio excluido
3 ¬(F ∧ ¬F ) Principio de no contradicción
4 (¬F → F ) → F Ley de Clavius
5 ¬F → (F → G) Ley de Duns Scoto
6 ((F → G) → F ) → F Ley de Peirce
7 (F → G) ∧ F → G Modus ponens
8 (F → G) ∧ ¬G → ¬F Modus tollens

2.3.6 Fórmulas equivalentes

Definición

F y G son equivalentes si I(F ) = I(G) para toda interpretación I

F ≡G

Ejemplo 7

Ejemplos de equivalencias:
– Idempotencia: F ∨ F ≡ F ; F ∧ F ≡ F
– Conmutatividad: F ∨ G ≡ G ∨ F ; F ∧ G ≡ G ∧ F .
– Asociatividad: F ∨ (G ∨ H) ≡ (F ∨ G) ∨ H; F ∧ (G ∧ H) ≡ (F ∧ G) ∧ H
– Absorción: F ∧ (F ∨ G) ≡ F ; F ∨ (F ∧ G) ≡ F
– Distributividad: F ∧ (G ∨ H) ≡ (F ∧ G) ∨ (F ∧ H); F ∨ (G ∧ H) ≡ (F ∨ G) ∧ (F ∨ H)
– Doble negación: ¬¬F ≡ F
– Leyes de De Morgan: ¬(F ∧ G) ≡ ¬F ∨ ¬G; ¬(F ∨ G) ≡ ¬F ∧ ¬G
– Leyes de tautologı́as: Si F es una tautologı́a, F ∧ G ≡ G; F ∨ G ≡ F
– Leyes de contradicciones: Si F es una contradicción F ∧ G ≡ F ; F ∨ G ≡ G
 Propiedades de la equivalencia lógica
– Relación entre equivalencia y bicondiconal:
F ≡ G syss (si y solo si) |= F ↔ G

– Propiedades básicas de la equivalencia lógica:

∗ Reflexiva: F ≡ F
∗ Simétrica: Si F ≡ G, entonces G ≡ F
∗ Transitiva: Si F ≡ G y G ≡ H, entonces F ≡ H
– Principio de sustitución de fórmulas equivalentes:
Si en la fórmula F se sustituye una de sus subfórmulas G por una fórmula G0 lógicamente
equivalente a G, entonces la fórmula obtenida, F 0 , es lógicamente equivalente a F .
Ejemplos:
∗ F = ¬(p ∧ q) → ¬(p ∧ ¬¬r)
∗ G = ¬(p ∧ q)
∗ G0 = ¬p ∨ ¬q
∗ F 0 = (¬p¬q) → ¬(p ∧ ¬¬r)

22
2.3.7 Modelo de conjuntos de fórmulas

Definición

S, S1 , S2 , . . . representarán conjuntos de fórmulas. I es modelo de S si para toda F ∈ S se tiene

que I |= F .
I |= S

Ejemplo 8

Sea S = {(p ∨ q) ∧ (¬q ∨ r), q → r}

– La interpretación I1 tal que I1 (p) = 1, I1 (q) = 0, I1 (r) = 1 es modelo de S(I1 |= S).

{(p ∨ q) ∧ (¬q ∨ r), q → r}

{(1 ∨ 0) ∧ (¬0 ∨ 1), 0 → 1}
{1 ∧ (1 ∨ 1), 1}
{1 ∧ 1, 1}
{ 1, 1}
La interpretación I2 tal que I2 (p) = 0, I2 (q) = 1, I1 (r) = 0 no es modelo de S(I2 6|= S).

{(p ∨ q) ∧ (¬q ∨ r), q → r}

{(0 ∨ 1) ∧ (¬1 ∨ 0), 1 → 0}
{1 ∧ (0 ∨ 0), 0}
{1 ∧ 0, 0}
{ 0, 0}

2.3.8 Conjunto consistente de fórmulas

Definición

S es consistente si S tiene algún modelo. Por otro lado, S es inconsistente si S no tiene ningún
modelo.

Ejemplo 9

De acuerdo con la siguiente tabla de verdad:

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

I1 0 0 0 0 1 0 1 1
I2 0 0 1 0 1 0 1 0
I3 0 1 0 1 0 0 1 1
I4 0 1 1 1 1 1 1 0
I5 1 0 0 1 1 1 0 1
I6 1 0 1 1 1 1 1 0
I7 1 1 0 1 0 0 0 1
I8 1 1 1 1 1 1 1 0

• {(p ∨ q) ∧ (¬q ∨ r), p → r} es consistente con los modelos I4 , I6 , I8 .

• {(p ∨ q) ∧ (¬q ∨ r), p → r, ¬r} es inconsistente.

23
2.3.9 Consecuencia lógica

Definición

F es consecuencia de S si todos los modelos de S son modelos de F

S |= F

Ejemplo 10

De acuerdo con la siguientes tablas de verdad, {p → q, q → r} |= p → r y {p} 6|= p ∧ q

p q r p→q q→r p→r

I1 0 0 0 1 1 1
I2 0 0 1 1 1 1 p q p∧q
I3 0 1 0 1 0 1 1 1 1
I4 0 1 1 1 1 1 1 0 0
I5 1 0 0 0 1 0 0 1 0
I6 1 0 1 0 1 1 0 0 0
I7 1 1 0 1 0 0
I8 1 1 1 1 1 1

 Propiedades de la consecuencia
– Propiedades básicas de la relación de consecuencia:
∗ Reflexividad: S |= S
∗ Monotonı́a: Si S1 |= F y S1 ⊆ S2 , entonces S2 |= F
∗ Transitividad: Si S |= F y {F } |= G, entonces S |= G
– Relación entre consecuencia, validez, satisfacibilidad y consistencia. Las siguientes condiciones
son equivalentes:
1. {F1 , . . . , Fn } |= G
2. |= F1 ∧ · · · ∧ Fn → G
3. ¬(F1 ∧ · · · ∧ Fn →) es insatisfacible
4. {F − 1, . . . , Fn , ¬G} es inconsistente

2.3.10 Argumentaciones y problemas lógicos

El siguiente es un ejemplo de argumentación:
Problema de los animales. Se sabe que
• Los animales con pelo o que dan leche son mamı́feros.

• Los mamı́feros que tienen pezuñas o que rumian son ungulados.

• Los ungulados de cuello largo son jirafas.
• Los ungulados con rayas negras son cebras.
Se observa un animal que tiene pelos, pezuñas y rayas negras. Por consiguiente, se concluye que el
animal es una cebra.
El argumento se puede formalizar de la siguiente manera:
Formalización

24
 { tiene pelos ∨ da leche → es mamı́fero,
es mamı́fero ∧ (tiene pezuñas ∨ rumia) → es ungulado,
es ungulado ∧ tiene cuello largo → es jirafa,
es ungulado ∧ tiene rayas negras → es cebra,
tiene pelos ∧ tiene pezuñas ∧ tiene rayas negras }
|= es cebra
A continuación se muestra un ejemplo de problemas lógicos: Veraces y mentirosos. En una isla hay
dos tribus, la de los veraces (que siempre dicen la verdad) y la de los mentirosos (que siempre mienten).
Un viajero se encuentra con tres isleños A, B y C y cada uno le dice una frase
• A dice ”B y C son veraces syss C es veraz”
• B dice ”Si A y C son veraces, entonces B y C son veraces y A es mentiroso”
• C dice ”B es mentiroso syss A o B es veraz”
Determinar a qué tribu pertenecen A, B y C.
Simbolización.
• a: ”A es veraz”, b: ”B es veraz”, c: ”C es veraz”.
Formalización.
• F1 = a ↔ (b ∧ c ↔ c), F2 = b ↔ (a ∧ c → b ∧ c ∧ ¬a) y F3 = c ↔ (¬b ↔ a ∨ b).
Modelos de F1 , F2 yF3
• Si I es modelo de {F1 , F2 , F3 }, entonces I(a) = 1, I(b) = 1, I(c) = 0.
Conclusión: A y B son veraces y C es mentiroso.

3 Deducción en lógica proposicional

3.1 Reglas de deducción
3.1.1 Reglas de la conjunción
• Regla de introducción de la conjunción:
F G
∧i
F ∧ G

• Reglas de eliminación de la conjunción:

F ∧ G F ∧ G
∧e1 ∧e2
F G

Ejemplo 1

p ∧ q, r ` q ∧ r :
1. p ∧ q premisa
2. r premisa
3. q ∧e2 1
4. q ∧ r ∧i 2, 3
Adecuación de las reglas de la conjunción:
∧i : {F, G} |= F ∧ G
∧e1 : F ∧ G |= F
∧e2 : F ∧ G |= G

25
3.1.2 Reglas de la doble negación
• Regla de eliminación de la doble negación:

¬¬F
¬¬e
F

• Regla de introducción de la doble negación:

F
¬¬i
¬¬F

Ejemplo 2

p, ¬¬(q ∧ r) ` ¬¬p ∧ r :
1. p premisa
2. ¬¬(q ∧ r) premisa
3. ¬¬p ¬¬i 1
4. q∧r ¬¬e 2
5. r ∧e3 4
6. ¬¬p ∧ r ∧i 3, 5

Adecuación de las reglas de la conjunción:

¬¬e : {¬¬F } |= F
¬¬i : {F } |= ¬¬F

3.1.3 Reglas de eliminación del condicional

• Regla de eliminación del condicional:

F F →G
→e
G

Ejemplo 3

¬p ∧ q, ¬p ∧ q → r ∨ ¬p ` r ∨ ¬p :

1. ¬p ∧ q premisa
2. ¬p ∧ q → r ∨ ¬p premisa
3. r ∨ ¬p → e 1, 2

Ejemplo 4

p, p → q, p → (q → r) :
1. p premisa
2. p→q premisa
3. p → (q → r) premisa
4. q → e 1, 2
5. q→r → e 1, 3
6. r → e 4, 5

26
3.1.4 Regla derivada de modus tollens
• Regla derivada de modus tollens:
F →F ¬G
MT
¬F

Ejemplo 5

p → (q → r), p, ¬r ` ¬q :
1. p → (q → r) premisa
2. p premisa
3. ¬r premisa
4. q→r → e 1, 2
5. ¬q M T 3, 4

Ejemplo 6

¬p → q, ¬q ` p :
1. ¬p → q premisa
2. ¬q premisa
3. ¬¬p M T 1, 2

3.1.5 Regla de introducción del condicional

• Regla de introducción del condicional:
F
·
·
· →i
G

F →G

Ejemplo 7

p → q ` ¬q → ¬p :
1. p→q premisa
2. ¬q supuesto
3. ¬p M T 1, 2
4. ¬q → ¬p →i2-3
Adecuación de la regla de introducción del condicional
Si F |= G, entonces |= F → G

Ejemplo 8

¬q → ¬p ` p → ¬¬q :
1. ¬q → ¬p premisa
2. p supuesto
3. ¬¬p ¬¬i 2
4. ¬¬q M T 1, 3
5. p → ¬¬q →i2-4

27
 Ejemplo 9

(q → r) → ((¬q → ¬p) → (p → r)):

1. q→r supuesto
2. ¬p → ¬p supuesto
3. p isupuesto
4. ¬¬p ¬¬i 3
5. ¬¬q M T 2, 3
6. q ¬¬e 5
7. r → e 1, 6
8. p→r →i3-7
9. (¬q → ¬p) → (p → r) →i2-8
10. (q → r) → ((¬q → ¬p) → (p → r)) →i1-9

3.1.6 Reglas de la disyunción

• Reglas de introducción de la disyunción

F
∨ i1
F ∨G

G
∨ i2
F ∨G

• Regla de eliminación de la disyunción:

F G
· ·
· ·
· · ∨e
F ∨G H H

Ejemplo 10

q →r `p∨q →p∨r :
1. q→r premisa

2. p∨q supuesto

3. p supuesto
4. p∨r ∨r1 3

5. q supuesto
6. r → e 1, 5
7. p∨r ∨i2 6

8. p∨r ∨e 2, 3 - 4, 5 - 7

9. p∨q →p∨r →i2-8

28
3.1.7 Reglas de la negación
Extensiones de la lógica para usar falso:
• Extensión de la sintasis: ⊥ es una fórmula proposicional.
• Extensión de la semántica: I(⊥) = 0 en cualquier interpretación I.

Las siguientes son reglas de la negación:

• Regla de eliminación de lo falso:
⊥
⊥e
F

• Regla de eliminación de la negación:

F ¬F
¬e
⊥

Adecuación de las reglas de la negación:

– ⊥|= F
– {F, ¬F } |=⊥

Ejemplo 11

¬p ∨ q ` p → q :
1. ¬p ∨ q premisa

2. p supuesto

3. ¬p supuesto
4. ⊥ ¬e 2, 3
5. q ⊥e4

6. q supuesto

7. q ∨e 1, 3 - 5, 6 - 6
8. p→q →i2-7

• Regla de introducción de la negación:

F
·
·
¬i
·
⊥
¬F

Adecuación : Si F |=⊥, entonces |= ¬F

Ejemplo 12

29
 p → q, p → ¬q ⊥ ¬p :
1. p→q premisa
2. p → ¬q premisa

3. p supuesto
4. q → e 1, 3
5. ¬q → e 2, 3
6. ⊥ ¬e 4, 5

7. ¬p ¬i 3 - 6

3.1.8 Regla del bicondicional

• Regla de introducción del bicondicional:

F →G G→F
↔i
F ↔G

Ejemplo 13

p∧q ↔q∧p :
1. p∧q supuesto
2. p ∧e1 1
3. q ∧e2 1
4. q∧p ∧i 2,3

5. p∧q →q∧p →i1-4

6. q∧p supuesto
7. q ∧e2 6
8. p ∧e1 6
9. p∧q ∧i 7, 8

10. q∧p→p∧q →i6-9

• Eliminación del bicondicional:

F ↔G
↔ e1
F →G

F ↔G
↔ e2
G→F

Ejemplo 14

p∧q ↔q∧p :
1. p ↔ q premisa
2. p ∨ q premisa

3. p supuesto q supuesto
4. p → q ↔ e1 1 q→p → e2 1
5. q → q → e 4, 3 p → e 4’, 3’
6. p ∧ q ∧i 3, 5 p∧q ∧i 3’, 5’

7. p∧q ∧e 2, 3 - 6-, 3’ - 5’

30
3.2 Reglas derivadas
3.2.1 Regla del modus tollens
• Regla derivada de modus tollens (MT):

F ↔ G ¬G
MT
¬F

Derivación:
1. F → G premisa
2. ¬G premisa

3. F supuesto
4. G → e 1,3
5. ⊥ ¬e 2 - 4

6. ¬F ¬i 2 - 4

3.2.2 Regla de introducción de la doble negación

• Regla de introducción de la doble negación:

F
¬¬i
¬¬F

Derivación:
1. F premisa

2. ¬F supuesto
3. ⊥ ¬e 1, 2

4. ¬¬F ¬i 2 - 3

3.2.3 Regla de reducción al absurdo (RAA)

• Regla de reducción al absurdo:
¬F
·
·
· RAA
⊥

Derivación:
1. ¬F →⊥ premisa

2. ¬F supuesto
3. ⊥ → e 1, 2

4. ¬¬F ¬i 2 - 3
5. F ¬e ¬4

31
3.2.4 Ley del tercio exluido (LEM)
• Ley del tercio exluido (LEM):
LEM
F ∨ ¬F

Derivación:
1. ¬(F ∨ ¬F ) supuesto

2. F supuesto
3. F ∨ ¬F ∨i1 2
4. ⊥ ¬e 1, 3

5. ¬F ¬i 2 - 4
6. F ∨ ¬F ∨i2 5
7. ⊥ ¬e 1, 6

8. F ∨ ¬F RAA 1 - 7

Ejemplo 15

p → q ` ¬p ∨ q :
1. p→q premisa
2. p ∨ ¬p LEM

3. p supuesto
4. q → e 1, 3
5. ¬p ∨ q ∨i2 4

6. ¬p supuesto
7. ¬p ∨ q ∨i1 6

8. ¬p ∨ q ∨e 2, 3 - 5, 6 - 7

4 Sintáxis y semántica de primer orden

4.1 Representación del conocimiento en lógica de primer orden
4.1.1 Limitación expresiva de la lógica proposicional

Ejemplo 1

Si Sevilla es vecina de Cádiz, entonces Cádiz es vecina de Sevilla. Sevilla es vecina de Cádiz. Por
tanto, Cádiz es vecina de Sevilla
Representación en lógica proposicional:

{SvC → CvS, SvC} |= CvS

Ejemplo 1

32
 Si una ciudad es vecina de otra, entonces la segunda es vecina de la primera. Sevilla es vecina de
Cádiz. Por tanto, Cádiz es vecina de Sevilla
Representación en lógica proposicional: Imposible
Representación en lógica de primer orden:

{∀x∀y[vecina(x, y) → vecina(y, x)], vecina(Sevilla, Cadiz)} |= vecina(Cadiz, Sevilla)

4.1.2 Representación del mundo de los bloques

Simbolización:
• sobre(x, y) se verifica si el bloque x está colocado sobre el bloque y
• sobre mesa(x) se verifica si el bloque x está sobre la mesa
Situación del ejemplo: sobre(a, b), sobre(b, c), sobre mesa(c), sobre(d, e), sobre mesa(e)
Definiciones:
• bajo(x, y) se verifica si el bloque x está debajo del bloque y ∀x∀y[bajo(x, y) ↔ sobre(y, x)]
• encima(x, y) se verifica si el bloque x está encima del bloque y pudiendo haber otros bloques entre
ellos
∀x∀y[encima(x, y) ↔ sobre(x, y) ∨ ∃z[sobre(x, z) ∧ encima(z, y)]]

• libre(x) se verifica si el bloque x no tiene bloques encima

∀x[libre(x) → ¬∃ysobre(y, x)]

• pila(x, y, z) se verifica si el bloque x está sobre el y , el y sobre el z y el z sobre la mesa

∀x∀y∀z[pila(x, y, z) ↔ sobre(x, y) ∧ sobre(y, z) ∧ sobre mesa(z)]

 Propiedades: Si z, y, z es una pila entonces y no está libre

∀x∀y∀z[pila(x, y, z) → ¬libre(y)]

4.1.3 Representación del mundo de los bloques con funciones e igualdad

• Simbolización:
– es bloque(x) se verifica si x es un bloque.
– superior(x) es el bloque que está sobre el bloque x.
• Situación del ejemplo:
– es bloque(a), es bloque(b), es bloque(c), es bloque(d), es bloque(e)
– superior(b) = a, superior(c) = b, superior(e) = d
• Definiciones:

33
 – sobrem esa(x) se verifica si el bloque x está sobre la mesa
∀x[sobre mesa(x) ↔ es bloque(x) ∧ ¬∃ysuperior(y) = x]

– libre(x) se verifica si el bloque x no tiene bloques encima

∀x[libre(x) → ¬∃ysuperior(x) = y]

– tope(x) es el bloque libre que está encima de x

∀x[(libre(x) → tope(x) = x) ∧ (¬libre(x) → tope(x) = tope(superior(x)))]

4.1.4 Representación de conocimiento astronómico

• La Tierra es un planeta:
planeta(T ierra)

• La Luna no es un planeta:
¬planeta(Luna)

• La Luna es un satélite:
satélite(Luna)

• La Tierra gira alrededor del Sol:

gira(T ierra, Sol)

• Todo planeta es un satélite:

∀x[planeta(x) → satélite(x)]

• Todo planeta gira alrededor del Sol:

∀x[planeta(x) → gira(x, Sol)]

• Algún planeta gira alrededor de la Luna:

∃x[planeta(x) ∧ gira(x, Luna)]

• Hay por lo menos un satélite:

∃x satélite(x)

• Ningún planeta es un satélite:

¬∃x[planeta(x) ∧ satélite(x)]

• Ningún objeto celeste gira alrededor de sı́ mismo:

¬∃xgira(x, x)

• Alrededor de los satélites no giran objetos:

∀x[ satélite(x) → ¬∃ygira(y, x)]

• Hay exactamente un satélite:

∃x[ satélite(x) ∧ ∀y[ satélite(y) → x = y]]

• La Luna es un satélite de la Tierra:

satélite(Luna, T ierra)

• Todo planeta tiene un satélite:

∀x[planeta(x) → ∃y satélite(y, x)]

34
4.2 Sintaxis de la lógica de primer orden
4.2.1 Lenguaje de primer orden
Sı́mbolos lógicos:

• Variables: x, y, z, . . . , x1, x2, . . . .

• Conectivas: ¬, ∧, ∨, →, ↔.
• Cuantificadores: ∀, ∃.
• Sı́mbolo de igualdad: =.

Sı́mbolos propios:
• Sı́mbolos de constantes: a, b, c, . . . , a1 , a2 , . . . .
• Sı́mbolos de predicado (con aridad): P, Q, R, . . . , P1 , P2 , . . . .

• Sı́mbolos de función (con aridad): f, g, h, . . . , f1 , f2 , . . . .

Sı́mbolos auxiliares: ”(”, ”)”, ”,”.
Notación:
• L, L1 , L2 , . . . representan lenguajes de primer orden.

• V ar representa el conjunto de las variables.

• Los sı́mbolos de predicados de aridad mayor que 1 se llaman de relaciones.

Ejemplo 2

Lenguaje del mundo de los bloques:

– Sı́mbolos de constantes: a, b, c, d, e
– Sı́mbolos de predicado (y de relación):
∗ de aridad 1: sobre mesa, libre, es bloque
∗ de aridad 2: sobre, bajo, encima
∗ de aridad 3: pila
– Sı́mbolos de función (de aridad 1): superior, tope

Ejemplo 3

Lenguaje de la aritmética:

– Sı́mbolos de constantes: 0, 1
– Sı́mbolos de función:
∗ monaria: s (siguiente)
∗ binarias: +, ·
– Sı́mbolo de predicado binario: <

35
4.2.2 Términos

Definición

de término de un lenguaje de primer orden L:

– Las variables son términos de L.
– Las constantes de L son términos de L.
– Si f es un sı́mbolo de función n–aria de L y t1 , . . . , tn son términos de L, entonces f (t1 , . . . , tn )
es un término de L.

Ejemplo 4

• En el lenguaje de la aritmética,
– +(·(x, 1), s(y)) es un término, que se suele escribir como (x · 1) + s(y)
– +(·(x, <), s(y)) no es un término
• En el lenguaje del mundo de los bloques,
– superior(superior(c)) es un término.
– libre(superior(c)) no es un término.

Notación:

• s, t, t1 , t2 , . . . representan términos.
• Térm(L) representa el conjunto de los términos de L.

4.2.3 Fórmulas atómicas

Definición

de fórmula atómica de un lenguaje de primer orden L:

– Si t1 y t2 son términos de L, entonces t1 = t2 es una fórmula atómica de L.
– Si P es un sı́mbolo de relación n–aria de L y t1 , . . . , tn son términos de L, entonces P (t1 , . . . , tn )
es una fórmula atómica de L.

Ejemplo 5

• En el lenguaje de la aritmética,
– < (·(x, 1), s(y)) es una fórmula atómica que se suele escribir como x · 1 < s(y)
– +(x, y) = ·(x, y) es una fórmula atómica que se suele escribir como x + y = x · y
• En el lenguaje del mundo de los bloques,
– libre(superior(c)) es una fórmula atómica.
– tope(c) = superior(b) es una fórmula atómica.

Notación:

36
 • A, B, A1 , A2 , . . . representan fórmulas atómicas.
• Atóm(L) representa el conjunto de las fórmulas atómicas de L.

Definición

Las fórmulas atómicas de L son fórmulas de L.

– Si F y G son fórmulas de L, entonces ¬F, (F ∧ G), (F ∨ G), (F → G) y (F ↔ G) son fórmulas
de L.
– Si F es una fórmula de L, entonces ∀xF y ∃xF son fórmulas de L.

Ejemplo 6

• En el lenguaje de la aritmética,
– ∀x∃y < (x, y) es una fórmula que se escribe como ∀x∃yx < y
– ∀x∃y + (x, y) no es una fórmula.
• En el lenguaje del mundo de los bloques,
– ∀x(tope(x) = x ↔ libre(x)) es una fórmula.

Notación:
• F, G, H, F1 , F2 , . . . representan fórmulas.
• Fórm(L) representa el conjunto de las fórmulas de L.

4.2.4 Subfórmulas

Definición

El conjunto Subf (F ) de las subfórmulas de una fórmula F se define recursivamente por:




 {F }, si F es una fórmula atómica;
{F } ∪ Subf (G), Si F = ¬G;




Subf (F ) = {F } ∪ Subf (G) ∪ Subf (H), si F = G ∗ H;

{F } ∪ Subf (G), si F = ∀xG;





{F } ∪ Subf (G), si F = ∃xG

Ejemplo 7

Subf (∀x(R(x, c) → P (f (y)))) = {∀x(R(x, c) → P (f (y))),

(R(x, c) → P (f (y))),
R(x, c),
P (f (y))}

37
4.2.5 Criterios de reducción de paréntesis
• Pueden eliminarse los paréntesis externos.

F ∧ G es una abreviatura de (F ∧ G)

• Precedencia de asociación de conectivas y cuantificadores:

∀, ∃, ¬, ∧, ∨, →, ↔
∀xP (x) → Q(x) es una abreviatura de (∀xP (x)) → Q(x)

• Cuando una conectiva se usa repetidamente, se asocia por la derecha.

F ∨ G ∨ H es una abreviatura de (F ∨ (G ∨ H))

F ∧ G ∧ H → ¬F ∨ G es una abreviatura de ((F ∧ (G ∧ H)) → (¬F ∨ G)

• Los sı́mbolos binarios pueden escribirse en notación infija.

x + y es una abreviatura de + (x, y)

x < y es una abreviatura de < (x, y)

4.2.6 Conjuntos de variables

Definición

El conjunto de las variables del término t es


 ,
 si t es una constante;
V (t) = {x} si t es una variablex;

V (t1 ) ∪ · · · ∪ V (tn ), si t esf (t1 , . . . , tn )


Definición

El conjunto de las variables de la fórmula F es



 V (t1 ) ∪ V (t2 ), si F es t1 = t2 ;

V (t1 ) ∪ · · · ∪ V (tn ), si F es P (t1 , . . . , tn );





V (G), si F es ¬G;
V (F ) =


 V (G) ∪ V (H), si F es G ∗ H;
V (G), si F es ∀xG;




V (G), si F es ∃xG;


Ejemplo 8

• El conjunto de las variables de ∀x(R(x, c) → P (f (y))) es {x, y}.

• El conjunto de las variables de ∀x(R(a, c) → P (f (y))) es {y}.

38
4.2.7 Variables libres y ligadas
• La variable x es libre en F si tiene una aparición libre en F .
• La variable x es ligada en F si tiene una aparición ligada en F .
• El conjunto de las variables libres de una fórmula F es:


 V (t1 ) ∪ V (t2 ), si F es t1 = t2 ;

V (t1 ) ∪ · · · ∪ V (tn ), si

 F es P (t1 , . . . , tn );


V L(G), si F es ¬G;
V L(F ) =


 V L(G) ∪ V L(H), si F es G ∗ H;
V L(G) {x}, si F es ∀xG;





V L(G) {x}, si F es ∃xG;


Ejemplo 9

Table 2: My caption

Fórmula Ligadas Libres

∀x(P (x) → R(x, y)) → (∃yP (y) → R(x, z)) x, y x, y, z
∀x(P (x) → ∃yR(x, y)) x, y
∀z(P (x) → R(x, y)) x, y

4.2.8 Fórmulas cerradas y abiertas

Definición

Una fórmula cerrada (o sentencia) es una fórmula sin variables libres.

Ejemplo 10

• ∀x(P (x) → ∃yR(x, y)) es cerrada.

• ∃xR(x, y) ∨ ∀yP (y) no es cerrada.

Definición

Una fórmula abierta es una fórmula con variables libres.

Ejemplo 11

• ∀x(P (x) → ∃yR(x, y)) no es abierta.

• ∀xR(x, y) ∨ ∀yP (y) es abierta.

39
4.3 Semántica de la lógica de primer orden
4.3.1 Estructuras, asignaciones e interpretaciones
Una estructura del lenguaje L es un par I = (U, I) tal que:
• U es un conjunto no vacı́o, denominado universo de la estructura;
• I es una función con dominio el conjunto de sı́mbolos propios de L tal que
– si c es una constante de L, entonces I(c) ∈ U ;
– si f es un sı́mbolo de función n–aria de L, entonces I(f ) : U n → U ;
– si P es un sı́mbolo de relación 0–aria de L, entonces I(P ) ∈ {1, 0};
– si R es un sı́mbolo de relación n–aria (n > 0) de L, entonces I(R) ⊆ U n ;
Una asignación A en una estructura (U, I) es una función A : V ar → U que hace corresponder a
cada variable del alfabeto un elemento del universo de la estructura.
Una interpretación de L es un par (I, A) formado por una estructura I de L y una asignación A
en I.

Notación: A veces se usa para los valores de verdad V y F en lugar de 1 y 0.

Ejemplo 12

Sea L el lenguaje de la aritmética cuyos sı́mbolos propios son:

– constante: 0;
– sı́mbolo de función monaria: s;
– sı́mbolo de función binaria: + y
– sı́mbolo de relación binaria: ≤
• Primera estructura de L:
– U1 = N
– I1 (0) = 0
– I1 (s) = {(n, n + 1) : n ∈ N} (sucesor)
– I1 (+) = {(a, b, a + b) : a, b ∈ N} (suma)
– I1 (≤) = {(n, m) : n, m ∈ N, n ≤ m} (menor o igual)
• Segunda estructura de L:
– U2 = {0, 1}∗ (cadenas de 0 y 1)
– I2 (0) = (cadena vacı́a)
– I2 (s) = {(w, w1 ) : w ∈ {0, 1}∗ } (siguiente)
– I2 (+) = {(w1 , w2 , w1 w2 ) : w1 , w2 ∈ {0, 1}∗ } (concatenación)
– I2 (≤) = {(w1 , w2 ) : w1 , w2 ∈ {0, 1}∗ , w1 es prefijo de w2 } (prefijo)
• Tercera estructura de L:
– U3 = {abierto, cerrado}
– I3 (0) = cerrado
– I3 (s) = {(abierto, cerrado), (cerrado, abierto)}
– I3 (+) = {(abierto, abierto, abierto), (abierto, cerrado, abierto), (cerrado, abierto, abierto), (cerrado, cerrado
– I3 (≤) = {(abierto, abierto), (cerrado, abierto), (cerrado, cerrado)}

40
 e I3 (s)(e)
abierto cerrado
cerrado abierto

I3 (+) abierto cerrado

abierto abierto abierto
cerrado abierto cerrado

I3 (≤) abierto cerrado

abierto 1 0
cerrado 1 1

4.3.2 Evaluación de términos

Definición

Dada una estructura I = (U, I) de L y una asignación A en I, se define la función de evaluación

de términos IA : Térm(L) → U por

I(c),
 si t es una constante c;
IA (t) = A(x), si t es una variable x

I(f )(IA (t1 ), . . . , IA (tn )), si t es f (t1 , . . . , tn )


IA (t) se lee ”el valor de t en I respecto de A”.

Ejemplo 13

Sean L el lenguaje del Ejemplo 12, t el término s(+(x, s(0))), I la primera estructura y A(x) = 3.

IA (t) = IA (s(+(x, s(0)))) = I(s)(IA (+(x, s(0)))) =

= I(s)(I(+)(IA (x), IA (s(0)))) = I(s)(I(+)(A(x), IA (s(0))))
= I(s)(I(+)(3, I(s)(IA (0)))) = I(s)(I(+)(3, I(s)(I(0)))) =
= I(s)(I(+)(3, I(s)(0))) = I(s)(I(+)(3, 1)) =
= I(s)(4) = 5

4.3.3 Evaluación de fórmulas

Definición

Dada una estructura I = (U, I) de L y una asignación A sobre I, se define la función de evalu-
ación de fórmulas IA : Fórm(L) → B por

Si F es t1 = t2 , IA (F ) = H = (IA (t1 ), IA (t2 ))

Si F es P (t1 , . . . , tn ), IA (F ) = HI(P ) (IA (t1 ), . . . , IA (tn ))
Si F es ¬G, IA (F ) = H¬(IA (G))
Si F es G ∗ H, IA (F ) = H ∗ (IA (G), IA (H))

Si F es ∀xG, (
1, Si para todo u ∈ U se tiene IA[x/u] (G) = 1;
IA (F ) =
0, en caso contrario

41
 Si F es ∃xG, (
1, Si para todo u ∈ U tal que IA[x/u] (G) = 1;
IA (F ) =
0, en caso contrario

4.3.4 Conceptos auxilares para la evaluación de fórmulas

La función de verdad de la igualdad en U es la función H= : U 2 → B definida por
(
1, Si u1 = u2 ;
H= (u1 , u2 ) =
0, en caso contrario
Función de verdad de una relación: Si R es una relación n–aria en U (i.e. R ⊆ U n ), entonces la
función de verdad de R es la función HR : U n → B definida por
(
1, Si (u1 , . . . , un ) ∈ R;
H= (u1 , . . . , un ) =
0, en caso contrario
Variante de una asignación: Sea A una asignación en la estructura (U, I) y u ∈ U . Mediante
A[x/u] se representa la asignación definida por
(
u, Si y = x;
A[x/u](y) =
A(y), si y es distinta de x

Ejemplo 14

Evaluación de ∀x∃yP (x, y) en la estructura I = (U, I) tal que U = {1, 2} e I(P ) = (1, 1), (2, 2)

IA (∀x∃yP (x, y)) = V ⇔ IA[x/1] (∃yP (x, y)) = V y

IA[x/2] (∃yP (x, y)) = V
IA[x/1] (∃yP (x, y)) = V ⇔ IA[x/1,y/1] P (x, y) = V ó
IA[x/1,y/2] P (x, y) = V
IA[x/1,y/1] P (x, y) = P I (1, 1) = V
Luego, IA[x/1] (∃yP (x, y)) = V.
IA[x/2] (∃yP (x, y)) = V ⇔ IA[x/2,y/1] P (x, y) = V ó
IA[x/2,y/2] P (x, y) = V
IA[x/2,y/2] P (x, y) = P I (2, 2) = V
Luego, IA[x/2] (∃yP (x, y)) = V.
Por tanto, IA (∀x∃yP (x, y)) = V

4.3.5 Evaluación y variables libres

Sea t un término de L e I una estructura de L.

• Si A y B son dos asignaciones en I que coinciden sobre las variables de t, entonces IA (t) =
mathcalIB (t).
• Si t no tiene variables, entonces IA (t) = IB (t) para cualesquiera asignaciones A y B en I. Se suele
escribir simplemente I(t).

Sea F una fórmula de L e I una estructura de L.

• Si A y B son dos asignaciones en I que coinciden sobre las variables libres de F , entonces IA (F ) =
IB (F ).
• Si F es cerrada, entonces IA (F ) = IB (F ) para cualesquiera asignaciones A y B en I. Se suele
escribir simplemente I(F ).

42
4.3.6 Modelo de una fórmula
Sean F una fórmula de L e I una estructura de L.
• (I, A) es una realización de F si A es una asignación en I tal que IA (F ) = 1. Se representa por
IA |= F .
• I es un modelo de F si, para todo asignación A en I, IA (F ) = 1. Se representa por I |= F .

Ejemplo 15

Sea I = (N, I) una estructura tal que I(f ) = +eI(g) = ∗.

– Si A es una asignación en I tal que A(x) = A(y) = 2. Entonces IA |= f (x, y) = g(x, y),
– Si B es una asignación en I tal que B(x) = 1, B(y) = 2. Entonces IB |= f (x, y) = g(x, y),
– I |= f (x, y) = g(x, y)
– I |= f (x, y) = f (y, x)

4.3.7 Satisfacibilidad y validez

Definición

Sea F una fórmula de L.

– F es válida si toda estructura de L es modelo de F , (i.e. para toda estructura I de L y toda
asignación A en I se tiene que IA (F ) = 1). Se representa por |= F .
– F es satisfacible si tiene alguna realización (i.e. existe alguna estructura I de L y alguna
asignación A en I tales que IA (F ) = 1).
– F es insatisfacible si no tiene ninguna realización (i.e. para toda estructura I de L y toda
asignación A en I se tiene que IA (F ) = 0).

Ejemplo 16

• ∃xP (x) ∨ ∀x¬P (x) es válida.

• ∃xP (x) ∧ ∃x¬P (x) es satisfacible, pero no es válida.
• ∀xP (x) ∧ ∃x¬P (x) es insatisfacible.

• F es válida syss ¬F es insatisfacible.

F es válida
⇔ para toda estructura I y toda asignación A se tiene que IA (F ) = 1
⇔ para toda estructura I y toda asignación A se tiene que IA (¬F ) = 0
⇔ ¬F es insatisfacible.
• Si F es válida, entonces F es satisfacible.
F es válida
⇒ para toda estructura I y toda asignación A se tiene que IA (F ) = 1
⇒ existe una estructura I y una asignación A tales que IA (F ) = 1
⇒ F es satisfacible.

43
 • F es satisfacible ⇒ ¬F es insatisfacible.
∀xP (x) y ¬∀xP (x) son satisfacibles.
• Sea F una fórmula de L y x1 , . . . , xn las variables libres de F .
F es válida syss ∀x1 . . . ∀xn F es válida.
[∀x1 . . . ∀xn F es el cierre universal de F ].
F es satisfacible syss ∃x1 . . . ∃xn F es satisfacible.
[∃x1 . . . ∃xn F es el cierre existencial de F ].

4.3.8 Modelo de un conjunto de fórmulas

Notación: S, S1, S2, . . . representarán conjuntos de fórmulas.

Definición

Sean S un conjunto de fórmulas de L, I una estructura de L y A una asignación en I.

– (I, A) es una realización de S si A es una asignación en I tal que para toda F ∈ S se tiene
que IA(F ) = 1. Se representa por
IA |= S
– I es un modelo de S si para toda F ∈ S se tiene que I |= F (i.e. para toda F ∈ S y toda
asignación A en I se tiene IA(F ) = 1). Se representa por I |= S.

Ejemplo 17

• Sea S = {∀yR(x, y), ∀yf (x, y) = y}.

– (I, A) con I = (N, I), RI =≤, f I = +, A(x) = 0 es realización de S.
– (I, A) con I = (N, I), RI =<, f I = +, A(x) = 0 no es realización de S.

Ejemplo 18

• Sea S = {R(e, y), f (e, y) = y}.

– I = (N, I)conRI =≤, f I = +, eI = 0 es modelo de S.
– I = (N, I)conRI =<, f I = +, eI = 0 no es modelo de S.

4.3.9 Consistencia de un conjunto de fórmulas

Definición

Sea S un conjunto de fórmulas de L.

– S es consistente si S tiene alguna realización (i.e. existe alguna estructura I de L y alguna
asignación A en I tales que, para toda F ∈ S, IA (F ) = 1).
– S es inconsistente si S no tiene ninguna realización (i.e. para toda estructura I de L y toda
asignación A en I, existe alguna F ∈ S, tal que IA (F ) = 0).

Ejemplo 19

44
 • S = {∀yR(x, y), ∀yf (x, y) = y} es consistente. (I, A) con I = (N, I), RI =≤, f I = +, A(x) = 0 es
realización de S.
• S = {P (x) → Q(x), ∀yP (y), ¬Q(x)} es inconsistente.

 Propiedad. Sea S un conjunto de fórmulas cerradas de L. Entonces S es consistente syss S tiene

algún modelo.

4.3.10 Consecuencia lógica

Definición

Sean F una fórmula de L y S un conjunto de fórmulas de L. F es consecuencia lógica de S si todas

las realizaciones de S lo son de F . (i.e. para toda estructura I de L y toda asignación A en I, si
IA |= S entonces IA |= F ). Se representa por S |= F .
– Se escribe G |= F en lugar de {G} |= F .
– Se escribe G 6|= F en lugar de {G} 6|= F .

Ejemplo 20

• ∀xP (x) |= P (y)

• P (y) 6|= ∀xP (x)
(I, A) con I = (U, I), U = 1, 2, P I = 1, A(y) = 1.
• {∀x(P (x) → Q(x)), P (c)} |== Q(c)
• {∀x(P (x) → Q(x)), Q(c)} 6|= P (c)
(I, A) con I = (U, I), U = 1, 2, cI = 1, P I = 2, QI = 1, 2.
• {∀x(P (x) → Q(x)), ¬Q(c)} |= ¬P (c)
• {P (c), ¬P (d)} |= c 6= d

4.3.11 Consecuencia lógica e inconsistencia

S |= F syssS ∪ {¬F } es inconsistente.
S |= F
⇔ para toda estructura I de L y toda asignación A en I, si, para todo G ∈ S, IA (G) = 1 entonces
IA (F ) = 1.
⇔ para toda estructura I de L y toda asignación A en I, si, para todo G ∈ S, IA (G) = 1 entonces
IA (¬F ) = 0.
⇔ para toda estructura I de L y toda asignación A en I, existe alguna H ∈ S ∪ {¬F } tal que
IA (H) = 0.
⇔ S ∪ {¬F } es inconsistente.
Sean F una fórmula cerrada de L y S un conjunto de fórmulas cerradas de L. Entonces, son equiva-
lentes
• F es consecuencia lógica de S
• todos los modelos de S lo son de F .

45
4.3.12 Equivalencia lógica

Definición

Sean F y G fórmulas de L. F y G son equivalentes si para toda estructura I de L y toda asignación

A en I, IA (F ) = IA (G). Se representa por F ≡ G.

Ejemplo 20

• P (x) ≡ P (y).
I = ({1, 2}, I) con P I = {1}yA(x) = 1, A(y) = 2.
• ∀xP (x) ≡ ∀yP (y).
• ∀x(P (x) ∧ Q(x)) ≡ ∀xP (x) ∧ ∀xQ(x).
• ∃x(P (x) ∧ Q(x)) ≡ ∃xP (x) ∧ ∃xQ(x).
I = ({1, 2}, I) con P I = {1} y QI = {2}.

 Propiedades básicas de la equivalencia lógica:

– Reflexiva: F ≡ F
– Simétrica: Si F ≡ G, entonces G ≡ F
– Transitiva: Si F ≡ G y G ≡ H, entonces F ≡ H

• Principio de sustitución de fórmulas equivalentes:

 Propiedad . Si en la fórmula F 1 se sustituye una de sus subfórmulas G1 por una fórmula G2
lógicamente equivalente a G1 , entonces la fórmula obtenida, F2 , es lógicamente equivalente
a F1 .

Ejemplo 21

• F1 = ∀xP (x) → ∃xQ(x)

• G1 = ∀xP (x)
• G2 = ∀yP (y)
• F2 = ∀yP (y) → ∃xQ(x)

5 Formas normales
5.1 Forma normal conjuntiva
5.1.1 Definición de forma normal conjuntiva

Definición

Un átomo es una variable proposicional (ejemplo: p, q, . . . ).

Definición

46
 Un literal es un átomo o su negación (ejemplo: p, ¬p, q, ¬q, . . . ).
Notación: L, L1 , L2 , . . . representarán literales.

Definición

Una fórmula está en forma normal conjuntiva (FNC) si es una conjunción de disyunciones de
literales; es decir, es de la forma (L1,1 ∨ · · · ∨ L1,n1 ) ∧ · · · ∧ (Lm,1 ∨ · · · ∨ Lm,nm ).

Ejemplo 1

• (¬p ∨ q) ∧ (¬q ∨ p) está en FNC.

• (¬p ∨ q) ∧ (q → p) no está en FNC.

Definición

Una fórmula G es una forma normal conjuntiva (FNC) de la fórmula F si G está en forma normal
conjuntiva y es equivalente a F .

Ejemplo 2

• Una FNC de ¬(p ∧ (q → r)) es (¬p ∨ q) ∧ (¬p ∨ ¬r).

5.2 Forma normal disyuntiva

5.2.1 Definición de forma normal disyuntiva

Definición

Una fórmula está en forma normal disyuntiva (FND) si es una disyunción de conjunciones de
literales; es decir, es de la forma
(L1,1 ∧ · · · ∧ L1,n1 ) ∨ · · · ∨ (Lm,1 ∧ · · · ∧ Lm,nm ).

Ejemplo 7

• (¬p ∧ q) ∨ (¬q ∧ p) está en FND.

• (¬p ∧ q) ∨ (q → p) no está en FND.

Definición

Una fórmula G es una forma normal disyuntiva (FND) de la fórmula F si G está en forma normal
disyuntiva y es equivalente a F .

Ejemplo 8

Una FND de ¬(p ∧ (q → r)) es ¬p ∨ (q ∧ ¬r).

47
Bibliografı́a
[1] Calixto Badesa, Ramón Jansana Ferrer, and Ignacio Jané, Elementos de lógica formal, Ariel, 1998.

[2] ML Bonet, Apuntes de lpo, 2003.

[3] José Luis Fernández, A Manjarrés, and Francisco Javier Dı́ez, Lógica computacional, 2003.
[4] Jean H Gallier, Logic for computer science: foundations of automatic theorem proving, Courier Dover
Publications, 2015.

[5] Michael Huth and Mark Ryan, Logic in computer science: Modelling and reasoning about systems,
Cambridge university press, 2004.
[6] José A Alonso Jiménez and Marı́a J Hidalgo Doblado, Lógica matemática y fundamentos (2011–12).

48