PDF de programación - Tema DA-7: Formalización en Prolog de la lógica proposicional

Razonamiento Automático

Curso 2002–03

Tema DA-7: Formalización en

Prolog de la lógica proposicional

José A. Alonso Jiménez

Miguel A. Gutiérrez Naranjo

Dpto. de Ciencias de la Computación e Inteligencia Artificial

Universidad de Sevilla

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.1

Sintaxis de la lógica proposicional
x Alfabeto proposicional:
u símbolos proposicionales.
u conectivas lógicas: ¬ (negación), ∧ (conjunción), ∨
(disyunción), → (condicional), ↔ (equivalencia).
u símbolos auxiliares: “(“ y “)”.
x Fórmulas proposicionales:
u símbolos proposicionales
u ¬F , (F ∧ G), (F ∨ G), (F → G), (F ↔ G)

.x Eliminación de paréntesis:
u Eliminación de paréntesis externos.
u Precedencia: ¬, ∧, ∨ →, ↔
u Asociatividad: ∧ y ∨ asocian por la derecha
x Sintaxis en Prolog
Usual ¬ ∧ ∨ → ↔
Prolog - & v => <=>
x Declaración de operadores:

-).
:- op(610, fy,
:- op(620, xfy, &).
:- op(630, xfy, v).
:- op(640, xfy, =>).
:- op(650, xfy, <=>).

% negación
% conjunción
% disyunción
% condicional
% equivalencia

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.2

Valores y funciones de verdad
x Valores de verdad:
u 1: verdadero y 0: falso
x Def. de valor de verdad:
u valor de verdad(?V) si V es un valor de verdad.

valor_de_verdad(0).
valor_de_verdad(1).

x Funciones de verdad:

i ¬i
1 0
0 1

i
j
1 1
1 0
0 1
0 0

i ∧ j i ∨ j i → j i ↔ j
1
0
0
0

1
0
1
1

1
1
1
0

1
0
0
1

x Def. de funcion de verdad:
u funcion de verdad(+Op, +V1, +V2, -V) si Op(V1,V2)=V.

0, 0, 0) :- !.
_, _, 1).
1, 1, 1) :- !.
_, _, 0).

funcion_de_verdad(v,
funcion_de_verdad(v,
funcion_de_verdad(&,
funcion_de_verdad(&,
funcion_de_verdad(=>, 1, 0, 0) :- !.
funcion_de_verdad(=>, _, _, 1).
funcion_de_verdad(<=>, X, X, 1) :- !.
funcion_de_verdad(<=>, _, _, 0).

u funcion de verdad(+Op, +V1, -V) si Op(V1)) = V

.

funcion_de_verdad(-, 1, 0).
funcion_de_verdad(-, 0, 1).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.3

Valor de una fórmula
x Representación de las intepretaciones
u Listas de pares de variables y valores de verdad
u Ejemplo: [(p,1),(r,0),(u,1)]
x Def. del valor de una fórmula en una inter-
u valor(+F, +I, -V) se verifica si el valor de la fórmula
u Ejemplos:

F en la interpretación I es V

pretación

?- valor((p v q) & (-q v r),[(p,1),(q,0),(r,1)],V).
V = 1
?- valor((p v q) & (-q v r),[(p,0),(q,0),(r,1)],V).
V = 0

u Def. de valor:

valor(F, I, V) :-

memberchk((F,V), I).

valor(-A, I, V) :-

valor(A, I, VA),
funcion_de_verdad(-, 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).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.4

Interpretaciones de una fórmula
x I interpretación principal de F syss I es una

aplicación del conjunto de los símbolos proposi-
cionales de F en el conjunto de los valores de
verdad.

x Cálculo de las interpretaciones principales:
u interpretaciones formula(+F,-L) se verifica si L es el

conjunto de las interpretaciones principales de la
fórmula F.

u Ejemplo

?- interpretaciones_formula((p v q) & (-q v r),L).
L = [[ (p, 0), (q, 0), (r, 0)],
(r, 1)],
(r, 0)],
(r, 1)],
(r, 0)],
(r, 1)],
(r, 0)],
(r, 1)]]

