Seminario sobre Lógica de Primer orden

Prof. MSc. Ricardo José Da Silva Araujo

UNIVERSIDAD CENTRAL DE VENEZUELA
FACULTAD DE HUMANIDADES Y EDUCACIÓN
ESCUELA DE FILOSOFÍA
DEPARTAMENTO DE LÓGICA Y FILOSOFÍA DE LA CIENCIA
 Agradecimiento

Ante todo quiero agradecer a la

Universidad Mayor de San Andrés de La Paz,
Bolivia; así como el Logic & Analytics Group
La Paz-Bolivia por la invitación realizada
para dictar el siguiente seminario.
 Primera sesión
•Breve comentario sobre el surgimiento de
la Lógica de primer orden (L1)
•Acercamiento informal (intuitivo) a la
sintaxis de L1
• Caracterización formal de la sintaxis de
L1
• Un ejemplo de lenguaje de primer orden:
El lenguaje de la aritmética en primer
orden.
 Breve comentario sobre el
surgimiento de la Lógica de primer
orden (L1)
 Para este comentario estamos
siguiendo a:
• Ewald, William, "The Emergence of First-Order Logic", The
Stanford Encyclopedia of Philosophy (Spring 2019 Edition).

• Moore, G.H., “A House divide against itself: The emergence of

first-Order logic as the basis for mathematics ” en Esther R.
Phillips (editor), Studies in the History of Mathematics
(Washington, D.C., Mathematical Association of America, 1987),
98-136).

• Moore, G.H., “Hilbert and the emergence of modern mathematical

logic” en Theoria: An International Journal for Theory, History
and Foundations of Science, Vol. 12, No. 1(28) (Enero 1997), pp.
65-90.
 Para cualquier persona educada en lógica
moderna, la lógica de primer orden puede parecer
un objeto de estudio completamente natural.

Es semánticamente completa; es adecuada para

la axiomatización de todas las matemáticas
ordinarias; y el teorema de Lindström muestra que
es la lógica con mayor poder expresivo que satisface
la compacidad y las propiedades de Löwenheim-
Skolem. Por tanto, no parece sorprendente que la
lógica de primer orden haya sido considerada
durante mucho tiempo como la lógica "correcta"
para las investigaciones sobre los fundamentos de
las matemáticas.
 Pero no siempre fue así, el lugar central
que ocupa la Lógica de primer orden en la
investigación de los fundamentos de la
matemática se debe a varias razones, de
diversa índole, y que en ocasiones
interactuaban entre sí.
 Estas razones son:

Programas de
investigación de los Distintas
fundamentos de la revisiones
matemática conceptuales

Distintas
reflexiones
filosóficas

Resultados técnicos
Diferentes
concepciones de
la lógica
 La lógica como disciplina es sistematizada
por primera vez en la obra de Aristóteles, pero
lo que actualmente conocemos como lógica
formal tiene sus raíces en las obras de G. Boole
de 1947 titulada Mathematical Analysis of
Logic, en donde presentó a la misma desde una
perspectiva algebraica. Para Boole la lógica era
una rama de la matemática y, al igual que el
álgebra, se presentaba como un cálculo no
interpretado de símbolos y operaciones que
potencialmente podía ser dotado de
significado; de hecho, el mismo Boole, ofrece
dos interpretaciones: una en términos de
clases y otra en términos de proposiciones.
George Boole (1815-1864)
 Sin embargo, la lógica que presenta el
matemático inglés no es, para ese entonces,
lo que hoy en día llamamos Lógica de
primer orden y mucho menos es una lógica
adecuada y potente para tratar a la
matemática. Lo máximo que se puede hacer
con el sistema de Boole (desde un punto de
vista anacrónico) es expresar parte de la
lógica de predicados monádicos.
 No fue hasta finales del siglo XIX cuando
de la mano de Frege y Peirce surge lo que
parece una lógica más adecuada para tal
motivo. Las dos revoluciones conceptuales
que determinaron el surgimiento de una
lógica más apropiada para el tratamiento de
la matemática vendrían a ser las siguientes:
 (a) Un tratamiento lógico pertinente para las
expresiones relacionales y funcionales. De esta
manera se supera la Silogística aristotélica y el
Cálculo de Boole, que no podían dar cuenta de
argumentos que estuviesen compuestos de
proposiciones relacionales. Esto lo respalda Hilbert
junto con Ackerman en su obra Elementos teóricos
de la Lógica y citamos a los autores: “Ahora bien, las
relaciones desempeñan el papel más esencial en la
construcción lógica de las matemáticas. Únicamente
pudo subsistir el error de que la lógica tradicional
bastaba para construir lógicamente las matemáticas
a partir de sus fundamentos, porque antes de Frege
y Peano nadie había emprendido un análisis total de
los modos deductivos empleados en la matemática”.
 (b) La distinción y separación de la
Lógica proposicional de la Lógica
cuantificacional, en palabras de G. Moore, lo
que se hizo fue “la adecuada separación y
representación simbólica de las nociones de
conectiva proposicional y cuantificador”.
Charles Sanders Peirce (1839-1914)
 Peirce introdujo, en sus escritos de 1883
