Unidad 1: Lógica Proposicional
Asignatura
Matemáticas Discretas
Catedrático
Dr. Nicandro Farías Mendoza
Alumno
Juan Miguel González Pérez
Villa de Álvarez, Col., a 12 de febrero del 2018
PRIMEROS TRES EJERCICIOS – SECCIÓN 1(Diapositiva 12)
Utilizando las afirmaciones R y H para “Marco es rico” y “Marco es feliz”, respectivamente, escriba las siguientes
afirmaciones en forma simbólica
a. Marco no es rico -R
b. Marco es rico y feliz R V H
c. Marco es rico o feliz R Ʌ H
d. Si Marco es rico entonces es feliz R => H
e. Marco es feliz solo si es rico R H
Identifique todas las proposiciones atómicas en las siguientes oraciones y abrévielas con símbolos P, Q y R. Entonces
convierta las oraciones al cálculo proposicional.
a) Si Jaime esta en el granero, entonces Javier debe estar en el granero también.
P = Jaime esta en el granero
Q =Javier esta en el granero
P => Q
b) El coche que se escapo era rojo o marron.
P = El coche era rojo
Q = El coche era marron
PVQ
c) Las noticias no son buenas
P = Las noticias son buenas
-P
d) Estarás a tiempo solo si te apuras
P = Estarás a tiempo
Q = Si te apuras
PQ
e) El vendrá si tiene tiempo
P = El vendrá
Q = Tiene tiempo
P => Q
f) Si ella estaba allí, entonces debió haber oído
Q = ella estaba allí
R = debió haberlo oído
Q => R
Prepare la tabla de verdad para le O exclusivo
P Q PVQ
V V F
V F V
F V V
F F F
PRIMEROS TRES EJERCICIOS – SECCIÓN 2 (Diapositiva 13)
(1) Construir la tabla de verdad para cada una de las siguientes expresiones. Indique para cada expresión si es una
tautología, una contradicción o una contingencia.
a) (P Ʌ (P =>Q)) => Q
P Q P => Q P Ʌ (P=>Q) P Ʌ (P =>Q)) => Q
V V V V V
V F F F V
F V V F V
F F V F V
Es una TAUTOLOGIA
b) (P => Q) (-P V Q)
P Q -P (P => Q) (-P V Q) (P => Q) (-P V Q)
V V F V V V
V F F F F V
F V V V V V
F F V V V V
Es una TAUTOLOGIA
c) ((P => Q) Ʌ (Q => R)) => (P =>R)
((P => Q) Ʌ (Q => R)) => (P =>R)
P Q R (P => Q) (Q => R) (P =>R) ((P => Q) Ʌ (Q => R)
V V V V V V V V
V V F V F F F V
V F V F V V V V
V F F F V F F V
F V V V V V V V
F V F V F V F V
F F V V V V V V
F F F V V V V V
Es una TAUTOLOGIA
d) (P Q) ((P Ʌ Q) V (-P Ʌ -Q))
(P Q) ((P Ʌ Q) V
P Q -P -Q (P Q) (P Ʌ Q) (-P Ʌ -Q) ((P Ʌ Q) V (-P Ʌ -Q)) (-P Ʌ -Q))
V V F F V V F V V
V F F V F F F F V
F V V F F F F F V
F F V V V F V V V
Es una TAUTOLOGIA
e) (Q Ʌ (P => Q)) =>P
P Q (P=>Q) (Q Ʌ (P => Q)) (Q Ʌ (P => Q)) =>P
V V V V V
V F F F V
F V V V F
F F V F V
Es una CONTINGENCIA
f) -(P V (Q Ʌ R)) ((P V Q) Ʌ (P V R))
-(P V (Q Ʌ R)) ((P V Q) Ʌ (P V R))
P Q R (Q Ʌ R) P V (Q Ʌ R) -(P V (Q Ʌ R)) PVQ PVR ((P V Q) Ʌ (P V R)
V V V V V F V V V F
V V F F V F V V V F
V F V F V F V V V F
V F F F V F V V V F
F V V V V F V V V F
F V F F F V V F F F
F F V F F V F V F F
F F F F F V F F F F
Es una CONTRADICCION
(2) Utilizar la tautología P V -P para demostrar que las siguientes expresiones son Tautologías.
TAUTOLOGIA P V -P
P -P P V -P
V F V
V F V
F V V
F V V
a) (P => Q) V – (P=> Q)
(P => Q) V – (P=> Q)
P Q (P=>Q) -(P=> Q)
V V V F V
V F F V V
F V V F V
F F V F V
b) -P V –P
-P --P -P V –P
F V V
F V V
V F V
V F V
c) ((P Ʌ S) V Q) V -((P Ʌ S) V Q)
((P Ʌ S) V Q) V -((P Ʌ S) V Q)
P S Q PɅS (P Ʌ S) V Q -((P Ʌ S) V Q)
V V V V V F V
V V F V V F V
V F V F V F V
V F F F F V V
F V V F V F V
F V F F F V V
F F V F V F V
F F F F F V V
(3) Demuestre que (P => Q) Ʌ (-P => Q) => - Q es una tautología. Convierta esta tautología en un esquema con A
reemplazando P y B reemplazando Q. use este esquema para demostrar que:
(-P => -Q) Ʌ (--P => -Q) => -Q
(-A => -B) Ʌ (--A => -B) => -B
A B -A -B -A => -B --A => -B (-A => -B) Ʌ (--A => -B)
V V F F V F F V
V F F V V V V V
F V V F F V V V
F F V V V V V V
EJERCICIOS 6,7,8 – Sección 3 (Diapositiva 14)
(1) Supuesto que P y Q son verdaderos y R y S son falsos. Hallar los valores de verdad de las siguientes expresiones
a) P v (Q Ʌ R)
P Q R QɅR P V (Q Ʌ R)
V V F F V
b) (P Ʌ (Q Ʌ R)) V –((P V Q) Ʌ (R V S))
(P Ʌ (Q Ʌ R)) V –((P V
–((P V Q) Ʌ
P Q R S QɅR (P Ʌ (Q Ʌ R)) PVQ RVS (P V Q) Ʌ (R V S)) Q) Ʌ (R V S))
(R V S))
V V F F F F V F F V V
c) (-(P Ʌ Q) V -R) V (((-P Ʌ Q) V -R ) Ʌ S)
(-(P Ʌ Q) V -R) V
P Q R S -(P Ʌ Q) -(P Ʌ Q) V -R) -P Ʌ Q (-P Ʌ Q) V -R (((-P Ʌ Q) V -R ) Ʌ S) (((-P Ʌ Q) V -R ) Ʌ S)
V V F F F V F V F V
(2) Supuesto que P y Q son verdaderos y R y S son falsos, hallar los valores de verdad de las siguientes expresiones:
a) (-(P Ʌ Q) V -R) V ((Q -P) => (R V -S)
(-(P Ʌ Q) V -R) V ((Q -P)
P Q R S -(P Ʌ Q) -(P Ʌ Q) V -R Q -P R V -S ((Q -P) => (R V -S) => (R V -S)
V V F F F V F V V V
b) (P R ) Ʌ (-Q => S)
P Q R S PR -Q => S (P R ) Ʌ (-Q => S)
V V F F F V F
c) (P V (Q => (R Ʌ -P))) (Q V -S)
P Q R S R Ʌ -P Q => (R Ʌ -P) (P V (Q => (R Ʌ -P))) Q V -S (P V (Q => (R Ʌ -P))) (Q V -S)
V V F F F F V V V
(3) Construya las tablas de verdad para las siguientes formulas:
a) -(-P V -Q)
P Q (-P V -Q) -(-P v -Q)
V V F V
V F V F
F V V F
F F V F
b) -(-P Ʌ -Q)
P Q (-P Ʌ -Q) -(-P Ʌ -Q)
V V F V
V F F V
F V F V
F F V F
c) P Ʌ (P V Q)
P Q PVQ P Ʌ (P V Q)
V V V V
V F V V
F V V F
F F F F
d) P Ʌ (P Ʌ Q)
P Q PɅQ P Ʌ (P V Q)
V V V V
V F F V
F V F F
F F F F
e) (-P Ʌ (-Q Ʌ R)) V (Q Ʌ R) V (P Ʌ R)
(-P Ʌ (-Q Ʌ R)) V (Q Ʌ R) V (P Ʌ R)
P Q R -Q Ʌ R -P Ʌ (-Q Ʌ R) QɅR (-P Ʌ (-Q Ʌ R)) V (Q Ʌ R) PɅR
V V V F F V V V V
V V F F F F F F F
V F V V F F F V V
V F F F F F F F F
F V V F F V V F V
F V F F F F F F F
F F V V V F V F V
F F F F F F F F F
f) (P Ʌ Q) V (-P Ʌ Q) V (P Ʌ -Q) V (-P Ʌ -Q)
(P Ʌ Q) V (-P Ʌ Q) V
P Q PɅQ -P Ʌ Q P Ʌ -Q -P Ʌ -Q (P Ʌ Q) V (-P Ʌ Q) (P Ʌ -Q) V (-P Ʌ -Q)
(P Ʌ -Q) V (-P Ʌ -Q)
V V V F F F V F V
V F F F V F F V V
F V F V F F V F V
F F F F F V F V V
Ejercicios 1 y 6 – SECCIÓN 4 (Diapositiva 38)
Complete las demostraciones formales siguientes dando las explicaciones da paso.
(1) a) 𝑆𝑖 𝑝 → (𝑞 ∨ 𝑟), 𝑞 → 𝑠 𝑦 𝑟 → 𝑡, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑝 → (𝑠 ∨ t).
1. 𝑝 → (𝑞 ∨ 𝑟) Hipótesis
2. 𝑞 → s Hipótesis
3. 𝑟 → 𝑡 Hipótesis
4. (𝑞 ∨ r) → (𝑠 ∨ t) (2 y 3) se aplican dilemas constructivos (26a)
5. 𝑝 → (𝑠 ∨ t) (1 y 4) se aplica silogismo hipotético (regla 33)
(2) b) Si 𝑝 → (𝑞 ∧ 𝑟), (𝑞 ∨ s) → 𝑡 𝑦 𝑝 ∨ s , 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑡.
1. 𝑝 → (𝑞 ∧ 𝑟), Hipótesis
2. (𝑞 ∨ s ) → 𝑡 Hipótesis
3. 𝑝 ∨ s Hipótesis
4. (𝑞 ∧ 𝑟) → 𝑞 (1) Simplificación
5. 𝑝 → 𝑞 (1 y 4) Se aplico silogismo hipotético
6. (𝑝 ∨ s) → (𝑞 ∨ s) (5) 25a Silogismo hipotético
7. 𝑞 ∨ s (3 y 6) Modus Ponens (regla 30)
8. t (2 y 7) Modus Ponens (regla 30)
(3) Construya la demostración formal del teorema:
Si 𝑆𝑖 𝑝 → (𝑞 𝑉 𝑟) 𝑦 𝑞 → 𝑠, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑝 → (𝑟 𝑉 𝑠)
1.- 𝑝 → (𝑞 𝑉 𝑟) Hipótesis
2.- q→ 𝑠 Hipótesis
3.- 𝑝 → 𝑟 (1) 6b se aplicó Identidad
4.- (𝑝 𝑉 𝑞) → (r V s) (3,2) 26a Constructivo
5.- 𝑝 → (𝑟 𝑉 𝑠) (4) 6a identidad
Primeros ejercicios – SECCIÓN 5 (Diapositiva 43)
(1) Demuestre:
𝑛(𝑛 + 1)(2𝑛 + 1)
Σ𝑛𝑘=1 𝑘 2 = 1 + 4 + 9 + ⋯ + 𝑛2 = 𝑝𝑎𝑟𝑎 𝑛 € 𝑃
6
Demostración para 1:
1((1) + 1)(2(1) + 1)
(1)2 =
6
1=1
Valor para k:
2𝑘 3 + 3𝑘 2 + 𝑘
𝑘2 =
6
Demostración para k +1:
2𝑘 3 + 3𝑘 2 + 𝑘 (𝑘 + 1)((𝑘 + 1) + 1)(2(𝑘 + 1) + 1)
+ (𝑘 + 1)2 =
6 6
2𝑘 3 + 3𝑘 2 + 𝑘 6(𝑘 2 + 2𝑘 + 1) (𝑘 + 1)(𝑘 + 2)(2𝑘 + 3)
+ =
6 6 6
=
2𝑘 3 + 9𝑘 2 + 13𝑘 + 6 = 2𝑘 3 + 9𝑘 2 + 13𝑘 + 6
(2) Demuestre:
4 + 10 + 16 + ⋯ + (6𝑛 − 2) = 𝑛(3𝑛 + 1)𝑝𝑎𝑟𝑎 𝑡𝑜𝑑𝑎 𝑛 € 𝑃
Demostración para 1:
(6(1) − 2) = (1)(3(1) + 1)
4=4
Valor para k:
(6𝑘 − 2) = 𝑘(3𝑘 + 1)
Demostración para k + 1
𝑘(3𝑘 + 1) + (6(𝑘 + 1) − 2) = (𝑘 + 1)(3(𝑘 + 1) + 1)
3𝑘 2 + 𝑘 + 6𝑘 + 4 = (𝑘 + 1)(3𝑘 + 4)
3𝑘 2 + 7𝑘 + 4 = 3𝑘 2 + 7𝑘 + 4
Ejercicio 2,4 y 8 – SECCIÓN 6 (Diapositiva 43)
(1) Expresar las frases siguientes en cálculo de predicados. El universo de discurso es el conjunto
de todas las personas
a) Si a María le gusta Kiko y a Kiko le gusta Juli, entonces a María le gusta Juli.
m=maría k= Kiko j=Juli G=le gusta
∀𝑚∀𝑘∀𝑗(𝐺(𝑚, 𝑘) ∧ 𝐺(𝑘, 𝑗)) → 𝐺(𝑚, 𝑗)
b) Juan esta muy ocupado, pero Beni no.
j=Juan b=Beni O= muy ocupado
∀𝑗∀𝑏(𝑂(𝑗) ∧ ¬𝑂(𝑏))
c) Benja conoce al Sr. Suarez, pero Sr. Suarez no conoce a Benja.
b=Benja s= Sr. Suarez K=conoce
∀𝑏∀𝑠(𝐾(𝑏, 𝑠) ∧ ¬(𝐾(𝑠, 𝑏))
(2) Suponga que el universo de discurso es un conjunto de personas. Traduzca la frase “Todos los
presentes hablan inglés o francés” al calculo de predicados.
X= los presentes I= hablan inglés F=hablan francés
∀𝑥(𝐼(𝑥) V 𝐹(𝑥))
(3) En el dominio de los animales, ¿Cómo traducirías las siguientes expresiones?
a) Todos los leones son depredadores
∀𝑥(𝑙𝑒𝑜𝑛(𝑥) ⇒ 𝑝𝑟𝑒𝑑𝑎𝑑𝑜𝑟(𝑥))
b) Algunos leones viven en África
∃𝑥(𝑙𝑒𝑜𝑛(𝑥) ∧ 𝑣𝑖𝑣𝑒𝑛𝐴𝑓𝑟𝑖𝑐𝑎(𝑥))
c) Solo rugen los leones
∀𝑥(𝑟𝑢𝑔𝑒(𝑥) ⇒ 𝑙𝑒𝑜𝑛(𝑥))
d) Algunos leones comen cebras
∃𝑥(𝑙𝑒𝑜𝑛(𝑥) ∧ (𝑐𝑒𝑏𝑟𝑎(𝑦) ∧ 𝐶𝑜𝑚𝑒(𝑥, 𝑦))
e) Algunos leones solo comen cebras
∃𝑥(𝑙𝑒𝑜𝑛(𝑥) ∧ ∀𝑦(𝑐𝑜𝑚𝑒(𝑥, 𝑦) ⇒ 𝑐𝑒𝑏𝑟𝑎(𝑦)))
Ejercicios 1,2 y 3 - SECCIÓN 7 (Diapositiva 44)
(1) Un universo contiene los tres individuos a,b y c. Para estos individuos, se define un predicado Q(x,y)
y sus valores de verdad están dados por la siguiente tabla:
a b c
a V F V
b F V V
c F V V
Calcular:
a) ∀𝑥∃𝑦(𝑄(𝑥, 𝑦)) = V Existe por lo menos una y para todo x
a b c
a V F V
b F V V
c F V V
Verdadero
b) ∀𝑦(𝑄(𝑦, 𝑏)) = F Para todo y existe una “b”
a b c
a V F V
b F V V
c F V V
Falso
c) ∀𝑦(𝑄(𝑦, 𝑦)) = V Para toda y existe una y
a b c
a V F V
b F V V
c F V V
Verdadero
(2) Dado el universo descrito en el problema 1, determinar los valores de verdad para:
a) ∃𝑥¬(𝑄(𝑎, 𝑥) = V para “a” no existe alguna x
a b c
a V F V
b F V V
c F V V
Verdadero
b) ∀𝑦(𝑄(𝑏, 𝑦)) = F Para “b” debe existir una y
a b c
a V F V
b F V V
c F V V
Falso
c) ∀𝑦(𝑄(𝑦, 𝑦)) ∧ ∃𝑥∀𝑦(𝑄(𝑥, 𝑦)) = F Para todo y existe una y Y para algunas x existen y
a b c
a V F V
b F V V
c F V V
Falso
(3) Sea un universo de discurso que consta de tres personas solamente, a saber, Juan, Maria y Juana.
Los tres son alumnos, y ninguno de ellos es rico. Juan es varón, mientras que Maria y Juana son
Hembras . S,F,M y R denotan respectivamente las propiedades alumno, hembra, varón y rico.
a) Presentar la asignación de los predicados S,F,M,R.
S F M R
Juan V F V F
Maria V V F F
Juana V V F F
b) Calcular:
i) ∀𝑥(𝑆(𝑥)) = V Todas las x son S
S F M R
Juan V F V F
Maria V V F F
Juana V V F F
Verdadero
ii) ∀𝑥(𝐹(𝑥)) V ∀𝑥(𝑀(𝑥)) = F Para toda x es F o para toda x es M
S F M R
Juan V F V F
Maria V V F F
Juana V V F F
Falso
iii) ∀𝑥(𝐹(𝑥) V M(x)) = V Para toda x es F o M
Juan V F V F
Maria V V F F
Juana V V F F
Verdadero
iv) ∃𝑥(𝑅(𝑥)) = F Algunos x son R
v) S F M R
Juan V F V F
Maria V V F F
Juana V V F F
Falso
vi) ∃𝑥(𝐹(𝑥) ⇒ 𝑅(𝑥)) = F Algunos x son F entonces son R
S F M R
Juan V F V F
Maria V V F F
Juana V V F F
Falso
Ejercicios - SECCIÓN 8 (Diapositiva 49)
(1) Escriba una tabla de verdad que demuestre:
𝑆𝑖 (𝑝 𝑉 𝑞) 𝑦 (¬𝑝 𝑉 𝑟)𝑠𝑜𝑛 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑎𝑠, 𝑒𝑛𝑡𝑜𝑛𝑐𝑒𝑠 (𝑞 𝑉 𝑟)𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑟𝑎 (1.5.1)
p q r ¬𝑝 (p V q) (¬𝑝 V r) (q v r)
V V V F V V V
V V F F V F V
V F V F V V V
V F F F V F F
F V V V V V V
F V F V V V V
F F V V F V V
F F F V F V F
(2) Utilice la resolución para deducir cada conclusión:
1 ¬P V Q V R a) Se aplica silogismo disyuntivo (32) en (1 y 2) dando como resultado: 4. ¬𝑃 𝑉 𝑅
2 ¬Q b) Se aplica silogismo disyuntivo (32) en (4 y 3) dando como resultado: 5. ¬𝑃
3 ¬R_________
⁂ ¬P
(3) Utilice la resolución para deducir cada conclusión:
¬P V R a) Se aplica silogismo disyuntivo en (1 y 3) dando como resultado: 4. R
¬R V Q b) Se aplica 1.5.1 en (2 y 4) dando como resultado: 5. Q
P_________
⁂ Q
