MATEMATICA

DISCRETA - 1o de Grado en Ingeniera Inform

atica (2014/15)

Tema 1: Fundamentos de logica

TEORIA

Indice
1. Proposiciones y conectivas
1.1. Proposiciones . . . . . . . . . .
1.2. Conectivas u operadores logicos
1.3. Precedencia de conectivas . . .
1.4. Formalizacion de enunciados del
1.5. Operaciones con bits . . . . . .

.
.
.
.
.

1
2
2
3
4
4

2. Equivalencias proposicionales
2.1. Tautologas y contradicciones . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Consistencia de un conjunto de formulas . . . . . . . . . . . . . . . . . . . .
2.3. Equivalencias logicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
5
5
5

3. Reglas de inferencia para el C

alculo proposicional
3.1. Falacias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
8

. . . . .
. . . . .
. . . . .
lenguaje
. . . . .

. . . . .
. . . . .
. . . . .
natural
. . . . .

4. Predicados y cuantificadores
4.1. Predicados . . . . . . . . . . . . . . . . . . . . . .
4.2. Especificacion y cuantificacion de predicados . . .
4.3. Formalizacion de enunciados del lenguaje natural
4.4. Cuantificadores anidados . . . . . . . . . . . . . .
4.5. Negacion de cuantificadores . . . . . . . . . . . .
4.6. Reglas de inferencia con cuantificadores . . . . . .

1.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

8
8
9
10
10
11
11

Proposiciones y conectivas
El objeto de la Logica es el de estudiar las leyes de inferencia en los razonamientos.

El n
ucleo mas tradicional de la Logica es la Logica Clasica, que suele dividirse en Logica
Proposicional y Logica de Primer Orden (o Logica de Predicados). En este tema aprenderemos algunas nociones basicas de ambas teoras desde un punto de vista mas bien intuitivo.


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

1.1.

Proposiciones

on es una oracion enunciativa que es verdadera o falsa, pero no

Definicion: Una proposici
las dos cosas a la vez.
Ejemplos: Las siguientes oraciones son proposiciones:
Bruselas es la capital de Portugal.
Madrid es la capital de Espa
na.
1 + 1 = 2.
2 + 2 = 7.
Ejemplos: Las siguientes oraciones no son proposiciones:
Que hora es?
Estudiad!
x + 1 = 2.
x + y = z.
Notacion: Usaremos las letras P , Q, R, S, . . . para denotar las diferentes proposiciones.
Dichas letras se suelen denominar variables proposicionales.
Definicion: Se dice que el valor de verdad de una proposicion es 1 si dicha proposici
on es
verdadera, mientras que es 0 si es falsa.
Ejemplos:
Proposicion
Valor de verdad
2 + 2 = 4
1
2 = 3
0
1
Un perro es un mamfero
La Tierra es una tostada
0
Notacion: Usualmente denotaremos el valor de verdad de una proposicion mediante el uso
de corchetes dobles. Por ejemplo, si P =Un perro es un mamfero, entonces [[P ]] = 1.

1.2.

Conectivas u operadores l
ogicos

Cuestiones: Como generar nuevas proposiciones a partir de otras? Que valor de verdad
toma la nueva proposicion en funcion de los valores de las proposiciones que la integran?
Por una parte podemos considerar la negaci
on de una proposicion, que toma valor de
verdad contrario:
2


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

P
0
1

Negaci
on
P
1
0

Por otra parte, dadas dos proposiciones P y Q podemos unirlas con las conectivas
, , , , para crear nuevas proposiciones, con los siguientes valores de verdad:
P
0
0
1
1

Q
0
1
0
1

P Q P Q P Q P Q
0
0
1
1
0
1
1
0
0
1
0
0
1
1
1
1

P Q
0
1
1
0

Definicion:
P es la negaci
on de P y se lee no P .
P Q es la conjunci
on de P y Q y se lee P y Q.
P Q es la disyunci
on de P y Q y se lee P o Q.
P Q es la implicaci
on de P y Q y se lee P implica Q.
P Q es la bicondicional de P y Q y se lee P si y solo si Q.
P Q es la disyunci
on exclusiva de P y Q y se lee P o Q pero no ambos.
Definicion: Una f
ormula no es mas que la expresion obtenida por aplicacion de una o m
as
conectivas a varias variables proposicionales.
Observacion: Los posibles valores de verdad que puede tomar una formula se representan
en una tabla denominada tabla de verdad de la formula. En cada fila de dicha tabla se
representara el valor de verdad que toma la formula para una posible combinacion de valores
de verdad (llamada valoraci
on) de las variables proposicionales presentes en la formula.
Ejercicio: Realizar la tabla de verdad de la formula (P Q) R.

