Universit e de Tunis El Manar
Facult e des Sciences
economique et de Gestion de
Tunis
T.D. Logique math ematique
La logique des pr edicats ou logique de premier ordre CP1
2015-2016
Section : 2LFIG
Exercice 1
Si p(x) et q(x) repr esentent respectivement x est un nombre rationnel et x est un nombre
r eel, symboliser les phrases suivantes :
1. chaque nombre rationnel est un nombre r eel.
2. certains nombres r eels sont des nombres rationnels
3. chaque r eel nest pas n ecessairement un rationnel
Exercice 2
Soit I linterpr etation suivante : D = {1, 2}, a = 1, f (1) = 2, f (2) = 1, p(1) = F , p(2) = V ,
q(1, 1) = V , q(2, 1) = F ,q(2, 2) = V ,q(1, 2) = V
Publicité
Evaluer les formules suivantes dans linterpr etation
1 : x(p(f (x)) ' q(x, f (a)))
2 : x(p(x) ' q(x, a))
3 : xy(p(x) ' q(x, y))
Exercice 3
Transformer les formules suivantes en forme normale pr enexe :
1 : x(p(x) yq(x, y))
2 : x( (y p(x, y)) (zq(z) r(x)))
3 : xy(z p(x, y, z) ' (u q(x, u) v q(y, v)))
Exercice 4
Mettre sous forme normale de Skolem les formules suivantes :
1 : (x p(x) yz q(y, z))
2 : x( (E(x, 0) y(E(y, g(x)) ' z(E(z, g(x)) E(y, z))))
3 : (x p(x) y p(y))
1
Exercice 5
Soient 1 = {x/a, y/f (z), z/y}, 2 = {x/b, y/z, z/g(x)}
Publicité
D eterminer 1 2 et 2 1
Exercice 6
Etudier luniabilit e de dans chacun des cas suivants :
1 = {q(f (a), g(x)), q(y, y)}
2 = {q(a), q(b)}
3 = {q(a, x), q(a, a)}
4 = {q(a, x, f (x)), q(a, y, y)}
5 = {q(x, y, z), q(u, h(u, v), u)}
6 = {p(x, y), p(y, f (z))}
7 = {p(a, y, f (y)), p(z, z, u)}
8 = {p(x, g(x)), p(y, y)}
9 = {p(x, g(x), y), p(z, u, g(u))}
10 = {p(a, x, f (g(y))), p(z, f (z), f (u))}
11 = {p(x, f (x), g(f (x), x)), p(z, f (f (a)), g(f (g(a, z)), v))}
Exercice 7
D eterminer si les clauses suivantes ont des facteurs, si oui les citer.
1. p(x) ( q(y) ( p(f (x))
Publicité
2. p(x) ( p(a) ( q(f (x)) ( q(f (a))
3. p(x, y) ( p(a, f (a))
4. p(a) ( p(b) ( p(x)
5. p(x) ( p(f (y)) ( q(x, y)
Exercice 8
Trouver tout les r esolvants possibles des paires de clauses suivantes :
C1 : p(x) ( q(x, b)
C2 : p(x) ( q(x, x)
C3 : p(x, y, u) ( p(y, z, v) ( p(x, v, w) ( p(u, z, w) D3 : p(g(x, y), x, y)
D4 : p(w, h(x, x), w)
C4 : p(v, z, v) ( p(w, z, w)
D5 : p(a) ( p(y)
C5 : p(x) ( p(y)
D1 : p(a) ( q(a, b)
D2 : q(a, f (a))
2
Exercice 9
Publicité
Montrer en utilisant le principe de r esolution que est cons equence logique de { 1, ..., n} dans
chacun des cas suivants :
1. : u q(u)
2. : x(p(x) p(f (f (x)))) 1 : x(p(x) r(f (x)))
3. : z q(z)
4. : x s(x)
1 : xy p(x, y)
2 : z1z2 (p(z1, z2) q(z1))
2 : x(r(x) p(f (x)))
2 : (xy p(x, y) z q(z))
1 : yx p(x, y)
1 : xy(p(x, y) ( p(y, x)) 2 : x(p(x, x) (q(x) ( r(x)))
3 : z(q(z) s(z))
4 : u(r(u) q(u))
3