Argumentation A t ti in Artificial Intelligence: Theoretical Foundations and Technological Applications Carlos Chesñevar & Guillermo Simari

CONICET and Laboratory of R&D in A.I. Department of Computer Science and Engineering Universidad Nacional del Sur Bahía Blanca Blanca, Argentina

Argumentos

Argumentos ¨

Consideremos el siguiente ejemplo: •

¨

Creo en Dios porque la vida tiene significado. Si no hubiera Dios la vida no tendría significado.

El mismo ejemplo ligeramente reordenado: La vida tiene significado Si no hubiera Dios la vida no tendría significado Luego, creo que Dios existe.

3

Argumentos ¨

Esta construcción lingüistica se denomina Argumento.

¨

En el ejemplo anterior se argumenta a partir de las dos primeras sentencias: La vida tiene significado

Premisas

Si no hubiera Dios la vida no tendría significado. en favor f de d la l últi última: Luego, creo que Dios existe.

Conclusión

4

Argumentos ¨

Las primeras dos sentencias se ofrecen como razones que soportan la l úl última. i

¨

Es decir, las p premisas del argumento g darían lugar g o llevarían naturalmente a la conclusión.

¨

Así, un argumento puede definirse como una secuencia Así de sentencias, una de las cuales es la conclusión a favor de la que se argumenta, y las otras son las premisas, o razones para aceptar la conclusión.

¨

Esta relación entre las premisas y la conclusión es difícil de establecer y ha dado lugar a diversos problemas que mencionaremos brevemente en lo que sigue. 5

Sentencias ¨

Las sentencias q que componen p la secuencia argumentativa tienen la característica de p algo, g , es decir son declarativas,, que q expresar tiene la propiedad de ser verdadero o falso. ¨ No toda sentencia es declarativa, declarativa por ejemplo: ¡Alto! ¿Está ocupado? Gracias a Dios…

no son ni verdaderas ni falsas falsas. ¨ Discutiremos ahora el concepto de sentencia. 6

Sentencias vs Proposiciones ¨

La sentencia “Yo soy un hombre” es verdadera o falsa de acuerdo a quien la pronuncie pronuncie.

¨

Es decir que son sentencias diferentes que dependen d l contexto del t t para determinar d t i su significado. i ifi d

¨

En lo que sigue supondremos que el contexto no cambia bi durante d t lla enunciación i ió d dell argumento. t

¨

Esta convención determina el significado de los argumentos t all fij fijar ell significado i ifi d d de cada d sentencia t i que pertenece a la secuencia de sentencias que lo forman.

¨

Esta elección es una abstracción necesaria para poder dar un tratamiento sistemático a la construcción y análisis de los argumentos 7

Sentencias vs Proposiciones ¨

Por ejemplo, en el argumento: Todas las mujeres son mortales Yo soy una mujer Luego, soy mortal

¨

El agente que pronuncia las sentencias se considera fij all iiguall que ell contexto fijo, t t generall d donde d estas t son enunciadas.

¨

Estas E t sentencias t i con significado i ifi d fij fijo se d denominan i proposiciones.

8

Sentencias vs Proposiciones ¨

Existe otra diferencia entre sentencias y proposiciones. i i Por ejemplo, las sentencias: •

Der Schnee ist weiss

•

La neige est blanche

•

Snow is white

•

La nieve es blanca

establecen la misma proposición a pesar de las diferencias aparentes entre ellas. ¨

Es decir, las proposiciones son independientes del lenguaje. g j 9

Argumentos ¨

Algunos argumentos son convincentes y otros no lo son.

¨

P ejemplo: Por j l Los seres humanos son los únicos seres racionales. Solo la racionalidad permite a los seres realizar juicios morales. Luego, solo los seres humanos tienen la capacidad de tener metas propias.

¨

Sin duda esta secuencia de sentencias es un argumento, pero no es el tipo de secuencia que querríamos aceptar como tal. ¿Por qué?

¨

En p principio, p no existe una conexión aparente p entre las premisas y la conclusión del argumento. 10

Argumentos ¨

El siguiente argumento, cuyo origen es incierto pero que ciertamente es muy antiguo antiguo, parece ser convincente: Los seres humanos son mortales. S Sócrates es un ser humano. h Luego, Sócrates es mortal.

¨

¿Por qué razón sentimos que es buen argumento?

¨

Percibimos una fuerte conexión entre las p premisas y la conclusión del argumento.

¨

