practicas

Practicas de Logica en aula informatica (Curso 2010-11)

Practica 1: Logica y lenguaje Prolog, parte I.Febrero: 10 y 17.

Practica 2: Logica y lenguaje Prolog, parte II.Febrero: 24; Marzo: 3

Practica 3: Logica y lenguaje Prolog, parte III.Marzo:10, 17

Practica 4: Logica y lenguaje Prolog, parte IV.Marzo: 24, 31

Practica 5: Deduccion natural con ADN. Proposiciones.Abril: 6, 14

Practica 6: Deduccion natural con ADN. Predicados.Mayo: 5, 12

Nota: El trabajo realizado en cada practica se debera entregar al fina-lizar la misma o con una demora maxima de 7 dıas (por ejemplo, si unapractica se realiza en Jueves el tiempo de entrega acaba a las 24 horas delMiercoles siguiente).

La entrega se realizara exclusivamente a traves del servidor belenus. Nose valoraran las entregas realizadas fuera de plazo, en disquetes o correoelectronico, salvo que problemas tecnicos impidieran la entrega a traves delservidor.

Los alumnos que no hayan asistido al menos a cinco practicas informati-cas, o los que habiendo asistido hayan presentado soluciones incompletas oincorrectas, deberan realizar en el examen final de practicas, que se valo-rara tambien hasta un maximo de un punto.

Los alumnos que no hayan aprobado las practicas informaticas medianteasistencia y entrega de las practicas realizadas y hayan suspendido el examenfinal de practicas informaticas podran presentarse a la segunda convocatoria(examen de Julio).

El actual sistema de evaluacion no permite “guardar”las practicas de uncurso al siguiente. De modo que el alumno que no hay superado la segundaconvocatoria si se matricula de nuevo en la asignatura se le aplicara de nuevoel sistema de evalacion descrito anteriormente.

Practicas de Logica en aula informatica (Curso 2010-11) — Practica 1

PROLOG Y EL LENGUAJE DE LA LOGICA DE PRIMER ORDEN

1. Creando mi primer programa prolog

Vamos a realizar nuestro primer programa prolog (gprolog). Para ello,utilizando la aplicacion XGP, crea un documento que se llamara familia.pl

(NO TECLEES EL PROGRAMA EN LA CONSOLA)(ACUERDATE DE ACABAR EN PUNTO LA LINEA)(NO HAY ESPACIO BLANCO ANTES DEL PARENTESIS)

%Empezamos creando una base de datos con predicados monadicos:

mujer(maria).mujer(laura).mujer(teresa).mujer(elena).hombre(pablo).hombre(juan).hombre(luis).hombre(carlos).

%Continuamos con predicados binarios (2-adicos, 2-arios)

progenitor(pablo,juan).progenitor(juan,luis).progenitor(juan,maria).progenitor(luis,carlos).progenitor(luis,laura).progenitor(laura,teresa).progenitor(laura,elena).

%Ahora guarda el documento con el nombre de familia. La aplicacion XGP%creara un documento llamado familia.pl

2. Consultando mi primer programa

Utiliza ‘Open’ del menu ‘File’ para abrir el documento.Si el codigo era correcto contesta en la consola con una expresion del si-guiente tipo:

.../prolog/proyectos/familia.pl compiled, 27 lines read - 1203 bytes written,14 msSi el codigo fuente no es correcto, en la consola aparece un mensaje de laforma:.../prolog/proyectos/familia.pl:8 error: syntax error: . or operator expectedafter expression (char:1)1 error(s)compilation failed

Entonces en la ventana de edicion puedes introducir el numero de lınea,el 8 en este caso, y despues intentar corregir el error. Despues de salvar eldocumento, lo puedes reconsultar desde el menu ‘Tools’. Repite el procesohasta que se pueda compilar el programa.Nota: Si se ha utilizado utilizado un editor externo, puede haber problemassi no se ha creado un documento con finales de lınea de tipo UNIX.

3. Realizando consultas

Respuestas: Sı o no.

Tras compilar un programa desde el interprete, se pueden realizar consultasrelacionadas con el programa. En la subventana superior introduce:

progenitor(juan, luis).

El la inferior se obtiene:?- progenitor(juan, luis).Success

Si se repite el proceso conprogenitor(juan, laura).

Se obtiene:?- progenitor(juan, laura).Failure

Consultas y variables

Si alguno de los atributos es una variable, el interprete retornara los valo-res que puede tomar para ser satisfecha. El nombre de una variable ha decomenzar con mayuscula, o con guion bajo:

Si realizas la consultaprogenitor(juan,X).El interface grafico del interprete puede responder de varias formas: Pulsan-do el boton ‘Once’ responde:

?- progenitor(juan,X).X = luis

Pulsando el boton ‘First’ y a continuacion pulsamos ‘Next’ dos veces seobtiene?-progenitor(juan,X)Soln: 1X = luis;Soln: 2X = maria;No More Solutions.

El punto y coma hay que interpretarlo como el conector logico ∨ . En estecaso significa que a la consulta realizada son soluciones la primera o (; , ∨)la segunda. Se puede seguir pulsando ‘Next’ hasta que se agoten las posiblessoluciones. Si directamente pulsamos ‘All’, el interprete responde:?- progenitor(juan,X).Soln 1: SuccessX = luisSoln 2: SuccessX = mariaSoln 3: No More Solutions.Significa que hay dos soluciones y cuando intenta busca la tercera no en-cuentra mas soluciones.Varias variablesEn consultas con varias variables, se retornaran todas las combinaciones devalores posibles. Si se realiza la consulta:?- progenitor(X,Y).se obtienen las soluciones:?-progenitor(X,Y)Soln: 1 X = pablo Y = juan ;Soln: 2 X = juan Y = luis ;Soln: 3 X = juan Y = maria ;Soln: 4 X = luis Y = carlos ;Soln: 5 X = luis Y = laura ;Soln: 6 X = laura Y = teresa ;Soln: 7 X = laura Y = elena ; No More Solutions.

Consultas con varios predicadosEs posible combinar varios predicados en la misma consulta. En este caso,para satisfacer la consulta deberan satisfacerse todos ellos:La consultaprogenitor(juan,Y), progenitor(Y,carlos).es contestada ası:?- progenitor(juan,Y), progenitor(Y,carlos).

Soln 1: SuccessY = luis;No More Solutions.Es importante observar que la coma es interpretada como el conector logicoconjuntivo (y , ∧).La pregunta (ATENCION PONE PUNTO Y COMA)progenitor(juan,Y) ; progenitor(Y,carlos).es contestada del modo siguiente:?- progenitor(juan,Y) ; progenitor(Y,carlos).Soln 1: SuccessY = luisSoln 2: SuccessY = mariaSoln 3: SuccessY = luis;No More Solutions.En este caso el punto y coma es interpretado como el conector logico dis-yuntivo.EjerciciosFormula en prolog las siguientes consultas:¿Quien es el progenitor de Luis?¿Quien es el abuelo de Laura?¿Quien es hermano de Carlos?¿Quien es tıo o tıa de Carlos?

4. Reglas

Si tenemos una formula conteniendo variables libres que describen un domi-nio finito, podemos considerar la tuplas que satisfacen dicha formula. Porotro lado una formula implica otra si cada tupla que satisface la primera,tambien satisface la segunda.El el programa familia podrıamos introducir todos los hechos inversos acercade quien es hijo de quien:hijo(luis,juan).hijo(maria,juan).Una manera mas sencilla serıa introducir una regla:Para todo X e Y, si X es progenitor de Y, entonces Y es hijo de X .Que se formula como∀X∀Y (progenitor(X, Y )→hijo(Y,X)) .En la sintaxis de prolog, lo que se hace es considerar la siguiente reglaasociada

