• Author / Uploaded
• keivn

Citation preview

MATEMÁTICAS PARA LA COMPUTACIÓN CAPÍTULO 5. ÁLGEBRA BOOLEANA

RESPUESTA Y DESARROLLO DE EJERCICIOS AUTOR: JOSÉ ALFREDO JIMÉNEZ MURILLO

AVC APOYO VIRTUAL PARA EL CONOCIMIENTO

Matemáticas para la computación

4.-

4.1.a)

Respuesta a todos los problemas de Lógica.

Sean p: Vivo en un lugar bajo. q: Se inunda la casa. r: Vivo en un lugar alto. s: Me falta el agua. t: Es zona cara. u: Vivo en la montaña. [p→q]∧[r→(s∨t)]⇒[(t’∧q’∧s)→u]

b)

Sean P: ESTÁ EN LA SELECCIÓN DE FUT BOL.

q: Es buen jugador. r: Tiene una edad menor de 27 años. s: Pertenece al América. t: Es del Morelia. [p ↔ (q ∧ r ∨ s)] ∧ [(p ∧ q’ ∨ s’)→ t] ⇒ [t→q] c) Sean P: ESTUDIA INFORMÁTICA.

q: Estudia sistemas. r: Es alumno del Tecnológico. s: Es buen estudiante. [ (p ∨ q) → r ] ∧ [r ↔ s] ⇒ [ [ (q ∨ p)’ ∧ r’ ]→ s’ ] d) Sean: p: El programa corre. q: Tiene errores de compilación. r: Tiene errores de lógica. s: El programa está bien. t: Los resultados son satisfactorios. [ p↔q’ ] ∧ [(r’ ∧ q’ ) → (s ∧ t)] ⇒ [ (q ∨ r) → (p’ ∧ t’ ) ]

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial -2-

Matemáticas para la computación

e) Sean: a: Se realiza un buen diseño de la base de datos. b: Se hace buena programación. c: Se accesa rápidamente la información. d: Toma mucho tiempo corregir el programa. [(a ∧ b) → c] ∧ [b’ → d] ⇒ [(c’ ∧ d) → a’ ] 4.2.a) Sean p: Haré la tarea de matemáticas para computación. q: Tengo tiempo. r: Iré a la disco. s: Tengo dinero. t: Veré un buen programa de televisión. Teorema: [p ↔ q] ∧ [r ↔ (q ∧ s)] ∧ [s’→ (p ∧ t)] ⇒ [(t ∧ q) → p] b) Sean p: Gana medalla en los juegos olímpicos. q: Es buen deportista. r: Tiene edad menor de 27 años. s: Lo descalifican los jueces. t: Es Mexicano. Teorema: [p ↔ (q ∧r ∨ s’)] ∧ t’ ⇒ [(p’ ∧ q’ ∨ s) → t] c) Sean p: Estudia informática. q: Estudia sistemas. r: Es alumno del Tecnológico. s: Es buen estudiante. Teorema: [(p ∨ q) → r] ∧[r ↔ s] ⇒[ [(q ∨ p)’ ∧ r’] → s’] d) Sean p: Tengo conocimientos de computación. q: Domino el inglés. r: Tengo problemas para encontrar trabajo. s: Tengo más de 40 años. t: Me preparé lo suficiente.

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial -3-

Matemáticas para la computación

Teorema: [(p∧ q) → r’] ∧ [r →(s ∨ t’)] ⇒ [(t ∧ s’ ∧ q) → r’]

4.3.a)

[(p→q)’→r]→ (p’∨r’∧q) p 0 0 0 0 1 1 1 1

b)

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ (r’∧q) (p’∨r’∧q) (p→q)’ (p→q)’→r [(p→q)’→r]→ (p’∨r’∧q) 1 0 1 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0

p → q’ ∨ r ↔ p ∧ q → r’ p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ p∧q q’∨r p→q’∨r p→q’∨r↔p∧q p→q’∨r↔p∧q→r’ 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0

c) (p → r) ↔ [(q ∨ r ∧ p’ ) → r’ ]’ p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ r∧p’ (q∨r∧p’) (p→r) [(q∨r∧p’)→r’ ] [(q∨r∧p’)→r’ ]’ 1 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1

Donde F = (p→r) ↔[(q∨r∧p’)→r’ ]

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial -4-

F 0 1 0 1 1 0 1 1

Matemáticas para la computación

d) [(p→q)→r’]∧ [(p’∨r)↔ q’) P 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ (p→q) [(p→q)→r’] (p’∨r) (p’∨r)↔ q’ [(p→q)→r’]∧[(p’∨r)↔q’)] 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 0 1 0 1 0 0

e) p → q ↔ r’∨ q’→ p’∧ r p 0 0 0 0 1 1 1 1 f)

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ p’∧r r’∨q’ p→q p→q ↔ r’∨q’ p→q ↔ r’∨q’→p’∧r 1 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1

[[((p∧r)↔q’ )→ p’]→ r’ ]’ p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ p∧r (p∧r)↔q’ ((p∧r)↔q’ )→ p’ [((p∧r)↔q’ )→ p’]→ r’ 1 0 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0

Donde: F=[[((p∧r)↔q’ )→ p’]→ r’ ]’

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial -5-

F 0 1 0 1 0 0 0 1

Matemáticas para la computación

4.4.- Elaborar las tablas de verdad para cada una de las siguientes proposiciones: a) p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ p→q (p→q)’ (p→q)’→r ((p→q)’→r)∨p’ (r’∧q’) [((p→q)’→r)∨p’]→(r’∧q’) 1 1 0 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0

b) p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ p∨q p∨q→p’ q∧(p∨q→p’) q’∨r p↔q’∨r p↔q’∨r→p’ p↔q’∨r→p’→q∧(p∨q→p’) 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1

d) p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ (p→q’) [(p→q’)→r] q∧r p’∨q ∧r (p’∨q∧r)’ [(p→q’)→r]→(p’∨q∧r)’ 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0 0

e) p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ q∧p (r’∨q∧p) r∨q’ p’→(r’∨q∧p) p’→(r’∨q∧p)↔r∨q’ p’→(r’∨q∧p)↔r∨q’→p 1 0 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial -6-

Matemáticas para la computación

f) [(p→q’)→(q∨r∧p’)]↔[(q→p)’→r] p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p’ 1 1 1 1 0 0 0 0

q’ 1 1 0 0 1 1 0 0

r’ p→q’ r∧p’ q∨r∧p’ (p→q’)→(q∨r∧p’) q→p (q→p)’ (q→p)’→r F 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 1

Donde : F=[(p→q’)→(q∨r∧p’)]↔[(q→p)’→r]

4.5.a) [(p → r)∧(q→ r)] ≡ [( p∧q)→r] [(p∧q)→(r∧r)] ≡ [(p∧q)→r] [(p∧q)→ r] ≡ [(p∧q)→r]

por 9b por 21b

[p∨ (q∧r)] ≡ [(p∧p)∨(p∧r)∨(p∧q)∨(q∧r)] [p∨ (q∧r)] ≡ [ p∨ (p∧q) ∨ (p∧r) ∨(q∧r)] [p∨ (q∧r)] ≡ [ p∨ p∧(q∨r) ∨(q∧r)] [p∨ (q∧r)] ≡ [ p∨ (q∧r)]

Por 21b y 18a Por 20b Por 27f

b)

4.6. Demostrar que las proposiciones de cada uno de los incisos siguientes son lógicamente equivalentes, usando para ello las equivalencias lógicas restantes: a) [(p → q) ∧ (p → r)] ≡ [p → (q ∧ r)] [(p’ ∨ q)] ∧(p’ ∨ r)] ≡ [p → (q ∧ r)] [(p’ ∨ (q ∧r)] ≡ [p → (q ∧ r)] [p → (q ∧ r)] ≡ [p → (q ∧ r)] b) (p → q) ≡ (p’ ∨ q) (p ∧ q’)’ ≡ (p’ ∨ q) (p’ ∨ q) ≡ (p’ ∨ q)

Variantes de la condicional 24a Ley distributiva 20a Variantes de la condicional 24a

Variantes de la condicional 24b Ley de Morgan 22b

c) [p’ ∧ (s ∨ r’)] ≡ [p’ → (s ∨ r’)’]’ [p’ ∧ (s ∨ r’)] ≡ [p ∨ (s ∨ r’)’]’ [p’ ∧ (s ∨ r’)] ≡ [p’∧ (s ∨ r’)]

Variantes de la condicional 24a Ley de Morgan 22a

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial -7-

Matemáticas para la computación

d) [(p ∨ s) → (q ∧ p ∨ s’)] ≡ [(q ∧ p ∨ s’)’ → (p ∨ s)’] [(p ∨ s) → (q ∧ p ∨ s’)] ≡ [(q ∧ p ∨ s’) ∨ (p ∨ s)’] [(p ∨ s) → (q ∧ p ∨ s’)] ≡ [(p ∨ s)’ ∨ (q ∧ p ∨ s’)] [(p ∨ s) → (q ∧ p ∨ s’)] ≡ [(p ∨ s) → (q ∧ p ∨ s’)]

Variantes de la condicional 24c Ley conmutativa 18a Variantes de la condicional 24a

4.7.p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

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

4.8.- Demostrar por medio de una tabla de verdad que las reglas 4a, 6a, 8c y 9a realmente son tautologías.

a) Se sabe que: [[p ∧ (p → q)] ⇒ q] ≡[[p ∧ (p → q)] → q] p 0 0 1 1

