problemas

Lógica Matemática para Informáticos
Ejercicios propuestos

Teresa Hortalá González
Narciso Martí Oliet
Miguel Palomino Tarjuelo
Mario Rodríguez Artalejo
Rafael del Vado Vírseda
Departamento de Sistemas Informáticos y Computación
Universidad Complutense de Madrid

Parte I

LÓGICA PROPOSICIONAL

CAPÍTULO

A

,σ
111
000
00
11
000
111
0
1
0
1
00
11
0
1
00
11
10
000
111
00
11
1
0
1
0
000
111
0
1
0
1
11
00
11
00
11
00
11
00
1
0
1
0
00
11
0
1
0
1
0
001
11
11
00
11
00
00
11
0
1
1
0
0
1
00
11
1
0
00
11
0
1
00
11
00
11
0
1
00
11
11
00
00
11
00
11
0
1
0
1
0
11
1
0
11
00
0
1
00
11
11
00
00
11
0
1
00
11
0
1
00
11
11
00
11
00
1
0
00
11
11
00
00
11
0
1
01
00
11
0
00
11
0 00
1
111
00
11
1
0

1

SINTAXIS Y SEMÁNTICA

| ϕ

1.1.

PREGUNTAS DE TEST
1.1.

La cadena de símbolos (( p ∨ q) → (¬q → p)) formada usando
(a) es una fórmula proposicional

1.2.

1.5.

La cadena de símbolos ((( p ↔ ¬q) ∧ p) ∧ ¬q) formada con

(b) no se puede saber

(c) es una fórmula proposicional

(b) v( p) debe valer 0

(c) v( p) puedevaler 0 o 1

(b) v( p) = 1 y v(q) = 0

(c) v(q) = 1

Sabiendo que [[q → ¬ p]]v = 0, se puede asegurar:
(a) v( p) = 1 y v(q) = 0

1.8.

= { p, q}

Sabiendo que [[¬( p → q)]]v = 1, se puede asegurar:
(a) v( p) = 0

1.7.

(c) no es una fórmula proposicional

Sabiendo que [[( p → q) → p]]v = 0, ¿qué se puede asegurar acerca de v( p)?
(a) v( p) debe valer 1

1.6.

(c) no sepuede saber

= { p, q, r }

(b) no se puede saber

(a) no es una fórmula proposicional

(c) no se puede saber

= { p, q}

(b) no es una fórmula proposicional

La cadena de símbolos ( p → (q → ¬r )) formada usando
(a) es una fórmula proposicional

1.4.

(b) no es una fórmula proposicional

La cadena de símbolos ( p ∨ q) → ((¬q → p) formada usando
(a) es una fórmula proposicional1.3.

= { p, q}

(b) v( p) = 1 y v(q) = 1

(c) v( p) = 0

Sabiendo que [[( p ∧ q) → (¬ p ∨ ¬q)]]v = 0,
(a) debe ser v( p) = 1

(b) debe ser v( p) = 0

(c) puede ser v( p) = 1 o v( p) = 0

4 Lógica Matemática para Informáticos
1.9.

Sabiendo que [[¬ p → (q → p)]]v = 0, se puede asegurar:
(a) v( p) = 1

1.10.

(b) v(r ) = 1

(c) v(r ) = 0

(b) v(r ) = 1

(c) v(r ) =0

(b) v(r ) = 1

(c) No depende de v(r )

Dadas la fórmula proposicional ϕ = (q → r ) → ¬(q ∨ r ) y la valoración v(q) = 0, ¿cuánto vale [[ϕ]]v ?
(a) Depende de v(r )

1.2.

(c) v(r ) = 0

Dadas la fórmula proposicional ϕ = ( p → r ) → (q → r ) y la valoración v( p) = v(q) = 0, para que
[[ϕ]]v = 1, ¿cuánto debe valer v(r )?
(a) v(r ) = 0

1.15.

(b) v(r ) = 1

Dadas lafórmula proposicional ϕ = ¬( p → r ) → (q ∨ r ) y la valoración v( p) = v(q) = 0, para que
[[ϕ]]v = 1, ¿cuánto debe valer v(r )?
(a) No depende de v(r )

1.14.

(c) v(r ) = 0

Dadas la fórmula proposicional ϕ = ¬((¬ p → r ) → ( p ∧ r )) y la valoración v( p) = 0, para que
[[ϕ]]v = 1, ¿cuánto debe valer v(r )?
(a) No depende de v(r )

1.13.

(b) v(r ) = 1

Dadas la fórmula proposicional ϕ= ( p → q) ∧ ((¬ p → r ) → q) y una valoración v tal que v( p) =
v(q) = 0, para que [[ϕ]]v = 1, ¿cuánto debe valer v(r )?
(a) No depende de v(r )

1.12.

(c) v(q) = 0

Dadas la fórmula proposicional ϕ = ( p → q) → ((q ∨ ¬r ) → ¬ p) y una valoración v tal que
v( p) = v(q) = 0, para que [[ϕ]]v valga 1, ¿cuánto debe valer v(r )?
(a) No depende de v(r )

1.11.

(b) v( p) = 0 y v(q) = 1(b) [[ϕ]]v = 1

(c) [[ϕ]]v = 0

EJERCICIOS

1.16.

Considera las siguientes fórmulas:
(a) ¬ p ∨ q ∧ ¬r
(b) ¬q ∧ p → r
(c) ¬ p ∨ q ∧ ¬r → ¬q ∧ p → r
(d) ¬ p ∨ q ∧ ¬r → ¬q ∧ p → r ↔ ¬s
Para cada fórmula, escríbela en forma no abreviada, indicando cómo construirla mediante las reglas de
formación, y dibuja su árbol estructural.

1.17.

Escribe una definición recursiva de la...