UNIDAD 1_LOGICA_2016

Vista previa del material en texto

UNIDAD I 
ESTRUCTURA DEL PENSAMIENTO LÓGICO 
TEORIA 
 
 
MATEMATICA DISCRETA 
2016 
 Es la disciplina que trata sobre los métodos de 
razonamiento, proporcionando reglas y técnicas 
para determinar si un razonamiento es o no válido 
 Se emplea en Matemáticas para demostrar 
Teoremas; en informática para verificar si son o no 
correctos los programas; en las ciencias físicas para 
sacar conclusiones de experimentos; etc…. 
VIDEO MOTIVADOR 
https://www.youtube.com/watch?v=YlY4sQBV4-g 
 
 
 QUE ES LA LOGICA? 
UNIDAD I - 2016 
https://www.youtube.com/watch?v=YlY4sQBV4-g
https://www.youtube.com/watch?v=YlY4sQBV4-g
https://www.youtube.com/watch?v=YlY4sQBV4-g
CONTENIDO 
 Proposiciones y Conectivos 
 Leyes Lógicas: Equivalencias e 
Implicaciones lógicas 
 Razonamientos 
Métodos de Demostración 
 Principio de Inducción Matemática 
UNIDAD I - 2016 
PROPOSICIÓN: Definición y clasificación 
Proposición es 
cualquier oración 
afirmativa de la cual 
puede decirse 
verdadero o falso, 
pero no ambas. 
Se dice que una 
proposición posee 
Valor de Verdad 
Se 
clasifican 
en 
Simples 
Las que consisten 
en un única 
afirmación 
Se denotan con 
letras minúsculas: 
Por ejemplo: 
p, q , r , .. 
Compuestas 
Son las 
afirmaciones que 
combinan 
proposiciones 
simples 
UNIDAD I - 2016 
Conectivos 
Las proposiciones compuestas son 
generadas por la presencia de 
conectivos lógicos 
los cuales son: 
Negación: ¬ 
Conjunción: ∧ 
Disyunción incluyente: ∨ 
Disyunción excluyente: ∨ 
Condicional: → 
Bicondicional:↔ 
Llamaremos Expresión Lógica a toda proposición 
ya sea simple o compuesta. Las denotaremos con 
letras mayúsculas A, B, C, etc 
C
O
N
EC
TI
V
O
S
 
LO
G
IC
O
S
 
Negación: ¬p No p 
Conjunción: p∧q p y q ( p además de q) 
Disyunción 
incluyente: p∨q 
p o q 
Disyunción 
excluyente:p ∨q 
p o q pero no ambas 
Condicional: 
p→q 
Si p entonces q. (Si p, q) 
 p solo si q (Solo si q, p) 
Es suficiente p para q 
Es necesario q cuando p 
Cuando sucede p, sucede q 
Q sucede, siempre que p sucede 
Bicondicional: 
p↔q 
p si y solo si q. 
p es suficiente y necesario para q 
ACTIVIDAD Nº1 
 Exprese las siguientes frases en forma simbólica 
 
a) Luis se traslada en moto y usa casco 
b) Ni Luis se traslada en moto ni usa casco 
c) Luis se traslada en moto o usa casco 
d) Si Luis se traslada en moto, entonces usa casco 
e) Luis se traslada en moto si y solo si usa casco 
 
 
 
 
UNIDAD I - 2016 
TABLAS DE VERDAD 
 
p p p q pq pq pq pq p q 
v F V V V V F V V 
F V V F F V V F F 
F V F V V V F 
F F F F F V V 
Son arreglos que representan todas las combinaciones posibles de 
valores de verdad de una expresión lógica en función de los valores 
de verdad de las prop. simples intervinientes. Si la proposición 
compuesta tiene n variables proposicionales, entonces la tabla tendrá 
2n renglones 
 
Las tablas de verdad para las expresiones lógicas p, pq, pq , 
pq , pq y p q son: 
 
 
 
 
 
 
 
 
 
ACTIVIDAD Nº2 
 Analizar los posibles valores de verdad de las 
proposiciones siguientes 
 
a) Luis se traslada en moto y usa casco 
b) Ni Luis se traslada en moto ni usa casco 
c) Luis se traslada en moto o usa casco 
d) Si Luis se traslada en moto, entonces usa casco 
e) Luis se traslada en moto si y solo si usa casco 
 
 
 
 
UNIDAD I - 2016 
ANALISIS DE UNA EXPRESION LOGICA 
COMPUESTA - CONECTIVO PRINCIPAL 
 Llamamos conectivo principal al conectivo que da el valor 
