Download escuela de computación - Ing. Gerardo Alberto Leal, MSc

FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
UNIDAD 1: FUNDAMENTOS DE LA LÓGICA
1.1 Proposiciones Lógicas
La lógica es una disciplina que busca modelar las leyes del pensamiento
humano. La lógica proposicional es un área de la matemática que permite el
razonamiento de enunciados y sentencias matemáticas. Son reglas que:
- Dan significado a enunciados y sentencias matemáticas.
- Distinguen argumentos validos y no validos.
- Se aplican en la construcción de programas, modelado de algoritmos, estructuras
de datos y circuitos de computadores.
Las Proposiciones Lógicas son oraciones declarativas que pueden ser
verdaderas o falsas pero no ambas a la vez.
Ejemplo:
a.- Maracaibo es la capital del Estado Zulia
b.- Bachaquero es la capital del Municipio Lagunillas
c.- 2 + 2 = 4
d.- 3 + 3 = 9
Todas son proposiciones, a y c verdaderas; b y d falsas.
Ejemplo:
a.- Que día es hoy?
b.- Lee esto con atención
c.- X + 1 = 2
d.- X + Y = Z
En este caso a y b no son proposiciones porque no son declaraciones, por
otra parte, c y d no son proposiciones porque no son ni verdaderas, ni falsas.
Las Proposiciones se denotan con letras minúsculas p, q, r y s. Tiene dos
posibles valores llamados Valor de Verdad, que pueden ser V = verdadero y F =
Falso. Para simplificar el análisis, los valores verdaderos se asocian con el
número 1 y los falsos con el número 0 del sistema binario aplicado en
computación.
La Tabla de la Verdad muestra las relaciones entre los valores de verdad de las
proposiciones.
p
1
0
q
1
0
R
0
1
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
1
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
1.2 Operadores y Conectivos Lógicos
Los Operadores Lógicos, son operadores aplicados a las proposiciones,
para generar nuevas proposiciones compuestas por dos o mas proposiciones
simples. Los Conectivos Lógicos, son operadores lógicos que se usan para
formar nuevas proposiciones a partir de 2 o mas proposiciones existentes.
Los Tipos de Operadores Lógicos son:
a. Negación: sea p una proposición, el enunciado << no se cumple p >> es otra
proposición llamada “Negación de p”. Se denota: ¬p y se lee <<no p >>. Su tabla
de verdad es:
P
¬p
1
0
0
1
b. Conjunción: sean p y q proposiciones. La proposición << p y q >>, denotada
por p q, es la proposición que es verdadera cuando tanto p como q son
verdaderas y falsa en cualquier otro caso. Su tabla de verdad es:
p q p q
0 0
0
0 1
0
1 0
0
1 1
1
Ejemplo: p << hoy es viernes >>
q << hoy llueve >>
p q<< hoy es viernes y hoy llueve >>
Verdadera: Los viernes con lluvia
Falsa: Cualquier otro día diferente de viernes y los viernes que no llueve
c. Disyunción: sean p y q proposiciones. La proposición << p o q >>, denotada
por p q, es la proposición que es falsa cuando tanto p como q son falsas y
verdadera en cualquier otro caso. Su tabla de verdad es:
p q p q
0 0
0
0 1
1
1 0
1
1 1
1
Ejemplo: p << hoy es viernes >>
q << hoy llueve >>
p q<< hoy es viernes u hoy llueve >>
Verdadera: Cualquier día que sea viernes o llueva, incluyendo viernes que llueva..
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
2
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
Falsa: Los días que ni son viernes, ni llueve.
d. Disyunción Excluyente u O-Excluyente: sean p y q proposiciones. La
proposición << p o q (pero no ambas) >>, denotada por p q, es la proposición
que es verdadera cuando solo una de las dos proposiciones p y q es verdadera; y
es falsa cuando ambas son verdaderas o ambas son falsas. Su tabla de verdad
es:
p q p q
0 0
0
0 1
1
1 0
1
1 1
0
Ejemplo: p << hoy es viernes >>
q << hoy llueve >>
p q<< hoy es viernes u hoy llueve >>
Verdadera: Cualquier otro día que sea viernes o llueva, pero no ambos.
Falsa: Los viernes que llueve, los otros días que no llueve.
1.3 Implicaciones y Bicondicionales:
Sean p y q proposiciones. La implicación pq es la proposición que es
falsa cuando p es verdadera y q es falsa; y es verdadera en cualquier otro caso.
(Hipótesis o Causa) p q (Conclusión o Consecuencia)
Su tabla de verdad es:
p
0
0
1
1
q
0
1
0
1
pq
1
1
0
1
Las formas de expresar el condicional p q son:
<< si p, entonces q >>, << p implica q >>, << q si p >>, << p solo si q >>,<< q
siempre que p>>
Ejemplo:
<< si soy elegido, entonces bajare los impuestos >>
Si el político es elegido (p es verdadera), no baja los impuestos (q es falsa), las
expectativas son falsas. (p q es F)
Otras implicaciones derivadas de p q son:
-Reciproca de p q:
q p
-Contrarreciproca de p q: ¬q ¬p
-Inversa de p q:
¬p ¬q
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
3
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
Tablas de verdad:
q
0
0
1
1
p
0
1
0
1
qp
1
1
0
1
¬q
0
0
1
1
¬p
0
1
0
1
¬q¬p
1
1
0
1
¬p ¬ q
0 0
0 1
1 0
1 1
¬p¬q
1
1
0
1
Reciproca
Contrarreciproca
Inversa
Ejemplo:
Cuales son las contrarreciproca, reciproca e inversa de la implicación:
<< el equipo gana siempre que llueve >>
Se identifican la causa y la consecuencia: p q
<< si llueve, entonces el equipo local gana >>
Contrarreciproca: ¬q¬p << si el equipo no gana, entonces no llueve >>
Reciproca: qp << si el equipo gana, entonces llueve >>
Inversa: ¬p¬q << si no llueve, entonces el equipo no gana >>
Sean p y q proposiciones, el Bicondicional o Doble Implicación, p q es la
proposición que es verdadera cuando p y q tienen los mismos valores de verdad y
falsa en los otros casos.
Su tabla de verdad es:
p
0
0
1
1
q
0
1
0
1
pq
1
0
0
1
La proposición p q, es verdadera cuando p q y q p son verdaderas. Las
formas de expresar el bicondicional p q son:
<< p si, y solo si q >>,<< p es necesario y suficiente para q >>,<< p sii q >>
Ejemplo:
p << puedes tomar el vuelo>>
q << compras un pasaje>>
p q << puedes tomar el vuelo si, y solo si compras un pasaje>>
.Esta expresión es verdadera si p y q son ambas verdaderas o ambas falsas.
1.4 Precedencia de Operadores Lógicos
Orden en que se aplican en la construcción de formulas, cuando no se usan
paréntesis:
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
4
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
Orden
1
2
3
4
5
Operador
¬




