4. representaciÓn formal - disi.unal.edu.codisi.unal.edu.co/~lctorress/iartificial/ia0009l.pdf ·...

4. REPRESENTACIÓN FORMAL"Es fácil tocar cualquier instrumento musical:

todo lo que hay que hacer es tocar la tecla correcta en el instante apropiado, y el instrumento tocará sólo"

J.S. Bach.

Una motivación importante en el uso de programas de computador es incrementar lafiabilidad, oportunidad y completez con la que se aplica conocimiento para ejecutaruna determinada tarea. La lógica, como herramienta para el análisis delcomportamiento racional tiene una historia milenaria, por tanto juega un papeldestacado en la representación del conocimiento.

Aristóteles (384-322 a.C.), es considerado el padre de la lógica, valorado así por losgriegos por la gran capacidad para la oratoria1, al construir argumentos persuasivos afavor, y refutar argumentos de los demás; Aristóteles creo métodos sistemáticos paraanalizar y evaluar los argumentos. El análisis científico aristotélico transcurrió enforma sosegada de lo general a lo particular, aplicando silogismos dentro de unaconcepción de la unidad de la ciencia. Desarrolló la lógica silogística y catalogó unbuen número de falacias usadas en los argumentos; mediante la inducción y deducciónestableció el método de investigación que conduciría al conocimiento.

Un siglo después de Aristóteles, otro griego Chryssipus desarrolló la lógicaproposicional, determinó procedimientos para hallar la verdad o falsedad de unaproposición compuesta a partir de la verdad o falsedad de sus componentes.

El trabajo de los lógicos medievales culminaron con William de Occam, quiendesarrolló la lógica modal2 en el siglo XIV, la cual incluye conceptos tales comoposibilidad, necesidad, creencia, duda, etc.

En el siglo XVII, Wilhelm Leibniz (1676-1716), planteó un esquema para que lamáquina razonara, una "característica universal", un cálculo para cubrir todopensamiento y reemplazar controversias en los cálculos, requiriéndose para ello que elconocimiento estuviese en forma sistemática. Además, planteó que la dependencialógica entre proposiciones se logra reduciendo conceptos amplios a conceptos simplesque lo constituyen; igualmente, buscó representar el conocimiento en una forma que

1 Se llamó oratoria a la habilidad para refutar o plantear argumentos en un debate público. 2 La lógica modal es el método clásico para razonar sobre el conocimiento, aumenta la capacidad de lalógica de primer orden por medio de operadores modales, tales como C (cree) y S (sabe), con los que lasoraciones constituyen argumentos en vez de términos.

Inteligencia artificial

Luis Carlos Torres Soler122

pudiera usarse en un razonamiento mecánico,3 desafortunadamente, no contó conherramientas para implementar sus ideas. Solamente con las capacidades del modernocomputador es que puede concebirse remotamente aproximarnos a la representacióndel conocimiento y a los sistemas de razonamiento propuestos por Leibniz.

El progreso de la lógica continuo su desarrollo en el siglo XIX por filósofos ymatemáticos como Bolzano, De Morgan, Boole, Venn y Frege.

En 1854 George Boole (1815-1864) publicó "Una investigación de las leyes delpensamiento", en la cual se fundamentan teorías matemáticas de lógica y probabilidad.El mayor logro del libro fue la demostración de las herramientas del álgebra que seaplican en la deducción lógica. Boole tomó los operadores aritméticos de adición,multiplicación y sustracción y creo sus operadores lógicos equivalentes de unión,intersección y el conectivo "de negación". Boole también formuló las tablas de verdaden orden a comprobar la verdad de proposiciones compuestas.

Fue Gottlob Frege (1848-1925) quien creó una teoría completa de la lógica, queexcepto, algunos cambios de notación, es la lógica de primer orden que se utilizaactualmente en la representación de conocimiento. Alfred Whitehead y BertrandRussell4 (1872-1970) hacia 1910 codificaron la lógica en su presente forma como unsistema por reducciones matemáticas. La constitución de la lógica formal moderna es amenudo atribuida a ellos. En 1930, Kurt Gödel (1906-1978) demostró que existe unprocedimiento eficiente para demostrar cualquier aseveración verdadera en la lógica deprimer orden de Frege y Russell.

La lógica formal ha tenido su desarrollo a pesar de innatas tendencias de humanos airracionales y emocionales conductas que se hallan a menudo fuera de cualquierlógica. La lógica está fuertemente relacionada con los procesos para manipular yrepresentar conocimiento a fin de probar la validez de proposiciones o predicadosteniendo en cuenta la validez de los argumentos que posean (ver anexo B), esto es, lalógica son métodos para determinar si unas conclusiones pueden deducirse partir deunos hechos supuestos5.

Las lógicas con mayor desarrollo son:

- Lógica booleana o bivaluadas, lógica de proposiciones. Son aquellas en la quesólo se admiten dos valores: verdadero o falso (uno o cero, blanco o negro).

3 Leibniz fue optimista y apoyó la visión mecanicista del mundo con importantes contribuciones a lafísica y a la matemática. Las causas finales o teológicas fueron también su preocupación, apoyándose enconcepciones analógicas. 4 Russell particularmente desarrollo toda la aritmética en términos de lógica pura.5 El análisis logístico estudia el crecimiento del conocimiento a partir de juicios y razonamiento conproposiciones concretas lógico-matemáticas y con un lenguaje que se manifiesta en una sintaxis.

Representación formal

Universidad Nacional de Colombia 123

- Lógica de orden 0+, permite la representación en ternas del tipo objeto,atributo, valor.

- Lógica trivalente. Es aquella en que las variables admiten tres posiblesvalores.

- Lógica multivalente. En la que las variables toman muchos valores discretos.

- Lógica de primer orden o lógica de predicados.

- Lógica difusa o borrosa. Una generalización de la lógica multivalente ypermite la existencia de valores continuos entre los valores límites (creada porLofti Zadeh en 1965)

La lógica difusa nace de la necesidad para representar proposiciones como: María esmuy alta, Luis está un poco enfermo, Ganar Millonarios es casi imposible, Lamayoría de mujeres vallunas son bellas.

Mientras la lógica clásica define el pertenecer al conjunto o no, la lógica difusa indicael grado de pertenencia de un elemento a ese conjunto, inclusive pertenencia con gradocero.

También existen la lógica modal, lógica temporal6, lógica de creencias, lógica derestricciones, lógica paraconsistente, ...

Además de la lógica y del cálculo, la matemática ha dado grandes contribuciones a laIA. La teoría de probabilidad es una de ellas. Fue el italiano Gerolamo Cardano (1501-1576) quien concibiera primero la noción de probabilidad como posible resultado delos juegos de apuesta. Pierre Fermat (1601-1665), Blas Pascal (1623-1662), JamesBernoulli (1654-1705), Pierre Laplace (1749-1827) y otros más hicieron avanzar estateoría e introdujeron métodos estadísticos. En la teoría de decisión, propuesta por JohnVon Newman y Oskar Morgenstern (1944), se combina la teoría de la probabilidadcon la teoría de la utilidad; la teoría de decisiones constituye la base teórica de muchastécnicas de IA.

Si deseamos que un computador actúe inteligentemente, debemos ayudarlo. Hay quedecirle qué conocimiento tiene y cómo debe trabajarlo: manipularlo, almacenarlo, etc.No necesariamente con sólo procesos algorítmicos, también pueden ser declarativos ofuncionales.

Existen diferentes tipos de conocimiento, sin entrar en puntos filosóficos (o

6 El anexo C indica unas carácterísticas de la lógica temporal.



especialmente epistemología7), hay dos principales: hechos y procedimientos derazonamiento. Hechos, son proposiciones o predicados acerca de los objetos delmundo, y procedimientos de razonamiento, son maneras de cómo se encadenan loshechos. La lógica, utilizando diferentes simbologías manipulan el conocimiento segúnnormas y procedimientos preestablecidos que conducen a la solución de problemas enun sistema por medio de modelos que las ciencias proponen.

{PRIVADO }4.1. Lógica de predicados

La lógica proposicional permite representar propiedades elementales del dominio.Construcciones simples del lenguaje. Pero, es insuficiente para representar losprocesos del lenguaje que son utilizados efectivamente en la computación, linguistica,matemática,... o para formalizar fragmentos significativos del razonamiento, porejemplo: ciertos estudiantes asisten a todos los cursos; ningún estudiante asiste a uncurso no interesante.

Lo que le falta a la lógica proposicional, es la posibilidad de distinguir un hechoelemental bajo la forma de un objeto que posee un atributo; una relación entre variosobjetos.

Los patrones o expresiones de la lógica proposicional se construyen a partir de unalfabeto que consta de los siguientes símbolos:1. Conectivos lógicos: ¬, ∧, ∨, →, ↔.2. Los paréntesis: ), (3. Un conjunto P = {p, q, r, ...} de variables proposicionales.

El lenguaje L(P) de expresiones de la lógica proposicional puede definirseinductivamente a partir de las siguientes reglas:1. Cada variable proposicional de P es una expresión (atómo - atómica).2. Si X es una expresión, entonces la negación ¬X también es una expresión.3. Si X y Y son expresiones, entonces también lo son:

Conjunción (X, Y): X∧YDisyunción (X, Y): X∨YImplicación (X, Y): X→YEquivalencia (X, Y): X↔Y

Por ejemplo, si P = {enchufado, fusibleQuemado, funciona}, entonces las siguientesexpresiones, entre otras, pertenecen a L(P):

7 Del griego: episteme, "conocimiento"; logos, "teoría", rama de la filosofía que trata de los problemasque rodean la teoría del conocimiento. La epistemología se ocupa de la definición del saber y de losconceptos relacionados, de las fuentes, los criterios, los tipos de conocimiento posible y el grado con elque cada uno resulta válido; así como la relación exacta entre el que conoce y el objeto conocido.



(¬enchufado ∨ fusibleQuemado) → ¬funciona(enchufado ∧ ¬funciona) → fusibleQuemado

Los paréntesis pueden omitirse según la precedencia habitual de los conectivoslógicos.

La semántica8 del lenguaje proposicional depende i) de la interpretación de losconectivos lógicos y, ii) de los valores de verdad asignados a las variablesproposicionales, distintos según la situación reflejada.

Dado un lenguaje proposicional L(P), se define su semántica por medio de unavaluación que asigna a las variables proposicionales en P un valor: verdadero (1) ofalso (0).

Una valuación es una función s: de P en {0, 1}:

Por ejemplo, si P = {p, q, r}, entonces son valuaciones, entre otras:s1: p=1, q=0, r=1s2: p=0, q=1, r=1

Si P tiene n variables proposicionales, entonces a priori hay 2n valuaciones posibles,aunque no todas tengan sentido en el universo modelado.

Valuación de expresiones compuestas. Para obtener el valor de verdad deexpresiones compuestas, se extiende la función de valuación definiéndolainductivamente sobre L(P). Esta definición precisa formalmente el significado de losconectivos lógicos. Dado un lenguaje proposicional L(P) y una asignación s: P en {0,1}, se define una función extendida.

Dada una expresión arbitraria X de L(P), el valor de verdad s(X) es:1. Si X es una expresión perteneciente a la expresión P, entonces s(X) es el valor deverdad asignado inicialmente a dicha variable.2. Pasos inductivos:

Si X es ¬Y, entonces s(X) = 1 - s(Y).Si X es (Y∧Z), entonces s(X) = min{s(Y), s(Z)}.Si X es (Y∨Z), entonces s(X) = max{s(Y), s(Z)}.Si X es (Y⇒Z), entonces s(X) = 0 si s(Y) = 1 y s(Z) = 0, 1 en caso contrario.Si X es (Y⇔Z), entonces s(X) = 1 si s(Y) = s(Z), 0 en caso contrario.

8 En términos generales, la semántica atribuye significado a las expresiones del lenguaje simbólicoconsiderado. En el caso de un lenguaje de programación como C, la semántica consiste en describir elefecto que produce el programa sobre las estructuras de datos. Para el lenguaje de representación, lo queinteresa es capturar una descripción del universo a modelar. La lógica permite hacer esto asignandovalores de verdad a cada expresión del lenguaje.



Esto puede verse más claramente definiendo la semántica de los conectivos lógicosmediante tablas de verdad.

Tablas de verdad. Dado que la lógica proposicional opera sólo con dos valores deverdad, para cualquier expresión existe un número finito de valuaciones posibles detabular. La tabla de verdad de una expresión con n variables proposicionales tiene 2n

filas.{PRIVADO}X

Y ¬X (X∧Y) (X∨Y) (X⇒Y) (X⇔Y)

0 0 1 0 0 1 10 1 1 0 1 1 01 0 0 0 1 0 01 1 0 1 1 1 1

Equivalencia lógica. Dos fórmulas de L(P) son lógicamente equivalentes siexactamente las mismas valuaciones las hacen verdaderas, lo que puede verificarseutilizando una tabla de verdad. Por ejemplo, para P={p, q}:

{PRIVADO }Tabla 4.1 Tablas de verdad.

p q ~p p & q p v q p → q

VVFF

VFVF

FFVV

VFFF

VVVF

VFVV

Mirando la tabla es claro que (p⇒q) y (¬p∨q) son lógicamente equivalentes, ya quesus valores de verdad coinciden para cada una de las cuatro valuaciones posibles.

Validez de expresiones lógicas. La validez de una expresión se verificaexhaustivamente mediante las tablas de verdad. Una expresión X de L(P) es válidasiempre y cuando sea siempre verdadera, es decir, si y sólo si, para toda valuación s: Pen {0, 1} se cumple s(X) = 1. Estas expresiones, que son verdaderasindependientemente del universo modelado, se llaman tautologías.

Un ejemplo trivial de tautología es cualquier expresión de la forma (X∨¬X). Laimportancia de las tautologías desde el punto de vista computacional radica en elhecho que pueden estudiarse y aplicar en forma general. Pertenecen al sistema lógico yno al dominio de aplicación.

Satisfacibilidad de expresiones lógicas. Una expresión X de L(P) es satisfacible



siempre y cuando existe por lo menos una valuación s: P en {0, 1} que cumple s(X) =1. Esta noción es menos fuerte que la noción de validez (si una expresión es válidatambién es satisfacible, pero la recíproca no es verdadera).

Por ejemplo, la expresión (¬enchufado ∨ fusibleQuemado → ¬funciona) essatisfacible pero no válida. Esto se ve en una tabla de verdad verificando que lacolumna de valores de la expresión contiene valores verdaderos y falsos:Sea p1=enchufado, q1=fusiblequemado, r1=funciona

{PRIVADO}p1

q1 r1 (¬p1∨q1) →¬r1)

0 0 0 10 0 1 00 1 0 10 1 1 01 0 0 11 0 1 11 1 0 11 1 1 0

Si la expresión considerada corresponde a una regla general del universo modelado, lanoción de satisfacibilidad permite acotar los mundos posibles descartando lasvaluaciones que entregan valor falso. Por ejemplo, de la tabla, se puede afirmar que noes posible un mundo en que un equipo funcione sin estar enchufado.

Insatisfacibilidad de expresiones lógicas. Una expresión X de L(P) es insatisfacible sino es satisfacible, es decir, siempre y cuando no exista ninguna valuación s: P {0, 1}que la hace verdadera. Por ejemplo, cualquier expresión de la forma (X∧¬X) esinsatisfacible. También se dice que es una contradicción. Las nociones de validez,satisfacibilidad e insatisfacibilidad están relacionadas por las siguientes propiedades:

1. X es satisfacible, si y sólo si, X¬ no es válida2. X es insatisfacible, si y sólo si, ¬X es válida3. X es válida, si y sólo si, ¬X es insatisfacible

Las nociones de validez e insatisfacibilidad también son extensibles a conjuntos deexpresiones lógicas.

Consecuencia lógica. Una expresión es consecuencia lógica de un conjunto deexpresiones siempre y cuando, cada vez que el conjunto de expresiones es verdadero,necesariamente la expresión también es verdadera. Esta relación, entre un conjunto deexpresiones y una expresión aislada X, se escribe así: a X (puede interpretarse como a



"implica" X). La noción de consecuencia lógica se define en función de la noción desatisfacibilidad y se denota con el mismo símbolo.

Los sistemas inteligentes (SI) usan lenguajes y sublenguajes. Especialmente utilizan lalógica de predicados para representar hechos del conocimiento en un lenguajeexpresivo, conciso, inequívoco, independiente del contexto y eficiente.9

Esto requiere simbolizar proposiciones del lenguaje ordinario en estructuras a fin dehacer explícitas sus conexiones lógicas. Proposiciones como: todo hombre es mortal,todo metal brilla, todo felino tiene garras, etc., fueron representadas por Aristóteles enla expresión TODO P ES Q. Y proposiciones como: algunos hombres son buenos,existen animales mansos, los árboles son seres vivos, etc., en la expresión EXISTE PES Q.

La lógica de predicados estudia la estructura lógica de las proposiciones a través deformar conexiones sujeto-acción-complemento para representar hechos u objetos delmundo.

El desarrollo de la lógica de predicados se basa en unidades representativas deinformación llamadas átomos, los cuales representan una oración declarativa quepuede ser verdadera o falsa pero no ambas. A partir de los átomos se construyennuevas fórmulas. Sin embargo, existe conocimiento que no puede ser tratado mediantedeterminadas estructuras atómicas (EA), pero son muy correctas en el lenguaje natural(LN), por ejemplo:

Sólo los tontos se dejan engañar por los vendedoresAlberto se deja engañar por JuanAlberto es tonto

luego,Juan es un vendedor

Estas proposiciones podrían tener la siguiente representación formal:

p(x) → t(y), q(z), r(x) => ¬ s(y)

Se observa que ninguna proposición puede escribirse mediante partes de las mismasdotadas de significado propio, se unen por conectivas y la relación entre premisas yconclusión hace que la deducción correcta no pueda detectarse con este nivel derepresentación. Esto se debe a que la relación entre las proposiciones está en la propiaestructura interna, en efecto se afirma en ellas propiedades o relaciones de distintas

9 El poder de expresión de la lógica de predicados es mucho mayor que el de la lógica proposicional:primero es necesario construir términos que representan los objetos y las fórmulas atómicas quecorresponden a las relaciones entre objetos.



personas o conjuntos de personas (las propiedades son: “...es tonto..”, “...se dejaengañar por...”, “..es vendedor ambulante..”, los objetos de la atribución de estaspropiedades y relaciones son colectivos definidos a su vez por propiedades yrelaciones en la proposición: Alberto y Juan), por ello, para tratar este tipo de EA espreciso desarrollar una teoría que tome como base sus componentes, es decir: ¿Qué seafirma?, ¿de quién se afirma?, y ¿cuánto se afirma?

Un sistema lógico se define desde dos puntos de vista diferentes que son equivalentes:* Punto de vista semántico, y* Punto de vista sintáctico.

Las dos aproximaciones se fundamentan en la definición de un lenguaje. Un lenguajees una colección de símbolos y de reglas para la construcción de fórmulas bienformadas.

La primera componente se define como el predicado, la segunda como el objeto osujeto y la tercera, cuarta, quinta, etc., componente: valor que se ha de tomar.

Así en las frases:

Juan es negro,Objeto: Juan; predicado: es negronegro(juan)

César está en clase, entre Pedro y ManuelaPredicado: está en clase entre; objeto: César; valores: Pedro, Manuelaen_clase_entre(carlos, césar, maría)

La película está de primeraPredicado: está de primera; objeto: la películade_primera(película)

Juan es un estudiante adelantadoPredicado: es un estudiante; objeto: Juan; valor: adelantadoestudiante(juan, adelantado)

El atributo, la relación, la asignación de la proposición se denomina "predicado" y losobjetos y/o valores "argumentos".

