Ir al contenido principal

Simplificación de expresiones proposicionales

Misceláneas

El siguiente tipo de dato algebraico representa las fórmulas proposicionales construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):

data Form = X
          | V
          | F
          | Neg Form
          | Dis Form Form
          deriving (Eq, Ord, Show)

Por ejemplo, la fórmula (¬X v V) se representa por (Dis (Neg X) V).

Definir las funciones

valor      :: Form -> Bool -> Bool
simplifica :: Form -> Form

tales que (valor p i) es el valor de la fórmula p cuando se le asigna a X el valor i. Por ejemplo,

valor (Neg X) True           ==  False
valor (Neg F) True           ==  True
valor (Dis X (Neg X)) True   ==  True
valor (Dis X (Neg X)) False  ==  True

y (simplifica p) es una forma obtenida aplicándole a p las siguientes reglas de simplificación:

Neg V       = F
Neg F       = V
Neg (Neg q) = q
Dis V q     = V
Dis F q     = q
Dis q V     = V
Dis q F     = F
Dis q q     = q

Por ejemplo,

simplifica (Dis X (Neg (Neg X)))                      ==  X
simplifica (Neg (Dis (Neg (Neg X)) F))                ==  Neg X
simplifica (Dis (Neg F) F)                            ==  V
simplifica (Dis (Neg V) (Neg (Dis (Neg X) F)))        ==  X
simplifica (Dis (Neg V) (Neg (Dis (Neg (Neg X)) F)))  ==  Neg X

Comprobar con QuickCheck que para cualquier fórmula p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).

Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de fórmulas proposicionales

import Test.QuickCheck
import Control.Monad

data Form = X
          | V
          | F
          | Neg Form
          | Dis Form Form
          deriving (Eq, Ord, Show)

valor :: Form -> Bool -> Bool
valor = undefined

simplifica :: Form -> Form
simplifica = undefined

-- La propiedad es
prop_simplifica :: Form -> Bool -> Bool
prop_simplifica p i = undefined

-- La comprobación es

-- Generador de fórmulas
instance Arbitrary Form where
    arbitrary = sized form
        where form n | n <= 0    = atom
                     | otherwise = oneof [ atom
                                         , liftM Neg subform
                                         , liftM2 Dis subform subform ]
                     where atom    = oneof [elements [X,V,F]]
                           subform = form (n `div` 2)

Leer más…

2015 y los números con factorización capicúa

Misceláneas

Un número tiene factorización capicúa si puede escribir como un producto de números primos tal que la concatenación de sus dígitos forma un número capicúa. Por ejemplo, el 2015 tiene factorización capicúa ya que 2015 = 13531, los factores son primos y su concatenación es 13531 que es capicúa.

Definir la sucesión

conFactorizacionesCapicuas :: [Int]

formada por los números que tienen factorización capicúa. Por ejemplo,

λ> take 20 conFactorizacionesCapicuas
[1,2,3,4,5,7,8,9,11,12,16,18,20,25,27,28,32,36,39,44]

Usando conFactorizacionesCapicuas escribir expresiones cuyos valores sean las respuestas a las siguientes preguntas y calcularlas

  1. ¿Qué lugar ocupa el 2015 en la sucesión?
  2. ¿Cuál fue el anterior año con factorización capicúa?
  3. ¿Cuál será el siguiente año con factorización capicúa?

Soluciones

import Data.List (permutations)

conFactorizacionesCapicuas :: [Int]
conFactorizacionesCapicuas =
    [n | n <- [1..], not (null (factorizacionesCapicua n))]

-- (factorizacionesCapicua n) es la lista de las factorizaciones
-- capicúas de n. Por ejemplo,
--    factorizacionesCapicua 2015  ==  [[13,5,31],[31,5,13]]
factorizacionesCapicua :: Int -> [[Int]]
factorizacionesCapicua n =
    [xs | xs <- permutations (factorizacion n),
          esCapicuaConcatenacion xs]

-- (factorizacion n) es la lista de todos los factores primos de n; es
-- decir, es una lista de números primos cuyo producto es n. Por ejemplo,
--    factorizacion 300  ==  [2,2,3,5,5]
factorizacion :: Int -> [Int]
factorizacion n | n == 1    = []
                | otherwise = x : factorizacion (div n x)
    where x = menorFactor n

-- (menorFactor n) es el menor factor primo de n. Por ejemplo,
--    menorFactor 15  ==  3
--    menorFactor 16  ==  2
--    menorFactor 17  == 17
menorFactor :: Int -> Int
menorFactor n = head [x | x <- [2..], rem n x == 0]

-- (esCapicuaConcatenacion xs) se verifica si la concatenación de los
-- números de xs es capicúa. Por ejemplo,
--    esCapicuaConcatenacion [13,5,31]   ==  True
--    esCapicuaConcatenacion [135,31]    ==  True
--    esCapicuaConcatenacion [135,21]    ==  False
esCapicuaConcatenacion :: [Int] -> Bool
esCapicuaConcatenacion xs = ys == reverse ys
    where ys = concat (map show xs)

