Menu Close

Relaciones totales

Usando el tipo de las relaciones binarias, definir la función

   total :: Eq a => Rel a -> Bool

tal que total r se verifica si la relación r es total; es decir, si para cualquier par x, y de elementos del universo de r, se tiene que x está relacionado con y o y está relacionado con x. Por ejemplo,

   total (R ([1,3],[(1,1),(3,1),(3,3)]))  ==  True
   total (R ([1,3],[(1,1),(3,1)]))        ==  False
   total (R ([1,3],[(1,1),(3,3)]))        ==  False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck (quickCheck)
 
-- 1ª solución
-- ===========
 
total :: Eq a => Rel a -> Bool
total (R (u,g)) =
  and [(x,y) `elem` g || (y,x) `elem` g | x <- u, y <- u]
 
-- 2ª solución
-- ===========
 
total2 :: Eq a => Rel a -> Bool
total2 (R (u,g)) =
  all (relacionados g) (producto u u)
 
-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,
--    λ> producto [2,5] [1,4,6]
--    [(2,1),(2,4),(2,6),(5,1),(5,4),(5,6)]
producto :: [a] -> [a] -> [(a,a)]
producto xs ys =
  [(x,y) | x <- xs, y <- ys]
 
-- (relacionados g (x,y)) se verifica si los elementos x e y están
-- relacionados por la relación de grafo g. Por ejemplo,
--    relacionados [(2,3),(3,1)] (2,3)  ==  True
--    relacionados [(2,3),(3,1)] (3,2)  ==  True
--    relacionados [(2,3),(3,1)] (1,2)  ==  False
relacionados :: Eq a => [(a,a)] -> (a,a) -> Bool
relacionados g (x,y) =
  (x,y) `elem` g || (y,x) `elem` g
 
-- 3ª solución
-- ===========
 
total3 :: Eq a => Rel a -> Bool
total3 (R (u,g)) = aux1 u
  where aux1 []       = True
        aux1 (x:xs)   = aux2 x u && aux1 xs
        aux2 _ []     = True
        aux2 x (y:ys) = relacionados g (x,y) && aux2 x ys
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_total :: Rel Int -> Bool
prop_total r =
  all (== total r)
      [total2 r,
       total3 r]
 
-- La comprobación es
--    λ> quickCheck prop_total
--    +++ OK, passed 100 tests.


Soluciones en Python

from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.Relaciones_binarias import Rel, relacionArbitraria
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def total(r: Rel[A]) -> bool:
    (u, g) = r
    return all(((x, y) in g or (y, x) in g for x in u for y in u))
 
# 2ª solución
# ===========
 
# producto(xs, ys) es el producto cartesiano de xs e ys. Por ejemplo,
#    >>> producto([2, 5], [1, 4, 6])
#    [(2, 1), (2, 4), (2, 6), (5, 1), (5, 4), (5, 6)]
def producto(xs: list[A], ys: list[A]) -> list[tuple[A,A]]:
    return [(x, y) for x in xs for y in ys]
 
# relacionados(g, (x, y)) se verifica si los elementos x e y están
# relacionados por la relación de grafo g. Por ejemplo,
#    relacionados([(2, 3), (3, 1)], (2, 3))  ==  True
#    relacionados([(2, 3), (3, 1)], (3, 2))  ==  True
#    relacionados([(2, 3), (3, 1)], (1, 2))  ==  False
def relacionados(g: list[tuple[A,A]], p: tuple[A,A]) -> bool:
    (x, y) = p
    return (x, y) in g or (y, x) in g
 
def total2(r: Rel[A]) -> bool:
    (u, g) = r
    return all(relacionados(g, p) for p in producto(u, u))
 
# 3ª solución
# ===========
 
def total3(r: Rel[A]) -> bool:
    u, g = r
    return all(relacionados(g, (x, y)) for x in u for y in u)
 
# 4ª solución
# ===========
 
def total4(r: Rel[A]) -> bool:
    (u, g) = r
    def aux2(x: A, ys: list[A]) -> bool:
        if not ys:
            return True
        return relacionados(g, (x, ys[0])) and aux2(x, ys[1:])
 
    def aux1(xs: list[A]) -> bool:
        if not xs:
            return True
        return aux2(xs[0], u) and aux1(xs[1:])
 
    return aux1(u)
 