1.3.

Precedencia de conectivas

Cuestion: Como interpretar el orden de actuacion de mas de una conectiva?

Se usaran parentesis para fijar el orden. Si no se utilizan, el orden de prelacion sera:
Operador

Precedencia
1o
2o
3o
4o
5o
3


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

Ejemplo: P Q se interpreta como (P ) Q, y no como (P Q).

Ejemplo: P Q R se interpreta como P (Q R), y no como (P Q) R.

1.4.

Formalizaci
on de enunciados del lenguaje natural

Se denomina formalizaci
on el proceso mediante el que se expresan frases del lenguaje
natural en terminos de variables proposicionales y conectivas. Mediante dicho proceso se
pretende abstraer la estructura logica subyacente en el lenguaje natural.
as la
Ejercicio: Formaliza la siguiente frase: Si haces todos los ejercicios entonces aprobar
asignatura.
Ejercicio: Formaliza la siguiente frase: Solo si haces todos los ejercicios aprobaras la asignatura.
Ejercicio: Cual es la formalizacion de la siguiente frase?:
Puedes acceder a Internet desde el campus solo si estudias Graduado en Ingeniera Informatica o no eres alumno de primero.
Ejercicio: Formaliza la siguiente frase: La respuesta automatizada no se puede enviar cuando
el sistema de archivos esta lleno.
on
Definicion: En una implicacion P Q, solemos llamar a P el antecedente (o la condici
suficiente) de la implicacion, y a Q el consecuente (o la condici
on necesaria).
Observacion: Al formalizar un enunciado del lenguaje natural empleando la Logica de Proposiciones, distinguimos dos tipos de enunciados:
Enunciados at
omicos: aquellos que al no poder ser descompuestos en otros mas
simples son formalizados con una variable proposicional.
Enunciados moleculares: estan compuestos por otros mas simples, y son formalizados mediante formulas en las que aparecen conectivas.

1.5.

Operaciones con bits

Los ordenadores emplean bits para representar la informacion. Un bit es la unidad mnima
de informacion; puede tomar dos valores: 0 y 1. Una cadena de bits es una sucesion de
cero o mas bits. La longitud de la cadena es el n
umero de bits que la integran.
Manejaremos tres operaciones OR, AN D y XOR sobre cadenas de bits de la misma
longitud. Consisten en aplicar respectivamente los operadores logicos , y a los bits en
la misma posicion, como si fueran valores de verdad.
Ejercicio: Aplicar las operaciones OR, AN D y XOR a las cadenas 01 1011 0110 y 11 0001 1101.


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

2.
2.1.

Equivalencias proposicionales
Tautologas y contradicciones

Definicion: Una formula que siempre es verdadera, independientemente de los valores de verdad de las variables proposicionales que la integran, se denomina tautologa. Si una formula
es siempre falsa se denomina contradicci
on. Una formula que no es ni una tautologa ni
una contradiccion se denomina contingencia.
Ejercicio: Es la formula P P una tautologa, una contradiccion o una contingencia? Y
la formula P P ?

2.2.

Consistencia de un conjunto de f
ormulas

A menudo se desea conocer si un conjunto de formulas es consistente, en el sentido de

que exista una asignacion de valores de verdad a las variables proposicionales con la que
todas las formulas sean verdaderas.
Ejercicio: Determinar la consistencia del conjunto de especificaciones de sistema siguiente:
El mensaje de diagnostico se almacena en memoria o se vuelve a transmitir , El mensaje
de diagnostico no se almacena en memoria, Si el mensaje de diagnostico se almacena en
memoria, entonces se vuelve a transmitir .
nade El mensaje de diagnostico no se vuelve a transmitir. ?
Ejercicio: Que pasa si se a

2.3.

Equivalencias l
ogicas