-- El cálculo de la 1ª respuesta es
--    λ> length (takeWhile (<= 2015) conFactorizacionesCapicuas)
--    265

-- El cálculo de la 2ª respuesta es
--    λ> last (takeWhile (<2015) conFactorizacionesCapicuas)
--    2001

-- El cálculo de la 3ª respuesta es
--    λ> head (dropWhile (<=2015) conFactorizacionesCapicuas)
--    2023

Período de una lista

Misceláneas

El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período "abababab" es "ab" ya que "abababab" se obtiene repitiendo tres veces la lista "ab".

Definir la función

periodo :: Eq a => [a] -> [a]

tal que (periodo xs) es el período de xs. Por ejemplo,

periodo "ababab"      ==  "ab"
periodo "buenobueno"  ==  "bueno"
periodo "oooooo"      ==  "o"
periodo "sevilla"     ==  "sevilla"

Leer más…

La función suelo

Misceláneas

La función suelo asigna a cada número real el número entero más próximo por defecto; es decir, el mayor número entero igual o menor que ese número real. Por ejemplo, al -2.4 le asigna el -3 y al 1.7 el 1.

Haskell tiene una implementación de la función suelo llamada floor. El objetivo de este ejercicio es redefinir dicha función; es decir, definir la función

suelo :: Float -> Integer

tal que (suelo x) es el suelo de x. Por ejemplo,

suelo (-2.7)  ==  -3
suelo (-2.4)  ==  -3
suelo (-2)    ==  -2
suelo 0       ==   0
suelo 2       ==   2
suelo 2.4     ==   2
suelo 2.7     ==   2

Comprobar con QuickCheck que las funciones suelo y floor son equivalentes.

Leer más…

Enumeración de los pares de números naturales

Misceláneas

Los pares de los números naturales se pueden ordenar por la suma de sus componentes y entres los pares con la misma suma elegir antes al que tiene mayos su primera componente.

Definir la función

pares :: [(Int,Int)]

tal que pares es la lista de los pares de números naturales con el orden anterior. por ejemplo,

λ> take 10 pares
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3)]

Usando la definición de pares, definir la función

posicion :: (Int,Int) -> Int

tal que (posicion p) es la posición del par p en la lista pares. Por ejemplo,

posicion (0,0)  ==  0
posicion (2,0)  ==  3

Finalmente, comprobar con QuickCheck que para cualquier par (x,y) de números naturales, la (posicion (x,y)) es igual a (y + (x+y+1)*(x+y) div 2).

Nota. En la comprobación usar

quickCheckWith (stdArgs {maxSize=7}) prop_posicion

Leer más…

Elementos más frecuentes

Misceláneas

Definir la función

masFrecuentes :: Ord a => Int -> [a] -> [(Int,a)]

tal que (masFrecuentes n xs) es la lista de los pares formados por los elementos de xs que aparecen más veces junto con el número de veces que aparecen. Por ejemplo,

λ> masFrecuentes 2 "trianera"
[(2,'r'),(2,'a')]
λ> masFrecuentes 2 "interdisciplinariedad"
[(5,'i'),(3,'d')]
λ> masFrecuentes 3 (show (product [1..10000]))
[(5803,'0'),(3416,'2'),(3341,'4')]

Leer más…

Puntos en regiones rectangulares

Misceláneas

Los puntos se puede representar mediante pares de números

type Punto = (Float,Float)

y las regiones rectangulares mediante el siguiente tipo de dato

   data Region = Rectangulo Punto  Punto
               | Union      Region Region
               | Diferencia Region Region
               deriving (Eq, Show)

donde

  • (Rectangulo p1 p2) es la región formada por un rectángulo cuyo vértice superior izquierdo es p1 y su vértice inferior derecho es p2.
  • (Union r1 r2) es la región cuyos puntos pertenecen a alguna de las regiones r1 y r2.
  • (Diferencia r1 r2) es la región cuyos puntos pertenecen a la región r1 pero no pertenecen a la r2.

Definir la función

enRegion :: Punto -> Region -> Bool

tal que (enRegion p r) se verifica si el punto p pertenece a la región r. Por ejemplo, usando las regiones definidas por

r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)

se tiene

enRegion (1.6,0.7) r0021                               ==  True
enRegion (3.6,0.7) r0021                               ==  False
enRegion (1,1) (Union r0021 r3051)                     ==  True
enRegion (4,0) (Union r0021 r3051)                     ==  True
enRegion (4,2) (Union r0021 r3051)                     ==  False
enRegion (3,1) (Diferencia r3051 r4162)                ==  True
enRegion (4,1) (Diferencia r3051 r4162)                ==  False
enRegion (4,2) (Diferencia r3051 r4162)                ==  False
enRegion (4,2) (Union (Diferencia r3051 r4162) r4162)  ==  True