hijo(Y,X):-progenitor(X,Y).Notemos, que este tipo de programas prolog las variables toman finitos va-lores buscando en la base de datos formada por los hechos.Ahora tenemos dos opciones o ampliar nuestro documento familia con lalınea anterior o crear un nuevo programa con la linea adicional. Si quierescrea un nuevo documento ampliacion.pl con la regla anterior. Si consultasambos documentos familia.pl y apliacion.pl tendras a tu disposicion los he-chos y reglas que contienen ambos. Por ejemplo, puedes consultarhijo(X,juan).Varios antecedentesSi quieres distinguir hijo de hija lo puedes hacer utilizando la conjuncion devarios antecedentes. Borra la lınea anterior de ampliacion.pl e introduce lasdos siguientes:hija(Y,X) :- progenitor(X,Y),mujer(Y).hijo(Y,X) :- progenitor(X,Y),hombre(Y).Salva el documento y ahora realiza la consultahijo(X,juan).La respuesta es?- hijo(X,juan).SuccessX = luisEs posible que obtengas otra respuesta. Puede deberse a que anteriormentehijo(Y,X) estaba definido de otro modo. Si has (re) consultado el docu-mento amplicacion.pl obtendras la respuesta correcta, en otro caso seguirasobteniendo la que tenıas con la regla antigua.Es interesante que te fijes si en la ventana ‘Evaluate Query ...’ esta activadoo no el boton ‘Consult Changes Before Evaluating ...’ . Si esta activado XGPse encarga de (re) consultar las reglas y hechos por si ha habido cambios.Volviendo a la sintaxis de prolog, hay que observar que la conjuncion depredicados se expresa mediante comas y que los caracteres ‘:-’ correspondenal conector condicional ← .Por ejemplo, ahora puedes introducir el predicado binario (2-ario) hermanomediantehermano(X,Y) :- progenitor(Z,X), progenitor(Z,Y).EjerciciosEscribe en prolog: Todo aquel que tiene un hijo es feliz.Define las relaciones “abuelo” y “nieto”Describe (informalmente) como modificarıas el predicado hermano para queno saliera uno hermano de sı mismo.En vez de conjuncion de predicados se puede trabajar con disyuncion depredicados. Si queremos averiguar el universo que describen las variables,podemos buscar los hechos descritos por predicados monadicos (1-arios) yhacer la reunion de los dominios de cada predicado monadico (1-ario).universo(X):-hombre(X); mujer(X).

Si en algun otro lugar de los documentos consultados o predicados predefi-nidos en el sistema existe otra regla con cabeza (consecuente), universo(X),el universo puede hacerse aun mayor de lo que permite la regla anterior.Por ejemplo podemos considerar las dos reglastrozouniverso(X):-hombre(X).trozouniverso(X):-mujer(X).Ahora la consultasuniverso(X).trozouniverso(X).obendran identica respuesta.