de verdad final de la proposición compuesta 
 En una expresión lógica completamente entre paréntesis 
es claro quien es el conectivo principal 
 Ejercicio: ¿Cuál es el conectivo principal en las siguientes 
expresiones lógicas? 
 
(p q) 
(p  q) (s p) 
(pq)((rp)q) 
 
UNIDAD I - 2016 
 En una expresión sin paréntesis hay que respetar la 
REGLA DE PRIORIDAD. 
 
 Ella indica que la prioridad de mayor a menor está 
dada por el siguiente orden: 
     
 Ejercicio: Determinar el conectivo principal en las 
siguientes afirmaciones 
 
pqr 
pqr 
pqrs 
TAUTOLOGÍAS, CONTRADICCIONES Y CONTINGENCIAS 
 Una expresión lógica verdadera para todas las 
combinaciones posibles de sus variables se llama 
tautología. 
 
 Una expresión lógica falsa para todas las 
combinaciones posibles de sus variables se llama 
contradicción. 
 
 Una expresión lógica que no es tautología ni 
contradicción se llama contingencia. 
 
UNIDAD I - 2016 
Actividad Nº3 
 Analizar si las siguientes expresiones lógicas son 
tautologías , contradicciones o contingencias 
 
a) p  p 
b) p  p 
c) (p  q)p 
d) p (p  q) 
 
UNIDAD I - 2016 
EQUIVALENCIA LÓGICA 
 Dos expresiones lógicas A y B son equivalentes si y solo si 
tienen los mismos valores de verdad para cada una de las 
posibilidades de valores de verdad de las prop simples 
que intervengan 
 Se denota A  B o AB 
 En otras palabras; A y B tienen el mismo significado, se puede sustituir una en lugar de la otra. 
 
 De la definición se desprende que: 
 A  B si y solo si A  B es una tautología 
 Ejemplo: 
 
 p  (q  r)  (p q)  r ya que p  (q  r) (p q)  r es una tautología 
EQUIVALENCIAS LOGICAS NOMBRE DE LA LEY 
1) p  q  q p , p  q  q  p Conmutatividad 
2) (p q)r  p(qr) , (pq)r  p(qr) Asociatividad 
3) p(qr)  (pq)(pr) , p(qr) (pq)(p  r) Distributividad 
4) pp  p , pp  p Idempotencia 
5) (p)  p Doble Negación 
6)  (p q )  p  q ,  (p q )  p q De Morgan 
7) pV  p , p  F  p Elementos Neutros 
8) p  V  V , pF  F Dominación 
LEYES LOGICAS (1º PARTE) 
EQUIVALENCIAS LOGICAS NOMBRE DE LA LEY 
 
9) p  p  V , p  p  F Opuestos 
10) p(pq)  p , p (pq)  p Absorción 
11) (pq) (pq) Condicional 
12) (pq) (q  p) Contrarecíproca 
13) (pq) (p  q) Negación de la condicional 
14) (pq) (pq)(q  p) Bicondicional 
15) (pq) (p   q) (q   p) Neg de la bicond. 
 
 
 
 
 
LEYES LOGICAS (1º PARTE-cont) 
ACTIVIDAD N°4 
1) Demostrar la Ley distributiva de la disyunción respecto de la 
conjunción 
2) Desmostrar la Ley de la Negación de la Condicional 
3) Escribir una frase equivalente a las siguientes: 
 a) No es cierto que no estudié 
 ………………………………….. 
 b) No estudie Inglés ni Francés 
 ………………………………….. 
 c) No es cierto que, comeré chocolates o caramelos 
 ………………………………….. 
 d) No es cierto que, si cobro el dinero viajare al sur 
 ………………………………….. 
 
 
IMPLICACIÓN LÓGICA 
 Sean A y B dos expresiones lógicas. 
 Diremos que A implica lógicamente a B si y solo si 
cada vez que A es verdadera , B también lo es. 
 Se denota A  B 
 Ejemplo : ( p  q )  p 
 Observe que: 
 A  B si y solo si AB sea una tautología 
 
