Relaciones binarias

Clausura transitiva

PorJosé A. Alonso 14-abril-202314-abril-2023

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

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

1	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)])

1 2	λ> 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.

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

Clausura simétrica

PorJosé A. Alonso 13-abril-202330-marzo-2023

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

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

1	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)])

1 2	λ> 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.

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

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

Clausura reflexiva

PorJosé A. Alonso 12-abril-202329-marzo-2023

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

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

1	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)])

1 2	λ> 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])

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}))

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}))

Relaciones totales

PorJosé A. Alonso 11-abril-202323-marzo-2023

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

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

1	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

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.

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

Relaciones antisimétricas

PorJosé A. Alonso 10-abril-202322-marzo-2023

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

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

1	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

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.

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

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

PorJosé A. Alonso 7-abril-202318-marzo-2023

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

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

1	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

1 2	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.

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

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

PorJosé A. Alonso 6-abril-202318-marzo-2023

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

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

1	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

λ> 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

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)

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

PorJosé A. Alonso 5-abril-202313-marzo-2023

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

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

1	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

1 2	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

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

100

101

102

103

104

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

Composición de relaciones binarias

PorJosé A. Alonso 3-abril-202311-marzo-2023

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

   composicion :: Eq a => Rel a -> Rel a -> Rel a

1	composicion :: Eq a => Rel a -> Rel a -> Rel a

tal que composicion r s es la composición de las relaciones r y s. Por ejemplo,

   λ> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)]))
   R ([1,2],[(1,1),(2,1)])

1 2	λ> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)])) R ([1,2],[(1,1),(2,1)])

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
-- ===========

composicion :: Eq a => Rel a -> Rel a -> Rel a
composicion (R (u1,g1)) (R (_,g2)) =
  R (u1,[(x,z) | (x,y) <- g1, (y',z) <- g2, y == y'])

-- 2ª solución
-- ===========

composicion2 :: Eq a => Rel a -> Rel a -> Rel a
composicion2 (R (u1,g1)) (R (_,g2)) =
  R (u1, aux g1)
  where aux [] = []
        aux ((x,y):g1') = [(x,z) | (y',z) <- g2, y == y'] ++ aux g1'

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_composicion :: Rel Int -> Rel Int -> Bool
prop_composicion r1 r2 =
  composicion r1 r2 == composicion2 r1 r2

-- La comprobación es
--    λ> quickCheck prop_composicion
--    +++ OK, passed 100 tests.

import Relaciones_binarias (Rel(R))

import Test.QuickCheck

-- 1ª solución

-- ===========

composicion :: Eq a => Rel a -> Rel a -> Rel a

composicion (R (u1,g1)) (R (_,g2)) =

R (u1,[(x,z) | (x,y) <- g1, (y',z) <- g2, y == y'])

-- 2ª solución

-- ===========

composicion2 :: Eq a => Rel a -> Rel a -> Rel a

composicion2 (R (u1,g1)) (R (_,g2)) =

R (u1, aux g1)

where aux [] = []

aux ((x,y):g1') = [(x,z) | (y',z) <- g2, y == y'] ++ aux g1'

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_composicion :: Rel Int -> Rel Int -> Bool

prop_composicion r1 r2 =

composicion r1 r2 == composicion2 r1 r2

-- La comprobación es

-- λ> quickCheck prop_composicion

-- +++ 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 composicion(r1: Rel[A], r2: Rel[A]) -> Rel[A]:
    (u1, g1) = r1
    (_,  g2) = r2
    return (u1, [(x, z) for (x, y) in g1 for (u, z) in g2 if y == u])

# 2ª solución
# ===========

def composicion2(r1: Rel[A], r2: Rel[A]) -> Rel[A]:
    (u1, g1) = r1
    (_,  g2) = r2
    def aux(g: list[tuple[A, A]]) -> list[tuple[A, A]]:
        if not g:
            return []
        (x, y) = g[0]
        return [(x, z) for (u, z) in g2 if y == u] + aux(g[1:])

    return (u1, aux(g1))

# 2ª solución
# ===========

def composicion3(r1: Rel[A], r2: Rel[A]) -> Rel[A]:
    (u1, g1) = r1
    (_,  g2) = r2
    r: list[tuple[A, A]] = []
    for (x, y) in g1:
        r = r + [(x, z) for (u, z) in g2 if y == u]
    return (u1, r)

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=0, max_value=10),
       st.integers(min_value=0, max_value=10))
