Kard

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

1111 00 0000 , σ 11 00 111 000 1 0 11 00 11 1 00 0 1111 00 0000 11 111 000 11 00 1111 000011 1111 0000 111 000 111 000 1111 0000 1111 1 0000 0 11 00 11 00 10 01 1110 111 0000 000 111 000 11 00 001 11 00 11 00 1 00 01 11 0 11 1 0 11 011 1 00 1 00 0 1111 0000 11 00 1 11 0 00 1 0 11 00 11 11 00 1111 111 0000 000 11 00 1 0 1 0 11 00 1 0 1 0

A

CAPÍTULO
SINTAXIS Y SEMÁNTICA

| ϕ

1

1.1.

PREGUNTAS DE TEST 1.1.
La cadena de símbolos (( p ∨ q) → (¬q → p)) formada usando (a)es una fórmula proposicional = { p, q} (c) no se puede saber

(b) no es una fórmula proposicional = { p, q}

1.2.

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

(b) no es una fórmula proposicional = { p, q, r }

(c) no se puede saber

1.3.

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

(b) no sepuede saber

(c) no es una fórmula proposicional = { p, q} (c) es una fórmula proposicional

1.4.

La cadena de símbolos ((( p ↔ ¬q) ∧ p) ∧ ¬q) formada con (a) no es una fórmula proposicional

(b) no se puede saber

1.5.

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

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

1.7.

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

1.8.

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 paraInformáticos 1.9.
Sabiendo que [[¬ p → (q → p)]]v = 0, se puede asegurar: (a) v( p) = 1 (b) v( p) = 0 y v(q) = 1 (c) v(q) = 0

1.10.

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 ) (b) v(r ) = 1 (c) v(r ) = 0

1.11.

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 ) (b) v(r ) = 1 (c) v(r ) = 0

1.12.

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 ) (b) v(r ) = 1 (c) v(r ) = 0

1.13.

Dadas la fórmulaproposicional ϕ = ¬( 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 ) (b) v(r ) = 1 (c) v(r ) = 0

1.14.

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 (b) v(r ) = 1 (c) No depende de v(r )

1.15.

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

1.2.

EJERCICIOS
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, ydibuja su árbol estructural.

1.16.

1.17.

Escribe una definición recursiva de la aplicación sub que hace corresponder a cada fórmula proposicional ϕ ∈ L el conjunto finito sub(ϕ) formado por todas las subfórmulas de ϕ. Calcula el conjunto de todas las subfórmulas de las siguientes fórmulas: (a) (¬ p ∨ (q ∧ ¬r ))

1.18.

Sintaxis y semántica

5

(b) ((¬q ∧ p) → r ) (c) ((¬ p ∨ (q ∧...