Relaciones binarias – Exercitium

Clausura transitiva

José A. Alonso, 14-abril-2023, Haskell y Python

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

   clausuraTransitiva :: Eq a => Rel a -> Rel a

tal que clausuraTransitiva r es la clausura transitiva de r; es decir, la menor relación transitiva que contiene a r. Por ejemplo,

   λ> clausuraTransitiva (R ([1..6],[(1,2),(2,5),(5,6)]))
   R ([1,2,3,4,5,6],[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)])

Comprobar con QuickCheck que clausuraTransitiva es transitiva.

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_transitivas (transitiva)
import Data.List (union)
import Test.QuickCheck
 
--  1ª solución
--  ===========
 
clausuraTransitiva :: Ord a => Rel a -> Rel a
clausuraTransitiva (R (u,g)) = R (u, aux g)
  where
    aux u' | cerradoTr u' = u'
           | otherwise    = aux (u' `union` comp u' u')
    cerradoTr r       = subconjunto (comp r r) r
    comp r s          = [(x,z) | (x,y) <- r, (y',z) <- s, y == y']
    subconjunto xs ys = all (`elem` ys) xs
 
-- 2ª solución
-- ===========
 
clausuraTransitiva2 :: Ord a => Rel a -> Rel a
clausuraTransitiva2 (R (u,g)) =
  R (u, until cerradoTr (\r -> r `union` comp r r) g)
  where
    cerradoTr r       = subconjunto (comp r r) r
    comp r s          = [(x,z) | (x,y) <- r, (y',z) <- s, y == y']
    subconjunto xs ys = all (`elem` ys) xs
 
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_clausuraTransitiva :: Rel Int -> Bool
prop_clausuraTransitiva r =
  clausuraTransitiva r == clausuraTransitiva2 r
 
-- La comprobación es
--    λ> quickCheck prop_clausuraTransitiva
--    +++ OK, passed 100 tests.
 
-- Propiedad
-- =========
 
-- La propiedad es
prop_clausuraTransitivaEsTransitiva :: Rel Int -> Bool
prop_clausuraTransitivaEsTransitiva r =
  transitiva (clausuraTransitiva r)
 
-- La función transitiva está definida en el ejercicio
-- "Relaciones transitivas" que se encuentra en
-- https://bit.ly/42WRPJv
 
-- La comprobación es
--    λ> quickCheck prop_clausuraTransitivaEsTransitiva
--    +++ 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
from src.Relaciones_transitivas import transitiva
 
A = TypeVar('A')
 
# 1ª solución
# ===========
 
def clausuraTransitiva(r: Rel[A]) -> Rel[A]:
    (u, g) = r
 
    def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool:
        return set(xs) <= set(ys)
 
    def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]:
        return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1})
 
    def cerradoTr(r: list[tuple[A, A]]) -> bool:
        return subconjunto(comp(r, r), r)
 
    def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]:
        return xs + [y for y in ys if y not in xs]
 
    def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]:
        if cerradoTr(u1):
            return u1
        return aux(union(u1, comp(u1, u1)))
 
    return (u, aux(g))
 
# 2ª solución
# ===========
 
def clausuraTransitiva2(r: Rel[A]) -> Rel[A]:
    (u, g) = r
 
    def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool:
        return set(xs) <= set(ys)
 
    def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]:
        return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1})
 
    def cerradoTr(r: list[tuple[A, A]]) -> bool:
        return subconjunto(comp(r, r), r)
 
    def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]:
        return xs + [y for y in ys if y not in xs]
 
    def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]:
        if cerradoTr(u1):
            return u1
        return aux(union(u1, comp(u1, u1)))
 
    g1: list[tuple[A, A]] = g
    while not cerradoTr(g1):
        g1 = union(g1, comp(g1, g1))
    return (u, g1)
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_clausuraTransitiva(n: int) -> None:
    r = relacionArbitraria(n)
    assert clausuraTransitiva(r) == clausuraTransitiva2(r)
 
# Propiedad
# =========
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_cla(n: int) -> None:
    r = relacionArbitraria(n)
    assert transitiva(clausuraTransitiva(r))
 
# La función transitiva está definida en el ejercicio
# "Relaciones transitivas" que se encuentra en
# https://bit.ly/42WRPJv
 
# La comprobación es
#    > poetry run pytest -q Clausura_transitiva.py
#    2 passed in 0.16s