Ejercicio para entregar. Amplia el programa familia.pl del modo siguien-te:a) Aumenta el numero de hombres y mujeres que forman la base de hechos.b) Introduce en la base de hechos algunos matrimonios (matrimonio/2)d) Define los predicados binarios: suegro, suegra, yerno, nuera, cunado,cunada.e) Introduce en la base de hechos algunos divorcios y redefine el predicadomatrimonio.f) Define los siguientes nuevos predicados: exmarido, exmujer, ....Antes de entregar la practica comprueba que el codigo fuente funciona co-rrectamente.Para la practica 1 se entregaran en dos ficheros: memoria y codigo. Se entre-gara utilizando la zona de envıo del servidor belenus (http://belenus.unirioja.es/).El codigo fuente entregado tendra todo lo necesario para que se pueda eje-cutar los diferentes procedimientos. El codigo debera estar adecuadamentecomentado.La memoria constara de las siguientes secciones:1. Introduccion (una hoja de descripcion de lo que hay que hacer desdevuestro punto de vista y no copiando el enunciado).2. Descripcion a alto nivel de lo realizado: que predicados se han definidoque problema resuelve cada uno de ellos y como se relacionan unos con otros,etc3. Codigo fuente completo con comentarios (el codigo final no deberıa sermuy largo)4. Unas cuantas consultas y los resultados obtenidos5. Conclusiones (que se ha aprendido, dificultades encontradas, comentariossobre gprolog, etc).


PROLOG Y PROGRAMACION CON VARIABLES CONRESTRICCIONES

5. Introduccion a la programacion con variablesde domino finito

Esta practica explicara brevemente algunas funciones que se utilizan enGprolog para resolucion de restricciones, veremos como se utilizan y unosejemplos resueltos para facilitar la comprension.Para trabajar con las funciones de dominio finito se necesita un nuevo tipo dedatos, estas son las variables FD que tienen asociado un dominio que acotalos valores que pueden tomar. Inicialmente este dominio comprende el rangode 0..fd max integer, siendo la constante el valor maximo que puede tomarla variable. Estas variables son totalmente compatibles con las variables yenteros de prolog, si un predicado de restricciones espera una variable fd,se le puede pasar una variable de prolog que tomara los valores de todo elrango o un entero que sera considerado como un rango de un solo valor.Vamos a describir los predicados FD mas importantes que se han utilizadoen los problemas de ejemplo resueltos. Estos predicados son:fd domain/2, fd domain/3fd labeling/1, fd labeling/2fd all different/1Predicados : fd domain/2, fd domain/3Los predicados fd domain restringen una variable a tomar valores dentro deun dominio. Definiendo una restriccion para una variable comun de prologcreamos una variable con un dominio finito (variable FD).Veamos unos ejemplos:fd domain/3Este predicado se utilizara para definir variables con un dominio finito quees un rango continuo.fd domain(A,B,C)A – variable FDB – cota inferior del rango del dominio finitoC – cota superior del rango del dominio finitoEjemplo: Queremos definir una variable con un dominio finito que es el rango[5..25].

| ? fd_domain(VariableFD,5,25).VariableFD = _#3(5..25)

(En la invocacion al fd domain VariableFD era una variable normal, quefinalmente se mapea a una variable #3 con un dominio finito [5..25]. Aunqueponga (5..25), los valores 5 y 25 forman parte del dominio.)En el siguiente ejemplo vemos que fd domain establece restricciones sobre eldominio y que su accion es consistente con otras restricciones que hayamospodido definir antes.Ejemplo: Definimos una restriccion sobre la variable X, no puede tomar elvalor 5, con ello implıcitamente hemos declarado una variable FD con domi-nio [0..4,6..127]. Para a continuacion, agregar otra restriccion con fd domain,reduciendo el dominio de X a [0..4,6..10].

| ?X#\=5, fd_domain(X,1,10).X = _#2(1..4:6..10)

fd domain/2Este predicado se utilizara para definir variables con un dominio finito for-mado por un conjunto de valores arbitrarios que se representaran por unalista.fd domain(A,B)A – variable FDB – lista de valores que representa el dominioEjemplo: Queremos definir una variable con un dominio finito que es el rango[2..4]. Algo, que podıamos tambien haber hecho con fd domain(VariableFD,2,4).

| ?fd_domain(VariableFD,[2,3,4]).VariableFD = _#2(2..4)

Como curiosidad vemos que podemos definir el mismo rango, desordenandolos valores. El dominio resultante es el mismo que en el ejemplo anterior.

| ?fd_domain(VariableFD,[2,4,3]).VariableFD = _#2(2..4)

Predicados : fd labeling/2, fd labeling/1Aplicando el mecanismo de resolucion de restricciones integrado en gprolog,podemos encontrarnos en 3 escenarios:– Se obtiene el dominio vacıo para una o mas variables FD. Esto signifi-cara que el problema es insatisfactible.– Los dominios de todas las variables FD se han reducido a un solo elemento(pueden ser valores distintos para cada variable). Esta situacion se definecomo “valuation domain”. De esta situacion se deduce una asignacion a lasvariables que representa una solucion del problema.– No hay dominios vacıos, pero algunos dominios tienen mas de un elemento.Esta situacion no nos permite saber si el problema es satisfactible (en unprimer momento).

El tercer escenario da lugar a la conclusion de que el mecanismo de resolucionintergrado basado en restricciones sin mas es incompleto. Necesitamos unprocedimiento que nos permita iterar sobre esos dominios multivaluados,reduciendo en cada iteracion el dominio de cada variable al sucesivo valory volviendo a propagar las restricciones esperando obtener un “valuationdomain”. Cada “valuation domain” representara una solucion al problema.Este procedimiento viene implementado en gprolog con el predicado fd labeling(fd labeling/1 y fd labeling/2) (que por otro lado se puede programar facil-mente haciendo uso de varios predicados sencillos de fd, como fd dom). Conel uso de fd labeling ya obtenemos un mecanismo de resolucion de restric-ciones sobre dominios finitos completo.El predicado fd labeling/1 recibe como primer parametro la lista con las va-riables con dominio finito y prueba a asignar a cada variable un valor dentrode su dominio y realiza backtracking sobre esas asignaciones permitiendoencontrar todas las posibles soluciones.Ejemplo: Tenemos un problema con dos variables A y B que tienen ambasdominios de mas de un elemento [1..3], a aparte de la restriccion del dominioa [1..3], tambien definimos por ejemplo que A debe ser distinta de B. Laresolucion intergrada en gprolog basada solo en restricciones, lo maximoque ha podido es reducir los dominios de las variables a los que se ven [1..3],pero no es capaz de proporcionarnos una respuesta concreta determinista.Necesitamos que el dominio de cada variable se reduzca a un solo valor,obteniendo una asignacion que representa una solucion al problema.

| ?fd_domain([A,B],1,3),A#\=B.A = _#3(1..3)B = _#25(1..3)

Ahora aplicamos fd labeling sobre las lista de variables FD (A y B) y vemosque se realiza un backtracking sobre la reduccion de cada dominio a los suce-sivos valores que lo formaban, en cada iteracion se propagan las restriccionesen funcion de los monovalores concretos a los que quedan restringidas lasvariables y se obtienen todas las soluciones.

| ?fd_domain([A,B],1,3),A#\=B, fd_labeling([A,B]).A = 1B = 2 ? ;A = 1B = 3 ? ;A = 2B = 1 ? ;A = 2B = 3 ? ;A = 3

B = 1 ? ;A = 3B = 2

El orden de la seleccion de los valores a los que quedara reducido el dominio,ası como por que variable empezara la accion del etiquetado pueden tener unefecto notable en el rendimiento de la busqueda. El predicado fd labeling/2permite definir con su segundo parametro distintas estrategias para la se-leccion del valor y la variable. Algunas de estas estrategias son por ejemploempezar por las variables cuyo dominio es el mas reducido de todos o porlas variables que intervienen en un mayor numero de restricciones,... Enfd labeling/1 se omite la especificacion de las estrategias lo que supone uti-lizar las estrategias establecidas por defecto.Para mas informacion remitimos al manual de gprolog y el ejemplo del pro-blema de resolucion de Sudoku. Normalmente la metodologıa mas eficientepara la definicion de los predicados que resuelven un problema con res-tricciones es generar las restricciones y despues aplicar el “etiquetado” confd labeling (“constrain and generate methodology”). El establecimiento derestricciones hace que el solver basado en restricciones reduzca los dominiosde las variables como consecuencia de las mismas. Tras lo cual, el espaciode valores sobre los que tendra que trabajar fd labeling sera normalmentemucho menor.fd all different/1Este predicado sirve para establecer la restriccion de que todas las variablestomen valores distintos entre sı. Como unico parametro recibe la lista con lasvariables FD sobre las que se quiere establecer dicha restriccion. Ejemplo:Tenemos 3 (A,B,C) variables con rango [1:3] y queremos que tomen valoresdistintos entre sı (A=B and B=C and A=C).

| ?fd_domain([A,B,C],1,3),fd_all_different([A,B,C]),fd_labeling([A,B,C]).A = 1B = 2C = 3 ? ;A = 1B = 3C = 2 ? ;A = 2B = 1C = 3 ? ;A = 2

B = 3C = 1 ? ;A = 3B = 1C = 2 ? ;A = 3B = 2C = 1

Restricciones Aritmeticas:Son expresiones que representan funciones aritmeticas compuestas por va-riables o enteros y los operadores. Se pueden utilizar los siguientes, siendoExp$ donde $ es el numero de la expresion FD que se utiliza:“+ Exp1”: El mismo valor.“- Exp1”: El valor opuesto.“Exp1 + Exp2”: La suma de las 2 expresiones.“Exp1 – Exp2”: La resta de las 2 expresiones.“Exp1 * Exp2”: El producto de las 2 expresiones.“Exp1 / Exp2”: El cociente de las 2 expresiones, solo se cumple si el restoes 0.“Exp1 ** Exp2”: La Exp1 elevada a Exp2, una de las 2 debe ser entera.“min(Exp1, Exp2)”: El mınimo de las 2 expresiones.“max(Exp1, Exp2)”: El maximo de las 2 expresiones.“dist(Exp1, Exp2)”: La distancia entre las 2 expresiones, |Exp1–Exp2|.“Exp1 // Exp2”: El cociente de la division entera de las expresiones.“Exp1 rem Exp2”: El resto de la division entera de las expresiones.“quot rem(Exp1,Exp2,R)”: Cociente de la division entera de las expresionesdevolviendo el resto en la variable R.Las siguientes restricciones pueden utilizarse con arco consistencia completao parcial, se puede utilizar la parcial para reducir el dominio de las va-riables complejas. Hay una menor propagacion de las variables en la arcoconsistencia parcial, pero aumenta la eficiencia y es mejor para las variablesaritmeticas. Cuando se utiliza una arco consistencia completa es a la inver-sa. Estos operadores se colocan entre las 2 expresiones como los operadoresaritmeticos anteriores.

#= (#=# )Las expresiones deben ser iguales.#\= (#\=#) Las expresiones deben ser diferentes.#< (#<#) La primera expresion debe ser menor ala segunda.#=< (#=<#) La primera expresion debe ser menor o igual a la segunda.#> (#>#) La primera expresion debe ser mayor a lasegunda.#>= (#>=#) La primera expresion debe ser mayor o igual a la segunda.

Ejemplos:

| ?A#\= 5, B#>=6, A#>=B+7.A = _#2(13..127@)B = _#27(6..120)

| ?A#\= 5, B#>=6, A#>=B.A = _#2(6..127@)B = _#27(6..127)

6. Un programa para resolver sudokus

% Sudoku%% (para GNU Prolog)%% version en castellano de un program prolog realizado de Jerome Cornet%

% --------------------------------------

%El objetivo de este program prolog es definir el siguiente predicado/81.%Se trata de compilar el programa y realizar una consulta que sustiya las%correspondientes variables por los valores conocidos del sudoku que queremos%resolver. La respuesta a la consulta sera la solucion del sudoku

%sudoku(A1, A2, A3, A4, A5, A6, A7, A8, A9,% B1, B2, B3, B4, B5, B6, B7, B8, B9,% C1, C2, C3, C4, C5, C6, C7, C8, C9,% D1, D2, D3, D4, D5, D6, D7, D8, D9,% E1, E2, E3, E4, E5, E6, E7, E8, E9,% F1, F2, F3, F4, F5, F6, F7, F8, F9,% G1, G2, G3, G4, G5, G6, G7, G8, G9,% H1, H2, H3, H4, H5, H6, H7, H8, H9,% I1, I2, I3, I4, I5, I6, I7, I8, I9)

% por ejemplo, si se consulta%sudoku(A1, 2, A3, A4, 6, 7, 8, 4, A9,% 4, B2, B3, B4, B5, B6, 3, 5, B9,% 5, 9, C3, C4, C5, C6, C7, C8, C9,% D1, 1, 4, D4, D5, D6, 5, D8, 8,% E1, E2, E3, 4, E5, E6, 9, 2, 7,% 6, F2, F3, F4, F5, 5, 4, 1, F9,% 9, G2, 6, 7, 4, 2, G7, 8, 5,% H1, 5, 1, 6, 8, 3, 2, H8, 4,% I1, I2, 2, I4, I5, 1, 7, 3, I9).

%Se obtiene como respuesta (en la consola)

%-------------------------%| 1 2 3 | 5 6 7 | 8 4 9 |%| 4 6 7 | 1 9 8 | 3 5 2 |%| 5 9 8 | 2 3 4 | 6 7 1 |%-------------------------%| 2 1 4 | 3 7 9 | 5 6 8 |%| 3 8 5 | 4 1 6 | 9 2 7 |%| 6 7 9 | 8 2 5 | 4 1 3 |%-------------------------%| 9 3 6 | 7 4 2 | 1 8 5 |%| 7 5 1 | 6 8 3 | 2 9 4 |%| 8 4 2 | 9 5 1 | 7 3 6 |%-------------------------

% X es una variable con dominio finito (fd) que toma valores enteros del 1 al 9.

validez(X) :- fd_domain(X, 1, 9).

%Comprueba que dos elementos cualquiera de la lista L son distinto entre sı.

todosdistintos(L) :- fd_all_different(L).%---------------------------------------% fila toma una lista de nueve terminos y los escribe%en una fila separados de tres en tres.

fila(X1, X2, X3, X4, X5, X6, X7, X8, X9) :-write(’| ’),

write(X1), write(’ ’), write(X2), write(’ ’), write(X3), write(’ | ’), write(X4),write(’ ’), write(X5), write(’ ’), write(X6), write(’ | ’), write(X7), write(’ ’),write(X8), write(’ ’), write(X9), write(’ |’), nl.%Escribe una lınea horizontal con giones.lineahorizontal :- write(’-------------------------’), nl.

% cuadrodesudoku escribe un 81 terminos en un cuadro%de 9 por 9 dividos en cuadraditos 3 por 3.

cuadrodesudoku(A1, A2, A3, A4, A5, A6, A7, A8, A9,B1, B2, B3, B4, B5, B6, B7, B8, B9,C1, C2, C3, C4, C5, C6, C7, C8, C9,

D1, D2, D3, D4, D5, D6, D7, D8, D9,E1, E2, E3, E4, E5, E6, E7, E8, E9,F1, F2, F3, F4, F5, F6, F7, F8, F9,G1, G2, G3, G4, G5, G6, G7, G8, G9,H1, H2, H3, H4, H5, H6, H7, H8, H9,I1, I2, I3, I4, I5, I6, I7, I8, I9) :-

nl,lineahorizontal,fila(A1, A2, A3, A4, A5, A6, A7, A8, A9),fila(B1, B2, B3, B4, B5, B6, B7, B8, B9),fila(C1, C2, C3, C4, C5, C6, C7, C8, C9),lineahorizontal,fila(D1, D2, D3, D4, D5, D6, D7, D8, D9),fila(E1, E2, E3, E4, E5, E6, E7, E8, E9),fila(F1, F2, F3, F4, F5, F6, F7, F8, F9),lineahorizontal,fila(G1, G2, G3, G4, G5, G6, G7, G8, G9),fila(H1, H2, H3, H4, H5, H6, H7, H8, H9),fila(I1, I2, I3, I4, I5, I6, I7, I8, I9),lineahorizontal.

%---------------------------------------

%sudoku: Primero hace que las 81 variables tengan dominio finito de enteros entre 1 y 9.%El predicado fd_labeling/1 recibe como primer parametro la lista con las variables%con dominio finito y prueba a asignar a cada variable un valor dentro de su%dominio y realiza backtracking sobre esas asignaciones permitiendo encontrar%todas las posibles soluciones. Una vez encontrada la solucion%la visualiza en un cuadrado de sudoku

sudoku(A1, A2, A3, A4, A5, A6, A7, A8, A9,B1, B2, B3, B4, B5, B6, B7, B8, B9,C1, C2, C3, C4, C5, C6, C7, C8, C9,D1, D2, D3, D4, D5, D6, D7, D8, D9,E1, E2, E3, E4, E5, E6, E7, E8, E9,F1, F2, F3, F4, F5, F6, F7, F8, F9,G1, G2, G3, G4, G5, G6, G7, G8, G9,H1, H2, H3, H4, H5, H6, H7, H8, H9,I1, I2, I3, I4, I5, I6, I7, I8, I9) :-

% tous les nombres compris entre 1 et 9validez(A1), validez(A2), validez(A3),validez(A4), validez(A5), validez(A6),validez(A7), validez(A8), validez(A9),validez(B1), validez(B2), validez(B3),validez(B4), validez(B5), validez(B6),

validez(B7), validez(B8), validez(B9),validez(C1), validez(C2), validez(C3),validez(C4), validez(C5), validez(C6),validez(C7), validez(C8), validez(C9),validez(D1), validez(D2), validez(D3),validez(D4), validez(D5), validez(D6),validez(D7), validez(D8), validez(D9),validez(E1), validez(E2), validez(E3),validez(E4), validez(E5), validez(E6),validez(E7), validez(E8), validez(E9),validez(F1), validez(F2), validez(F3),validez(F4), validez(F5), validez(F6),validez(F7), validez(F8), validez(F9),validez(G1), validez(G2), validez(G3),validez(G4), validez(G5), validez(G6),validez(G7), validez(G8), validez(G9),validez(H1), validez(H2), validez(H3),validez(H4), validez(H5), validez(H6),validez(H7), validez(H8), validez(H9),validez(I1), validez(I2), validez(I3),validez(I4), validez(I5), validez(I6),validez(I7), validez(I8), validez(I9),

% distintos en cada filatodosdistintos([A1, A2, A3, A4, A5, A6, A7, A8, A9]),todosdistintos([B1, B2, B3, B4, B5, B6, B7, B8, B9]),todosdistintos([C1, C2, C3, C4, C5, C6, C7, C8, C9]),todosdistintos([D1, D2, D3, D4, D5, D6, D7, D8, D9]),todosdistintos([E1, E2, E3, E4, E5, E6, E7, E8, E9]),todosdistintos([F1, F2, F3, F4, F5, F6, F7, F8, F9]),todosdistintos([G1, G2, G3, G4, G5, G6, G7, G8, G9]),todosdistintos([H1, H2, H3, H4, H5, H6, H7, H8, H9]),todosdistintos([I1, I2, I3, I4, I5, I6, I7, I8, I9]),

% distintos en cada subcuadrado 3x3todosdistintos([A1, A2, A3, B1, B2, B3, C1, C2, C3]),todosdistintos([D1, D2, D3, E1, E2, E3, F1, F2, F3]),todosdistintos([G1, G2, G3, H1, H2, H3, I1, I2, I3]),todosdistintos([A4, A5, A6, B4, B5, B6, C4, C5, C6]),todosdistintos([D4, D5, D6, E4, E5, E6, F4, F5, F6]),todosdistintos([G4, G5, G6, H4, H5, H6, I4, I5, I6]),todosdistintos([A7, A8, A9, B7, B8, B9, C7, C8, C9]),todosdistintos([D7, D8, D9, E7, E8, E9, F7, F8, F9]),todosdistintos([G7, G8, G9, H7, H8, H9, I7, I8, I9]),

% distintos en cada columnatodosdistintos([A1, B1, C1, D1, E1, F1, G1, H1, I1]),todosdistintos([A2, B2, C2, D2, E2, F2, G2, H2, I2]),todosdistintos([A3, B3, C3, D3, E3, F3, G3, H3, I3]),

todosdistintos([A4, B4, C4, D4, E4, F4, G4, H4, I4]),todosdistintos([A5, B5, C5, D5, E5, F5, G5, H5, I5]),todosdistintos([A6, B6, C6, D6, E6, F6, G6, H6, I6]),todosdistintos([A7, B7, C7, D7, E7, F7, G7, H7, I7]),todosdistintos([A8, B8, C8, D8, E8, F8, G8, H8, I8]),todosdistintos([A9, B9, C9, D9, E9, F9, G9, H9, I9]),

% busca todas las soluciones posiblesfd_labelingff([A1, A2, A3, A4, A5, A6, A7, A8, A9,

B1, B2, B3, B4, B5, B6, B7, B8, B9,C1, C2, C3, C4, C5, C6, C7, C8, C9,D1, D2, D3, D4, D5, D6, D7, D8, D9,E1, E2, E3, E4, E5, E6, E7, E8, E9,F1, F2, F3, F4, F5, F6, F7, F8, F9,G1, G2, G3, G4, G5, G6, G7, G8, G9,H1, H2, H3, H4, H5, H6, H7, H8, H9,I1, I2, I3, I4, I5, I6, I7, I8, I9]),

% visualiza en un cuadrado la solucion encontradacuadrodesudoku(A1, A2, A3, A4, A5, A6, A7, A8, A9,

B1, B2, B3, B4, B5, B6, B7, B8, B9,C1, C2, C3, C4, C5, C6, C7, C8, C9,D1, D2, D3, D4, D5, D6, D7, D8, D9,E1, E2, E3, E4, E5, E6, E7, E8, E9,F1, F2, F3, F4, F5, F6, F7, F8, F9,G1, G2, G3, G4, G5, G6, G7, G8, G9,H1, H2, H3, H4, H5, H6, H7, H8, H9,I1, I2, I3, I4, I5, I6, I7, I8, I9).

Practica 2: Utilizando Prolog y si preferiblemente variables con restriccionesescribe un programa para resolver el siguiente puzle de la cebra.Para la practica 2 se entregaran en dos ficheros: memoria y codigo. Se entre-gara utilizando la zona de envıo del servidor belenus (http://belenus.unirioja.es/).El codigo fuente entregado tendra todo lo necesario para que se pueda eje-cutar los diferentes procedimientos. El codigo debera estar adecuadamentecomentado.La memoria constara de las siguientes secciones:1. Introduccion (una hoja de descripcion de lo que hay que hacer desdevuestro punto de vista y no copiando el enunciado).2. Descripcion a alto nivel de lo realizado: que predicados se han definidoque problema resuelve cada uno de ellos y como se relacionan unos con otros,etc3. Codigo fuente completo con comentarios (el codigo final no deberıa sermuy largo)4. Unas cuantas consultas y los resultados obtenidos5. Conclusiones (que se ha aprendido, dificultades encontradas, comentarios

sobre gprolog, etc).Modelar y resolver el Puzle de la Cebra: cinco personas de diferente na-cionalidad viven en cinco casas de la misma calle. Estas personas tienenprofesiones distintas, y cada una de ellas tiene una bebida favorita y unanimal favorito, todos distintos. Las cinco casas estan pintadas de coloresdistintos. Se conocen los siguientes hechos:a. La persona inglesa vive en una casa roja.b. La persona espanola tiene un perro.c. La persona japonesa pinta como profesion.d. La persona italiana bebe te.e. La persona noruega vive en la primera casa.f. El dueno de la casa verde bebe cafe.g. La casa verde va a continuacion de la casa blanca.h. El escultor crıa caracoles.i. El diplomatico vive en la casa amarilla.j. Se bebe leche en la tercera casa.k. La casa de la persona noruega esta al lado de la casa azul.l. El violinista bebe zumo.m. El zorro esta en la casa de al lado del doctor.n. El caballo esta en la casa de al lado del diplomatico.o. La cebra esta en la casa verde.p. Una de las personas bebe agua.El programa debe responder a la siguiente pregunta: ¿Quien vive en cadacasa?


MODELOS CONSECUENCIA LOGICA E INCONSISTENCIA

Modelos de una proposicion

%Funciones auxiliares pertenece y concatena.%concatena(A,B,C) se verifica si C es la lista A seguida de la lista B

concatena([],L,L).concatena([X|L1], L, [X|L2]):-concatena(L1,L,L2).

%pertenece(X,L) se verifica si X esta en la lista L

pertenece(X,[X|L]).pertenece(X,[ |L]):-pertenece(X,L).

%Funciones para calcular el valor de verdad de una proposicion.%Hay dos valores de verdad.%Se definen cuatro operadores/conectores mediante sus tablas de verdad

valor de verdad(0).valor de verdad(1).

%Declaracion de los operadores logicos

:-op(610,fx,no).:-op(620,xfy, y).:-op(630,xfy,o).:-op(640,xfy,im).:-op(650,xfy,sii).funcion de verdad(no,1,0).funcion de verdad(no,0,1).funcion de verdad(y,1,1,1).funcion de verdad(y,1,0,0).funcion de verdad(y,0, ,0).funcion de verdad(o,1, ,1).funcion de verdad(o,0,1,1).funcion de verdad(o,0,0,0).funcion de verdad(im,1,1,1).funcion de verdad(im,1,0,0).funcion de verdad(im,0, ,1).funcion de verdad(sii,X,X,1).funcion de verdad(sii,1,0,0).funcion de verdad(sii,0,1,0).

%Este es un modo alternativo de definir la funcion pertenece.

comprueba pertenece(X,[X| ]):-!.

comprueba pertenece(X,[ |L]):-comprueba pertenece(X,L).

%Valor de una formula en una interpretacion.

valor(F,I,V):-comprueba pertenece((F,V),I).valor(no A, I, V):-valor(A,I,VA), funcion de verdad(no, VA,V).valor(F,I,V):-F=..[Op,A,B], valor(A,I,VA), valor(B,I,VB),funcion de verdad(Op,VA,VB,V).

%La relacion interpretaciones formula(F,L) se verifica si L es el conjunto%de todas las interpretaciones de la formula F.

interpretaciones formula(F,U) :- findall(I,interpretacion formula(I,F),U).

%findall(+T, +O, -S) Se verifica si la lista de todos los T que satisfacen el%objetivo O es la misma que la lista de resultados S.

%La relacion interpretacion formula(I,F) se verifica si I es una%interpretacion de la formula F.

interpretacion formula(I,F):-simbolos formula(F,U),interpretacion simbolos(U,I).

%simbolos formula(F,U) se verifica si U es el conjunto ordenado de los%sımbolos proposicionales de F%interpretacion simbolos(L,I) se verifica si I es una interpretacion de la%lista de atomos L

simbolos formula(F,U):-simbolos formula aux(F,U1), sort(U1,U).

%sort(+Lista, -Ordenados) Se satisface si Ordenados es la lista que%resulta al ordenar los miembros de Lista y ademas removiemdo los%elementos duplicados.

simbolos formula aux(F,[F]):- atom(F).simbolos formula aux(no F,U):-simbolos formula aux(F,U).simbolos formula aux(F,U):- F=..[ Op,A,B],simbolos formula aux(A,UA), simbolos formula aux(B,UB),concatena(UA,UB,U).

interpretacion simbolos([],[]).interpretacion simbolos([A|L],[(A,V)|IL]):- valor de verdad(V),interpretacion simbolos(L,IL).

%La relacion es modelo formula(I,F) se verifica si la interpretacion I es un%modelo de F.

es modelo formula(I,F):- valor(F,I,V), V=1.

%Los modelos principales de un formula son las interpretaciones%principales de F que son modelos de F.%modelos formula(+F,-L) se verifica si L es el conjunto de los modelos%principales de una formula F.

modelo formula(I,F):-interpretacion formula(I,F), es modelo formula(I,F).

modelos formula(F,L):-findall(I,modelo formula(I,F),L1), sort(L1,L).

%es satisfacible(+F) se verifica si F tiene un modelo.

es satisfacible(F):-interpretacion formula(I,F), es modelo formula(I,F).

%contramodelos es una interpretacion tal que I(F)=0.

contramodelo formula(I,F):- interpretacion formula(I,F),\+ es modelo formula(I,F).

%F es valida es lo mismo que F es tautologıa

es tautologia(F):- \+ contramodelo formula( I,F).

Modelos de un conjunto de proposiciones

%Simbolos comjunto(+S,?U) se verifica si U es el conjunto ordenado de lod%sımbolos proposiocinales de las proposiciones de S

simbolos conjunto(S,U):- simbolos conjunto aux(S,U1), sort(U1,U).

simbolos conjunto aux([],[]).simbolos conjunto aux([F|S],U):- simbolos formula(F,A),simbolos conjunto aux(S,B), concatena(A,B,U).

%interpretacion conjunto(?I, +S) se verifica si I es una interpretacion del%conjunto de formulas S

interpretacion conjunto(I,S):- simbolos conjunto(S,U),interpretacion simbolos(U,I).

%Interpretaciones conujunto(+S,-L) se verifica si L es el conjunto de todas%las interpretaciones principales de un conjunto de proposiciones S.

interpretaciones conjunto(S,U):-findall(I,interpretacion conjunto(I,S), U).

%La relacion es modelo conjunto(+I,+S) se verifica si la interpretacion I%es modelo del conjunto de formulas S.

es modelo conjunto(I,[]).es modelo conjunto(I,[F|S]):- es modelo formula(I,F),es modelo conjunto(I,S).

%modelo conjunto(?I,+S) se verifica si I es un modelo principal de un%conjunto de formulas S

modelo conjunto(I,S):- interpretacion conjunto(I,S),es modelo conjunto(I,S).

%modelos conjunto(S,L) se verifica si L es el conjunto de modelos del%conjunto de formulas S

modelos conjunto(S,L):- findall(I,modelo conjunto(I,S), L).

%consistente(S) se verifica si al menos tiene un modelo.

consistente(S):- modelo conjunto( I,S),!.

%inconsistente((S) se verifica si el conjunto S de proposiciones no tiene%modelos.

inconsistente(S):- \+ modelo conjunto( I,S).

%es consecuencia(S,F) se verifica si F es una consecuencia del conjunto de%formulas S

es consecuencia(S,F):- inconsistente([ no F|S]).

Resolucion

complementario(no A,A):- !.complementario(A, no A).

resolvente(C1,C2,C):- pertenece(L1,C1),complementario(L1,L2), pertenece(L2,C2),delete(C1, L1, C1P), delete(C2, L2, C2P),concatena(C1P, C2P, C3), sort(C3,C).

apply(Termino,Lista) :- Termino =..[Pred|Arg1],concatena(Arg1,Lista,Arg2),Atomo =.. [Pred|Arg2], Atomo.

maplist( ,[],[]).maplist(R,[X1|L1],[X2|L2]) :- apply(R,[X1,X2]), maplist(R,L1,L2).

refutacion(S,R):- maplist(sort,S,S1), refutacion aux(S1,R).

refutacion aux(S,R) :-pertenece([],S), !, reverse(S,R).refutacion aux(S,R) :-pertenece(C1,S), pertenece(C2,S),resolvente(C1,C2,C), \+ pertenece(C, S),

%format(’ N w resolvente de w y w n’,[C,C1,C2]),

refutacion aux([C|S],R).


Pequeno manual de lp.lpEste programa prolog puede ser utilizado para el calculo de proposiciones.Se utiliza la siguiente sintaxis

¬ ∧ ∨ → ↔no y o im sii

y el orden de la tabla indica el orden de precedencia de los conectores utili-zados.Ejemplo.La proposicion b↔ ((a ∧ c)→ (b ∨ c) le corresponde

b sii a y c im b o c

Recordamos a continuacion los principales functores del programa con ladescripcion de las propiedades que se deben satisfacer para poderse verificar.

interpretaciones formula(F,L). La relacion interpretaciones formula(F,L)se verifica si L es el conjunto de todas las interpretaciones de la formula F.Ejemplo.?- interpretaciones formula(b sii (a y c im b y c y (no a)),L). SuccessL = [[(a, 0), (b, 0), (c, 0)], [(a, 0), (b, 0), (c, 1)], [(a, 0), (b, 1), (c, 0)], [(a,0), (b, 1), (c, 1)], [(a, 1), (b, 0), (c, 0)], [(a, 1), (b, 0), (c, 1)], [(a, 1), (b, 1),(c, 0)], [(a, 1), (b, 1), (c, 1)]]

interpretacion formula(I,F). La relacion interpretacion formula(I,F) severifica si I es una interpretacion de la formula F.Ejemplo.?- interpretacion formula([(a, 0), (b, 0), (c, 0)],b sii a y c im b y c y no a).Success

simbolos formula(F,U). Se verifica si U es el conjunto ordenado de lossımbolos proposicionales de FEjemplo.?- simbolos formula(b sii a y c im b y c y no a, S).SuccessS = [a, b, c]

es modelo formula(I,F). La relacion es modelo formula(I,F) se verifica sila interpretacion I es un modelo de F.Ejemplo.?- es modelo formula([(a, 0), (b, 0), (c, 0)],b sii a y c im b y c y no a).Failure

modelos formula(+F,-L). Se verifica si L es el conjunto de los modelosprincipales de una formula F. A veces se utiliza la notacion +F para indicarque es una entrada (un termino sin variables libre) y con -L la salida.

Ejemplo.?- modelos formula(b sii (a y c im b y c y (no a)),L).SuccessL = [[(a, 0), (b, 1), (c, 0)], [(a, 0), (b, 1), (c, 1)], [(a, 1), (b, 0), (c, 1)], [(a,1), (b, 1), (c, 0)]]

es satisfacible(+F) Se verifica si F tiene un modelo.Ejemplo.?- es satisfacible(b sii (a y c im b y c y (no a))).Success

contramodelo formula(I,F). Se satisface si I es una interpretacion de laformula F tal que I(F)=0.

es tautologia(F). Se verifica si F es una tautologıa.

Existen los analogos de los funtores anteriores para conjuntos de formulas

interpretaciones conjunto(S,L). La relacion interpretaciones conjunto(S,L)se verifica si L es el conjunto de todas las interpretaciones del conjunto deformulas S. Se consideran todos los diferentes atomos que aparecen en lasdiversas formulas de S.

interpretacion conjunto(I,S). La relacion interpretacion conjunto(I,S) severifica si I es una interpretacion de alguna formula del conjunto S.

simbolos conjunto(S,U). Se verifica si U es el conjunto ordenado de lossımbolos proposicionales de las formulas de S.

es modelo conjunto(I,S). La relacion es modelo conjunto(I,F) se verificasi la interpretacion I es un modelo de cada una de las formulas del conjuntoS.

modelos conjunto(+S,-L). Se verifica si L es el conjunto de los modelosprincipales de la lista de formulas S.

consistente(S). Se verifica si al menos tiene un modelo.

inconsistente(S). Se verifica si el conjunto S de proposiciones no tienemodelos.

es consecuencia(S,F). Se verifica si F es una consecuencia del conjuntode formulas S

refutacion(+S,-R). La relacion refutacion(+S,-R) se verifica si R es unarefutacion por resolucion del conjunto de clausulas S. Una clausula se intro-duce como una lista de literales, un atomo o su negacion.Ejemplos:?- refutacion([[no p,no q],[p,q],[no p,q],[no q,p]],R). R = [[p, no q],[q,nop],[p,q],[no p,no q], [q,no q],[p,no p],[no p],[q],[p],[]]Success?- refutacion([[p,q],[-p,q],[-q,p]],R).Failure

Aplicaciones del razonamiento proposicionalVamos aplicar los procedimientos anteriores a la resolucion de problemas.

1. El problema de los veraces y los mentirosos. En una isla haydos tribus, la de los veraces (que siempre dicen la verdad) y la de losmentirosos (que siempre mienten). Un viajero se encuentra con tresislenos A, B y C y cada uno le dice una frase:

A dice “B y C son veraces sii C es veraz”

B dice “Si A y C son veraces, entonces B y C son veraces y A esmentiroso”

C dice “B es mentiroso sii A o B es veraz”

Determinar a que tribu pertenecen A, B y C.

Solucion: Representaremos por a, b y c que A, B y C son veraces. Portanto, (no a), (no b) y (no c) representan que A, B y C son menti-rosos. Para determinar las tribus calculamos los modelos del conjuntode formulas correspondientes a las tres frases. Una vez que abras elprograma lp.pl se puede utilizar el funtor modelosconjunto(S,L), quedetermina el conjunto de modelos L de un conjunto de formulas S.

modelos conjunto([a sii (b y c sii c), b sii (a y c im b y c y (no a)), csii ((no b) sii a o b)], L).

L = [[ (a, 1), (b, 1), (c, 0)]]

Por tanto, A y B son veraces y C es mentiroso.

2. Problema de los trabajos. Juan, Sergio y Carlos trabajan de pro-gramador, ingeniero y administrador (aunque no necesariamente eneste orden). Juan le debe 1000 euros al programador. La esposa deladministrador le ha prohibido a su marido pedir dinero prestado (yeste le obedece). Sergio esta soltero. Determinar el trabajo de cadauno.

Solucion: Usaremos los siguientes sımbolos proposicionales cp (Carloses programador), ci (Carlos es ingeniero), ca (Carlos es administra-dor), jp (Juan es programador), ji (Juan es ingeniero), ja (Juan esadministrador), sp (Sergio es programador), si (Sergio es ingeniero) ysa (Sergio es administrador). Calculamos los modelos del conjunto deformulas correspondiente al problema (hemos comentado el significadode cada formula). Veamos como se pueden encontar un conjunto deproposiciones que recoja la informacion anterior. Despues de le aplica,el modelosconjunto.

modelos conjunto( [

% Juan es programador, ingeniero o administrador:

jp o ji o ja,

% Sergio es programador, ingeniero o administrador:

sp o si o sa,

% Carlos es programador, ingeniero o administrador:

cp o ci o ca,

% No hay mas de un programador:

(jp y (no sp) y (no cp)) o ((no jp) y sp y (no cp)) o ((no jp) y (no sp)y cp),

% No hay mas de un ingeniero:

(ji y (no si) y (no ci)) o ((no ji ) y si y (no ci)) o ((no ji) y (no si) yci),

% No hay mas de un administrador:

(ja y (no sa) y (no ca)) o ((no ja) y sa y (no ca)) o ((no ja) y (no sa)y ca),

% Juan le debe 1000 pesetas al programador

% [Luego, Juan no es el programador]:

(no jp),

% La esposa del administrador le ha prohibido a

% su marido pedir dinero prestado (y este le obedece)

% [Luego, Juan no es el administrador]:

(no ja),

% Sergio esta soltero [Luego, no es el adminitrador]:

(no sa)], L).

Eliminado los comentarios, puedes realizar la siguiente consulta:

modelos conjunto([(jp o ji) o ja , (sp o si) o sa , (cp o ci) o ca ,(((jp y(no sp)) y (no cp)) o (((no jp) y sp) y (no cp))) o (((no jp) y (no sp))y cp), (ji y (no si) y (no ci)) o ((no ji ) y si y (no ci)) o ((no ji) y (nosi) y ci), (ja y (no sa) y (no ca)) o ((no ja) y sa y (no ca)) o ((no ja)y (no sa) y ca), (no jp), (no ja),(no sa)], L).

En la que se obtiene la siguiente respuesta:

L = [[(ca,1),(ci,0),(cp,0),(ja,0),(ji,1),(jp,0),(sa,0),(si,0),(sp,1)]]

A continuacion damos una lista de problemas para que intentes resol-verlos mediante la aplicacion de los predicados definidos en el programalp.pl

3. El problema de los cuadrados. Existe nueve sımbolos proposicio-nales que se pueden ordenar en un cuadrado:

a1 a2 a3b1 b2 b3c1 c2 c3

Se sabe que existe alguna letra tal que para todos los numeros lasformulas son verdaderas (es decir, existe una fila de formulas verda-deras). El objetivo de este ejercicio demostrar que para cada numeroexiste una letra cuya formula es verdadera (es decir, en cada columnaexiste una formula verdadera).

4. Problema del coloreado del pentagono Demostrar que es impo-sible colorear los vertices de un pentagono de rojo o azul de forma quelos vertices adyacentes tengan colores distintos.

Nota: Denota por a1 , a2 , a3 , a4 , a5 sımbolos proposicionales que seinterpretan afirmando que el vertice i es azul ai. Analogamente parael rojo puedes utilizar r1 , r2 , r3 , r4 , r5 . Construye un conjunto deproposiciones con los sımbolos anteriores cuya veracidad sea equiva-lente a que existe una coloracion de los vertices de un pentagono derojo o azul de forma que los vertices adyacentes tengan colores distin-tos. Prueba ahora que ese conjunto de proposiciones en inconsistente(contradictorio). Utiliza el functor inconsistente del programa lp.pl

5. Problema del coloreado del pentagono (con tres colores). De-mostrar que es posible colorear los vertices de un pentagono de rojo,azul o negro de forma que los vertices adyacentes tengan colores dis-tintos.

6. Problema del palomar. Cuatro palomas comparten tres huecos yno hay mas de dos palomas en cada hueco. Demostrar que dos palomastienen que estar en el mismo hueco.

7. El problema de las 4 reinas. Calcular las formas de colocar 4 reinasen un tablero de 4× 4 de forma que no haya mas de una reina en cadafila, columna o diagonal.

8. El problema de hermano mentiroso. Trata de resolver el siguien-te problema mediante la creacion de un conjunto de proposiciones yencontrando modelos para dicho conjunto.

Los tres hermanos Lezaum tienen la curiosa costumbre de que cadavez que se les hace una pregunta, dos dicen la verdad y el otro miente.Cuando les pregunte quien habıa nacido primero me contestaron:

Andoni: “Benito nacio en primer lugar”.

Benito: “Yo no soy el mayor”.

Carlos:“Andoni nacio el primero”

¿Cual es el mayor de ellos?

Notas: Se supone que dos hermanos no pueden nacer simultaneamente.Para la construccion de las proposiciones puedes utilizar los siguientesatomos:

-a: Andoni dice la verdad

-b: Benito dice la verdad

-c: Carlos dice la verdad

-am: Andoni es el mayor

-bm: Benito es el mayor

-cm: Carlos es el mayor

9. El robo del libro de recetas de la Duquesa. Trata de resolverel siguiente problema1 mediante la creacion de un conjunto de propo-siciones y encontrando modelos para dicho conjunto. La solucion sedebe encontrar mediante el uso Prolog.

“-Aquı estan los moldes - dijo el Rey - ya puedes hacerme los pasteles.

-¿Sin la receta?- pregunto la Reina.

-Hazlos como siempre- grito el Rey con impaciencia-, la ultima vezestaban riquısimos.

-No puedo- dijo la Reina-. La receta esta en el libro de cocina y me loacaban de robar.

El principal sospechoso era la Cocinera y el libro fue encontrado enefecto en la cocina de la Duquesa. Los unicos posibles sospechosos eranla Cocinera, la Duquesa y el Gato de Cheshire.

-¡ Lo robo el gato de Cheshire! - dijo la Duquesa en el juicio-.

-Sı, yo lo robe - dijo el Gato con una sonrisa-.

-¡Yo no lo robe! -dijo la Cocinera.

El ladron habıa mentido y al menos uno de los otros dos habıa dichola verdad.

¿Quien robo el libro a la cocinera?”.

Nota: Para la construccion de las proposiciones asociadas a la infor-macion anterior puedes utilizar los siguientes atomos

-g: el gato dice la verdad -c: la cocinera dice la verdad-d: la duquesa dice la verdad -gl: el gato es el ladron-cl: la cocinera es la ladrona -dl: la duquesa es la ladrona

1Del libro “Alicia en el pais de las adivinanzas”, de Raymond Smullyan, Ed. Catedra,1982.


DEDUCCION NATURAL CON ((ADN)). PROPOSICIONES

ADN significa Asistente para la Deduccion Natural. Es una herramien-ta disenada por F. Llorens y S. Mira en la Universidad de Alicante,que han pretendido fabricar ((un instrumento didactico que ayude a losestudiantes a escribir formulas logicas bien formadas y a realizar de-ducciones correctamente)). Sirve para trabajar con proposiciones y conpredicados. En esta primera practica tomaremos contacto con ADN ylo usaremos con proposiciones. En la siguiente practica continuaremoscon ADN incorporando predicados. Una limitacion de ADN es queno permite almacenar lo ya probado para que sea utilizado en nuevasdemostraciones, de modo que todas deben hacerse ıntegramente a par-tir de las reglas primitivas, pudiendo algunas exceder el tamano de lapizarra.

1.—ADN incorpora su propia AYUDA, que debe ser leıda al iniciar lapractica y acudir a ella cuando sea necesario a medida que se va tra-bajando. Es conveniente consultar en la AYUDA la forma de escribirlos conectores logicos y los nombres que reciben las reglas primitivas.En la ayuda hay ejercicios resueltos que se pueden estudiar antes deabordar los que aquı se proponen.

2.—Escritura de proposiciones y visualizacion de arboles. Ir a la barrade formulas ((Objetivo)), escribir una formula y pulsar ((intro)). Si laformula no esta bien formada aparece la explicacion del error abajoa la derecha (en la version 2.1, a la derecha) y la formula se puedereparar. Si la formula esta bien formada se puede visualizar su arbolsintactico. Ejemplos (cada estudiante puede crearse otros):

P¬ ∧Q, P ∧Q ∨R, P ∧ ¬Q, P ∧ (¬Q).

(P → ¬(Q ∧R)) ∨ ¬R ∧ (P → Q).

3.—Construir deducciones mediante las reglas de deduccion natural.

a)P → (Q→ R)(P ∧Q)→ R

b)(P ∧Q)→ R

P → (Q→ R)c)

P

¬¬P(RI¬¬)

d)P ∨Q¬P