No parece posible aceptar las premisas y rechazar la conclusión dado que, intuitivamente, percibimos que la conclusión está contenida implícitamente en las premisas. i 11

Argumentos ¨

Veamos otro ejemplo, Es imposible realizar el acto de criticar unicamente a aquellos que no son autocríticos. Luego, en ciertas cosas los seres humanos no poseen libre Luego albedrío (o voluntad propia).

¨

Si fuera p posible ejecutar j el acto se daría una situación p paradójica. j

¨

Para analizar la factibilidad de ejecutar la acción propuesta consideremos las dos posibilidades para un agente particular: ¿Es E autocrítico t íti o no lo l es? ?

¨

•

Si fuera autocrítico, por definición se criticaría a si mismo y por lo tanto no debería criticarse y no sería autocrítico.

•

Si no fuera autocrítico debería criticarse y así sería autocrítico.

Es decir, en ambos casos se llega a una contradicción (cuyo origen es la autoreferencia) y de alli la conclusión queda establecida. 12

Argumentos ¨

Volviendo al ejemplo de Sócrates: Los seres humanos son mortales. Sócrates es un ser humano. humano Luego, Sócrates es mortal.

¨

Las virtudes que este argumento posee son, entre otras, otras las siguientes: • Sus premisas son verdaderas • El razonamiento es válido

13

Argumentos ¨

La p primera virtud se refiere a la verdad de las premisas y poco se puede decir aquí, dado que establecer la verdad o falsedad de las q premisas no es parte de la Lógica.

¨

La segunda L d virtud it dh habla bl d de lla validez lid del d l razonamiento y es la que crea el ámbito de t b j d trabajo de Ló Lógica i como di disciplina. i li

¨

Otras virtudes, virtudes tales como relevancia, relevancia han dado lugar a extensiones de Lógica.

14

Validez ¨

La idea de validez de un argumento desde el punto de vista clásico es simple: • Un argumento es válido si no es posible que las premisas sean verdaderas y la conclusión no lo sea. sea

¨

Es decir, no se puede imaginar en una situación en la que las premisas sean satisfechas y la conclusión no no.

¨

El argumento sobre la mortalidad de Sócrates es válido porque si aceptamos que los hombres son mortales y que Sócrates es un hombre no es posible pensar en una situación en estas premisas sea verdaderas y en la que Sócrates no sea mortal.

¨

Los argumentos inválidos son aquellos que no son válidos. 15

Sensatez ¨

Un argumento puede ser válido pero aún puede ser un mall argumento.

¨

Para ello basta con que se apoye en una o más premisas falsas.

¨

Tales argumentos se dicen válidos pero no sensatos (unsound)

¨

Un argumento es sensato (sound) si

¨

a.

es válido y además

b b.

t d sus premisas todas i son verdaderas. d d

En general, no estudiaremos argumentos que no sean sensatos. t 16

Evaluando Argumentos g ¿Es posible que todas las premisas i sean verdaderas d d y lla conclusión sea falsa? No es posible

Es posible

El Argumento es válido

El Argumento es inválido

¿Son las premisas verdaderas? Si

El argumento es sensato

No

El argumento no es sensato

Contraejemplos ¨

Analicemos el siguiente argumento: Todos los cirujanos son cuidadosos en su tarea. tarea Juan no es un cirujano. L Luego, J Juan no es cuidadoso id d en su ttarea

¨

Nuestra intuición nos dice que hay algo incorrecto en la construcción de este argumento argumento.

¨

¿Pero como estar seguros?

¨

Una forma es diseñar una na situación sit ación en la q que e las premisas sean verdaderas y la conclusión falsa.

¨

Basta con elegir un Juan particular que sea una persona cuidadosa y que no sea cirujano. Sin duda existen estas personas! Por ejemplo, los pilotos de avión.

¨

Este sería un contrajemplo para la validez del argumento. 18

Contraejemplos ¨

Analicemos otro argumento: Al Alguna gente t fuma f en pipa. i Alguna gente fuma cigarros. Luego, alguna gente fuma en pipa y también cigarros

¨

Este argumento también parece ser incorrecto.

¨

Para dar el contraejemplo basta con elegir un conjunto de personas separable p p en dos subconjuntos j disjuntos j de personas tales que en un subconjunto están los que fuman solo pipa y en el otro los que solo fuman cigarros.

¨

Observemos que en el mundo existen personas que fuman tanto pipa como cigarros pero la situación en la estas personas no existen i t es concebible. bibl 19