ogicamente equivalentes si
Definicion: Dos proposiciones (o formulas) P y Q se dicen l
P Q es una tautologa, es decir, si P y Q tienen los mismos valores de verdad. Dicha
equivalencia se denotara por P Q.
Observacion: Para formulas con n variables proposicionales las tablas de verdad son de 2n
filas. Cuando n es un poco grande construir tablas de verdad no es un procedimiento viable.
Una alternativa es emplear equivalencias logicas conocidas, que nos permiten sustituir unas
formulas por otras equivalentes mas simples.
Notacion: En la tabla siguiente el smbolo T denota una tautologa, mientras que el smbolo
C denota una contradiccion.


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

Equivalencias de formulas en las que aparecen , y :

Equivalencia
Nombre
P T P;
P CP
Leyes de identidad
P T T;
P CC
Leyes de dominacion
P P P;
P P P
Leyes de idempotencia
(P ) P
Ley de la doble negacion
P Q Q P;
P QQP
Leyes conmutativas
(P Q) R P (Q R);
(P Q) R P (Q R)
Leyes asociativas
(P Q) R (P R) (Q R);
(P Q) R (P R) (Q R)
Leyes distributivas
(P Q) P Q;
(P Q) P Q
Leyes de De Morgan
P (P Q) P ;
P (P Q) P
Leyes de absorcion
P P C;
P P T
Leyes de negacion

Las diez leyes anteriores conforman el Algebra

de Boole del Calculo proposicional.
Ejercicio: Justificar que las formulas (P (P Q)) y Q P son equivalentes.
Equivalencias de formulas en las que ademas aparecen y :
(E1) P Q P Q.

(E8) (P R) (Q R) (P Q) R.

(E2) P Q P Q.

(E9) P Q (P Q) (Q P ).

(E3) P Q (P Q).

(E10) P Q Q P .

(E3) (P Q) P Q.
(E11) P Q P Q.
(E4) P Q (P Q).
(E5) (P Q) (P R) P (Q R).

(E12) P Q (P Q) (P Q).

(E6) (P R) (Q R) (P Q) R. (E13) (P Q) P Q.
(E7) (P Q) (P R) P (Q R). (E14) P Q Q P .
Ejercicio: Comprobar si (P Q) [(Q P ) P ] P.


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

3.

Reglas de inferencia para el C

alculo proposicional

Las reglas de inferencia son los procedimientos utilizados para deducir conclusiones a
partir de afirmaciones. Es decir, enlazan los pasos dados en una demostracion.
Reglas de inferencia del Calculo proposicional:
Regla de inferencia
P
P Q
P Q
P
P
Q
P Q
P
P Q
Q
Q
P Q
P
P Q
QR
P R
P Q
P
Q
P Q
P R
QR

Tautologa

Nombre

P (P Q)

Adicion

(P Q) P

Simplificacion

((P ) (Q)) (P Q)

Conjuncion o ley de combinacion

(P (P Q)) Q

Modus ponens

(Q (P Q)) P )

Modus tollens

((P Q) (Q R)) (P R)

Silogismo hipotetico

((P Q) P ) Q

Silogismo disyuntivo

((P Q) (P R)) (Q R)

Ley de resolucion

Ejercicio: En que regla de inferencia se basa el siguiente argumento?

Si llueve hoy, entonces hoy no haremos barbacoa. Si no hacemos una barbacoa hoy, haremos una barbacoa ma
nana. Por tanto, si hoy llueve, haremos una
barbacoa ma
nana.
Definicion: Un argumento deductivo se dice correcto si siempre que todas las hipotesis son
verdaderas, la conclusion tambien lo es. En tal caso se dice que la conclusion es consecuencia l
ogica de las hipotesis.
Observacion: As, demostrar que Q se deduce de P1 , P2 , . . . , Pn es lo mismo que demostrar
que la implicacion (P1 P2 . . . Pn ) Q es una tautologa.


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

Notacion: Es habitual el uso de la notacion {P1 , P2 , . . . , Pn } |= Q para denotar que una

proposicion Q es consecuencia logica de las hipotesis P1 , P2 , . . . , Pn .
Ejercicio: Demostrar que las hipotesis:
Esta tarde no hace sol y hace mas fro que ayer
Iremos a nadar solo si hace sol
Si no vamos a nadar, daremos un paseo en barca
Si damos un paseo en barca, estaremos en casa a la puesta de sol
conducen a: Estaremos en casa a la puesta de sol
Ejercicio: Dadas las hipotesis: Si me mandas un mensaje por correo electronico, entonces
acabare de escribir el programa, Si no me mandas un mensaje por correo electronico, me
ire a casa temprano, Si me voy a casa temprano, me levantare descansado; deducir que
Si no acabo de escribir el programa, me levantare descansado.