q p→q p∧(p→q) [p∧(p→q)]→ q 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1

b) Considerar que:

Se observa que es una tautología

[(p↔q)∧(q↔r)]⇒(p↔r) ≡ [(p↔q)∧(q↔r)] → (p↔r) p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r p↔q q↔r (p↔q)∧(q↔r) p↔r [(p↔q)∧(q↔r)] → (p↔r) 0 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial -8-

Matemáticas para la computación

c) Considerar que: (p→q)⇒[(q→r)→(p→r)] ≡ (p→q) → [(q→r)→(p→r)] p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r p→q q→r p→r (q→r)→(p→r) (p→q) → [(q→r)→(p→r)] 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1

d) Se sabe que: [(p→q)∧(r→s)]⇒[(p∨r)→(q∨s)] ≡ [(p→q)∧(r→s)] → [(p∨r)→(q∨s)] p 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

q 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

r 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

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

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial -9-

Matemáticas para la computación

4.9.a) (q’∨ p’) ∧ (r ∧ q) ⇒ (p ↔ r’)

Se dice que un argumento es válido si se trata de una tautología Lo recomendable es hacer la tabla de verdad. p q r p’ q’ r’ q’∨ p’ r∧q p↔r’ (q’∨ p’)∧(r∧q) 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 1 1 0 0

0 0 0 1 0 0 0 1

0 1 0 1 1 0 1 0

(q’∨ p’)∧(r∧q) → (p↔r’)

0 0 0 1 0 0 0 0

1 1 1 1 1 1 1 1

Se puede observar que se trata de un argumento válido (ya que en todos los casos es verdadero). Otra forma de demostrar la validez del argumento, es haciendo una pequeña demostración, partiendo de las hipótesis y llegando a la conclusión usando para ello tautologías, reglas de inferencia y equivalencias lógicas: 1.- q’∨ p’ 2.- r ∧ q 3.- q → p’ 4.- q 5.- r 6.- p’ 7.- p’ ∨ r’ 8.- r ∨ p 9.- (p’ ∨ r’) ∧ (r ∨ p) 10.- p ↔ r’

Hipótesis Hipótesis 1; Variantes de la condicional 24c. 2; Simplificación; 11 2; Simplificación; 11 3,4; Modus ponenes; 15 6; Adición; 1 5; Adición; 1 7,8; Conjunción; 14 9; Variantes de la bicondicional; 25b

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 10 -

Matemáticas para la computación

b) (r→p’) ∧ (q’∨ r’) ⇒ (p’→q )

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

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 1 0 1 0

1 1 1 0 1 1 1 0

1 1 1 0 1 0 1 0

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

0 0 1 1 1 1 1 1

0 0 1 1 1 1 1 1

Se observa que el argumento no es válido, ya que cuando (p=0, q=0, r =0) y (p=0, q=0, r=1) el argumento es falso. c) (p’→r)∧[(p’→ r)→(q’∧p)]⇒(q’∧p) Se trata de un argumento válido como se observa en la tabla de verdad: p q r p’ q’ r’ p’→r q’∧p (p’→ r)→(q’∧p) (p’→r)∧[(p’→ r)→(q’∧p)] 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

0 1 0 1 1 1 1 1

0 0 0 0 1 1 0 0

1 0 1 0 1 1 0 0

0 0 0 1 1 1 1 1

La demostración es muy sencilla: 1.- (p’→ r) 2.- (p’→ r)→(q’∧p) 3.- (q’∧p)

Hipótesis Hipótesis 1,2; Modus ponens; 15

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 11 -

(p’→r)∧[(p’→ r)→(q’∧p)] → (q’∧p) 1 1 1 1 1 1 1 1

Matemáticas para la computación

4.10.- Establecer si los siguientes enunciados son válidos o no. Explicar su respuesta: a) [(p’∨r)→q]∧q’⇒(p’∨r)’

Se dice que un argumento no es válido si se encuentra algún caso en que la proposición sea falsa. Lo más seguro en este problema es hacer la tabla de verdad. p q r p’ q’ r’ (p’∨r) (p’∨r)→q [(p’∨r)→q]∧q’ (p’∨r)’ 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 0 1 0 1

0 0 1 1 1 0 1 1

0 0 0 0 1 0 0 0

0 0 0 0 1 0 1 0

[(p’∨r)→q]∧q’→ (p’∨r)’ 1 1 1 1 1 1 1 1

Otra forma es haciendo una pequeña demostración considerando, partiendo de las hipótesis y llegando a la conclusión usando para ello tautologías, reglas de inferencia y equivalencias lógicas: 1.- (p’∨r)→q Hipótesis 2.- q’ Hipótesis 3.- (p’∨r)’ 1,2; Modus tollens. b) (p↔q’)∧(q∨r)⇒(p’→r’)

p q r p’ q’ r’ (p↔q’) (q∨r) (p↔q’)∧(q∨r) (p’→r’) (p↔q’)∧(q∨r) → (p’→r’) 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

0 0 1 1 1 1 0 0

0 1 1 1 0 1 1 1

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 12 -

0 0 1 1 0 1 0 0

1 0 1 0 1 1 1 1

1 1 1 0 1 1 1 1

Matemáticas para la computación

No es un argumento válido porque existe al menos un caso en donde la proposición es falsa como se observa en la tabla de verdad para p=0, q=1 y r=1 el argumento es falso. c) [(p’∧r)→(q→r’)]⇒[[(q→r’)→(p∨q’)]→[(p’∧r)→(p∨q’)]]

En este caso es más fácil demostrar la validez del enunciado por demostración como se muestra: 1.- [(p’ ∧ r) → (q → r’)] 2.- [(q → r’) → (p ∨ q’)] → [(p’ ∧ r) → (p ∨ q’)] 1; Pero también es válido, usando para ello la tabla de verdad.

Extensión de la condicional, 8c.

p q r p’ q’ r’ p’∧r q→r’ (p’∧r)→(q→r’) p∨q’ (q→r’)→(p∨q’) (p’∧r)→(p∨q’) G F 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

0 1 0 1 0 0 0 0

1 1 1 0 1 1 1 0

1 1 1 0 1 1 1 1

1 1 0 0 1 1 1 1

1 1 0 1 1 1 1 1

1 1 1 0 1 1 1 1

1 1 1 0 1 1 1 1

1 1 1 1 1 1 1 1

Donde: G= [(q→r’)→(p∨q’)]→[(p’∧r)→(p∨q’)] F= [(p’∧r)→(q→r’ )] → [[(q→r’ )→(p∨q’ )]→[(p’∧r)→(p∨q’ )]] d) (p→r’)∧(p’↔q)⇒(q’∨r). No es argumento válido, como lo muestra la siguiente tabla de verdad. p q r p’ q’ r’ p→r’ p’↔q (p→r’)∧(p’↔q) q’∨r 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 1 0 1 0

0 0 1 1 1 1 0 0

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 13 -

0 0 1 1 1 0 0 0

1 1 0 1 1 1 0 1

(p→r’)∧(p’↔q) → (q’∨r) 1 1 0 1 1 1 1 1

Matemáticas para la computación

e) (r→q’)∧[(p∧q’)→r’]⇒(q→r). No es un argumento válido, ya que en dos casos es falsa. p q r p’ q’ r’ (r→q’) p∧q’ (p∧q’)→r’ (r→q’)∧[(p∧q’)→r’]

q→r

0 0 0 0 1 1 1 1

1 1 0 1 1 1 0 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 0 1 1 1 0

0 0 0 0 1 1 0 0

1 1 1 1 1 0 1 1

1 1 1 0 1 0 1 0

4.11.- Sean: p: Tengo mucho dinero. q: Estoy muy carita. r: Las muchachas me quieren. s: Todas quieren salir conmigo. Por lo tanto las hipótesis son: (p ∨ q) → r s’ r→s p’

Hipótesis Hipótesis Hipótesis Conclusión

El teorema queda como sigue: [(p ∨ q) → r] ∧ s’ ∧ (r → s) ⇒ p’ Demostración por el método directo, del siguiente teorema. 1.2.3.4.5.6.7.-

(p ∨ q) → r s’ r→s r’ p→(p∨ q) p →r p’

Hipótesis Hipótesis Hipótesis 3,2; Modus Tollens; 16 Adición; 1 5,1; Silogismo hipotético; 13 6,4; Modus Tollens; 16

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 14 -

(r→q’)∧[(p∧q’)→r’] → (q→r) 1 1 0 1 1 1 0 1

Matemáticas para la computación

Demostración por Contradicción, del teorema. [(p ∨ q) → r] ∧ s’ ∧ (r → s) ⇒ p’ 1.2.3.4.5.6.7.8.9.10.-

(p ∨ q) → r s’ r→s p p→ (p ∨ q) p→r r r’ r ∧ r’ 0

Hipótesis Hipótesis Hipótesis Negación de la conclusión Adición; 1 5,1; Silogismo hipotético; 13 4,6; Modus ponens; 15 3,2; Modus Tollens; 16 7,8; Conjunción; 14 9; Contradicción; 26a

4.12.Sean: p: Estudio electrónica. q: Realizaré investigación en sistemas digitales. r: Estudio informática. s: Manejaré la información de una empresa. t: Estoy feliz. p →q r→s (q ∨ s) → t t’ →(p’ ∧ r’ )

Hipótesis Hipótesis Hipótesis Conclusión