y 1885, notaciones diferenciables con
respecto a las conectivas y a los
cuantificadores, pero deja claro en dichas
notas, que entendía a los cuantificadores
como las abreviaturas de fórmulas
infinitarias, así pues, una fórmula existencial
“Ǝx Px” vendría a interpretarse como una
cadena infinita de disyunciones y de forma
análoga ocurre con el cuantificador
universal, sólo que esta vez se trataba de
una cadena infinita de conjunciones.
 Peirce reconocía que los cuantificadores ligaban
variables individuales, pero también cuantificó
sobre variables predicativas, de hecho usó lo que se
conoce hoy en día como Lógica de segundo orden, o
L2, para poder definir la relación de identidad, así
pues, según Peirce:

“…decir que dos cosas son idénticas es decir que

todo predicado es verdadero de ambas o falso de
ambas”

Debemos notar que la expresión “todo

predicado” denota un cuantificador universal que
está ligando una variable predicativa o de segundo
orden ([a=b → ∀P (P(a) ↔P(b))])
Gottlob Frege (1848-1925)
 Mientras tanto el caso de Frege dista mucho de lo
que ocurría con Peirce. El creador de la Conceptografía,
quien tenía en mente reducir la aritmética y el análisis a
la lógica, sí hizo un fuerte uso de la Lógica de segundo
orden, de hecho el uso de tal lógica era necesario por los
objetivos que guiaban su filosofía de la matemática de
corte logicista. El lógico alemán había sustituido las
nociones de sujeto y predicado, que pertenecían a la
gramática clásica y a la lógica aristotélica, por las
nociones matemáticas de argumento y función, de tal
manera que ahora se podría, desde la lógica, dar cuenta
de las estructuras relacionales como funciones que eran
satisfechas o no satisfechas por n argumentos (donde n
es la aridad de la función); en el caso de Frege, tanto los
argumentos como las funciones podían ser
cuantificados, inclusive el poder cuantificar sobre
funciones le permite enunciar el Principio de inducción
matemática.
 Lo que debe llamar poderosamente
nuestra atención es que en un principio la
lógica que parecía más adecuada para tratar
a la matemática era la Lógica de segundo
orden, de hecho los seguidores de la
tradición booleana, como es el caso de Ernst
Schröder y Leopold Löwenheim, usaban una
Lógica de segundo orden que entendía a los
cuantificadores como conjunciones o
disyunciones infinitas.
Ernst Schröder (1841 – 1902)
 El sistema lógico imperante durante la
última mitad del siglo XIX fue el presentado
por Schröder en sus tres volúmenes de
Vorlesungen über die Algebra der Logik (1890
– 1895).

Schröder realiza un tratamiento y

ampliación de los métodos y conceptos
presentados por la tradición algebraica (Boole
y Peirce), aunque no hay una distinción
consciente entre la cuantificación de primer y
de segundo orden (como si ocurría en Peirce).
 Siguiendo los pasos lógico-filosóficos de
Frege, pero mediante un simbolismo más
cercano al de Peano, encontramos el trabajo
de Bertrand Russell y Alfred Whitehead,
quienes trataban de reducir toda la
matemática a la lógica. En el transcurso de
tal logicismo fuerte, Russell descubrió que
tanto de la teoría ingenua de conjuntos de
Cantor como de la obra lógica de Frege se
podían derivar paradojas que conllevan a
sendas contradicciones.
Bertrand Arthur William Russell (1872–1970)
Alfred North Whitehead (1861–1947)
 A finales de 1908, y luego en 1910, el
filósofo inglés presenta como base lógico-
deductiva de Principia Mathematica a la
Teoría de tipos que consistía en una
jerarquización del lenguaje, en donde, al
primer tipo lógico, o nivel, pertenecen los
individuos, el segundo tipo es propio de las
propiedades de los individuos del primer
tipo, al tercer tipo pertenecen las
propiedades de las propiedades de los
individuos del primer tipo y así
sucesivamente, y donde la regla general es
que sólo se permiten expresiones en donde
el predicado es de un tipo lógico
inmediatamente superior al tipo del sujeto.
 Una consecuencia inmediata de la Teoría de
tipos es que ésta incluye a la Lógica de primer
orden en tanto que permite la predicación de
objetos, pero también permite predicar sobre
predicados, predicar sobre predicados de
predicados y así sucesivamente, es decir,
abarca también a la Lógica de segundo orden,
tercer orden, etc. Si bien empiezan a detallarse
las fronteras de L1, la misma no aparece para
esa época como un sistema propio en la obra
de Russell y Whitehead, sino como un sub-
sistema de la Teoría de tipos.
 En 1915 el lógico matemático Leopold
Löwenheim demuestra lo que se considera, en
términos formales, el primer teorema
metalógico importante, abriendo así el campo
de la teoría de modelos.

Entre los fundamentos y métodos usados

por Löwenheim para demostrar su teorema se
encuentra una clase de proposiciones en
primer orden, aunque su terminología no
coincide con la Lógica de primera
intencionalidad de Peirce ni con la Teoría de
Tipos de Russell-Whitehead.
Leopold Löwenheim (1878 - 1957)
 La Lógica de primer orden (L1) fue caracterizada
