27 noviembre 2012 – Vestigium

LI2012: Representación del conocimiento mediante lógica de primer orden

PorJosé A. Alonso 27 noviembre 20128 marzo 2013

En la primera parte de la clase de hoy del curso Lógica Informática se presentado la lógica de primer orden como sistema de representación del conocimiento.

La clase ha comenzado recordando la ecuación que resumen el curso: LI=RC+AR, donde LI = Lógica informática, RC = Representación del conocimiento y AR = Automatización del razonamiento.

Ya hemos estudiado el sistema básico de representación del conocimiento (la lógica proposicional) y tres sistemas deductivos (deducción natural, tableros semánticos y resolución). Además, hemos usado Prover9 y Mace4 para resolver problemas que se pueden codificar mediante la lógica proposicional, como el de las 4 reinas. Un inconveniente de las codificaciones es la cantidad y el tamaño de las fórmulas resultantes. En la clase vamos a ver una forma de reducir el tamaño de las codificaciones: la lógica de primer orden. Este sistema permite representar de forma más compacta conocimiento representable en lógica proposicional y también representar conocimiento que no se puede representar en lógica proposicional.

Como ejemplos de representación hemos visto cómo representar conocimiento geográfico, del mundo de los bloques y conocimiento astronómico. En los distintos ejemplos hemos resaltado los tipos de símbolos lógicos utilizados.

Como tutor para la representación del conocimiento, se ha presentado el APLI2 (APLIcación de Ayuda Para Lógica Informática).

En la segunda parte se ha estudiado la sintaxis de la lógica de primer orden resaltando los puntos en los que se amplia la lógica proposiconal.

Las transparencias de esta clase son las páginas 1 a 23 del tema 7:
Read More “LI2012: Representación del conocimiento mediante lógica de primer orden”

I1M2012: Ordenación por mezcla

PorJosé A. Alonso 27 noviembre 20128 marzo 2013

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los ejercicios de la 8ª relación que tratan de la ordenación por mezcla.

Los ejercicios, y sus soluciones, se muestran a continuación:
Read More “I1M2012: Ordenación por mezcla”

I1M2012: Sumas de factoriales que dan cuadrados perfectos

PorJosé A. Alonso 27 noviembre 20128 marzo 2013

En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de un problema propuesto en la revista Mathematics Magazine. Su enunciado es

Encontrar todos los enteros positivos m y n para los que se
cumpla que: $1!+2!+3!+ \dots +n!=m^2$ .

Su traducción directa es

sol :: [(Integer,Integer)]
sol = [(n,m) | n <- [1..], m <- [sumaFactoriales n], esCuadrado m]

1 2	sol :: [(Integer,Integer)] sol = [(n,m) \| n <- [1..], m <- [sumaFactoriales n], esCuadrado m]

o, usando let,

sol' :: [(Integer,Integer)]
sol' = [(n,m) | n <- [1..], let m = sumaFactoriales n, esCuadrado m]

1 2	sol' :: [(Integer,Integer)] sol' = [(n,m) \| n <- [1..], let m = sumaFactoriales n, esCuadrado m]

donde

(sumaFactoriales n) es la suma de los factoriales de 1 a n

Haskell

sumaFactoriales :: Integer -> Integer sumaFactoriales n = sum [factorial x | x <- [1..n]]

1
2

sumaFactoriales :: Integer -> Integer
sumaFactoriales n = sum [factorial x | x <- [1..n]]
(factorial n) es el factorial de n.

Haskell

factorial :: Integer -> Integer factorial n = product [1..n]

1
2

factorial :: Integer -> Integer
factorial n = product [1..n]
(esCuadrado x) se verifica si x es un cuadrado perfecto.

Haskell

esCuadrado :: Integer -> Bool esCuadrado x = x == y*y where y = floor (sqrt (fromIntegral x))

1
2
3

esCuadrado :: Integer -> Bool
esCuadrado x = x == y*y
where y = floor (sqrt (fromIntegral x))

Con esta definición se encuentran las siguientes soluciones

ghci> sol
[(1,1),(3,9)  
C-c C-c
Interrupted.

ghci> sol

[(1,1),(3,9)

C-c C-c

Interrupted.

Se observa que después de calcular las dos primeras sigue buscando por lo que hay que terminar el cálculo (con C-c C-c) sin encontrar más soluciones.

Que las dos primeras son soluciones se comprueba fácilmente:

$1! = 1 = 1^2$
$1!+2!+3! = 9 = 3^2$ .

Vamos a investigar porqué no hay más soluciones. Para ello, empezamos calculando las sumas de los factoriales

ghci> [sumaFactoriales n | n <- [1..10]]
[1,3,9,33,153,873,5913,46233,409113,4037913]

1 2	ghci> [sumaFactoriales n \| n <- [1..10]] [1,3,9,33,153,873,5913,46233,409113,4037913]

Se observa que, a partir de la cuarta, todas terminan en 3. Por otra parte, calculando los cuadrados de los dígitos

ghci> [x^2 | x <- [0..9]]
[0,1,4,9,16,25,36,49,64,81]

1 2	ghci> [x^2 \| x <- [0..9]] [0,1,4,9,16,25,36,49,64,81]

se observa que ninguno termina en 3; es decir, ningún cuadrado perfecto temina en 3.

Para terminar, nos falta demostrar la conjetura anterior (si n>3, entonces $1!+2!+3!+ \dots +n!$ termina en 3). Para ello calculamos los primeros factoriales

ghci> [factorial n | n <- [1..10]]
[1,2,6,24,120,720,5040,40320,362880,3628800]

1 2	ghci> [factorial n \| n <- [1..10]] [1,2,6,24,120,720,5040,40320,362880,3628800]

Se observa que para n=4 termina en 3 (es 1+2+6+24=33) y que, para n>4, el último dígito de n! es 0 (que es fácil de demostrar ya que si n>4, entre los factores de n están el 2 y el 5).