Q

(RE∨) e)

¬P1 ∨ ¬Q1P → P1Q→ Q1¬P ∨ ¬Q

f)P ∨Q1¬P ∨Q2Q1 ∨Q2

(RR)

g)P → Q

¬(P ∧ ¬Q

4.—Las dos equivalencias de De Morgan dan dan lugar a cuatro reglas(dos a dos recıprocas), a saber:

a) ¬P ∧ ¬Q ` ¬(P ∨Q)

b) ¬(P ∧Q) ` ¬P ∨ ¬Q

c) ¬(P ∨Q) ` ¬P ∧ ¬Q

d) ¬P ∨ ¬Q ` ¬(P ∧Q)

Demostrad cada una de ellas.

5.—Tambien se pueden demostrar las tautologıas, como si fueran reglaspero sin premisas. Por ejemplo, los tres axiomas de Lukasiewicz:

(L1) P → (Q→ P )

(L2) (P → (Q→ R))→ ((P → Q)→ (P → R))

(L3) (¬P → ¬Q)→ (Q→ P )

Notese que a cada una de estas proposiciones le podemos asociar unaregla de la siguiente forma:

(RL1)P

Q→ P(RL2)

P → (Q→ R)(P → Q)→ (P → R)

(RL3)

¬P → ¬Q