por primera vez por David Hilbert en sus clases
magistrales (lectures) de 1917-1918: Prinzipien der
Mathematik und Logik. Luego fue presentado, en 1928,
en la obra Grundzüge der theoretischen Logik que
escribieron conjuntamente Hilbert y Ackermann
(También Paul Bernays realizo trabajos junto a Hilbert
caracterizando a la lógica de primer orden) . En dicha
obra, los autores presentan a L1 como un subsistema de
la Teoría de tipos, pero se ocupan de ella como si se
tratase de un sistema en sí mismo (exigiendo para la
misma pruebas de completitud, consistencia,
independencia y decidibilidad), es decir, establecen cual
es su lenguaje y ofrecen un sistema axiomático para la
misma.
 David Hilbert (1862-1943)
Paul Bernays (1888 - 1977)
Wilhelm Ackermann (1896 – 1962)
 Sin embargo, en el mismo momento en
que Hilbert presenta a L1 como un sistema
propio, también la desacredita como una
base adecuada para la matemática, y la
razón de ello es que las nociones de la teoría
de conjunto así como el principio de
inducción matemática no podían ser
adecuadamente tratados en Lógica de
primer orden.
 A pesar de lo anterior en el año 1923 el
matemático noruego Thoraf Skolem realizó
dos propuestas ante la comunidad
matemática: La primera consistía en
considerar a la Lógica de primer orden
como toda la lógica, mientras que la
segunda tenía que ver con trabajar a la
teoría de conjuntos en el marco de la Lógica
de primer orden.
Thoralf Skolem (1887 - 1963)
 A pesar de las limitaciones expresivas que
le son intrínsecas a L1, ésta terminó ganando la
batalla como lógica base de la matemática
debido a dos resultados metateóricos que se
demostraron iniciando la década de los 30 del
siglo pasado. Se trata del teorema de
completitud de la lógica de primer orden
probado por Gödel en 1930 y el teorema
limitativo que Gödel probó en 1931. Además
debemos agregar como razones de la
constitución la simplicidad de dicha lógica y lo
fructífero que han resultado sus métodos para
los estudios matemáticos y meta-matemáticos.
Kurt Friedrich Gödel (1906 - 1978)
 Desde entonces, la Lógica de primer orden
ocupa un importante lugar en la lógica
matemática presentándose como una de las
más versátiles y aplicables al igual que una de
las más estudiadas. Lo que distingue a la Lógica
de primer orden de la Lógica proposicional es
la posibilidad de dar cuenta de la estructura
interna de las proposiciones, en términos de
predicados e individuos, de tal manera que con
L1 se pueden estudiar dos actos esenciales del
lenguaje, propios también del lenguaje
matemático, esto es, la predicación y la
cuantificación.
Acercamiento informal (intuitivo) a la
sintaxis de L1
 Para este comentario seguiremos a
los siguientes autores:
Copi, I., Lógica simbólica, C.E.C.S.A, México D.F., 1979.

Copi, I. y Cohen, C., Introducción a la lógica, Editorial Limusa, México

D.F., 2000 (Traducción de la 8va edición en ingles)

Deaño, A., Introducción a la lógica formal, Alianza Edotiral, Madrid,

1999.

Garrido, M., Lógica simbólica. Tecnos. Madrid. 2001 (4ta edición).

Trevijano, G., El Arte de la lógica. Tecnos, Madrid, 2008.

 El lenguaje nos permite: (1) Designar
objetos de un universo del discurso mediante
nombre propios, (2) Designar propiedades de
los objetos de dicho universo mediante
predicados (nombres comunes) y finalmente
(3) Decir de algunos o de todos los objetos del
universo que tienen una determinada
propiedad.

En síntesis podemos decir que con el

lenguaje podemos, entre otras cosas, (1)
referir, (2) predicar y (3) cuantificar.
 Con La lógica de primer orden (de la que es
parte la lógica de predicados monádicos y
poliádicos) podemos formalizar y modelar dichos
fenómenos lingüísticos (la referencia, la predicación
y la cuantificación). Esto a su vez permite estudiar
las estructuras de las proposiciones y analizar los
argumentos cuya inferencia depende de dichos
fenómenos lógico-lingüísticos.
 Sujetos y predicados
Ejemplos de nombres propios son: Jorge,
Ana, María, Pedro, Platón, La luna, Marte,
Amazonas, Venezuela, Vía Láctea, etc.
Ejemplos de predicados son: Humano,
Hombre, Mujer, Profesor, Filósofo, Planeta,
Ciudad, País, Región, Hermano, Padre, Profesor,
etc.
A los nombres propios se les suele entender
en términos lógicos como sujetos de los que se
predica una determinada propiedad.
 Predicados absolutos
Se consideran predicados de carácter
absoluto o monádico, esto es, nombres
comunes que sirven para denotar una
propiedad, rasgo o cualidad que conviene
simplemente a un objeto. Por ejemplo, el
predicado «profesor» es monádico, en tanto
que su evaluación corresponde a un solo
objeto, esto es, Pedro es profesor o no lo es
con independencia de los otros objetos o
individuos del universo del discurso.
Predicados relativos (relaciones)

En otras ocasiones la cualidad o