Por lo tanto el teorema queda integrado de la siguiente manera: [p → q ] ∧ [r → s ] ∧ [(q ∨ s) → t ] ⇒ [t’ →(p’ ∧ r’ )] Demostración por el método directo. 1.p →q 2.r→s 3.(q ∨ s) → t 4.[(p → q ] ∧ [r → s ] 5.(p ∨ r)→ (q ∨ s) 6.(p ∨ r)→ t 7.t’ → (p ∨ r)’ 8.t’ → (p’ ∧ r’ )

Hipótesis Hipótesis Hipótesis 1,2; Conjunción; 14 4; Dilema constructivo; 9a 5,3; Silogismo hipotético; 13 6; Contrapositiva; 23 7; Ley de Morgan; 22a

Demostración por contradicción del siguiente teorema: [p → q ] ∧ [r → s ] ∧ [(q ∨ s) → t ] ⇒ [t’ →(p’ ∧ r’ )]

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 15 -

Matemáticas para la computación

1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.-

p →q r→s (q ∨ s) → t [t’ → (p’ ∧ r’) ]’ [t ∨ (p’ ∧ r’)]’ t’ ∧ (p’ ∧ r’)’ t’ ∧ (p’ ∧ r’)’ t’ ∧ (p ∨ r) t’ (p ∨ r) [p → q ] ∧ [r → s] (p ∨ r) → (q ∨ s) (p ∨ r) → t t t∧t’ 0

Hipótesis Hipótesis Hipótesis Negación de la conclusión 4; Variantes de la condicional; 24a 5; Ley de Morgan; 22a 6; Doble negación; 17 7; Ley de Morgan; 22b 8; Simplificación; 11 8; Simplificación; 11 1, 2; Conjunción; 14 11; Dilema constructivo; 9a 12,3; Silogismo hipotético; 13 10,12; Modus ponens; 15 14,9; Conjunción; 14 15; Contradicción; 26

4.13.- Sean: p: Se ha realizado un buen diseño de la base de datos. q: Se hace buena programación. r: Se accesa rápidamente la información. s: Toma poco tiempo corregir el programa. (p ∧ q) → r q’ → s’ (r’ ∧ s) → p’

Hipótesis Hipótesis Conclusión

Por lo tanto el teorema queda integrado de la siguiente manera: [(p ∧ q) → r ] ∧ [ q’ → s’ ] ⇒ [(r’ ∧ s) → p’] Demostración por el método directo. 1.2.3.4.5.6.7.8.9.10.11.12.-

(p ∧ q) → r q’ → s’ r’ → (p ∧ q)’ r’ → (p’ ∨ q’) s→q [r’ → (p’ ∨ q’)] ∧ [s → q] (r’ ∧ s) → [(p’ ∨ q’)∧ q] (r’ ∧ s) → [q ∧ (p’ ∨ q’)] (R’ ∧ S) → [(Q ∧ P’) ∨ (Q ∧ Q’)] (R’ ∧ S) → [(Q ∧ P’) ∨ 0] (R’ ∧ S) → (Q ∧ P’) (R’ ∧ S) → (P’ ∧ Q)

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 16 -

Hipótesis Hipótesis 1; Contrapositiva; 23 3; Ley de Morgan; 22b 2; Contrapositiva; 23 4,5; Conjunción; 14 6; Dilema constructivo; 9b 7; Ley conmutativa; 18b 8; LEY DISTRIBUTIVA; 20B 9; CONTRADICCIÓN; 26 10; LEY DE IDENTIDAD; 27ª 11; LEY CONMUTATIVA; 18B

Matemáticas para la computación

13.14.-

(P’ ∧ Q) → P’ (R’ ∧ S) → P’

SIMPLIFICACIÓN; 2 12,13; SILOGISMO HIPOTÉTICO; 13

Demostración por contradicción del teorema: [(p ∧ q) → r ] ∧ [ q’ → s’ ] ⇒ [(r’ ∧ s) → p’] 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.-

(p ∧ q) → r q’ → s’ [(r’ ∧ s) → p’ ]’ [[(r’ ∧ s) ∧p ]’ ]’ (r’ ∧ s) ∧p (r’ ∧ s) p r’ → (p ∧ q)’ s→q [r’ → (p ∧q)’ ] ∧ [s → q] (r’ ∧ s) → [(p∧ q)’∧ q] (r’ ∧ s) → [q ∧ (p ∧ q)’ ] (r’ ∧ s) → [q ∧ (p’ ∨ q’)] (R’ ∧ S) → [(Q ∧ P’) ∨ (Q ∧ Q’)] (R’ ∧ S) → [(Q ∧ P’) ∨ 0] (R’ ∧ S) → (Q ∧ P’) (Q ∧ P’) P’ P ∧ P’ 0

Hipótesis Hipótesis Negación de la conclusión. 3; Variantes de la condicional; 24b 4; Doble negación; 17 5; Simplificación; 11 5; Simplificación; 11 1; Contrapositiva; 23 2; Contrapositiva; 23 8,9; Conjunción; 14 10; Dilema constructivo; 9b 11; Ley conmutativa; 18b 12; Ley de Morgan; 22b 13; LEY DISTRIBUTIVA; 20B 14; CONTRADICCIÓN; 26 15; LEY DE IDENTIDAD; 27A 6,16; MODUS PONENS; 15 17; SIMPLIFICACIÓN; 11 7,18; CONJUNCIÓN; 14 19; CONTRADICCIÓN; 26 4.14.-

a)

Demostración por el método directo. [p → (q ∧ r)] ∧ [(q ∨ s) → t] ∧ (p ∨ s) ⇒ (r ∨ t) 1.2.3.4.5.6.7.8.9.10.11.12.-

p → (q ∧ r) (q ∨ s) → t (p ∨ s) s → (s ∨ q) s → (q ∨ s) s→t (r ∧ q) → r (q ∧ r) → r p→r (p → r ) ∧ (s → t) (p ∨ s) → (r ∨ t) (r ∨ t)

Hipótesis Hipótesis Hipótesis Adición; 1 4; ley conmutativa; 18a 5,2; Silogismo hipotético; 13 Simplificación; 2 7; Ley conmutativa; 18b 1,8; Silogismo hipotético; 13 9,6; Conjunción; 14 10; Dilema constructivo; 9a 3,11; Modus ponens; 15

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 17 -

Matemáticas para la computación

b)

Demostración por el método directo del siguiente teorema. [ (p ∧ q) → r ] ∧ [q’ → s’ ] ⇒ [(r’ ∧ s) → p’ ] 1.2.3.4.5.6.7.8.9.10.11.12.13.14.-

c)

(p ∧ q) → r q’ → s’ r’ → (p ∧ q)’ r’ → (p’ ∨ q’) s→q [r’ → (p’ ∨ q’)] ∧ [s → q] (r’ ∧ s) → [ (p’ ∨ q’) ∧ q] (r’ ∧ s) → [ q ∧ (p’ ∨ q’) ] (r’ ∧ s) → [( q ∧ p’) ∨ (q ∧ q’) ] (r’ ∧ s) → [( q ∧ p’) ∨ 0 ] (r’ ∧ s) → ( q ∧ p’) (r’ ∧ s) → ( p’ ∧ q) (p’∧ q) → p’ (r’ ∧ s) → p’

Hipótesis Hipótesis 1; Contrapositiva; 23 3; Ley de Morgan; 22b 2; Contrapositiva; 23 4,5; Conjunción; 14 6; Dilema constructivo; 9b 7; Ley conmutativa; 18b 8; Ley distributiva; 20b 9; Contradicción; 26 10; Ley de identidad; 27a 11; Ley conmutativa; 18b Simplificación; 2 12,13; Silogismo hipotético; 13

Demostración por el método directo del siguiente teorema. [ (p’ ∧ r ) → q ] ∧ q’ ∧ [r → s ] ⇒ [ r → ( s ∧ p ) ] 1.2.3.4.5.6.7.8.9.10.11.-

(p’ ∧ r ) → q q’ r→s q’ → (p’ ∧ r )’ q’ → (p’’ ∨ r’ ) q’ → (p ∨ r’ ) (p ∨ r’ ) (r’ ∨ p ) r→ p (r → s) ∧ (r → p) r → ( s ∧ p)

Hipótesis Hipótesis Hipótesis 1; Contrapositiva; 23 4; Ley de Morgan; 22b 5; Doble negación; 17 2,6; Modus ponens; 15 7; Ley conmutativa; 18a 8; Variantes de la condicional; 24a 3,9; Conjunción; 14 10; Variantes de la condicional; 24f

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 18 -

Matemáticas para la computación

d)

Demostración por el método directo del siguiente teorema. [ p’ → q’ ] ∧ (r → s’ ) ∧ [(q’ ∨ s’ ) → w ] ⇒ [ w’ → (p ∧ r’ ) ] 1.2.3.4.5.6.7.8.9.-

e)

p’ → q’ r → s’ (q’ ∨ s’ ) → w [p’ → q’ ] ∧ [r → s’ ] (p’ ∨ r) → (q’ ∨ s’ ) (p’ ∨ r) → w w’ → (p’ ∨ r ) ‘ w’ → (p’’ ∧ r’ ) w’ → (p ∧ r’ )

Hipótesis Hipótesis Hipótesis 1; Conjunción; 14 4; Dilema constructivo; 9b 5,3; Silogismo hipotético; 13 6; Contrapositiva; 23 7; Ley de Morgan; 22a 8; Doble negación; 17