Nombre
Negación
Conjunción
Disyunción
Implicación
Bicondicional
¬p q equivale (¬p) q (Negación precede a la conjunción)
p q 
q)  r (Conjunción precede a la disyunción)
p q r equivale (p q) q (Disyunción precede a la implicación)
1.5 Traducción de Frases del Lenguaje Natural:
Consiste en pasar del lenguaje natural al lenguaje formal, se conoce como
Formalización.
Ejemplo:
Cual es la formalización de la frase: << puedes acceder a Internet desde el
laboratorio solo si estudias computación o no eres alumno de primero >>
p << puedes acceder a Internet desde el laboratorio >>
q<< estudias computación >>
r<< eres alumno de primero>>
Formalización: p q ¬r)
Ejemplo:
Cual es la formalización de la siguiente frase: << No puedes montarte en la
montaña rusa si mides menos de 1,2 Mts a no ser que seas mayor de 16 años>>
q << Puedes montarte en la montaña rusa >>
r << Mides mas de 1,2 Mts >>
s << Eres mayor de 16 años >>
Formalización: (r ¬s) ¬q
1.6 Equivalencias Proposicionales
Dos formulas son lógicamente equivalentes si tienen los mismos valores
de verdad en todos los casos. También se dice que p y q son lógicamente
equivalentes si p q es una tautología y se denota por p  q
Ejemplo:
p
1
0
¬p
1
0
Tautología Contradicción
p¬p
p¬p
1
0
1
0
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
5
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
Ejemplo:
Utilizando tablas de verdad determinar si las proposiciones ¬(pq) y ¬p¬p son
lógicamente equivalentes.
p q p q
¬p
¬q
¬ (p q)
¬p¬q
V V
V
F
F
F
F
V F
V
F
F
V
F
F V
V
F
V
F
F
F F
F
V
V
V
V
¬(pq)  ¬p¬p
Los siguientes son términos utilizados para la denominación de algunas
formulas lógicas, en función de los valores que se tienen en su tabla de verdad.
Tautología:
Es una formula proposicional que es siempre verdadera no importa los
valores de verdad de las proposiciones que la componen.
Contradicción:
Es una formula proposicional que es siempre falsa no importa los valores de
verdad de las proposiciones que la componen.
Contingencia:
Es una formula proposicional que no es tautología ni contradicción.
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
6
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
1.7 Ejercicios Propuestos de la Unidad 1:
1.- ¿Cuales de las siguientes frases son proposiciones? ¿Cual es el valor de
verdad de aquellas que son proposiciones?
a) Bogota es la capital de Colombia.
b) 2 + 3 = 5
c) 5 + 7 = 10
d) Responde a esta pregunta.
e) x + y = y + x para todo par real x e y.
f) ¿Qué hora es?
g) 4 + x = 5
h) x + 1 = 5 si x = 1
i) x + y = y + z si x = z
2.- ¿Cual es la negación de cada uno de los siguientes enunciados?
a) Hoy es martes.
b) No hay contaminación en C.Ojeda.
c) 2 + 1 = 3
d) El clima en Mérida es calido y soleado.
3.- Sean p y q los enunciados.
p: Compre un ticket de lotería esta semana.
q: Gane el premio de 10 Millones de Bolívares del viernes.
Expresa cada una de las formulas siguientes en lenguaje natural:
a) p b) p q
c) p q
d) p q e) p q
f) p q
4.- Sean p, q y r los enunciados «Tienes fiebre», «Suspendes el examen final» y
«Apruebas el curso» respectivamente. Expresa cada una de las siguientes
formulas en lenguaje natural.
a) p q
b) q rc) q r
d) (p r) (q r)
5.- Sean p y q los enunciados «Conduces a mas de 100 Km. por hora» y «Te
multan por exceso de velocidad», respectivamente. Escribe los siguientes
enunciados usando p, q y conectivos lógicos:
a) Conduces a más de 100 Km. por hora, pero no te multan por exceso de
velocidad.
b) Te multaran por exceso de velocidad si conduces a más de 100 Km. Por
hora.
c) Si no conduces a mas de 100 Km. por hora no te multarán por exceso de
velocidad.
6.- Sean p, q y r los enunciados «Se han visto osos pardos por la zona», «Es
seguro caminar por el sendero» y «Las bayas del sendero están maduras»,
respectivamente. Escribe los siguientes enunciados usando p, q, r y conectivos
lógicos:
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
7
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
a) Las bayas del sendero están maduras, pero no se han visto osos pardos
por la zona.
b) No se han visto osos pardos por la zona y es seguro caminar por el
sendero, pero las bayas del sendero están maduras.
c) Si las bayas del sendero están maduras, es seguro caminar por el
sendero si y solo si, no se han visto osos pardos por la zona.
7.- Determina si estas implicaciones bicondicionales son verdaderas o falsas:
a) 2 + 2 = 4 si y solo si, 1 + 1 = 2
b) 1 + 1 = 2 si y solo si, 2 + 3 = 4
c) 0 > 1 si y solo si, 2 > 1
8.- Determina si estas implicaciones son verdaderas o falsas:
a) Si 1 + 1 = 2, entonces 2 + 2 = 5
b) Si 1 + 1 = 3, entonces 2 + 2 = 4
c) Si 1 + 1 = 3, entonces 2 + 2 = 5
9.- Escribe cada uno de estos enunciados de la forma «si p, entonces q».
a) Es necesario lavar el carro del jefe para ascender.
b) Puedes acceder a la página Web si pagas una cuota de suscripción.
c) Pedro se marea siempre que se monta en un barco.
10.- Escribe cada uno de estos enunciados de la forma «p si, y sólo si, q».
a) Para ganar la rifa es necesario y suficiente tener el número ganador.
b) Ascenderás solo si tienes contactos, y tienes contactos solo si asciendes.
c) Si ves televisión tu mente se empobrecerá y viceversa.
11.- Enuncia la reciproca, contrarreciproca e inversa de cada una de estas
implicaciones:
a) Si nieva hoy, esquiare mañana.
b) Voy a clase siempre que vaya a haber un examen.
c) Si llueve esta noche me quedare en casa.
12.- Escribe cada uno de estos enunciados de la forma <<si p, entonces q>> y
luego determina en cada caso la implicación que se pide adjunta a la proposición
dada.
- Practicar a diario le permitirá a Daniela ganar el torneo. (Reciproca)
- Marta puede usar la bicicleta al utilizar el casco. (Inversa)
- Roberto no va a la universidad cuando llueve. (Contrareciproca)
13.- Construye la tabla de la verdad para cada una de las siguientes formulas:
a) p q
b) p q)q
c) (p q) (p q)
d) (pq) q  p)
e) (pq)p q)
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
8
FACULTAD DE INGENIERÍA
ESCUELA DE COMPUTACIÓN
ESTRUCTURAS DISCRETAS (IC33)
PROFESOR: ING. GERARDO ALBERTO LEAL, MSc.
14.- Construye la tabla de la verdad para cada una de las siguientes formulas:
a) (p q) r
b) (p q) r
c) (p q) r
d) p q r)
e) (p q) qr)
15.- Utiliza tablas de verdad para verificar las siguientes equivalencias:
a) p 1 p
b) p  q q  p c) p q q p
d) (p  q)r p  (qr)
16.- Demuestra que cada una de estas implicaciones es una tautología.
a) ((p q)  (q r)) p r)
b) ((p q)  (p r) q r)) r
17.- Una expresión lógica tiene como causa que <<5 + 3 es igual a 8 ó 9 +5 es
igual a 13>>; y como consecuencia que <<estructuras discretas es del 5to
semestre e ingeniería de computación tiene turno nocturno>>. Para la expresión
dada:
a) Define las variables proposicionales la conforman
b) Escribe una formula proposicional basada en variables y conectores lógicos
c) Determina analíticamente al valor de verdad de la expresión.
d) Escribe la inversa de dicha expresión
18.- Sean las proposiciones p « Tienes Fiebre», q «No suspendes el Examen»,
r «Apruebas la asignatura». Expresa en Lenguaje Natural la expresión:
((p q) (p r))
19.- Dada la expresión «Tendrás un 20 en la asignatura si, y solo si, tienes un
20 en el examen o haces todos los problemas de la guía» Expresar el
enunciado a través de una formula propocicional con conectores lógicos.
20.- Determinar la tabla de verdad para la siguiente expresión lógica:
[(p q) (p q)] (p q)
Modulo Instruccional Estructuras Discretas. Teoría y Práctica
9