12
Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Embed Size (px)

Citation preview

Page 1: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Práctica especificación 1Lógica proposicional

Algoritmos y Estructuras de Datos 1

28 de marzo de 2011

Page 2: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 2

Fórmulas bien formadas

Sean p y q fórmulas bien formadas.

¿Cuáles de las siguientes fórmulas son bien formadas?

•(pq)

•pq

•p

•(p q)

• p

Page 3: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 3

Tablas de verdad

Armar la tabla de verdad de las siguientes fórmulas:

a) ((pq)(pq))

b) ((p (qr))(pr))

Page 4: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 4

Tablas de verdad

a) ((pq)(pq))

p q p (pq) (pq) ((pq)(pq))p q p (pq) (pq) ((pq)(pq))

1

1

0

0

p q p (pq) (pq) ((pq)(pq))

1 1

1 0

0 1

0 0

p q p (pq) (pq) ((pq)(pq))

1 1 0

1 0 0

0 1 1

0 0 1

p q p (pq) (pq) ((pq)(pq))

1 1 0 1

1 0 0 0

0 1 1 1

0 0 1 1

p q p (pq) (pq) ((pq)(pq))

1 1 0 1 1

1 0 0 0 0

0 1 1 1 1

0 0 1 1 1

p q p (pq) (pq) ((pq)(pq))

1 1 0 1 1 1

1 0 0 0 0 1

0 1 1 1 1 1

0 0 1 1 1 1

Page 5: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 5

b) ((p (qr))(pr))

p q r r (qr) (p (qr)) (pr) ((p (qr))(pr))

1 1 1 0 0 0 1 0

1 1 0 1 1 1 0 0

1 0 1 0 0 0 1 0

1 0 0 1 0 0 0 0

0 1 1 0 0 1 0 0

0 1 0 1 1 1 0 0

0 0 1 0 0 1 0 0

0 0 0 1 0 1 0 0

Tablas de verdad

Page 6: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 6

Tautologías - Contingencias - Contradicciones

¿Son las fórmulas que vimos antes tautologías, contingencias o contradicciones?

Dar dos subfórmulas que sean equivalentes

((pq)(pq)) Tautología

((p (qr))(pr)) Contradicción

(p (qr))

(pq) y (pq)

Dar una subfórmula que sea contingencia

Page 7: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 7

Relación de fuerza

Determinar para los siguientes pares de fórmulas la relación de fuerza:

• p y (pq)

• p y (pq)

• p y (qp)

Es más fuerte:Entre:

• (pq)

• ninguno

• p

Decimos que “p es más fuerte que q” cuando (p → q) es tautología.

Page 8: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 8

Usando la lógica para expresar cosas del mundo

Sean las variables proposicionales f, e y m, con los siguientes significados:

• f “es fin de semana”

• e “Juan estudia”

• m “Juan escucha música”

Escribir usando lógica proposicional:

“Si es fin de semana, Juan estudia o escucha música, pero no ambas.”

• (f ( (e m) (e m)))

Page 9: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 9

Falacia de afirmar el consecuenteConsiderar la siguiente afirmación:

¿Si la semana que viene llego con el pelo azul, es cierto que me peleé con mi novio?

“Siempre que me peleo con mi novio me cambio el color de pelo.”

Page 10: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 10

Falacia de afirmar el consecuenteAnálisis:

• f “me peleo con mi novio”

• e “me cambio el color de pelo”

“Siempre que me peleo con mi novio me cambio el color de pelo.”

Se puede expresar como:

(f e)

Sean las variables proposicionales p y q, con el siguiente significado:

La conclusión que queríamos sacar era:

(e f)

No es lo mismo. Y no es cierto que si vale uno entonces vale el otro.

Page 11: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 11

Semántica trivaluada

Tablas de verdad para esta semántica:

p q p (pq) (pq) (pq) (pq)p q p (pq) (pq) (pq) (pq)

1 1 0

1 0 0

0 1 1

0 0 1

1 - 0

0 - 1

- 1 -

- 0 -

- - -

p q p (pq) (pq) (pq) (pq)

1 1 0 1

1 0 0 0

0 1 1 0

0 0 1 0

1 - 0 -

0 - 1 0

- 1 - -

- 0 - -

- - - -

p q p (pq) (pq) (pq) (pq)

1 1 0 1 1

1 0 0 0 1

0 1 1 0 1

0 0 1 0 0

1 - 0 - 1

0 - 1 0 -

- 1 - - -

- 0 - - -

- - - - -

p q p (pq) (pq) (pq) (pq)

1 1 0 1 1 1

1 0 0 0 1 0

0 1 1 0 1 1

0 0 1 0 0 1

1 - 0 - 1 -

0 - 1 0 - 1

- 1 - - - -

- 0 - - - -

- - - - - -

p q p (pq) (pq) (pq) (pq)

1 1 0 1 1 1 1

1 0 0 0 1 0 0

0 1 1 0 1 1 0

0 0 1 0 0 1 1

1 - 0 - 1 - -

0 - 1 0 - 1 -

- 1 - - - - -

- 0 - - - - -

- - - - - - -

Page 12: Práctica especificación 1 Lógica proposicional Algoritmos y Estructuras de Datos 1 28 de marzo de 2011

Lógica proposicional 12

Semántica trivaluadaConsiderar si el par de fórmulas (pq) y (qp) son equivalentes.

• (pq)

• ((pq) (qp))

• ((qp) (pq))

¿Y éstas? ¿Son equivalentes entre sí?