def test_simetrica(n: int, m: int) -> None:
    r1 = relacionArbitraria(n)
    r2 = relacionArbitraria(m)
    res = composicion(r1, r2)
    assert composicion2(r1, r2) == res
    assert composicion2(r1, r2) == res

# La comprobación es
#    > poetry run pytest -q Composicion_de_relaciones_binarias_v2.py
#    1 passed in 0.19s

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 composicion(r1: Rel[A], r2: Rel[A]) -> Rel[A]:

(u1, g1) = r1

(_, g2) = r2

return (u1, [(x, z) for (x, y) in g1 for (u, z) in g2 if y == u])

# 2ª solución

# ===========

def composicion2(r1: Rel[A], r2: Rel[A]) -> Rel[A]:

(u1, g1) = r1

(_, g2) = r2

def aux(g: list[tuple[A, A]]) -> list[tuple[A, A]]:

if not g:

return []

(x, y) = g[0]

return [(x, z) for (u, z) in g2 if y == u] + aux(g[1:])

return (u1, aux(g1))

# 2ª solución

# ===========

def composicion3(r1: Rel[A], r2: Rel[A]) -> Rel[A]:

(u1, g1) = r1

(_, g2) = r2

r: list[tuple[A, A]] = []

for (x, y) in g1:

r = r + [(x, z) for (u, z) in g2 if y == u]

return (u1, r)

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=0, max_value=10),

st.integers(min_value=0, max_value=10))

def test_simetrica(n: int, m: int) -> None:

r1 = relacionArbitraria(n)

r2 = relacionArbitraria(m)

res = composicion(r1, r2)

assert composicion2(r1, r2) == res

# La comprobación es

# > poetry run pytest -q Composicion_de_relaciones_binarias_v2.py

# 1 passed in 0.19s

Relaciones simétricas

PorJosé A. Alonso 31-marzo-202310-marzo-2023

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

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

1	simetrica :: Eq a => Rel a -> Bool

tal que simetrica r se verifica si la relación r es simétrica. Por ejemplo,

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

simetrica (R ([1,3],[(1,1),(1,3),(3,1)])) == True

simetrica (R ([1,3],[(1,1),(1,3),(3,2)])) == False

simetrica (R ([1,3],[])) == 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
-- ===========

simetrica :: Eq a => Rel a -> Bool
simetrica (R (_,g)) = and [(y,x) `elem` g | (x,y) <- g]

-- 2ª solución
-- ===========

simetrica2 :: Eq a => Rel a -> Bool
simetrica2 (R (_,g)) = all (\(x,y) -> (y,x) `elem` g) g

-- 3ª solución
-- ===========

simetrica3 :: Eq a => Rel a -> Bool
simetrica3 (R (_,g)) = aux g
  where aux [] = True
        aux ((x,y):ps) = (y,x) `elem` g && aux ps

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_simetrica :: Rel Int -> Bool
prop_simetrica r =
  all (== simetrica r)
      [simetrica2 r,
       simetrica3 r]

-- La comprobación es
--    λ> quickCheck prop_simetrica
--    +++ OK, passed 100 tests.

import Relaciones_binarias (Rel(R))

import Test.QuickCheck

-- 1ª solución

-- ===========

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

simetrica (R (_,g)) = and [(y,x) `elem` g | (x,y) <- g]

-- 2ª solución

-- ===========

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

simetrica2 (R (_,g)) = all (\(x,y) -> (y,x) `elem` g) g

-- 3ª solución

-- ===========

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

simetrica3 (R (_,g)) = aux g

where aux [] = True

aux ((x,y):ps) = (y,x) `elem` g && aux ps

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_simetrica :: Rel Int -> Bool

prop_simetrica r =

all (== simetrica r)

[simetrica2 r,

simetrica3 r]

-- La comprobación es

-- λ> quickCheck prop_simetrica

-- +++ 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 simetrica(r: Rel[A]) -> bool:
    (_, g) = r
    return all(((y, x) in g for (x, y) in g))

# 2ª solución
# ===========

def simetrica2(r: Rel[A]) -> bool:
    (_, g) = r
    def aux(ps: list[tuple[A, A]]) -> bool:
        if not ps:
            return True
        (x, y) = ps[0]
        return (y, x) in g and aux(ps[1:])

    return aux(g)

# 3ª solución
# ===========