Demostración por el método directo del siguiente teorema: [ p ↔ q’ ] ∧ [r ∨ q’] ∧ p’ ∧[p’ → r]⇒ [[r →(r ∨ q)] ∧ p] Demostración 1.p ↔ q’ 2.r’ ∨ q’ 3.p’ 4.p’ → r 5.[p→ q’ ] ∧ [q’→ p ] 6.q’→ p 7.r → q’ 8.r → p 9.r’ 10.r → (r∨q ) 11.r’ → p 12.p 13.p’∧ p 14.0

Hipótesis Hipótesis Hipótesis Hipótesis 1; Variantes de la condicional; 25a 5; Simplificación; 11 2; Variantes de la condicional; 24c 7,6; Silogismo hipotético; 13 8,3; Modus tollens; 16 Adición; 1 4; Contrapositiva; 23 9,11; Modus ponens; 15 10,12; Conjunción; 14 13; Contradicción; 26.

Si por el método directo se llega a una contradicción como ocurrió en este caso, eso significa que el teorema es falso.

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 19 -

Matemáticas para la computación

4.15.a) Demostración por el método directo del teorema: [ (r ∨ q) → q’ ] ∧ [ p’ → r ] ∧ (q ∨ r ) ∧ [q → p ] ⇒ [q’ ∧ [p’ → (q’ ∧ r ) ]] Demostración 1.(r ∨ q) → q’ 2.p’ → r 3.(q ∨ r ) 4.[q → p ] 5.q → (r ∨ q)’ 6.(r ∨ q) 7.q’ 8.p’ → q’ 9.[p’ → q’ ] ∧ [p’ → r ] 10.(p’ ∧ p’) → (q’ ∧ r) 11.p’ → (q’ ∧ r) 12.q’ ∧ [p’ → (q’ ∧ r)] b)

Hipótesis Hipótesis Hipótesis Hipótesis 1; Contrapositiva; 23 3; Ley conmutativa; 18a 5,6; Modus tollens; 16 4; Contrapositiva; 23 8,2; Conjunción; 14 9; Dilema constructivo; 9b 10; Ley de idempotencia; 21b 7,11; Conjunción; 14

Demostración por el método directo del teorema: [ q → (p ∧ s) ] ∧ [ s’ → r ]⇒ [(s’ ∧ p’ ∨ s’ ) → (r ∧ q’ ) ] Demostración 1.q → (p ∧ s) 2.s’ → r 3.(p ∧ s )’ → q’ 4.(p’ ∨ s’ ) → q’ 5.[s’ → r ] ∧ [(p’ ∨ s’ ) → q’ ] 6.[s’ ∧ (p’ ∨ s’ )] → (r ∧ q’) 7.[(s’ ∧ p’) ∨ (s’ ∧ s’ )] → (r ∧ q’) 8.[s’ ∧ p’ ∨ s’ ] → (r ∧ q’)

c)

Hipótesis Hipótesis 1; Contrapositiva; 23 3; Ley de Morgan; 22b 2,4; Conjunción; 14 5; Dilema constructivo; 9b 6; Ley distributiva; 20b 7; Ley de idempotencia; 21b

Demostración por el método directo del teorema: [ (q ∨ r’) → s ] ∧ [ t → q’ ]⇒ [(q ∨ s’ ) → (t’ ∨ r ) ] Demostración 1.(q ∨ r’) → s 2.t → q’ 3.r’ → (r’ ∨ q) 4.r’ → (q ∨ r’ ) 5.r’ → s 6.[t → q’ ] ∧ [r’ → s] 7.(t ∧ r’) → (q’ ∧ s) 8.(q’ ∧ s)’ → (t ∧ r’)’ 9.(q ∨ s’) → (t’ ∨ r)

Hipótesis Hipótesis Adición 3; Ley conmutativa; 18a 4,1; Silogismo hipotético; 13 2,5; Conjunción; 14 6; Dilema constructivo; 9b 7; Contrapositiva; 23 8; Ley de morgan; 22b

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 20 -

Matemáticas para la computación

d)

Demostración por el método directo del teorema: [ q ∧ r] ∧ [p → q’ ] ∧ [ s → (q→r’)] ⇒ [s’ ∧ (q → p’ )] Demostración 1.(q ∧ r) 2.p → q’ 3.s → (q→r’) 4.q → p’ 5.(q → r’ )’ 6.s’ 7.s’ ∧ (q → p’)

e)

Demostración por el método directo del teorema: [ (q ∨ s) → t ] ∧ t’ ⇒ [(q’ ∧ t’ ) ∧ (q → t)] Demostración 1.(q ∨ s) → t 2.t’ 3.(q ∨ s )’ 4.(q’ ∧ s’ ) 5.q’ 6.q’ ∧ t’ 7.q → (q ∨ s) 8.q → t 9.(q’ ∧ t’ ) ∧ (q → t)

f)

Hipótesis Hipótesis Hipótesis 2; Contrapositiva; 23 1; Variantes de la condicional; 24d 3,5; Modus tollens; 16 6,4; Conjunción; 14

Hipótesis Hipótesis 1,2; Modus tollens; 16 3; ley de Morgan; 22a 4; Simplificación; 11 5,2; Conjunción; 14 Adición; 1 7,1; Silogismo hipotético; 13 6,8; Conjunción; 14

Demostración por el método directo del siguiente teorema: [ p ↔ q’ ] ∧ [p’→ r ] ⇒ [p’→ (q ∨ r) ] Demostración 1.p ↔ q’ 2.p’→ r 3.[p → q’ ] ∧ [q’→ p] 4.q’→ p 5.r’→ p 6.[q’→ p ] ∧ [r’→ p ] 7.(q’∧r’ ) → (p∧p) 8.(q’∧r’ ) → p 9.(q∨r )’ → p 10.p’ → (q∨r )

Hipótesis Hipótesis 1; Variantes de la bicondicional; 25a 3; Simplificación; 11 2; Contrapositiva; 23 4,5; Conjunción; 14 6; Dilema constructivo; 9b 7; Ley de idempotencia; 21b 8; Ley de Morgan; 22a 9; Contrapositiva; 23

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 21 -

Matemáticas para la computación

g)

1.2.3.4.5.6.7.8.9.10.11.12.13.-

Demostración por el método directo del siguiente teorema. [ (p ∧ r ) → q ] ∧ [r’ → p ] ∧ [p ∧ r’ ]’ ⇒ [r ∨ q] Demostración. (p ∧ r ) → q r’ → p (p ∧ r’ )’ q’ → (p ∧ r )’ q’ → (p’ ∨ r’ ) [r’ → p ] ∧ [q’ → (p’ ∨ r’ ) ] [r’ ∧ q’ ] → [p ∧ (p’ ∨ r’ ) ] [r’ ∧ q’ ] → [(p ∧ p’) ∨ (p ∧ r’ ) ] [r’ ∧ q’ ] → [ 0 ∨ (p ∧ r’ ) ] [r’ ∧ q’ ] → [p ∧ r’ ] [r’ ∧ q’ ]’ r’’ ∨ q’’ r∨q

Hipótesis Hipótesis Hipótesis 1; Contrapositiva; 23 4; Ley de Morgan; 22b 2,5; Conjunción; 14 6; Dilema constructivo; 9b 7; Ley distributiva; 20b 8; Contradicción; 26 9; Ley de identidad; 27a 10,3; Modus tollens; 16 11; Ley de Morgan; 22b 12; Doble negación; 17

4.16.- Demostración por contradicción de los teoremas del problema 4.14. a) [p → (q ∧ r)] ∧ [(q ∨ s) → t] ∧ (p ∨ s) ⇒ (r ∨ t) 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.-

p → (q ∧ r) (q ∨ s) → t (p ∨ s) (r ∨ t)’ r ‘∧ t’ r’ t’ (q ∨ s)’ q’∧s’ q’ s’ p’→ s p (q ∧ r) q q’∧q 0

Hipótesis Hipótesis Hipótesis Negación de conclusión. 4; Ley de Morgan; 22a 5; Simplificación: 11 5; Simplificación; 11 2,7; Modus tollens; 16 8; Ley de Morgan; 22a 9; Simplificación; 11 9; Simplificación; 11 3; Variantes de la condicional; 24a 12,11; Modus tollens; 16 13,1; Modus ponenes; 15 14; Simplificación; 11 10,15; Conjunción; 14 16; Contradicción; 26

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 22 -

Matemáticas para la computación

b) [ (p ∧ q) → r ] ∧ [q’ → s’ ] ⇒ [(r’ ∧ s) → p’ ] 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.-

(p ∧ q) → r q’ → s’ [(r’ ∧ s) → p’ ]’ [(r’ ∧ s)’ ∨ p’ ]’ (r’ ∧ s) ∧ p (r’ ∧ s) p [(p ∧ q) → r] ∧ [q’ → s’ ] [(p ∧ q) ∨ q’] → [ r ∨ s’] [q’∨ (p ∧ q)] → [ r ∨ s’] [(q’∨ p) ∧ (q’∨ q)] → [ r ∨ s’] [(q’∨ p) ∧ 1] → [ r ∨ s’] (q’∨ p) → [ r ∨ s’] [ r ∨ s’]’ → [ q’ ∨ p]’ [ r ‘∧ s] → [ q ∧ p’] [ q ∧ p’] p’ p ∧p’ 0

