R3 Trabajo_1__L_gica_Matem_tica (1)

Vista previa del material en texto

Lógica Matemática
Trabajo 1
Ángela Maŕıa Ruiz Gómez-070200082019
Juan José Tovar Rodŕıguez-070200032019
Hary Nicol Trujillo Portillo-070200072019
UNIVERSIDAD DEL TOLIMA
FACULTAD DE CIENCIAS
MATEMÁTICAS CON ÉNFASIS EN ESTADÍSTICA
SEMESTRE 2022B
1
Arnold Oostra
Nota adhesiva
Este es un muy buen trabajo. Hay algunos detalles para revisar, especialmente en el 2 y el 3. Lo que se compensa con la presentación, que está realmente sobresaliente, muchas gracias.
Calificación: 5.0
Trabajo1. Lógica Matemática
Ángela Maŕıa Ruiz Gómez-070200082019
Juan José Tovar Rodŕıguez-070200032019
Hary Nicol Trujillo Portillo-070200072019
Docente:
Anton Arnold Oostra
Profesor Asociado,Departamento de Matemáticas con
Énfasis en Estad́ıstica
UNIVERSIDAD DEL TOLIMA
FACULTAD DE CIENCIAS
MATEMÁTICAS CON ÉNFASIS EN ESTADÍSTICA
2
Lógica Matemática
Trabajo 1
(A entregar: viernes 4 de noviembre)
Los trabajos se elaboran en grupos de tres estudiantes y se presentan escritos (a mano o en
LATEX) en hojas blancas tamaño carta que deben estar numeradas.
1.1. Demuestre por inducción en fórmulas que S[α] = 3I[α] + 1 para toda
fórmula α, siendo S la cantidad de śımbolos e I la de paréntesis izquierdos.
Demostración:
Teniendo en cuenta que S es la cantidad de Śımbolos e I la cantidad de
paréntesis izquierdos.
• Paso Inicial:
Si p es letra, entonces S[p] = 3I[p] + 1, pues I[p] = 0, por lo que S[p] =
1 = (3(0) + 1)
• Paso Inductivo:
1. Si S[α] = 3I[α] + 1 entonces S[¬(α)] = 3I[¬(α)] + 1
Veamos que
S[¬(α)] = 3 + S[α]
S[¬(α)] = 3 + (3I[α] + 1)
S[¬(α)] = 3 + (1 + I[α] + 1)
S[¬(α)] = 3I[¬(α)] + 1
Se debe a que I[¬(α)] = 1 + I[α]
3
Arnold Oostra
Nota adhesiva
3(1 + I[a]) +1
2. Si S[α] = 3I[α] + 1 ∧ S[β] = 3I[β] + 1 entonces S[(α) ∗ (β)] =
3I[(α) ∗ (β)] + 1
Veamos que
S[(α) ∗ (β)] = 5 + S[α] + S[β]
S[(α) ∗ (β)] = 5 + (3I[α] + 1) + (3I[β] + 1)
S[(α) ∗ (β)] = 5 + 3I[α] + 1 + 3I[β] + 1
S[(α) ∗ (β)] = 6 + 3I[α] + 3I[β] + 1
S[(α) ∗ (β)] = 3(2 + I[α] + I[β]) + 1
S[(α) ∗ (β)] = 3I[(α) ∗ (β)] + 1
1.2. Elabore un árbol con al menos cuatro conectivos binarios y cinco nega-
ciones. Luego escriba la fórmula correspondiente en la notación usual y en la
notación polaca.
• Notación Usual:
¬(¬(r → t) ∧ ¬s) ↔ (¬(¬p ∨ q)))
4
Arnold Oostra
Nota adhesiva
sobra esta negación...
• Notación Polaca:
¬ ↔ ∧¬ → rt¬s¬ ∨ ¬pq
1.3. Demuestre utilizando únicamente los axiomas y la regla de inferencia
modus ponens:
⊢ α → ((β → α) ∧ (α ∨ γ)).
Demostración:
Por TD hay que probar:
⊢ , α → ((β → α) ∧ (α ∨ γ)).
1. α P
2. (α → (β → α)) → ((α → (α ∨ γ) → (α → ((β → α) ∧ (α ∨ γ))) Ax.6
3. α → (β → α) Ax.1
4. (α → (α∨ γ)) → (α → (β → α)∧ (α∨ γ)) MP/2,3
5. α → (α ∨ γ) Ax.7
6. α → (β → α) ∧ (α ∨ γ) MP/4,5
7. (β → α) ∧ (α ∨ γ) MP/1,6
1.4. Demuestre:
α → β, α ∨ γ ⊢ β ∨ γ.
5
Arnold Oostra
Nota adhesiva
De nuevo, sobra esta negación ;)
Arnold Oostra
Nota adhesiva
Si dice "únicamente los axiomas y modus ponens", no se puede usar TD...
Arnold Oostra
Nota adhesiva
No es premisa válida...
Arnold Oostra
Nota adhesiva
Aquí demostraron lo que debían probar, sin TD... (solo falta un paréntesis, ojo)
Demostración:
1. α → β P
2. (α ∨ γ) P
3. β → (β ∨ γ) Ax.7
4. α → (β ∨ γ) T/1,3
5. (α → (β∨γ)) → ((γ → (β∨γ)) → ((α∨γ) → (β∨γ))) Ax.9
6. (γ → (β∨γ)) → ((α∨γ) → (β∨γ)) MP/4,5
7. γ → (β ∨ γ) Ax.8
8. (α∨ γ) → (β ∨ γ) MP/7,6
9. (β ∨ γ) MP/2,8
1.5. Demuestre:
α → β, γ ⊢ α → (β ∧ γ).
6
Demostración:
1. α → β P
2. γ P
3. γ → (α → γ) Ax.1
4. α → γ MP/2,3
5. (α → β) → ((α → γ) → (α → (β ∧ γ))) Ax.6
6. (α → γ) → (α → (β ∧ γ)) MP/1,5
7. α → (β ∧ γ) MP/4,6
7