def simetrica3(r: Rel[A]) -> bool:
    (_, g) = r
    for (x, y) in g:
        if (y, x) not in g:
            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 = simetrica(r)
    assert simetrica2(r) == res
    assert simetrica3(r) == res

# La comprobación es
#    > poetry run pytest -q Relaciones_simetricas.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 simetrica(r: Rel[A]) -> bool:

(_, g) = r

return all(((y, x) in g for (x, y) in g))

# 2ª solución

# ===========

def simetrica2(r: Rel[A]) -> bool:

(_, g) = r

def aux(ps: list[tuple[A, A]]) -> bool:

if not ps:

return True

(x, y) = ps[0]

return (y, x) in g and aux(ps[1:])

return aux(g)

# 3ª solución

# ===========

def simetrica3(r: Rel[A]) -> bool:

(_, g) = r

for (x, y) in g:

if (y, x) not in g:

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 = simetrica(r)

assert simetrica2(r) == res

assert simetrica3(r) == res

# La comprobación es

# > poetry run pytest -q Relaciones_simetricas.py

# 1 passed in 0.11s

Relaciones reflexivas

PorJosé A. Alonso 30-marzo-20239-marzo-2023

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

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

1	reflexiva :: Eq a => Rel a -> Bool

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

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

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

Soluciones

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

Soluciones en Haskell

module Relaciones_reflexivas where

import Relaciones_binarias (Rel(R))
import Test.QuickCheck

-- 1ª solución
-- ===========

reflexiva :: Eq a => Rel a -> Bool
reflexiva (R ([], _))   = True
reflexiva (R (x:xs, ps)) = (x, x) `elem` ps && reflexiva  (R (xs, ps))

-- 2ª solución
-- ===========

reflexiva2 :: Eq a => Rel a -> Bool
reflexiva2 (R (us,ps)) = and [(x,x) `elem` ps | x <- us]

-- 3ª solución
-- ===========

reflexiva3 :: Eq a => Rel a -> Bool
reflexiva3 (R (us,ps)) = all (`elem` ps) [(x,x) | x <- us]

-- 4ª solución
-- ===========

reflexiva4 :: Eq a => Rel a -> Bool
reflexiva4 (R (us,ps)) = all (\x -> (x,x) `elem` ps) us

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_reflexiva :: Rel Int -> Bool
prop_reflexiva r =
  all (== reflexiva r)
      [reflexiva2 r,
       reflexiva3 r,
       reflexiva4 r]

-- La comprobación es
--    λ> quickCheck prop_reflexiva
--    +++ OK, passed 100 tests.

module Relaciones_reflexivas where

import Relaciones_binarias (Rel(R))

import Test.QuickCheck

-- 1ª solución

-- ===========

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

reflexiva (R ([], _)) = True

reflexiva (R (x:xs, ps)) = (x, x) `elem` ps && reflexiva (R (xs, ps))

-- 2ª solución

-- ===========

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

reflexiva2 (R (us,ps)) = and [(x,x) `elem` ps | x <- us]

-- 3ª solución

-- ===========

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

reflexiva3 (R (us,ps)) = all (`elem` ps) [(x,x) | x <- us]

-- 4ª solución

-- ===========

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

reflexiva4 (R (us,ps)) = all (\x -> (x,x) `elem` ps) us

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_reflexiva :: Rel Int -> Bool

prop_reflexiva r =

all (== reflexiva r)

[reflexiva2 r,

reflexiva3 r,

reflexiva4 r]

-- La comprobación es

-- λ> quickCheck prop_reflexiva

-- +++ OK, passed 100 tests.

Soluciones en Python

from random import choice, randint, sample
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 reflexiva(r: Rel[A]) -> bool:
    (us, ps) = r
    if not us:
        return True
    return (us[0], us[0]) in ps and reflexiva((us[1:], ps))

# 2ª solución
# ===========

def reflexiva2(r: Rel[A]) -> bool:
    (us, ps) = r
    return all(((x,x) in ps for x in us))

# 3ª solución
# ===========

def reflexiva3(r: Rel[A]) -> bool:
    (us, ps) = r
    for x in us:
        if (x, x) not in ps:
            return False
    return True

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_reflexiva(n: int) -> None:
    r = relacionArbitraria(n)
    res = reflexiva(r)
    assert reflexiva2(r) == res
    assert reflexiva3(r) == res