Contraejemplos ¨

¨

El mecanismo para construir un contraejemplo sigue los siguientes pasos: 1 1.

Se afirma la verdad de todas las premisas

2.

Se niega que la conclusión del argumento sea verdadera d d

3.

Se dá una explicación de como esto puede ser posible

Al seguir estos tres pasos se diseña una situación en la que el argumento es inválido.

20

Argumentos Deductivos

Argumentos ¨

Los argumentos descriptos se denominan argumentos deductivos. deductivos

¨

Los argumentos válidos de este tipo siguen formas reconocidas como sensatas sensatas.

¨

Estas formas garantizan que si se introducen premisas ciertas la conclusión deberá serlo serlo.

¨

Por ejemplo,

¨

•

T d los Todos l Gonks G k son Tronks T k

•

Sócrates es un Gonk

•

L Luego, S Sócrates es un Tronk T k

Se observa que tiene la misma forma que el argumento sobre b lla mortalidad t lid d d de Só Sócrates. t 22

Argumentos ¨

La forma es, •

Todos los

son

•

☺ es un

•

Luego, ☺ es un

¨

Si se reemplazan consistentemente los símbolos, a igual símbolo le corresponde p igual g reemplazo, p , se obtiene un argumento válido.

¨

Es decir, decir cualquier situación que haga falsa la conclusión también hará falsa al menos una premisa.

¨

E i t muchas Existen h formas f con esta t propiedad. i d d 23

Argumentos ¨

Las siguientes son algunas otras formas con la propiedad de producir argumentos válidos válidos. T d los Todos l

son

Al Algunos

Todos los

son ☺

Todos los

Luego, todo

Todo

es un ☺

es un

o un ☺

no es un E Entonces,

son son ☺

Así, algunos

Todo

es un

Por lo tanto,

son ☺

y un ☺ es un

es un ☺ 24

Consistencia ¨

Un conjunto de sentencias se dice consistente si es posible ibl que todas d ellas ll sean simultáneamente i lá verdaderas. d d

¨

Si esto no es posible, el conjunto se dice inconsistente.

¨

Por ejemplo, Sócrates en un hombre de gran moral Sócrates roba regularmente de las arcas del estado No es posible tener gran moral y robar

¨

Estas tres sentencias no pueden ser simultáneamente verdaderas. 25

Consistencia y Validez ¨

Sorprendentemente, las nociones de consistencia y validez están relacionadas, relacionadas a pesar de ser conceptos diferentes diferentes.

¨

Decir que un argumento es válido equivale a decir que algo es imposible: no puede suceder que las premisas sean verdaderas y la conclusión falsa.

¨

Decir que un conjunto de sentencias es inconsistente es equivalente a decir que algo es imposible: no puede ser que todas las sentencias sean simultáneamente verdaderas.

¨

Un argumento válido garantiza que la conclusión es verdadera.

¨

Un conjunto inconsistente garantiza que no es posible que sus miembros sean todos simultáneamente verdaderos. 26

Consistencia y Validez La relación entre ambos conceptos esta reflejada en el siguiente procedimiento: a.

Tomamos el argumento que deseamos testear por validez considerado como un conjunto de sentencias.

b b.

Reemplazamos la conclusión por la afirmación de que la misma es falsa.

c.

Ch Chequeamos por consistencia ell conjunto resultante. l

d.

j es inconsistente el argumento g es Si este conjunto válido, si el conjunto es consistente entonces el argumento es inválido.

27

Consistencia y Validez ¨

¿Por qué este procedimiento resulta efectivo para verificar validez? lid ?

¨

Si el conjunto de premisas ampliado con la afirmación de que la conclusión es falsa es consistente consistente, entonces es posible pensar en una situación en la que las premisas son verdaderas y la conclusión es falsa.

¨

Esto es así porque todas las sentencias de este conjunto son verdaderas, en particular las premisas y la afirmación de que la conclusión es falsa f son sentencias verdaderas.

¨

Si la afirmación “la conclusión es falsa” es una sentencia verdadera d d entonces t la l conclusión l ió puede d ser ffalsa l all mismo i tiempo que las premisas son verdaderas.

¨

Luego el argumento debe ser inválido Luego, inválido. 28

Premisa-1, Premisa-2 …, Premisa-n “Es Es falso que que” + Conclusión

Consistencia y Validez

Test de Consistencia

Argumento válido

Argumento inválido

Inconsistente