Otras formas de leer: 
Si A  B se dirá que B se deduce lógicamente de A , o que 
B se desprende de A o que B se infiere de A 
 
 
IMPLICACIONES LOGICAS NOMBRE DE LA LEY 
1) (pq)  p Simplificación 
2) p  (pq) Adición 
3) [(pq) p]  q Modus Ponens 
4) [(pq) q]  p Modus Tollens 
5) [(p  q) p]  q Silogismo Disyuntivo 
6) [(pq)(qr)]  (p  r) Silogismo hipotético 
 
 
LEYES LOGICAS (2º PARTE) 
UNIDAD I - 2016 
ACTIVIDAD N°5 
1) Demostrar las Leyes de Simplificacióny la Ley Modus 
Ponens 
2) Completar en los puntos suspensivos con alguna 
expresión lógica de tal modo que valga la  
 r q  ……………….. 
 s  ……………….. 
 [( pq)   p]  ……………….. 
 [(p  q) q]  ……………….. 
 [(p   q)  q]  ……………….. 
 [( pq)( r  q)]  ……………….. 
 
 
 
 
 Un razonamiento o argumento es una sucesión de 
expresiones lógicas estructurados del siguiente modo: 
 p1 
 p2 
 … 
 pn 
  q 
 
 donde p1, p2 , …, pn 
se dicen premisas o 
hipótesis y q se dice 
conclusión o tesis. 
ARGUMENTOS O 
RAZONAMIENTOS LOGICOS 
 Se lee: 
 A partir de las premisas p1, p2 , …y pn se deduce la conclusión q 
 Un razonamiento es válido si y solo sí cada vez que las 
premisas son verdaderas, la conclusión también lo es. 
 Esto es: 
 El razonamiento es válido si y sólo si p1 p2…pn  q 
 
 Se dice también: El razonamiento es válido si y solo si la 
conclusión q se infiere de las premisas p1 , p2 , …y pn 
 
 Los razonamientos válidos mas elementales son llamados 
Reglas de Inferencia 
 
 
ARGUMENTOS O 
RAZONAMIENTOS VALIDOS 
Ley de 
Simplificación 
 
p  q 
_______ 
∴ p 
PRINCIPALES REGLAS DE INFERENCIA 
Ley de Adición 
 
p 
_______ 
∴ p ∨ q 
Modus Ponens 
 p 
p → q 
_______ 
∴ q 
Modus Tollens 
 ¬q 
p → q 
_________ 
∴ ¬p 
Silogismo Hipotético 
p →q 
q → r 
_______ 
∴ p→ r 
Silogismo 
Disyuntivo 
 
p ∨ q 
¬ p 
_________ 
∴ q 
Ley de 
Combinación 
 
p 
q 
________ 
∴ p ∧ q 
 
Estudio Inglés y Francés 
___ ____ 
∴ …………………. 
Si el banco deposita el 
dinero, pagaré. 
Pero no pague 
 _____ __ 
∴ …………………….. 
Si el banco deposita el 
dinero, pagaré. 
El banco depositó el dinero 
______ __ _ 
∴ ……………………….. 
Si el banco deposita el dinero, 
pagaré. 
Si pago, cancelo la deuda 
_ ____ __ 
∴ ………………………… 
ACTIVIDAD N°6: Escribir una conclusión que se 
deduzca de las premisas que se dan en cada caso: 
 
MÉTODOS DE DEMOSTRACION 
 Para la demostración de la validez de un razonamiento 
se pueden usar, además de tablas de verdad, métodos 
algebraicos que usan las Reglas de Inferencia ya 
probadas. Los métodos algebraicos se clasifican en 
Directos e Indirectos 
 El MÉTODO DIRECTO es aquel que consiste en suponer 
que las premisas son verdaderas y , usando las reglas 
de inferencia convenientes, se debe mostrar que la 
conclusión tambien es verdadera. Simbólicamente 
p1  p2  … pn …..….  ……. q 
 Hay dos formas de demostrar la validez de un 
razonamiento de manera indirecta: 
 Una manera es usando el METODO INDIRECTO POR LA 
CONTRARECÍPROCA que consiste en plantear la implicación 
equivalente y probar esta última. Esto es, suponer que la 
conclusión no es cierta y arribar, por medio de las leyes de 
inferencia a demostrar que las premisas tampoco podrían 
ser verdaderas simultáneamente. Simbólicamente 
 
 q  ( p1  p2  … pn ) 
 El otro METODO INDIRECTO es el llamado POR 
CONTRADICCION que consiste en plantear que 
suponer que simultáneamente se den las premisas y 
lo contrario de la conclusión lleva a un absurdo, a 
una falacia 
 p1  p2  …  pn ∧ ¬q  F 
