• Author / Uploaded
• Erick Trejo

Citation preview

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO FACULTAD DE ESTUDIOS SUPERIORES ARAGÓN INGENIERÍA EN COMPUTACIÓN DR. ARTURO RODRÍGUEZ GARCÍA ESTRUCTURAS DISCRETAS

NOMBRE DE LOS ALUMNOS:

CORONA CASTRO LEONARDO GONZÁLEZ MANUEL ERICK RICARDO GUTIÉRREZ CRUZ CARLOS OSWALDO SALGADO FLORES CARLOS NOÉ

EJERCICIOS

Tema 1 Lógica proposicional 1. Construye las tablas de verdad de las siguientes proposiciones

a .( p ∧q ) →( p ∨q) P

p ∧q

q

V V F F

V F V F

p ∨q V F F F

¿) →( p ∨q) V V V F

V V V V

b. ( p ∧q ) ∧(∼ q ∧∼ r ) p V V V V F F F F

q

r

( p ∧q )

(∼ q ∧ ∼ r)

V V F F V V F F

V F V F V F V F

V V F F F F F F

F F F V F F F V

( p ∧q ) ∧(∼ q ∧∼ r ) F F F F F F F F

c .∼( p∨ q ∨r ∨ s) p

Q

R

( p ∨q ∨ r ∨ s)

s

. ∼( p ∨q ∨ r ∨ s)

V V

V V

V V

V F

V V

F F

V V V V V V F F F F

V V F F F F V V V V

F F V V F F V V F F

V F V F V F V F V F

V V V V V V V V V V

F F F F F F F F F F

F F F F

F F F F

V V F F

V F V F

V V V V

F F F V

( q ∧ r ) → ( s ∨t ) p ↔ [ ( q ∧ r ) → ( s ∨t ) ] ∼ { p ↔ [ ( q ∧r ) → ( s ∨t ) ] }

d .∼ { p ↔ [ ( q ∧r ) → ( s ∨ t ) ]} p

q

R

s

t

q∧r

( s ∨t )

V V V V V V V V V V V V V V V V F F F F F F F F F F F F F F F

V V V V V V V V F F F F F F F F V V V V V V V V F F F F F F F

V V V V F F F F V V V V F F F F V V V V F F F F V V V V F F F

V V F F V V F F V V F F V V F F V V F F V V F F V V F F V V F

V F V F V F V F V F V F V F V F V F V F V F V F V F V F V F V

V V V V F F F F F F F F F F F F V V V V F F F F F F F F F F F

V V V F V V V F V V V F V V V F V V V F V V V F V V V F V V V

V V V F V V V V V V V V V V V V V V V F V V V V V V V V V V V

V V V V V V V F V V V F V V V F V V V V V V V F V V V F V V V

F F F F F F F V F F F V F F F V F F F F F F F V F F F V F F F

F

F

F

F

F

F

F

V

F

V

2. Clasifica las preposiciones del ejercicio anterior en tautologías, contradicciones o contingencias. a) b) c) d)

Tautología Contradicción Contingencia Contingencia

3. Determine si las siguientes tablas son equivalentes

a .( p ↔ q)≡ [ ( p → q ) ∧ ( q → p ) ] P V V F F

q V F V F

P

q

( p →q )

(q → p)

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

V V F f

v f V F

V F V v

v V F V

V F F V

( p ↔ q) V F F V

Si son equivalentes.

b . ∼ ( p ∨ q ∨r ∨ s ) ≡∼ p ∧∼ q ∧ ∼r ∧ ∼ s P

q V V V V V V V V F

r V V V V F F F F V

s V V F F V V F F V

V F V F V F V F V

( p ∨q ∨ r ∨ s )

∼ ( p ∨q ∨ r ∨ s )

V V V V V V V V V

F F F F F F F F F

F F F F F F F

P V V V V V V V V F F F F F F F F

V V V F F F F

q V V V V F F F F V V V V F F F F

r V V F F V V F F V V F F V V F F

V F F V V F F

s V F V F V F V F V F V F V F V F

Si son equivalentes

F V F V F V F

V V V V V V F

F F F F F F V

∼p

∼q

∼r

∼s

F F F F F F F F V V V V V V V V

F F F F V V V V F F F F V V V V