Consistente

Un Problema El Misterio de la Mansion Dreadsbury La tía Agata fue asesinada por alguien que vive en la mansion. mansion Agata, el mayordomo y Charles viven en Dreadsbury Mansion, y ellos son los únicos que viven alli alli. Un asesino siempre odia a su víctima y nunca es más rico que ella. Charles no odia a nadie que la tía Agata odia. Agata odia a todo el mundo menos al mayordomo. El mayordono odia a todos los que no son tan ricos como la tía Agata. El mayordomo odia a todos los que la tía Agata odia. Nadie odia a todos. Agata no es el mayordomo. Dadas estas pistas, tres detectives noruegos no pueden ponerse de p Bjorn j está seguro g de qque Charles no lo hizo. acuerdo. El Inspector ¿Tendrá razón? El Inspector Reidar está seguro de que fue suicidio. ¿Será cierto? El Inspector Olaf está seguro de que, en contra de la sabiduría popular, popular mayordomo es inocente. inocente ¿Será así? 30

Lógica ¨

Hemos discutido muy someramente un área cuyo desarrollo comenzó hace más de dos milenios y medio.

¨

Nuestro objetivo es poder estudiar el razonamiento llevado a cabo en lenguaje natural en los debates y otros contextos estructurados.

¨

Esta disciplina nació del intento de desarrollar que p pudieran analizar y evaluar herramientas q ese razonamiento informal.

31

Lógica ¨

Durante la segunda mitad del siglo XIX otros desarrollos confluyeron en la creación de la Lógica Formal, aunque hubo intentos previos que confluyeron en ese momento.

¨

Es costumbre obviar el adjetivo Formal al referirse a ella, así Lógica significa Lógica Formal. Formal

¨

Desde hace algunos g años existe un área de investigación conocida como Lógica Informal que g estudia argumentación. 32

Lógica Lógica, de acuerdo al diccionario, es: “...la ciencia que trata con los principios y criterios para establecer la validez de la inferencia y demostración: es la ciencia de l principios los i i i formales f l del d l razonamiento” i t ”

33