propiedad designada por el predicado es
una relación que se da entre dos o más
objetos, por ejemplo, el predicado relativo
“ser mayor” o “ser hermano de”.
 Gracias al lenguaje podemos informar
que un determinado objeto tiene una
determina propiedad, o que dos objetos se
encuentran en una determinada relación.
Esto lo hacemos uniendo o componiendo
nombres propios con predicados, esto da
lugar a proposiciones (predicaciones).
 Por ejemplo:
• Ana es mujer
• Jorge es mujer
• Pedro es hombre
• María es hombre
• La Luna es un planeta
• Ana es hermana de Pedro
• La luna es más pequeña que Júpiter
• Entre el Sol y Júpiter se encuentra la Luna.

Al ser la forma más simple de formar proposiciones

se les suele calificar como proposiciones primitivas o
atómicas.
 Para llevar a cabo una exitosa simbolización de
proposiciones atómicas (monádicas o poliádicas), es
necesario distinguir entre dos tipos de símbolos
para dar cuenta de los componentes subatómicos
(calificados tradicionalmente como sujeto y
predicado). Para simbolizar a los objetos usaremos
letras minúsculas, en especial las primeras del
alfabeto y excluyendo a las últimas (desde la v hasta
la z). A dichas letras minúsculas se les suele llamar
constantes individuales. Para denotar a las
propiedades usaremos letras mayúsculas. En el
último caso dichos símbolos son conocidos como
letras o variables predicativas (cuya aridad
dependerá del número de objetos que afecte el
predicado).
 Por simplicidad consideremos las siguientes
proposiciones monádicas atómicas:

• Aristóteles es filósofo
• Kant es filósofo
• Frege es filósofo
• Jackson es filósofo
 Todas estas proposiciones tienen algo en común,
se predica de todos ellos los objetos (Aristóteles,
Kant, Frege y Jackson) que son filósofos, esto es, el
predicado “es filósofo”. El esquema proposicional
que tienen en común las proposiciones anteriores es
x es filósofo (denotada por “F(x)”).

F(x) no es una proposición, pues «x» es una

variable y no es una constante individual, por lo que
Fx no puede considerarse como verdadera o falsa
hasta no sustituir (satisfacer) x por una constante
individual. De esta manera contamos con un nuevo
símbolo, se trata de las variables individuales (el rol
de la variable se asemeja al rol del pronombre en el
lenguaje natural).
Esquema proposicional y proposición
Una de las formas que tenemos para
obtener de un esquema proposicional una
proposición es sustituyendo la variable del
esquema por una constante individual. Pero
existe otra forma de obtener una proposición a
partir de un esquema proposicional mediante
la adhesión de un cuantificador. De esta
manera si tenemos el esquema proposicional
Fx, entonces podemos volverlo una proposición
(compleja) al convertirlo en: Todos los x son F
o Algunos x son F.
 Las proposiciones que se fundan en la
partícula «todo» (o similares) reciben el
nombre de generales o universales,
mientras que la se fundan en la partícula
«algunos» (o similares) reciben el nombre
de particulares o existenciales. Dichas
partículas reciben el nombre de
cuantificadores.
 Intuitivamente el cuantificador universal
indica que todos los individuos que
sustituyan la variable cumplen con la
propiedad en cuestión, mientras que
intuitivamente el cuantificador existencial
indica que por lo menos existe una
sustitución de la variable que cumple con la
propiedad en cuestión.
 Todo lo anterior se puede caracterizar de
manera formal y rigurosa presentando la
sintaxis de la lógica de primer orden.
 Sintaxis de L1

•Lenguaje ℒ de primer para fórmulas de L1

orden •Definición de subfórmula
•Formalización del •Definición de Variable
lenguaje libre en una fórmula
•Definición de Término •Definición de Variable
•Definición de Fórmula ligada en una fórmula
atómica •Definición de Sentencia
•Definición de Fórmula •Definición de Término
•Principio de inducción sustituible en una fórmula
 Para definir la sintaxis de la lógica de primer
orden seguiremos a los siguientes autores:
• Di Prisco, C., Introducción a la lógica matemática, EMALCA AMAZONIA,
2009.
• Chang, C. C. y Keisler, H., Model Theory, Editorial North-Holland, New
York, 1990 (3ra. Ed.)
• Ebbinghaus, H. D., Flum, J. y Thomas, W., Mathematical logic, Springer,
1994.
• Enderton, H., Una Introducción Matemática a la Lógica, Universidad
Nacional Autónoma de México, 2004.
• Galindo, F., Tesis de licenciatura: Una demostración del Teorema de
Lindström (Tutor: Dr. Carlos Di Prisco), UCV, Caracas, 1996.
• Hamilton, A. Lógica para matemáticos. Paraninfo. Madrid. 1981.
• Mendelson, E., Introduction to Mathematical Logic. Chapman and
Hall/CRL. U.S.A. 2009.
• Nerode, A. y Shore, R., Logic for applications. Springer, 1997, entre
otros
 Es importante señalar que trabajaremos
con la Lógica plena de primer orden (first
order logic full), es decir, con la que contiene
símbolos para funciones y símbolos de
constantes, a diferencia de la Lógica pura de
primer orden (first order logic pure) que no
contiene dichos símbolos.
 Lenguaje ℒ de primer orden