Q→ P

Comparese la demostracion de una de estas reglas con la de la corres-pondiente tautologıa.

6.—Terminamos con un ejemplo de tautologıa a demostrar cuyo co-nector raız no es el condicional: P ∨ ¬(Q ∧ P ).


DEDUCCION NATURAL CON ((ADN)). PREDICADOS

1.— Las expresiones P (x), R(x, y), etc. son siempre formulas atomicas.Sin embargo ADN no permite introducir formulas con variables libres.En los apuntes de teorıa se suele utilizar expresiones del tipo (∀x)P (x) ,no obstante, ADN prefiere la expresion ∀xP (x) .

2.—Escritura de proposiciones y visualizacion de arboles. Si la formulaesta bien formada se puede visualizar su arbol sintactico. En otro casohay que repararla hasta que se pueda visualizar su arbol sintactico:

Mal formada : ∀(x)(Q(x)→ ∃y(P (y) ∧ (R(x, y)

Bien formada : ∀x(Q(x)→ ∃y(P (y) ∧ (R(x, y)))

3.—Demostrar mediante las reglas de deduccion natural los silogismossiguientes:

a)∀x(P (x)→ Q(x))∀x(R(x)→ ¬Q(x))∀x(R(x)→ ¬P (x))

b)∀x(P (x)→ ¬Q(x))∃x(R(x) ∧Q(x))∃x(R(x) ∧ ¬P (x))

4.—Las dos equivalencias de De Morgan cuantificadas dan cuatro re-glas (dos a dos recıprocas), por ejemplo, ¬∀xP (x) ` ∃x¬P (x), etc..Demostrad la anterior regla.

5.—Tambien se pueden demostrar las tautologıas, como si fueran reglaspero no hay premisas. Por ejemplo:

(∀x(P → Q(x))→ (P → ∀xQ(x))

y tambien su recıproco.

Notese que a la formula anterior le podemos asociar la regla:

∀x(P → Q(x))P → ∀xQ(x)

y analogamente con la formula recıproca. Comparese la demostracionde estas reglas con las de las correspondientes leyes logicas.

6.— En la formulas pueden intervenir mas variables como en caso delas siguientes que se deben demostrar mediante la aplicacion ADN

a)∃x(P1(x) ∧ ∀y(P2(y)→ P3(x, y)))∀x∀y(P1(x) ∧ P4(y)→ ¬P3(x, y))

∀x(P2(x)→ ¬P4(x))

b) Probad la siguiente ley logica

¬(¬∃x¬P (x) ∧ ¬∀xP (x))

Documents

practicas