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

Programación lógica

Curso 2002–03

Tema 4: Formalización en

Prolog de la lógica proposicional

José A. Alonso Jiménez

[email protected]
http://www.cs.us.es/∼jalonso

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

Universidad de Sevilla

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.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

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.2

Sintaxis de la lógica proposicional
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

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.3

Valores 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).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.4

i ¬i
1 0
0 1

j
i
1 1
1 0
0 1
0 0

1
1
1
0

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

1
0
1
1

1
0
0
1

Funciones de verdad
x Funciones de verdad:

u función de verdad(+Op, +V1, +V2, -V) si Op(V1,V2)=V.

función de verdad(+Op, +V1, -V) si Op(V1)) = V

.

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

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

función_de_verdad(-, 1, 0).
función_de_verdad(-, 0, 1).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.5

Valor de una fórmula
x Representación de las interpretaciones
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 interpretación
u valor(+F, +I, -V) se verifica si el valor de la fórmula F en la interpretación I es V
u Ejemplos:

?- 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

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.6

Valor de una fórmula
u Def. de valor:

valor(F, I, V) :-

memberchk((F,V), I).

valor(-A, I, V) :-

valor(A, I, VA),
función_de_verdad(-, VA, V).

valor(F, I, V) :-

functor(F,Op,2), arg(1,F,A), arg(2,F,B),
valor(A, I, VA),
valor(B, I, VB),
función_de_verdad(Op, VA, VB, V).

% F =..[Op,A,B],

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.7

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

de los símbolos proposicionales de F en el conjunto de los valores de
verdad.

x Cálculo de las interpretaciones principales:
u interpretaciones fórmula(+F,-L) se verifica si L es el conjunto de las interpretaciones
u Ejemplo

principales de la fórmula F.

?- interpretaciones_fórmula((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 fórmula:

interpretaciones_fórmula(F,U) :-

findall(I,interpretación_fórmula(I,F),U).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.8

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

?- interpretación_fórmula(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 interpretación fórmula:

interpretación_fórmula(I,F) :-

símbolos_fórmula(F,U),
interpretación_símbolos(U,I).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.9

Interpretaciones de una fórmula
x Símbolos de una fórmula
u símbolos fórmula(+F,?U) se verifica si U es el conjunto ordenado de los símbolos
u Ejemplo:

proposicionales de la fórmula F.

?- símbolos_fórmula((p v q) & (-q v r), U).
U = [p, q, r]

u Def. de símbolo fórmula

símbolos_fórmula(F,U) :-

símbolos_fórmula_aux(F,U1),
sort(U1,U).

símbolos_fórmula_aux(F,[F]) :-

atom(F).

símbolos_fórmula_aux(-F,U) :-
símbolos_fórmula_aux(F,U).

símbolos_fórmula_aux(F,U) :-

arg(1,F,A), arg(2,F,B),
símbolos_fórmula_aux(A,UA),
símbolos_fórmula_aux(B,UB),
union(UA,UB,U).

% F =..[_Op,A,B],

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.10

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

símbolos proposicionales L.

?- interpretación_símbolos([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 interpretación símbolos

interpretación_símbolos([],[]).
interpretación_símbolos([A|L],[(A,V)|IL]) :-

valor_de_verdad(V),
interpretación_símbolos(L,IL).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.11

es verdadero.

Modelo de una fórmula
x La interpretación I es un modelo de la fórmula F si el valor de F en I
x Comprobación de modelo de una fórmula:
u es modelo fórmula(+I,+F) se verifica si la interpretación I es un modelo de la fórmula
u Ejemplos:

F.

?- es_modelo_fórmula([(p,1),(q,0),(r,1)], (p v q) & (-q v r)).
Yes
?- es_modelo_fórmula([(p,0),(q,0),(r,1)], (p v q) & (-q v r)).
No

u Def. de es modelo fórmula:

es_modelo_fórmula(I,F) :-

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

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.12

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

?- modelo_fórmula(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 fórmula:

modelo_fórmula(I,F) :-

interpretación_fórmula(I,F),
es_modelo_fórmula(I,F).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.13

Cálculo de los modelos de una fórmula
u modelos fórmula(+F,-L) se verifica si L es el conjunto de los modelos principales de
u Ejemplo:

la fórmula F.

?- modelos_fórmula((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 fórmula

modelos_fórmula(F,L) :-

findall(I,modelo_fórmula(I,F),L).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.14

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

?- 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) :-

interpretación_fórmula(I,F),
es_modelo_fórmula(I,F).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.15

que no es modelo de F .

Contramodelo de una fórmula
x Un contramodelo principal de F es una interpretación principal de F
x Cálculo de contramodelos:
u contramodelo fórmula(?I,+F) se verifica si I es un contramodelo principal de la
u Ejemplos:

fórmula F.

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

u Def. de contramodelo fórmula:

contramodelo_fórmula(I,F) :-

interpretación_fórmula(I,F),
\+ es_modelo_fórmula(I,F).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.16

F .

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

?- es_tautología((p => q) v (q => p)).
Yes
?- es_tautología(p => q).
No

u Def. de es tautología:

es_tautología(F) :-

\+ contramodelo_fórmula(_I,F).

u Definición alternativa:

es_tautología_alt(F) :-

\+ es_satisfacible(-F).

PL 2002–03

CcIa

Formalización en Prolog de la lógica proposicional

4.17

Interpretaciones de conjuntos
x Una interpretación principal de un conjunto de fórmulas es una apli-

cación del conjunto de sus símbolos proposicionales en el conjunto de
los valores de verdad.

x Cálculo de las interpretaciones principales de un conjunto de fórmulas:
u interpretaciones conjunto(+S,-L) se verifica si L es el conjunto de las interpreta-
u Ejemplo:

ciones principales del conjunto S.

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

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

u Def. de interpretacion