# 5ª solución
# ===========
 
def total5(r: Rel[A]) -> bool:
    (u, g) = r
    for x in u:
        for y in u:
            if not relacionados(g, (x, y)):
                return False
    return True
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_total(n: int) -> None:
    r = relacionArbitraria(n)
    res = total(r)
    assert total2(r) == res
    assert total3(r) == res
    assert total4(r) == res
    assert total5(r) == res
 
# La comprobación es
#    > poetry run pytest -q Relaciones_totales.py
#    1 passed in 0.11s

Relaciones antisimétricas

Usando el tipo de las relaciones binarias, definir la función

   antisimetrica :: Eq a => Rel a -> Bool

tal que antisimetrica r se verifica si la relación r es antisimétrica; es decir, si (x,y) e (y,x) están relacionado, entonces x=y. Por ejemplo,

   antisimetrica (R ([1,2],[(1,2)]))        ==  True
   antisimetrica (R ([1,2],[(1,2),(2,1)]))  ==  False
   antisimetrica (R ([1,2],[(1,1),(2,1)]))  ==  True

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
antisimetrica :: Eq a => Rel a -> Bool
antisimetrica (R (_,g)) =
  null [(x,y) | (x,y) <- g, x /= y, (y,x) `elem` g]
 
-- 2ª solución
-- ===========
 
antisimetrica2 :: Eq a => Rel a -> Bool
antisimetrica2 (R (_,g)) =
  and [(y,x) `notElem` g | (x,y) <- g, x /= y]
 
 
-- 3ª solución
-- ===========
 
antisimetrica3 :: Eq a => Rel a -> Bool
antisimetrica3 (R (_,g)) =
  all (\(x, y) -> (y,x) `notElem` g || x == y) g
 
 
-- 4ª solución
-- ===========
 
antisimetrica4 :: Eq a => Rel a -> Bool
antisimetrica4 (R (u,g)) =
  and [((x,y) `elem` g && (y,x) `elem` g) --> (x == y)
       | x <- u, y <- u]
  where p --> q = not p || q
 
-- 5ª solución
-- ===========
 