F F V V F F V V F F V V F F V V

F V F V F V F V F V F V F V F V

∼ p ∧∼ q ∧∼r ∧∼ s F F F F F F F F F F F F F F F V

Tema 2 Argumentos Utilizando una tabla de verdad demuestra la validez de los siguientes argumentos. En caso de ser válidos demuestra con esquemas de inferencia. a)

P1 : p → q P2 : p ∨ r

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

P3 :∼r C :q p

q

V V V V F F F F

V V F F V V F F

R

p →q

V F V F V F V F

V V F F V V V V

p ∨r V V V V V F V F

( p → q)∧¿ V V F F V F V F

∼r F V F V F V F V

Tautología por lo tanto Validez del argumento.

P1 : p → q

Silogismo disyuntivo P1 y P3

P2 : p ∨ r

Modus ponens

P3 :∼r C :q

b)

P1 : p ∧ q ∧∼ r

P1 y C1

C1: P C2: q

( p → q)∧( p ∨r )∧(∼rCondición ) F V F F F F F F

V V V V V V V V

P2 : s → r

( p ∧q ∧ ∼r)∧(s → r )∧ (∼ s ∧ p ) → t ¿ →t

P3 : ( ∼ s ∧ p ) → t C :t P V V V V V V V V V V V V V V V V F F F F F F F F F F F F F F F F

q V V V V V V V V F F F F F F F F V V V V V V V V F F F F F F F F

R V V V V F F F F V V V V F F F F V V V V F F F F V V V V F F F F

S V V F F V V F F V V F F V V F F V V F F V V F F V V F F V V F F

t V F V F V F V F V F V F V F V F V F V F V F V F V F V F V F V F

Condició ( p ∧q ∧ ∼ r) ( p ∧q ∧ ∼r)∧(s →( rp)∧q ∧ ∼r) ∧(s → r )∧ (∼ s ∧ p ) → t F F F F V V V V F F F F F F F F F F F F F F F F F F F F F F F F

Tautología por lo tanto Validez del argumento. b)

F F F F F F V V F F F F F F F F F F F F F F F F F F F F F F F F

F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F

n V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V

P1 : p ∧ q ∧∼ r

∼ r ∧ p ∧q

P1

P2 : s → r

Simplificación

P3 : ( ∼ s ∧ p ) → t

Modus Tollens C1 y P2 C2: S

C :t

P1

C1: ∼ r

Simplificación

P1

C3: p

Conjunción

C2 y P1 C4: ∼ s ∧ p

Modus Ponens C4 y P3 C5: t

c)

P1 : ( p ∨ q ) →(r ∧ s)

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

P2 : p C : s∧ p p

Q

R

S

p ∨q ( p ∨q ) → ( r ∧ s ) [ ( p ∨ q ) → ( r ∧ s ) ]∧ sp∧ p [ ( p ∨ q ) → ( r ∧ s ) ]∧ p → s ∧ p

V V V V V V V V V F F F V V F V F F V V F F F F V F V V V V V F V F F F V F F V F F V F F F F F F V V V V V F V V F F F F V F V F F F V F F F F F F V V V V F F V F V V F F F V V V F F F F V V Tautología por lo tanto Validez del argumento.

P1 : ( p ∨ q ) →(r ∧ s)

Suma

V F F F V F F F F F F F F F F F

P2

P2 : p

Modus ponens P1 y C1

C : s∧ p

Simplificación

C2

C1: p V q C2: r ∧ s : s ∧r C3: s

V F V F V F V F F F F F F F F F

V V V V V V V V V V V V V V V V

Conjunción

P2 y C3

C4: P ∧S: S∧ P

Tema 3 Lógica de primer orden Sea N= { 0 ,1 , 2 , … } .Determina el valor de verdad de las siguientes expresiones. Explica con tus palabras el porqué de tus respuestas. 1.

∀ x ∈ N , x ≥ 0 (V)

Todos los números naturales son mayores o iguales a cero ya que los números naturales empiezan desde el número cero y no antes. 2. ∃ x ∈ N , x=x2 (V) Existe un número natural que es igual a su cuadrado. Es verdadero ya que hay números como el cero o el uno que al elevarlos al cuadrado resulta el mismo número. 3. ∀ x ∈ N , ( x