Lógica ¨ Esos principios y criterios son siempre descriptos en términos de un lenguaje en el que la inferencia, f demostración y razonamiento p pueden ser expresados. p ¨ Pero esto no es todo ... (

34

Formalismo y Lógica ¨

La Lógica es la disciplina que estudia los formalismos.

¨

En el orden de las cosas la Lógica está en la l provincia i i d de lla Fil Filosofía. fí

¨

Los Matemáticos aplicaron a problemas abstractos las ideas desarrolladas en la Fil Filosofía. fí

35

Lógica ¨

El desarrollo de la Lógica Matemática comenzó a mediados del siglo XIX y alcanzó gran impulso i l a comienzos i d dell siglo i l XX y permitió abordar problemas centrales de los F d Fundamentos t de d la l M Matemática. t áti

¨

Hacia mediados del siglo XX se logró caracterizar la idea moderna de Computabilidad. Computabilidad

36

Computación y Lógica ¨

Turing T i desarrolló d lló su id idea d de máquina á i abstracta tratando de encontrar un formalismo alternativo lt ti para los l F Fundamentos d t de d lla Matemática.

¨

Luego surgió la Tesis de Church-Turing en la que la l fformalización li ió d de lla id idea d de procedimiento efectivo es la Máquina d desarrollada ll d por T Turing. i

37

Matemática, Computación y Lógica La noción de procedimiento efectivo intervino de manera decisiva en la demostración de que cualquier fragmento d la de l M Matemática t áti que iincluyera l a lla que no son Aritmética contiene verdades q demostrables (Kurt Gödel, 1931).

38

Lógica Análisis Matemático

Lógica

Física

Ciencias de la Computación Observación de John McCarthy en los años 60.

La Lógica ha permitido plantear los problemas computacionales con rigor y precisión científica. Lentamente se está logrando evolucionar desde ARTESANÍA y TÉCNICA a CIENCIA e INGENIERÍA 39

¿Por qué esto es interesante? ¨

Cada Sistema Computacional es una SIMULACIÓN conceptual de algún aspecto de la realidad.

¨

A esta simulación se asocia un proceso de abstracción.

¨

Durante D t la l abstracción b t ió se d descartan t aspectos t no esenciales para el sistema.

¨

¡El proceso de abstracción es la fuente de los errores!

¨

El formalismo lógico sirve al propósito de minimizarlos. 41

Una Tríada ¨

Al definir un lenguaje declarativo es necesario dar cuenta t d de tres t componentes t esenciales: i l Sintaxis ((Forma del lenguaje) g j ) Semántica (Significado del lenguaje) Pragmática (Uso del lenguaje)

¨

Es posible que para cierto tipo de lenguajes sea necesario incluir o separar otros componentes.

¨

Por ejemplo, en los lenguajes naturales es guías de p pronunciación. necesario dar g 42

Una Tríada En la Representación Computacional de la Realidad aparecen las mismas características con la particularización de la pragmática al uso computacional: Sintaxis (Forma) S Semántica (S (Significado) f d ) Computación (Evolución)

43

Representación Computacional de la Realidad ¨

Deciamos que al definir un lenguaje declarativo para representar t computacionalmente t i l t la l realidad es necesario dar cuenta de tres componentes esenciales: Sintaxis (Forma) ( ) Semántica (Significado) Computación (Evolución)

¨

Buscaremos relacionar esas tres nociones.

45

Sintaxis: Lenguajes Formales ¨ Al definir un lenguaje formal para expresar conocimiento i i t acerca d dell d dominio i i (“ (“mundo”) d ”) se debe definir su sintaxis de manera de describir l fórmulas las fó l llegales l del d l llenguaje. j ¨ Primero se establece cuales son los símbolos legales y luego se definen reglas para formar expresiones aceptables a partir de ellos ellos. ¨ Las fórmulas legales se especifican por medio de una gramática.

46

Semántica ¨

Dado un dominio, la semántica determina el significado i ifi d de d llas sentencias t i d dell llenguaje j en ell dominio, es decir, su designación en ese dominio. dominio

¨

Así, se pone de manifiesto un compromiso en la relación de los símbolos del lenguaje con el dominio.

¨

Este compromiso semántico permite discutir la correctitud tit d y/o / la l veracidad id d del d l conocimiento i i t d de manera independiente al uso que de él se haga haga. 47

Teoría de Prueba ¨ Usualmente, esta teoría consiste de un conjunto de R l d Reglas de IInferencia. f i ¨ Cada una de estas reglas de inferencia es un patrón de arg mentación o de ra argumentación, razonamiento onamiento reconocido como correcto. ¨ Hay dos criterios fundamentales para la construcción de estas reglas: Dado un conjunto de premisas premisas, las reglas deben permitir inferir solo aquellas conclusiones que se siguen logicamente de estas premisas. Dado un conjunto de premisas, las reglas deben permitir inferir todas las conclusiones que se siguen logicamente d estas de t premisas. i 48

Teoría de Prueba y Semántica ¨ Es posible que la Teoría de Prueba y la Semántica no se adecuen (no se lleven bien). ¨ Si la Teoría de Prueba solo infiere respuestas correctas en acuerdo con la Semántica se dice que es Sana o Sensata o Sólida (en inglés Sound). ¨ Si genera todas las respuestas correctas se dice que es Completa. Completa

49

Teorías Formales

Teorías Formales ¨

Veremos ahora una forma de establecer de manera clara los tres elementos mencionados: Sintaxis,, Semántica,, Teoría de Prueba.

¨

Las definiciones que siguen se mantendrán a un nivel intuitivo con la intención de dar un marco general para desarrollos formales posteriores.

¨

El objetivo bj ti es iintroducir t d i llos elementos l t básicos presentes en cualquier formalismo ló i lógico. 51

Motivación ¨

Intuitivamente, la definición de una teoría Intuitivamente formal puede entenderse como la especificación de un “juego juego (formal) (formal)”.

¨

Esto es, se debe introducir un lenguaje y reglas no ambiguas para manipularlo.

¨

Un punto determinado en el desarrollo del juego será una situación válida si se puede llegar a ella con las reglas dadas a partir de un estado inicial.

52

Teoría Formal DEFINICIÓN: Una teoría formal T consiste de: 1. Un conjunto contable de símbolos.

53

Conjuntos contable Def: Un conjunto es numerable si puede construirse una correspondencia biunívoca con el conjunto N de los números naturales. Def: Un conjunto es contable, si es finito o numerable. Ejemplos de conjuntos contables: { a, b, c } (finito) { 1, 2, 3, +, ∗ } (finito) Enteros Z (numerable) ( ) Impares I (numerable) { Xi con i un natural } (numerable) 54

Conjuntos de símbolos Ejemplo: El conjunto Z de los enteros es numerable. Sea f la función de Z en N definida por si k < 0 entonces f(k) = –2k 2k si k ≥ 0 entonces f(k) = 2k+1 ( (suponiendo i d N = {1, { 2, 3, ... } ) Deben convencerse de que este mapeo es una biyección, i.e. una correspondencia biunívoca en los enteros y los naturales. naturales 55

Teoría Formal (cont.) DEFINICIÓN: Una teoría formal T consiste de: 1. Un conjunto contable de símbolos. Se llamará expresión a toda secuencia finita de símbolos.

56

Ejemplos de Expresiones Si el conjunto de símbolos es { a } ¿Qué expresiones se pueden formar? Hay infinitas expresiones:

a,, aa,, aaa,, aaaa,, ... ¿Y con el conjunto de símbolos { a, ∗ }?

∗∗∗, a, a∗a, ∗a∗, ∗∗∗a∗aaa, ...

57

Teoría Formal (cont.) DEFINICIÓN: Una teoría formal T consiste de: 1. Un conjunto contable de símbolos. Se llamará expresión a toda secuencia finita de símbolos. 2 Un 2. U subconjunto b j t d de llas expresiones i llllamado d Fórmulas Bien Formadas (fbf), en inglés wff.

58

Ejemplos de fbfs Si las fbfs fueran fbfs del tipo: a, ∗a, ∗∗a, ∗∗∗a, ∗∗∗∗a, ∗∗∗∗∗a, ... ¿cómo se definen estas fbfs? 1. a es una fbf, y 2 si Q es una fbf 2. fbf, entonces ∗Q es una fbf fbf. Metavariable

59

Esquemas, meta-variables e instancias ¨

Un esquema provee un molde para especificar la forma de una expresión.

¨

Dado el conjunto de símbolos { 1, 2, +, x, z } y siguiente definición de fbf: 1 , 2, 2 x, x y z son fbfs yy, si P y Q son fbfs entonces Q + P + Q es una fbf.

En este ejemplo P y Q no son elementos “en” el g j sino q que se “refieren” al mismo. lenguaje P y Q son meta-variables. Q + P + Q es un esquema. esquema 60

Esquemas, meta-variables e instancias ¨

Una instancia de un esquema se obtiene reemplazando cada meta-variable por una misma expresión del lenguaje. lenguaje

¨

Dada la definición: 1, 2, x, y z son fbfs y, si P y Q son fbfs entonces Q+P+Q es una fbf.

Entonces, x+2+x, 1+1+1, 2+1+2+1+2 son fbfs, fbfs pero 1+2+2, Q+P+Q, 3 no lo son. 61

Teoría Formal (def. completa) DEFINICIÓN: Una teoría formal T consiste de: 1. Un conjunto contable de símbolos. Se llamará expresión a toda secuencia finita de símbolos. 2 Un 2. U subconjunto b j t d de llas expresiones i llllamado d Fórmulas Bien Formadas (fbf), en inglés wff. 3. Un subconjunto de las fbf llamado Axiomas. 4. Un conjunto finito de relaciones sobre las fbf llamadas Reglas de Inferencia. 62

Reglas de Inferencia ¨

Recordemos que estas reglas relacionan las premisas i con una conclusión. l ió

¨

Más formalmente,, una regla g de inferencia es una relación R de n fbfs F1, ..., Fn-1, Q tal que es p posible decidir si la n-upla p ((F1, ...,, Fnn-11, Q) pertenece a la relación R.

¨

Si (F1, ..., Fn-1, Q) ∈ R entonces la conclusión Q se dice una consecuencia directa de las premisas F1, ..., Fn-1 por la aplicación de la regla de inferencia R.

63

Reglas de Inferencia Veamos algunos ejemplos de diferentes formas d describir de d ibi reglas l de d iinferencia, f i d donde d PyQ son metavariables que representan fbfs: a) Si P+Q es una consecuencia directa de P y Q entonces, para toda fbf P y Q, esta regla de inferencia define la relación (P, Q, P+Q). b) Dada la relación (P, P∗Q, Q) entonces se dice que Q es una consecuencia directa de P y P∗Q para toda fbf P y Q.

64

Reglas de Inferencia Ej Ejemplos l (continuación): ( ti ió ) c) Si Q es una consecuencia directa de P y P∗Q entonces, para toda fbf P y Q, se puede escribir: P , P∗Q

Q

o también P

P∗Q Q 65

Teoría Formal

L Lengua aje

1.

Un conjunto contable de símbolos. Se llamará expresión ió a toda t d secuencia i fi finita it de d símbolos. í b l

2.

Un subconjunto de las expresiones llamado Fórmulas Bien Formadas (fbf), en inglés wff.

Prrueba

DEFINICIÓN: Una teoría formal T consiste de:

3.

Un subconjunto de las fbf llamado Axiomas.

4 4.

Un conjunto finito de relaciones sobre las fbf llamadas Reglas de Inferencia. 66

Ejemplo: la Teoría Formal V El lenguaje: ¨

Conjunto de símbolos: { ∗,

¨

Fbfs: i es una fbf para todo Fbf t d i natural, t l y si P y Q son fbfs entonces P ∗Q es una fbf

i

con i natural }

Mecanismo de prueba (Máquina inferencial): ¨

Esquemas de Axioma: (solo una en este caso) P∗P

¨

Reglas de Inferencia: (solo una en este caso) P ∗Q Q es consecuencia directa de P ∗W W y Q ∗S S (i.e. P ∗W, Q ∗S P ∗Q )

67

Ejemplo: la Teoría Formal V ¨

C j t d Conjunto de símbolos: í b l { ∗, Ejemplos de Expresiones: ∗

¨

Fbfs:

i

i

con i natural t l} ∗∗ 1∗∗,

∗∗ 5∗∗,

3

92

es una fbf para todo i natural, y

si P y Q son fbfs entonces P∗Q es una fbf. Ejemplos de fbfs:

9,

1923,

1∗

2∗

12

68

Ejemplo: la Teoría Formal V ¨

¨

Esquema de Axioma: P∗P Ejemplos: 1∗ 1, 100101∗

100101

Regla R l d de IInferencia: f i P∗Q es consecuencia directa de P ∗W y Q ∗S (i.e. P∗W, Q∗S P∗Q ) je p o Ejemplo: 8∗

1

1∗

1

8∗

es consecuencia directa de (i.e.

8

∗

8,

1

∗

1

8

∗

8

y

1)

69

Ejemplo: la Teoría Formal V Ejemplos de los elementos que la forman: ¨

Expresiones: ∗

¨

Fbfs:

¨

Axiomas:

¨

Inferencia: 8∗ 8∗ 8 y 1∗ 1 (i.e.

9,

8∗

1∗∗,

3

∗

2

1923, 1∗

8,

1

1∗

∗∗,

∗

100101∗

1, 1

5

92

12 100101

es consecuencia directa de

1

8∗

1

)

70

Teoría T í de d Prueba

Deducibilidad, derivaciones y pruebas Def: Sea T una teoría, S un conjunto de fbfs (hipótesis o premisas) i ) y P una fbf (conclusión) ( l ió ) en T, T se dice di que P es deducible a partir de S en T (denotado S T P o S P) sii existe i t una secuencia i fifinita it d de fbf fbfs P1, P2, ..., Pn tal t l que Pn = P y para todo 1≤i≤n, 1 1.