# La comprobación es
#    > poetry run pytest -q Relaciones_reflexivas.py
#    1 passed in 0.41s

from random import choice, randint, sample

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 reflexiva(r: Rel[A]) -> bool:

(us, ps) = r

if not us:

return True

return (us[0], us[0]) in ps and reflexiva((us[1:], ps))

# 2ª solución

# ===========

def reflexiva2(r: Rel[A]) -> bool:

(us, ps) = r

return all(((x,x) in ps for x in us))

# 3ª solución

# ===========

def reflexiva3(r: Rel[A]) -> bool:

(us, ps) = r

for x in us:

if (x, x) not in ps:

return False

return True

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(st.integers(min_value=0, max_value=10))

def test_reflexiva(n: int) -> None:

r = relacionArbitraria(n)

res = reflexiva(r)

assert reflexiva2(r) == res

assert reflexiva3(r) == res

# La comprobación es

# > poetry run pytest -q Relaciones_reflexivas.py

# 1 passed in 0.41s

Universo y grafo de una relación binaria

PorJosé A. Alonso 29-marzo-20236-marzo-2023

Usando el tipo de las relaciones binarias, definir las funciones

   universo :: Eq a => Rel a -> [a]
   grafo    :: Eq a => ([a],[(a,a)]) -> [(a,a)]

1 2	universo :: Eq a => Rel a -> [a] grafo :: Eq a => ([a],[(a,a)]) -> [(a,a)]

tales que

universo r es el universo de la relación r. Por ejemplo,

     λ> r = R ([1, 3],[(3, 1), (3, 3)])
     λ> universo r
     [1,3]

λ> r = R ([1, 3],[(3, 1), (3, 3)])

λ> universo r

[1,3]

grafo r es el grafo de la relación r. Por ejemplo,

     λ> grafo r
     [(3,1),(3,3)]

1 2	λ> grafo r [(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

universo :: Eq a => Rel a -> [a]
universo (R (u,_)) = u

grafo :: Eq a => Rel a -> [(a,a)]
grafo (R (_,g)) = g

import Relaciones_binarias

universo :: Eq a => Rel a -> [a]

universo (R (u,_)) = u

grafo :: Eq a => Rel a -> [(a,a)]

grafo (R (_,g)) = g

Soluciones en Python

from typing import TypeVar

A = TypeVar('A')

Rel = tuple[list[A], list[tuple[A, A]]]

def universo(r: Rel[A]) -> list[A]:
    return r[0]

def grafo(r: Rel[A]) -> list[tuple[A, A]]:
    return r[1]

from typing import TypeVar

A = TypeVar('A')

Rel = tuple[list[A], list[tuple[A, A]]]

def universo(r: Rel[A]) -> list[A]:

return r[0]

def grafo(r: Rel[A]) -> list[tuple[A, A]]:

return r[1]

PorJosé A. Alonso 28-marzo-202311-marzo-2023

Una relación binaria R sobre un conjunto A se puede mediante un par (u,g) donde u es la lista de los elementos de tipo A (el universo de R) y g es la lista de pares de elementos de u (el grafo de R).

Definir el tipo de dato (Rel a), para representar las relaciones binarias sobre a, y la función

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

1	esRelacionBinaria :: Eq a => Rel a -> Bool

tal que esRelacionBinaria r se verifica si r es una relación binaria. Por ejemplo,

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

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

True

λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 2)]))

False

Además, definir un generador de relaciones binarias y comprobar que las relaciones que genera son relaciones binarias.

Soluciones

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

Soluciones en Haskell

import Data.List (nub)
import Test.QuickCheck

newtype Rel a = R ([a], [(a,a)])
  deriving (Eq, Show)

-- 1ª solución
-- ===========

esRelacionBinaria :: Eq a => Rel a -> Bool
esRelacionBinaria (R (u, g)) =
  and [x `elem` u && y `elem` u | (x,y) <- g]

-- 2ª solución
-- ===========

esRelacionBinaria2 :: Eq a => Rel a -> Bool
esRelacionBinaria2 (R (u, g)) =
  all (\(x,y) -> x `elem` u && y `elem` u) g

-- 3ª solución
-- ===========

esRelacionBinaria3 :: Eq a => Rel a -> Bool
esRelacionBinaria3 (R (_, []))         = True
esRelacionBinaria3 (R (u, (x,y):g)) =
  x `elem` u &&
  y `elem` u &&
  esRelacionBinaria3 (R (u, g))

