Download Lógica

David Camacho Fernández
Temas Avanzados en Ingeniería Informática I
(Lógica)
Lógica Computacional
“La mayoría de las ideas fundamentales de la
ciencia son esencialmente sencillas y, por regla
Tema 1: Introducción
general pueden ser expresadas en un lenguaje
comprensible para todos.”
Albert Einstein
Definiciones
Lógica Computacional
La Lógica Computacional aborda el estudio de la Lógica
Matemática desde la perspectiva de su aplicación al mundo de la
computación
La Lógica se utilizará para:
Como una forma de representación del conocimiento
Para la implementación de procesos que permitan la
Lógica
logos:razón, tratado o ciencia
Lógica : Ciencia del Razonamiento
La lógica surge con la filosofía: Debate entre el
materialismo y el idealismo
resolución de problemas
Lógica
1
David Camacho Fernández
Definiciones
Lógica Matemática= “La Lógica es la ciencia que tiene
como objetivo el análisis de los métodos de
razonamiento”
Lógica Matemática = Lógica Formal = Lógica Simbólica
Definiciones
obtención de nuevo conocimiento (conclusión) a partir de una
serie de conocimientos previos (premisas)
Lógica Formal= deducción de conocimiento a partir de
otros elementos. Ciencia que estudia la validez formal del
razonamiento
Breve historia de la Lógica Formal
Validez formal: un razonamiento es formalmente válido si la
conclusión es necesariamente verdadera cuando las premisas
son verdaderas (es válido en virtud de su forma -su estructura-,
es decir, independientemente del conocimiento concreto del que
trata). En este caso se dice que la conclusión es una
consecuencia lógica de las premisas
Breve historia de la Lógica Formal
Demócrito (460-370 a.c) Fundador de la teoría atomística
Razonamiento (deducción, inferencia, argumentación):
Sócrates (469-339 a.c.) y Platón (427-347 a.c.): contra la corriente
materialista
La Lógica fue formalmente introducida en el marco de la Filosofía
por el filósofo griego Aristóteles (384-322 A.C.). Teoría del
raciocionio y de la demostración: rigurosa diferenciación entre lo
verdadero y lo falso
Edad Media
Bacon (1561-1626): lógica inductiva
Descartes (1596-1650), Método Científico
El matemático alemán Leibniz (1646-1716) fue el primero en
plantear una verdadera formalización de la lógica como cálculo
matemático
Lógica
También antecedentes en China y la India
2
David Camacho Fernández
Breve historia de la Lógica Formal
Breve historia de la Lógica Formal
El gran desarrollo de la lógica formal se produjo a finales del siglo
XIX y primera mitad del XX, con las aportaciones de:
El trabajo es completado a mediados del siglo XIX con los
trabajos de los matemáticos ingleses Boole y De Morgan, que
aplicaron a la lógica métodos algebraicos:
G. Boole(1815-1864): Lógica Booleana
Augustus de Morgan(1806-1871): leyes distributivas de la
Gottlob Frege(1848-1925): fundador de la lógica moderna y de
la lógica de primer orden
Bertrand Russell(1872-1957), Alfred North Whitehead(18611947): Principia Mathematica: lógica simbólica
Kurt Gödel (1906-1978): Teoremas de Gödel
Alfred Tarski (1902-1983), Fundamentación de la metalógica y la
negación
metamatemática
Hilbert, Herbrand…
Tipos de Lógicas
Breve historia de la Lógica Formal
Lógica Clásica
Considera únicamente construcciones declarativas, sobre las que
A partir de los años 50 una parte importante de la
investigación en lógica se centra en el estudio de
podemos pronunciarnos acerca de su verdad o falsedad sin
sus aplicaciones en computación, en particular
consideraciones de contexto
como herramienta de programación
Es veritativo-funcional. Una expresión es veritativa-funcional si
forma estructuras compuestas en los que basta conocer el valor
de verdad de sus partes para saber el valor de verdad de la
estructura total
Lógica
3
David Camacho Fernández
Tipos de Lógicas
Tipos de Lógicas
Lógica Clásica
Su estudio se realiza en dos niveles de análisis estructural:
1.
Se contemplan únicamente construcciones declarativas
simples y compuestas: Lógica Clásica Proposicional
2.
En cada afirmación simple se distingue qué se declara o de
qué o quién se declara: Lógica Clásica de Predicados
Lógica Clásica Proposicional (I)
Representación del lenguaje natural tomando como elemento
básico una representación matemática de las frases declarativas
simples (o proposiciones)
Ej: Jorge es listo (p)
Tipos de Lógicas
Tipos de Lógicas
Lógica Proposicional (o de enunciados) (III)
Ejemplos de formalización de razonamientos:
Lógica Proposicional (o de enunciados) (II)
Estudia el comportamiento de las fórmulas proposicionales,
construidas exclusivamente a partir de:
proposiciones atómicas (sentencias declarativas sin estructura
interna que siempre son o bien ciertas o bien falsas)
conectivas lógicas (y, o, no, implica, ...)
Lógica
Ejemplos de formalización de frases:
llueve (p); me mojo (q) ; llueve o me mojo (p ∨ q); no llueve
(¬p);si llueve, me mojo (p → q)
Ejemplo A (razonamiento válido)
Premisa 1: Si las rosas son rojas, las violetas son azules: p → q
Premisa 2: Las violetas no son azules: ¬q
Conclusión: Las rosas no son rojas: ¬p
Ejemplo B (razonamiento NO válido)
Premisa 1: Si los problemas son difíciles, estudiamos: p → q
Premisa 2: Los problemas no son difíciles: ¬ p
Conclusión: No estudiamos: ¬q
4
David Camacho Fernández
Tipos de Lógicas
Lógica Clásica de Predicados (I)
Representación del lenguaje natural tomando como elemento
Tipos de Lógicas
Lógica Predicados (de primer orden) (II)
Existen razonamientos válidos que no son expresables ni
básico los componentes de algunos tipos de proposición (términos
analizables en lógica de proposiciones
y predicados)
Ej: Jorge
término
es listo
La lógica de predicados es una extensión de la lógica de
proposiciones que tiene en cuenta la estructura interna de los
predicado
enunciados
Tipos de Lógicas
Lógica Predicados (de primer orden) (II)
Lógica Predicados (de primer orden) (II)
Introduce los siguientes (nuevos) elementos:
Ejemplo de formalización de una frase:
Lógica
Tipos de Lógicas
predicados, que permiten expresar propiedades o relaciones
entre objetos
cuantificadores, que permiten expresar la generalidad de los
enunciados (enunciados válidos para todos los objetos de un
cierto tipo o sólo para algunos)
funciones, que permiten expresar transformaciones de
objetos
constantes y variables, que permiten referirse a objetos
concretos u objetos generales
“a es el límite de una sucesión f(n) si para todo ε > 0 existe un n0
tal que para todo n ≥ n0 se verifica abs(f(n) - a) < ε"
5
David Camacho Fernández
Tipos de Lógicas
Lógica Predicados (de primer orden) (II)
Ejemplo de formalización de un razonamiento:
Tipos de Lógicas
Premisa 1: Todas las personas son mortales
Premisa 2: Sócrates es una persona. P(s)
Conclusión: Sócrates es mortal. M(s)
(razonamiento formalmente válido)
Lógicas de orden superior
En lógica de predicados de primer orden los
cuantificadores sólo se pueden aplicar a objetos
(elementos de primer orden)
Las lógicas de orden superior son extensiones de la
lógica de predicados de primer orden que permiten
aplicar cuantificadores a predicados definidos sobre
objetos (segundo orden), predicados definidos sobre
predicados (tercer orden), etc.
Tipos de Lógicas
Lógica
Lógicas de orden superior
Tipos de Lógicas
Lógicas No Clásicas
Lógicas con mayor poder expresivo
Ejemplos:
“Todos los múltiplos de 8 comparten una propiedad interesante“
“Todos los problemas filosóficos tienen un rasgo en común"
Extensiones de la Lógica Clásica: extienden el vocabulario y
añaden nuevas leyes
Lógica Temporal: considera contextos temporales
Lógica Modal: considera contextos de necesidad o posibilidad
Lógica Doxástica: considera contextos de creencia
6
David Camacho Fernández
Tipos de Lógicas
Características de una Lógica
Lógicas No Clásicas
Desviaciones de la Lógica Clásica: no mantienen algunas leyes de
la Lógica clásica
Lógica Intuicionista: no contempla como ley “A o no A” (ley del
tercero excluido)
Lógica 3-valuada: se consideran tres valores de verdad
Lógicas que incorporan el tratamiento de la incertidumbre o
la imprecisión: Lógicas multivaluadas, Lógicas probabilistas,
Lógicas borrosas (fuzzy)
Un lenguaje formal (sintaxis)
Una Semántica (o Teoría de Modelos)
Una Teoría de la demostración
Automatizar las Deducciones
Lógica lineal: no es veritativo funcional
Lenguaje Formal
Características de una Lógica
Sintaxis
Describe los elementos básicos del lenguaje y las reglas
que permiten construir las expresiones admitidas por el
lenguaje, denominadas fórmulas
Semántica
Permite asignar un significado (valor de verdad, cierto o
falso) a las fórmulas del lenguaje, y definir qué significa que
una fórmula o un razonamiento sean válidos
Sistemas de demostración
Son sistemas formales que permiten averiguar cuándo una
fórmula es válida o cuándo un razonamiento es válido
Lenguaje universal sobre A:
A* = ∪ An
n∈N
Alfabeto: Un alfabeto es cualquier conjunto finito o infinito
numerable de símbolos (A)
Lógica
Para definir una lógica es necesario
Lenguaje sobre A: es cualquier subconjunto del lenguaje
universal: L ⊆ A*
7
David Camacho Fernández
Lenguaje Formal
Semántica o Teoría de Modelos
Los elementos de L se denominan fórmulas bien formadas (fbf), o
Una semántica o Teoría de modelos sobre un lenguaje L
viene de dada por los siguientes tres elementos :
fórmulas sintácticamente correctas (fsc)
Un conjunto de valores semánticos (S)
Un conjunto D ⊂ S de valores destacados
Equivalentemente, un lenguaje L viene determinado por:
Alfabeto: Conjunto de símbolos admitidos en el lenguaje
Gramática: Conjunto de reglas de formación que determinan
quá cadenasde símbolos son fbf en el lenguaje
Semántica o Teoría de Modelos
Modelo. Una interpretación es un modelo de un conjunto de
Teoría de la demostración
fbfs Ω si asigna a toda fórmula de Ω un valor destacado
Fórmula válida: una fbf es válida si toda interpretación del
Es un “mecanismo deductivo”, es decir, un mecanismo que
permite obtener una fbf de otras sin hacer referencia a ninguna
semántica
Tiene como objetivo establecer la noción sintáctica de deducción
lenguaje es un modelo para ella; se denota: |= α
Inferencia semántica: una fbf α se deriva o infiere
semánticamente de un conjunto de fbfs Ω, si todo modelo de Ω
es modelo de α. Se denota: Ω |= α
Lógica
Un conjunto (I) de aplicaciones I : L → S denominadas
interpretaciones
Sistemas axiomáticos
Sistemas de Deducción Natural
Sistemas de Gentzen
8
David Camacho Fernández
Sistema axiomático
Sistema axiomático
El mecanismo deductivo viene dado por los dos elementos
siguientes:
Axiomas: Conjunto finito o infinito numerable de fbfs de L
Reglas de inferencia: Conjunto de reglas deducción o
transformación que establecen cuando un fbf es consecuencia
inmediata de una o varias fórmulas
Fórmula válida o teorema. Una demostración es una secuencia finita de
fbfs en la cual cada fbf es o un axioma o una consecuencia inmediata de
una o varias fórmulas precedentes
Si A es la última fórmula de la secuencia, decimos que A es una fórmula
válida o teorema; lo denotamos ├ A
Deducción o derivación. Una deducción o derivación de una fbf A desde
un conjunto Ω de fbfs es una secuencia finita de fbfs en la cual cada
fórmula es un axioma, un elemento de Ω o una consecuencia inmediata de
una o varias fórmulas precedentes. Lo denotamos: Ω ├ A
Corrección y completitud
Estas nociones se asocian a un sistema de demostración
Automatización de las demostraciones
Decidibilidad: Una lógica se dice decidible, si para ella es posible
diseñar un algoritmo que determine si cualquier inferencia es, o no,
definido sobre un lenguaje con una teoría de modelos
válida
Corrección: Una teoría de la demostración es correcta si
todo lo derivable en ella es derivable en la semántica: Ω ├ A
⇒ Ω |= A
Semidecidibilidad
Complejidad de los algoritmos de decisión
Completitud: Una teoría de la demostración es completa si
toda inferencia válida en la semántica es derivable en ella: Ω
|= A ⇒ Ω ├ A
Lógica
9
David Camacho Fernández
Campos de aplicación
Campos de aplicación
Lógica computacional
Lógica de la programación
Uso de la lógica formal para describir la semántica de los
lenguajes de programación, para verificar la corrección de
programas o para probar propiedades de los programas
(ejemplo: Lógica de Hoare,1969)
Especificación formal
Uso de la lógica formal para especificar formalmente
programas (ejemplo: lenguaje de especificación Z, 1989)
Breve historia de la Lógica Computacional
Años 50
Nacimiento de la Inteligencia Artificial y del primer lenguaje de
programación declarativo (LISP) (McCarthy, 1959)
Aparición de los primeros sistemas de demostración
automática
Análisis, síntesis y verificación de Programas
Teoría de la especificación
Programación Lógica
Inteligencia Artificial
Control de Procesos
Robótica
Breve historia de la Lógica Computacional
Años 70
Introducción de la programación lógica como mecanismo
general de resolución de problemas (Greene, Kowalski)
Años 60
Lógica
Lógica computacional
Nuevos sistemas de demostración automática, más eficientes
y completos (Gilmore, Davis-Putnam, ...)
Aparición del sistema de Resolución (Robinson, 1965):
sistema muy eficiente, sencillo y de fácil implementación
(sistema utilizado por PROLOG)
Primera implementación de un lenguaje de programación
lógico (Prolog, Colmenauer, 1972)
10
David Camacho Fernández
Programación Lógica
Breve historia de la Lógica Computacional
Años 80 en adelante
Prolog alcanza su madurez (varias implementaciones
Constituye una parte fundamental de la
Inteligencia Artificial ≡ construcción de
sistemas informáticos capaces de reproducir
comportamientos “inteligentes"
comerciales, libros, etc), su uso se empieza a generalizar y se
define un estándar
Programación lógica concurrente, Programación lógicofuncional, programación lógica con restricciones, sistemas
distribuidos y orientación a objetos, uso de otras lógicas, ...
Programación Lógica
Programación Lógica
Se basa en dos ideas fundamentales:
1.
El “conocimiento" asociado con un sistema se puede expresar
de forma declarativa mediante fórmulas lógicas (≡ uso de la
lógica como mecanismo de representación del conocimiento)
A diferencia del paradigma de programación imperativo o
procedural (e.g. Pascal, Ada, C, etc), o del orientado a objetos
(C++, Java, Eiffel, Smalltalk, etc.) los programas en un lenguaje
de programación lógico no describen cómo resolver el
2.
Lógica
El “razonamiento" de un sistema se traduce entonces en la
realización de una serie de operaciones lógicas (deducciones)
sobre dicho conocimiento (≡ uso de la lógica como mecanismo
de resolución de problemas)
problema sino simplemente especifican qué hay que resolver
11
David Camacho Fernández
Programación Lógica
Escribir un programa lógico consiste en:
1.
2.
Programación Lógica
Declarar el conocimiento relativo al problema mediante una
Funcionamiento de la programación lógica
La realización de una consulta se traduce en averiguar si la
serie de fórmulas lógicas (≡ construir una base de
fórmula existencial es una consecuencia lógica de las fórmulas
conocimientos)
que constituyen la base de conocimientos
Representar el problema a resolver mediante una fórmula
lógica de tipo existencial (≡ realizar una consulta a la base de
Para ello, los lenguajes lógicos incorporan mecanismos de
demostración automática, basados en sistemas de
conocimientos)
demostración lógicos
Programación Lógica
Ventajas de la programación lógica
Programación Lógica
Ejemplo
Base de conocimientos
Madre(m1,m2);Madre(m2,m3);Madre(m2,m4)
Padre(p1,m2); Padre(p1, p2)
Los programas están muy próximos a la especificación de los
problemas que pretenden resolver
Son por ello más sencillos, más fáciles de entender y
mantener y más fiables
Lógica
Consultas
12