Carrera: LICENCIATURA EN MATEMÁTICAS

Materia : LÓGICA MATEMÁTICA

U1-EA: Evidencia de Aprendizaje.

Grupo : MT-MLMA-2302-B2-001

Alumno: Rolando Ortiz Herbas

Matrícula: ES18210414044

Maestro: Ing. Rafael Pacheco Espinosa

Página 1 de 8
1) Describe los árboles de construcción de las fórmulas

a) ((𝑷𝟎 → 𝑷𝟏 ) ∧ (𝑷𝟐 → 𝑷𝟑 ) → (¬𝑷𝟏 ∨ 𝑷𝟑 ))

((𝑷𝟎 → 𝑷𝟏 ) ∧ (𝑷𝟐 → 𝑷𝟑 ) → (¬𝑷𝟏 ∨ 𝑷𝟑 ))

(𝑷𝟎 → 𝑷𝟏 ) ∧ (𝑷𝟐 → 𝑷𝟑 ) (¬𝑷𝟏 ∨ 𝑷𝟑 )

(𝑷𝟎 → 𝑷𝟏 ) (𝑷𝟐 → 𝑷𝟑 ) ¬𝑷𝟏 𝑷𝟑

𝑷𝟎 𝑷𝟏 𝑷𝟐 𝑷𝟑 𝑷𝟏 𝑷𝟑

b) ((𝑷𝟎 → 𝑷𝟏 ) → ((𝑷𝟎 → ¬𝑷𝟏 ) → ¬𝑷𝟏 ))

((𝑷𝟎 → 𝑷𝟏 ) → ((𝑷𝟎 → ¬𝑷𝟏 ) → ¬𝑷𝟏 ))

𝑷𝟎 → 𝑷 𝟏 (𝑷𝟎 → ¬𝑷𝟏 ) → ¬𝑷𝟏

𝑷𝟎 → ¬𝑷𝟏 ¬𝑷𝟏

𝑷𝟎 ¬𝑷𝟏 𝑷𝟏
𝑷𝟎 𝑷𝟏

𝑷𝟏

Página 2 de 8
 ̅ para cada una de las siguientes fórmulas usando las tablas de verdad
2) Calcula 𝒗

a) ((𝑷 → 𝑸) ∨ (𝑷 → (𝑸 ∧ 𝑷)))

𝑷 𝑸 𝑷→𝑸 𝑸∧𝑷 𝑷 → (𝑸 ∧ 𝑷) (𝑷 → 𝑸) ∨ (𝑷 → (𝑸 ∧ 𝑷))

V V V V V V

V F F F F F

F V V F V V

F F V F V V

𝒃) ¬ (𝑷 → ¬((𝑸 ∧ 𝑷)) → (𝑷 ∨ 𝑹))

𝑷 𝑸 𝑹 𝑸∧𝑷 ¬((𝑸 ∧ 𝑷)) 𝑷∨𝑹 𝑷 → ¬((𝑸 ∧ 𝑷)) (𝑷 → ¬((𝑸 ∧ 𝑷)) → (𝑷 ∨ 𝑹)) ¬ (𝑷 → ¬((𝑸 ∧ 𝑷)) → (𝑷 ∨ 𝑹))

V V V V F F V V F

V V F V F F V V F

V F V F V V V V F

V F F F V V V V F

F V V F V V V V F

F V F F V V F F V

F F V F V V V V F

F F F F V V F F V

Página 3 de 8
c) ((𝑷 ∧ (𝑸 → 𝑷)) → ¬𝑷)

𝑷 𝑸 𝑸→𝑷 𝑷 ∧ (𝑸 → 𝑷) ¬𝑷 ((𝑷 ∧ (𝑸 → 𝑷)) → ¬𝑷)

V V V V F F

V F V V F F

F V F F V V

F F V F V V

d) (((𝑷 ∧ ¬𝑸) → 𝑸) → (𝑷 → 𝑸))

𝑷 𝑸 ¬𝑸 𝑷 ∧ ¬𝑸 (𝑷 ∧ ¬𝑸) → 𝑸 𝑷→𝑸 (((𝑷 ∧ ¬𝑸) → 𝑸) → (𝑷 → 𝑸))

V V F F V V V

V F V V F F V

F V F F V V V

F F V F V V V

3) Demuestra que (𝑨𝟐 ↔∨ 𝑨𝟏 ) no es una fórmula.

Por las reglas de formación de fórmulas, las que nos permiten definir fórmulas que son expresiones
(gramaticalmente correctas), por definición, tenemos:

a. Todo símbolo de enunciado es una fórmula.

b. Si 𝛼 𝑦 𝛽 son fórmulas, entonces también lo son

(¬𝛼), (𝛼 ˄ 𝛽),(𝛼 ˅ 𝛽), (𝛼 → 𝛽),(𝛼 ↔ 𝛽)

c. Ninguna expresión es fórmula a menos que a) y b) obliguen a ello.

𝑷𝒐𝒓 𝒍𝒐 𝒕𝒂𝒏𝒕𝒐 𝒔𝒊 𝒂𝒑𝒂𝒓𝒆𝒄𝒆 𝒖𝒏 𝒔𝒊𝒎𝒃𝒐𝒍𝒐 ∨ 𝒒𝒖𝒆 𝒆𝒔 𝒖𝒏 𝒐𝒑𝒆𝒓𝒂𝒅𝒐𝒓 𝒃𝒊𝒏𝒂𝒓𝒊𝒐, 𝒅𝒆𝒃𝒆 𝒂𝒑𝒂𝒓𝒆𝒄𝒆𝒓 𝒂

𝒊𝒛𝒒𝒖𝒊𝒆𝒓𝒅𝒂 𝒚 𝒅𝒆𝒓𝒆𝒄𝒉𝒂 𝒖𝒏𝒂 𝒇𝒐𝒓𝒎𝒖𝒍𝒂 𝒚 𝒏𝒐 𝒆𝒔 𝒆𝒍 𝒄𝒂𝒔𝒐 𝒆𝒏 𝒍𝒂 𝒇𝒐𝒓𝒎𝒖𝒍𝒂 (𝑨𝟐 ↔∨ 𝑨𝟏 ) .

Página 4 de 8
4) ¿Es (((𝑷 → 𝑸) → 𝑷) → 𝑷) una tautología?

Para decidir si es tautología, encontramos los valores de verdad con las tablas

𝑷 𝑸 𝑷→𝑸 (𝑷 → 𝑸) → 𝑷 ((𝑷 → 𝑸) → 𝑷) → 𝑷

V V V V V

V F F V V

F V V F V

F F V F V

Concluimos que es una tautología.

5) Demuestra que si 𝜶 ⊨ 𝜷 , entonces existe alguna cuyos símbolos de enunciado aparecen

todos tanto en 𝜶 como 𝜷, y tal que 𝜶 ⊨ 𝜸 ⊨ 𝜷.

Sean 𝛼,𝛽 y 𝛾 fórmulas del lenguaje.

Si 𝛾 ∈ sub (𝛼) 𝛾 ∈ sub (𝛽),𝛾 es lógicamente equivalente a 𝛼 𝑦 𝛽, ya que 𝛾 es una fórmula
obtenida de 𝛼 𝑦 𝛽, sustituyendo los elementos de 𝛼 𝑦 𝛽.
Entonces, 𝛼 es lógicamente equivalente a 𝛾, y a su vez equivalente a 𝛽.

6) Prueba que | y ↓ son las únicas conectivas completas por si solas y que {¬, #} no es
completo.
Para prueba que | y ↓ son las únicas conectivas completas por sí solas:
Teorema: La barra de Scheffer | y el funtor de Peirce ↓, son los únicos sistemas de conectivos
binarios que conforman, por sí mismos, un sistema completo de conectivos para los conjuntos de
conectivos unarios y binarios.
Demostración.: Se tiene que para cualesquiera proposiciones p y q:

¬p≡ ¬𝑝˄𝑞) ≡ 𝑝|𝑝

Por tanto

p ˄ 𝑞 ≡ ¬¬(𝑝˄𝑞) ≡ ¬(𝑝|𝑞) ≡ (𝑝|𝑞)|(𝑝|𝑞)

Así la | es un sistema completo de conectivos.

Tambien

Página 5 de 8
¬p≡ ¬(𝑝˅𝑞) ≡ 𝑝 ↓ 𝑝

Por tanto

p ˄ 𝑞 ≡ ¬(¬𝑝˅¬𝑞) ≡ ¬[(p↓ 𝑝)˅(𝑞 ↓ 𝑞)] ≡ (𝑝 ↓ 𝑝) ↓ (𝑞 ↓ 𝑞)

Concluimos que ↓ es un sistema completo de conectivos.

Y para prueba que {¬, #} no es completo:

7) Demuestra que si 𝛴 es un conjunto decidible de fórmulas entonces el conjunto de las

consecuencias tautológicas de 𝛴 es efectivamente numerable.