Comprobar con QuickCheck que si el punto p está en la región r1, entonces, para cualquier región r2, p está en (Union r1 r2) y en (Union r2 r1), pero no está en (Diferencia r2 r1).

Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de regiones

import Test.QuickCheck
import Control.Monad

type Punto = (Float,Float)

data Region = Rectangulo Punto  Punto
            | Union      Region Region
            | Diferencia Region Region
            deriving (Eq, Show)

r0021, r3051, r4162 :: Region
r0021 = Rectangulo (0,0) (2,1)
r3051 = Rectangulo (3,0) (5,1)
r4162 = Rectangulo (4,1) (6,2)

enRegion :: Punto -> Region -> Bool
enRegion = undefined

-- La propiedad es
prop_enRegion p r1 r2 = undefined

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxDiscardRatio=20}) prop_enRegion
--    +++ OK, passed 100 tests.

-- Generador de regiones:
instance Arbitrary Region where
    arbitrary = sized arb where
        arb 0         = liftM2 Rectangulo arbitrary arbitrary
        arb n | n > 0 = oneof [liftM2 Rectangulo arbitrary arbitrary,
                               liftM2 Union sub sub,
                               liftM2 Diferencia sub sub]
              where sub = arb (n `div` 2)

Leer más…

Desemparejamiento de listas

Misceláneas

Definir la función

desemparejada :: [(a,b)] -> ([a],[b])

tal que (desemparejada ps) es el par de lista (xs,ys) tal que al emparejar (con zip) xs e ys devuelve ps. Por ejemplo,

λ> desemparejada [(3,'l'),(2,'u'),(5,'i'),(9,'s')]
([3,2,5,9],"luis")

Comprobar con QuickCheck que

  • desemparejada es equivalente a la función predefinida unzip.
  • si el valor de (desemparejada ps) es (xs,ys), entonces (zip xs ys) es igual a ps.

Leer más…

2015 y los números tales que la suma de sus dígitos es igual al número de sus divisores

Misceláneas

Una propiedad del 2015 es que la suma de sus dígitos coincide con el número de sus divisores; en efecto, la suma de sus dígitos es 2+0+1+5=8 y tiene 8 divisores (1, 5, 13, 31, 65, 155, 403 y 2015).

Definir la sucesión

especiales :: [Int]

formada por los números n tales que la suma de los dígitos de n coincide con el número de divisores de n. Por ejemplo,

take 12 especiales == [1,2,11,22,36,84,101,152,156,170,202,208]

Usar la sucesión para responder las siguientes cuestiones

  • ¿Cuántos años hasta el 2015 inclusive han cumplido la propiedad?
  • ¿Cuál fue el anterior al 2015 que cumplió la propiedad?
  • ¿Cuál será el siguiente al 2015 que cumplirá la propiedad?

Nota: La sucesión especiales es la misma que la A057531 de la OEIS (On-Line Encyclopedia of Integer Sequences).

Leer más…

2015 como raíz cuadrada de la suma de tres cubos

Misceláneas

Todos los años, en las proximidades del final de año suelen aparecer cuestiones con propiedades del número del nuevo año. Una sobre el 2015 es la publicada el martes en la entrada 2015 como raíz de la suma de tres cubos del blog Números y algo más en la que se pide calcular tres números tales que 2015 sea igual a la raíz cuadrada de la suma de dichos tres números.

A partir de dicha entrada, se propone el siguiente problema: Definir la sucesión

raicesCuadradasDeSumasDe3Cubos :: [Integer]

cuyos elementos son los números que se pueden escribir como raíces cuadradas de sumas de tres cubos. Por ejemplo,

take 9 raicesCuadradasDeSumasDe3Cubos = [6,9,15,27,48,72,53,59,78]

El 6 está en la sucesión porque 1³+2³+3³ = 36 y la raíz cuadrada de36 es 6 y el 9 está porque 3³+3³+3³ = 81 y la raíz cuadrada de 81 es 9. Algunos números tienen varias descomposiones como raíz cuadrada de suma de tres cubos; por ejemplo, el 71 se puede escribir como la raíz cuadrada de la suma de los cubos de 6, 9 y 16 y también como la de 4, 4, y 17.

A partir de la sucesión se plantean las siguientes cuestiones:

  • ¿Qué lugar ocupa el 2015 en la sucesión?
  • ¿Cuál será el próximo año que se podrá escribir como la raíz cuadrada de suma de tres cubos?
  • ¿Cuáles son las descomposiciones de 2015 como raíz cuadrada de suma de tres cubos?
  • ¿Cuáles son los años hasta el 2015 que se pueden escribir como raíz cuadrada de suma de tres cubos de más formas distintas?

Leer más…