from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria from src.Relaciones_transitivas import transitiva A = TypeVar('A') # 1ª solución # =========== def clausuraTransitiva(r: Rel[A]) -> Rel[A]: (u, g) = r def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool: return set(xs) <= set(ys) def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]: return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1}) def cerradoTr(r: list[tuple[A, A]]) -> bool: return subconjunto(comp(r, r), r) def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]: return xs + [y for y in ys if y not in xs] def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]: if cerradoTr(u1): return u1 return aux(union(u1, comp(u1, u1))) return (u, aux(g)) # 2ª solución # =========== def clausuraTransitiva2(r: Rel[A]) -> Rel[A]: (u, g) = r def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool: return set(xs) <= set(ys) def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]: return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1}) def cerradoTr(r: list[tuple[A, A]]) -> bool: return subconjunto(comp(r, r), r) def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]: return xs + [y for y in ys if y not in xs] def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]: if cerradoTr(u1): return u1 return aux(union(u1, comp(u1, u1))) g1: list[tuple[A, A]] = g while not cerradoTr(g1): g1 = union(g1, comp(g1, g1)) return (u, g1) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_clausuraTransitiva(n: int) -> None: r = relacionArbitraria(n) assert clausuraTransitiva(r) == clausuraTransitiva2(r) # Propiedad # ========= # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_cla(n: int) -> None: r = relacionArbitraria(n) assert transitiva(clausuraTransitiva(r)) # La función transitiva está definida en el ejercicio # "Relaciones transitivas" que se encuentra en # https://bit.ly/42WRPJv # La comprobación es # > poetry run pytest -q Clausura_transitiva.py # 2 passed in 0.16s

Leer más →

Clausura simétrica

José A. Alonso, 13-abril-2023, Haskell y Python

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

   clausuraSimetrica :: Eq a => Rel a -> Rel a

tal que clausuraSimetrica r es la clausura simétrica de r; es decir, la menor relación simétrica que contiene a r. Por ejemplo,

   λ> clausuraSimetrica (R ([1,3,5],[(1,1),(3,1),(1,5)]))
   R ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)])

Comprobar con QuickCheck que clausuraSimetrica es simétrica.

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Data.List (union)
import Relaciones_simetricas (simetrica)
import Test.QuickCheck
 
clausuraSimetrica :: Eq a => Rel a -> Rel a
clausuraSimetrica (R (u,g)) =
  R (u, g `union` [(y,x) | (x,y) <- g])
 
-- La propiedad es
prop_ClausuraSimetrica :: Rel Int -> Bool
prop_ClausuraSimetrica r =
  simetrica (clausuraSimetrica r)
 
-- La función simetrica está definida en el ejercicio
-- "Relaciones simétricas" que se encuentra en
-- https://bit.ly/3zlO2rH
 
-- La comprobación es
--    λ> quickCheck prop_ClausuraSimetrica
--    +++ 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
from src.Relaciones_simetricas import simetrica
 
A = TypeVar('A')
 
def clausuraSimetrica(r: Rel[A]) -> Rel[A]:
    (u, g) = r
    return (u, list(set(g) | {(y, x) for (x,y) in g}))
 
# 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)
    assert simetrica(clausuraSimetrica(r))
 
# La función simetrica está definida en el ejercicio
# "Relaciones simétricas" que se encuentra en
# https://bit.ly/3zlO2rH
 
# La comprobación es
#    > poetry run pytest -q Clausura_simetrica.py
#    1 passed in 0.12s

Leer más →

Clausura reflexiva

José A. Alonso, 12-abril-2023, Haskell y Python

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

   clausuraReflexiva :: Eq a => Rel a -> Rel a

tal que clausuraReflexiva r es la clausura reflexiva de r; es decir, la menor relación reflexiva que contiene a r. Por ejemplo,

   λ> clausuraReflexiva (R ([1,3],[(1,1),(3,1)]))
   R ([1,3],[(1,1),(3,1),(3,3)])

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Data.List (union)
import Test.QuickCheck (quickCheck)
 
clausuraReflexiva :: Eq a => Rel a -> Rel a
clausuraReflexiva (R (u,g)) =
  R (u, g `union` [(x,x) | x <- u])

Soluciones en Python

from typing import TypeVar
 
from src.Relaciones_binarias import Rel
 
A = TypeVar('A')
 
def clausuraReflexiva(r: Rel[A]) -> Rel[A]:
    (u, g) = r
    return (u, list(set(g) | {(x, x) for x in u}))

Leer más →

Relaciones totales

José A. Alonso, 11-abril-2023, Haskell y Python

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

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

Leer más →

Relaciones antisimétricas

José A. Alonso, 10-abril-2023, Haskell y Python

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

Leer más →

Etiqueta: Relaciones binarias

Clausura transitiva

Clausura simétrica

Clausura reflexiva

Relaciones totales

Relaciones antisimétricas

Subscribe to Blog via Email

Entradas recientes

Etiquetas