Ir al contenido principal

Simplificación de expresiones booleanas

Misceláneas

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

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

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

Definir las funciones

valor      :: Expr -> Bool -> Bool
simplifica :: Expr -> Expr

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 expresión 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).

Para la comprobación, de define el generador

instance Arbitrary Expr where
  arbitrary = sized expr
    where expr n | n <= 0    = atom
                 | otherwise = oneof [ atom
                                     , liftM Neg subexpr
                                     , liftM2 Dis subexpr subexpr ]
            where atom    = oneof [elements [X,V,F]]
                  subexpr = expr (n `div` 2)

que usa las funciones liftM y liftM2 de la librería Control.Monad que hay que importar al principio.

Leer más…

Cálculo de pi mediante la serie de Nilakantha

Misceláneas

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es

           4       4       4       4
pi = 3 + ----- - ----- + ----- - ------ + ···
         2x3x4   4x5x6   6x7x8   8x9x10

Definir las funciones

aproximacionPi :: Int -> Double
tabla          :: FilePath -> [Int] -> IO ()

tales que

  • (aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,
aproximacionPi 0        ==  3.0
aproximacionPi 1        ==  3.1666666666666665
aproximacionPi 2        ==  3.1333333333333333
aproximacionPi 3        ==  3.145238095238095
aproximacionPi 4        ==  3.1396825396825396
aproximacionPi 5        ==  3.1427128427128426
aproximacionPi 10       ==  3.1414067184965018
aproximacionPi 100      ==  3.1415924109719824
aproximacionPi 1000     ==  3.141592653340544
aproximacionPi 10000    ==  3.141592653589538
aproximacionPi 100000   ==  3.1415926535897865
aproximacionPi 1000000  ==  3.141592653589787
pi                      ==  3.141592653589793
  • (tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión
tabla "AproximacionesPi.txt" [0,10..100]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|   10 | 3.141406718497 | 0.000185935093 |
|   20 | 3.141565734659 | 0.000026918931 |
|   30 | 3.141584272675 | 0.000008380915 |
|   40 | 3.141589028941 | 0.000003624649 |
|   50 | 3.141590769850 | 0.000001883740 |
|   60 | 3.141591552546 | 0.000001101044 |
|   70 | 3.141591955265 | 0.000000698325 |
|   80 | 3.141592183260 | 0.000000470330 |
|   90 | 3.141592321886 | 0.000000331704 |
|  100 | 3.141592410972 | 0.000000242618 |
+------+----------------+----------------+

al evaluar la expresión

tabla "AproximacionesPi.txt" [0,500..5000]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|  500 | 3.141592651602 | 0.000000001988 |
| 1000 | 3.141592653341 | 0.000000000249 |
| 1500 | 3.141592653516 | 0.000000000074 |
| 2000 | 3.141592653559 | 0.000000000031 |
| 2500 | 3.141592653574 | 0.000000000016 |
| 3000 | 3.141592653581 | 0.000000000009 |
| 3500 | 3.141592653584 | 0.000000000006 |
| 4000 | 3.141592653586 | 0.000000000004 |
| 4500 | 3.141592653587 | 0.000000000003 |
| 5000 | 3.141592653588 | 0.000000000002 |
+------+----------------+----------------+

Leer más…

Sucesión de sumas de dos números abundantes

Misceláneas

Un número n es abundante si la suma de los divisores propios de n es mayor que n. El primer número abundante es el 12 (cuyos divisores propios son 1, 2, 3, 4 y 6 cuya suma es 16). Por tanto, el menor número que es la suma de dos números abundantes es el 24.

Definir la sucesión

sumasDeDosAbundantes :: [Integer]

cuyos elementos son los números que se pueden escribir como suma de dos números abundantes. Por ejemplo,

take 10 sumasDeDosAbundantes  ==  [24,30,32,36,38,40,42,44,48,50]

Leer más…

Particiones de enteros positivos

Misceláneas

Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.

Definir la función

particiones :: Int -> [[Int]]

tal que (particiones n) es la lista de las particiones del número n. Por ejemplo,

particiones 4  ==  [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]]
particiones 5  ==  [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]]
length (particiones 50)  ==  204226

Leer más…

Término ausente en una progresión aritmética

Misceláneas

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

ausente :: Integral a => [a] -> a

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

ausente [3,7,9,11]               ==  5
ausente [3,5,9,11]               ==  7
ausente [3,5,7,11]               ==  9
ausente ([1..9]++[11..])         ==  10
ausente ([1..10^6] ++ [2+10^6])  ==  1000001

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay un término de la progresión aritmética que no está en la lista.

Leer más…

Aritmética lunar.

Misceláneas

En la aritmética lunar la suma y el producto se hace como en la terrícola salvo que sus tablas de sumar y de multiplicar son distintas. La suma lunar de dos dígitos es su máximo (por ejemplo, 1 + 3 = 3 y 7 + 4 = 7) y el producto lunar de dos dígitos es su mínimo (por ejemplo, 1 x 3 = 1 y 7 x 4 = 4). Por tanto,

  3 5 7        3 5 7
+   6 4      x   6 4
-------      -------
  3 6 7        3 4 4
             3 5 6
             -------
             3 5 6 4

Definir las funciones

suma     :: Integer -> Integer -> Integer
producto :: Integer -> Integer -> Integer

tales que

  • (suma x y) es la suma lunar de x e y. Por ejemplo,
suma 357 64  ==  367
suma 64 357  ==  367
suma 1 3     ==  3
suma 7 4     ==  7
  • (producto x y) es el producto lunar de x e y. Por ejemplo,