3.1.

Falacias

Falacias o razonamientos incorrectos frecuentes:

Afirmar el consecuente: [(P Q) Q] P . No es una tautologa, pues es falsa
cuando P es falsa y Q verdadera.
Negar el antecedente: [(P Q) P ] Q. No es una tautologa, pues es falsa
cuando P es falsa y Q verdadera.
Ejercicio: Son correctos los argumentos siguientes?
Si haces los ejercicios propuestos por el profesor, aprenderas Matematica Discreta.
Has aprendido Matematica Discreta, luego hiciste los ejercicios propuestos por el profesor .
Si haces los ejercicios propuestos por el profesor, aprenderas Matematica Discreta. No
has hecho los ejercicios propuestos por el profesor, luego no has aprendido Matem
atica
Discreta.

4.
4.1.

Predicados y cuantificadores
Predicados

Observacion: Pueden encontrarse muchos ejemplos de razonamientos correctos cuya validez

no puede ser establecida mediante una formalizacion en Logica de proposiciones. La Logica
de predicados refina la Logica de proposiciones, permitiendo analizar con mas profundidad
estos razonamientos.
Ejemplos: Los siguientes razonamientos son correctos:
8


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

Algunos estudiantes viven en este barrio. Todos los habitantes de este barrio compran
en mi tienda. Luego algunos estudiantes compran en mi tienda.
El norteamericano K. Rosen es autor de un libro de la bibliografa. Los libros de la
bibliografa estan disponibles en la biblioteca. Luego alg
un norteamericano es autor de
alg
un libro que esta en la biblioteca.
Notacion de predicado: Emplearemos la notacion P (x) para formalizar oraciones en las que
se enuncia que un individuo x cumple una propiedad P . Por tanto P (x) se leera x tiene la
propiedad P .
Definicion: El universo de discurso de un razonamiento se corresponde con el conjunto
de individuos o elementos sobre los que se realiza el razonamiento.
Definicion: Un predicado se corresponde con una familia de proposiciones, una proposici
on
P (x) para cada elemento x del universo de discurso U.
Ejemplos:
1. P (x) = x + 2 = 11 en el universo de discurso de los n
umeros enteros.
2. R(x) = x tiene dos patas en el universo de discurso de todos los mamferos.
3. Q(x, y) = x tiene y patas en el universo de todos los pares (x, y) donde x es un
mamfero e y es un n
umero natural.
Observacion: Un predicado no es una proposicion porque no tiene sentido asignarle un valor
de verdad verdadero o falso. A continuacion veremos tres maneras en que se pueden construir
proposiciones a partir de predicados.

4.2.

Especificaci
on y cuantificaci
on de predicados

Definicion: El proceso por el que dado un predicado P (x) junto con un objeto a del universo de
discurso, se obtiene la proposicion P (a) se denomina especificaci
on o particularizaci
on
del predicado.
Ademas de la especificacion existen otras dos proposiciones obtenidas a partir de un
predicado y del uso de dos nuevos smbolos logicos ( y ):
x[P (x)] tiene el valor de verdad 1 si y solo si P (a) tiene el valor de verdad 1 para
alg
un objeto a del universo U.
x[P (x)] tiene el valor de verdad 1 si y solo si P (a) tiene el valor de verdad 1 para
todo objeto a del universo U.
Definicion: El smbolo se denomina cuantificador existencial y se lee existe.
Definicion: El smbolo se denomina cuantificador universal y se lee para todo.
Ejemplos: Consideremos los predicados P (n) = n es par e I(n) = n es impar en el
universo de los enteros.
9


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

n[P (n)] tiene valor de verdad 1, pues P (0) tiene valor de verdad 1.
n[P (n)] tiene valor de verdad 1 en el universo de los enteros pares. Pero que valor
de verdad tiene en el universo de todos los enteros?

4.3.

Formalizaci
on de enunciados del lenguaje natural