antisimetrica5 :: Eq a => Rel a -> Bool
antisimetrica5 (R (_,g)) = aux g
  where aux []         = True
        aux ((x,y):g') = ((y,x) `notElem` g || x == y) && aux g'
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_antisimetrica :: Rel Int -> Bool
prop_antisimetrica r =
  all (== antisimetrica r)
      [antisimetrica2 r,
       antisimetrica3 r,
       antisimetrica4 r,
       antisimetrica5 r]
 
-- La comprobación es
--    λ> quickCheck prop_antisimetrica
--    +++ OK, passed 100 tests.


Soluciones en Python

from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.Relaciones_binarias import Rel, relacionArbitraria
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def antisimetrica(r: Rel[A]) -> bool:
    (u, g) = r
    return [(x, y) for (x, y) in g if x != y and (y, x) in g] == []
 
# 2ª solución
# ===========
 
def antisimetrica2(r: Rel[A]) -> bool:
    (u, g) = r
    return all(((y, x) not in g for (x, y) in g if x != y))
 
# 3ª solución
# ===========
 
def antisimetrica3(r: Rel[A]) -> bool:
    (u, g) = r
    return all ((not ((x, y) in g and (y, x) in g) or x == y
                 for x in u for y in u))
 
# 4ª solución
# ===========
 
def antisimetrica4(r: Rel[A]) -> bool:
    (u, g) = r
    def aux(xys: list[tuple[A, A]]) -> bool:
        if not xys:
            return True
        (x, y) = xys[0]
        return ((y, x) not in g or x == y) and aux(xys[1:])
 
    return aux(g)
 
# 5ª solución
# ===========
 
def antisimetrica5(r: Rel[A]) -> bool:
    (u, g) = r
    for (x, y) in g:
        if (y, x) in g and x != y:
            return False
    return True
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_antisimetrica(n: int) -> None:
    r = relacionArbitraria(n)
    res = antisimetrica(r)
    assert antisimetrica2(r) == res
    assert antisimetrica3(r) == res
    assert antisimetrica4(r) == res
    assert antisimetrica5(r) == res
 
# La comprobación es
#    > poetry run pytest -q Relaciones_antisimetricas.py
#    1 passed in 0.13s

Relaciones irreflexivas

Usando el tipo de las relaciones binarias, definir la función

   irreflexiva :: Eq a => Rel a -> Bool

tal que irreflexiva r se verifica si la relación r es irreflexiva; es decir, si ningún elemento de su universo está relacionado con él mismo. Por ejemplo,

   irreflexiva (R ([1,2,3],[(1,2),(2,1),(2,3)]))  ==  True
   irreflexiva (R ([1,2,3],[(1,2),(2,1),(3,3)]))  ==  False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
irreflexiva :: Eq a => Rel a -> Bool
irreflexiva (R (u,g)) = and [(x,x) `notElem` g | x <- u]
 
-- 2ª solución
-- ===========
 
irreflexiva2 :: Eq a => Rel a -> Bool
irreflexiva2 (R(u,g)) = all (\x -> (x,x) `notElem` g) u
 
-- 3ª solución
-- ===========
 
irreflexiva3 :: Eq a => Rel a -> Bool
irreflexiva3 (R(u,g)) = aux u
  where aux []     = True
        aux (x:xs) = (x,x) `notElem` g && aux xs
 
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_irreflexiva :: Rel Int -> Bool
prop_irreflexiva r =
  all (== irreflexiva r)
      [irreflexiva2 r,
       irreflexiva3 r]
 
-- La comprobación es
--    λ> quickCheck prop_irreflexiva
--    +++ OK, passed 100 tests.


Soluciones en Python

from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.Relaciones_binarias import Rel, relacionArbitraria
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def irreflexiva(r: Rel[A]) -> bool:
    (u, g) = r
    return all(((x, x) not in g for x in u))
 
# 2ª solución
# ===========
 
def irreflexiva2(r: Rel[A]) -> bool:
    (u, g) = r
    def aux(xs: list[A]) -> bool:
        if not xs:
            return True
        return (xs[0], xs[0]) not in g and aux(xs[1:])
 
    return aux(u)
 
# 3ª solución
# ===========
 
def irreflexiva3(r: Rel[A]) -> bool:
    (u, g) = r
    for x in u:
        if (x, x) in g:
            return False
    return True
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_irreflexiva(n: int) -> None:
    r = relacionArbitraria(n)
    res = irreflexiva(r)
    assert irreflexiva2(r) == res
    assert irreflexiva3(r) == res
 
# La comprobación es
#    > poetry run pytest -q Relaciones_irreflexivas.py
#    1 passed in 0.12s

Relaciones de equivalencia

Usando el tipo de las relaciones binarias, definir la función

   esEquivalencia :: Ord a => Rel a -> Bool

tal que esEquivalencia r se verifica si la relación r es de equivalencia. Por ejemplo,

   λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))
   True
   λ> esEquivalencia (R ([1,2,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))
   False
   λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,3),(5,5)]))
   False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Relaciones_reflexivas (reflexiva)
import Relaciones_simetricas (simetrica)
import Relaciones_transitivas (transitiva)
 
esEquivalencia :: Ord a => Rel a -> Bool
esEquivalencia r = reflexiva r && simetrica r && transitiva r


Soluciones en Python

from typing import TypeVar
 
from src.Relaciones_binarias import Rel, relacionArbitraria
from src.Relaciones_reflexivas import reflexiva
from src.Relaciones_simetricas import simetrica
from src.Relaciones_transitivas import transitiva
 
A = TypeVar('A')
 
def esEquivalencia(r: Rel[A]) -> bool:
    return reflexiva(r) and simetrica(r) and transitiva(r)

Relaciones transitivas

Usando el tipo de las relaciones binarias, definir la función

   transitiva :: Ord a => Rel a -> Bool

tal que transitiva r se verifica si la relación r es transitiva. Por ejemplo,

   transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) == True
   transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(5,5)]))       == False

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Reconocimiento_de_subconjunto (subconjunto)
import Universo_y_grafo_de_una_relacion_binaria (grafo)
import Composicion_de_relaciones_binarias_v2 (composicion)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
transitiva1 :: Ord a => Rel a -> Bool
transitiva1 r@(R (_,g)) = subconjunto (grafo (composicion r r)) g
 
