Relaciones antisimétricas
Usando el tipo de las relaciones binarias, definir la función
|
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,
|
1 2 3 |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
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. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
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 |