Inteligencia Artificial: Lógica formal

Ejemplos Clic

Muchos de los sistemas de representación del conocimiento de la actualidad se basan en algún tipo de lógica formal. La lógica formal aporta un buen número de ventajas para la representación del conocimiento y su manejo, partiendo de una sintaxis y semántica bien definidas que detallan perfectamente la forma de construir sentencias y razonamientos sobre ellas.

Una proposición es una sentencia que puede decirse que es falsa o verdadera. En la lógica proposicional se asigna símbolos a cada sentencia y se utilizan operadores lógicos sobre ellos para crear proposiciones más complejas. Los símbolos utilizados son AND (∧), OR (∨), NOT (¬), IMPLIES (→ o ⇒), y EQUIVALENCE (⇔). Partiendo de los símbolos y utilizando los diferentes operadores se construyen proposiciones complejas, las cuales es posible obtener si son ciertas o falsas operando a partir de los valores de verdad de cada uno de los símbolos iniciales, utilizando el cálculo proposicional.

Por ejemplo la sentencia si “El libro está en casa (A) y Juan está en el trabajo (B), Juan no puede leer el libro (C)”, podría representarse como: A ∧ B → C

LÓGICA DE PRIMER ORDEN

Es una ampliación de la lógica proposicional a partir de dos operadores más, el cuantificador universal ∀ y el existencial ∃. Utiliza también símbolos para representar conocimiento y operadores lógicos para construir sentencias más complejas, pero a diferencia de la lógica proposicional, los símbolos pueden representar constantes, variables, predicados y funciones.

Las constantes son símbolos que comienzan por minúsculas y las variables símbolos que empiezan por mayúsculas. Los predicados representan afirmaciones sobre objetos, por ejemplo, la afirmación “El libro está en casa” se representaría como un predicado de nombre in:

in(libro, casa)

Se podría reescribir el predicado de forma más general sustituyendo las constantes por variables de la forma: in(X, Y). Con él podríamos representar diferentes proposiciones como “El libro está en casa”, “El coche está en el garaje”, “Juan está en el trabajo”.

El último símbolo que queda por explicar son las funciones. Éstas permiten asociar elementos de un conjunto a un elemento de otro conjunto, por ejemplo: propietario(casa) = juan.

Con todo esto podríamos representar el mismo ejemplo que con lógica proposicional de la siguiente forma:

in(libro, casa) ∧ in(juan, trabajo) → ¬puedeLeer(juan, libro)

En cuanto a los dos nuevos operadores, ∀ y ∃, permiten delimitar el alcance de las variables en las sentencias, de forma que “∀X” se leería como “para toda x” y “∃X” como “existe un x tal que”.

∃X puedeLeer(X, libro): alguien puede leer el libro
∀X puedeLeer(X, libro): todo el mundo puede leer el libro

Considera el siguiente argumento:

Mañana es miércoles o mañana es jueves.
Mañana no es jueves.
Por lo tanto, mañana es miércoles.

Es un argumento válido. Quiere decir que es imposible que las premisas sean verdaderas y la conclusión falsa. Esto no quiere decir que la conclusión sea verdadera. Si las premisas son falsas, entonces la conclusión también podría serlo. Pero si las premisas son verdaderas, entonces la conclusión también lo es.

Está soleado o está nublado.
No está nublado.
Por lo tanto, está soleado.

En cambio, la validez de estos dos argumentos depende del significado de las expresiones «o» y «no». Si alguna de estas expresiones se cambiara por otra, entonces podría ser que los argumentos dejaran de ser válidos. Por ejemplo:

Ni está soleado ni está nublado.
No está nublado.
Por lo tanto, está soleado.

Las expresiones de las que depende la validez de los argumentos se llaman constantes lógicas. La lógica proposicional estudia el comportamiento de algunas de estas expresiones, llamadas conectivas lógicas. En cuanto a las expresiones como "está nublado" o "mañana es jueves", lo único que importa de ellas es que tengan un valor de verdad. Es por esto que se las reemplaza por simples letras, cuya intención es simbolizar una expresión con valor de verdad cualquiera. A estas letras se las llama variables proposicionales, y en general se toman del alfabeto latino, empezando por la letra p, luego q, r,s, etc. Así, los dos primeros argumentos de esta sección podrían reescribirse así:

p o q
No q
Por lo tanto, p

Y el tercer argumento, a pesar de no ser válido, puede reescribirse así:

Ni p ni q
No q
Por lo tanto, p

Conectivas lógicas