Demuestre la validez del razonamiento por 
los tres métodos 
 
 
 
 
 
 
ACTIVIDAD N°7 
UNIDAD I - 2016 
Definición: Llamamos predicado a toda 
oración afirmativa que no es proposición, pero 
que contiene una o más variables que, cuando 
se particularizan, hacen que la oración se 
convierta en proposición. 
 Simbólicamente: Representaremos como P(x) o P(x,y) , ya 
sea que el predicado sea de una o dos variables 
respectivamente 
 Al conjunto de valores de la o las variables para los cuales 
tienen sentido los predicados les llamaremos Dominio 
 
LOGICA DE PREDICADOS 
ACTIVIDAD Nº8 
1) Dé un predicado en una variable y 
diga cual es su dominio 
2) Asigne valores a la variable y dé el 
valor de verdad de la proposición 
resultante 
 
 
 
 
UNIDAD I - 2016 
Definición: Cuantificar un predicado es expresar la 
frecuencia con la que se cumple el mismo. 
 
 Hay dos modos de hacerlo; por medio de la 
Cuantificación Universal o por medio de la Cuantificación 
Existencial 
CUANTIFICADORES 
UNIDAD I - 2016 
 La cuantificación universal de un predicado P(x) expresa que P(x) 
se cumple para todos los valores de x. Se genera la siguiente 
proposición: 
 “Para todos los valores de x , se cumple P(x)” 
 Simbólicamente: x, P(x) 
 Dominio de la variable: Todos los valores de x para los cuales P(x) 
tenga sentido. Si se desea restringir los valores de x, se debe 
especificar. 
 
CUANTIFICADOR UNIVERSAL 
UNIDAD I - 2016 
 La cuantificación existencial de un predicado P(x) expresa que P(x) se 
cumple para por lo menos algún valor de x. 
 Se genera la siguiente proposición: 
 “Por lo menos algún x cumple P(x)” 
 Simbólicamente: x, P(x) 
 Dominio de la variable: Todos los valores de x para los cuales P(x) 
tenga sentido. Si se desea restringir los valores de x, se debe 
especificar. 
 
CUANTIFICADOR EXISTENCIAL 
UNIDAD I - 2016 
Valor de Verdad de x, P(x) y de x, P(x) 
 
• Es verdadera cuando P(x) se cumple 
para cada uno de los valores de x 
• Es falsa si P(x) es falso para por lo 
menos un valor de x 
x, P(x) 
• Es verdadera cuando P(x) se cumple 
por lo menos para algún valor de x 
• Es falsa si P(x) es falso para cada 
valor de x 
x, P(x) 
UNIDAD I - 2016 
1) Dar el valor de verdad de las siguientes expresiones lógicas. 
Considere que el Dominio es el conjunto de los Números Reales 
 
 a) x, x >0 
 b) x, 3x – 5 = 0 
 
2) Dar el valor de verdad de las expresiones anteriores 
considerando que el Dominio es el conjunto de los Numeros 
Naturales. 
ACTIVIDAD Nº 9 
UNIDAD I - 2016 
 
1) [x, P(x)]  x, P(x) 
2) [x, P(x)]  x, P(x) 
 
 
 
 
 
 Demostración de 1) 
 Sin perdida de generalidad podemos suponer que el dominio es el 
conjunto de los Números Naturales, entonces… 
 [x, P(x)]  [P(1) P(2) P(3) …]  P(1)   P(2)   P(3)  
…  x, P(x) 
NEGACION DE LOS 
CUANTIFICADORES 
UNIDAD I - 2016 
1) Dar el valor de verdad de las siguientes expresiones lógicas. 
 a) n  N , n – 1 > 0 
 b)  n  N, 3n – 6 = 0 
 
2) Encontrar la negación de cada una y dar su valor de verdad. 
ACTIVIDAD Nº 10 
UNIDAD I - 2016 
 Los cuantificadores universal y existencial pueden aplicarse a cada 
variable. Ejemplo 
Suponga P(x,y) : x es padre de y 
Entonces, 
xy P(x,y) Se lee “Cualquier persona es padre de todos” 
xy P(x,y) Se lee “Todas las personas son padres de alguna 
persona” 
xy P(x,y) Se lee “Alguna persona es padre de todas las personas” 
 xy P(x,y) Se lee “Alguna persona es padre de alguien” 
yx P(x,y) Se lee “Todas las personas son hijos del alguien” 
yx P(x,y) Se lee “Alguien es hijo de todos” 
 
 
PREDICADOS EN DOS VARIABLES 
ACTIVIDAD Nº11 
 Sea P(x,y) : “ x es múltiplo de y” 