Traducir frases del lenguaje natural a expresiones logicas es una tarea crucial en diversos
campos, en particular en el de la Ingeniera Informatica.
Ejercicio: Formalizar la frase:
Todo estudiante de esta clase ha estudiado Calculo.
Ejercicio: Considerando como universo de discurso el conjunto de criaturas, formalizar las
frases:
Todos los leones son fieros.
Algunos leones son fieros.
Ning
un leon es fiero.
Algunos leones no toman cafe.
Algunas criaturas fieras no toman cafe.
Cuestion: Por que la cuarta sentencia no se puede expresar como x[L(x) C(x)]?

4.4.

Cuantificadores anidados

Definicion: Un cuantificador anidado es un cuantificador que se localiza dentro del rango

de aplicacion de otros.
Ejemplos:
1. xy [x + y = y + x], con los n
umeros reales como universo del discurso (Propiedad
conmutativa de la suma).
2. xyz [(x + y) + z = x + (y + z)], con los n
umeros reales como universo del discurso
(Propiedad asociativa de la suma).
3. Sean O(x) = x tiene ordenador y A(x, y) = x e y son amigos en el universo de los
alumnos de la Escuela de Ingenieras. x[O(x) y[O(y) A(x, y)]] = cada estudiante
de la Escuela tiene ordenador o un amigo en la Escuela que lo tiene.
Ejercicio: Considerando como universo de discurso el conjunto de las personas, formalizar
la frase: Si una persona es del sexo femenino y tiene un hijo, esta persona es madre de
alguien.
10


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

4.5.

Negaci
on de cuantificadores

Leyes de negacion de cuantificadores:

Dado un predicado P (x) definido sobre un universo U se tienen dos equivalencias logicas:
(x[P (x)]) x[P (x)]
(x[P (x)]) x[P (x)]
Demostracion: Veamos que en cada caso las formulas tienen los mismos valores de verdad.
Suponiendo que x[P (x)] es verdadera, se cumplira que P (a) es verdadera para cada
a del universo, por particularizacion del universal. Es decir, P (a) es falsa para cada a del
universo, luego no existe ning
un a en el universo tal que P (a) sea verdadera. O en otras
palabras, x[P (x)] es falsa, luego (x[P (x)]) es verdadera.
Ejercicio: Terminar la demostracion.
Observacion: La negacion de sentencias con cuantificadores anidados se realiza aplicando
sucesivamente las reglas de negacion a sentencias con un u
nico cuantificador.
Ejercicio: Expresa la negacion de xy [xy = 1] de forma que ninguna negacion preceda a
un cuantificador.
Ejercicio: Expresa con cuantificadores No existe ninguna mujer que haya viajado en un
vuelo de cada una de las lneas aereas del mundo.

4.6.

Reglas de inferencia con cuantificadores

Las reglas de inferencia sobre predicados con cuantificadores se basan en las propiedades
de generalizacion y particularizacion del universal y del existencial:
Generalizaci
on del universal: Para probar que x[P (x)] tiene el valor de
verdad 1, basta tomar un objeto fijo pero arbitrario c en el universo y probar que
la proposicion P (c) tiene valor de verdad 1.
Generalizaci
on del existencial: Para probar que x[P (x)] tiene el valor de
verdad 1, basta probar que existe un objeto c en el universo tal que la proposicion
P (c) tiene valor de verdad 1.
Particularizaci
on del universal: Supongase que x[P (x)] tiene el valor de
verdad 1 y consideremos c en el universo del discurso. Entonces la proposicion
P (c) tiene valor de verdad 1.
Particularizaci
on del existencial: Si x[P (x)] tiene el valor de verdad 1, entonces existe alg
un objeto c en el universo del discurso tal que la proposicion
P (c) tiene valor de verdad 1.

11


MATEMATICA
DISCRETA - 1o de Grado en Ingeniera Inform
atica (2014/15)

Regla de inferencia

Nombre

x[P (x)]
P (c) para cualquier c arbitrario (o concreto)

Particularizacion del universal

P (c) para cualquier c arbitrario

x[P (x)]

Generalizacion del universal

x[P (x)]
P (c) para un c concreto

Particularizacion del existencial

P (c) para un c concreto (o arbitrario)

x[P (x)]

Generalizacion del existencial

Ejercicio: Mostrar que las siguientes premisas Un estudiante de este grupo no ha ledo los
apuntes y Todo el mundo en este grupo aprobo el primer examen, implican Alguien que
aprobo el primer examen no ha ledo los apuntes.

12