Un lenguaje ℒ es una colección de símbolos
que puede ser de cardinalidad numerable o
mayor que numerable, en nuestro caso nos
concentraremos en un lenguaje de cardinalidad
numerable. Los símbolos de ℒ son de tres tipos:

• Símbolos relacionales: R0, R1,…, Rn ,…

• Símbolos funcionales: f0, f1,…, fn ,…
• Símbolos constantes: c0, c1,…, cn,…
 En términos extensionales ℒ es el
siguiente conjunto:

ℒ = {R0, R1,…, Rn,…; f0, f1,…, fn ,…; c0, c1,…, cn,…}

 Es importante señalar que todo símbolo
relacional y funcional lleva asociado un
número natural igual o mayor a 1 que
simboliza su aridad o el número de sus
argumentos. Así, tenemos símbolos funcionales
o relacionales monádicos, diádicos,…, n-ádicos.
Otro detalle importante es que los lenguajes
pueden ser finitos o infinitos, y dentro de
aquellos que son infinitos están los que son
numerables y los que son innumerables, pero
para nuestros propósitos trabajaremos con
lenguajes numerables.
Ejemplos de lenguaje de primer
orden
 Un lenguaje para la aritmética es el
siguiente

{≤, +, ·, 0, 1}

Contiene:
Un símbolo relacional diádico para la relación de orden
“menor o igual que”.
Un símbolo funcional diádico para la función “suma”.
Un símbolo funcional diádico para la función “producto”.
Un símbolo constante para el número cero (0).
Un símbolo constante para el número uno (1).
 Un lenguaje para órdenes

{≤}

Contiene un símbolo relacional diádico

para la relación de orden “menor o igual
que”.
 Un lenguaje para la Teoría de
conjuntos

{∈}

Contiene un símbolo relacional diádico

para la relación de “pertenencia”.
 Formalización del lenguaje
Para llevar a cabo la formalización de un lenguaje ℒ
usamos los símbolos lógicos:

• Conectivas: ¬ (negación), ⋀ (conjunción),

⋁(disyunción), (condicional), ⟷ (bicondicional)
• Cuantificadores: ∃(existencial), ∀(universal)
• Símbolo de identidad: ≡ (símbolo relacional binario)
• Variables: x0, x1, x2,…, xn,…. (n ∈ ℕ)
• Paréntesis: (,)
• Coma: ,

Denotaremos por VAR al conjunto de las variables.

Definición (inductiva) de Término
(i) Toda variable es un término y todo símbolo de
constante es también un término.

(ii) Si f es un símbolo funcional n-ario y t1,…, tn son

términos, entonces f (t1,…, tn) es un término.

(iii) Una sucesión de símbolos es un término sólo si se

obtiene mediante la cláusula (i) y (ii) en un número
finito de pasos.

Denotaremos por Tℒ al conjunto de términos del

lenguaje ℒ.
 Ejemplos de términos de ℒ:

(a)x1

(b) c500

(c) f2(c500, c40)

 Definición de Fórmula atómica
(i) Si t1 y t2 son términos, entonces t1 ≡ t2 es
una fórmula atómica.

(ii)Si R es una símbolo relacional n-ario y

t1,…, tn son términos, entonces R(t1,…, tn)
es una fórmula atómica.
 Ejemplos de fórmulas atómicas
(a)f2(c500, c40) ≡ c15

(b) R3(c500, c40, f2(c14, c30))

Definición (inductiva) de Fórmula
(i) Toda fórmula atómica es una fórmula.

(ii) Si φ y ψ son fórmulas, entonces (¬ φ), (φ ⋁ ψ), (φ ⋀ ψ),

(φ ⟶ ψ) y (φ ⟷ ψ) son fórmulas.

(iii) Si 𝑣 es una variable y φ es una fórmula, entonces (∀x)φ y

(∃x)φ son fórmulas.

(iv) Una sucesión de símbolos es una fórmula sólo si se

obtiene mediante un número finito de aplicaciones de las
cláusulas (i), (ii) y (iii).

Denotaremos por FBFℒ al conjunto de términos del

lenguaje ℒ.
 Cuando no exista ambigüedad
escribiremos ∀x φ en vez de (∀x)φ y lo
mismo para el caso del existencial. El uso de
paréntesis evita las ambigüedades en la
lectura de una fórmula, pero en la medida
que sea posible omitiremos los mismos por
simplicidad.
 Ejemplos de fórmulas

(a) ¬(f2 (c14, c30) ≡ c15)

(b) R3(c500, c40, f2(c14, c30)) ⟶ R2(c512, c6)

(c) ∃x2 (f1(x2) ≡ c40)

 Nótese que tanto la definición de término como la de
fórmula bien formada (fbf) son definiciones inductivas,
por tanto, si se desea probar o definir alguna propiedad
sobre los términos o sobre las fórmulas conviene usar
inducción basada en la complejidad de dichos términos o
fórmulas, dicha inducción se puede realizar de varias
maneras: Por ejemplo, (1) usando la definición inductiva
anteriormente formulada y (2) considerando el número
de conectivas y cuantificadores de la fórmula, notar que
a toda fórmula se le puede asociar un número natural, su
rango, el cual corresponde al número de conectivas y
cuantificadores presentes en la fórmula. En base a dicho
rango se puede definir o probar propiedades sobre las
fórmulas utilizando inducción en los números naturales.
Análogamente se le puede asignar un número natural, su
longitud, a todo término considerando el número de sus
símbolos primitivos.
 Principio de inducción para las