Otros ejemplos son: (m(x), q(x), r(y,3), s(t(x), z, 3115)ciudad(Bogotá, Cali, Medellín)nombre_predicado_largo(argumento_largo, argumento_corto, calificativo)

Una vez se definan los componentes de la proposición, se plantea su representaciónformal con base a términos. Para la simbolización de los términos se toma como basede referencia un dominio genérico, no vacío. Los términos se representan porconstantes o variables cuyos valores posibles son elementos del dominio. La intención



de un predicado es relacionar cosas en espacio y tiempo por familiaridad, asignación osimilitud. Un objeto puede estar al norte, sur, este u oeste de otro objeto, o estar alfrente, atrás, arriba, abajo, a la izquierda, a la derecha. Similarmente, un evento en eltiempo puede estar antes, después, simultáneamente con otro evento.

Variable. Indica un objeto cualquiera que pertenece a una clase determinada; sea x oy, son términos que permiten identificar diferentes entidades o individuos u objetos deuna clase.

Constante. Indica un objeto especial, es un térmiono simple de un dominio; porejemplo, Bogotá, corto, ciudad, 3.1416, 48, Gaviria.

Función. Permite representar transformaciones del dominio; por ejemplo, t(x),marido(x), madre(x)

Por ejemplo, la función padre puede usarse para denotar una aplicación entre unindividuo y el hijo. Para expresar la proposición "La madre y el padre de John soncasados" se haría:

casados(padre(john),madre(john))

Se define el alfabeto, constituido por los siguientes conjuntos de caracteres:

1. Símbolos para constantes = {a,b,c,...a1,a2,a3,...}

2. Símbolos para variables = {x,y,z,...x1,x2,x3,...}

3. Símbolos de función = {f,g,h,...f1,f2,f3,... o cadenas de caracteres enminúscula como: padre, madre, mayor, etc.}

4. Símbolos de predicado = {P,Q,R,....P1,P2,P3,...}

5. Símbolos de conectivas = {¬, &, v, ⇒, ⇔}

6. Símbolos de cuantificación = { ∀, ∃}

7. Paréntesis = { ( , ) }

8. Símbolos especiales: Τ fórmula inválida, ⊥ fórmula válida, => se deduce, Vverdadero, F falso.

Los objetos o términos son definidos recursivamente como sigue:

1. Las constantes son términos,2. Las variables son términos,



3. Si f es un símbolo de función de aridad10 n y t1,t2,...,tn son términos, entoncesf(t1,t2,...,tn) es un término

4. Todos los términos son obtenidos por la aplicación de las reglas 1,2 y 3.

Definición. Un predicado es una correspondencia entre una lista de constantes ovariables del alfabeto y el conjunto de valores de verdad {V, F}

Definición. Si P(p1,p2,...,pn) es un símbolo de predicado de aridad n y t1,t2,...,tn sontérminos, entonces P(t1,t2,...,tn) es un átomo. Ninguna otra expresión puede ser átomo.

De lo anterior, el símbolo de predicado P(p1,p2,...,pn) no puede ser considerado unátomo hasta que no se reemplace cada uno de sus argumentos p1,p2,...,pn por untérmino.

Esto puede hacerse de dos formas:

1. Por sustitución

En este caso se asigna a cada símbolo argumento del predicado un símbolo términoque puede ser constante, variable o función. En el símbolo de predicado P(p1,p2,...,pn)una sustitución puede ser:

P(x1,x2,a3,a4,...,f(x1))2. Por cuantificación

Algunas veces una EA, digamos P(x), toma valor "V" sin interesar que asignación se leda a la variable x, o puede tomar valor "V" para unas pocas asignaciones a la variablex.

En este caso se asigna a cada argumento símbolo del predicado un conjunto deelementos del dominio. Los cuantificadores indican cuantas particularizacionesnecesitan tomar las variables para que la proposición tenga un valor de verdad"VERDADERO". Hay dos posibilidades:

a. Cuantificación universal

Uno o varios argumentos símbolo del predicado se cuantifican universalmente,colocando el símbolo de cuantificador universal, ∀, junto con la variable, ejemplo:

∀x2 …∀xn P(a1,x2,x3,...,Xn) o, ∀x2xn P(a1,x2,x3,...,Xn)

b. Cuantificación existencial

10 Según el número de términos que tienen los predicados se define la aridad, un término da aridad uno,dos términos es aridad dos o diádicos, tres de aridad tres o triádicos, etc.



Uno o varios argumentos símbolo del predicado se cuantifican existencialmente,colocando el símbolo de cuantificador existencial, ∃, junto con la variable, ejemplo:

∃x2 …∃xn P(a1,x2,f(x3),...,Xn) o, ∃x2... xn P(a1,x2,f(x3),...,Xn)

La fórmula con cuantificador universal (∀x) al frente, (∀x)p(x) toma el valor "V" paratoda asignación de x en el dominio. La fórmula con cuantificador existencial (∃x) alfrente (∃x)p(x) toma el valor "V" para al menos una asignación de x en el dominio11.

Ejemplos:(∃x) { animal(x) --> color(x,gris) }(∀x) { escribió(x,programas_ajedrez) }

La cuantificación existencial y universal puede mezclarse en la misma expresión. Eneste caso, el orden con el que se introducen las variables cuantificadas puede afectar elsignificado.

P.e., ∀x ∃y (empleado(x) -->supervisa(y,x) ). Podría leerse como: todo empleado tienesupervisor.

Mientras que si se invierte el orden, ∃y ∀x (empleado(x) --> supervisa(y,x)). Se leería:hay una persona que supervisa a todos.

Otros ejemplos son:

a. Para todo número x existe al menos otro y tal que x<y.∀x ∃y menor(x,y)

b. Existe al menos un número y tal que para todo x, x < y.∃y ∀x menor(x,y)

Debe definirse el alcance de un cuantificador que está en una fórmula. Por ejemplo: enla fórmula ∀x ∃y menor(f(x),y), el alcance de los cuantificadores ∀x y ∃y esmenor(f(x),y). En la fórmula ∀x P(x) ⇒ Q(x) el alcance es solo P(x).

Como se ha dicho, al computador debe ayudársele para que actúe inteligentemente.Por ejemplo, al desear decir o comunicar algo acerca del Presidente Gaviria, se escribe:presidente(gaviria), que significaría "Gaviria es Presidente", o en otras palabras queGaviria es un ejemplo del tipo "Presidente". El predicado es "presidente", y elargumento "gaviria".

También debe informarsele para dos o más objetos del predicado presidente, así: 11 El radio de acción del cuantificador es justamente esa parte del dominio en el cual las proposicionesson verdaderas.



presidente(uribe)presidente(chavez)presidente(castro)

Similarmente se dan otros predicados como:barco(arc_gloria)barco(almirante_padilla)universidad(fundación_universitaria_autónoma_de_colombia)universidad(universidad_de_los_andes)universidad(universidad_distrital)universidad(manuela_beltrán)día_de_la_semana(lunes)día_de_la_semana(domingo)

Un objeto puede tener asociado más de un tipo:presidente(uribe)antioqueño(uribe)liberalismo(uribe)

Y los tipos pueden contener subtipos:militar(arc_gloria),barco(militar)

loco(julio),persona(loco)

Todos estos ejemplos son tipos de predicados, y ellos tienen un sólo argumento. Pararepresentar propiedades de objetos como expresiones de predicados, es necesarioespecificar la característica o propiedad en el nombre del predicado, el primerargumento es el nombre del objeto y el segundo es el valor de la propiedad, porejemplo:

barco(arc_gloria)color(arc_gloria, gris)tamaño(arc_gloria, grande)

Color y tamaño son nombres de las propiedades para los cuales gris y grande sonvalores. Mostrar la relación entre gris y Arc_gloria, y entre grande y Arc_gloria, es unaventaja.

Al clasificar, se ordenan los objetos que van a ser manipulados. En realidad laclasificación es la construcción de una relación "uno a uno" entre los símbolos y losobjetos o ideas externas.



La relación de objetos por predicados es importante en IA porque el razonamientohumano se basa en la relación.

Sean los hechos:parte_de(arc_gloria, armada_colombiana)parte_de(armada_colombiana, gobierno_colombiano)parte_de(escuela_naval, armada_colombiana)parte_de(sistema_propulsión, barco)

En otras palabras, el arc_gloria es parte de la armada_colombiana, laarmada_colombiana es parte del gobierno_colombiano, la escuela_naval es parte de laarmada_colombiana, el sistema_propulsión es parte del barco.

Un predicado de relación "dueño" indica que "x es dueño".dueño(julián, fido)dueño(julián, carro_negro)

Definición. Una variable es acotada en una fórmula, sii, una ocurrencia de la variableestá dentro del alcance del cuantificador.

Definición. Una variable es libre en una fórmula, si está libre del alcance de uncuantificador.

En la fórmula, ∀x P(z,x) , la variable x es acotada, z es libre. También puede hallarseuna variable libre y acotada a la vez; ejemplo ∀x Q(x,t) → ∃t R(x,t)12.

Con el fin de decidir sobre la aceptabilidad de un determinado argumento, es necesariohacer alguna prueba. La forma de realizar esto, dentro de la lógica, es comparar eltexto bajo estudio con una serie de patrones abstractos de argumentos, y ver si algunose ajusta con el planteado. Tales patrones se denominan "modelos" y están constituidospor secuencias abstractas de hechos y por reglas que previamente se han demostradoque son válidas13 de una forma matemática (o formal).

Por ejemplo, sea la regla:"SI Mario estudia sistemasIMPLICA Mario es un masoquista "

Asumiendo el hecho "Mario estudia sistemas" puede parecer natural concluir que:"Mario es masoquista", formalmente se está aplicando el modelo lógico

SI P IMPLICA Q, P POR TANTO Q

12 Es importante colocar los paréntesis para evitar interpretaciones contradictorias. 13 Cuando una fórmula tiene cuantificadores, no todas las veces es posible verificar la validez oconsistencia. Hay necesidad de evaluarla bajo todas las posibles interpretaciones.



P → Q, P ⇒ Q

Habiendo encontrado el modelo correspondiente, puede afirmarse que el predicadotiene estructura lógica aceptable.

El hecho que el contenido no tenga sentido en el mundo real, no produce ningúnelemento para la validez del "modelo". P.e., el siguiente argumento es valido, aunquela suposición pueda ser quizás dudosa

SI Fxx es políticoIMPLICA Fxx está muerto.

Federico es político, POR TANTO, Federico está muerto.

El sencillo modelo de argumento utilizado en los ejemplos anteriores, es fundamentalen lógica, y se le ha dado nombre especial en Latín: modus ponendo ponens (abreviadomodus ponens).

A menudo, de una proposición, el predicado es identificado con el verbo, y lostérminos son identificados con el sujeto y complemento. Usualmente, puede tenersevarias formas para representar una proposición. Por ejemplo, puede representarse laproposición "la manzana es roja" por:

roja(manzana) ,color(manzana,rojo) , Ovalor(color,manzana,rojo).

El diseño de una representación selecciona el alfabeto y los términos a emplear.

A cada predicado, se le asigna una relación correspondiente en el dominio; a cadaconstante una entidad, y a cada transformación una función. Esas asignaciones definenla semántica del lenguaje del cálculo de predicados. Una vez una interpretación parauna fórmula se define, se dice que la fórmula tiene valor V (verdadero), justamente,cuando la correspondiente instrucción en el dominio es verdadera, y tendrá valor F(falso) en caso contrario.14

Así,escribió(garcía_márquez, cien_años_de_soledad); tiene valor V;escribió(garcía_márquez,la_eneida); tiene valor F.

Definición. Una fórmula bien formada15 (FBF) se define como:

14 En lógica de predicados las estructuras denominadas proposiciones siempre toman el valor"VERDAD" o el valor "FALSO". Las proposiciones son: estudia(federico,sistemas); masoquista(federico);político(martha); muerta(martha). 15 En inglés Well Formed Formulas -WFF's-



1. Todo átomo es una fórmula.

2. Si P(p1,p2,...,pn) es un predicado, entonces P(t1,t2,...,tn) es fórmula siendot1,t2,...,tn términos.

3. Si G(a) es una fórmula y x es una variable del dominio, ∀xG(x) y ∃xG(x) sonfórmulas.

4. Si H(a) y G(b) son fórmulas, también lo son ¬H(x), H(x)^G(x), H(x)vG(x),G(x)→H(x), H(x)⇔G(x).

5. Las fórmulas son generadas solamente por la aplicación de un número finitode veces de las reglas 1,2,3 y 4.

Las siguientes expresiones son fbf:∃x { ∀y [P(x,y) & Q(y,x)] → R(x) }~ ∀y { ∃x [P(x) v R(y)] }~ P[ A, s(a,b,c) ]{ ~ [P(w) →P(u) ] } → P(u)

En estas expresiones se usan llaves, paréntesis y corchetes como delimitadores paraagrupar componentes de las fbf. Se usan delimitadores para eliminar cualquierambigüedad y para mejorar su compresión.

Algunos ejemplos de expresiones que no son fbf:{PRIVADO }~ f(B)f( P(A))Q{ g(A), [P(B) → Q(C)]}& ~ ∀x v R(x)

Se niega un predicado no una función.Un predicado no puede ser parte de una función.La implicación no puede ser parte de un argumento.La conjunción debe unir dos predicados.

Las fórmulas quiere_a(X,Y) y, hermano(X,Y) son estructuras que forman predicadosbásicos.

Las fórmulas atómicas, como escribió(x,y), son construcciones elementales. Secombinan fórmulas atómicas para formar fbf más complejas usando conectivas, talcomo: " & " (y), " v " (o), y "→" (implica).

La conectiva "&" (conjunción o conjuntor) tiene un obvio uso representando oracionescompuestas,

gusta(john,maría) & gusta(john,susana),vive(patricia,suba) & color(casa,azul).

El símbolo "v" se usa para representar la disjunción o disjuntor.



Por ejemplo, "María juega béisbol o practica ciclismo" puede representarse por:juega(maría,béisbol) v practica(maría,ciclismo).

El valor verdad de una conjunción y una disyunción está determinado por los valoresde verdad de las componentes. Una conjunción tiene valor "V" si cada una de lascomponentes de la conjuntiva tiene valor "V", en otro caso el valor es "F". Unadisyunción tiene valor "V" si al menos una de las disyuntivas tiene valor "V", en otrocaso toma valor "F".

P.e., la oración "si María juega en el equipo, se gana el partido" se representa por:juega(maría,equipo) --> gana(equipo,partido).

Una fórmula construida conectando dos fórmulas con un "→" se llama unaimplicación. El lado izquierdo de una implicación se llama antecedente, y el ladoderecho se llama consecuente. Una implicación tiene valor "F" si el antecedente tienevalor "V" y el consecuente tiene valor "F", en otros casos el valor es "V".

El símbolo "~" (negación o negador) se emplea para negar el valor de una fórmula;esto es, se cambia el valor de una fbf de V a F o viceversa. P.e., la oración "GarcíaMárquez no escribe programas de Ajedrez" se representa como:

~ escribe(garcía_márquez, programas_ajedrez)..

Ejemplo: analizar si la expresión ∃x(P(x) → ∀y Q(y,w)) es fbf.

Q(y,w) es fórmula por la regla 2 ya que esta constituida por la letra de predicado, Q,seguida por las variables de términos y y w.

∀y Q(y,w) es fórmula de acuerdo a la regla 3.P(x) es fórmula de acuerdo a la regla 2, ∃x P(x) lo es por la regla 3∃x P(x) → ∀y Q(y,w) es fórmula por la regla 4, ya que P(x) y ∀y Q(y,w) sonfórmulas.

∃x P(x) → ∀y Q(y,w) tiene las variables acotadas x y y, w es libre.

El proceso descrito anteriormente permite decidir en un número finito de pasos si unafórmula es o no correcta de acuerdo a las reglas de la gramática del 1 al 5 y losconjuntos de símbolos definidos para el alfabeto.

Cuando se trate de fórmulas con varios cuantificadores se realiza en el orden de mayora menor proximidad a la fórmula cuantificada.

Así, la fórmula:∀x ∃y ∀z ∃w P(z,x,y,w)



debe entenderse en la forma ∀x (∃y (∀z (∃w (P(z,x,y,w) ) ) ) ).

{PRIVADO }4.1.1. Formalización

No puede definirse un procedimiento mecánico que permita obtener la fórmula querepresenta una frase. En algunos casos debe modificarse la redacción de la frase, sinalterar el significado hasta obtener una expresión lingüística que contenga elementosde fácil traslación a expresiones lógicas con conectivas y cuantificadores.

A continuación se dan ejemplos de cómo formalizar frases en lógica de predicados.

Frases simples. Son constituidas por átomos con un único predicado que puede estarcuantificado o no.

Existe un número que es primo.Dominio: como la propiedad es "... es primo", sólo está definida para elconjunto de los números enteros positivos, por tanto se deja éste comodominio.Símbolo constante: no haySímbolo variable: sea x para denotar número entero.Símbolo función: no haySímbolo predicado: P(x) ↔ x es primoFórmulas: ∃x P(x)

Todos son negros.Dominio: Conjunto de personas de... (aunque puede cambiar tomando otrocontexto).Constantes: no hayVariables: x para denotar una persona cualquiera.Función: no hayPredicados: N(x) ↔ x es negroFórmulas: ∀x N(x)

Juan es amigo de todos. Algunos son amigos de Juan.Dominio: Conjunto de personas de.Constantes: J ↔ JuanVariables: x para denotar una persona cualquiera.Función: no hayPredicados: A(x,y) ↔ x es amigo de yFórmulas: ∀x A(j,x); ∃x A(x,j)

Frases compuestas. Están constituidas por expresiones cuantificadas en las queintervienen conectivas y cuantificadores. Las frases compuestas tienen gran variedad



de estructuras.

Algunos Bogotanos son ricos.

Sin alterar el contenido de información, la frase puede redactarse:

¿Existen personas que son Bogotanos y ricos a la vez?Dominio: Conjunto de personas.Constantes: no hayVariables: x para denotar una persona cualquiera.Función: no hayPredicados: B(x) ↔ x es Bogotano; R(x) ↔ x es ricoFórmulas: ∃x (B(x) & R(x)).

Todas las águilas vuelan alto. Cualquier ave, si el ave es águila, entonces vuela alto.

Dominio: Conjunto de águilas (¿Conjunto de todas las aves?).Constantes: no hayVariables: x para denotar un águila cualquiera.Función: no hayPredicados: V(x) ↔ x vuela alto; A(x) ↔ x es águilaFórmulas: ∀x (A(x) & V(x)); ∀x (A(x) → V(x))

En toda pareja de vecinos existe algún envidioso.

Se transforma la frase en la siguiente:

¿Cualesquiera que sean x y w, si x y w son vecinos, entonces x o w o ambos sonenvidiosos?

Dominio: Conjunto de personas.Constantes: no hayVariables: x, w para denotar una persona cualquiera.Función: no hayPredicados: V(x,w) ↔ x es vecino de w; E(x) ↔ x es envidiosoFórmulas: ∀x ∀w (V(x,w) → E(x) ∨ E(w)).

Algunos estudiantes de sistemas tienen amigos aficionados al fútbol.Dominio: Conjunto de personas.Constantes: no hayVariables: x, w para denotar una persona cualquiera.Función: no hayPredicados: S(x) ↔ x estudia sistemas; F(x) ↔ x es aficionado al fútbol;

A(x,w) ↔ x es amigo de wFórmulas: ∃x ∃w (S(x) → A(x,w) & F(w)).



Sólo los CUAN's admiran a los CUAN'sDominio: Conjunto de personas.Constantes: no hayVariables: x, w para denotar una persona cualquiera.Función: no hayPredicados: S(x) ↔ x es CUAN; AD(x,w) ↔ x admira a wFórmulas: ∃x ∀w (AD(x,w) & S(w) → S(x)).

Todos los CUAN's admiran sólo a los CUAN'sDominio: Conjunto de personas.Constantes: no hayVariables: x, w para denotar una persona cualquiera.Función: no hayPredicados: S(x) ↔ x es CUAN; AD(x,w) ↔ x admira a wFórmulas: ∀x (S(x) → ∀w (AD(x,w) → S(w)).

Sólo los tontos se dejan engañar por los vendedores

¿Para todo w y z del dominio, si w se deja engañar por z y z es vendedor, entonces wes tonto?

Dominio: Conjunto de personas.Constantes: no hayVariables: x, w para denotar una persona cualquiera.Función: no hayPredicados: V(x) ↔ x es vendedor; E(x,w) ↔ x se deja engañar por w

T(x) ↔ x es tontoFórmulas: ∀x,w (E(x,w) & V(w) → T(x)).

Lo más necesario, es extenderse a frases más complejas

Juan es antioqueño, Sandra es del valle, todos los antioqueños son trabajadores, todaslas vallunas son bellas, Narda es hermosa y es antioqueña, luego hay antioqueñasbellas y trabajadoras.

Dominio: Conjunto de personasConstantes: Juan, Sandra, NardaVariables: x,y,z para denotar cualquier personaFunción: no hayPredicados: A(x) ↔ x es antioqueño; V(x) ↔ x es del valle

B(y) ↔ y es bella; T(y) ↔ y es trabajadorFórmulas: {A(juan), V(sandra),{ ∀z A(z) → T(z)},{ ∀y V(y) →B(y)},

{B(narda) & A(narda)} } →{ ∃x A(x) → B(x) & T(x)}

Los valores de verdad de las fbf se calculan por tablas de verdad. (ver tabla 4.1), y



aplicando fórmulas equivalentes16.

Las reglas básicas de inferencia son dadas en la tabla 4.2.{PRIVADO }Tabla 4.2 Reglas básicas de inferencia.

A → B , A ⇒ BA → B , ~B → ~ AA ⇔ ~ ( ~ A )A , B ⇒ A & BA → B , A → ~ B , ⇒ ~A∀x W(x) , s → W(s)

Modus ponendo ponens, MPPModus tollendo tollens, MTTDoble negación, DNIntroducción, INTReducción al absurdo, RAAEspecialización universal, US

Identidades lógicas. La equivalencia lógica entre expresiones depende sólo de laforma de las expresiones comparadas, y no del conjunto particular de predicadosutilizados. Sin embargo, existen identidades lógicas genéricas como:

R1: ~(~X) ↔ XR2: X v Y ↔ ~Y->X

(~Y v X)&(Y v ~X) ↔ Y<->XLeyes DeMorganR3: ~(X & Y) ↔ ~X v ~Y

~(X v Y) ↔ ~X & ~YLeyes distributivasR4: X & (Y ∨ Z) ↔ (X & Y) ∨ (X & Z)

X ∨ (Y & Z) ↔ (X ∨ Y) & (X ∨ Z)Leyes conmutativasR5: X & Y ↔ Y & X

X ∨ Y ↔ Y ∨ XLeyes asociativasR6: (X & Y) & Z ↔ X & (Y & Z)

(X ∨ Y) ∨ Z ↔ X ∨ (Y ∨ Z)Ley contrapositivaR7 X -> Y ↔ ~Y -> ~X

Las identidades lógicas se utilizan para trasformar expresiones conservando susignificado. Esto es especialmente útil para obtener formas normales más fáciles demanipular. Por ejemplo, toda expresión lógica puede reescribirse utilizando sólo losconectivos ¬ y ∧.

Usando cuantificadores, existen otras equivalencias:

R9: ~ ∃x P(x) ↔ ∀x {~P(x)}~ ∀x P(x) ↔ ∃x {~P(x)}

16 Si dos fbf tienen el mismo valor de verdad pero estas difieren en su LN aunque parecen iguales alobservar la interpretación, entonces se dice que esas fbf son equivalentes.



R10: ∀x P(x) ↔ ∀y P(y)∃x P(x) ↔ ∃y P(y)

Estas dos equivalencias indican que la variable acotada en una expresión cuantificadaes una clase de variable simulada. Puede arbitrariamente reemplazarse por cualquierotro símbolo variable.

R11: ∀x[P(x) & Q(x)] ↔ ∃xP(x) & ∀yQ(y)∃x[P(x) v Q(x)] ↔ ∃xP(x) ∨ ∃yQ(y)

R12: ∀x[P(x) ∨ ¬P(x)] ↔ ΤR13: ∀x[P(x) & ~P(x)]↔ ⊥R14: P(x) & V ↔ P(x)R15: P(x) ∨ V ↔ VR16: P(x) & F ↔ FR17: P(x) ∨ F ↔ P(x)

Otras reglas básicas son:

R19: P(x) v P(x) ↔ P(x)R20: P(x) & P(x) ↔ P(x)R21: ~P(x) & P(x) ↔ F (falso) 17

R22: ~P(x) ∨ P(x) ↔ V (verdadero)R23: {P(x) ∨ Q(x) } & { ~P(x) ∨ Q(x) } ↔ Q(x)

Para mostrar la versatilidad de la lógica de predicados como un lenguaje paraexpresiones de varias acepciones, veamos unos ejemplos más:

Toda ciudad tiene un cartero quien ha sido mordido por todo perro de la ciudad

∀x{ciudad(x) → ∃y{cartero(x,y) & ∀z{[perro(z) & vive(x,z)] → mordido(y,z)}}}

"Para todo conjunto x, hay un conjunto y, tal que la cardinalidad de y es mayor que lacardinalidad de x"

∀x{conjunto(x) → ∃y{mayor[cardinalidad(y),cardinalidad(x)]}}

Todo bloque encima de un bloque o que ha sido ligado a un bloque que se muevetambién se mueve.

∀x ∀y{{bloque(x)&bloque(y)&[encima(x,y)∨ligado(x,y)]&mueve(y)} → mueve(x)}

17 Existen tres principios o postulados, que se refieren a los seres y que se imponen necesariamente porsu evidencia inmediata: a) Todo objeto es idéntico a sí mismo; b) Ningún objeto puede ser, al mismotiempo, P y no P; c) Todo objeto tiene que ser P o no P.