-- Comprobación de equivalencia
-- ============================

-- Generador de relaciones binarias. Por ejemplo,
--    λ> sample (relacionArbitraria :: Gen (Rel Int))
--    R ([0],[])
--    R ([0,-1,1],[(0,-1),(0,1),(-1,1),(1,0)])
--    R ([1],[])
--    R ([-5,3],[(-5,-5),(-5,3),(3,-5),(3,3)])
--    R ([-2,-7],[(-7,-7)])
--    R ([11,-7],[])
--    R ([0],[])
--    R ([-13,-11],[(-13,-13)])
relacionArbitraria :: (Arbitrary a, Eq a) => Gen (Rel a)
relacionArbitraria = do
  n <- choose (0, 10)
  u1 <- vectorOf n arbitrary
  let u = nub u1
  g <- sublistOf [(x,y) | x <- u, y <- u]
  return (R (u, g))

-- Relaciones es una subclase de Arbitrary.
instance (Arbitrary a, Eq a) => Arbitrary (Rel a) where
  arbitrary = relacionArbitraria

-- La propiedad es
prop_esRelacionBinaria :: Rel Int -> Bool
prop_esRelacionBinaria r =
  esRelacionBinaria r  &&
  esRelacionBinaria2 r &&
  esRelacionBinaria3 r

-- La comprobación es
--    λ> quickCheck prop_esRelacionBinaria
--    +++ OK, passed 100 tests.

import Data.List (nub)

import Test.QuickCheck

newtype Rel a = R ([a], [(a,a)])

deriving (Eq, Show)

-- 1ª solución

-- ===========

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

esRelacionBinaria (R (u, g)) =

and [x `elem` u && y `elem` u | (x,y) <- g]

-- 2ª solución

-- ===========

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

esRelacionBinaria2 (R (u, g)) =

all (\(x,y) -> x `elem` u && y `elem` u) g

-- 3ª solución

-- ===========

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

esRelacionBinaria3 (R (_, [])) = True

esRelacionBinaria3 (R (u, (x,y):g)) =

x `elem` u &&

y `elem` u &&

esRelacionBinaria3 (R (u, g))

-- Comprobación de equivalencia

-- ============================

-- Generador de relaciones binarias. Por ejemplo,

-- λ> sample (relacionArbitraria :: Gen (Rel Int))

-- R ([0],[])

-- R ([0,-1,1],[(0,-1),(0,1),(-1,1),(1,0)])

-- R ([1],[])

-- R ([-5,3],[(-5,-5),(-5,3),(3,-5),(3,3)])

-- R ([-2,-7],[(-7,-7)])

-- R ([11,-7],[])

-- R ([0],[])

-- R ([-13,-11],[(-13,-13)])

relacionArbitraria :: (Arbitrary a, Eq a) => Gen (Rel a)

relacionArbitraria = do

n <- choose (0, 10)

u1 <- vectorOf n arbitrary

let u = nub u1

g <- sublistOf [(x,y) | x <- u, y <- u]

return (R (u, g))

-- Relaciones es una subclase de Arbitrary.

instance (Arbitrary a, Eq a) => Arbitrary (Rel a) where

arbitrary = relacionArbitraria

-- La propiedad es

prop_esRelacionBinaria :: Rel Int -> Bool

prop_esRelacionBinaria r =

esRelacionBinaria r &&

esRelacionBinaria2 r &&

esRelacionBinaria3 r

-- La comprobación es

-- λ> quickCheck prop_esRelacionBinaria

-- +++ OK, passed 100 tests.

Soluciones en Python

from random import choice, randint, sample
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')

Rel = tuple[list[A], list[tuple[A, A]]]

# 1ª solución
# ===========

def esRelacionBinaria(r: Rel[A]) -> bool:
    (u, g) = r
    return all((x in u and y in u for (x, y) in g))

# 2ª solución
# ===========

def esRelacionBinaria2(r: Rel[A]) -> bool:
    (u, g) = r
    if not g:
        return True
    (x, y) = g[0]
    return x in u and y in u and esRelacionBinaria2((u, g[1:]))

# 3ª solución
# ===========

def esRelacionBinaria3(r: Rel[A]) -> bool:
    (u, g) = r
    for (x, y) in g:
        if x not in u or y not in u:
            return False
    return True

# Generador de relaciones binarias
# ================================