fórmulas del lenguaje de L1
Sea P(x) una propiedad sobre las fórmulas de L1

Si:
(Hipótesis)
(i) Toda Fórmula atómica tiene la propiedad P
(ii) Si φ y ψ son fórmulas que tienen la propiedad P, entonces (¬φ), (φ ⋀
ψ), (φ ⋁ ψ), (φ ⟶ ψ) , (φ ⟷ ψ).
(iii) Si φ es una fórmula , x es una variables y φ tiene la propiedad P,
entonces ∀x φ y ∃ x φ tienen la propiedad P.

Entonces:
(Tesis)
Toda fórmulas de L1 tiene la propiedad P.
Demostración (usando inducción matemática fuerte)
(Sugerencia del Dr. Franklin Galindo (UCV)):

Sea α una fórmula del lenguaje de la

lógica de primer orden, el rango de α, al que
denotamos por RAN(α), se define como
sigue:

RAN(α)= el número de conectivas y

cuantificadores en α.
 Suponiendo como hipótesis (i), (ii) y
(iii), probaremos por inducción fuerte que:

∀n∈ℕ ∀γ∈ FBFℒ1[RAN(γ) = n⟶ P(γ) es

cierta], donde

Q(n) : ∀γ∈ FBFℒ1[RAN(γ) = n⟶ P(γ) es

cierta].
 Caso Base: n=0
Debemos probar que Q(0) es cierta, esto es,
que ∀γ∈ FBFℒ1[RAN(γ) = 0⟶ P(γ) es cierta].

Sea β ∈ FBFℒ1 una fórmula atómica, es decir,

β = t1 ≡ t2 o β = R(t1,…, tn), donde t1,…, tn son
términos y R es una símbolo relacional n-ario.

En este caso P(β) se cumple, por la cláusula

(i) de la hipótesis.
 Caso inductivo:
Sea r ∈ ℕ, r > 0. Supongamos además
que para cada natural j<r, se cumple Q(j), es
decir, ∀γ∈ FBFℒ1[RAN(γ) = j ⟶ P(γ) es
cierta].

Debemos probar que Q(r) se cumple,

esto es, ∀γ∈ FBFℒ1[RAN(γ) = r ⟶ P(γ) es
cierta].
 Sea α una fórmula de la lógica de primer orden tal
que RAN(α)=r, entonces α puede ser de cualquiera de
las siguientes siete (7) formas:

(1) α=¬β
(2) α =β⋀λ
(3) α =β⋁λ
(4) α =β⟶λ
(5) α =β⟷λ
(6) α =∀x β, donde x es una variable
(7) α =∀x β, donde x es una variable

Probaremos que para cada uno de estos sub-casos

((1), (2), (3), (4), (5), (6) y (7)), P(α) se cumple.
 Sub-caso (1) : α=¬β
Si α=¬β, entonces RAN(β) = r-1, pues
RAN(¬β)= r.

Luego, P(β) es verdadera por hipotesis

inductiva. En consecuencia, por la cláusula
(ii) de la hipotesis, P(α) es verdadera.
 Sub-caso (2): α =β⋀λ
Si α = β⋀λ, entonces, como
RAN(α) = RAN(β)+RAN(λ)+1, se cumple
que RAN(β) < RAN(α) y RAN(λ)< RAN(α)
(Esto es, RAN(β) < r y RAN(λ) <r).

Por la hipótesis inductiva P(β) y P(λ) son

verdaderas. En consecuencia, por la cláusula
(ii) de la hipótesis, P(β⋀λ) es cierta.
 Sub-caso (3): α =β⋁λ
Si α = β⋁λ, entonces, como
RAN(α) = RAN(β)+RAN(λ)+1, se cumple
que RAN(β) < RAN(α) y RAN(λ)< RAN(α)
(Esto es, RAN(β) < r y RAN(λ) <r).

Por la hipótesis inductiva P(β) y P(λ) son

verdaderas. En consecuencia, por la cláusula
(ii) de la hipótesis, P(β⋁λ) es cierta.
 Sub-caso (4): α =β⟶λ
Si α = β⟶λ, entonces, como
RAN(α) = RAN(β)+RAN(λ)+1, se cumple
que RAN(β) < RAN(α) y RAN(λ)< RAN(α)
(Esto es, RAN(β) < r y RAN(λ) <r).

Por la hipótesis inductiva P(β) y P(λ) son

verdaderas. En consecuencia, por la cláusula
(ii) de la hipótesis, P(β⟶λ) es cierta.
 Sub-caso (5): α =β⟷λ
Si α = β⟷λ, entonces, como
RAN(α) = RAN(β)+RAN(λ)+1, se cumple
que RAN(β) < RAN(α) y RAN(λ)< RAN(α)
(Esto es, RAN(β) < r y RAN(λ) <r).