Ejemplo de encadenamiento hacia adelante con predicados:

Sean los hechos H1: hermano(carlos,maría) H2: hermano(maría,alberto) H3: hermano(josé,carlos)

y las reglas R1: ∀x,y hermano(x,y) → quiere_a(y,x)R2: ∀x,y,z hermano(x,y) & quiere_a(z,y) → quiere_a(z,x)

¿Cómo usar estas reglas para ver si puede generarse la inferenciaquiere_a(alberto,josé)?

Se ve que la inferencia no puede hacerse directamente; de R1 + H2 se tiene quiere_a(alberto,maría) (H4)

con H4 + R2 + H1 se tiene quiere_a(alberto,carlos) (H5)

ahora H5 + R2 + H3 se tiene quiere_a(alberto,josé) (H6)

que es lo que se quería hallar.

Las reglas de inferencia, producen fbf derivadas de unas dadas, tales fbf derivadas sellaman teoremas y la secuencia de aplicación de reglas de inferencia en la derivaciónconstituye la demostración del teorema.

{PRIVADO }4.1.2. Válidez

El problema de encontrar un procedimiento general de decisión para verificar lavalidez (o inconsistencia) de todas las fórmulas de la lógica de Primer Orden es muyantiguo. Los primeros trabajos provienen de Leibnitz (1646-1716). Peano revisó lostrabajos de Leibnitz a finales del siglo XIX, pero sin obtener ninguna conclusiónimportante; y no hasta 1920, cuando la escuela de Hilbert continuó trabajando en ello,encuentra resultados importantes. Un poco después, en 1936, Church y Turing, cadauno por su lado, demostraron que es imposible encontrar un procedimiento general dedecisión. A pesar de esto existen procedimientos de prueba que pueden verificar si unafórmula es válida (cuando efectivamente lo es), aunque no se pueda conocerefectivamente cuando una fórmula es inválida.

