elem

Modelos de FNC (fórmulas en forma normal conjuntiva)

PorJosé A. Alonso 17-febrero-202024-febrero-2020

Nota: En este ejercicio usaremos las mismas notaciones que en anterior importando los módulos Interpretaciones_de_FNC y Evaluacion_de_FNC

Una interpretación I es un modelo de un literal L si el valor de L en I es verdadero. Por ejemplo, la interpretación [2,5]

es modelo del literal x(2) (porque 2 ∈ [2,5])
no es modelo del literal x(3) (porque 3 ∉ [2,5])
es modelo del literal -x(4) (porque 4 ∉ [2,5])

Una interpretación I es un modelo de una cláusula C si el valor de C en I es verdadero. Por ejemplo, la interpretación [2,5]

es modelo de la cláusula (x(2) v x(3)) (porque x(2) es verdadero)
no es modelo de la cláusula (x(3) v x(4)) (porque x(3) y x(4) son falsos)

Una interpretación I es un modelo de una FNC F si el valor de F en I es verdadero. Por ejemplo, la interpretación [2,5]

es modelo de la FNC ((x(2) v x(5)) & (-x(4) v x(3)) porque lo es de sus dos cláusulas.

Definir las siguientes funciones

   esModeloLiteral  :: Interpretacion -> Literal -> Bool
   esModeloClausula :: Interpretacion -> Clausula -> Bool
   esModelo         :: Interpretacion -> FNC -> Bool
   modelosClausula  :: Clausula -> [Interpretacion]
   modelos          :: FNC -> [Interpretacion]

esModeloLiteral :: Interpretacion -> Literal -> Bool

esModeloClausula :: Interpretacion -> Clausula -> Bool

esModelo :: Interpretacion -> FNC -> Bool

modelosClausula :: Clausula -> [Interpretacion]

modelos :: FNC -> [Interpretacion]

tales que

(esModeloLiteral i l) se verifica si i es modelo del literal l. Por ejemplo,

     esModeloLiteral [3,5] 3     ==  True
     esModeloLiteral [3,5] 4     ==  False
     esModeloLiteral [3,5] (-3)  ==  False
     esModeloLiteral [3,5] (-4)  ==  True

esModeloLiteral [3,5] 3 == True

esModeloLiteral [3,5] 4 == False

esModeloLiteral [3,5] (-3) == False

esModeloLiteral [3,5] (-4) == True

(esModeloClausula i c) se verifica si i es modelo de la cláusula c. Por ejemplo,

     esModeloClausula [3,5] [2,3,-5]  ==  True
     esModeloClausula [3,5] [2,4,-1]  ==  True
     esModeloClausula [3,5] [2,4,1]   ==  False

esModeloClausula [3,5] [2,3,-5] == True

esModeloClausula [3,5] [2,4,-1] == True

esModeloClausula [3,5] [2,4,1] == False

(esModelo i f) se verifica si i es modelo de la fórmula f. Por ejemplo,

     esModelo [1,3] [[1,-2],[3]]  ==  True
     esModelo [1]   [[1,-2],[3]]  ==  False
     esModelo [1]   []            ==  True

esModelo [1,3] [[1,-2],[3]] == True

esModelo [1] [[1,-2],[3]] == False

esModelo [1] [] == True

(modelosClausula c) es la lista de los modelos de la cláusula c. Por ejemplo,

     modelosClausula [-1,2]  ==  [[],[2],[1,2]]
     modelosClausula [-1,1]  ==  [[],[1]]
     modelosClausula []      ==  []

modelosClausula [-1,2] == [[],[2],[1,2]]

modelosClausula [-1,1] == [[],[1]]

modelosClausula [] == []

(modelos f) es la lista de los modelos de la fórmula f. Por ejemplo,

     modelos [[-1,2],[-2,1]]    ==  [[],[1,2]]
     modelos [[-1,2],[-2],[1]]  ==  []
     modelos [[1,-1,2]]         ==  [[],[1],[2],[1,2]]

modelos [[-1,2],[-2,1]] == [[],[1,2]]

modelos [[-1,2],[-2],[1]] == []

modelos [[1,-1,2]] == [[],[1],[2],[1,2]]

Nota: Escribir la solución en el módulo Modelos_de_FNC para poderlo usar en los siguientes ejercicios.

Soluciones

module Modelos_de_FNC where

import Interpretaciones_de_FNC 
import Evaluacion_de_FNC

esModeloLiteral :: Interpretacion -> Literal -> Bool
esModeloLiteral i l
  | l > 0     = l `elem` i
  | otherwise = negate l `notElem` i

esModeloClausula :: Interpretacion -> Clausula -> Bool
esModeloClausula i = any (esModeloLiteral i)

esModelo :: Interpretacion -> FNC -> Bool
esModelo i = all (esModeloClausula i)

modelosClausula :: Clausula -> [Interpretacion]
modelosClausula c =
  [i | i <- interpretacionesClausula c,
       esModeloClausula i c]

modelos :: FNC -> [Interpretacion]
modelos f =
  [i | i <- interpretaciones f,
       esModelo i f]

module Modelos_de_FNC where

import Interpretaciones_de_FNC

import Evaluacion_de_FNC

esModeloLiteral :: Interpretacion -> Literal -> Bool

esModeloLiteral i l

| l > 0 = l `elem` i

| otherwise = negate l `notElem` i

esModeloClausula :: Interpretacion -> Clausula -> Bool

esModeloClausula i = any (esModeloLiteral i)

esModelo :: Interpretacion -> FNC -> Bool

esModelo i = all (esModeloClausula i)

modelosClausula :: Clausula -> [Interpretacion]

modelosClausula c =

[i | i <- interpretacionesClausula c,

esModeloClausula i c]

modelos :: FNC -> [Interpretacion]

modelos f =

[i | i <- interpretaciones f,

esModelo i f]

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«Por muy correcto que parezca un teorema matemático, nunca hay que conformarse con que no haya algo imperfecto en él hasta obtener la impresión de qie es bello.»

George Boole.

Evaluación de FNC (fórmulas en forma normal conjuntiva)

PorJosé A. Alonso 12-febrero-202019-febrero-2020

Una FNC (fórmula en forma normal conjuntiva) es una conjunción de cláusulas, donde una cláusula es una disyunción de literales y un literal es un átomo o su negación. Por ejemplo,

   (x(1) v -x(3)) & x(2) & (-x(2) v x(3) v x(1))

1	(x(1) v -x(3)) & x(2) & (-x(2) v x(3) v x(1))

es una FNC con tres clásulas tales que la primera cláusula tiene 2 literales (x(1) y -x(3)), la segunda tiene 1 (x(2)) y la tercera tiene 3 (-x(2), x(3) y x(1)).

Usaremos las siguientes representaciones:

Los átomos se representan por enteros positivos. Por ejemplo, 3 representa x(3).
Los literales se representan por enteros. Por ejemplo, 3 representa el literal positivo x(3) y -5 el literal negativo -x(5).
Una cláusula es una lista de literales que representa la disyunción se sus literales. Por ejemplo, [3,2,-4] representa a (x(3) v x(2) v -x(4)).
Una fórmula en forma normal conjuntiva (FNC) es una lista de cláusulas que representa la conjunción de sus cláusulas. Por ejemplo, [[3,2],[-1,2,5]] representa a ((x(3) v x(2)) & (-x(1) v x(2) v x(5))).

Una interpretación I es un conjunto de átomos. Se supone que los átomos de I son verdaderos y los restantes son falsos. Por ejemplo, en la interpretación [2,5]

el literal x(2) es verdadero (porque 2 ∈ [2,5])
el literal x(3) es falso (porque 3 ∉ [2,5])
el literal -x(4) es verdadero (porque 4 ∉ [2,5])
la cláusula (x(2) v x(3)) es verdadera (porque x(2) es verdadero)
la cláusula (x(3) v x(4)) es falsa (porque x(3) y x(4) son falsos)
la FNC ((x(2) v x(5)) & (-x(4) v x(3)) es verdadera porque lo son sus dos cláusulas

En el ejercicio se usarán los siguientes tipos de datos

   type Atomo          = Int
   type Literal        = Int
   type Clausula       = [Literal]
   type FNC            = [Clausula]
   type Interpretacion = [Atomo]

type Atomo = Int

type Literal = Int

type Clausula = [Literal]

type FNC = [Clausula]

type Interpretacion = [Atomo]

Definir las siguientes funciones

   valorLiteral  :: Interpretacion -> Literal -> Bool
   valorClausula :: Interpretacion -> Clausula -> Bool
   valor         :: Interpretacion -> FNC -> Bool

valorLiteral :: Interpretacion -> Literal -> Bool

valorClausula :: Interpretacion -> Clausula -> Bool

valor :: Interpretacion -> FNC -> Bool

tales que

(valorLiteral i l) es el valor del literal l en la interpretación i. Por ejemplo,

     valorLiteral [3,5] 3     ==  True
     valorLiteral [3,5] 4     ==  False
     valorLiteral [3,5] (-3)  ==  False
     valorLiteral [3,5] (-4)  ==  True

valorLiteral [3,5] 3 == True

valorLiteral [3,5] 4 == False

valorLiteral [3,5] (-3) == False

valorLiteral [3,5] (-4) == True

(valorClausula i c) es el valor de la cláusula c en la interpretación i. Por ejemplo,

     valorClausula [3,5] [2,3,-5]  ==  True
     valorClausula [3,5] [2,4,-1]  ==  True
     valorClausula [3,5] [2,4,1]   ==  False

valorClausula [3,5] [2,3,-5] == True

valorClausula [3,5] [2,4,-1] == True

valorClausula [3,5] [2,4,1] == False

(valor i f) es el valor de la fórmula en FNC f en la interpretación i. Por ejemplo,

     valor [1,3] [[1,-2],[3]]  ==  True
     valor [1]   [[1,-2],[3]]  ==  False
     valor [1]   []            ==  True

valor [1,3] [[1,-2],[3]] == True

valor [1] [[1,-2],[3]] == False

valor [1] [] == True

Nota: Escribir la solución en el módulo Evaluacion_de_FNC para poderlo usar en los siguientes ejercicios.

Soluciones

module Evaluacion_de_FNC where

type Atomo          = Int
type Literal        = Int
type Clausula       = [Literal]
type FNC            = [Clausula]
type Interpretacion = [Atomo]

-- Definición de valorLiteral
-- ==========================

valorLiteral :: Interpretacion -> Literal -> Bool
valorLiteral i l
  | l > 0     = l `elem` i
  | otherwise = negate l `notElem` i

-- Definiciones de valorClausula
-- =============================

-- 1ª definición
valorClausula :: Interpretacion -> Clausula -> Bool
valorClausula i c = or [valorLiteral i l | l <- c]

-- 2ª definición
valorClausula2 :: Interpretacion -> Clausula -> Bool
valorClausula2 i = any (valorLiteral i)

-- Definiciones de valor de FNC
-- ============================

-- 1ª definición
valor :: Interpretacion -> FNC -> Bool
valor i f = and [valorClausula i c | c <- f]

-- 2ª definición
valor2 :: Interpretacion -> FNC -> Bool
valor2 i = all (valorClausula i)

module Evaluacion_de_FNC where

type Atomo = Int

type Literal = Int

type Clausula = [Literal]

type FNC = [Clausula]

type Interpretacion = [Atomo]

-- Definición de valorLiteral

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

valorLiteral :: Interpretacion -> Literal -> Bool

valorLiteral i l

| l > 0 = l `elem` i

| otherwise = negate l `notElem` i

-- Definiciones de valorClausula

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

-- 1ª definición

valorClausula :: Interpretacion -> Clausula -> Bool

valorClausula i c = or [valorLiteral i l | l <- c]

-- 2ª definición

valorClausula2 :: Interpretacion -> Clausula -> Bool

valorClausula2 i = any (valorLiteral i)

-- Definiciones de valor de FNC

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

-- 1ª definición

valor :: Interpretacion -> FNC -> Bool

valor i f = and [valorClausula i c | c <- f]

-- 2ª definición

valor2 :: Interpretacion -> FNC -> Bool

valor2 i = all (valorClausula i)

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«Todo buen matemático es al menos medio filósofo, y todo buen filósofo es al menos medio matemático.»

Gottlob Frege.

Conjetura de Collatz generalizada

PorJosé A. Alonso 10-febrero-202017-febrero-2020

Sea p un número primo. Toma un número natural positivo, si es divisible entre un número primo menor que p divídelo entre el menor de dicho divisores, y en otro caso multiplícalo por p y súmale uno; si el resultado no es igual a uno, repite el proceso. Por ejemplo, para p = 7 y empezando en 42 el proceso es

   42
   -> 21   [= 42/2]
   -> 7    [= 21/3]
   -> 50   [= 7*7+1]
   -> 25   [= 50/5]
   -> 5    [= 25/5]
   -> 1    [= 5/5]

-> 21 [= 42/2]

-> 7 [= 21/3]

-> 50 [= 7*7+1]

-> 25 [= 50/5]

-> 5 [= 25/5]

-> 1 [= 5/5]

La conjetura de Collatz generalizada afirma que este proceso siempre acaba en un número finito de pasos.

Definir la función

   collatzGeneral :: Integer -> Integer -> [Integer]

1	collatzGeneral :: Integer -> Integer -> [Integer]

tal que (collatzGeneral p x) es la sucesión de los elementos obtenidos en el proceso anterior para el primo p enpezando en x. Por ejemplo,

   take 15 (collatzGeneral 7 42) == [42,21,7,50,25,5,1,8,4,2,1,8,4,2,1]
   take 15 (collatzGeneral 3  6) == [6,3,10,5,16,8,4,2,1,4,2,1,4,2,1]
   take 15 (collatzGeneral 5  6) == [6,3,1,6,3,1,6,3,1,6,3,1,6,3,1]
   take 15 (collatzGeneral 7  6) == [6,3,1,8,4,2,1,8,4,2,1,8,4,2,1]
   take 15 (collatzGeneral 9  6) == [6,3,1,10,5,1,10,5,1,10,5,1,10,5,1]

take 15 (collatzGeneral 7 42) == [42,21,7,50,25,5,1,8,4,2,1,8,4,2,1]

take 15 (collatzGeneral 3 6) == [6,3,10,5,16,8,4,2,1,4,2,1,4,2,1]

take 15 (collatzGeneral 5 6) == [6,3,1,6,3,1,6,3,1,6,3,1,6,3,1]

take 15 (collatzGeneral 7 6) == [6,3,1,8,4,2,1,8,4,2,1,8,4,2,1]

take 15 (collatzGeneral 9 6) == [6,3,1,10,5,1,10,5,1,10,5,1,10,5,1]

Comprobar con QuickCheck que se verifica la conjetura de Collatz generalizada; es decir, para todos enteros positivos n, x si p es el primo n-ésimo entonces 1 pertenece a (collatzGeneral p x).

Nota: El ejercicio etá basado en el artículo Los primos de la conjetura de Collatz publicado la semana pasada por Francisco R. Villatoro en su blog La Ciencia de la Mula Francis.

Soluciones

import Data.Numbers.Primes (primeFactors, primes)
import Test.QuickCheck

collatzGeneral :: Integer -> Integer -> [Integer]
collatzGeneral p x =
  iterate (siguiente p) x

siguiente :: Integer -> Integer -> Integer
siguiente p x 
  | null xs   = p * x + 1
  | otherwise = x `div` head xs
  where xs = takeWhile (<p) (primeFactors x)

prop_collatzGeneral :: Int -> Integer -> Property
prop_collatzGeneral n x =
  n > 0 && x > 0 ==>
  1 `elem` collatzGeneral p x
  where p = primes !! n 

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

import Data.Numbers.Primes (primeFactors, primes)

import Test.QuickCheck

collatzGeneral :: Integer -> Integer -> [Integer]

collatzGeneral p x =

iterate (siguiente p) x

siguiente :: Integer -> Integer -> Integer

siguiente p x

| null xs = p * x + 1

| otherwise = x `div` head xs

where xs = takeWhile (<p) (primeFactors x)

prop_collatzGeneral :: Int -> Integer -> Property

prop_collatzGeneral n x =

n > 0 && x > 0 ==>

1 `elem` collatzGeneral p x

where p = primes !! n

-- La comprobación es

-- λ> quickCheck prop_collatzGeneral

-- +++ OK, passed 100 tests.

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«Las matemáticas son la ciencia que utiliza palabras fáciles para ideas difíciles.»

Edward Kasner y James R. Newman

Primer elemento repetido

PorJosé A. Alonso 28-enero-202026-marzo-2022

Definir la función

   primerRepetido :: Eq a => [a] -> Maybe a

1	primerRepetido :: Eq a => [a] -> Maybe a

tal que (primerRepetido xs) es justo el primer elemento repetido de la lista xs o Nothing si no tiene elementos repetidos. Por ejemplo,

   primerRepetido [3,7,5,7,2]  ==  Just 7
   primerRepetido [3,9,5,6,2]  ==  Nothing

1 2	primerRepetido [3,7,5,7,2] == Just 7 primerRepetido [3,9,5,6,2] == Nothing

Soluciones

primerRepetido :: Eq a => [a] -> Maybe a
primerRepetido xs = aux xs []
  where
    aux [] _                     = Nothing
    aux (x:xs') ys | x `elem` ys = Just x
                   | otherwise   = aux xs' (x:ys)

primerRepetido :: Eq a => [a] -> Maybe a

primerRepetido xs = aux xs []

where

aux [] _ = Nothing

aux (x:xs') ys | x `elem` ys = Just x

| otherwise = aux xs' (x:ys)

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

Pensamiento

«¿Cuál es el núcleo central de la ciencia de la computación? ¿Qué es lo que lo diferencia de los otros temas con los que se relaciona? ¿Qué es lo que el hilo de unión que reúne estas ramas dispares en una sola disciplina? Mi respuesta a estas preguntas es simple: es el arte de programar un ordenador. Es el arte de diseñar métodos eficientes y elegantes para conseguir que un ordenador resuelva problemas, teóricos o prácticos, pequeños o grandes, simples o complejos. Es el arte de traducir estos diseños programas correctos y eficientes.»

Tony Hoare.

Números de Munchausen

PorJosé A. Alonso 13-enero-202020-enero-2020

Un número de Munchausen es un número entero positivo tal que es igual a la suma de sus dígitos elevados a sí mismo. Por ejemplo, 3435 es un número de Munchausen ya que

   3³ + 4⁴ + 3³ + 5⁵ = 27 + 256 + 27 + 3125 = 3435

1	3³ + 4⁴ + 3³ + 5⁵ = 27 + 256 + 27 + 3125 = 3435

Definir la función

   esMunchausen :: Integer -> Bool

1	esMunchausen :: Integer -> Bool

tal que (esMunchausen n) se verifica si n es un número de Munchausen. Por ejemplo,

   esMunchausen 3435  ==  True
   esMunchausen 2020  ==  False

1 2	esMunchausen 3435 == True esMunchausen 2020 == False

Comprobar con QuickCheck que que los únicos números de Munchausen son 1 y 3435.

Nota 1: No usar la propiedad en la definición.

Nota 2: El ejercicio está basado en el artículo ¿Por qué 3435 es uno de mis números favoritos? de Miguel Ángel Morales en El Aleph.

Soluciones

import Test.QuickCheck

esMunchausen :: Integer -> Bool
esMunchausen n =
  n == sum [x^x | x <- digitos n]

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 3435  ==  [3,4,3,5]
digitos :: Integer -> [Integer]
digitos n = [read [c] | c <- show n]

-- La propiedad es
prop_Munchausen :: Integer -> Property
prop_Munchausen n =
  n > 0
  ==>
  esMunchausen n == elem n [1, 3435]

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

import Test.QuickCheck

esMunchausen :: Integer -> Bool

esMunchausen n =

n == sum [x^x | x <- digitos n]

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 3435 == [3,4,3,5]

digitos :: Integer -> [Integer]

digitos n = [read [c] | c <- show n]

-- La propiedad es

prop_Munchausen :: Integer -> Property

prop_Munchausen n =

n > 0

==>

esMunchausen n == elem n [1, 3435]

-- La comprobación es

-- λ> quickCheck prop_Munchausen

-- +++ OK, passed 100 tests.

Pensamiento

Escribiré en tu abanico:
te quiero para olvidarte,
para quererte te olvido.

Antonio Machado

Modelos de FNC (fórmulas en forma normal conjuntiva)

Soluciones

Otras soluciones

Pensamiento

Evaluación de FNC (fórmulas en forma normal conjuntiva)

Soluciones

Otras soluciones

Pensamiento

Conjetura de Collatz generalizada

Soluciones

Otras soluciones

Pensamiento

Primer elemento repetido

Soluciones

Otras soluciones

Pensamiento

Números de Munchausen

Soluciones

Pensamiento

Entradas recientes

Buscar

Correo electrónico