Por la hipótesis inductiva P(β) y P(λ) son

verdaderas. En consecuencia, por la cláusula
(ii) de la hipótesis, P(β⟷λ) es cierta.
Sub-caso (6): α =∀x β, donde x es una
variable.
Si α =∀x β, entonces, como
RAN (∀x β) = RAN (β) + 1 = R, se tiene que
RAN(β) < r. Se sigue entonces, por hipótesis
inductiva, que P(β) es cierta.

Luego, por la cláusula (iii) de la

hipótesis, P(∀x β) es verdadera.
Sub-caso (7): α =∃x β, donde x es una
variable.
Si α =∃x β, entonces, como
RAN (∃x β) = RAN (β) + 1 = R, se tiene que
RAN(β) < r. Se sigue entonces, por hipótesis
inductiva, que P(β) es cierta.

Luego, por la cláusula (iii) de la

hipótesis, P(∃x β) es verdadera.
 Luego, por el principio de inducción
matemática fuerte se concluye que ∀n ∈ ℕ
Q(n), esto es, toda fórmula de la lógica de
primer orden tiene la propiedad P. ∎
Definición (inductiva) de Sub-fórmula

Una subfórmula de una fórmula φ es una

secuencia consecutiva de símbolos de φ que
por sí mismo es una fórmula. Al conjunto de
las sub-fórmulas de φ se le denota por
SF(φ), a dicho conjunto se le puede definir
por inducción matemática en φ de la
siguiente manera:
(i) Si φ es atómica, entonces SF(φ) = {φ}.

(ii) Si φ = ¬ψ, entonces SF(φ) = {¬ψ} ∪ SF{ψ}.

(iii) Si φ = ψ ⋁ γ, entonces SF(φ) = {ψ ⋁ γ} ∪ SF{ψ} ∪ SF{γ}.

(iv) Si φ = ψ ⋀ γ, entonces SF(φ) = {ψ ⋀ γ} ∪ SF{ψ} ∪ SF{γ}.

(v) Si φ = ψ ⟶ γ, entonces SF(φ) = {ψ ⟶ γ} ∪ SF{ψ} ∪

SF{γ}.

(vi) Si φ = ψ ⟷ γ, entonces SF(φ) = {ψ ⟷ γ} ∪ SF{ψ} ∪

SF{γ}.

(vii)Si φ = ∀𝑣 ψ, entonces SF(φ) = {∀x ψ } ∪ SF{ψ}.

(viii)Si φ = ∃𝑣 ψ, entonces SF(φ) = {∃x ψ } ∪ SF{ψ}.

 Ejemplo de sub-fórmulas de una
fórmula

Sea φ= R3(c500, c40, f2(c14, c30)) ⟶ R2(c512, c6)

SF(φ) =
{R3(c500, c40, f2(c14, c30)) ⟶ R2(c512, c6);
R3(c500, c40, f2(c14, c30)); R2(c512, c6)}.
Definición (inductiva) de variable
libre en una fórmula

Si 𝑣 es una variable y φ es una fórmula,

definiremos por inducción lo que significa
que 𝑣 ocurre libre en φ:
(i) Sea φ es una fórmula atómica, entonces x
ocurre libre en φ, si es símbolo de φ.
(ii)x ocurre libre en (¬ φ), si ocurre libre en
φ; x ocurre libre en (φ ⋁ ψ), si ocurre libre
en φ o ψ; x ocurre libre en (φ ⋀ ψ), si
ocurre libre en φ o ψ; x ocurre libre en
(φ ⟶ ψ), si ocurre libre en φ o ψ; x ocurre
libre en (φ ⟷ ψ), si ocurre libre en φ o ψ.
(iii)x ocurre libre en ∀xi φ o ∃xi φ si ocurre
libre en φ y x ≠ xi.
Ejemplo de una variable libre en una
fórmula

Consideremos la siguiente fórmula:

∀x2∀x40 f2((x2, x40) ≡ x15)

En ella, la variable x15 se encuentra libre.

Definición de Variable ligada en una
fórmula

Si x ocurre en φ, pero no libremente,

entonces diremos que x ocurre ligada en φ.
 Una variable puede estar libre y ligada
en una misma fórmula, por eso se habla de
ocurrencias libres y ligadas. Por ejemplo en
la siguiente fórmula:

∀x2∀x40 f2((x2, x40) ≡ x15) ⟶ ∀x2∀x40∃x15 f2((x2, x40) ≡ x15)

La primera ocurrencia de x15 se

encuentra libre mientras que la segunda
ocurrencia de x15 se encuentra ligada (bajo
el alcance del cuantificador ∃).
 Definición de Sentencia

Decimos que una fórmula φ es una

sentencia, si φ no tiene variables libres.

Ejemplo:
La fórmula ∀x2∀x40∃x15 f2((x2, x40)≡ x15)
es una sentencia.
Definición (inductiva) de Término
sustituible en una fórmula

Sea φ(x) una fórmula y t un término,

decimos que t es libre para x en φ, si
ninguna variable libre de x queda
cuantificada (ligada) al sustituir las
ocurrencias libres de x por t en φ.
Ofrecemos una definición por inducción de
dicho concepto.
Sea φ(x) una fórmula y t un término:

(i) Si φ es atómica, t es libre para x en φ.

(ii) ii.1. t es libre para x en (¬ φ), si t es libre para x en φ

ii.2. t es libre para x en (φ ˄ ψ), si t es libre para x en φ y

en ψ

ii.3. t es libre para x en (φ ∨ ψ), si t es libre para x en φ y

en ψ

ii.4. t es libre para x en (φ ⟶ ψ), si t es libre para x en φ y

en ψ

ii.5. t es libre para x en (φ ⟷ ψ), si t es libre para x en φ

y en ψ.
(iii)
iii.1. t es libre para una variable 𝑣 en (∀x)φ si:
a) 𝑣 no ocurre libre en (∀x)φ,
o
b) x no ocurre en t y t es libre para 𝑣 en φ.

iii.2. t es libre para una variable 𝑣 en (∃x)φ si:

a) 𝑣 no ocurre libre en (∃x)φ,
o
b) x no ocurre en t y t es libre para 𝑣 en φ.
Consideremos el siguiente ejemplo:

Sea φ = ∀x2∀x40 f2((x2, x40) ≡ x15) y t=

f1(x2), entonces t no es libre para x15 en φ.

Sea la φ anterior y t= f1(x800), entonces t

es libre para x15 en φ.
¿Un término es siempre sustituible en
una fórmula?

No, sólo lo es cuando al sustituirlo, las

variables libres del término no quedan
ligadas.
 Evaluemos el siguiente caso:

Consideremos la siguiente fórmula:

∃x ¬(x ≡ y)

Formalmente nos dice que existe un x tal que no es cierto que x sea
idéntico a y.

Si interpretamos dicha fórmula en la estructura estándar de la

aritmética, la fórmula dice, intuitivamente, que hay un número que es distinto
de y.

Pero podemos construir una asignación (una función que tiene por
conjunto de partida a VAR y por conjunto de llega a los naturales) para y que
satisface dicha fórmula, por ejemplo, A: VAR ⇒ℕ, tal que A(y)= S(x) (Donde
S(x) es el sucesor de x, esto es, S(x): x+1).
 Ahora bien, si sustituimos x por y
(teniendo presente que la variable y se
encuentra libre), tendríamos:

∃x ¬(x ≡ x)

Lo cual resulta falso en la aritmética

pues no hay ninguna asignación que
satisfaga dicha fórmula.
 Un ejemplo de lenguaje de primer
orden: El lenguaje de la aritmética en
primer orden.
Para la construcción del siguiente
lenguaje nos inspiramos en:

Hamilton, A. Lógica para matemáticos.

Paraninfo. Madrid. 1981.
 Consideremos a la aritmética como todas
las sentencias que son verdad en la
siguiente estructura ‹ℕ, +, ∙, S, 0›, donde ℕ
es el conjunyo de los naturales, + es la suma
entre naturales, ∙ es el producto entre
naturales, S es la función sucesor, es decir, la
función que a cada natural n le asigna n+1,
y por último tenemos un individuo
destacado que es el cero. Podemos ver
entonces a la aritmética como el siguiente
conjunto: {ϕ| ϕ es verdad en ‹ℕ, +, ∙, S, 0›}.
 Construiremos un lenguaje en primer
orden para formalizar y simbolizar dicha
teoría, lo llamaremos N
 Lenguaje de N

Símbolos lógicos:

• Conectivas: ¬, ⟶
• Símbolos auxiliares: (, ), ,
• Cuantificadores: 
• Variables: x, y, z,… (una cantidad
numerable)
• Identidad: ≡
Símbolos no-lógicos:

• Una constantes para el cero, que en nuestro

caso será el símbolo 0.
• Dos símbolos funcionales diádicos, uno para
la suma y otro para el producto, que en
nuestro caso serán los símbolos + (para la
suma) y ∙ (para el producto).
• Un símbolo funcional monádico para la
función sucesor, que en nuestro caso será S.
 Definición de término en N
(i) 0 es un término y toda variable es un
término.
(ii)Si t es un término, entonces S(t) es un
término.
(iii)Si t1 y t2 son términos, entonces t1 + t2 y
t1 ∙ t2 son términos.
(iv)Sólo son términos las secuencias finitas de
símbolos que podemos construir mediante
las clausulas (i), (ii) y (iii).
Definición de fórmula atómica en N

Si t1 y t2 son términos, entonces t1≡t2 es

una fórmula atómica.
 Definición de fórmula (fbf) en N
(i) Toda fórmula atómica es una fórmula.
(ii)Si ϕ y δ son fórmulas entonces (¬ϕ) y
(ϕ → δ) son fórmulas.
(iii)Si x es una variable y ϕ es una fórmula,
entonces x (ϕ) es una fórmula.
(iv)Sólo son fórmulas las secuencias finitas de
símbolos que se pueden construir
mediante las clausulas i, ii y iii.
 Ejemplos de sentencias en N

x y z ((x + y) + z = x + (y + z))
(Propiedad asociativa de la suma)

x y z (x ∙ (y + z) = (x ∙ y) + (x ∙ z))
(Distribución del producto en la suma)
¡Gracias por su atención!