Hipótesis Hipótesis Negación de la conclusión. 3; Variantes de la condicional; 24a. 4; Ley de Morgan; 22a. 5; Simplificación; 11 5; Simplificación; 11 1,2; conjunción; 14 8; Dilema constructivo; 9a. 9; Ley conmutativa; 18a. 10; Ley distributiva; 20a. 11; Ley de identidad; 27d 12; Ley de identidad; 27e 13; Contrapositiva; 23 14; Ley de morgan; 22a. 6,15; Modus Ponens; 15 16; Simplificación; 11 7,17; Conjunción; 14 18; contradicción; 26

c) [ (p’ ∧ r ) → q ] ∧ q’ ∧ [r → s ] ⇒ [ r → ( s ∧ p ) ] 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.-

(p’ ∧ r ) → q q’ r→s [r→(s∧p)] ‘ [ r ‘∨ ( s ∧ p ) ] ‘ r ∧( s ∧ p )’ r ( s ∧ p )’ (p’ ∧ r )’ p ∨ r’ p’ → r’ p s’∨ p’ p’∨ s’ p → s’ s p’ p ∧ p’ 0

Hipótesis Hipótesis Hipótesis Negación de la conclusión. 4; Variantes de la condicional; 24a. 5; Ley de Morgan; 22a. 6; Simplificación; 11 6; Simplificación; 11 1,2; Modus tollens; 16 9; Ley de Morgan; 22b 10; Variantes de la condicional; 24a. 11,7; Modus tollens; 16 8 ; Ley de Morgan ; 22b 13; Ley conmutativa; 18a. 14; Variantes de la condicional; 24a. 7,3; Modus ponens; 15 15,16; Modus Tollens; 16 12,17; Conjunción; 14 18; Contradicción; 26

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 23 -

Matemáticas para la computación

d) [ p’ → q’ ] ∧ (r → s’ ) ∧ [(q’ ∨ s’ ) → w ] ⇒ [ w’ → (p ∧ r’ ) ] 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.19.20.-

p’ → q’ r → s’ (q’ ∨ s’ ) → w [ w’ → (p ∧ r’ ) ]’ [ w ∨ (p ∧ r’ ) ]’ w’ ∧ (p ∧ r’ )’ w’ (p ∧ r’ )’ p’ ∨ r p→r p → s’ (q’ ∨ s’ )’ q∧s q s p p’ p ∧ p’ 0

Hipótesis Hipótesis Hipótesis Negación de la conclusión. 4; Variantes de la condicional; 24a. 5; Ley de Morgan; 22a. 6; Simplificación; 11 6; Simplificación; 11 8; Ley de Morgan; 22b 9; Variantes de la condicional; 24a. 10,2; Silogismo hipotético; 13 3,7; Modus Tollens; 16 12; Ley de Morgan; 22a. 13; Simplificación; 11 13; Simplificación; 11 1,14; Modus Tollens; 16 11,15; Modus Tollens; 16 16,17; Conjunción; 14 19; Contradicción; 26

e) [ p ↔ q’ ] ∧ [r ∨ q’] ∧ p’ ∧[p’ → r]⇒ [[r →(r ∨ q)] ∧ p] 1.2.3.4.5.6.7.8.9.10.11.-

p ↔ q’ r’ ∨ q’ p’ p’ → r [[r →(r ∨ q)] ∧ p]’ [r →(r ∨ q)]’ ∨ p’ [r’ ∨ (r ∨ q)]’ ∨ p’ [(r’∨ r) ∨ q)]’ ∨ p’ [1 ∨ q)]’ ∨ p’ 1’∨ p’ p’

Hipótesis Hipótesis Hipótesis Hipótesis Negación de conclusión. 5; Ley de Morgan; 22b 6; Variantes de la condicional; 24a. 7; Ley asociativa; 19a. 8; Ley de identidad; 27d. 9; Ley de identoidad; 27b 10; Ley de identidad; 27a.

Observar que p’ es una hipótesis que se considera verdadera porque es parte del enunciado, y de la negación de la conclusión resultó que también p’ es verdadera, algo que no debe suceder, por lo tanto se considera que el teorema es falso.

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 24 -

Matemáticas para la computación

4.17.a) Primera. Demostración por el método directo del teorema: [ (p∨q)→r] ∧ [r → s] ⇒ [s’ → q’] Demostración 1.(p∨q)→r 2.r→s 3.q → (q∨ p) 4.q → (p∨ q) 5.q→ r 6.q→ s 7.s’ → q’

Hipótesis Hipótesis Adición; 1 1; Ley conmutativa; 18a 4,1; Silogismo hipotético; 13 5,2; Silogismo hipotético; 13 6; Contrapositiva; 23

Otra manera de resolver el mismo problema es: [ (p∨q)→r] ∧ [r → s] ⇒ [s’ → q’] Demostración 1.(p∨q)→r 2.r→s 3.r’ → (p∨ q)’ 4.r’ → (p’∧ q’) 5.s’→ r’ 6.s’→ (p’∧q’) 7.(q’∧p’) → q’ 8.(p’∧q’) → q’ 9.s’ → q’

Hipótesis Hipótesis 1; Contrapositiva; 23 3; Ley de Morgan; 22a 2; Contrapositiva; 23 5,4; Silogismo hipotético; 13 Simplificación; 2 7; Ley conmutativa; 18b 6,8; Silogismo hipotético; 13

Demostración por contradicción del teorema: [ (p∨q)→r] ∧ [r → s] ⇒ [s’ → q’] Demostración 1.(p∨q)→r 2.r→s 3.[s’ → q’]’ 4.[[s’ ∧ q]’ ]’ 5.s’ ∧ q 6.s’ 7.q 8.(p ∨ q) → s 9.s’ → (p ∨ q)’ 10.s’→ (p’∧q’) 11.(q’∧p’) → q’ 12.(p’∧q’) → q’ 13.s’ → q’ 14.q’

Hipótesis Hipótesis Negación de la conclusión. 3; Variantes de la condicional; 24b 4; Doble negación; 17 5; Simplificación; 11 5; Simplificación; 11 1,2; Silogismo hipotético; 13 8; Contrapositiva; 23 9; Ley de Morgan; 22a Simplificación; 2 11; Ley conmutativa; 18b 10,12; Silogismo hipotético; 13 6,13; Modus ponens; 15

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 25 -

Matemáticas para la computación

15.16.b)

q∧q’ 0

7,14; Conjunción; 14 15; Contradicción; 26

Primera. Demostración por el método directo del siguiente teorema. [(p ∧ q) → r] ∧ [q’ → s’ ] ⇒ [(r’ ∧ s)→ (q ∧ p’)] 1.2.3.4.5.6.7.8.9.10.11.-

(p ∧ q) → r q’ → s’ r’ → (p ∧ q)’ r’ → (p’ ∨ q’) s→q [r’ → (p’ ∨ q’)]∧[ s → q] (r’∧s) → [(p’ ∨ q’) ∧ q] (r’∧s) → [q ∧ (p’ ∨ q’)] (r’ ∧ s) → [(q ∧ p’)∨ (q ∧ q’)] (r’ ∧ s) → (q ∧ p’) ∨ 0 (r’ ∧ s) → (q ∧ p’)

Hipótesis Hipótesis 1; Contrapositiva; 23 3; Ley de Morgan; 22b 2; Contrapositiva; 23 4,5; Conjunción; 14 6; Dilema constructivo; 9b 7; Ley conmutativa; 18b 8; Ley distributiva; 20b 9; Contradicción; 26 10; Ley de identidad; 27a

Otra manera de resolver el mismo problema es [ (p ∧ q ) → r ] ∧ [q’ → s’ ] ⇒ [ (r’ ∧ s) → (q∧ p’ )] Demostración. 1.(p ∧ q ) → r 2.q’ → s’ 3.[(p ∧ q ) → r ] ∧ [q’ → s’ ] 4.[(p ∧ q ) ∨ q’ ] → (r ∨ s’ ) 5.[q’ ∨ (p ∧ q ) ] → (r ∨ s’ ) 6.(r ∨ s’ )’ → [q’ ∨ (p ∧ q ) ]’ 7.(r’ ∧ s ) → [q ∧ (p ∧ q )’ ] 8.(r ∧ s’ ) → [q ∨ (p’ ∨ q’ ) ] 9.(r ∧ s’ ) → [(q ∧p’) ∨ (q ∧ q’ ) ] 10.(r ∧ s’ ) → (q ∧p’) ∨ 0 11.(r ∧ s’ ) → (q ∧p’)

Hipótesis Hipótesis 1,2; Conjunción; 14 3; Dilema constructivo; 9a 4; Ley conmutativa; 18a 5; Contrapositiva; 23 6; Ley de Morgan; 22a 7; Ley de morgan; 22b 8; Ley distributiva; 20b 9; Contradicción; 26 10; Ley de identidad; 27a

Demostración por contradicción del teorema. [ (p ∧ q ) → r ] ∧ [q’ → s’ ] ⇒ [ (r’ ∧ s) → (q∧ p’ )] 1.2.3.4.-

(p ∧ q ) → r q’ → s’ [ (r’ ∧ s) → (q∧ p’ )]’ [[ (r’ ∧ s) ∧ (q∧ p’ )’ ]’ ]’

Hipótesis Hipótesis Negación de la conclusión. 3; Variantes de la condicional; 24b

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 26 -

Matemáticas para la computación

5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.c)