Conectiva	Expresión en el lenguaje natural	Ejemplo	Símbolo en este artículo	Símbolos alternativos
Negación	no	No está lloviendo.	$\neg \,$	$\sim \,$
Conjunción	y	Está lloviendo y está nublado.	$\and$	$\And \,$ $.$
Disyunción	o	Está lloviendo o está soleado.	$\or$
Condicional material	si... entonces	Si está soleado, entonces es de día.	$\to \,$	$\supset$
Bicondicional	si y sólo si	Está nublado si y sólo si hay nubes visibles.	$\leftrightarrow$	$\equiv \,$
Negación conjunta	ni... ni	Ni está soleado ni está nublado.	$\downarrow \,$
Disyunción excluyente	o bien... o bien	O bien está soleado, o bien está nublado.	$\nleftrightarrow$	$\oplus, \not\equiv, W$

Deducción natural

Un sistema de lógica proposicional también puede construirse a partir de un conjunto vacío de axiomas. Para ello se especifican una serie de reglas de inferencia que intentan capturar el modo en que naturalmente razonamos acerca de las conectivas lógicas.

Introducción de la negación: De $(p \to q)$ y $(p \to \neg q)$ , se infiere $\neg p$ .; Esto es, $\{ (p \to q), (p \to \neg q) \} \vdash \neg p$ .
Eliminación de la negación: De $\neg p$ , se infiere $(p \to r)$ .; Esto es, $\{ \neg p \} \vdash (p \to r)$ .
Eliminación de la doble negación: De $\neg \neg p$ , se infiere $p$ .; Esto es, $\neg \neg p \vdash p$ .
Introducción de la conjunción: De $p$ y $q$ , se infiere $(p \land q)$ .; Esto es, $\{ p, q \} \vdash (p \land q)$ .
Eliminación de la conjunción: De $(p \land q)$ , se infiere $p$ .; De $(p \land q)$ , se infiere $q$ .; Esto es, $(p \land q) \vdash p$ y $(p \land q) \vdash q$ .
Introducción de la disyunción: De $p$ , se infiere $(p \lor q)$ .; Esto es, $p \vdash (p \lor q)$ y $q \vdash (p \lor q)$ .
Eliminación de la disyunción: De $(p \lor q)$ y $(p \to r)$ y $(q \to r)$ , se infiere $r$ .; Esto es, $\{p \lor q, p \to r, q \to r\} \vdash r$ .
Introducción del bicondicional: De $(p \to q)$ y $(q \to p)$ , se infiere $(p \leftrightarrow q)$ .; Esto es, $\{p \to q, q \to p\} \vdash (p \leftrightarrow q)$ .
Eliminación del bicondicional: De $(p \leftrightarrow q)$ , se infiere $(p \to q)$ .; De $(p \leftrightarrow q)$ , se infiere $(q \to p)$ .; Esto es, $(p \leftrightarrow q) \vdash (p \to q)$ y $(p \leftrightarrow q) \vdash (q \to p)$ .
Modus ponens (eliminación del condicional): De $p$ y $(p \to q)$ , se infiere $q$ .; Esto es, $\{ p, p \to q\} \vdash q$ .
Prueba condicional (introducción del condicional): De [acepando que $p$ permite una prueba de $q$ ], se infiere $(p \to q)$ .; Esto es, $(p \vdash q) \vdash (p \to q)$ .

Nombre	Consecuente	Descripción
Modus Ponens	$((p \to q) \land p) \vdash q$	Si $p$ entonces $q$ ; $p$ ; por lo tanto $q$
Modus Tollens	$((p \to q) \land \neg q) \vdash \neg p$	Si $p$ entonces $q$ ; no $q$ ; por lo tanto no $p$
Silogismo Hipotético	$((p \to q) \land (q \to r)) \vdash (p \to r)$	Si $p$ entonces $q$ ; si $q$ entonces $r$ ; por lo tanto, si $p$ entonces $r$
Silogismo Disyuntivo	$((p \lor q) \land \neg p) \vdash q$	Either $p$ o $q$ , o both; no $p$ ; por lo tanto, $q$
Dilema Constructivo	$((p \to q) \land (r \to s) \land (p \lor r)) \vdash (q \lor s)$	Si $p$ entonces $q$ ; y si $r$ entonces $s$ ; pero $p$ o $r$ ; por lo tanto $q$ o $s$

Ejemplo de una demostración[editar]

Demostrar:

A \to A \,

Una posible prueba de esto (que, aunque válida, pasa a contener más pasos de los necesarios) se puede disponer de la siguiente manera:

Paso	Fórmula	Razón
1	$A$	Premisa.
2	$A \or A$	Desde (1) por introducción de la disyunción.
3	$(A \or A) \and A$	Desde (1) y (2) por introducción de la conjunción.
4	$A$	Desde (3) por eliminación de la conjunción.
5	$A \vdash A$	Resumen de (1) hasta (4).
6	$\vdash A \to A$	Desde (5) por introducción del condicional. QED

Inteligencia Artificial

domingo, 10 de agosto de 2014

Lógica formal

Deducción natural

Ejemplo de una demostración[editar]

No hay comentarios:

Publicar un comentario