[ (p, 0), (q, 0),
[ (p, 0), (q, 1),
[ (p, 0), (q, 1),
[ (p, 1), (q, 0),
[ (p, 1), (q, 0),
[ (p, 1), (q, 1),
[ (p, 1), (q, 1),

u Def. de interpretaciones formula:

interpretaciones_formula(F,U) :-

findall(I,interpretacion_formula(I,F),U).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.5

Interpretaciones de una fórmula
x Interpretación de una fórmula:
u interpretacion formula(?I,+F) se verifica si I es una
u Ejemplo:

interpretación de la fórmula F.

?- interpretacion_formula(I,(p v q) & (-q v r)).
I = [ (p, 0), (q, 0), (r, 0)] ;
I = [ (p, 0), (q, 0), (r, 1)] ;
I = [ (p, 0), (q, 1), (r, 0)] ;
I = [ (p, 0), (q, 1), (r, 1)] ;
I = [ (p, 1), (q, 0), (r, 0)] ;
I = [ (p, 1), (q, 0), (r, 1)] ;
I = [ (p, 1), (q, 1), (r, 0)] ;
I = [ (p, 1), (q, 1), (r, 1)] ;
No

u Def. de interpretacion formula:

interpretacion_formula(I,F) :-

simbolos_formula(F,U),
interpretacion_simbolos(U,I).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.6

Interpretaciones de una fórmula
x Símbolos de una fórmula
u simbolos formula(+F,?U) se verifica si U es el conjunto

ordenado de los símbolos proposicionales de la fórmula
F.

u Ejemplo:

?- simbolos_formula((p v q) & (-q v r), U).
U = [p, q, r]

u Def. de simbolo formula

simbolos_formula(F,U) :-

simbolos_formula_aux(F,U1),
sort(U1,U).

simbolos_formula_aux(F,[F]) :-

atom(F).

simbolos_formula_aux(-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),
union(UA,UB,U).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.7

Interpretaciones de una fórmula
x Interpretación de una lista de símbolos:
u interpretacion simbolos(+L,-I) se verifica si I es una

interpretación de la lista de símbolos proposicionales
L.

u Ejemplo:

?- interpretacion_simbolos([p,q,r],I).
I = [ (p, 0), (q, 0), (r, 0)] ;
I = [ (p, 0), (q, 0), (r, 1)] ;
I = [ (p, 0), (q, 1), (r, 0)] ;
I = [ (p, 0), (q, 1), (r, 1)] ;
I = [ (p, 1), (q, 0), (r, 0)] ;
I = [ (p, 1), (q, 0), (r, 1)] ;
I = [ (p, 1), (q, 1), (r, 0)] ;
I = [ (p, 1), (q, 1), (r, 1)] ;
No

u Def. de interpretacion simbolos

interpretacion_simbolos([], []).
interpretacion_simbolos([A|L],[(A,V)|IL]) :-

valor_de_verdad(V),
interpretacion_simbolos(L, IL).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.8

Modelo de una fórmula
x La interpretación I es un modelo de la fórmula
x Comprobación de modelo de una fórmula:
u es modelo formula(+I,+F)
u Ejemplos:

se verifica si
pretación I es un modelo de la fórmula F.

F si el valor de F en I es verdadero.

la inter-

?- es_modelo_formula([(p,1),(q,0),(r,1)],
(p v q) & (-q v r)).

Yes
?- es_modelo_formula([(p,0),(q,0),(r,1)],
(p v q) & (-q v r)).

No

u Def. de es modelo formula:

es_modelo_formula(I,F) :-

valor(F,I,V),
V = 1.

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.9

Cálculo de los modelos de una fórmula
x Cálculo de los modelos principales de una
u modelo formula(?I,+F) se verifica si I es un modelo
u Ejemplo:

principal de la fórmula F.

fórmula:

?- modelo_formula(I,(p v q) & (-q v r)).
I = [ (p, 0), (q, 1), (r, 1)] ;
I = [ (p, 1), (q, 0), (r, 0)] ;
I = [ (p, 1), (q, 0), (r, 1)] ;
I = [ (p, 1), (q, 1), (r, 1)] ;
No

u Def. de modelo formula:

modelo_formula(I,F) :-

interpretacion_formula(I,F),
es_modelo_formula(I,F).

u modelos formula(+F,-L) se verifica si L es el conjunto
u Ejemplo:

de los modelos principales de la fórmula F.

?- modelos_formula((p v q) & (-q v r),L).
L = [[ (p, 0), (q, 1), (r, 1)],
(r, 0)],
(r, 1)],
(r, 1)]]

[ (p, 1), (q, 0),
[ (p, 1), (q, 0),
[ (p, 1), (q, 1),

u Def. de modelos formula

modelos_formula(F,L) :-

findall(I,modelo_formula(I,F),L).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.10

insatisfacible si no lo tiene.

Satisfacibilidad
x Una fórmula es satisfacible si tiene modelo e
x Comprobación de satisfacibilidad:
u es satisfacible(+F) se verifica si la fórmula F es satis-
u Ejemplos:

facible.

?- es_satisfacible((p v q) & (-q v r)).
Yes
?- es_satisfacible((p & q) & (p => r) & (q => -r)).
No

u Def. de es satisfacible:

es_satisfacible(F) :-

interpretacion_formula(I,F),
es_modelo_formula(I,F).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.11

Contramodelo de una fórmula
x Un contramodelo principal de F es una inter-

pretación principal de F que no es modelo de
F .

x Cálculo de contramodelos:
u contramodelo formula(?I,+F) se verifica si I es un con-
u Ejemplos:

tramodelo principal de la fórmula F.

?- contramodelo_formula(I, p <=> q).
I = [ (p, 0), (q, 1)] ;
I = [ (p, 1), (q, 0)] ;
No
?- contramodelo_formula(I, p => p).
No

u Def. de contramodelo formula:

contramodelo_formula(I,F) :-

interpretacion_formula(I,F),
not(es_modelo_formula(I,F)).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.12

pretaciones son modelos de F .

Validez. Tautologías
x F es válida (o tautología) si todas las inter-
x Comprobación de tautologías:
u es tautologia(+F) se verifica si la fórmula F es una
u Ejemplos:

tautología.

?- es_tautologia((p => q) v (q => p)).
Yes
?- es_tautologia(p => q).
No

u Def. de es tautologia:

es_tautologia(F) :-

not(contramodelo_formula(_I,F)).

u Definición alternativa:

es_tautologia_alt(F) :-

not(es_satisfacible(-F)).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.13

Interpretaciones de conjuntos
x Una interpretación principal de un conjunto

de fórmulas es una aplicación del conjunto de
sus símbolos proposicionales en el conjunto de
los valores de verdad.

x Cálculo de las interpretaciones principales de
u interpretaciones conjunto(+S,-L) se verifica si L es el

un conjunto de fórmulas:

conjunto de las interpretaciones principales del con-
junto S.

u Ejemplo:

?- interpretaciones_conjunto([p => q, q=> r],U).
U = [[ (p, 0), (q, 0), (r, 0)],
(r, 1)],
(r, 0)],
(r, 1)],
(r, 0)],
(r, 1)],
(r, 0)],
(r, 1)]]

[ (p, 0), (q, 0),
[ (p, 0), (q, 1),
[ (p, 0), (q, 1),
[ (p, 1), (q, 0),
[ (p, 1), (q, 0),
[ (p, 1), (q, 1),
[ (p, 1), (q, 1),

u Def. de interpretaciones conjunto:

interpretaciones_conjunto(S,U) :-

findall(I,interpretacion_conjunto(I,S),U).

RA 2002–03

CcIa

Formalización en Prolog de la lógica proposicional DA-7.14

Interpretaciones de conjuntos
u interpretacion conjunto(?I,+S) se verifica si I es una
u Ejemplo:

interpretación del conjunto de fórmulas S.

?- interpretacion_conjunto(I,[p => q, q=> r]).
I = [ (p, 0), (q, 0), (r, 0)] ;
I = [ (p, 0), (q, 0), (r, 1)] ;
I = [ (p, 0), (q, 1), (r, 0)] ;
I = [ (p, 0), (q, 1), (r, 1)] ;
I = [ (p, 1), (q, 0), (r, 0)]