Pi es un axioma, i o

2.

pertenece a S, o

3.

Pi se obtiene como una consecuencia directa por la aplicación de alguna regla de inferencia sobre elementos de la secuencia que preceden a Pi

Tal secuencia se llama derivación o prueba de P a partir de S en T. 72

Deducibilidad, derivaciones y pruebas Siguiendo con la teoría V: P ∗P es un axioma y P ∗Q es una consecuencia i di directa t d de P ∗W W y Q ∗S S Ejemplo: j p {

2∗

3

1∗

}

2

Una secuencia de prueba o derivación es: 1∗

1,

↑ (axioma),

2∗

↑

3,

1∗

2

↑

(hipótesis), (aplicación de R.I.)

73

Teoremas Def: Sea P una fbf de una teoría T si P es deducible a partir del conjunto vacío (denotado P o T P ) se dice que P es un teorema en T o que es demostrable en T. En la teoría V : P∗P es un axioma y P∗Q es una consecuencia i di directa t d de P∗W P W y Q∗S. Q S ¿

1∗

2

es teorema?, i.e. ¿

1∗

2?

(¿

V

1∗

2

?)

1.

1∗

1

axioma.

2 2.

2∗

2

axioma axioma.

3.

1∗

2

se deduce de 1 y 2 por la regla de inferencia.

