{"id":1836,"date":"2012-01-17T16:53:51","date_gmt":"2012-01-17T16:53:51","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1836"},"modified":"2013-03-08T05:48:56","modified_gmt":"2013-03-08T05:48:56","slug":"i1m2011-demostracion-de-propiedades-por-induccion","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-demostracion-de-propiedades-por-induccion\/","title":{"rendered":"I1M2011: Demostraci\u00f3n de propiedades por inducci\u00f3n"},"content":{"rendered":"<p>La clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_13.hs\">13\u00aa relaci\u00f3n<\/a> en la que se plantean ejercicios de demostraci\u00f3n por inducci\u00f3n de propiedades de programas. En concreto,<\/p>\n<ul>\n<li> la suma de los n primeros impares es <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=n%5E2&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"n^2\" class=\"latex\" \/>,\n<li> <img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=1+%2B+2%5E0+%2B+2%5E1+%2B+2%5E2+%2B+%5Ccdots+%2B+2%5En+%3D+2%5E%7Bn%2B1%7D&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"1 + 2^0 + 2^1 + 2^2 + &#92;cdots + 2^n = 2^{n+1}\" class=\"latex\" \/>,\n<li> todos los elementos de (copia n x) son iguales a x.\n<\/ul>\n<p>Adem\u00e1s, se plantea la definici\u00f3n de la traspuesta de una matriz.<\/p>\n<p>Estos ejercicios corresponden al <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-8.pdf\">tema 8<\/a>.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.1. Definir por recursi\u00f3n la funci\u00f3n\r\n--    sumaImpares :: Int -> Int\r\n-- tal que (sumaImpares n) es la suma de los n primeros n\u00fameros\r\n-- impares. Por ejemplo,\r\n--    sumaImpares 5  ==  25\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaImpares :: Int -> Int\r\nsumaImpares 0     = 0\r\nsumaImpares (n+1) = sumaImpares n + (2*n+1) \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.2. Definir, sin usar recursi\u00f3n, la funci\u00f3n\r\n--    sumaImpares' :: Int -> Int\r\n-- tal que (sumaImpares' n) es la suma de los n primeros n\u00fameros\r\n-- impares. Por ejemplo,\r\n--    *Main> sumaImpares' 5  ==  25\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaImpares' :: Int -> Int\r\nsumaImpares' n = sum [1,3..(2*n-1)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.3. Definir la funci\u00f3n\r\n--    sumaImparesIguales :: Int -> Int -> Bool\r\n-- tal que (sumaImparesIguales m n) se verifica si para todo x entre m y\r\n-- n se tiene que (sumaImpares x) y (sumaImpares' x) son iguales.\r\n-- \r\n-- Comprobar que (sumaImpares x) y (sumaImpares' x) son iguales para\r\n-- todos los n\u00fameros x entre 1 y 100.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n es\r\nsumaImparesIguales :: Int -> Int -> Bool\r\nsumaImparesIguales m n = \r\n    and [sumaImpares x == sumaImpares' x | x <- [m..n]]\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main>  sumaImparesIguales 1 100\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.4. Definir la funci\u00f3n \r\n--    grafoSumaImpares :: Int -> Int -> [(Int,Int)]\r\n-- tal que (grafoSumaImpares m n) es la lista formadas por los n\u00fameros x\r\n-- entre m y n y los valores de (sumaImpares x).\r\n--\r\n-- Calcular (grafoSumaImpares 1 9).\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n es\r\ngrafoSumaImpares :: Int -> Int -> [(Int,Int)]\r\ngrafoSumaImpares m n =\r\n    [(x,sumaImpares x) | x <- [m..n]]\r\n\r\n-- El c\u00e1lculo es\r\n--    *Main> grafoSumaImpares 1 9\r\n--    [(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.5. Demostrar por inducci\u00f3n que para todo n, \r\n-- (sumaImpares n) es igual a n^2.\r\n-- ---------------------------------------------------------------------\r\n\r\n{-\r\n Caso base: Hay que demostrar que\r\n    sumaImpares 0 = 0^2 \r\n En efecto,\r\n    sumaImpares 0   [por hip\u00f3tesis]  \r\n    = 0               [por sumaImpares.1]\r\n    = 0^2             [por aritm\u00e9tica]\r\n \r\n  Caso inductivo: Se supone la hip\u00f3tesis de inducci\u00f3n (H.I.)\r\n     sumaImpares n = n^2\r\n  Hay que demostrar que\r\n     sumaImpares (n+1) = (n+1)^2\r\n  En efecto,\r\n     sumaImpares (n+1) = \r\n     = (sumaImpares n) + (2*n+1    )    [por sumaImpares.2]\r\n     = n^2 + (2*n+1)                    [por H.I.]\r\n     = (n+1)^2                          [por \u00e1lgebra]\r\n-} \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.1. Definir por recursi\u00f3n la funci\u00f3n\r\n--    sumaPotenciasDeDosMasUno :: Int -> Int\r\n-- tal que \r\n--    (sumaPotenciasDeDosMasUno n) = 1 + 2^0 + 2^1 + 2^2 + ... + 2^n. \r\n-- Por ejemplo, \r\n--    sumaPotenciasDeDosMasUno 3  ==  16\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaPotenciasDeDosMasUno :: Int -> Int\r\nsumaPotenciasDeDosMasUno 0     = 2\r\nsumaPotenciasDeDosMasUno (n+1) = sumaPotenciasDeDosMasUno n + 2^(n+1)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.2. Definir por comprensi\u00f3n la funci\u00f3n\r\n--    sumaPotenciasDeDosMasUno' :: Int -> Int\r\n-- tal que \r\n--    (sumaPotenciasDeDosMasUno' n) = 1 + 2^0 + 2^1 + 2^2 + ... + 2^n. \r\n-- Por ejemplo, \r\n--    sumaPotenciasDeDosMasUno' 3  ==  16\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaPotenciasDeDosMasUno' :: Int -> Int\r\nsumaPotenciasDeDosMasUno' n = 1 + sum [2^x | x <- [0..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.3. Demostrar por inducci\u00f3n que\r\n--    sumaPotenciasDeDosMasUno n = 2^(n+1)\r\n-- ---------------------------------------------------------------------\r\n\r\n{-\r\n  Caso base: Hay que demostrar que \r\n     sumaPotenciasDeDosMasUno 0 = 2^(0+1)\r\n  En efecto,\r\n       sumaPotenciasDeDosMasUno 0 \r\n     = 2                              [por sumaPotenciasDeDosMasUno.1]\r\n     = 2^(0+1)                        [por aritm\u00e9tica]\r\n\r\n  Caso inductivo: Se supone la hip\u00f3tesis de inducci\u00f3n (H.I.)\r\n     sumaPotenciasDeDosMasUno n = 2^(n+1)\r\n  Hay que demostrar que \r\n     sumaPotenciasDeDosMasUno (n+1) = 2^((n+1)+1)\r\n  En efecto, \r\n       sumaPotenciasDeDosMasUno (n+1)\r\n     = (sumaPotenciasDeDosMasUno n) + 2^(n+1)  [por sumaPotenciasDeDosMasUno.2]\r\n     = 2^(n+1) + 2^(n+1)                       [por H.I.]\r\n     = 2^((n+1)+1)                             [por aritm\u00e9tica]\r\n-}\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.1. Definir por recursi\u00f3n la funci\u00f3n\r\n--    copia :: Int -> a -> [a]\r\n-- tal que (copia n x) es la lista formado por n copias del elemento\r\n-- x. Por ejemplo, \r\n--    copia 3 2  ==  [2,2,2]\r\n-- ---------------------------------------------------------------------\r\n \r\ncopia :: Int -> a -> [a]\r\ncopia 0 _     = []              -- copia.1\r\ncopia (n+1) x = x : copia n x   -- copia.2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.2. Definir por recursi\u00f3n la funci\u00f3n \r\n--    todos :: (a -> Bool) -> [a] -> Bool\r\n-- tal que (todos p xs) se verifica si todos los elementos de xs cumplen\r\n-- la propiedad p. Por ejemplo,\r\n--    todos even [2,6,4]  ==  True\r\n--    todos even [2,5,4]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\ntodos :: (a -> Bool) -> [a] -> Bool\r\ntodos p []       = True                -- todos.1\r\ntodos p (x : xs) = p x && todos p xs   -- todos.2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.3. Comprobar con QuickCheck que todos los elementos de \r\n-- (copia n x) son iguales a x.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_copia :: Eq a => Int -> a -> Bool\r\nprop_copia n x =\r\n    todos (==x) (copia n' x)\r\n    where n' = abs n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_copia\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.4. Demostrar, por inducci\u00f3n en n, que todos los elementos\r\n-- de (copia n x) son iguales a x.\r\n-- ---------------------------------------------------------------------\r\n\r\n{-\r\n  Hay que demostrar que para todo n y todo x,\r\n     todos (==x) (copia n x)\r\n\r\n  Caso base: Hay que demostrar que\r\n     todos (==x) (copia 0 x) = True \r\n  En efecto, \r\n       todos (== x) (copia 0 x)\r\n     = todos (== x) []            [por copia.1] \r\n     = True                       [por todos.1] \r\n\r\n  Caso inductivo: Se supone la hip\u00f3tesis de inducci\u00f3n (H.I.)\r\n     todos (==x) (copia n x) = True\r\n  Hay que demostrar que\r\n     todos (==x) (copia (n+1) x) = True\r\n  En efecto, \r\n       todos (==x) (copia (n+1) x)\r\n     = todos (==x) (x : copia n x )         [por copia.2]\r\n     = x == x && todos (==x) (copia n x )   [por todos.2] \r\n     = True && todos (==x) (copia n x )     [por def. de ==] \r\n     = todos (==x) (copia n x )             [por def. de &&] \r\n     = True                                 [por H.I.]\r\n-}\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.5. Definir por plegado la funci\u00f3n \r\n--    todos' :: (a -> Bool) -> [a] -> Bool\r\n-- tal que (todos' p xs) se verifica si todos los elementos de xs cumplen\r\n-- la propiedad p. Por ejemplo,\r\n--    todos' even [2,6,4]  ==>  True\r\n--    todos' even [2,5,4]  ==>  False\r\n-- ---------------------------------------------------------------------\r\n\r\ntodos' :: (a -> Bool) -> [a] -> Bool\r\ntodos' p = foldr ((&&) . p) True \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    traspuesta :: [[a]] -> [[a]]\r\n-- tal que (traspuesta m) es la traspuesta de la matriz m. Por ejemplo,\r\n--    traspuesta [[1,2,3],[4,5,6]]    ==  [[1,4],[2,5],[3,6]]\r\n--    traspuesta [[1,4],[2,5],[3,6]]  ==  [[1,2,3],[4,5,6]]\r\n-- ---------------------------------------------------------------------\r\n\r\ntraspuesta :: [[a]] -> [[a]]\r\ntraspuesta []           = []\r\ntraspuesta ([]:xss)     = traspuesta xss\r\ntraspuesta ((x:xs):xss) = \r\n    (x:[h | (h:_) <- xss]) : traspuesta (xs : [t | (_:t) <- xss])\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los ejercicios de la 13\u00aa relaci\u00f3n en la que se plantean ejercicios de demostraci\u00f3n por inducci\u00f3n de propiedades de programas. En concreto, la suma de los n primeros impares es , , todos los elementos de (copia&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[186],"tags":[295],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1836"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1836"}],"version-history":[{"count":8,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1836\/revisions"}],"predecessor-version":[{"id":2869,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1836\/revisions\/2869"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1836"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1836"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1836"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}