Download Lógica y sistemas axiomáticos - Página personal de César Ignacio

P(a)
P(a)
x
■
■
■
P(a)
■
x
Lógica y sistemas axiomáticos
César Ignacio García Osorio
P(a)
■
■
1
■ Conceptos
César Ignacio García Osorio
Lógica y sistemas axiomáticos
2
Lógica de proposiciones:
introducción
x
■ Es
❚ Proposición
❚ Consistencia
❚ Fórmula
❚ Satisfacibilidad
atómica o átomo
❚ Conectiva lógica
❚ Formula bien formada
❚ Valor de verdad
❚ Interpretación
❚ Tabla de verdad
❚ Asignación de verdad
César Ignacio García Osorio
La lógica ha sido históricamente uno de los primeros lenguajes
utilizados para representar el conocimiento.
Además es frecuente comparar la potencia expresiva de otros
formalismos de representación con la lógica.
Por ello ocupa un puesto especial entre los mecanismo de
representación.
Proporciona de manera inmediata un método muy potente para la
obtención de nuevo conocimiento a partir del antiguo:la deducción
matemática.
Por otra parte el lenguaje de la lógica es la base de la mayoría de los
programas de demostración automática de teoremas.
Además mecanismos de inferencia tan aceptados como la resolución
son la base de la programación lógica y de las bases de datos
deductivas.
P(a)
Lógica de proposiciones
x
Introducción
x
un lenguaje que nos permite expresar y razonar con
sentencias declarativas que son o bien ciertas o bien falsas.
❚ Ejemplos de sentencias declarativas ciertas son:
• Un rectángulo es un paralelogramo.
• Las proposiciones son sentencias declarativas ciertas o falsas.
❚ Modelo
❚ Validez
❚ Tautología
❚ Ejemplos
❚ Equivalencia
Lógica y sistemas axiomáticos
de sentencias declarativas falsas:
• El doble de 20 es 55.
• El número pi es racional.
■ Estas
3
sentencias declarativas se llaman proposiciones.
César Ignacio García Osorio
Lógica y sistemas axiomáticos
4
P(a)
x
❚A
menudo se expresan ideas más complejas, como:
•El periódico no ha llegado todavía.
•Ayer fui a la playa y al cine.
•Trae un tarro de mermelada de fresa o de melocotón.
•Sólo bebo agua o zumos.
•Si bebes, entonces no conduzcas.
•Si tu sabes tocar el piano, entonces yo soy el rey de Francia.
•Ganarás el concurso si y sólo si aciertas todas las preguntas.
■
■
P(a)
Lógica de proposiciones:
introducción
■
negación
conjunción
disyunción
implicación
bi-implicación
Las “palabras”: no, y, o, si-entonces, y si y sólo si nos permiten
construir sentencias complejas a partir de otras más simples. Estas
palabras se conocen como conectores lógicos (o conectivas
lógicas).
Las sentencias declarativas “consideradas simples”, se llaman
proposiciones atómicas. Las proposiciones formadas mediante el
uso de átomos y conectores lógicos se llaman proposiciones
compuestas.
César Ignacio García Osorio
P(a)
x
Lógica y sistemas axiomáticos
■
5
Lógica y sistemas axiomáticos
César Ignacio García Osorio
x
Lógica y sistemas axiomáticos
6
Lógica de predicados
Lógica de predicados o de primer orden
Sintaxis
❚ Vocabulario y aridad
❚ Variable
❚ Término
❚ Fórmula atómica
❚ Cuantificador
❚ Alcance del cuantificador
❚ Formula bien formada
■ Conceptualización
■ Interpretación
■ Valor de verdad
■
■
de verdad: La certeza o falsedad de una proposición se llama su valor de
verdad, el valor de certeza se representa por T (de true) y el de falsedad por F (de
false). Se dice que una proposición tiene valor de verdad T o que es cierta y que
tiene valor de verdad F o que es falsa.
■ Interpretación: Dada una fórmula proposicional G, con A1, A2, ..., An como sus
átomos constituyentes. Una interpretación de G es una asignación de valores de
verdad a A1, A2, ..., An. A cada Ai se le asigna T o F pero no ambos. El valor de
verdad (bajo una interpretación) de una fórmula está determinado por el valor de
verdad (bajo esa interpretación) de los átomos que la forman y por el modo en que
estos átomos están combinados mediante los conectores lógicos:
¬G G∧H
G
H
G∨H G→H G↔ H
T
T
F
T
T
T
T
T
F
F
F
T
F
F
F
T
T
F
T
T
F
F
F
T
F
F
T
T
■ Valor
César Ignacio García Osorio
Lógica de proposiciones:
sintaxis
Fórmula bien formada: Una fórmula bien formada (o fórmula para
abreviar) en lógica de proposiciones es una expresión construida
siguiendo las reglas que aparecen a continuación:
❚ Un átomo es una fórmula bien formadas.
❚ Si P es una fórmula bien formada, entonces (¬P) es una fórmula
bien formada.
❚ Si P y Q son fórmulas bien formadas, entonces también lo son:
(P ∧ Q), (P ∨ Q), (P → Q) y (P ↔ Q).
❚ Ninguna otra cosa es una fórmula bien formada.
Para evitar la proliferación de paréntesis se establece una prioridad
de los operadores, en orden creciente es: ↔, →, ∨, ∧, ¬.
P(a)
Lógica de proposiciones:
semántica
x
7
César Ignacio García Osorio
Lógica y sistemas axiomáticos
8
P(a)
■
■
■
x
P(a)
■
■
■
En la lógica de proposiciones los elementos básicos son los átomos
que representan sentencias declarativas que pueden ser o bien
ciertas o bien falsas. Con los átomos se pueden construir fórmulas,
las fórmulas se usan para expresar ideas complejas.
La estructura y composición de los átomos no se tiene en cuenta,
esto impide expresar sentencias generales, por ejemplo la sentencia:
“todos los hombres son mortales”, es en lógica de proposiciones una
única proposición y no se tiene en cuenta la relación interna
expresada entre los hombres y la mortalidad.
La lógica de predicados es más expresiva que la de proposiciones, y
se pueden expresar sentencias generales como la anterior teniendo
en cuenta su estructura interna (para ello se utilizan nuevos
conceptos como: variables, términos, predicados y cuantificadores).
César Ignacio García Osorio
■
P(a)
Lógica de predicados:
introducción
x
Lógica y sistemas axiomáticos
❚
9
■
■
■
■
■
11
Símbolos auxiliares: como paréntesis y comas.
César Ignacio García Osorio
P(a)
Lógica de predicados:
sintaxis
Lógica y sistemas axiomáticos
Se utilizan varios tipos de símbolos:
❚ Símbolos de predicados, representados normalmente por letras mayúsculas (P,
Q, R, ...) o por cadenas de letras mayúsculas (GREATER, EQUAL,
PADRE_DE, ...). Cada uno tiene asociado un número natural que indica el
número de argumentos del predicado y que se llama aridad del predicado. Los
símbolos de predicados de aridad cero se corresponden con las proposiciones,
los de aridad uno, dos o tres se califican como unarios, binarios o ternarios.
❚ Símbolos de variables, representados normalmente por letras minúsculas del
final del alfabeto con o sin subíndices: x, y, z, x1, y23, ...
❚ Símbolos de función, representados mediante letras minúsculas de la mitad del
alfabeto (f, g, h, ...). O mediante cadenas de caracteres en minúsculas
(marido_de, hijo_de, siguiente, ...). También tienen asociada una aridad que
indica su número de argumentos. Las funciones de aridad cero, es decir sin
argumentos, se suelen llamar constantes.
❚ Los símbolos de los conectores lógicos: ¬, ∨, ∧, ↔, →.
❚ Los símbolos de dos cuantificadores:
• (∀ x) el cuantificador universal (para todo x).
• (∃ x) el cuantificador existencial (existe x).
Término: Un término se define como sigue:
❚ Una constante (función de aridad cero) es un término.
❚ Una variable es un término.
❚ Si f es una función de aridad n (n ≥ 0) y t1, t2,..., tn son términos,
entonces f(t1, t2,..., tn) es un término.
❚ Ninguna otra cosa es un término.
Por tanto un término es o bien una constante, o bien una variable, o
bien una función sobre términos.
Fórmula atómica o átomo: Una fórmula atómica o átomo es una
expresión de la forma P(t1, t2,..., tn) donde P es un símbolo de
predicado de aridad n (n ≥ 0), y t1, t2,..., tn son términos.
César Ignacio García Osorio
Lógica de predicados:
sintaxis
x
x
Lógica y sistemas axiomáticos
10
Lógica de predicados:
sintaxis
Alcance: Sea (Qx) un cuantificador (existencia o universal). Si G es una fórmula
bien formada en la que ocurre (Qx), siempre será posible la descomposición:
G=r(Qx) Hs con r, s y H formados por elementos del vocabulario de la lógica de
predicados y siendo además H una formula bien formada. La formula bien
formada H obtenida de la descomposición anterior es el alcance del
cuantificador (Qx)
En termino coloquiales el alcance de un cuantificador es la primera forma normal
que se puede identificar tras el cuantificador; el 'trozo' de formula sobre el que se
aplica dicho cuantificador).
Ocurrencia de variable ligada/libre: Una ocurrencia de una variable es ligada
si y sólo si:
❚ o es la variable que emplea el cuantificador.
❚ o ocurre en el alcance de un cuantificador que emplea esa misma variable.
Se dice que la ocurrencia de una variable es libre, cuando no es ligada.
Variable libre/ligada: Se dice que una variable es libre en una fórmula si al
menos una ocurrencia de la variable es libre en la formula. Una variable es ligada
en una fórmula si todas las ocurrencias de la variable son ligadas en la fórmula.
César Ignacio García Osorio
Lógica y sistemas axiomáticos
12
P(a)
■
■
■
x
Fórmula cerrada: Una formula que no tenga ocurrencias de
variables libres se llama fórmula cerrada.
Fórmula bien formada: Una fórmula bien formada en lógica de
predicados se define recursivamente como:
❚ Un átomo es una fórmula bien formada.
❚ Si G es una fórmula bien formada, (¬G) es una fórmula bien
formada.
❚ Si G y H son fórmulas bien formadas, (G∧H), (G∨H), (G→H),
(G↔H) son fórmulas bien formadas.
❚ Si G es una fórmula bien formada y x una variable libre en G,
(∀x)G y (∃x)G son fórmulas bien formadas
❚ Todas las fórmulas bien formadas se obtienen por aplicación de
las reglas anteriores sobre el conjunto de las fórmulas atómicas.
Habitualmente solo interesan las fbf que sean cerradas.
César Ignacio García Osorio
P(a)
■
■
P(a)
Lógica de predicados:
sintaxis
x
Lógica y sistemas axiomáticos
■
■
■
13
Interpretación: Una interpretación de una fórmula F en la lógica de primer
orden está formada por un dominio D y por una asignación de “valores” a cada
una de las constates, símbolos de función y símbolos de predicado que ocurren en
F tal como sigue:
❚ A cada constante se le asigna un elemento en D.
❚ A cada símbolo de función de aridad n se le asigna una aplicación de Dn en D.
❚ A cada símbolo de predicado de aridad n se le asigna una aplicación de Dn en
{T, F} (O de forma equivalente una relación sobre Dn).
Para cada una de las interpretaciones de una formula sobre un dominio D, se
puede obtener el valor de verdad de la fórmula aplicando las siguientes reglas:
❚ Si se conocen los valores de verdad de la fórmulas G y H, entonces los valores
de verdad de las fórmulas (¬G), (G∧H), (G∨H), (G→H) y (G↔H). Se pueden
obtener como en la lógica de proposiciones.
❚ (∀x)G tiene valor de verdad T si para toda sustitución que se haga de x por un
elemento d del domino D, G es T.
❚ (∃x)G tiene valor de verdad T si el valor de verdad de G es T para al menos
un elemento d del dominio D por el que se sustituya x en G.
César Ignacio García Osorio
Lógica y sistemas axiomáticos
César Ignacio García Osorio
15
■
■
■
■
Lógica de predicados:
semántica
En la lógica de proposiciones una interpretación era una asignación
de valores de verdad a los átomos.
En la lógica de primer orden, dado que hay cuantificadores y
variables involucradas, una interpretación va a ser algo más
complejo.
En la definición formal de la interpretación va ha aparecer el
concepto de dominio. El dominio o universo de discurso es un
conjunto no vacío de elementos llamados objetos. El término objeto
tiene un sentido muy amplio. Un objeto puede ser algo concreto o
algo abstracto, simple o compuesto, real o ficticio. En general, un
objeto es “cualquier cosa sobre la que deseamos decir algo”.
P(a)
Lógica de predicados:
semántica
x
x
Lógica y sistemas axiomáticos
14
Más conceptos
Consistencia y satisfacibilidad, modelo: Una fórmula G se dice
que es consistente (o satisfacible) si y sólo si existe una
interpretación I para la cual G es cierta. Si una fórmula G es cierta
para una interpretación I se dice que I es un modelo de G y que I
satisface a G o que G es satisfecha por I.
Inconsistencia o insatisfacibilidad: Una fórmula G es inconsistente
(o insatisfacible) si y sólo si no existe ninguna interpretación que
satisfaga a G. Es decir, G tiene valor de verdad F para toda
interpretación.
Fórmula valida o tautológica: Una fórmula G es válida (o
tautológica) si y sólo si toda interpretación de G es un modelo de G.
Una fórmula es válida cuando su negación es insatisfacible y
viceversa. Una fórmula no válida se dice que es inválida.
Fórmulas equivalentes: Dos fórmulas G y H son equivalentes, y se
denota por G≡H, si y sólo si los valores de verdad de G y H son los
mismos para toda interpretación de F y G.
César Ignacio García Osorio
Lógica y sistemas axiomáticos
16
P(a)
Leyes de equivalencia
x
■
F↔G ≡ (F→G)∧(G→F)
(L2) Eliminación del condicional:
F→G ≡ ¬F∨G
(L3) Conmutativa:
F∨G ≡ G∨F
F∧G ≡ G∧F
(L4) Asociativa:
(F∨G)∨H ≡ F∨(G∨H)
(F∧G)∧H ≡ F∧(G∧H)
(L5) Distributiva:
F∨(G∧H) ≡ (F∨G)∧(F∨H)
F∧(G∨H) ≡ (F∧G)∨(F∧H)
(L6) Absorción:
F∧"≡F
F∨!≡F
(L7) Contradicción:
F∨"≡"
F∧! ≡!
(L8) Exclusión de los medios: ¬F ∨ F ≡ "
¬F∧F≡!
(L9) Idempotencia:
F∨F ≡ F
F∧F ≡ F
(L10) Doble negadión:
¬¬F ≡ F
(L11) De Morgan:
¬(F∨G) ≡ ¬F ∧ ¬G
¬(F∧G) ≡ ¬F ∨ ¬G
(L12)
G∨(Qx)F[x] ≡ (Qx)(G∨F[x])
G∧(Qx)F[x] ≡ (Qx)(G∧F[x])
■
(L13) De Morgan para los cuantificadores:
■
■
■
■
■
■
■
■
■
■
■
¬(∀x)F[x] ≡ (∃x) ¬F[x]
■
■
x
■
F1, F2, ..., Fn ❘= G
❚ ((F1∧ F2 ∧ ... ∧ Fn ) →G) es una tautología
❚ (F1∧ F2 ∧ ... ∧ Fn ∧ ¬G) es inconsistente
❚
¬ (∃ x)F[x] ≡ (∀x) ¬F[x]
(∃x)F[x] ∨ (∃x) H[x] ≡ (∃)(F[x] ∨ H[z])
(L15)
(Q1x)F[x]∧(Q2x)H[x] ≡ (Q1x)(Q2z)(F[x]∧H[z])
César Ignacio García Osorio
P(a)
x
(Q1x)F[x]∨(Q2x)H[x] ≡ (Q1x)(Q2z)(F[x]∨H[z])
Lógica y sistemas axiomáticos
17
César Ignacio García Osorio
P(a)
Sistema formal de deducción
■
■
■
■
■
■
■
■
Sistema formal axiomático
Axiomas lógicos
Reglas de inferencia
Solidez
Completitud
Teoría
Teorema
■
■
■
César Ignacio García Osorio
Mas conceptos
Consecuencia lógica: Una fórmula G es consecuencia lógica de las
fórmulas F1, F2, ..., Fn y se denota por F1, F2, ..., Fn ❘= G si y sólo si
todo modelo de F1, F2, ..., Fn es también un modelo de G. A las
fórmulas F1, F2, ..., Fn se las llama premisas y a G conclusión. Se
dice además que G se deriva de F1, F2, ..., Fn, o que F1, F2, ..., Fn
determinan G.
Teorema de refutación: Sean F1, F2, ..., Fn y G sentencias. Las
siguientes afirmaciones son equivalentes:
(L14) Distributiva de cuantificadores:
(∀x)F[x] ∧ (∀x) H[x] ≡ (∀x)(F[x] ∧ H[z])
■
P(a)
(L1) Eliminación del bicondicional:
Lógica y sistemas axiomáticos
19
x
Lógica y sistemas axiomáticos
18
Conceptos
Sistema formal de deducción: Un sistema formal de deducción es
cualquier sistema que permite derivar fórmulas aplicando reglas. El
tipo concreto de sistema formal de deducción que nos interesa es el
sistema formal axiomático.
Sistema formal axiomático: Un sistema formal axiomático es una
tripleta {LL, AL, R} donde:
❚ LL es el lenguaje lógico utilizado1.
❚ AL es un conjunto de axiomas lógicos.
❚ R es un conjunto de reglas de inferencia.
Axioma lógico: Un axioma lógico es cualquier formula bien formada
que sea tautológica. Lo habitual es trabajar son esquemas de axiomas.
Esquema de axiomas: Un esquema de axiomas es un patrón de
fórmula bien formada que denota fórmulas tautológicas. El patrón se
escribe con variables (que no tienen que ver con las variables de la
lógica), estas variables toman como rango el conjunto de fórmulas
bien formadas.
César Ignacio García Osorio
Lógica y sistemas axiomáticos
20
P(a)
x
P(a)
Axiomas lógicos
de la implicación: α→(β→α)
■ Distribución de la implicación:
(α→(β→γ))→((α→β) →(α→γ))
■ Distribución universal: (∀x)(α→β)→ ((∀x)α→ (∀x)β)
■ Generalización universal: α→(∀x)α
■ Introducción
❚
■
■
Siempre que x no ocurra en α
■ Instanciación
universal: α→(∀x)β
x es una variable libre en α
❚ t es un término libre respecto a x en α, es decir, las variables de t
no tienen cuantificadores en cuyo alcance este x
❚ β se obtiene de α sustituyendo la variable x por el término t
❚
Lógica y sistemas axiomáticos
César Ignacio García Osorio
P(a)
■
■
■
x
■
21
■
■
■
César Ignacio García Osorio
α→β
¬β
¬α
Eliminación del ∧: α ∧ β
α
β
Instanciación universal:
(∀x)α
β
❚ β se obtiene de α sustituyendo x
Modus tollens:
■
x
Conceptos
Ω |– A G
cuando el sistema formal axiomático utilizado se sobreentiende se
escribe:
Ω |– G
⊥
Lógica y sistemas axiomáticos
22
Prueba formal: Sea Ω un conjunto de fórmulas bien formadas, A
un sistema formal axiomático y G una fórmula bien formada. Se
llama prueba formal de G a partir de Ω utilizando el sistema formal
axiomático A, a la secuencia finita de fórmulas bien formadas:
G1, G2, ..., Gn
donde Gn = G y, o bien Gi ∈Ω, o bien Gi es un axioma lógico de A,
o bien se ha obtenido aplicando una regla de inferencia de A sobre
fórmulas previas de la secuencia. Se denota por:
por un término t libre con
respecto a x en α
César Ignacio García Osorio
Lógica y sistemas axiomáticos
⊥
Modus ponens: α→β
α
β
Abducción:
α→β
β
α
Modus pones: α
β
α∧β
Conceptos
Reglas de inferencia: Constan de dos partes:
❚ condiciones o premisas: conjunto de patrones de fórmulas bien
formadas.
❚ conclusión: conjunto de patrones de fórmulas bien formadas.
Se pueden denotar por un conjunto de pares ordenados, o bien de la
forma:
fórmulas de premisas
fórmulas de conclusiones
Si los patrones de las premisas se ajustan con las fórmulas del
conjunto sobre el que queremos aplicar la regla de inferencia,
podemos obtener la conclusión. La generación de fórmulas es por
tanto una operación sintáctica.
P(a)
Reglas de inferencia
x
23
César Ignacio García Osorio
Lógica y sistemas axiomáticos
24
P(a)
■
■
x
P(a)
Conceptos
■
Regla de inferencia sólida: Sea Ω un conjunto de fórmulas bien
formadas, r una regla de inferencia y G una formula bien formada
obtenida aplicando r sobre Ω. La regla r se dice que es una regla de
inferencia sólida si para todo G se cumple que Ω ❘= G.
Sistema sólido: Sea Ω un conjunto de fórmulas bien formadas, G
una fórmula bien formada y A un sistema formal axiomático. A es
un sistema sólido si y sólo si para todo G que cumpla que:
Sistema completo: Sea Ω un conjunto de fórmulas bien formadas, G una
fórmula bien formada y A un sistema formal axiomático. A es un sistema
completo si y sólo si para todo G que cumpla que:
Ω ❘= G
Ω |– A G
Teoría: Una teoría T es una cuadrupla {LL, AL, AP, R} donde:
❚ LL es un lenguaje lógico.
❚ AL es un conjunto de axiomas lógicos.
❚ AP es un conjunto de axiomas propios de la teoría.
❚ R es un conjunto de reglas de inferencia.
■ Teorema: Se dice que una fórmula bien formada G es un teorema de una
teoría T si existe una prueba formal o derivación de G a partir de T (en
concreto a partir del conjunto de axiomas propios de T y usando el sistema
formal axiomático de T). La comprobación de G puede derivarse
efectivamente de T se llama demostración de teoremas.
■
se verifica además que:
Ω ❘= G
Es decir, un sistema formal axiomático se dice que es sólido si todo
G obtenido de un conjunto Ω de fórmulas bien formadas aplicando
reglas de A también es consecuencia lógica de Ω.
Lógica y sistemas axiomáticos
Conceptos
se verifica además que:
Ω |– A G
César Ignacio García Osorio
x
25
César Ignacio García Osorio
Lógica y sistemas axiomáticos
26