Una interpretación Þ de una fórmula G sobre un dominio D no vacío, consiste de unaasignación de valores a cada una de las constantes, símbolos de función y predicadosque ocurren en la fórmula.



Una fórmula G es consistente o satisfactible, sii, existe una interpretación Þ, tal que elvalor de verdad de G bajo Þ es V.

Una fbf P es modelo lógico de un conjunto de fbf S, si toda interpretación satisfaciendoS también satisface P. Así, es fácil ver que la fórmula

∀x∀y[(P(x) v P(y) ] es modelo lógico del conjunto{∀x∀y[P(x) ∨ P(y)] , ∀z[R(z) ∨ Q(A)]}

También, la fbf P(A) es modelo lógico de ∀xP(x), al igual que ∀xQ(x) es modelológico del conjunto {∀x[~P(x) ∨ Q(x)] , ∀xP(x) }.

Si una fbf toma el valor V para toda posible interpretación, se dice es válida (lo básicode la validez de fbf son usualmente llamadas tautologías).

Utilizando tablas de verdad, la fbf P(A) → [P(A) v P(B) ] tiene el valor V para todainterpretación, por tanto, es válida. El método de la tabla de verdad puede usarsesiempre para determinar la validez de cualquier fbf que no tenga variables acotadas.Cuando se tienen cuantificadores, no siempre puede darse la validez de una fbf. Se hademostrado que es imposible encontrar un método general para decidir la validez deuna expresión cuantificada, por esta razón, en la LP se dice que es indecisa. Sinembargo, la validez de ciertas fórmulas conteniendo cuantificadores puede decidirse,cuando se hable de subclases definidas de la LP.

Hay una importante conección entre el concepto de una fbf modelo lógico, de unconjunto de fbf, y el concepto de una fbf teorema derivado de un conjunto de fbf poraplicación de reglas de inferencia.

Sea que se ha dado un sistema de reglas de inferencia. Se dice que un conjunto dereglas de inferencia son reglas sólidas si cualquier teorema derivado de cualquierconjunto de fbf es modelo lógico de ese conjunto de fbf.

Se dice que el sistema de reglas de inferencia es completo si toda fbf que es modelológico de cualquier conjunto es también teorema derivado de ese conjunto.

Unificación

En la prueba de teoremas se involucran fórmulas cuantificadas, es a menudo necesariohacer concordar ciertas subexpresiones. Por ejemplo, para aplicar la combinación demodus ponens y especialización para producir W2(A) a partir de fbf ∀x[W1(x) →W2(x)] y W1(A), es necesario encontrar la sustitución "A por x" que hace W1(A) yW1(x) idénticas. Encontrar sustituciones de términos por variables para hacerexpresiones idénticas es un proceso extremadamente importante en LP es llamado



unificación.

Un caso de sustitución de una expresión es obtenida al sustituir constantes porvariables, o una variable por otra, o una variable por una función en esa expresión. Así,ejemplos de P[x,f(y),B] son:

P[ z,f(w),B ]P[ x,f(C),B ]P[g(z),f(A),B]P[ C,f(A),B]

El primer caso es llamado variante alfabética por que solamente se ha sustituidovariables por variables.

El último caso es llamado básico, puesto que ninguno de los términos en el literalcontiene variables.

Se representa una sustitución por un conjunto de pares ordenados s = {t1/v1, t2/v2, ...,tn/vn}. El par ti/vi significa que el término ti sustituye a la variable vi en todas partes; noexisten dos parejas ti/vi, tj/vj tal que vi=vj, i><j.

Ninguna variable puede ser sustituida por un término conteniendo la misma variable.

Las sustituciones usadas antes para obtener los cuatro casos de P[x,f(y),B] son:

s1 = {z/x, w/y}s2 = {C/y}s3 = {g(z)/x, A/y}s4 = {C/x, A/y}

Sea E una expresión, y s una sustitución, entonces "Es" es una expresión obtenida de Eal reemplazar simultáneamente toda ocurrencia de la variable vi por el término ti, así:

P[ z, f(w), B ] = P[ x, f(y), B ]s1

La composición de dos sustituciones s1 y s2 es denotada por s1s2, la cual es lasustitución obtenida al aplicar s2 a los términos de s1 y además adicionando cualquierpar de s2 teniendo variables que no ocurren entre las variables de s1. Así,

{g(x,y)/z}{A/x,B/y,C/w} = {g(A,B)/z,A/x,B/y,C/w}

Puede demostrarse que aplicando s1 y s2 sucesivamente a una expresión E es lo mismoque aplicar s1s2 a E; esto es, (Es1)s2 = E (s1s2). Puede también demostrarse que lacomposición de sustituciones es asociativa:



(s1s2)s3 = s1(s2s3)

Las sustituciones no son en general conmutativas; esto es, no se tiene generalmente elcaso que s1s2 = s2s1.

Si una sustitución s es aplicada a todo miembro de un conjunto {Ei} de expresiones, sedenota la sustitución por {Ei}s. Se dice que un conjunto {Ei} de expresiones esunificada si existe una sustitución s tal que E1s = E2s = ... = Ens = ...

En tal caso, s se dice es un unificador de {Ei}.

Por ejemplo, s ={A/x,B/y} unifica a{P[x,f(y),B]}, {P[x,f(B),B]} para producir {P[A,f(B),B].

Hay muchos algoritmos que pueden usarse para unificar un conjunto finito deexpresiones y/o reportar fallas cuando el conjunto no puede ser unificado.

El procedimiento UNIFIC, dado informalmente, se usa para establecer una ideageneral de como unificar un conjunto de dos expresiones de estructuras de listas.

PROC UNIFIC(E1,E2)SI E1 o E2 es un átomo

V: SI E1 y E2 son idénticasV: retornar NULLF: SI E1 es una variable,

V: SI E1 ocurre en E2V: retornar FALLOF: retornar (E2/E1)

FSIF: SI E2 es una variable,

V: SI E2 ocurre en E1V: retornar FALLOF: retornar (E1/E2)

FSIFSI

F: retornar FALLOFSI

F1 <-- el primer elemento de E1, T1 <-- el resto de E1F2 <-- el primer elemento de E2, T2 <-- el resto de E2Z1 = UNIFIC(F1,F2)SI Z1=FALLO

V: retornar FALLOF: G1 <-- el resultado de aplicar F1 a T1

FSIG2 <-- el resultado de aplicar F1 a T2Z2 <-- UNIFIC(G1,G2)SI Z2 = FALLO

V: retornar FALLO



F: retornar la composición Z1 y Z2FSIFSIFin UNIFIC()

Típicamente se usa unificación para observar si componentes concuerdan.

{PRIVADO }4.1.3. Resolución

La resolución es una importante regla de inferencia que puede ser aplicada a ciertasclases de fbf padres para hallar cláusulas. Una cláusula es una fbf que sólo contienedisyunciones.

Primero que todo, cualquier fbf puede ser convertida a un conjunto de cláusulas. Seilustra el proceso de conversión al aplicarlo a la siguiente fbf como ejemplo:

∀x{P(x) →{ ∀y[P(y) → P(f(x,y)] & ~ y[Q(x,y) → P(y)]}}

El proceso de conversión consiste de los siguientes pasos:

1. Eliminar implicaciones y equivalencias. Se aplican reglas equivalentes comoR2

∀x{~P(x) ∨ {∀y[~P(y) ∨ P(f(x,y))] & ~∀y[~Q(x,y) ∨ P(y)]}}

2. Reducir campo de acción de una negación. Existen diferentes reglas deequivalencia a aplicar, con el objeto que una negación sólo actúe sobre un predicado,estructura atómica o átomo, y en ningún momento sobre un conjunto de ellos que sehallen agrupados por algún tipo de paréntesis.

Para la fbf en cuestión se tiene:

∀x{~P(x) ∨ {∀y[~P(y) ∨ P(f(x,y))] & ∃y[Q(x,y) & ~P(y)]}}

3. Estandarizar variables. Dentro del dominio de cada cuantificador, una variableacotada por ese cuantificador es una variable simulada. Puede reemplazarse porcualquier otra, siempre y cuando no cambie el valor de verdad en la fbf.

∀x{~P(x) ∨ {∀y[~P(y) ∨ P(f(x,y))] & ∃w[Q(x,w) & ~P(w)]}}

4. Eliminar cuantificadores existenciales. Considérese la fbf ∀y[∃xP(x,y)].Nótese que el cuantificador existencial está dentro del dominio del cuantificadoruniversal, que da la posibilidad que la x que exista, pueda depender del valor de y. Se



hace esta dependencia explícita al definir alguna función g(y), la cual aplica a cadavalor de y en la x que existe18. Al usar esta función se elimina el cuantificadorexistencial escribiendo ∀yP(g(y),y).

La regla general para eliminar un cuantificador existencial de una fbf es reemplazarcada ocurrencia de la variable de existencialidad cuantificada por una función cuyosargumentos son esas variables del cuantificador existencial y que es acotada por elcuantificador universal.

Ejemplo sea[∀wQ(w)] →∀x{∀y{∃z[P(x,y,z) →∀uR(x,y,u,z)]}}

queda[∀wQ(w)] → ∀x{ ∀y{ P(x,y,g(x,y)) → ∀uR(x,y,u,g(x,y))}}

Si el cuantificador existencial a ser eliminado no está dentro del dominio de uncuantificador universal, la función de Skolem es sin argumentos, es decir, unaconstante. Así, ∃xP(x) por P(A), donde el símbolo constante A se usa para referirse aentidad que se conoce en un contexto. Es importante que A es un nuevo símboloconstante y no empleado dentro de la fórmula.

Para el ejemplo en desarrollo se tiene:

∀x{~P(x) ∨ {∀y[~P(y) ∨ P(f(x,y))] & [Q(x,g(x)) & ~P(g(x))]}}

5. Convertir a forma Prefija. Es mover todos los cuantificadores al frente de lafbf. En este estado no existen cuantificadores existenciales y cada cuantificadoruniversal tiene su propia variable.

Una fbf en forma prefija consiste de una cadena de cuantificadores universales,llamados prefijos, seguida por una fórmula libre llamada matriz.

La forma prefija de la fbf en desarrollo es:

∀x∀y{~P(x) ∨ {[~P(y) ∨ P(f(x,y))] & [Q(x,g(x)) & ~P(g(x))]}}

6. Colocar la fbf en forma normal conjuntiva (FNC). Cualquier fbf puede serescrita como un conjunto finito de conjunciones de literales. Tal matriz se dice que esuna FNC.

Si F es fórmula, es FNC si es escribe (F1 & F2 & ... & Fk), donde cada Fi (i=1,2,...,k)es un predicado, su negación o puede escribirse de la forma (G1 v G2 v...v Gl), dondecada Gj (j=1,2,...,l) es un predicado o su negación. 18 Tal función se llama función de Skolem (función de depuración).



Ejemplos de fórmulas en FNC es:[P(x) ∨ Q(x,y)] & [P(w) ∨ ~R(y)] & Q(x,y)P(x) ∨ Q(x,y)P(A) & Q(x,y)~R(g(y))(P(x) ∨ ~Q(y)) & (~R(z) ∨ Q(y)) & ~P(x)

Para la fórmula del ejemplo en desarrollo se tiene:∀x∀y{[~P(x) ∨ ~P(y) ∨ P(f(x,y))] & [~P(x) ∨ Q(x,g(y))] & [~p(x) ∨ P(g(y))]}

7. Eliminar cuantificadores universales. Puesto que todas las variables en la fbfestán totalmente acotadas, aseguramos que todas las variables que permanecen en estepaso son cuantificables universalmente. Además el orden de la cuantificación universalno es importante.

Por tanto, para la fbf en proceso, se tiene:[~P(x) ∨ ~P(y) ∨ P(f(x,y))] & [~P(x) ∨ Q(x,g(y))] & [~P(x) ∨ P(g(y))]

8. Crear cláusulas. Ahora puede eliminarse las ocurrencias de los símbolos &(conjunciones) reemplazando expresiones de la forma X1 & X2, con el conjunto de fbf{X1, X2}.

Cualquier fbf consistiendo de solamente disyunciones de literales es llamada formaclausular.

Nuestro ejemplo de desarrollo se transforma en:{~P(x) ∨ ~P(y) ∨ P(f(x,y)), ~P(x) ∨ Q(x,g(y)), ~P(x) ∨ ~P(g(y))}

9. Normalizar variables. Las variables pueden ser renombradas así que ningúnsímbolo variable debe aparecer en más de una cláusula.

Nuestras cláusulas ahora son:~P(x) ∨ ~P(y) ∨ P(f(x,y))~P(w) ∨ Q(w,g(w))~P(u) ∨ ~P(g(u))

La resolución en el cálculo de predicados es una regla de inferencia para probarteoremas. El conjunto de fbf de la cual se desea probar el teorema primero se conviertea cláusulas.

Puede demostrarse que si la fbf R es un modelo lógico de un conjunto de fbf, S,entonces, es también modelo lógico del conjunto de cláusulas obtenidas convirtiendola fbf de S a forma clausular. Por tanto, para el propósito trazado, las cláusulas son



formas completamente generales para expresar fbf.

Ejemplo:

∀x {P(x) → ~∃y { {Q(x,y) → R(y)} ∨ ~{R(x) → Q(x,y) }}}

1. ∀x {~P(x) ∨ ~∃y { {~Q(x,y) ∨ R(y)} ∨ ~{~R(x) ∨ Q(x,y) }}}

2. ∀x {~P(x) ∨ ∀y ~{ {~Q(x,y) ∨ R(y)} ∨ ~{~R(x) ∨ Q(x,y) }}}∀x {~P(x) ∨∀y {~ {~Q(x,y) ∨ R(y)} & {~R(x) ∨ Q(x,y) }}}∀x {~P(x) ∨∀y { {Q(x,y) & ~R(y)} & {~R(x) ∨ Q(x,y) }}}

3. y 4. No se aplican en este ejemplo.

5. ∀x∀y {~P(x) ∨ { {Q(x,y) & ~R(y)} & {~R(x) ∨ Q(x,y) }}}

6. ∀x∀y {{~P(x) ∨{{Q(x,y) & ~R(y)}}&{~P(x)v{~R(x) ∨ Q(x,y)} }}}∀x∀y {{~P(x) ∨ Q(x,y) } & {~P(x)∨~R(y)}} & {~P(x)∨ ~R(x) ∨ Q(x,y) }}

7. {~P(x) ∨ Q(x,y) } & {~P(x)∨~R(y)}} & {~P(x) ∨ ~R(x) ∨ Q(x,y) }

8. ~P(x) ∨ Q(x,y), ~P(x) ∨ ~R(y), ~P(x) ∨ ~R(x) ∨ Q(x,y)

9. ~P(x) ∨ Q(x,y), ~P(w) ∨ ~R(z), ~P(u) ∨ ~R(u) ∨ Q(u,v)

Ejemplo:

∀x {∃y{P(x,y)→ ~∃y{{Q(x,y) → R(y,x)} ∨ ~∃y{R(x,y) → Q(x,y) }}}}

1. ∀x{∃y{~P(x,y) ∨ ~∃y{{Q(x,y) -> R(y,x)} v ~∃y{R(x,y) → Q(x,y) }}}}∀x{∃y{~P(x,y) ∨ ~∃y{{~Q(x,y) ∨ R(y,x)} v ~∃y{R(x,y) → Q(x,y) }}}}∀x{∃y{~P(x,y) ∨ ~∃y{{~Q(x,y) ∨ R(y,x)} ∨ ~∃y{~R(x,y) ∨ Q(x,y) }}}}

2. ∀x{∃y{~P(x,y) ∨ ∀y~{{~Q(x,y) ∨ R(y,x)} ∨ ~∃y{~R(x,y) ∨ Q(x,y) }}}}∀x{∃y{~P(x,y) ∨ ∀y~{{~Q(x,y) ∨ R(y,x)} ∨ ∀y~{~R(x,y) ∨ Q(x,y) }}}}∀x{∃y{~P(x,y) ∨ ∀y~{{~Q(x,y) ∨ R(y,x)} ∨ ∀y{~~R(x,y) &~Q(x,y)}}}}∀x{∃y{~P(x,y) ∨ ∀y{~{~Q(x,y) ∨ R(y,x)} & ~∀y{R(x,y) & ~Q(x,y) }}}}∀x{∃y{~P(x,y) ∨ ∀y{{~~Q(x,y)&~R(y,x)} & ∃y~{R(x,y) &~Q(x,y)}}}}∀x{∃y{~P(x,y) ∨ ∀y{{Q(x,y)& ~R(y,x)} & ∃y{~R(x,y) ∨ ~~Q(x,y) }}}}∀x{∃y{~P(x,y) ∨ ∀y{{Q(x,y) & ~R(y,x)} & ∃y{~R(x,y) ∨ Q(x,y) }}}}

3. ∀x{∃y{~P(x,y) ∨ ∀y{{Q(x,y) & ~R(y,x)} & ∃z{~R(x,z) ∨ Q(x,z)}}}}∀x{∃y{~P(x,y) ∨ ∀w{{Q(x,w) & ~R(w,x)} & ∃z{~R(x,z) ∨ Q(x,z)}}}}

4. ∀x{∃y{~P(x,y) ∨ ∀w{{Q(x,w)& ~R(w,x)} & {~R(x,h(w)) ∨ Q(x,h(w))}}}}



∀x{{~P(x,g(x)) ∨ ∀w{{Q(x,w)& ~R(w,x)}& {~R(x,h(w)) ∨ Q(x,h(w))}}}}

5. ∀x∀w{{~P(x,g(x)) ∨ {{Q(x,w)& ~R(w,x)}& {~R(x,h(w)) ∨ Q(x,h(w))}}}}

6. ∀x,w{{~P(x,g(x)) ∨ {{Q(x,w)& ~R(w,x)}} & {~P(x,g(x)) ∨ {~R(x,h(w)) ∨Q(x,h(w))}}

∀x,w{~P(x,g(x))∨Q(x,w)}&{~P(x,g(x))v~R(w,x)}&{~P(x,g(x))∨~R(x,h(w))∨Q(x,h(w))}

7. {~P(x,g(x))∨Q(x,w)} & {~P(x,g(x)) ∨~R(w,x)} & {~P(x,g(x))∨ ~R(x,h(w)) ∨Q(x,h(w))}

8. ~P(x,g(x)) ∨ Q(x,w), ~P(x,g(x)) ∨ ~R(w,x) ,~P(x,g(x)) ∨ ~R(x,h(w)) v Q(x,h(w))

9. ~P(x,g(x)) ∨ Q(x,w) ,~P(y,g(y)) ∨ ~R(u,y) ,~P(z,g(z)) ∨ ~R(z,h(r)) ∨ Q(z,h(r))

Resolución general. De lo anterior se nota que alguna cláusula contiene términos quees la negación exacta de términos en otra cláusula. Del par de cláusulas puede inferirseotra cláusula.

En orden a aplicar resolución a cláusulas conteniendo variables, se requiere encontraruna sustitución que pueda ser aplicada a cláusulas padres así que ellas contenganliterales complementarios. Para discutir este caso, nos ayuda la representación de unacláusula por un conjunto de literales. Sean las cláusulas padres {Pi} y {Qi} yasumiendo que las variables que ocurren en esas dos cláusulas han sido estandarizadas.Sea que {pi} es subconjunto de {Pi} y que {qi} es un subconjunto de {Qi} tal que ununificador general s existe para la unión de los conjuntos {pi} y {~qi}. Se dice que lascláusulas {Pi} y {Qi} resuelven y que la nueva cláusula:

{{Pi} - {pi}}s + {{Qi} - {qi}}s es una resolvente de las dos cláusulas

Si dos cláusulas resuelven, ellas pueden tener más de una resolvente porque hay másde una manera para escoger {pi} y {qi}. En cualquier caso, ellas pueden tener al menosun conjunto finito de resolventes. Como ejemplo, tómese las cláusulas:

P[x,f(A)] ∨ P[x,f(y)] ∨ Q(y) , y ~P[z,f(A)] ∨ ~Q(z)

Con {pi} = {P[x,f(A)]} y {qi} = {~P[z,f(A)]}, se obtiene la resolvente P[z,f(y)] v~Q(z) v Q(y)

Con {pi} = {[P(x,f(A)],P[x,f(y)]} y {qi} = {~P[z,f(A)]} se obtiene la resolvente Q(A) v~Q(z)



Notese que en el último caso, dos literales en la primera cláusula colisionan al sustituiren un sólo literal, complementado por un ejemplo de uno de los literales de la segundacláusula.

Hay cuatro diferentes resolventes de esas dos cláusulas, tres se obtienen solucionandosobre P y una solucionando sobre Q. No es difícil demostrar que la resolución es unabásica regla de inferencia; esto es, que la resolvente de un par de cláusulas es unmodelo lógico de ese par de cláusulas.

Uso de la lógica. La lógica de primer orden, en la actualidad, es una de lasherramientas más importantes para la solución de problemas. Y su enfoquecorresponde a lo que se ha denominado como la Demostración Automática deTeoremas. En términos generales se describe como: los métodos para demostrar queun conjunto de cláusulas es insatisfactible, basados en los trabajos de Herbrand. Unamanera de describir la mecánica de los mencionados métodos es la siguiente: A partirde un conjunto de cláusulas originales P, se genera un conjunto de cláusulas baseinstanciadas P1, P2, ...,Pk. Los métodos deben controlar la generacióncombinatorialmente explosiva de nuevas cláusulas y obtener un conjunto de cláusulasque resultan ser insatisfactibles.

El modelamiento de acciones para determinar estados óptimos y metas de un tipo deproblemas pueden describirse por fbf de la lógica. En la figura 4.1(a), por ejemplo, semuestra una situación en la cual hay 4 bloques; A,B,C y D sobre una tabla.

0Figura 4.1 Acciones y colocación de bloques.

Puede representarse esta situación al realizar conjunción de las siguientes fórmulas:SOBRE(A,C),SOBRE(D,A),SOBRE(B,D),TOP(B),BASE(C)∀x [TOP(x) →~∃y SOBRE(y,x)

La fórmula TOP(x) significa que el bloque x no tiene otro bloque sobre él. Elpredicado SOBRE se usa para describir cuál bloque está directamente sobre otrobloque. La fórmula BASE(y) significa que y está sobre la tabla, la última fórmula da



información de como TOP y SOBRE puede tener una relación.

Una conjunción de varias de estas fórmulas puede servir como una descripción de unasituación particular. Se llama estado descripción. Actualmente, cualquier conjunciónfinita de fórmulas realmente describe una familia de diferentes estados, cada miembropuede mirarse como una interpretación satisfaciendo las fórmulas. Puede eliminarsealgunas de esas interpretaciones al adicionar o eliminar términos a la descripción, porejemplo, el conjunto anterior de fórmulas no dice nada del color de los bloques, así,puede describirse una familia de estados en la cual los bloques pueden tener varioscolores. Por ejemplo, adicionar la fórmula COLOR(B,café).

La manera en la cual esas fórmulas se usan depende del problema y la interpretación.En modelos de cambio de estado tal como los bloques, las acciones son instantáneas yno hay lugar para decir que algo es verdadero mientras esté en ejecución. Puesto quelos estados de descripción no incluyen información acerca de las acciones ocurridas,tales sistemas no pueden representar la ocurrencia de una acción mientras otra acciónno ocurra. Finalmente, no hay razonamiento acerca del futuro en esos modelos exceptopor búsqueda a través de diferente secuencia de acciones.

Suponiendo que el problema es demostrar que cierta propiedad es verdadera en unestado dado, por ejemplo, puede establecerse que no hay ningún bloque C en el estadodescrito en la figura. Podemos probar este hecho al demostrar la verdad de la fórmula~∃y SOBRE(y, A). Equivalentemente podemos demostrar que dicha fórmula es unteorema derivado de la descripción de estados al aplicar reglas de inferencia19.

Un uso obvio y directo de probar teoremas es al aplicarse a teoremas. Una menosobvia, pero importante, es el uso en sistemas inteligentes de recuperación deinformación donde deducciones deben desarrollarse a partir de una base de datos dehechos para hallar respuesta a las preguntas. Por ejemplo, para las expresiones:

administrador(compras,juan_quintero),trabaja_en(compras,maría_garcía), Y{[administrador(x,y) & trabaja_en(x,z)] → jefe_de(y,z)}

Un sistema espera contestar a "¿Quién es el jefe de María García?", tal pregunta puedeescribirse como el siguiente teorema a probar:

19 Se usa un SP para demostrar que una formula dada, llamada fbf meta, es un teorema derivable de unconjunto de formulas.



∃x jefe_de(x,maría_garcía).Figura 4.2 Acciones realizadas para ir desde el estado inicial a la META.

A menudo muchas tareas de razonamiento de sentido común que ordinariamente nopuede formalizarse, se manipulan por sistemas que prueban teoremas. La estrategiageneral es representar conocimiento especializado en el dominio como expresiones delcálculo de predicados y representar el problema o pregunta como un teorema a probar.

El estado inicial mostrado en la figura 4.1(a) y la meta en la figura 4.1(b) induce arealizar un conjunto de acciones que hace pasar por diferentes estados para cumplir elplan. Se requiere de acciones que podría ser DESPLAZAR(x,y), para colocar el bloquex encima del bloque y, siempre y cuando se tenga TOP(x) ^ TOP(y). La figura 4.2muestra esta secuencia.

{PRIVADO }4.1.4. Construcción de bases de conocimiento

La organización de objetos en clases es una parte medular en la representación delconocimiento. Aunque la relación que se establece con el mundo se produce a nivel deobjetos individuales, buena parte del razonamiento se realiza a nivel de clases. Unejemplo sencillo sería el de quien desea comprar una manzana, no es la compra de unobjeto específico, es de una Manzana. Las clases permiten hacer predicciones acercade los objetos, una vez que estos se clasifican. Es posible poder inferir la existencia deun objeto determinado a partir de una información perceptual, inferir que tipo deobjeto es dentro de una clase con base en las propiedades que se hayan percibido dedicho objeto y luego utilizar la información de la clase para hacer predicciones sobretodo el conjunto de objetos. Por ejemplo, con base en su piel verde, tamaño pequeño yforma redonda, puede inferirse que un objeto es una manzana (podría ser un tomate); yde ello, se infiere que puede servir para ensalada de frutas.

Existen dos maneras para representar clases en la lógica de primer orden. La primera,



la representación de clases mediante predicados unarios. Por ejemplo limon(x)significa x es un limón, casa(y) significa y es una casa. La segunda manera consiste enobjetivar la clase. La objetivación es el procedimiento mediante el cual un predicado ouna función se convierte en un objeto del lenguaje.20 En este caso, manzana es unsigno constante que se refiere al objeto constituido por el conjunto de todas lasmanzanas. Para decir x es una manzana, se escribe x en Manzanas. Mediante las clasesobjetivadas se hacen aseveraciones sobre la clase misma, más que sobre los objetos dedicha clase, por ejemplo, puede afirmarse poblacion(gallinas)=500, refiriéndose a lapoblación de gallinas en algún lugar.

Las clases desempeñan un papel muy importante; sirven para organizar y simplificar laBC a través de la herencia. Si se afirma que todos los objetos de la clase comida soncomestibles, y si decimos que tubérculos es una subclase de comida y que papa es unasubclase de tubérculos, diremos que el objeto papa es comestible. Se dice entonces queel objeto papa hereda la propiedad de ser comestible.

Las relaciones de subclase facilitan una jerarquía taxonómica de las clase.

La lógica de primer orden facilita la expresión de hechos que se refieren a clases, searelacionando los objetos con las clases, o cuantificándolos con sus objetos.

* Un objeto es un miembro de una clase. Por ejemplo:limonj de Limones

* Una clase es una subclase de otra clase. Por ejemplo:Limones pertenece a Frutas

* Todos los objetos de una clase tienen algunas propiedades. Por ejemplo:Para todo z, z de Limones ⇒ verde(z) & redondo(z)

* Los objetos de una clase se reconocen por ciertas propiedades. Por ejemplo:∀x amarillo(interior(x))&verde(exterior(x)) & x es Manzana ⇒ x es Fruta

* Una clase en cuanto un todo tiene algunas propiedades. Por ejemplo:Limones es alimento_acido.

Si bien las relaciones de subclase y de objetos son los más importantes para las clases,también es necesario ser capaces de establecer relaciones entre categorías que no sonsubclase unas de otras. Por ejemplo, al afirmar que hombre y mujer son subclase dehumanos, no se está diciendo que un hombre no puede ser una mujer. Se dice que dosclases son disyuntas sino tienen ningún objeto en común. 20 Objetivar no es un término muy adecuado. Varios intentos se han dado por utilizar un término correctosin que prospere la idea. Como el término "cosificación" propuesto por John McCarthy



Algunas clases se definen de manera rigurosa: un objeto se considera un triángulo si ysólo si es un polígono de tres lados. Por el contrario, muchas clases del mundo real sonclases de género natural, carentes de una definición precisa. Por ejemplo, base en supiel verde, tamaño pequeño y forma redonda, puede inferirse que un objeto es untomate (ya se había dicho antes que era manzana) por que los tomates que no estánmaduros aún se hallan verdes, debe darse otras características para distinguir muy bien.

La idea clave, para evitar problemas como lo anterior, es separar lo que es válido paratodos los elementos de una clase, de aquello que sólo se cumple en determinados casosde la clase. Por ejemplo, además de verde, redondo y pequeño, puede indicarse pulpablanda y en casos extremos se contaría con la clase típico(tomates). En este caso,típico es una función que correlaciona una clase con la subclase donde se hallan tiposespeciales.

La planificación de un menú es un ejemplo sencillo de como construir una BC.Realizar una cena requiere de saber preparar unos platillos, y estos requieren unosingredientes que son objetos de alguna clase. Si debo ir a la tienda a comprar losingredientes como: tomates, lechuga, pepino, manzanas amarillas, aceite de oliva, etc.y no encuentro tomates, al saber que dichos ingredientes eran para la ensalada se meocurrirá cambiarla por pimentones rojos. Pero si la lista es: tomates, cebolla cabezona,apio, zanahoria, carne molida, leche, vino blanco, etc., inferirá que se trata de prepararuna salsa a la boloñesa, por tanto, deberá reemplazar los tomates es por tomatesenlatados. La persona tendrá que hacer dos tipos de inferencia. La primera, de la listade partes poder inducir el objeto compuesto (clase), es difícil por que la combinaciónde las partes puede dar como resultado varios objetos compuestos. La segunda, lapersona debe ser capaz de decidir cómo reemplazar una parte que no se encuentra paracomplementar el objeto compuesto que interesa. Puede hacerse en dos niveles:reemplazando un ingrediente por otro y complementar el platillo o, reemplazar todo elplatillo para completar la cena o comida.

El primer paso consiste en convertir la lista de compras en una lista de partes: una listade clases.

refiere("tomates", hortaliza) orefiere("tomates", tomates)refiere("lechuga", hortaliza)refiere("pepino" , verduras)refiere("cebolla", hortaliza)refiere("zanahoria", hortaliza)refiere("alverja", legumbres)................

El siguiente paso consiste en describir clases en función de sus partes necesarias y de



las opcionales.

∀r,z parte_requerida(r,z) ⇒ ∀y, y en r ⇒ parte_requerida(y,w)

∀t,z parte_opcional(t,z) ⇒∀m, m en t ⇒ parte_opcional(m,z)

∀s,z parte_de(s,z) ⇔∃p, p en z ⇒∀j, j en s, parte_de(j,p)

∃q,z parte_opcional(q,z) ⇔∃k, k en z ⇒∀c, c en q, parte_de(q,k)

El siguiente paso consiste en describir comidas y platillos en función de sus partesrespectivas:

parte_requerida({plato_principal}, comidas)parte_opcional({entradas, ensaladas,...}, comidas)parte_requerida({lechuga, aderezo}, ensalada_verduras)parte_opcional({tomate, pepino, pimentón, zanahoria,...}, ensalada_verdura)...............................

Luego se necesita la información sobre platillos y alimentos. Posteriormente se decideque platillos preparar de la lista. Tenga en cuenta que faltarían algunos objetosrequeridos, pero que no van en la lista dado que se hallan en la casa, como la sal, lamantequilla, etc., por tanto debe existir algún predicado que los incluya.

{PRIVADO }4.2. INCERTIDUMBRE

Una limitación de la lógica de primer orden es que el sistema casi nunca tiene acceso atoda la verdad acerca del dominio del problema. Algunas de las cláusulas se infieren apartir de cláusulas previas, habrán preguntas importantes a las que el sistema no puededar respuesta categórica. El sistema debe, por tanto, actuar bajo condiciones deincertidumbre. La incertidumbre es en general producto de la incompletez y de lainexactitud del conocimiento sobre las características del ambiente del problema.

Un diagnóstico -sea médico, mecánico, financiero, o cualquier otro- es una tarea en laque por lo general está presente la incertidumbre. Si lo que nos interesara fuera paradiagnóstico odontológico, en LP propondríamos las reglas:

∀x sintoma(x,dolor_dientes) → padece(x, caries)

El problema inicia aquí, porque conocemos que no todos los pacientes que tienen dolorde dientes padecen de caries, por tanto, se amplia la regla, como:

∀x sintoma(x,dolor_dientes) → padece(x, caries)& padece(x, dolor_encias)& padece(x, estres)...



Desafortunadamente, para que la regla sea válida es necesario añadir una lista deposibles causas. Si se transforma la regla en:

Para todo x padece(x, caries) → sintoma(x, dolor_dientes)

Se tendría que tampoco está bien; no todas las caries producen dolor.

La única manera de tener una regla correcta es haciéndola exhaustiva21 desde el puntode vista lógico: ampliar las partes pertinentes. Incluso así, para efectos de diagnóstico,es necesario tomar en cuenta la posibilidad que el paciente tenga dolor de dientes apartir de otra causa.

La probabilidad es una forma de resumir la incertidumbre originada por la ignorancia opara no crear fórmulas extremadamente grandes. Posiblemente no sepamos cual es elpadecimiento específico de un paciente, sin embargo, considerando que existe unaposibilidad de 70% que la caries sea el motivo22. El restante 30% resume todas lasotras causas de dolor.

La probabilidad 0 asignada a un determinado predicado no indica que el predicado esfalso, en tanto, que una probabilidad de 1 no da la total característica de verdadero. Laprobabilidad 0.6 no implica que haya 60% de verdad, sino que el grado de creencia es80%, es decir una posibilidad bastante elevada, si se asigna una probabilidad de 0.75 aun predicado, entonces se espera que en 75% de los casos evaluados, el predicadoresultará en efecto verdadero.

Conforme una persona o el sistema recibe nuevas percepciones y realiza acciones23, laprobabilidad se actualiza, de manera que refleje nuevas evidencias.

La presencia de la incertidumbre modifica radicalmente la forma de tomar decisiones.Por lo general, una persona (o sistema) tiene una sola meta y ejecuta cualquier planque garantice el logro. Una acción se acepta o se rechaza dependiendo que permita ono alcanzar la meta, sin importar si existen otras acciones que permitan lograrlo. Parapoder tomar decisiones, es necesario que previamente se tenga diferentes preferencias.Un resultado determinado constituye un estado completamente especificado. Para larepresentación y razonamiento con las preferencias nos valdremos de la teoría de lautilidad. La utilidad de un estado depende de las preferencias que la función de utilidad 21 El listar el conjunto completo de antecedentes y/o consecuentes necesarios para garantizar reglas sinexcepciones implica demasiado trabajo, y también sería muy difícil emplear las reglas resultantes,además existen ciencias que aun no cuentan con una teoría completa del dominio de un problemaproduciendo ignorancia teórica y en algunas veces práctica. 22 La probabilidad a priori del 70% se obtiene de datos estadísticos, de algunas reglas generales o apartir de una combinación de diversas fuentes de evidencias. 23 La percepción implica la interpretación de la visión, los sonidos, los olores y el tacto. La acciónincluye la habilidad de navegar por el mundo y de manipular objetos.



debe representar.

Ahora entramos a trabajar con un lenguaje formal para representar el conocimientoincierto y razonar con él.

La notación p(A) indica la probabilidad a priori o incondicional que A es verdadera.

p(viaja_a(x,cali)) = .6 indica que la probabilidad que x viaje a Cali es 0.6.

p(tiempo = soleado) = 0.60p(tiempo = nublado) = 0.25p(tiempo = lluvia) = 0.15

Este último caso, el objeto de atención es la variable (aleatoria) tiempo. A todavariable aleatoria X corresponde un dominio de valores que puede asumir [a1, a2,...,am]. Términos de predicados pueden ser variables aleatorias y su dominio es[verdadero, falso].

Considerando esta notación, se escribiría p(tiempo) = [.6, .25, .15]. La aseveraciónanterior define una distribución de probabilidad para la variable tiempo.

Sea: Juan no está asegurado, viajó a Cali y Chocó, puede escribirse:~asegurado(juan) & viajó_a(juan,cali) & choco(juan)

En predicado:~Q(x) & R(x,y) & S(x)

Así que se escribe:p(~Q(x) & R(x,y) & S(x))=0.75

Para expresar la probabilidad de la oración compleja, conocidos los hechos, pero si seconoce p(~Q(x))=.8, p(R(x,y))=.9 y p(S(x))=.3, ¿cuál debe ser el razonamiento?

Una vez que se cuenta con evidencias respecto a las proposiciones desconocidas queconstituyen el dominio, las probabilidades a priori pierden vigencia. En vez de éstas, seutilizan las probabilidades condicionales o posteriores, representadas como p(A/B) yque se interpreta como "la probabilidad de A, considerando que se conoce B".

La ecuación: 0>p(B) ,p(B)

B) & p(A = p(A/B) , evalúa la probabilidad condicional.

La ecuación p(A v B) = p(A) + p(B) - p(A & B) expresa la probabilidad de unadisyunción.



La ecuación, 0>p(A) ,p(A)

p(A/B)p(B) = p(B/A) , se le conoce como regla de

Bayes. Constituye una regla importante para los SBC que emplean factoresprobabilísticos en las premisas de una regla para determinación del valor de verdad dela inferencia.

Aparentemente, la regla de Bayes no parecería ser de utilidad. La regla de Bayes es útilen la práctica gracias a que hay muchos casos en los que se dispone de buenasestimaciones de probabilidad para los tres términos necesarios (una probabilidadcondicional y dos probabilidades incondicionales) y es necesario calcular el cuarto.

Suponga que un doctor asegura que la meningitis provoca una rigidez en el cuello delpaciente, en el 50% de los casos, también conoce que entre 50000, una persona puedesufrir meningitis (M) y la probabilidad que algún paciente padezca rigidez en el cuello(R) es de 1/20, entonces: p(R/M) = 0.5, p(M)=1/50000, p(R)=1/20, por tanto,

p(M/R)=p(R/M)p(M) / p(R) = [0.5 * 1/50000 ] / [1/20] =0.0002

Es decir, se espera que sólo una persona de 5000 que padezca de rigidez en el cuellotenga meningitis.

Supongase que también interesa conocer la posibilidad que el paciente sienta latigazos,

Q, consecuencia de la rigidez en el cuello: p(R)

p(R/Q)p(Q) = p(Q/R) .

Para poder calcular la posibilidad relativa de la meningitis y del latigazo, partiendo queexiste una rigidez en el cuello, vemos que es necesario valorar la probabilidad a priorip(R). Y suponga que p(R/Q)= 0.8 y p(Q)=1/1000. Por tanto:

801 =

10001*.8

500001*.5

= p(R/Q)p(Q)p(R/M)p(M) =

p(Q/R)p(M/R)

.

Es decir, el latigazo tiene 80 veces más de posibilidad de presentarse que la meningitis,en el caso de un cuello rígido.

Es posible escribir las ecuaciones correspondientes a M y a ~M:

p(R)p(R/M)p(M) = p(M/R) y

p(R)M)M)p(p(R/ = M/R)p( ¬¬

¬ .



Al sumar ambas ecuaciones, y tomando en cuenta que p(M/R)+p(~M/R)=1 se obtiene:

p(R) = p(R/M)p(M) + p(R/~M)p(~M) y al sustituir en la ecuación para p(M/R), setiene:

M)M)p(p(R/ + p(R/M)p(M)p(R/M)p(M) = p(M/R)

¬¬.

Procedimiento que se conoce con el nombre de normalización.

La lógica difusa es probablemente la técnica más prometedora para el manejo de laincertidumbre, la mayoría de los métodos disponibles modelan la incertidumbrecuantitativamente (un hecho tiene un grado de verdad de 0.8, por ejemplo). Por otraparte, la lógica difusa modela la incertidumbre con conjuntos difusos. Los conjuntosconvencionales tienen un bien definido grupo de elementos y estos pertenecen o no alconjunto. Sin embargo, en los conjuntos difusos las funciones de pertenencia puedenalcanzar valores entre 0 y 1, indicando que la pertenencia de ciertos elementos no esclara.

{PRIVADO }4.3. EJERCICIOS

1. Sean las oraciones Martha es la madre de Carlos, Fidel es un ancestro deCarlos.Representadas por madre(martha,carlos), ancestro(fidel,carlos) escribir una fbfpara representar Todo ancestro de Carlos es o su padre, su madre o uno de susancestros.

2. Representar las siguientes oraciones por fbf en lógica de predicados:

a) Un sistema de computador es inteligente si puede desarrollar una tarea lacual, si es desarrollada por un humano, usa inteligencia.b) Si un programa no puede entender un hecho, entonces el no puede aprenderese hecho.c) Todas las asignaturas son básicas para todas las carreras, existen asignaturasque no son básicas para la profesión, por tanto, hay asignaturas que no debenser básicas.

3. Convertir las siguientes fbf a forma clausular

a) ∀x{P(x) → {∀y[P(y) → P(f(x,y))] & ~∃y[Q(x,y) → P(y)]}}

b) {∀xP(x)} → {∃x[~P(x)]}



c) ∀xy{[P(x,y) → Q(y,x)] & [Q(y,x) → S(x,y)]}→ ∀xy[P(x,y) → S(x,y)]

d) ∀x{[R(x) & C(x,a)] → [O(x,b) ∨ {∃y(∃z[O(y,z) → Q(x,y)])}]}

4. Formalizar los siguientes enunciados:

a) Si gana millonarios, viajo a Cali. Si gana santafé, viajo a Medellín, ganósantafé o millonarios. Voy para Medellín, por tanto, millonarios no ganó.

b) Si Diego estudia, aprueba. Si Diego no estudia, está enfermo. Diego niestudia ni esta enfermo. Por tanto, Diego esta de vacaciones.

c) Todo estudiante es honesto. Juan no es honesto luego, Juan no esestudiante.

d) Todo atleta tiene físico y es fuerte. Todo aquel que es fuerte e inteligentetendrá éxito en la carrera, Pedro es atleta, Pedro es inteligente, luego, Pedrotiene éxito en la carrera.

e) No voy a Cali ni a Medellín.

4. representaciÓn formal - disi.unal.edu.codisi.unal.edu.co/~lctorress/iartificial/ia0009l.pdf ·...

Documents