Dé la interpretación de las siguientes expresiones 
simbólicas 
 xy P(x,y) 
 xy P(x,y) 
 xy P(x,y) 
  xy P(x,y) 
 yx P(x,y) 
 yx P(x,y) 
 
 
UNIDAD I - 2016 
ACTIVIDAD Nº12 
Marca con una x las negaciones de las siguientes 
frases: 
a) Todos quieren a alguien 
b) Alguien quiere a todos 
 
 
a) b) 
Todos no quieren a alguien Todos quieren a todos 
No todos quieren a alguien Todos quieren a alguien 
Alguien no quiere a todos No existe alguien que quiere a todos 
Nadie quiere a todos Nadie quiere a todos 
Alguien quiere a todos Nadie quiere a alguien 
 Es otra técnica de demostración. Se usa cuando se 
quiere mostrar que una proposición P(n) es válida 
para todos los números enteros n mayores o iguales 
que un entero dado.Simbólicamente, el método de Inducción se usa para 
probar que 
 nno , P(n) con n, no  
PRINCIPIO DE INDUCCION MATEMATICA 
UNIDAD I - 2016 
a) es llamado paso base y b) es llamado paso inductivo 
PRINCIPIO DE INDUCCION MATEMATICA 
Supóngase que n, no, k  
Si se cumplen las siguientes 
condiciones: 
a) P(no) es verdadera 
b) P(k) es verdadera  P(k+1) es 
verdadera , para todo k  no 
 
Entonces se concluye que P(n) es 
verdadera n no 
¿Cuál es la idea del Principio de Inducción? 
 La misma que la del 
famoso juego que se 
construye con las fichas 
de dominó, las cuales 
están ubicadas una 
detrás de otra, todas a 
la misma distancia . Si 
hacemos caer la 
primera, caen todas las 
demás. 
UNIDAD I - 2016 
ACTIVIDAD Nº 13 
Demuestre que : 
 
2
2
)13(
)13(...852 

 nNn
nn
n
UNIDAD I - 2016 
PREGUNTA TEORICAS SOBRE LA UNIDAD 1 
1) Defina a los conectivos Lógicos. Diga cuándo es verdadero cada 
uno de ellos. 
2)Dada una expresión lógica compuesta, diga a que llamamos 
conectivo principal y como se lo identifica en expresiones con y sin 
parentesis 
 3)Defina Predicado . Defina cuantificador. Dé un ejemplo 
 Es x P(x) una proposición? Es x P(x) una proposición? 
4) Defina Tautología, Contingencia y Contradicción. De ejemplos de 
cada una 
5) Defina Equivalencia Lógica. ¿Cuál es la relación entre la 
Equivalencia Lógica y el conectivo Bicondicional? Enuncie por lo 
menos 5 equivalencias importantes 
6) Enuncie las equivalencias que tienen que ver con Cuantificadores. 
Demuestrelas 
7) a) Defina Implicación Lógica. De ejemplos de aquellas donde 
intervenga el conectivo disyunción 
 b) Defina Razonamiento. A que llamamos premisas y conclusion? 
Las premisas son siempre verdaderas? 
8) a) Diga cuando un razonamiento es válido. Dé la relacion que 
existe con el concepto de implicacion logica 
 b) Enuncie los principales patrones de razonamientos validos 
(también llamados Reglas de Inferencia) 
9) Como se clasifican los Métodos de Demostración?. Describa a 
cada uno 
10) Enuncie el Principio de Inducción. ¿diga en qué casos se usa? . 
De un ejemplo donde lo aplicaría 
 
UNIDAD I - 2016 
11) Diga Verdadero o Falso, justificando su respuesta: 
 ( pq )  q  q 
 ( pq )  r  p ( q  r ) 
 p q  p 
 p  p  q 
12) La negación de „ Canto y bailo „ es „ No canto y no bailo‟ 
13) La negación de „Saldré a caminar, si no llueve‟ es „ No llueve y no 
saldré a caminar‟ 
14) Es válido el siguiente razonamiento? 
 p r , r t ,  s  t  s 
 15) Para probar que ( x + 1 ) 2 = x 2 + 2x + 1 , vale xR , se usa 
el Principio de Inducción 
 
M
A
PA
 
C
O
N
C
EP
TU
A
L 
 
U
N
ID
A
D
 1