(r’ ∧ s) ∧ (q∧ p’ )’ (r’ ∧ s) r’ s (q∧ p’ )’ [(p ∧ q ) → r ] ∧ [q’ → s’ ] [(p ∧ q ) ∨ q’ ] → (r ∨ s’ ) [q’ ∨ (p ∧ q ) ] → (r ∨ s’ ) [(q’∨ p) ∧ (q’∨ q )] → (r∨ s’) (r ∨ s’ )’ → [(q’∨ p) ∧ (q’∨ q ) ]’ (r ∨ s’ )’ → [(q’∨ p)’ ∨ (q’∨ q )’ ] (r’ ∧ s ) → [(q ∧p’) ∨ (q ∧ q’ ) ] (r’ ∧ s ) → (q ∧p’) ∨ 0 (r’ ∧ s ) → (q ∧p’) (r’ ∧ s )’ (r ∨ s’ ) s’ s∧s’ 0

4; Doble negación; 17 5; Simplificación; 11 6; Simplificación; 11 6; Simplificación; 11 5; Simplificación; 11 1,2; Conjunción; 14 10; Dilema constructivo; 9a 11; Ley conmutativa; 18a 12; Ley distributiva; 20a 13; Contrapositiva; 23 14; Ley de Morgan; 22b 15; Ley de Morgan; 22a 16; Contradicción; 26 17; Ley de identidad; 27a 18,9; Modus tollens; 16 19; Ley de Morgan; 22b 20,8; Silogismo disyuntivo; 12 8,21; Conjunción; 14 22; Contradicción; 26

Demostración por el método directo: [p → (q ∧ r) ] ∧ [(q ∨ s) → t ] ∧ (p ∨ s) ⇒ t Demostración. 1.p → (q ∧ r) 2.(q ∨ s) → t 3.p∨s 4.(q∧r) → q 5.p→q 6.(p ∨ s) → (q ∨ r’) 7.(q ∨ r’) 8.t

Hipótesis Hipótesis Hipótesis Simplificación; 11 1,4; Silogismo hipotético; 13 5; Extensión de la condcional; 8a 6,3; Modus ponens; 15 7,2; Modus ponens; 15

Demostración por contradicción. [p → (q ∧ r) ] ∧ [(q ∨ s) → t ] ∧ (p ∨ s) ⇒ t Demostración 1.p → (q ∧ r) 2.(q ∨ s) → t 3.p∨s 4.t’ 5.(q∨ s)’

Hipótesis Hipótesis Hipótesis Negación de la conclusión 2,4; Modus tollens; 16

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 27 -

Matemáticas para la computación

6.7.8.9.10.11.12.13.14.15.-

q’ ∧ s’ q’ s’ ∧ q’ s’ s∨p p q∧r q q ∧ q’ 0

5; Ley de Morgan; 22a 6; Simplificación; 11 6; Ley conmutativa; 18b 8; Simplificación; 11 3; Ley conmutativa; 18a 10,9; Silogismo disyuntivo; 12 11,1; Modus ponens; 15 12; Simplificación; 11 13,7; Conjunción; 14 14; Contradicción; 26

d) Demostración por el método directo del teorema: [p’ → r] ∧ q’ ∧ (p ∨ r’) ∧ (r → q) ⇒ [[p’ → (p ∧ q)] ∧ q’ ] Demostración 1.p’ → r 2.q’ 3.(p ∨ r’) 4.r→q 5.p’ → r’ 6.r→p 7.(r → p) ∧ (r → q) 8.(r ∧ r) → (p ∧ q) 9.r→ (p ∧ q) 10.p’ → (p ∧ q) 11.[p’ → (p ∧ q)] ∧ q’

Hipótesis Hipótesis Hipótesis Hipótesis 3; Variantes de la condicional; 24a 5; Contrapositiva; 23 6,4; Conjunción; 14 7; Dilema constructivo; 9b 8; Ley de idempotencia; 21b 1,9; Silogismo hipotético; 13 10,2; Conjunción; 14

Demostración por contradicción. [p’ → r] ∧ q’ ∧ (p ∨ r’) ∧ (r → q) ⇒ [[p’ → (p ∧ q)] ∧ q’ ] Demostración 1.p’ → r 2.q’ 3.(p ∨ r’) 4.r→q 5.[[p’ → (p ∧ q)] ∧ q’ ]’ 6.[[[p’ → (p ∧ q)] → q]’ ]’ 5; 7.[p’ → (p ∧ q)] → q 8.[p’ → (p ∧ q) ]’ 9.[p ∨ (p ∧ q) ]’ 10.p’ ∧ (p ∧ q)’ 11.p’ 12.(p ∧ q)’ 13.p’ → q

Hipótesis Hipótesis Hipótesis Hipótesis Negación de la conclusión Variantes de la condicional; 24d 6; Doble negación; 17 7,2; Modus Tollens; 16 8; Variantes de la condicional; 24a 9; Ley de Morgan; 22a 10; Simplificación; 11 11; Simplificación; 11 1,4; Silogismo hipotético; 13

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 28 -

Matemáticas para la computación

14.15.16.-

p p ∧ p’ 0

13,2; Modus Tollens; 16 11,14; Conjunción; 14 15; Contradicción; 26

e) Demostración por el método directo del teorema: [ p’ → q’ ] ∧ [ r’ → s’ ] ∧ [(q’ ∨ s’ ) → t ] ⇒ [ t’ → (p ∧ r ) ] Demostración 1.2.3.4.5.6.7.8.-

p’ → q’ r’ → s’ (q’ ∨ s’ ) → t [p’ → q’] ∧ [r’ → s’] 1,2; (p’ ∨ r’ ) → (q’ ∨ s’ ) 4; (p’ ∨ r’ ) → t t’ → (p’ ∨ r’ )’ t’ → (p ∧ r )

Hipótesis Hipótesis Hipótesis Conjunción; 14 Dilema constructivo; 9ª 5,3; Silogismo hipotético; 13 6; Contrapositiva; 23 7 ; Ley de Morgan ; 22a

Demostrar por contradicción el siguiente teorema. [ p’ → q’ ] ∧ [ r’ → s’ ] ∧ [(q’ ∨ s’ ) → t ] ⇒ [ t’ → (p ∧ r ) ] Demostración 1.p’ → q’ 2.r’ → s’ 3.(q’ ∨ s’ ) → t 4.[ t’ → (p ∧ r ) ]’ 5.[ t ∨ (p ∧ r ) ]’ 6.t’ ∧ (p ∧ r )’ 7.t’ 8.(p ∧ r )’ 9.[p’ → q’ ]∧ [r’ → s’ ] 1,2; 10.(p’ ∨ r’) → (q’ ∨ s’) 11.(p ∧ r)’ → (q’ ∨ s’) 12.(p ∧ r)’ → t 13.t 14.t’ ∧ t 15.0

Hipótesis Hipótesis Hipótesis Negación de la conclusión 4; Implicación; 24c 5; Ley de Morgan; 22a 6; Simplificación; 11 6; Simplificación; 11 Conjunción; 14 9; Dilema constructivo; 9a 10; Ley de Morgan; 22b 11,3; Silogismo hipotético; 13 8,12; Modus ponens; 15 7,13; conjunción; 14 14; Contradicción; 26

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 29 -

Matemáticas para la computación

4.18.a) 3 + 6 + 20 +............+ [n (n !) +2] = (n + 1)! + 2n – 1 Paso básico k = n = 1 [n (n !) + 2 ] = 1 (1! ) + 2 = 3 ∴ Se cumple el paso básico. Paso inductivo k = n+1 3 + 6 + 20 +............+ [n (n !) +2] + [(n+1)(n+1)!+2]= (n + 1)! + 2n – 1 + [(n+1)(n+1)!+2] = (n + 1)![1+(n+1)] + 2n + 2 - 1 = (n + 1)![(n + 1)+1] + 2(n + 1) -1 Sustituyendo k = n+1 = k! (k + 1) + 2k – 1 Se sabe que k! = 1 D 2 D 3 D ....... D k (k + 1)! = 1 D 2 D 3 D ....... D k D (k+1) ∴ (k + 1)! = k! (k +1) = (k + 1)! + 2k –1

∴ Se cumple el paso inductivo.

b)

0 + 3 + 8 +.........+ (n 2 − 1) = Paso básico k = n = 1 (n 2 − 1) = 12 – 1 = 0

n(2n + 5)(n − 1) 6 ∴ Se cumple el paso básico

Paso inductivo k = n+1

n(2n + 5)(n − 1) + [ (n + 1) 2 − 1 ] 6 n(2n + 5)(n − 1) + 6[(n + 1) 2 − 1] n(2n + 5)(n − 1) + 6(n 2 + 2n + 1 − 1) = = 6 6 2 n(2n + 5)(n − 1) + 6(n + 2n) n(2n + 5)(n − 1) + 6n(n + 2) = = 6 6 2 n[(2n + 5)(n − 1) + 6(n + 2)] n(2n − 2n + 5n − 5 + 6n + 12) = = 6 6 2 n(2n + 9n + 7) n(2n + 7)(n + 1) n(n + 1)[2(n + 1) + 5] = = = 6 6 6 (n + 1 − 1)(n + 1)[2(n + 1) + 5] (k − 1)k (2k + 5) k (2k + 5)(k − 1) = = = 6 6 6

0 + 3 + 8 +.........+ (n 2 − 1) + [ (n + 1) 2 − 1 ]=

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 30 -

Matemáticas para la computación

c)

n[n(n + 1) 2 − 4] 0 + 7 + 26 +............+ (n − 1) = 4 3

Paso básico k = n = 1 (n3 − 1) = 13 –1 = 0 Paso inductivo k = n+1

∴ Se cumple el paso básico.