74

Teoremas ¨

Los axiomas proveen un conjunto de fbfs que es posible ibl utilizar ili en lla d deducción d ió en cualquier l i momento.

¨

Observemos, trivialmente, q que todo axioma es un teorema.

¨

¿Cuál sería la secuencia de prueba?

¨

Por ejemplo, ¿es 1.

1∗

1

1∗

1

teorema?, i.e. ¿

1∗

1?

axioma.

Y esa es la secuencia de prueba completa completa.

75

Propiedades de Sea T una teoría, S1 y S2 conjuntos de fbf y P y Q fbf de fbfs d T. T p de Monotonía: Propiedad Si S1 ⊆ S2 y S1 P entonces S2 P Propiedad de Compacidad: S1 P sssi existe un subconjunto finito S2 de S1, tal que S2 P Propiedad de Modularidad: Si S1 P y para cada fbf Q en S1 vale que S2 Q entonces S2 P

76

Semántica

Interpretaciones ¨

Dada una teoría formal, resulta interesante obtener bt una visión i ió en té términos i d de otras t cosas conocidas.

¨

La forma natural de realizar esto es dar significado a los símbolos utilizados en la formación de expresiones y de alguna manera realizar la propagación de este significado atómico ó para obtener el significado f de las ffbfs f más complejas.

