Final 2021-07-28

Vista previa del material en texto

Introducción a la Lógica y la Computación. Examen Final 28/07/2021.
1. Determine si la afirmación es verdadera o falsa. Debe justificar su respuesta.
(a) Si L es un reticulado, entonces L es isomorfo a D(Irr(L)).
(b) Si L es un reticulado distributivo finito tal que At(L) = Irr(L), entonces L es un
álgebra de Boole.
(c) Si B,B′ son álgebras de Boole finitas, y tienen la misma cantidad de elementos,
entonces B y B′ son isomorfas.
2. (a) Defina isomorfismo de posets.
(b) Demuestre que si (L,∨,∧), (L′,∨′,∧′) son reticulados, y f : L → L′ es isomorfismo
de posets, entonces f(x ∨ y) = f(x) ∨′ f(y).
3. Hallar derivaciones que justifiquen ` ¬(ϕ ∧ ψ) → (ϕ→ ¬ψ) y ` ϕ ∨ ¬ϕ
4. Sea Γ un conjunto consistente formado por proposiciones que utilizan solamente los
śımbolos del conjunto {pi : i par} ∪ {⊥,¬,∨,∧,→, (, )} (es decir, todos los conectivos
con los pi par). ¿Existe un conjunto consistente maximal que contenga a Γ, y también
contenga a {p1 ∧ ¬p3}? Justifique su respuesta.
5. Sea el NFA M = ({q0, q1, q2, }, {0, 1}, δ, q0, {q2}) donde δ viene dada por la siguiente tabla
de transición:
0 1 �
q0 {q0} {q1, q2} ∅
q1 {q1} {q2} ∅
q2 {q0, q1} ∅ ∅
(a) Hacer el diagrama de transición de M .
(b) Utilizar Kleene para encontrar una expresión
regular que denote el mismo lenguaje.
6. Dar una expresión regular con alfabeto {a, b} cuyo lenguaje aceptado sea el conjunto de
todas las palabras con una cantidad par de letras a, que no poseen dos letras a consecutivas.
Por ejemplo, bbaba está en el conjunto, pero bbaab no está.
L. Sólo para alumnos libres:
Contar cuántos reticulados distributivos hay (no isomorfos), que tienen exactamente tres
elementos irreducibles, y dos de ellos son átomos. Justificar la respuesta.