n[n(n + 1) 2 − 4] 0 + 7 + 26 +............+ (n − 1) + [(n + 1) − 1] = + [(n + 1)3 − 1] 4 2 3 2 2 n[n(n + 1) − 4] + 4[(n + 1) − 1] n (n + 1) − 4n + 4(n + 1)3 − 4 = = 4 4 2 2 2 2 (n + 1) [n + 4(n + 1)] − 4n − 4 (n + 1) (n + 4n + 4) − 4n − 4 = = 4 4 (n + 1) 2 (n + 2)(n + 2) − 4(n + 1) (n + 1) 2 (n + 1 + 1)(n + 1 + 1) − 4(n + 1) = = 4 4 3

=

3

k 2 (k + 1)(k + 1) − 4k k 2 (k + 1) 2 − 4k k[k (k + 1) 2 − 4] = = 4 4 4

d) 2 – 3 + 10 – 15 + ..........+ [(−1)

n +1

Paso básico k = n = 1 [(−1) n +1 n 2 + 1] = (-1)1+112+1 = 2

n[(−1) n +1 (n + 1) + 2] n + 1] = 2 2

∴ Se cumple el paso básico

Paso inductivo k = n+1 2 – 3 + 10 – 15 + ..........+ [(−1) n +1 n 2 + 1] + [(−1) n +1+1 (n + 1) 2 + 1] = + [(−1) n +1+1 (n + 1) 2 + 1]

n[(−1) n +1 (n + 1) + 2] + 2[(−1) n +1+1 (n + 1) 2 + 1] 2 n +1 n[(−1) (n + 1) + 2] + 2(−1) n +1+1 (n + 1) 2 + 2 = 2 n +1 n(−1) (n + 1) + 2n + 2(−1) n +1+1 (n + 1) 2 + 2 = 2

=

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 31 -

n[(−1) n +1 (n + 1) + 2] 2

Matemáticas para la computación

= = = = =

(−1) n +1 (n + 1)[n + 2(−1)1 (n + 1)] + 2n + 2 2 n +1 (−1) (n + 1)(n − 2n − 2) + 2n + 2 2 n +1 (−1) (n + 1)(−n − 2) + 2n + 2 (−1) n +1 (n + 1)(−1)(n + 2) + 2(n + 1) = 2 2 n +1 k (−1) (n + 1)(−1)(n + 1 + 1) + 2(n + 1) (−1) k (−1)(k + 1) + 2k = 2 2 k +1 k +1 (−1) k (k + 1) + 2k k[(−1) (k + 1) + 2] = 2 2

4.19.a) 5 + 15 + 25 + 35 +……+ (10n - 5) = 5n2 Paso básico k = n = 1 (10n - 5) = 10(1) – 5 = 5

∴ Se cumple el paso básico.

Paso inductivo k = n+1 5 + 15 + 25 + 35 +……+ (10n - 5) + [10(n+1) – 5] = 5n2 + [10(n+1) – 5] = 5n2 + 10n + 5 = 5(n2 + 2n + 1) = 5(n + 1)(n + 1) Sustituyendo k = n+1 = 5k2 ∴ Se cumple el paso inductivo

b)

3 3 3 3 3 3n + + + +……..+ = 1D 3 3 D 5 5 D 7 7 D 9 (2n − 1)(2n + 1) (2n + 1) Paso básico k = n = 1

3 3 3 = = (2n − 1)(2n + 1) [2(1) − 1][2(1) + 1] 1 D 3 Paso inductivo k = n+1

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 32 -

∴ Se cumple el paso básico.

Matemáticas para la computación

3 3 3 3 3 3 3n + + + +……..+ + = + 1D 3 3D 5 5D7 7D9 (2n − 1)(2n + 1) [2(n + 1) − 1][2(n + 1) + 1] (2n + 1) 3 [2(n + 1) − 1][2(n + 1) + 1] 3n 3 + = (2n + 1) (2n + 1)(2n + 3) (2n + 3)3n + 3 (6n 2 + 9n + 3) = = (2n + 1)(2n + 3) (2n + 1)(2n + 3) 3(2n + 1)(n + 1) 3(2n 2 + 3n − 1) = = (2n + 1)(2n + 3) (2n + 1)(2n + 3) 3(n + 1) 3(n + 1) 3k = = = (2n + 3) (2(n + 1) + 1) (2k + 1)

a a a a (a n +1 − 1) a c) + + + +…….+ = a ∈R; a ≠0; a ≠1 2(a − 1) 2 2 2 2 2 2

3

4

n

Paso básico k = n = 1

a n a1 a = = 2 2 2

∴ Se cumple el paso básico

Paso inductivo k = n+1 2

3

4

n

a a a a a a + + + +…….+ + 2 2 2 2 2 2 (a n +1 − 1) = 2(a − 1)

n +1

=

a + 2

(a n +1 − 1) a + 2(a − 1) 2 n +1

=

n +1

(a n +1 − 1) + (a − 1)a n +1 2(a − 1)

=

(a n +1 − 1) + (a n + 2 − a n +1 ) (a n + 2 − 1) = 2(a − 1) 2(a − 1)

=

(a n +1+1 − 1) (a k +1 − 1) = 2(a − 1) 2(a − 1)

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 33 -

Matemáticas para la computación

d) 2n ≥ n2

n∈Z+; n≥4

Paso básico k = n = 4 (ya que en este caso se indica que el primer elemento no es cuando n=1) 2 n = 24 ≥ 4 2 Paso inductivo k = n+1 2n + 2n+1 ≥ n2 + 2n+1 2n + 2n+1 ≥ n2 + 2n2 Sabemos que ∀n; n∈Z+ 2n ≥ (n+1) Sustituyendo 2n = (n+1) se tiene que: 2n + 2n+1 ≥ n2 + (n+1) 2 2n + 2n+1 ≥ n2 + 2n +2 2n + 2n+1 ≥ (n + 1)(n +1) Como k = n+1 2n + 2n+1 ≥ k2 e)

20 +21 +22 +23 +……..+ 2n = 2n+1 – 1

n∈N

Paso basico k = n = 0 (en este caso n = 0, ya que es el primer elemento de N) 2 n = 20

f)

∴ se cumple el paso básico

Paso inductivo k = n+1 20 +21 +22 +23 +……..+ 2n + 2n+1 = 2n+1 – 1+ 2n+1 = 22n+1 – 1 = 2n+2 – 1 = 2n+1+1 – 1 = 2k+1 – 1 1-1 2-1 3-1 (2 ) + (2 ) + (2 ) +…….+ (2n-1) = 2n - 1 Paso básico k = n =1 (2n-1) = (21-1)

∴ se cumple el paso básico

Paso inductivo k = n+1 (21-1) + (22-1) + (23-1) +…….+ (2n-1) + (2n+1-1) = 2n – 1+ (2n+1-1) = 22n – 1 = 2n+1 – 1 = 2 k – 1

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 34 -

Matemáticas para la computación

4.20.Observar que el término n-enésimo es (2x+1) = (2n + 1). La sumatoria se puede encontrar al observar que: N 1 2 3 4

1+1

2 +1-2 22+1+2-2 23+1+3-2 24+1+4-2

Total 3 8 17 34

Así sucesivamente, de donde se deduce que la expresión que permite encontrar el total de la sumatoria en función de n es: 2n+1 + n-2 Por lo tanto la sumatoria queda de la siguiente manera: 3 + 8 + 17 +.........+ (2n+1) = 2n+1 + n-2 Por inducción matemática se tiene: Paso básico k = n = 1 (2n+1) = (21+1) = 3

∴ Se cumple el paso básico

Paso inductivo k = (n + 1) 3 + 8 + 17 +.........+ (2n+1) + (2n+1+1) = 2n+1 + n -2 + (2n+1+1) = 2n+1 + n -2 + 2n+1+1 = 2n+1 + 2n+1 + n +1 -2 = 2k + 2k + k -2 = 22k + k -2 = 2k+1 + k -2 ∴ Se cumple el paso inductivo

4.21.Si n=6 se obtienen los siguientes valores para cada una de las variables.

x 1 2 3 4 5 6

e 2 5 8 11 14 17

s 2 7 15 26 40 57

SE NOTA QUE EL TÉRMINO N-ESIMO ES (3N-1) YA QUE ES EL QUE GENERA LOS TÉRMINOS QUE SE VAN SUMANDO EN CADA ITERACIÓN.

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 35 -

Matemáticas para la computación

Si n = 6; los elementos a sumar son: 2 + 5+ 8 + 11 + 14 + 17 Se observa que al sumar los extremos el resultado es 2+17=19, el segundo con el penúltimo 5+14=19 y también 8+11=19. Como n=6 entonces 19=3(6)+1=3n+1. Además como son tres parejas las que se están sumando 3= parejas por el resultado de las sumas se tiene que:

3n 2 + n n(3n + 1) = . De tal mono que la proposición P(n) a 2 2

probar por medio de inducción matemática es como sigue:

3n 2 + n 2 + 5 + 8 + ........+ (3n − 1) = 2 Paso básico k = n = 1 (3n − 1) = 3(1) – 1 =2

∴ Se cumple el paso básico.

Paso inductivo k = n+1

3n 2 + n + [3(n + 1) − 1] 2 3n 2 + n 3n 2 + n + 2[3(n + 1) − 1] + [3(n + 1) − 1] = 2 2 2 2 3n + n + 2(3n + 2) 3n + n + 6n + 4 = 2 2 2 3n + 7n + 4 (3n + 4)(n + 1) [3(n + 1) + 1](n + 1) = = 2 2 2 2 (3k + 1)k (3k + k ) = 2 2

