{"id":7924,"date":"2023-04-15T09:10:03","date_gmt":"2023-04-15T07:10:03","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=7924"},"modified":"2023-04-15T09:10:03","modified_gmt":"2023-04-15T07:10:03","slug":"15-abr-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/15-abr-23\/","title":{"rendered":"La semana en Exercitium (15 de abril de 2023)"},"content":{"rendered":"<p>Estas dos \u00faltimas semanas he publicado en <a href=\"http:\/\/bit.ly\/2sqPtGs\">Exercitium<\/a> las soluciones de los siguientes problemas:<\/p>\n<ul>\n<li><a href=\"#ej1\">1. Composici\u00f3n de relaciones binarias<\/a><\/li>\n<li><a href=\"#ej2\">2. Reconocimiento de subconjunto<\/a><\/li>\n<li><a href=\"#ej3\">3. Relaciones transitivas<\/a><\/li>\n<li><a href=\"#ej4\">4. Relaciones de equivalencia<\/a><\/li>\n<li><a href=\"#ej5\">5. Relaciones irreflexivas<\/a><\/li>\n<li><a href=\"#ej6\">6. Relaciones antisim\u00e9tricas<\/a><\/li>\n<li><a href=\"#ej7\">7. Relaciones totales<\/a><\/li>\n<li><a href=\"#ej8\">8. Clausura reflexiva<\/a><\/li>\n<li><a href=\"#ej9\">9. Clausura sim\u00e9trica<\/a><\/li>\n<li><a href=\"#ej10\">10. Clausura transitiva<\/a><\/li>\n<\/ul>\n<p>A continuaci\u00f3n se muestran las soluciones.<br \/>\n<!--more--><br \/>\n<a name=\"ej1\"><\/a><\/p>\n<h3>1. Composici\u00f3n de relaciones binarias<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   composicion :: Eq a => Rel a -> Rel a -> Rel a\n<\/pre>\n<p>tal que <code>composicion r s<\/code> es la composici\u00f3n de las relaciones <code>r<\/code> y <code>s<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)]))\n   R ([1,2],[(1,1),(2,1)])\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncomposicion :: Eq a => Rel a -> Rel a -> Rel a\ncomposicion (R (u1,g1)) (R (_,g2)) =\n  R (u1,[(x,z) | (x,y) <- g1, (y',z) <- g2, y == y'])\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ncomposicion2 :: Eq a => Rel a -> Rel a -> Rel a\ncomposicion2 (R (u1,g1)) (R (_,g2)) =\n  R (u1, aux g1)\n  where aux [] = []\n        aux ((x,y):g1') = [(x,z) | (y',z) <- g2, y == y'] ++ aux g1'\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_composicion :: Rel Int -> Rel Int -> Bool\nprop_composicion r1 r2 =\n  composicion r1 r2 == composicion2 r1 r2\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_composicion\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef composicion(r1: Rel[A], r2: Rel[A]) -> Rel[A]:\n    (u1, g1) = r1\n    (_,  g2) = r2\n    return (u1, [(x, z) for (x, y) in g1 for (u, z) in g2 if y == u])\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef composicion2(r1: Rel[A], r2: Rel[A]) -> Rel[A]:\n    (u1, g1) = r1\n    (_,  g2) = r2\n    def aux(g: list[tuple[A, A]]) -> list[tuple[A, A]]:\n        if not g:\n            return []\n        (x, y) = g[0]\n        return [(x, z) for (u, z) in g2 if y == u] + aux(g[1:])\n\n    return (u1, aux(g1))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef composicion3(r1: Rel[A], r2: Rel[A]) -> Rel[A]:\n    (u1, g1) = r1\n    (_,  g2) = r2\n    r: list[tuple[A, A]] = []\n    for (x, y) in g1:\n        r = r + [(x, z) for (u, z) in g2 if y == u]\n    return (u1, r)\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10),\n       st.integers(min_value=0, max_value=10))\ndef test_simetrica(n: int, m: int) -> None:\n    r1 = relacionArbitraria(n)\n    r2 = relacionArbitraria(m)\n    res = composicion(r1, r2)\n    assert composicion2(r1, r2) == res\n    assert composicion2(r1, r2) == res\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Composicion_de_relaciones_binarias_v2.py\n#    1 passed in 0.19s\n<\/pre>\n<p><a name=\"ej2\"><\/a><\/p>\n<h3>2. Reconocimiento de subconjunto<\/h3>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   subconjunto :: Ord a => [a] -> [a] -> Bool\n<\/pre>\n<p>tal que <code>subconjunto xs ys<\/code> se verifica si <code>xs<\/code> es un subconjunto de <code>ys<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   subconjunto [3,2,3] [2,5,3,5]  ==  True\n   subconjunto [3,2,3] [2,5,6,5]  ==  False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nmodule Reconocimiento_de_subconjunto where\n\nimport Data.List (nub, sort)\nimport Data.Set (fromList, isSubsetOf)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nsubconjunto1 :: Ord a => [a] -> [a] -> Bool\nsubconjunto1 xs ys =\n  [x | x <- xs, x `elem` ys] == xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsubconjunto2 :: Ord a => [a] -> [a] -> Bool\nsubconjunto2 []     _  = True\nsubconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nsubconjunto3 :: Ord a => [a] -> [a] -> Bool\nsubconjunto3 xs ys =\n  all (`elem` ys) xs\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nsubconjunto4 :: Ord a => [a] -> [a] -> Bool\nsubconjunto4 xs ys =\n  fromList xs `isSubsetOf` fromList ys\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_subconjunto :: [Int] -> [Int] -> Bool\nprop_subconjunto xs ys =\n  all (== subconjunto1 xs ys)\n      [subconjunto2 xs ys,\n       subconjunto3 xs ys,\n       subconjunto4 xs ys]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_subconjunto\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> subconjunto1 [1..2*10^4] [1..2*10^4]\n--    True\n--    (1.81 secs, 5,992,448 bytes)\n--    \u03bb> subconjunto2 [1..2*10^4] [1..2*10^4]\n--    True\n--    (1.83 secs, 6,952,200 bytes)\n--    \u03bb> subconjunto3 [1..2*10^4] [1..2*10^4]\n--    True\n--    (1.75 secs, 4,712,304 bytes)\n--    \u03bb> subconjunto4 [1..2*10^4] [1..2*10^4]\n--    True\n--    (0.04 secs, 6,312,056 bytes)\n\n-- En lo sucesivo, usaremos la 4\u00aa definici\u00f3n\nsubconjunto :: Ord a => [a] -> [a] -> Bool\nsubconjunto = subconjunto4\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef subconjunto1(xs: list[A], ys: list[A]) -> bool:\n    return [x for x in xs if x in ys] == xs\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef subconjunto2(xs: list[A], ys: list[A]) -> bool:\n    if not xs:\n        return True\n    return xs[0] in ys and subconjunto2(xs[1:], ys)\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef subconjunto3(xs: list[A], ys: list[A]) -> bool:\n    return all(elem in ys for elem in xs)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef subconjunto4(xs: list[A], ys: list[A]) -> bool:\n    return set(xs) <= set(ys)\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers()),\n       st.lists(st.integers()))\ndef test_filtraAplica(xs: list[int], ys: list[int]) -> None:\n    r = subconjunto1(xs, ys)\n    assert subconjunto2(xs, ys) == r\n    assert subconjunto3(xs, ys) == r\n    assert subconjunto4(xs, ys) == r\n\n# La comprobaci\u00f3n es\n#    src> poetry run pytest -q Reconocimiento_de_subconjunto.py\n#    1 passed in 0.31s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> xs = list(range(2*10**4))\n#    >>> tiempo(\"subconjunto1(xs, xs)\")\n#    1.15 segundos\n#    >>> tiempo(\"subconjunto2(xs, xs)\")\n#    2.27 segundos\n#    >>> tiempo(\"subconjunto3(xs, xs)\")\n#    1.14 segundos\n#    >>> tiempo(\"subconjunto4(xs, xs)\")\n#    0.00 segundos\n\n# En lo sucesivo usaremos la cuarta definici\u00f3n\nsubconjunto = subconjunto4\n<\/pre>\n<p><a name=\"ej3\"><\/a><\/p>\n<h3>3. Relaciones transitivas<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   transitiva :: Ord a => Rel a -> Bool\n<\/pre>\n<p>tal que <code>transitiva r<\/code> se verifica si la relaci\u00f3n <code>r<\/code> es transitiva. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) == True\n   transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(5,5)]))       == False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Reconocimiento_de_subconjunto (subconjunto)\nimport Universo_y_grafo_de_una_relacion_binaria (grafo)\nimport Composicion_de_relaciones_binarias_v2 (composicion)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva1 :: Ord a => Rel a -> Bool\ntransitiva1 r@(R (_,g)) = subconjunto (grafo (composicion r r)) g\n\n-- La funci\u00f3n subconjunto est\u00e1 definida en el ejercicio\n-- \"Reconocimiento de subconjunto\" que se encuentra en\n-- https:\/\/bit.ly\/427Tyeq\n--\n-- La funci\u00f3n grafo est\u00e1 definida en el ejercicio\n-- \"Universo y grafo de una relaci\u00f3n binaria\" que se encuentra en\n-- https:\/\/bit.ly\/3J35mpC\n--\n-- La funci\u00f3n composici\u00f3n est\u00e1 definida en el ejercicio\n-- \"Composici\u00f3n de relaciones binarias\" que se encuentra en\n-- https:\/\/bit.ly\/3JyJrs7\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntransitiva2 :: Ord a => Rel a -> Bool\ntransitiva2 (R (_,g)) = aux g\n  where\n    aux [] = True\n    aux ((x,y):g') = and [(x,z) `elem` g | (u,z) <- g, u == y] &#038;&#038; aux g'\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_transitiva :: Rel Int -> Bool\nprop_transitiva r =\n  transitiva1 r == transitiva2 r\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_transitiva\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> transitiva1 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))\n--    False\n--    (3.15 secs, 898,932,776 bytes)\n--    \u03bb> transitiva2 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))\n--    False\n--    (0.01 secs, 1,396,720 bytes)\n--\n--    \u03bb> transitiva1 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))\n--    True\n--    (2.71 secs, 852,578,456 bytes)\n--    \u03bb> transitiva2 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))\n--    True\n--    (9.13 secs, 777,080,288 bytes)\n\n-- En lo sucesivo, usaremos la 1\u00aa definici\u00f3n\ntransitiva :: Ord a => Rel a -> Bool\ntransitiva = transitiva1\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Composicion_de_relaciones_binarias_v2 import composicion\nfrom src.Reconocimiento_de_subconjunto import subconjunto\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\nfrom src.Universo_y_grafo_de_una_relacion_binaria import grafo\n\nsetrecursionlimit(10**6)\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef transitiva1(r: Rel[A]) -> bool:\n    g = grafo(r)\n    return subconjunto(grafo(composicion(r, r)), g)\n\n# La funci\u00f3n subconjunto est\u00e1 definida en el ejercicio\n# \"Reconocimiento de subconjunto\" que se encuentra en\n# https:\/\/bit.ly\/427Tyeq\n#\n# La funci\u00f3n grafo est\u00e1 definida en el ejercicio\n# \"Universo y grafo de una relaci\u00f3n binaria\" que se encuentra en\n# https:\/\/bit.ly\/3J35mpC\n#\n# La funci\u00f3n composici\u00f3n est\u00e1 definida en el ejercicio\n# \"Composici\u00f3n de relaciones binarias\" que se encuentra en\n# https:\/\/bit.ly\/3JyJrs7\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef transitiva2(r: Rel[A]) -> bool:\n    g = grafo(r)\n    def aux(g1: list[tuple[A,A]]) -> bool:\n        if not g1:\n            return True\n        (x, y) = g1[0]\n        return all(((x, z) in g for (u,z) in g if u == y)) and aux(g1[1:])\n\n    return aux(g)\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef transitiva3(r: Rel[A]) -> bool:\n    g = grafo(r)\n    g1 = list(g)\n    for (x, y) in g1:\n        if not all(((x, z) in g for (u,z) in g if u == y)):\n            return False\n    return True\n\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_simetrica(n: int) -> None:\n    r = relacionArbitraria(n)\n    res = transitiva1(r)\n    assert transitiva2(r) == res\n    assert transitiva3(r) == res\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Relaciones_transitivas.py\n#    1 passed in 0.12s\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> u1 = range(6001)\n#    >>> g1 = [(x, x+1) for x in range(6000)]\n#    >>> tiempo(\"transitiva1((u1, g1))\")\n#    1.04 segundos\n#    >>> tiempo(\"transitiva2((u1, g1))\")\n#    0.00 segundos\n#    >>> tiempo(\"transitiva3((u1, g1))\")\n#    0.00 segundos\n#\n#    >>> u2 = range(60)\n#    >>> g2 = [(x, y) for x in u2 for y in u2]\n#    >>> tiempo(\"transitiva1((u2, g2))\")\n#    0.42 segundos\n#    >>> tiempo(\"transitiva2((u2, g2))\")\n#    5.24 segundos\n#    >>> tiempo(\"transitiva3((u2, g2))\")\n#    4.83 segundos\n\n# En lo sucesivo usaremos la 1\u00aa definici\u00f3n\ntransitiva = transitiva1\n<\/pre>\n<p><a name=\"ej4\"><\/a><\/p>\n<h3>4. Relaciones de equivalencia<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   esEquivalencia :: Ord a => Rel a -> Bool\n<\/pre>\n<p>tal que <code>esEquivalencia r<\/code> se verifica si la relaci\u00f3n <code>r<\/code> es de equivalencia. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))\n   True\n   \u03bb> esEquivalencia (R ([1,2,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))\n   False\n   \u03bb> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,3),(5,5)]))\n   False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Relaciones_reflexivas (reflexiva)\nimport Relaciones_simetricas (simetrica)\nimport Relaciones_transitivas (transitiva)\n\nesEquivalencia :: Ord a => Rel a -> Bool\nesEquivalencia r = reflexiva r && simetrica r && transitiva r\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\nfrom src.Relaciones_reflexivas import reflexiva\nfrom src.Relaciones_simetricas import simetrica\nfrom src.Relaciones_transitivas import transitiva\n\nA = TypeVar('A')\n\ndef esEquivalencia(r: Rel[A]) -> bool:\n    return reflexiva(r) and simetrica(r) and transitiva(r)\n<\/pre>\n<p><a name=\"ej5\"><\/a><\/p>\n<h3>5. Relaciones irreflexivas<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   irreflexiva :: Eq a => Rel a -> Bool\n<\/pre>\n<p>tal que <code>irreflexiva r<\/code> se verifica si la relaci\u00f3n <code>r<\/code> es irreflexiva; es decir, si ning\u00fan elemento de su universo est\u00e1 relacionado con \u00e9l mismo. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   irreflexiva (R ([1,2,3],[(1,2),(2,1),(2,3)]))  ==  True\n   irreflexiva (R ([1,2,3],[(1,2),(2,1),(3,3)]))  ==  False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nirreflexiva :: Eq a => Rel a -> Bool\nirreflexiva (R (u,g)) = and [(x,x) `notElem` g | x <- u]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nirreflexiva2 :: Eq a => Rel a -> Bool\nirreflexiva2 (R(u,g)) = all (\\x -> (x,x) `notElem` g) u\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nirreflexiva3 :: Eq a => Rel a -> Bool\nirreflexiva3 (R(u,g)) = aux u\n  where aux []     = True\n        aux (x:xs) = (x,x) `notElem` g && aux xs\n\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_irreflexiva :: Rel Int -> Bool\nprop_irreflexiva r =\n  all (== irreflexiva r)\n      [irreflexiva2 r,\n       irreflexiva3 r]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_irreflexiva\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef irreflexiva(r: Rel[A]) -> bool:\n    (u, g) = r\n    return all(((x, x) not in g for x in u))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef irreflexiva2(r: Rel[A]) -> bool:\n    (u, g) = r\n    def aux(xs: list[A]) -> bool:\n        if not xs:\n            return True\n        return (xs[0], xs[0]) not in g and aux(xs[1:])\n\n    return aux(u)\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef irreflexiva3(r: Rel[A]) -> bool:\n    (u, g) = r\n    for x in u:\n        if (x, x) in g:\n            return False\n    return True\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_irreflexiva(n: int) -> None:\n    r = relacionArbitraria(n)\n    res = irreflexiva(r)\n    assert irreflexiva2(r) == res\n    assert irreflexiva3(r) == res\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Relaciones_irreflexivas.py\n#    1 passed in 0.12s\n<\/pre>\n<p><a name=\"ej6\"><\/a><\/p>\n<h3>6. Relaciones antisim\u00e9tricas<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   antisimetrica :: Eq a => Rel a -> Bool\n<\/pre>\n<p>tal que <code>antisimetrica r<\/code> se verifica si la relaci\u00f3n <code>r<\/code> es antisim\u00e9trica; es decir, si (x,y) e (y,x) est\u00e1n relacionado, entonces x=y. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   antisimetrica (R ([1,2],[(1,2)]))        ==  True\n   antisimetrica (R ([1,2],[(1,2),(2,1)]))  ==  False\n   antisimetrica (R ([1,2],[(1,1),(2,1)]))  ==  True\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nantisimetrica :: Eq a => Rel a -> Bool\nantisimetrica (R (_,g)) =\n  null [(x,y) | (x,y) <- g, x \/= y, (y,x) `elem` g]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nantisimetrica2 :: Eq a => Rel a -> Bool\nantisimetrica2 (R (_,g)) =\n  and [(y,x) `notElem` g | (x,y) <- g, x \/= y]\n\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nantisimetrica3 :: Eq a => Rel a -> Bool\nantisimetrica3 (R (_,g)) =\n  all (\\(x, y) -> (y,x) `notElem` g || x == y) g\n\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nantisimetrica4 :: Eq a => Rel a -> Bool\nantisimetrica4 (R (u,g)) =\n  and [((x,y) `elem` g && (y,x) `elem` g) --> (x == y)\n       | x <- u, y <- u]\n  where p --> q = not p || q\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nantisimetrica5 :: Eq a => Rel a -> Bool\nantisimetrica5 (R (_,g)) = aux g\n  where aux []         = True\n        aux ((x,y):g') = ((y,x) `notElem` g || x == y) && aux g'\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_antisimetrica :: Rel Int -> Bool\nprop_antisimetrica r =\n  all (== antisimetrica r)\n      [antisimetrica2 r,\n       antisimetrica3 r,\n       antisimetrica4 r,\n       antisimetrica5 r]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_antisimetrica\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef antisimetrica(r: Rel[A]) -> bool:\n    (u, g) = r\n    return [(x, y) for (x, y) in g if x != y and (y, x) in g] == []\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef antisimetrica2(r: Rel[A]) -> bool:\n    (u, g) = r\n    return all(((y, x) not in g for (x, y) in g if x != y))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef antisimetrica3(r: Rel[A]) -> bool:\n    (u, g) = r\n    return all ((not ((x, y) in g and (y, x) in g) or x == y\n                 for x in u for y in u))\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef antisimetrica4(r: Rel[A]) -> bool:\n    (u, g) = r\n    def aux(xys: list[tuple[A, A]]) -> bool:\n        if not xys:\n            return True\n        (x, y) = xys[0]\n        return ((y, x) not in g or x == y) and aux(xys[1:])\n\n    return aux(g)\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef antisimetrica5(r: Rel[A]) -> bool:\n    (u, g) = r\n    for (x, y) in g:\n        if (y, x) in g and x != y:\n            return False\n    return True\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_antisimetrica(n: int) -> None:\n    r = relacionArbitraria(n)\n    res = antisimetrica(r)\n    assert antisimetrica2(r) == res\n    assert antisimetrica3(r) == res\n    assert antisimetrica4(r) == res\n    assert antisimetrica5(r) == res\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Relaciones_antisimetricas.py\n#    1 passed in 0.13s\n<\/pre>\n<p><a name=\"ej7\"><\/a><\/p>\n<h3>7. Relaciones totales<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   total :: Eq a => Rel a -> Bool\n<\/pre>\n<p>tal que <code>total r<\/code> se verifica si la relaci\u00f3n <code>r<\/code> es total; es decir, si para cualquier par x, y de elementos del universo de r, se tiene que x est\u00e1 relacionado con y o y est\u00e1 relacionado con x. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   total (R ([1,3],[(1,1),(3,1),(3,3)]))  ==  True\n   total (R ([1,3],[(1,1),(3,1)]))        ==  False\n   total (R ([1,3],[(1,1),(3,3)]))        ==  False\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntotal :: Eq a => Rel a -> Bool\ntotal (R (u,g)) =\n  and [(x,y) `elem` g || (y,x) `elem` g | x <- u, y <- u]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntotal2 :: Eq a => Rel a -> Bool\ntotal2 (R (u,g)) =\n  all (relacionados g) (producto u u)\n\n-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,\n--    \u03bb> producto [2,5] [1,4,6]\n--    [(2,1),(2,4),(2,6),(5,1),(5,4),(5,6)]\nproducto :: [a] -> [a] -> [(a,a)]\nproducto xs ys =\n  [(x,y) | x <- xs, y <- ys]\n\n-- (relacionados g (x,y)) se verifica si los elementos x e y est\u00e1n\n-- relacionados por la relaci\u00f3n de grafo g. Por ejemplo,\n--    relacionados [(2,3),(3,1)] (2,3)  ==  True\n--    relacionados [(2,3),(3,1)] (3,2)  ==  True\n--    relacionados [(2,3),(3,1)] (1,2)  ==  False\nrelacionados :: Eq a => [(a,a)] -> (a,a) -> Bool\nrelacionados g (x,y) =\n  (x,y) `elem` g || (y,x) `elem` g\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntotal3 :: Eq a => Rel a -> Bool\ntotal3 (R (u,g)) = aux1 u\n  where aux1 []       = True\n        aux1 (x:xs)   = aux2 x u && aux1 xs\n        aux2 _ []     = True\n        aux2 x (y:ys) = relacionados g (x,y) && aux2 x ys\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_total :: Rel Int -> Bool\nprop_total r =\n  all (== total r)\n      [total2 r,\n       total3 r]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_total\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef total(r: Rel[A]) -> bool:\n    (u, g) = r\n    return all(((x, y) in g or (y, x) in g for x in u for y in u))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\n# producto(xs, ys) es el producto cartesiano de xs e ys. Por ejemplo,\n#    >>> producto([2, 5], [1, 4, 6])\n#    [(2, 1), (2, 4), (2, 6), (5, 1), (5, 4), (5, 6)]\ndef producto(xs: list[A], ys: list[A]) -> list[tuple[A,A]]:\n    return [(x, y) for x in xs for y in ys]\n\n# relacionados(g, (x, y)) se verifica si los elementos x e y est\u00e1n\n# relacionados por la relaci\u00f3n de grafo g. Por ejemplo,\n#    relacionados([(2, 3), (3, 1)], (2, 3))  ==  True\n#    relacionados([(2, 3), (3, 1)], (3, 2))  ==  True\n#    relacionados([(2, 3), (3, 1)], (1, 2))  ==  False\ndef relacionados(g: list[tuple[A,A]], p: tuple[A,A]) -> bool:\n    (x, y) = p\n    return (x, y) in g or (y, x) in g\n\ndef total2(r: Rel[A]) -> bool:\n    (u, g) = r\n    return all(relacionados(g, p) for p in producto(u, u))\n\n# 3\u00aa soluci\u00f3n\n# ===========\n\ndef total3(r: Rel[A]) -> bool:\n    u, g = r\n    return all(relacionados(g, (x, y)) for x in u for y in u)\n\n# 4\u00aa soluci\u00f3n\n# ===========\n\ndef total4(r: Rel[A]) -> bool:\n    (u, g) = r\n    def aux2(x: A, ys: list[A]) -> bool:\n        if not ys:\n            return True\n        return relacionados(g, (x, ys[0])) and aux2(x, ys[1:])\n\n    def aux1(xs: list[A]) -> bool:\n        if not xs:\n            return True\n        return aux2(xs[0], u) and aux1(xs[1:])\n\n    return aux1(u)\n\n# 5\u00aa soluci\u00f3n\n# ===========\n\ndef total5(r: Rel[A]) -> bool:\n    (u, g) = r\n    for x in u:\n        for y in u:\n            if not relacionados(g, (x, y)):\n                return False\n    return True\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_total(n: int) -> None:\n    r = relacionArbitraria(n)\n    res = total(r)\n    assert total2(r) == res\n    assert total3(r) == res\n    assert total4(r) == res\n    assert total5(r) == res\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Relaciones_totales.py\n#    1 passed in 0.11s\n<\/pre>\n<p><a name=\"ej8\"><\/a><\/p>\n<h3>8. Clausura reflexiva<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   clausuraReflexiva :: Eq a => Rel a -> Rel a\n<\/pre>\n<p>tal que <code>clausuraReflexiva r<\/code> es la clausura reflexiva de <code>r<\/code>; es decir, la menor relaci\u00f3n reflexiva que contiene a r. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> clausuraReflexiva (R ([1,3],[(1,1),(3,1)]))\n   R ([1,3],[(1,1),(3,1),(3,3)])\n<\/pre>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Data.List (union)\nimport Test.QuickCheck (quickCheck)\n\nclausuraReflexiva :: Eq a => Rel a -> Rel a\nclausuraReflexiva (R (u,g)) =\n  R (u, g `union` [(x,x) | x <- u])\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom src.Relaciones_binarias import Rel\n\nA = TypeVar('A')\n\ndef clausuraReflexiva(r: Rel[A]) -> Rel[A]:\n    (u, g) = r\n    return (u, list(set(g) | {(x, x) for x in u}))\n<\/pre>\n<p><a name=\"ej9\"><\/a><\/p>\n<h3>9. Clausura sim\u00e9trica<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   clausuraSimetrica :: Eq a => Rel a -> Rel a\n<\/pre>\n<p>tal que <code>clausuraSimetrica r<\/code> es la clausura sim\u00e9trica de <code>r<\/code>; es decir, la menor relaci\u00f3n sim\u00e9trica que contiene a r. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> clausuraSimetrica (R ([1,3,5],[(1,1),(3,1),(1,5)]))\n   R ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)])\n<\/pre>\n<p>Comprobar con QuickCheck que clausuraSimetrica es sim\u00e9trica.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Data.List (union)\nimport Relaciones_simetricas (simetrica)\nimport Test.QuickCheck\n\nclausuraSimetrica :: Eq a => Rel a -> Rel a\nclausuraSimetrica (R (u,g)) =\n  R (u, g `union` [(y,x) | (x,y) <- g])\n\n-- La propiedad es\nprop_ClausuraSimetrica :: Rel Int -> Bool\nprop_ClausuraSimetrica r =\n  simetrica (clausuraSimetrica r)\n\n-- La funci\u00f3n simetrica est\u00e1 definida en el ejercicio\n-- \"Relaciones sim\u00e9tricas\" que se encuentra en\n-- https:\/\/bit.ly\/3zlO2rH\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_ClausuraSimetrica\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\nfrom src.Relaciones_simetricas import simetrica\n\nA = TypeVar('A')\n\ndef clausuraSimetrica(r: Rel[A]) -> Rel[A]:\n    (u, g) = r\n    return (u, list(set(g) | {(y, x) for (x,y) in g}))\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_irreflexiva(n: int) -> None:\n    r = relacionArbitraria(n)\n    assert simetrica(clausuraSimetrica(r))\n\n# La funci\u00f3n simetrica est\u00e1 definida en el ejercicio\n# \"Relaciones sim\u00e9tricas\" que se encuentra en\n# https:\/\/bit.ly\/3zlO2rH\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Clausura_simetrica.py\n#    1 passed in 0.12s\n<\/pre>\n<p><a name=\"ej10\"><\/a><\/p>\n<h3>10. Clausura transitiva<\/h3>\n<p>Usando el <a href=\"https:\/\/bit.ly\/3IVVqOT\">tipo de las relaciones binarias<\/a>, definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   clausuraTransitiva :: Eq a => Rel a -> Rel a\n<\/pre>\n<p>tal que <code>clausuraTransitiva r<\/code> es la clausura transitiva de <code>r<\/code>; es decir, la menor relaci\u00f3n transitiva que contiene a r. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> clausuraTransitiva (R ([1..6],[(1,2),(2,5),(5,6)]))\n   R ([1,2,3,4,5,6],[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)])\n<\/pre>\n<p>Comprobar con QuickCheck que clausuraTransitiva es transitiva.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport Relaciones_binarias (Rel(R))\nimport Relaciones_transitivas (transitiva)\nimport Data.List (union)\nimport Test.QuickCheck\n\n--  1\u00aa soluci\u00f3n\n--  ===========\n\nclausuraTransitiva :: Ord a => Rel a -> Rel a\nclausuraTransitiva (R (u,g)) = R (u, aux g)\n  where\n    aux u' | cerradoTr u' = u'\n           | otherwise    = aux (u' `union` comp u' u')\n    cerradoTr r       = subconjunto (comp r r) r\n    comp r s          = [(x,z) | (x,y) <- r, (y',z) <- s, y == y']\n    subconjunto xs ys = all (`elem` ys) xs\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nclausuraTransitiva2 :: Ord a => Rel a -> Rel a\nclausuraTransitiva2 (R (u,g)) =\n  R (u, until cerradoTr (\\r -> r `union` comp r r) g)\n  where\n    cerradoTr r       = subconjunto (comp r r) r\n    comp r s          = [(x,z) | (x,y) <- r, (y',z) <- s, y == y']\n    subconjunto xs ys = all (`elem` ys) xs\n\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_clausuraTransitiva :: Rel Int -> Bool\nprop_clausuraTransitiva r =\n  clausuraTransitiva r == clausuraTransitiva2 r\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_clausuraTransitiva\n--    +++ OK, passed 100 tests.\n\n-- Propiedad\n-- =========\n\n-- La propiedad es\nprop_clausuraTransitivaEsTransitiva :: Rel Int -> Bool\nprop_clausuraTransitivaEsTransitiva r =\n  transitiva (clausuraTransitiva r)\n\n-- La funci\u00f3n transitiva est\u00e1 definida en el ejercicio\n-- \"Relaciones transitivas\" que se encuentra en\n-- https:\/\/bit.ly\/42WRPJv\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_clausuraTransitivaEsTransitiva\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.Relaciones_binarias import Rel, relacionArbitraria\nfrom src.Relaciones_transitivas import transitiva\n\nA = TypeVar('A')\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef clausuraTransitiva(r: Rel[A]) -> Rel[A]:\n    (u, g) = r\n\n    def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool:\n        return set(xs) <= set(ys)\n\n    def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]:\n        return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1})\n\n    def cerradoTr(r: list[tuple[A, A]]) -> bool:\n        return subconjunto(comp(r, r), r)\n\n    def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]:\n        return xs + [y for y in ys if y not in xs]\n\n    def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]:\n        if cerradoTr(u1):\n            return u1\n        return aux(union(u1, comp(u1, u1)))\n\n    return (u, aux(g))\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef clausuraTransitiva2(r: Rel[A]) -> Rel[A]:\n    (u, g) = r\n\n    def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool:\n        return set(xs) <= set(ys)\n\n    def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]:\n        return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1})\n\n    def cerradoTr(r: list[tuple[A, A]]) -> bool:\n        return subconjunto(comp(r, r), r)\n\n    def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]:\n        return xs + [y for y in ys if y not in xs]\n\n    def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]:\n        if cerradoTr(u1):\n            return u1\n        return aux(union(u1, comp(u1, u1)))\n\n    g1: list[tuple[A, A]] = g\n    while not cerradoTr(g1):\n        g1 = union(g1, comp(g1, g1))\n    return (u, g1)\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_clausuraTransitiva(n: int) -> None:\n    r = relacionArbitraria(n)\n    assert clausuraTransitiva(r) == clausuraTransitiva2(r)\n\n# Propiedad\n# =========\n\n# La propiedad es\n@given(st.integers(min_value=0, max_value=10))\ndef test_cla(n: int) -> None:\n    r = relacionArbitraria(n)\n    assert transitiva(clausuraTransitiva(r))\n\n# La funci\u00f3n transitiva est\u00e1 definida en el ejercicio\n# \"Relaciones transitivas\" que se encuentra en\n# https:\/\/bit.ly\/42WRPJv\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q Clausura_transitiva.py\n#    2 passed in 0.16s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Estas dos \u00faltimas semanas he publicado en Exercitium las soluciones de los siguientes problemas: 1. Composici\u00f3n de relaciones binarias 2. Reconocimiento de subconjunto 3. Relaciones transitivas 4. Relaciones de equivalencia 5. Relaciones irreflexivas 6. Relaciones antisim\u00e9tricas 7. Relaciones totales 8. Clausura reflexiva 9. Clausura sim\u00e9trica 10. Clausura transitiva A continuaci\u00f3n se muestran las soluciones.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[337],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7924"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=7924"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7924\/revisions"}],"predecessor-version":[{"id":7925,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/7924\/revisions\/7925"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=7924"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=7924"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=7924"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}