Download José Alfredo Cervantes Guzmán (UMSNH / Fac. de C

IX Encuentro Internacional de Didáctica de
la Lógica
Lógica de las Relaciones
José Alfredo Cervantes Guzmán
UMSNH
Coautor: Jesús Rivera
Algebra de Relaciones

¿Qué es una Relación?
Podemos entender de manera intuitiva a una relación como una propiedad que liga un
elemento a con otro elemento b

Algunas Operaciones Fundamentales
Inclusión:
R  S  def.( x)( y )( xRy  xSy).
Identidad:
R  S  def. ( x)( y )( xRy  xSy).
Suma:
R  S  def. xˆ yˆ ( xRy  xSy)
Producto:
R  S  def. xˆ yˆ ( xRy  xSy)
Complemento:
R  def. xˆ ŷ ( xRy)
Relación Universal:
V  def. x̂ ŷ ( x  x  y  y)
Relación Nula:
  def. x̂ ŷ ( x  x  y  y)


Algunas Leyes del Algebra de Relaciones:
R1 : R  R

R2 : (R  R )  
R3 : ( R  R )  V
R4 : R  R
 R
R5 : 
R6 : R  V
R7 : ( R  R)  R
R8 : ( R  R)  R
R10a : ( R  S )  R
R10b : ( R  S )  R
R12 : ( R  S )  ( S  R)
R13 : ( R  S )  ( S  R )
R15a : ( R  S )  ( R  S )
R15b : ( R  S )  ( R  S )
R19 : ( R  S )  ( S  R )
R 20 : ( R  S )  ( R  S )
R 21 : ( R  S )  (( R  S )  ( S  R ))
  V
R 22 : 

R 23 : V  

R 24 : V  
R 25 : ( R  V )  R
 

R 26 : ( R  
) R
R 27 : ( R  
R 28 : ( R  V )  V

Propiedades de las Relaciones
Reflexiva.-
( x)( xRx)
Irreflexiva.-
( x)( xRx)
No Reflexiva.-
( x)( xRx)  ( x)( xRx)
Simetría.-
( x)( y )( xRy  yRx )
Asimetría.-
( x)( y )( xRy  ( yRx ))
No Simétrica.-
( x)( y)( xRy  yRx )  ( x)( y)( xRy  ( yRx ))
Transitiva.-
( x)( y )( z )(( xRy  yRz )  xRz)
Intransitiva.-
( x)( y )( z )(( xRy  yRz )  ( xRz))
No Transitiva.-
( x)( y)( z)(( xRy  yRz )  xRz)  ( x)( y)( z)(( xRy  yRz )  ( xRz))

Funciones
En un esquema relacional “xRy” llamaremos a x relacionante y a y relacionado.
Estableceremos tres clases de relaciones:

Relaciones de uno a muchos o aquellas en las cuales todo y cada uno de los
relacionados de una relación R tiene exactamente un relacionante.

Relaciones de muchos a uno o aquellas en las cuales todos y cada uno de los
relacionantes de una relación R tiene exactamente un relacionado.

Relaciones de uno a uno o aquellas en las cuales todos y cada uno de los
relacionantes de una relación R tienen exactamente un relacionado, y todos y
cada uno de los relacionados de la misma relación R tienen exactamente un
relacionante.
Las funciones son relaciones de muchos a uno y de uno a uno. Las funciones
constituyen, un tipo especial de relaciones.
¿Estructura?
A
I
A
Relaciones entre la Lógica Proposicional
y la Lógica de Primer Orden.
Lenguaje de primer orden L, de un tipo dado. El tipo consta de los símbolos de
predicado, de función y de constante y el resto de los símbolos son comunes a
cualquier lenguaje de primer orden y son:
a) Variables:
x , x , x ,...

0
b) Cuantificadores:
1
2
, .
c) Símbolos de Igualdad:

d) Conectivos:
, , , , 
e) Auxiliares:
), (, '.
Estructuras Algebraico-Relacionales de un tipo dado.
Aquí el tipo corresponde al tipo de lenguaje del cual la estructura es interpretación.
Las denotaremos con las letras A, B, C, etc.; y respectivamente con las letras
latinas A, B, C, etc., a sus universos.

La estructura A es una cuarteta

A  , ,  ,  
Interpretación de términos. Si t es un término del lenguaje L y A es una
estructura interpretación para L y S es una sucesión de elementos de su
universo A, denotamos con t A s la interpretación del termino t en la
estructura con la sucesión de S.


Satisfacción de fórmulas. Si  es una fórmula del lenguaje L, A es una
interpretación para L y S una sucesión de elementos de A, denotamos A  [ s ]
para abreviar que la fórmula  es satisfecha por la sucesión S en la estructura
A.




Verdad de Tarski. Si es fórmula de L y A es una interpretación para L. con A  
denotamos que  es verdadera en A o que A es modelo de  ; es decir que para
toda sucesión S de elementos de A, A  [ s ]
Verdad universal. Si  es fórmula de L. Con   denotamos que  es
universalmente válida, es decir, que para toda interpretación A de L, A   .
Es decir, es verdadera en toda interpretación de L.
Consecuencia lógica. Si  es un conjunto de fórmulas de L y  es una fórmula
de L, con    denotamos que  es consecuencia lógica de  ; es decir,
que para toda interpretación A de L y toda sucesión S de elementos de A, se
cumple lo siguiente: si A   [s ] para toda    , entonces A  [ s ] .
Satisfacibilidad. Si  es un conjunto de fórmulas de L decimos que
es

satisfacible, si hay una interpretación A de L y una sucesión S de elementos de
A, tales que para toda   , entonces A   [s ].
Consideremos a L un lenguaje de primer orden, fijo pero arbitrario; es decir, están
dados los predicados, los símbolos de función y las constantes.
Una fórmula  de L se llama un bloque si  es una fórmula atómica o es una
cuantificación.
Ejemplos de bloques:
1)Si P es un predicado de n argumentos y t1 ,..., t n son términos, P(t1 ,..., t n )
Es un bloque ya que es una fórmula atómica.
2) x( Px  Qx ) Es una cuantificación.
x( Px)  Qx No es un bloque debido hay que hay variables libres.

Sea E el conjunto de todos los bloques de L.
 Una expresión es una sucesión de símbolos de L.
 Una Proposición se define como:
1)Los bloques son proposiciones
2)Si  ,  son proposiciones, entonces ( ), (   ), (   ), (   ), (   ),
Son proposiciones.
3) Una expresión es una proposición sólo si lo es con base en 1) y 2)


Teorema 1 Para cualquier expresión  :
 es una fórmula
 es una proposición


Una valuación es una función v definida sobre el conjunto E y con valores en
{0,1}. Es decir v : E  {0,1}

Dada una valuación v, definimos su extensión v* sobre todas las fórmulas de
L, como:
v* ( )  v( ) si   E
v* ( )  1  v* ( )
v* (   )  máximo v* ( ), v* (  )
v* (   )  minimo v* ( ), v* (  )
0 si v* ( )  1 y v* (  )  0
v (   ) 
1 en otro caso
0 si v* ( )  v* (  )
*
v (   ) 
1 si v* ( )  v* (  )
*
Dada una interpretación para L: una estructura A y dada una sucesión S de
elementos de A, definimos la valuación asociada

v As : E  {0,1} tal que para todo bloque P:
1 si A P[ s]
v As(P) 
0 si A /  P[s]
Es decir:
v As (P)  1 sii A
Lema Sea  fórmula cualquiera, A interpretación para L y S una sucesión de
elementos de A. Entonces:

v
P[s]
*
As
( )  1 sii A
 [s]
()

Teorema Principal: Toda Tautología es Universalmente
  , pero no
válida. Es decir si
T  , entonces
inversamente.
Demostración:
/   , entonces hay A, S tales que
Sea  . Supongamos que
*
A
/  [ s ] entonces por Lema, v As ( )  0 de donde 
no es tautología.
Contraejemplos para el inverso:
(x P( x)
x (x  x)
P(c))
pero
pero
/ T  (x P( x)  P(c)).
/ T  x (x  x ).
Conclusión


La comprensión de la Lógica de Relaciones es
fundamental para profundizar en los estudios de Lógica a
nivel medio y superior. Ya que permite conectar con
conceptos vitales de la matemática, tales como las
relaciones de orden y la noción de función, proponiendo un
tratamiento alternativo ya que generalmente se reduce el
estudio de las funciones a sus aspectos numéricos
olvidando la estructura asociada a ella.
Si nos fijamos más en las estructuras tendremos la
posibilidad de encontrar similitudes entre distintas
relaciones que aparentemente no tienen que ver entre sí,
llegando en el caso finito a entender de manera clara la
noción de relación isomorfica a través de la representación
grafica de la relación..
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, 1993.Publicaciones del
Departamento de Matematicas de la Facultad de
Ciencias de la UNAM.
Ferrater Mora, José. Leblane, Hugues. Lógica
Matemática. Fondo de Cultura Económica. 1975.
Amor. M, José Alfredo. Compacidad en la Lógica de
Primer Orden y su relación con el teorema de
completitud. Facultad de Ciencias UNAM, 2006