-- La función subconjunto está definida en el ejercicio
-- "Reconocimiento de subconjunto" que se encuentra en
-- https://bit.ly/427Tyeq
--
-- La función grafo está definida en el ejercicio
-- "Universo y grafo de una relación binaria" que se encuentra en
-- https://bit.ly/3J35mpC
--
-- La función composición está definida en el ejercicio
-- "Composición de relaciones binarias" que se encuentra en
-- https://bit.ly/3JyJrs7
 
-- 2ª solución
-- ===========
 
transitiva2 :: Ord a => Rel a -> Bool
transitiva2 (R (_,g)) = aux g
  where
    aux [] = True
    aux ((x,y):g') = and [(x,z) `elem` g | (u,z) <- g, u == y] && aux g'
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_transitiva :: Rel Int -> Bool
prop_transitiva r =
  transitiva1 r == transitiva2 r
 
-- La comprobación es
--    λ> quickCheck prop_transitiva
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> transitiva1 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))
--    False
--    (3.15 secs, 898,932,776 bytes)
--    λ> transitiva2 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))
--    False
--    (0.01 secs, 1,396,720 bytes)
--
--    λ> transitiva1 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))
--    True
--    (2.71 secs, 852,578,456 bytes)
--    λ> transitiva2 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))
--    True
--    (9.13 secs, 777,080,288 bytes)
 
-- En lo sucesivo, usaremos la 1ª definición
transitiva :: Ord a => Rel a -> Bool
transitiva = transitiva1


Soluciones en Python

from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar
 
from hypothesis import given
from hypothesis import strategies as st
 
from src.Composicion_de_relaciones_binarias_v2 import composicion
from src.Reconocimiento_de_subconjunto import subconjunto
from src.Relaciones_binarias import Rel, relacionArbitraria
from src.Universo_y_grafo_de_una_relacion_binaria import grafo
 
setrecursionlimit(10**6)
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def transitiva1(r: Rel[A]) -> bool:
    g = grafo(r)
    return subconjunto(grafo(composicion(r, r)), g)
 
# La función subconjunto está definida en el ejercicio
# "Reconocimiento de subconjunto" que se encuentra en
# https://bit.ly/427Tyeq
#
# La función grafo está definida en el ejercicio
# "Universo y grafo de una relación binaria" que se encuentra en
# https://bit.ly/3J35mpC
#
# La función composición está definida en el ejercicio
# "Composición de relaciones binarias" que se encuentra en
# https://bit.ly/3JyJrs7
 
# 2ª solución
# ===========
 
def transitiva2(r: Rel[A]) -> bool:
    g = grafo(r)
    def aux(g1: list[tuple[A,A]]) -> bool:
        if not g1:
            return True
        (x, y) = g1[0]
        return all(((x, z) in g for (u,z) in g if u == y)) and aux(g1[1:])
 
    return aux(g)
 
# 3ª solución
# ===========
 
def transitiva3(r: Rel[A]) -> bool:
    g = grafo(r)
    g1 = list(g)
    for (x, y) in g1:
        if not all(((x, z) in g for (u,z) in g if u == y)):
            return False
    return True
 
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_simetrica(n: int) -> None:
    r = relacionArbitraria(n)
    res = transitiva1(r)
    assert transitiva2(r) == res
    assert transitiva3(r) == res
 
# La comprobación es
#    > poetry run pytest -q Relaciones_transitivas.py
#    1 passed in 0.12s
 
# Comparación de eficiencia
# =========================
 
def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")
 
# La comparación es
#    >>> u1 = range(6001)
#    >>> g1 = [(x, x+1) for x in range(6000)]
#    >>> tiempo("transitiva1((u1, g1))")
#    1.04 segundos
#    >>> tiempo("transitiva2((u1, g1))")
#    0.00 segundos
#    >>> tiempo("transitiva3((u1, g1))")
#    0.00 segundos
#
#    >>> u2 = range(60)
#    >>> g2 = [(x, y) for x in u2 for y in u2]
#    >>> tiempo("transitiva1((u2, g2))")
#    0.42 segundos
#    >>> tiempo("transitiva2((u2, g2))")
#    5.24 segundos
#    >>> tiempo("transitiva3((u2, g2))")
#    4.83 segundos
 
# En lo sucesivo usaremos la 1ª definición
transitiva = transitiva1