# conjuntoArbitrario(n) es un conjunto arbitrario cuyos elementos están
# entre 0 y n-1. Por ejemplo,
#    >>> conjuntoArbitrario(10)
#    [8, 9, 4, 5]
#    >>> conjuntoArbitrario(10)
#    [1, 2, 3, 4, 5, 6, 7, 8, 9]
#    >>> conjuntoArbitrario(10)
#    [0, 1, 2, 3, 6, 7, 9]
#    >>> conjuntoArbitrario(10)
#    [8, 2, 3, 7]
def conjuntoArbitrario(n: int) -> list[int]:
    xs = sample(range(n), randint(0, n))
    return list(set(xs))

# productoCartesiano(xs, ys) es el producto cartesiano de xs e ys. Por
# ejemplo,
#    >>> productoCartesiano([2, 3], [1, 7, 5])
#    [(2, 1), (2, 7), (2, 5), (3, 1), (3, 7), (3, 5)]
def productoCartesiano(xs: list[int], ys: list[int]) -> list[tuple[int, int]]:
    return [(x, y) for x in xs for y in ys]

# sublistaArbitraria(xs) es una sublista arbitraria de xs. Por ejemplo,
#    >>> sublistaArbitraria(range(10))
#    [3, 7]
#    >>> sublistaArbitraria(range(10))
#    []
#    >>> sublistaArbitraria(range(10))
#    [4, 1, 0, 9, 8, 7, 5, 6, 2, 3]
def sublistaArbitraria(xs: list[A]) -> list[A]:
    n = len(xs)
    k = randint(0, n)
    return sample(xs, k)

# relacionArbitraria(n) es una relación arbitraria tal que los elementos
# de su universo están entre 0 y n-1. Por ejemplo,
#    >>> relacionArbitraria(3)
#    ([0, 1], [(1, 0), (1, 1)])
#    >>> relacionArbitraria(3)
#    ([], [])
#    >>> relacionArbitraria(5)
#    ([0, 2, 3, 4], [(2, 0), (3, 3), (2, 3), (4, 0), (3, 4), (4, 2)])
def relacionArbitraria(n: int) -> Rel[int]:
    u = conjuntoArbitrario(n)
    g = sublistaArbitraria(productoCartesiano(u, u))
    return (u, g)

# Comprobación de la propiedad
# ============================

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_esRelacionBinaria(n: int) -> None:
    r = relacionArbitraria(n)
    assert esRelacionBinaria(r)
    assert esRelacionBinaria2(r)
    assert esRelacionBinaria3(r)

# La comprobación es
#    > poetry run pytest -q Relaciones_binarias.py
#    1 passed in 0.14s

100

from random import choice, randint, sample

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

A = TypeVar('A')

Rel = tuple[list[A], list[tuple[A, A]]]

# 1ª solución

# ===========

def esRelacionBinaria(r: Rel[A]) -> bool:

(u, g) = r

return all((x in u and y in u for (x, y) in g))

# 2ª solución

# ===========

def esRelacionBinaria2(r: Rel[A]) -> bool:

(u, g) = r

if not g:

return True

(x, y) = g[0]

return x in u and y in u and esRelacionBinaria2((u, g[1:]))

# 3ª solución

# ===========

def esRelacionBinaria3(r: Rel[A]) -> bool:

(u, g) = r

for (x, y) in g:

if x not in u or y not in u:

return False

return True

# Generador de relaciones binarias

# ================================

# conjuntoArbitrario(n) es un conjunto arbitrario cuyos elementos están

# entre 0 y n-1. Por ejemplo,

# >>> conjuntoArbitrario(10)

# [8, 9, 4, 5]

# >>> conjuntoArbitrario(10)

# [1, 2, 3, 4, 5, 6, 7, 8, 9]

# >>> conjuntoArbitrario(10)

# [0, 1, 2, 3, 6, 7, 9]

# >>> conjuntoArbitrario(10)

# [8, 2, 3, 7]

def conjuntoArbitrario(n: int) -> list[int]:

xs = sample(range(n), randint(0, n))

return list(set(xs))

# productoCartesiano(xs, ys) es el producto cartesiano de xs e ys. Por

# ejemplo,

# >>> productoCartesiano([2, 3], [1, 7, 5])

# [(2, 1), (2, 7), (2, 5), (3, 1), (3, 7), (3, 5)]

def productoCartesiano(xs: list[int], ys: list[int]) -> list[tuple[int, int]]:

return [(x, y) for x in xs for y in ys]

# sublistaArbitraria(xs) es una sublista arbitraria de xs. Por ejemplo,

# >>> sublistaArbitraria(range(10))

# [3, 7]

# >>> sublistaArbitraria(range(10))

# []

# >>> sublistaArbitraria(range(10))

# [4, 1, 0, 9, 8, 7, 5, 6, 2, 3]

def sublistaArbitraria(xs: list[A]) -> list[A]:

n = len(xs)

k = randint(0, n)

return sample(xs, k)

# relacionArbitraria(n) es una relación arbitraria tal que los elementos

# de su universo están entre 0 y n-1. Por ejemplo,

# >>> relacionArbitraria(3)

# ([0, 1], [(1, 0), (1, 1)])

# >>> relacionArbitraria(3)

# ([], [])

# >>> relacionArbitraria(5)

# ([0, 2, 3, 4], [(2, 0), (3, 3), (2, 3), (4, 0), (3, 4), (4, 2)])

def relacionArbitraria(n: int) -> Rel[int]:

u = conjuntoArbitrario(n)

g = sublistaArbitraria(productoCartesiano(u, u))

return (u, g)

# Comprobación de la propiedad

# ============================

# La propiedad es

@given(st.integers(min_value=0, max_value=10))

def test_esRelacionBinaria(n: int) -> None:

r = relacionArbitraria(n)

assert esRelacionBinaria(r)

assert esRelacionBinaria2(r)

assert esRelacionBinaria3(r)

# La comprobación es

# > poetry run pytest -q Relaciones_binarias.py

# 1 passed in 0.14s

Representación matricial de relaciones binarias

PorJosé A. Alonso 9-junio-20226-junio-2022

Dada una relación r sobre un conjunto de números enteros, la matriz asociada a r es una matriz booleana p (cuyos elementos son True o False), tal que p(i,j) = True si y sólo si i está relacionado con j mediante la relación r.

Las relaciones binarias homogéneas y las matrices booleanas se pueden representar por

   type Relacion = ([Int],[(Int,Int)])
   type Matriz = Array (Int,Int) Bool

1 2	type Relacion = ([Int],[(Int,Int)]) type Matriz = Array (Int,Int) Bool

Definir la función

   matrizRB:: Relacion -> Matriz

1	matrizRB:: Relacion -> Matriz

tal que (matrizRB r) es la matriz booleana asociada a r. Por ejemplo,

   λ> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)])
   array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True),
                        ((2,1),False),((2,2),False),((2,3),False),
                        ((3,1),True) ,((3,2),False),((3,3),True)]
   λ> matrizRB ([1..3],[(1,3), (3,1)])
   array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True),
                        ((2,1),False),((2,2),False),((2,3),False),
                        ((3,1),True) ,((3,2),False),((3,3),False)]
   λ> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)
   False

λ> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)])

array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True),

((2,1),False),((2,2),False),((2,3),False),

((3,1),True) ,((3,2),False),((3,3),True)]

λ> matrizRB ([1..3],[(1,3), (3,1)])

array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True),

((2,1),False),((2,2),False),((2,3),False),

((3,1),True) ,((3,2),False),((3,3),False)]

λ> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)

False

Soluciones

import Data.Array      (Array, accumArray, array, listArray)
import Test.QuickCheck (Arbitrary, Gen, arbitrary, sublistOf, suchThat,
                        quickCheck)

type Relacion = ([Int],[(Int,Int)])
type Matriz   = Array (Int,Int) Bool

-- 1ª solución
-- ===========

matrizRB1 :: Relacion -> Matriz 
matrizRB1 r = 
    array ((1,1),(n,n)) 
          [((a,b), (a,b) `elem` grafo r) | a <- [1..n], b <- [1..n]]
    where n = maximum (universo r)
          universo (us,_) = us
          grafo (_,ps)    = ps

-- 2ª solución
-- ===========

matrizRB2 :: Relacion -> Matriz
matrizRB2 r = 
    listArray ((1,1),(n,n)) 
              [(a,b) `elem` snd r | a <- [1..n], b <- [1..n]]
    where n = maximum (fst r)

-- 3ª solución
-- ===========

matrizRB3 :: Relacion -> Matriz
matrizRB3 r = 
    accumArray (||) False ((1,1),(n,n)) (zip (snd r) (repeat True))
    where n = maximum (fst r)

