Download David Becerril Rodríguez (UMSNH / Fac. de C. Físico

"Una Introducción Didáctica a la Teoría de los Tipos"
David Becerril Rodríguez*, Jesús Castañeda Rivera
Facultad de Ciencias Físico-Matemáticas UMSNH*
Instituto de Matemáticas UNAM Unidad Morelia
Grupo de Lógica y Matematicas Morelia AML
Email: [email protected]
Introducción
En este trabajo daremos una breve introducción a lo que es la teoría de tipos y la lógica
de primer orden. Se darán los conceptos y definiciones básicas relativos a la teoría de
tipos y la lógica de primer orden, con el objetivo de poder comprender y demostrar el
teorema de sustitución de tautologías.
La idea principal de este trabajo es ofrecer una manera alternativa de enseñanza para
mejorar el aprendizaje de los alumnos de nivel superior en la comprensión de este tema.
1.0 Definiciones Básicas
Lenguajes de Primer Orden de un P-tipo
Definición 1.- Un tipo es un conjunto de p-símbolos, de la forma:

 

p   Rn   Fm  C
1n  1m 
R
Donde n es un conjunto de símbolos relacionables de cardinalidad n, Fn es un
conjunto de símbolos funcionales de cardinalidad m y C es un conjunto de constantes.
Definición 2.- Los símbolos de un lenguaje de primer orden del tipo p, también
L
denotado como p son:
i) V0 , V1 ,...Vn , Vn1 (para variables individuales)
ii) (,),[,].... (Símbolos auxiliares)
iii) ,, ,  (conectivos lógicos)
iv)  (símbolo de igualdad)
v) ,  (cuantificadores)
Observación.- Un lenguaje de primer orden L de un tipo dado consta de los
símbolos de un p tipo y de los símbolos de un lenguaje de primer orden,
Definición 3.- Una estructura se define como:
A = <A,R,O,E>
Donde A   , A siendo el conjunto universo, R es un conjunto de relaciones sobre A,
1
que son la interpretación de los símbolos del tipo. O es una colección de operaciones
sobre A que son interpretaciones de los símbolos de función de operaciones sobre A. E
es una colección de elementos de A que son interpretaciones de los símbolos constantes
del tipo.
Observación.- Una interpretación es una función de A sobre el universo A.
Definición 4.- Sea “p” un tipo, una expresión de un tipo “p”, también llamada “p”
L
expresión, es una sucesión finita de símbolos de lenguaje p .
Definición 5.- Una p-formula atómica es una expresión de la forma (t1  t2 ) o
p * (t1 ,..., t n )
,
P *  Rn  P
donde t1 ,..., t m son “p” términos y
Definición 6.- El conjunto de formulas de un tipo "p", es el conjunto de p expresiones
tal que:
i) {  :  es una p-formula atómica}
ii) si  ,   X  ( ), (   )  X X siendo el conjunto de las p-expresiones
 
iii) si    y V una variable, entonces vi   X
Observación.- Una P formula es un elemento del conjunto de las formulas tipo P.
2.0 Bloques, Proposiciones y Valuaciones
Sea L un lenguaje de primer orden de un tipo dado arbitrario:
Definición 7.- Una formula  de un lenguaje L se llama bloque si y solo si  es una
formula atómica o es una cuantificación.
Observación.- Un bloque no es una fórmula que sea una negación, una
disyunción, una conjunción un condicional o un bicondicional.
Definición 8.- Se definirá E como el conjunto de todos los bloques de L.
Observación.- Toda formula de L se puede genera a partir de E mediante una
seria finita de aplicaciones de los conectivos.
Definición 9.- Una expresión es una sucesión de símbolos de L.
Definición 10.- Una proposición se define recursivamente como:
i) Los bloques son proposiciones.
ii) Si  y  son proposiciones, entonces también lo son:
( ), (   ), (   ), (   ), (   )
Definición 11.- Una valuación es una función V definida sobre el conjunto E con
valores en {0,1}. Es decir V: E  {0,1}.
2
En otras palabras, una valuación le asignas valores de verdad a los bloques del conjunto
E, el cero siendo el valor de falso y el uno siendo el valor de verdadero. Ahora, es claro
que E es un subconjunto del conjunto de todas las formulas de L. A continuación se
*
extenderá la definición de valuación para todas la formulas y se denotara con V .
*
Definición 12.- Dada una valuación V, definimos su extensión V sobre todas las
formulas de L como:
V * ( )  V ( ) Si   E
V * ( )  1  V * ( )
V * (   )  Máximo {V * ( ), V * ( )}
V * (   )  Mínimo {V * ( ), V * ( )}
V * (   )  0 si V * ( )  1 y V * ( )  0
= 1 en otros casos
*
V (   )  0 si V * ( )  V * (  )
*
*
= 1 si V ( )  V ( )
3.0 Tautologías y Satisfacibilidad
Definición 13.- Decimos que una valuación V satisface a una formula  si y sólo si
V(  )=1.
Definición 14.- Decimos que  es una tautología si y sólo si toda valuación satisface a
 , y denotara como:
| T 
Definición 15.-  es consecuencia tautológica de  si y sólo si toda valuación que
satisface a
 | T 
 también satisface  , y se denotara como:
Observación.-  puede ser un conjunto de formulas, así que si tenemos que
 | T  y   { 1 ,....,  n } entonces { 1 ,....,  n } | T  .
Definición 14.- Sean  y  formulas de un lenguaje L, decimos que  y 
tautologicamente equivalentes, lo cual denotaremos como  T  si y sólo si
son
|T (   )
4.0 El Teorema de Sustitución en Tautologías
A1 ,...., Ai son los bloques de la
Si una fórmula  es tautología, | T  y
3
fórmula  y sean  1 ,....,  i fórmulas cualesquiera y sea ´ el resultado de sustituir  i
en  , entonces ´ también es tautología; | T ´
Demostración.- Sea V, cualquier valuación, entonces V (  )= 1, porque  es
A
V * ( i )  i  1, . . . n. ,
tautología. Sea V´ una valuación tal que V´ ( i ) =
. Esto
*
implica que V ´ ( ) =1, pero entonces
´
, esto se debe a que la valuación de
esta determinada por su
A
estructura y los valores de verdad de las i bajo la valuación, pero estos valores de
verdad y su estructura son exactamente las misma que las de la formula original  . Por
lo que vemos que:
V´ (
V
´
*
)=
V ´* ( )
(´)  1 y | T ´
Referencias
AMOR M., José Alfredo, “Lógica Proposicional dentro de la Lógica de premier orden”,
Serie: Notas de clase, vínculos matemáticos #113, Publicaciones del Departamento de
Matemáticas de la Facultad de Ciencias de la UNAM, México, 1993
_____, Compacidad en la Lógica de Primer Orden y su relación con el teorema de
completitud, Facultad de Ciencias UNAM, México 2006
BARNES W., Ronald y John Mack M., Una Introducción a la Lógica Matemática,
EUNIBAR, 1978
FERRATER Mora, José y Hugues Leblane, Lógica Matemática, FCE, México, 1975
4