{"id":1596,"date":"2011-10-03T16:11:58","date_gmt":"2011-10-03T16:11:58","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1596"},"modified":"2011-10-04T06:18:21","modified_gmt":"2011-10-04T06:18:21","slug":"li2011-12-sintaxis-y-semantica-de-la-logica-proposicional","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/li2011-12-sintaxis-y-semantica-de-la-logica-proposicional\/","title":{"rendered":"LI2011-12: Sintaxis y sem\u00e1ntica de la l\u00f3gica proposicional"},"content":{"rendered":"<p>El objetivo fundamental de la clase de hoy del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/li-11\">L\u00f3gica Inform\u00e1tica<\/a> ha consistido en responder estas dos preguntas:<\/p>\n<ul>\n<li>\u00bfc\u00f3mo se puede construir un programa para que dada una cadena de caracteres decida si es una f\u00f3rmula proposicional?\n<li>\u00bfc\u00f3mo se puede construir un programa para que dada una f\u00f3rmula decida si es verdadera?\n<\/ul>\n<p>Para responder a la primera pregunta, desarrollamos la sintaxis de la l\u00f3gica proposicional. Pero antes de abordar la respuesta, nos planteamos otro an\u00e1logo que es el reconocimiento de los n\u00fameros naturales. Los n\u00fameros naturales pueden representarse por 0, s(0), s(s(0)), &#8230; La pregunta es \u00bfc\u00f3mo se puede construir un programa para que dada una cadena de caracteres decida si es un n\u00famero natural? Una respuesta se basa en utilizar las dos reglas siguientes:<\/p>\n<ul>\n<li>0 es un n\u00famero natural;\n<li>si n es un n\u00famero natural, entonces s(n) es un n\u00famero natural.\n<\/ul>\n<p>Vemos que es una definici\u00f3n recursiva con un elemento b\u00e1sico (el 0) y un constructor (s, que representa el siguiente). Basado en esta analog\u00eda se define las f\u00f3rmulas proposicionales tomando como elementos b\u00e1sicos las f\u00f3rmulas at\u00f3micas y como constructores las conectivas.<\/p>\n<p>La siguiente cuesti\u00f3n que nos planteamos es c\u00f3mo definir procedimientos sobre f\u00f3rmulas. Volvemos a apoyarnos en los n\u00fameros naturales y vemos c\u00f3mo se puede definir la suma de dos n\u00fameros naturales:<\/p>\n<ul>\n<li> 0 + y = y\n<li> s(n) + y = s(n+y)\n<\/ul>\n<p>Vemos que es una definici\u00f3n por recursi\u00f3n en el primer argumento con dos casos correspondientes a las dos reglas de definici\u00f3n de los n\u00fameros naturales. En el caso de las f\u00f3rmulas proposicionales las definiciones tendr\u00e1 una ecuaci\u00f3n para las f\u00f3rmulas at\u00f3micas y una por cada una de las conectivas (aunque generalmente las binarias se agrupen en una \u00fanica ecuaci\u00f3n). Como ejemplo de definiciones sobre f\u00f3rmulas se definen funciones para calcular el n\u00famero de par\u00e9ntesis y el conjunto de subf\u00f3rmulas de una f\u00f3rmula.<\/p>\n<p>La tercera cuesti\u00f3n sint\u00e1ctica que nos planteamos es c\u00f3mo demostrar que todas las f\u00f3rmulas cumplen una propiedad. De nuevo nos apoyamos en la aritm\u00e9tica y recordando el principio de inducci\u00f3n sobre los n\u00fameros naturales introducimos el principio de inducci\u00f3n sobre f\u00f3rmulas.<\/p>\n<p>Para responder a la primera pregunta, desarrollamos la sem\u00e1ntica de la l\u00f3gica proposicional. En primer lugar, el valor de verdad de una f\u00f3rmula en una interpretaci\u00f3n se define por recursi\u00f3n. A partir del valor de verdad podemos, dada una f\u00f3rmula F, dividir las interpretaciones entre las que son modelo de F y las que no lo son. Adem\u00e1s, las f\u00f3rmulas pueden clasificarse en satisfacibles (las que tienen modelos) e insatisfacibles (en caso contrario). Las f\u00f3rmulas satisfacibles se pueden clasificar en tautolog\u00edas (para las que todas las interpretaciones son modelo) y contingentes (en caso contrario). <\/p>\n<p>Al final de la clase se han comentado soluciones de ejercicios de formalizaci\u00f3n con <a href=\"https:\/\/www.glc.us.es\/apli2\">APLI2<\/a> que han presentado mayores dificultades en su resoluci\u00f3n<\/p>\n<p>Los ejercicios pendientes para la pr\u00f3xima clase son desde el 22 al 26 del cap\u00edtulo 1 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/li\/temas\/ejercicios-LI-2011-12.pdf\">libro de ejercicios<\/a>.<\/p>\n<p>Las transparencias de esta clase son las p\u00e1ginas 6-20 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/li-11\/temas\/tema-1.pdf\">tema 1<\/a><br \/>\n<!--more--><br \/>\n<div class=\"jetpack-video-wrapper\"><iframe src='https:\/\/www.slideshare.net\/slideshow\/embed_code\/6980175' width='1290' height='1057' sandbox=\"allow-popups allow-scripts allow-same-origin allow-presentation\" allowfullscreen webkitallowfullscreen mozallowfullscreen><\/iframe><\/div><\/p>\n","protected":false},"excerpt":{"rendered":"<p>El objetivo fundamental de la clase de hoy del curso L\u00f3gica Inform\u00e1tica ha consistido en responder estas dos preguntas: \u00bfc\u00f3mo se puede construir un programa para que dada una cadena de caracteres decida si es una f\u00f3rmula proposicional? \u00bfc\u00f3mo se puede construir un programa para que dada una f\u00f3rmula decida si es verdadera? Para responder&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[183],"tags":[182],"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\/1596"}],"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=1596"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1596\/revisions"}],"predecessor-version":[{"id":1599,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1596\/revisions\/1599"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}