2 + 5 + 8 + ........+ (3n − 1) + [3(n + 1) − 1] = = = = =

4.22.- El sort de selección por intercambio funciona de la siguiente manera: • • • •

Buscar el menor de los elementos de la lista Intercambiarlo con el primero Buscar el menor de los elementos en el resto de la lista Intercambiarlo con el segundo. 5 8 20 26 32 3

3 8 20 26 32 5

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 36 -

3 5 20 26 32 8

n . Al multiplicar el número de 2

3 5 8 26 32 20

3 5 8 20 32 26

3 5 8 20 26 32

Matemáticas para la computación

De tal manera que en la primera pasada al menos ya se tiene el primero en la posición que debe ocupar y el número de comparaciones en esa primera pasada es (n-1). En la segunda pasada el elemento que ocupará la segunda posición ya está en su lugar y el número de comparaciones es (n-2) y así sucesivamente. Es obvio que el número de comparaciones depende de la forma en que estén colocados los datos y el método termina cuando ya no hace intercambios, pero en el peor de los casos el número de comparaciones es:

n2 − n , 2

como ocurre con el sort de la burbuja, de tal manera que la sumatoria y la forma de demostrar que la proposición es verdadera por medio del “Sort de selección por intercambio” es: 0 + 1 + 2 + 3 + ............+ (n-1) =

n2 − n 2

El número de intercambios es 0, si el conjunto de datos a ordenar es 1, el número de comparaciones es 1,si el conjunto de datos a ordenar son 2 y así sucesivamente. Demostración por inducción: 0 + 1 + 2 + 3 + ............+ ( n -1) = Paso básico k = n = 1 ( n -1) = 1-1 = 0

n2 − n 2

∴ Por lo tanto el paso básico se cumple.

Paso inductivo k = n+1 0 + 1 + 2 + 3 + ............+ ( n -1) + [( n +1)-1] =

n2 − n + [( n +1)-1] 2

n 2 − n + 2[(n + 1) − 1] n 2 − n + 2n = = 2 2 2 n +n n(n + 1) (n + 1 − 1)(n + 1) = = = 2 2 2 (k − 1)k k (k − 1) = ∴Por lo tanto el paso inductivo se cumple. = 2 2 4.23.- Para demostrar que en el peor de los casos el número de comparaciones que lleva a cabo el sort de la burbuja es

n2 − n , es necesario saber la mecánica en que realiza el ordenamiento de información. 2

Considerar que n=5 y que los elementos a ordenar son: 8,4,-1,10,2.

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 37 -

8 4 -1 10 2

4 -1 8 2 10

-1 4 2 8 10

-1 2 4 8 10

0 Comparaciones

4ª. Pasada

1 Comparaciones

3ª. Pasada

2 Comparaciones

2ª. Pasada

3 Comparaciones

1ª.Pasada

4 comparaciones

Inicialmente

Matemáticas para la computación

-1 2 4 8 10

En cada paso el algoritmo lleva a cabo (n-1) comparaciones, pero además después de la primera pasada el dato que se encuentra al final (en este caso el 10) se considera que ya está en su lugar y ya no lo toma en cuenta en la siguiente pasada. Al recorrer nuevamente la información el número de comparaciones se disminuye en 1 y el penúltimo dato ya no lo toma en cuenta y así sucesivamente hasta terminar.

Por lo anterior la proposición P(n) que representa el funcionamiento del sort de la burbuja es:

0 + 1 + 2 + 3 + ............+ (n-1) =

n2 − n 2

Comparaciones en la 1ª. pasada Comparaciones en la penúltima pasada Comparaciones en la ultima pasada

0 + 1 + 2 + 3 + ............+ ( n -1) = Paso básico k = n = 1 ( n -1) = 1-1 = 0

n2 − n 2

∴ Por lo tanto el paso básico se cumple.

Paso inductivo k = n+1 0 + 1 + 2 + 3 + ............+ ( n -1) =

n2 − n 2

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 38 -

Matemáticas para la computación

0 + 1 + 2 + 3 + ............+ ( n -1) + [( n +1)-1] =

n2 − n + [( n +1)-1] 2

n 2 − n + 2[(n + 1) − 1] n 2 − n + 2n = 2 2 2 n +n n(n + 1) (n + 1 − 1)(n + 1) = = = 2 2 2 k (k − 1) (k − 1)k = = 2 2 =

4.24.El árbol más pequeño es aquel que está integrado por 2 nodos. Observar también que a partir de este árbol pequeño, cada vez que se agrega un nodo, se debe agregar también una arista, lo cual implica sumar un 1 en cada paso. a

a

a

b

b

c

b

c e

Por lo anterior se puede decir que el término n-enésimo es: 1n+1. De tal manera que la sumatoria queda integrada de la siguiente manera: 1 + 1 + 1 + …….. + 1n -1 = (n-1) Paso básico k = n = 1 1n - 1 = 11- 1 = 10= 1 Paso inductivo k = (n + 1)

∴ Se cumple el paso básico

1 + 1 + 1 + …….. + 1n- 1 + 1(n+1) - 1

= (n-1) + 1(n+1) - 1 = n-1 + 1n+1 - 1 = n -1 + 1n = n -1 + 1 = n +1 – 1 = (k –1)

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 39 -

∴ Se cumple el paso inductivo

Matemáticas para la computación

4.25.Sean: p: “Tiene alas”. q: “Vuelan” r: “Tienen alas y vuelan” s: “Cacarean” t: “Ponen huevos” u: “Es ave” v: “Es gallina” w: “Es mamífero” a) b) c) d) e) f) g) h)

∀x p(x). (falso) ∃x q(x). (cierto) ∃x [p(x) ∧ q(x)] o bien ∃x r(x) (cierto) ∃x [p(x) ∧ q’(x)] (cierto) ∀x u(x) ⇒ p(x) (cierto) ∀x [u(x) ∧ t(x) ∧ s(x)] ⇒ v(x) (cierto) ∃x [v(x) ∧ t’(x)] (cierto) ∀x u(x) ⇒ w’(x). (cierto)

4.26.Sea: U = {x | x es un animal} A = {a | a es un gato} B = {b | b es un perro} C = {c | c es un león} p: Es carnívoro. q: Canta. i) j) k) l) m) n)

∀a p(a). ( verdadero ) p(x) ∧ p’(b) ⇒ p(a). ( falso ) p(x) ⇔ p(b) ∨ p(a) ( falso ) ∀a p(a) ⇒ ∀a q’(a) ( verdadero ) ∀x q(x) ⇒ ∀x p’(b) ∧∀x p’(a) ( falso ) p(x) ∧ q’(x) ∧ p’(b) ∧ p’(a) ⇒ p(c) ( falso )

4.27.a) “Para todo número real, existe al menos un número real en donde se cumple que y=x2-1” (Verdadero) ya que para todo número real (∀x), siempre se va a encontrar un real (∃y) que satisface y=x2-1. b) “Existe un número real para el cual se cumple que y=x2-1 para todos los números reales”. (Falso) ya que dado x la igualdad y=x2-1 es cierta solo para uno o dos valores de y, pero no para todos.

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 40 -

Matemáticas para la computación

c) “Para algún número real, se cumple que y=x2-1 para todos los números reales”. (Falso), al igual que inciso b) ya que ∃x ∀y p(x,y) ⇔ ∀y ∃x p(x,y) ⇔ ∃x p(x,y) debido a que el conjunto del discurso es el mismo tanto para x como para y. Solamente cambiaron de posición los cuantificadores, pero no los parámetros. d) “Para todo número real se cumple que y=x2-1 para todos los reales”. (Falso) ya que existen algunos valores de “y” en donde para ningún valor de “x” se cumple que “y=x2-1”; ejemplo y=-2. e) “Para algún número real se cumple que y=x2-1 para cuando menos un número real”. (Verdadero) ya que todos los puntos de la parábola y=x2-1 satisfacen la condición. 4.28.a) Para todo número real x existe a menos un número real y en donde se cumple que x-y = 1. (Verdadero). b) Para todo número real x existe a menos un número real y en donde se cumple que x-y = 1. (Verdadero). c) Para cuando menos un número real x se cumple que x-y = 1, para todos los números reales y. (Falso ya que no existe ningún número real que cumpla dicha condición para todos los números reales) d) Para cuando menos un número real x se cumple que x-y = 1, para todos los números reales y. (Falso) e) Para todo número real x y y se cumple que x-y = 1. (Falso) f) Existe al menos un número real x en donde se cumple que x-y = 1, para cuando menos un número real y. (Verdadero) 4.29.a) ∃y ∀x [ p(x,y) ∧ q(x,y) ⇒ r(x,y)] b) ∀y ∃x [ p’(x,y) ∨ r(x,y) ⇒ q’(x,y)] c) ∃x ∃y r(x,y) ∨ ∃x q(x,y) ∧ ∃y p’(x,y)

x,y∈U x,y∈U x,y∈U

4.30.Sea U = {x, y | x, y ∈ R}; p: “x ≤ y”; q: “x − y = 1”; r: “x2 + y2 = 1”: a) ∃x∀y [r(x, y) ∧ p’(x, y)∨q(x,y)] b) ∀x ∃y [p(x,y)] ⇒ ∃y∃x [q’(x,y) ∨ r(x,y)] c) [∀x ∀y [p’(x, y)] ∧ ∃x p(x,y)] ⇒ ∀x ∀y r(x,y)

res_resptodoslogica_131009.d Editorial: Alfaomega Grupo Editorial - 41 -