-- Comprobación de equivalencia
-- ============================

-- Tipo de relaciones binarias
newtype RB = RB Relacion
  deriving Show

-- relacionArbitraria genera una relación arbitraria. Por ejemplo, 
--    λ> generate relacionArbitraria
--    RB ([1,2,3,4,5],[(1,4),(1,5),(2,3),(2,4),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4)])
relacionArbitraria :: Gen RB
relacionArbitraria = do
  n <- arbitrary `suchThat` (> 1)
  xs <- sublistOf [(x,y) | x <- [1..n], y <- [1..n]]
  return (RB ([1..n], xs))

-- RB es una subclase de Arbitrary
instance Arbitrary RB where
  arbitrary = relacionArbitraria

-- La propiedad es
prop_matrizRB :: RB -> Bool
prop_matrizRB (RB r) =
  all (== matrizRB1 r)
      [matrizRB2 r,
       matrizRB3 r]

-- La comprobación es
--    λ> quickCheck prop_matrixzB
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> let n = 2000 in matrizRB1 ([1..n],[(1,n),(n,1)]) ! (n,n)
--    False
--    (2.02 secs, 1,505,248,912 bytes)
--    λ> let n = 2000 in matrizRB2 ([1..n],[(1,n),(n,1)]) ! (n,n)
--    False
--    (1.92 secs, 833,232,360 bytes)
--    λ> let n = 2000 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)
--    False
--    (0.05 secs, 32,848,696 bytes)

import Data.Array (Array, accumArray, array, listArray)

import Test.QuickCheck (Arbitrary, Gen, arbitrary, sublistOf, suchThat,

quickCheck)

type Relacion = ([Int],[(Int,Int)])

type Matriz = Array (Int,Int) Bool

-- 1ª solución

-- ===========

matrizRB1 :: Relacion -> Matriz

matrizRB1 r =

array ((1,1),(n,n))

[((a,b), (a,b) `elem` grafo r) | a <- [1..n], b <- [1..n]]

where n = maximum (universo r)

universo (us,_) = us

grafo (_,ps) = ps

-- 2ª solución

-- ===========

matrizRB2 :: Relacion -> Matriz

matrizRB2 r =

listArray ((1,1),(n,n))

[(a,b) `elem` snd r | a <- [1..n], b <- [1..n]]

where n = maximum (fst r)

-- 3ª solución

-- ===========

matrizRB3 :: Relacion -> Matriz

matrizRB3 r =

accumArray (||) False ((1,1),(n,n)) (zip (snd r) (repeat True))

where n = maximum (fst r)

-- Comprobación de equivalencia

-- ============================

-- Tipo de relaciones binarias

newtype RB = RB Relacion

deriving Show

-- relacionArbitraria genera una relación arbitraria. Por ejemplo,

-- λ> generate relacionArbitraria

-- RB ([1,2,3,4,5],[(1,4),(1,5),(2,3),(2,4),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4)])

relacionArbitraria :: Gen RB

relacionArbitraria = do

n <- arbitrary `suchThat` (> 1)

xs <- sublistOf [(x,y) | x <- [1..n], y <- [1..n]]

return (RB ([1..n], xs))

-- RB es una subclase de Arbitrary

instance Arbitrary RB where

arbitrary = relacionArbitraria

-- La propiedad es

prop_matrizRB :: RB -> Bool

prop_matrizRB (RB r) =

all (== matrizRB1 r)

[matrizRB2 r,

matrizRB3 r]

-- La comprobación es

-- λ> quickCheck prop_matrixzB

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> let n = 2000 in matrizRB1 ([1..n],[(1,n),(n,1)]) ! (n,n)

-- False

-- (2.02 secs, 1,505,248,912 bytes)

-- λ> let n = 2000 in matrizRB2 ([1..n],[(1,n),(n,1)]) ! (n,n)

-- False

-- (1.92 secs, 833,232,360 bytes)

-- λ> let n = 2000 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)

-- False

-- (0.05 secs, 32,848,696 bytes)

El código se encuentra en GitHub.

Relaciones binarias

Clausura transitiva

Clausura simétrica

Clausura reflexiva

Relaciones totales

Relaciones antisimétricas

Relaciones irreflexivas

Relaciones de equivalencia

Relaciones transitivas

Composición de relaciones binarias

Relaciones simétricas

Relaciones reflexivas

Universo y grafo de una relación binaria