¨

Esto se realiza por medio de una “aplicación” que p recibe el nombre de interpretación. 78

Interpretaciones y modelos Def: Una interpretación proporciona un significado para cada d uno d de llos símbolos í b l d de una tteoría í fformal, l de tal forma que toda fbf es verdadera o falsa bajo esa interpretación. i t t ió Def: Una interpretación p I es un modelo p para un conjunto de fbfs S si toda fbf de S es verdadera bajo p I. la interpretación Obs: Una interpretación I provee un modelo para una teoría t í formal f l T, T sii provee un modelo d l para ell conjunto de teoremas de T. 79

Interpretaciones y modelos ¨

Si una fbf P es verdadera en todas las interpretaciones usualmente esto se denota P y se dice que P es lógicamente verdadero.

¨

Dadas dos fbfs P y Q son tales que todo modelo de P es modelo de Q decimos q que P implica lógicamente a Q y se denota P Q

80

Meta Teoría Meta-Teoría

Conceptos Meta-teóricos ¨

Hemos definido la noción Sintáctica de demostrabilidad en la teoría (teorema). Denotado P

¨

También definimos la noción Semántica de verdad d d en todas t d las l iinterpretaciones. t t i Denotado P

¨

Ambos conceptos no están en principio relacionados. relacionados

82

Conceptos Meta-teóricos ¨

Las relaciones entre estos dos conceptos son sobre la teoría. Es decir, es parte de la metateoría. teoría ¨ Una teoría es completa si toda fbf que es verdadera en todas las interpretaciones es demostrable en la teoría. Si P entonces P ¨

Una teoría es sensata (sound) si toda sentencia t i demostrable d t bl en lla tteoría í es verdadera en todas las interpretaciones. Si P entonces P 83

Completitud y Sensatez: Ejemplo Sea A la teoría definida por: • Conjunto de símbolos: { a, } • Fbfs: a es una fbf,, y si Q es una fbf,, entonces Q es una fbf. • Esquema de Axiomas: a • Regla de Inferencia: Q es una consecuencia directa de Q. Q ¿Qué fbfs son demostrables en esta teoría? TODAS Entonces, la teoría es completa (Si P entonces P), pero NO es sensata (Si P entonces P). P) ¿Porqué? 84

Completitud y Sensatez ¨

En general, una teoría podría ser completa y sensata, podría verificar solo alguna de las dos metapropiedades o no cumplir ninguna de ellas.

¨

La sensatez y/o completitud son propiedades que deben demostrarse, no pueden asumirse.

¨

Una teoría que demuestra cosas falsas no parece de mucha utilidad.

¨

Una teoría en la cual toda fbf puede demostrarse es completa, pero no es sensata (¿porqué?).

¨

En una teoría sensata y completa, verdad y deducción parecen ser equivalentes, pero ... 85

Conceptos Meta-teóricos (2) ¨

Una teoría formal es consistente si no es posible demostrar en ella una fbf y su negación.

¨

Un método computacional es completo para una teoría si aplicado a cualquier fbf este termina en tiempo finito indicando si la fbf es verdadera en todas las interpretaciones.

¨

Una teoría formal es decidible si existe un procedimiento efectivo q p que determine p para cada fbf si esta fórmula es demostrable en la teoría. 86