Download Práctica 1

Lógica y computabilidad
Primer cuatrimestre — 2017
Práctica 1: Lenguaje del Cálculo Proposicional
1. Sea A = { a, e, i, o, u}, S = { p, q}, Σ = A ∪ S. Definimos un lenguaje L ⊆ Σ∗ por las
siguientes reglas:
• Si β ∈ A entonces β es una palabra.
• Si α1 , . . . , αn (n ≥ 0) son palabras, las expresión pα1 . . . αn q también lo es.
• Una expresión es una palabra si y sólo si se obtiene con estas reglas.
Se define el peso de una expresión como el número de p que aparecen en la expresión menos
el número de q que aparecen en la expresión.
(a)
(b)
(c)
(d)
Escribir cinco expresiones de Σ∗ que no sean palabras y cinco que si lo sean.
Probar que las palabras de L son expresiones de peso 0.
¿Es toda expresión de peso 0 una palabra?
Decidir si hay unicidad de escritura en las palabras.
2. Sea A = { a, e, i, o, u}, S = {l }, Σ = A ∪ S. Definimos un lenguaje L ⊆ Σ∗ por las siguientes
reglas:
• Si α ∈ A, entonces α es una palabra.
• Si χ1 , . . . , χn (n ≥ 0) son palabras, entonces lχ1 . . . χn l es una palabra.
• Una expresión es una palabra si y sólo si se obtiene con estas reglas.
(a) Probar que si α es una palabra, entonces el número de l que figuran en α (contados tantas
veces como aparecen) es un número par.
(b) ¿Toda expresión con una cantidad par de l es una palabra?
(c) Decidir si hay unicidad de escritura en las palabras.
Cálculo proposicional
El cálculo proposicional es el lenguaje que se obtiene de la siguiente manera: tomamos las variables Var = { p1 , p2 , p3 , . . . , pn , . . .}, los conectivos {∨, ∧, →}, la negación {¬} y los paréntesis
{(, )}. Formamos el alfabeto del lenguaje proposicional
Σ = Var ∪{∨, ∧, →} ∪ {¬} ∪ {(, )}
El lenguaje de fórmulas proposicionales (simplemente fórmulas), Form ⊆ Σ∗ , se construye bajo las
siguientes reglas de formación:
• Los elementos de Var, son fórmulas.
• Si P es una fórmula entonces (¬ P) es una fórmula.
• Si P y Q son fórmulas y c es un conectivo entonces ( PcQ) es una fórmula
Notación. Si X es un conjunto, #X denota su cardinal; Form denota el conjunto de todas las
fórmulas del cálculo proposicional y Var el conjunto de todas las variables proposicionales. Si
α ∈ Form,
•
•
•
•
l (α) denota la longitud de α,
c (α) denota la complejidad de α,
cb (α) la complejidad binaria de α,
Var (α) es el subconjunto de Var cuyos elementos son las variables proposicionales que
figuran en α,
1/3
Lógica y computabilidad — Primer cuatrimestre — 2017
Práctica 1
• # VarR (α) es el número de variables proposicionales que figuran en α contadas tantas
veces como aparecen, y
• s (α) es el conjunto de subfórmulas de α.
3. Decidir cuáles de las siguientes expresiones son fórmulas del cálculo proposicional.
4) ( p1 ∨ (¬ p2 ))
1) ( p1 ∨ p2 ) → p3
5) (( p1 ∨ ( p2 → p3 )) → ( p5 → p2 ))
2) (( p1 ∧ ( p2 → p3 )) → p4 )
3) (((¬(¬ p1 )) → p1 ) → p2 )
6) (( p1 ∧ p2 ∧ p3 ) → p3 )
4. Probar que si α es una fórmula del cálculo proposicional, entonces α admite infinitas cadenas de formación.
5. Para cada una de las siguientes fórmulas encontrar todas las cadenas de formación minimales y enumerar su conjunto de subfórmulas.
(a) (( p1 ∨ ( p2 → p3 )) → p4 )
(b) (( p1 ∨ ( p5 → p2 )) → ((¬ p1 ) → (¬ p2 )))
(c) (((¬ p1 ) ∨ p5 ) ∨ ( p1 ∧ (¬ p2 )))
6. Sean n ∈ N y n 6= 0. Mostrar que existe α ∈ Form tal que #s (α) = n.
7. Sea α ∈ Form. Probar que si β es una subfórmula de α, entonces β aparece en toda cadena
de formación de α.
8. Sea α ∈ Form tal que c (α) > 0. Probar que existe una subfórmula de α que tiene grado de
complejidad 1.
9. Sean k, n ∈ N tales que n > 2 y 1 < k < n. Si α ∈ Form tal que c (α) = n, ¿existe una
subfórmula de α con grado de complejidad k?
10. Sea α ∈ Form. Probar las siguientes relaciones
(a) #VarR (α) = cb (α) + 1
(b) # Var (α) ≤ cb (α) + 1
(c) #s (α) ≤ c (α) + # Var (α)
Random Fact. Hippopotomonstrosesquipedaliophobia es, en inglés, la fobia a las palabras largas.
11. Sea α ∈ Form tal que Var (α) = { p1 , . . . , pn } y sean β 1 , . . . , β n fórmulas arbitrarias. Definir
inductivamente la noción de sustituir en las variables proposicionales p1 , . . . , pn por β 1 , . . . , β n .
Llamamos α ( β 1 , . . . , β n ) a tal sustitución.
12. Sean α, γ ∈ Form tal que Var (α) = { p1 , . . . , pn }. Diremos que α y γ son sintácticamente
equivalentes y lo notaremos α ∼ γ si existen q1 , . . . , qn ∈ Var tales que qi 6= q j si i 6= j, y
α (q1 , . . . , qn ) = γ.
(a) Probar que es una relación de equivalencia en Form.
(b) Probar que si α ∼ γ, entonces α y γ tienen la misma complejidad y la misma complejidad
binaria.
13. Sea α ∈ Form. Notaremos con α¬ a la expresión que se obtiene al eliminar todas las apariciones del símbolo ¬ en α. (Por ejemplo, si α = (¬ ( p2 ∨ (¬ p3 ))), entonces α¬ = ( p2 ∨ p3 ) .)
(a) Definir α¬ inductivamente para toda α ∈ Form.
(b) Probar que si α ∈ Form, entonces α¬ ∈ Form.
(c) Analizar cuáles de las siguientes igualdades se cumplen para toda α ∈ Form:
1) l (α) = l (α¬ )
4) # Var (α) = # Var (α¬ )
2) c (α) = c (α¬ )
5) # VarR (α) = # VarR (α¬ )
3) cb (α) = cb (α¬ )
6) #s (α) = #s (α¬ )
2/3
Lógica y computabilidad — Primer cuatrimestre — 2017
Práctica 1
Lenguajes de primer orden
Un lenguaje de primer orden L es un lenguaje (con reglas de formación vistas en clase) en
el cual el alfabeto contiene a las variables Var, a los conectivos {∨, ∧, →}, la negación {¬},
los paréntesis {(, )} y los cuantificadores {∀, ∃}, junto con tres conjuntos distinguidos: los de
símbolos de constantes C , los símbolos de función F y los símbolos de predicado P (siendo
este último no vacío).
14. Sean L un lenguaje de primer orden con un símbolo de predicado binario P, dos símbolos
de función f 1 , f 2 , donde f 1 es unario y f 2 es binario, y un símbolo de constante c. Decidir
cuáles de las siguientes expresiones del lenguaje L son términos y cuáles son fórmulas. Las
letras x, y denotan variables.
d) ∀c∃ xP ( x, c)
a) ∃ f 2 ( x ) P ( f 2 ( x )).
e) ∃ x ∃y∃ xP ( f 2 ( x, y) , f 1 (y)).
b) f 2 ( f 1 ( x ) , f 1 (y)).
c) ∀ x ∃cP ( x, c).
f) ∃ xP ( x, y) ∀y.
15. Sea L un lenguaje con un símbolo de predicado binario P. En cada una de las siguientes
fórmulas, encontrar las apariciones libres y ligadas de las variables de dichas fórmulas. Decidir
en cada caso si son o no enunciados.
a) ∀ x ∃yP ( x, x ).
c) ∃ x (∃yP ( x, x ) ∧ P ( x, y)).
b) (∃ xP (y, y) → ∃yP (y, z)).
d) ∀z (∀ xP ( x, y) ∨ P ( x, z)).
16. En cada uno de los siguientes ejemplos, intuitivamente describir la propiedad que determinan los siguientes enunciados interpretadoles como sugiere cada item.
1. ∀ x ∀y ( P ( x, y) → ∃z (( Q (z) ∧ P ( x, z)) ∧ P (z, y))),
donde P y Q son símbolos de predicados binario y unario respectivamente, el universo
de la interpretación son los números reales, P es la relación de menor estricto, Q ( x )
significa “x es un número racional”.
2. ∀ x ( Q ( x ) → ∃y ( R (y) ∧ P (y, x ))),
donde P es un símbolo de predicado binario, Q y R son símbolos de predicados
unarios, y la interpretación es el conjunto de los días y las personas, P ( x, y) significa “x
nace en el día y”, Q ( x ) significa “x es un día”, y R ( x ) significa “x es un esclavo”.
3. ∀ x ∀y ( Q ( x ) ∧ Q (y)) → P ( f ( x, y)),
donde Q y P son símbolos de predicados unarios, f es un símbolo de función binario,
el universo de la interpretación son los números enteros, Q ( x ) significa “x es par”, P ( x )
significa “x es impar”, y f ( x, y) = x + y.
4. En los enunciados siguentes, la interpretación es conjunto de la gente, P es un símbolo
de predicado binario, tal que P ( x, y) significa x quiere a y.
a) ∃ x ∀yP ( x, y) b) ∀y∃ xP ( x, y)
c) ∃ x ∃y (∀zP (y, z) → P ( x, y)) d) ∃ x ∀y¬ P ( x, y)
3/3