Tenemos que, si Σ es un conjunto decidible de fórmulas, entonces el conjunto de las consecuencias

tautológicas de Σ es efectivamente numerable.

Para demostrar, basta que Σ esté efectivamente numerado: 𝛼1 , 𝛼2 , 𝛼3 , …

Dada cualquier fórmula 𝜏 es posible verificar si es que:

∅⊨𝜏
{𝛼1 } ⊨ 𝜏
{𝛼1 , 𝛼2 } ⊨ 𝜏
{𝛼1 , 𝛼2 , 𝛼3} ⊨ 𝜏

De otra forma, continúa probando. Esto produce una respuesta afirmativa siempre y cuando Σ ⊨ 𝜏,
por el corolario al teorema de compacidad.

8) Demuestra que la unión y la intersección de dos conjuntos efectivamente enumerables

también es efectivamente enumerable.

Un conjunto 𝛴 de expresiones es decidible si y sólo si existe un procedimiento eficaz que, dada una
expresión 𝛼, decidirá si 𝛼 ∈ 𝛴 o 𝛼 ∉ 𝛴.

Por definición se sabe que todo conjunto finito es decidible.

Por lo tanto, si los conjuntos A y B son efectivamente numerables, así mismo, lo son A U B y A ∩
B dado que a la clase de los conjuntos decidibles también es cerrada bajo la unión y la intersección.

9) Para cada una de las siguientes condiciones, dé un ejemplo de un conjunto de fórmulas

no satisfactible 𝚪 que cumplan la condición.

Página 6 de 8
a) Cada elemento de 𝚪 es, en sí mismo, satisfactible. Para cada una de las siguientes
condiciones, dé un ejemplo de un conjunto de fórmulas no satisfactible 𝚪 que cumplan la
condición.

Ejemplo 1:

Sea el conjunto Γ = {P, ¬P}

𝐸𝑛 𝑒𝑠𝑡𝑒 𝑒𝑗𝑒𝑚𝑝𝑙𝑜 , Γ contiene la formula P y su negación ¬P. Por lo que no puede haber una
interpretación que satisfaga ambas formulas al mismo tiempo, ya que són mutuamente excluyentes.

Podemos ver esto en la siguiente tabla de verdad ,

𝑷 ¬𝐏

V F

F V

c) Para cualesquiera dos elementos 𝜸𝟏 𝒚 𝜸𝟐 de 𝚪 el conjunto {𝜸𝟏 , 𝜸𝟐 } es satisfactible.

Sea el conjunto Γ = {P, Q, (¬𝑃 ∨ 𝑄)} veamos la tabla:

𝑃 𝑄 P∨Q ¬P ∨ Q

V V V V

V F V F

F V V V

F F F V

Este conjunto Γ = {P, Q, (¬𝑃 ∨ 𝑄)} es satisfacible ya que hay asignación de verdad que logre
satisfacer a sus 3 elementos.

10) Demuestra el teorema 1.5.3.4. que se presentó en el contenido, es decir:

Un conjunto de expresiones es decidible si tanto él como su complemento, con respecto al
conjunto de todas las expresiones, son efectivamente enumerables.

Página 7 de 8
Se dice que es decidible: Un conjunto 𝛴 de expresiones es decidible Ssi existe un procedimiento
eficaz que, dada una expresión 𝛼, decidirá si 𝛼 ∈ 𝛴 o 𝛼 ∉ 𝛴.
Por definición se sabe que todo conjunto finito es decidible.

Por la definición de efectivamente numerable: tenemos que se llamará a un conjunto A de

expresiones efectivamente numerable Ssi existe algún procedimiento efectivo que produce una
lista, en los elementos de A.

Conclusiones.- La lógica proposicional sirve para representar razonamientos con los cuales
podemos obtener conclusiones en base a un conjunto de premisas. Pero hay muchas ideas que no
se pueden representar, por lo que se desarrollo la lógica de predicados. En primera instancia la
lógica de predicados de primer orden y posteriormente la lógica de predicados de orden superior.

Bibliografía o Referencias (en formato APA):

[1] Contenido Lógica Matemática, UNADM, 2023, Cdmx México

[2] Lógica Computacional, E. Paniagua-J. Sánchez-F. Rubio, Paraninfo , 2015, España

[3] Lógica Matemática I proposicional, Max Fernández-Luis Villegas, UAM, 2014, Cdmx México

[4] Lógica Matemática II intuicionista y modal, Max Fernández-Luis Villegas, UAM, 2014, Cdmx México

Página 8 de 8