producto 357 64  ==  3564
producto 64 357  ==  3564
producto 1 3     ==  1
producto 7 4     ==  4

Comprobar con QuickCheck que la suma y el producto lunar son conmutativos.

Leer más…

Exterior de árboles

Misceláneas

Los árboles binarios con datos en loas hojas y los nodos se definen por

data Arbol = H Int
           | N Int Arbol Arbol
  deriving Show

Por ejemplo, los árboles

       3               3               3
      / \             / \             / \
     /   \           /   \           /   \
    2     8         2     8         2     8
   / \   / \       / \   / \       / \   / \
  5   7 6   9     5   7 6   9     5   7 6   9
 / \                   / \                 / \
1   4                 1   4               1   4

se representan por

ejArbol1, ejArbol2, ejArbol3 :: Arbol
ejArbol1 = N 3
             (N 2
                (N 5 (H 1) (H 4))
                (H 7))
             (N 8 (H 6) (H 9))
ejArbol2 = N 3
             (N 2 (H 5) (H 7))
             (N 8 (N 6 (H 1) (H 4))
                  (H 9))
ejArbol3 = N 3
             (N 2 (H 5) (H 7))
             (N 8 (H 6)
                  (N 9 (H 1) (H 4)))

Definir la función

exterior :: Arbol -> [Int]

tal que (exterior a) es la lista de los elementos exteriores del árbol a. Por ejemplo,

exterior ejArbol1  ==  [3,2,5,1,4,7,6,9,8]
exterior ejArbol2  ==  [3,2,5,7,1,4,9,8]
exterior ejArbol3  ==  [3,2,5,7,6,1,4,9,8]

El orden de los elementos es desde la raíz hasta el extremo inferior izquierdo desde él hasta el inferior derecho y desde él hasta la raíz.

Leer más…

Medias de dígitos de pi

Misceláneas

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir las funciones

mediasDigitosDePi        :: IO [Double]
graficaMediasDigitosDePi :: Int -> IO ()

tales que

  • mediasDigitosDePi es la sucesión cuyo n-ésimo elemento es la media de los n primeros dígitos de pi. Por ejemplo,
λ> xs <- mediasDigitosDePi
λ> take 5 xs
[1.0,2.5,2.0,2.75,4.0]
λ> take 10 xs
[1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]
λ> take 10 <$> mediasDigitosDePi
[1.0,2.5,2.0,2.75,4.0,3.6666666666666665,4.0,4.125,4.0,4.1]
  • (graficaMediasDigitosDePi n) dibuja la gráfica de los n primeros términos de mediasDigitosDePi. Por ejemplo,
  • (graficaMediasDigitosDePi 20) dibuja Medias de dígitos de pi
  • (graficaMediasDigitosDePi 200) dibuja Medias de dígitos de pi
  • (graficaMediasDigitosDePi 2000) dibuja Medias de dígitos de pi

Leer más…

Límites de sucesiones

Misceláneas

El límite de una sucesión, con una aproximación a y una amplitud n, es el primer término x de la sucesión tal que el valor absoluto de x y cualquiera de sus n siguentes elementos es menor que a.

Definir la función

limite :: [Double] -> Double -> Int -> Double

tal que (limite xs a n) es el límite de xs xon aproximación a y amplitud n. Por ejemplo,

λ> limite [(2*n+1)/(n+5) | n <- [1..]] 0.001 300
1.993991989319092
λ> limite [(2*n+1)/(n+5) | n <- [1..]] 1e-6 300
1.9998260062637745
λ> limite [(1+1/n)**n | n <- [1..]] 0.001 300
2.7155953364173175

Leer más…

Dígitos en las posiciones pares de cuadrados

Misceláneas

Definir las funciones

digitosPosParesCuadrado    :: Integer -> ([Integer],Int)
invDigitosPosParesCuadrado :: ([Integer],Int) -> [Integer]

tales que

  • (digitosPosParesCuadrado n) es el par formados por los dígitos de n² en la posiciones pares y por el número de dígitos de n². Por ejemplo,
digitosPosParesCuadrado 8     ==  ([6],2)
digitosPosParesCuadrado 14    ==  ([1,6],3)
digitosPosParesCuadrado 36    ==  ([1,9],4)
digitosPosParesCuadrado 116   ==  ([1,4,6],5)
digitosPosParesCuadrado 2019  ==  ([4,7,3,1],7)
  • (invDigitosPosParesCuadrado (xs,k)) es la lista de los números n tales que xs es la lista de los dígitos de n² en la posiciones pares y k es el número de dígitos de n². Por ejemplo,
invDigitosPosParesCuadrado ([6],2)             ==  [8]
invDigitosPosParesCuadrado ([1,6],3)           ==  [14]
invDigitosPosParesCuadrado ([1,9],4)           ==  [36]
invDigitosPosParesCuadrado ([1,4,6],5)         ==  [116,136]
invDigitosPosParesCuadrado ([4,7,3,1],7)       ==  [2019,2139,2231]
invDigitosPosParesCuadrado ([1,2],3)           ==  []
invDigitosPosParesCuadrado ([1,2],4)           ==  [32,35,39]
invDigitosPosParesCuadrado ([1,2,3,4,5,6],11)  ==  [115256,127334,135254]

Comprobar con QuickCheck que para todo entero positivo n se verifica que para todo entero positivo m, m pertenece a (invDigitosPosParesCuadrado (digitosPosParesCuadrado n)) si, y sólo si, (digitosPosParesCuadrado m) es igual a (digitosPosParesCuadrado n)

Leer más…