2016 chapitre 6 logique .pdf



Nom original: -2016_chapitre_6_logique.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.13, et a été envoyé sur fichier-pdf.fr le 27/11/2016 à 11:41, depuis l'adresse IP 90.104.x.x. La présente page de téléchargement du fichier a été vue 306 fois.
Taille du document: 145 Ko (5 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)










Aperçu du document


Logique

1
1.1

Syntaxe des formules logiques
proposition

En math´ematiques on manipule des propositions, phrases non ambigu¨es, auxquelles on peut attribuer une valeur de v´erit´e vrai
ou faux.
Dans la logique des propositions on ne s’int´eresse qu’aux relations logiques entre les propositions, ind´ependamment du sens de
ces propositions. Ainsi les propositions sont repr´esent´ees par des variables appel´ees variables propositionnelles

1.2


efinition des formules logiques

V est un ensemble au plus d´enombrable (i.e. fini ou en bijection avec N) de variables propositionnelles.
V et F sont deux constantes.
On d´efinit par induction structurelle les formules logiques.
B: la base
V, F sont des formules logiques
∀x ∈ V, x est une formule logique
Les constructeurs :
au nombre de trois,
si f , g sont des formules logiques alors
(¬f ), (f ∧ g), (f ∨ g) sont des formules logiques
¬ est un constructeur d’arit´e 1, ∧ et ∨ sont des constructeurs d’arit´e 2.
Ils sont aussi appel´es connecteurs logiques. ¬ est la n´egation, ∧ la conjonction, ∨ la disjonction.
Ainsi, toute formule logique est construite en appliquant un nombre fini de fois les r`egles ci-dessus.
Remarque : il existe d’autres connecteurs logiques; par exemple ⇒, ⇔, ⊕ mais nous ne les pr´esenterons pas dans ce cours.

1.3

conventions d’´
ecriture

Les parenth`eses sont des ´el´ements de la syntaxe des formules logiques, elles sont n´ecessaires pour qu’il n’y ait pas d’ambigu¨ıt´e.
On d´ecide souvent de ne pas ´ecrire les parenth`eses les plus externes. On convient d’un ordre de priorit´e pour all´eger l’´ecriture :
la n´egation est prioritaire sur les deux autres connecteurs.
Par exemple on ´ecrira ¬x ∧ y `
a la place de ((¬x) ∧ y).

1

1.4

repr´
esentation arborescente des formules

La syntaxe des formules induit une ´ecriture parenth´es´ee lourde et encombrante. Il y a une autre repr´esentation possible, sous
forme d’arbre.
Notons L l’ensemble des formules logiques, A l’ensemble des arbres binaires o`
u les feuilles sont ´etiquet´ees par V ∪ {V, F } et les
noeuds internes par {¬, ∧, ∨}.
On d´efinit une application de L dans A par induction structurelle :
1. les formules (dites atomiques) V, F, x sont repr´esent´ees par des feuilles (arbres r´eduits `a leur racine) d’´etiquettes respectives
V, F, x.
¬
2. la formule (¬f ) (o`
u f est une formule) est repr´esent´ee par l’arbre



o`
u a(f ) est l’arbre repr´esentant





a(f )

la formule f .

3. la formule (f ∧ g) (o`
u f et g sont deux formules) est repr´esent´ee par l’arbre



o`
u a(f ) est l’arbre



a(f )

a(g)

repr´esentant la formule f , a(g) celui repr´esentant g.

4. la formule (f ∨ g) (o`
u f et g sont deux formules) est repr´esent´ee par l’arbre


a(f )

o`
u a(f ) est l’arbre


a(g)

repr´esentant la formule f , a(g) celui repr´esentant g.
Exercice : quel est l’arbre repr´esentant la formule ((x ∧ (¬y)) ∨ (x ∧ z)) ?
On reconstitue la formule `
a partir de l’arbre en r´ealisant un parcours infixe.

2
2.1


emantique des formules logiques

efinition

Un contexte ou distribution de v´erit´e sur un ensemble de variables V est une application v de V dans {0, 1}. Si |V| = n alors il
y a 2n distributions de v´erit´e possibles.
Soit v une distribution de v´erit´e sur V. L l’ensemble des formules logiques qui s’expriment sur l’ensemble V .
On d´efinit r´ecursivement l’application ´evaluation associ´ee `a v, Ev : L → {0, 1}
Ev (V ) = 1
Ev (F ) = 0
Ev (x) = v(x) pour x ∈ V
Ev (¬f ) = 1 − Ev (f )
Ev (f ∧ g) = min (Ev (f ) , Ev (g)) (ou Ev (f ) .Ev (g))
Ev (f ∨ g) = max (Ev (f ) , Ev (g)) ( ou Ev (f ) + Ev (g) − Ev (f ) .Ev (g))

2.2


esultats possibles

Une tautologie est une formule qui est ´evalu´ee `
a 1 quelle que soit la distribution de v´erit´e.
Exemple: f = x ∨ ¬x. Soit v une distribution de v´erit´e. Ev (f ) = max (Ev (x) , 1 − Ev (x)) = max (v(x), 1 − v(x)) = 1. f est une
tautologie.
Une formule f est satisfiable (ou satisfaisable) s’il existe une distribution de v´erit´e v telle que Ev (f ) = 1. Ainsi une tautologie
est satisfiable.
A l’inverse une contradiction est une formule qui n’est pas satisfiable.
Proposition f ∈ L est une tautologie si et seulement si ¬f est une contradiction.

2.3

table de v´
erit´
e

Par induction structurelle on ´etablit la proposition
Soit f une formule logique; l’ensemble V(f ) des variables qui y figurent est fini.
Si v1 et v2 sont deux contextes qui co¨ıncident sur V(f ) alors Ev1 (f ) = Ev2 (f )
f est une formule d´ependant de n variables x1 , ..., xn . Il y a 2n distributions de v´erit´e possibles. On consigne les r´esultats dans
un tableau `
a 2n lignes et p colonnes, p > n + 1, o`
u la derni`ere colonne est Ev (f ). Par exemple la formule (x ∧ y) ∨ z, a pour
table de v´erit´e
x

y

z

x∧y

(x ∧ y) ∨ z

0

0

0

0

0

0

0

1

0

1

0

1

0

0

0

0

1

1

0

1

1

0

0

0

0

1

0

1

0

1

1

1

0

1

1

1

1

1

1

1

Ainsi une formule
est une tautologie si la derni`ere colonne de la table de v´erit´e ne comporte que des 1
est satisfiable si la derni`ere colonne de la table de v´erit´e comporte au moins un 1
est une contradiction si la derni`ere colonne de la table de v´erit´e ne comporte que des 0
Remarque : le temps de construction d’une table de v´erit´e est en O (2n )(il faut consid´erer toutes les distributions de v´erit´e)

2.4

Equivalence des formules

Les formules f et g sont dites ´equivalentes (ou logiquement ´equivalentes) si pour toute distribution de v´erit´e v, Ev (f ) = Ev (g).
On note alors f ≡ g.
Proposition:

f ≡ g si et seulement si f ⇔ g est une tautologie.

Preuve; supposons f ≡ g.
Soit v une distribution de v´erit´e. Ev (f ⇔ g) = ϕ⇔ (Ev (f ) , Ev (g)) o`
u ϕ⇔ (0, 0) = 1 = ϕ⇔ (1, 1) et ϕ⇔ (0, 1) = 0 = ϕ⇔ (1, 0). Or
f ≡ g : ainsi Ev (f ) = Ev (g) et par cons´equent Ev (f ⇔ g) = 1.
R´eciproquement, supposons que f ⇔ g soit une tautologie. Soit v une distribution de v´erit´e. Ev (f ⇔ g) = 1 = ϕ⇔ (Ev (f ) , Ev (g)).
Par d´efinition de ϕ⇔ , Ev (f ) = Ev (g). Ceci ´etant vrai pour toute distribution de v´erit´e v, f ≡ g.

Tautologies classiques :
(x ⇒ y) ⇔ (¬y ⇒ ¬x) contraposition
(x ⇒ y) ⇒ ((y ⇒ z) ⇒ (x ⇒ z)) syllogisme
x ∨ ¬x tiers exclu
¬ (x ∧ y) ⇔ ¬x ∨ ¬y
¬ (x ∨ y) ⇔ ¬x ∧ ¬y lois de De Morgan
Exercice: ( pour la suite)
si f ≡ g alors ¬f ≡ ¬g
si ( f ≡ f1 et g ≡ g1 ) alors f ∧ g ≡ f1 ∧ g1
si ( f ≡ f1 et g ≡ g1 ) alors f ∨ g ≡ f1 ∨ g1

3

Formes normales

L’exploitation informatique des formules logiques s’effectue
1. lors de l’´evaluation, quand on se donne une distribution de v´erit´e
2. `
a la question de la satisfiabilit´e : existe-t-il une distribution de v´erit´e v telle que Ev (f ) = 1?
3. `
a la question d’une tautologie: ∀v, Ev (f ) = 1
4. `
a la question de l’identit´e fonctionnelle: f ≡ g?
Pour ´etudier ces questions on d´efinit une forme standardis´ee des formules logiques, la forme normale.

3.1

formes normales conjonctives

Un litt´eral est une variable propositionnelle ou la n´egation d’une variable propositionnelle.
Une clause est une disjonction de litt´eraux : f = l1 ∨ l2 ... ∨ ln ; pour tout i li = x ∈ V ou li = ¬x o`
u x ∈ V.
Le mˆeme litt´eral peut apparaˆıtre plusieurs fois dans une clause.
Une fome normale conjonctive est une conjonction de clauses : f = C1 ∧ C2 ... ∧ Cp o`
u les Ci sont des clauses
Exemple: f = x ⇒ (y ∧ z) est ´equivalente `
a (¬x ∨ y) ∧ (¬x ∨ z)

3.2

formes normales disjonctives

on inverse les rˆ
oles de ∧ et ∨.

3.3

formes normales d’une formule

Proposition
f ∈ L. Il existe f ∗ ∈ L forme normale conjonctive, f + ∈ L forme normale disjonctive telles que f ≡ f ∗ , f ≡ f + .
Lemme
On prouve que

1. si f est un litt´eral, ¬f est ´equivalent `
a un litt´eral
2. si f est une conjonction de litt´eraux alors ¬f est ´equivalent `a une disjonction de litt´eraux
3. si f est une disjonction de litt´eraux alors ¬f est ´equivalent `a une conjonction de litt´eraux
4. si f est une conjonction de disjonctions de litt´eraux alors ¬f est ´equivalent `a une disjonction de conjonctions de litt´eraux
5. si f est une disjonction de conjonctions de litt´eraux alors ¬f est ´equivalent `a une conjonction de disjonctions de litt´eraux
On travaille par induction structurelle
f = V , f + = x1 ∨ ¬x1 (deux clauses), f ∗ = (x1 ∨ ¬x1 ) ∧ (x2 ∨ ¬x2 ) (deux clauses aussi)
f = F , f + = (x1 ∧ ¬x1 ) ∨ (x2 ∧ ¬x2 ) (deux clauses), f ∗ = x1 ∧ ¬x1 (deux clauses aussi )
f = x une variable propositionnelle, c’est `
a la fois une conjonction et une disjonction de litt´eraux.
f = ¬g ; g ≡ g + forme normale disjonctive. ¬g ≡ ¬g + ; or ¬g + ≡h conjonction de disjonctions de litt´eraux.
g ≡ g ∗ forme normale conjonctive. ¬g ≡ ¬g ∗ ; or ¬g ∗ ≡h disjonction de conjonctions de litt´eraux
f = g ∨ h; or g ≡ g + et h ≡ h+ donc f ≡ g + ∨ h+ disjonction de conjonctions de litt´eraux.
or g ≡ g ∗ et h ≡ h∗ avec g ∗ = g1 ∧ g2 ∧ ... ∧ gn , h∗ = h1 ∧ h2 ∧ ... ∧ hp . g ∨ h ≡

V

(gi ∨ hl ) o`
u gi , hj sont des

i∈[[1,n]]
j∈[[1,p]]

disjonctions de litt´eraux. f est ´equivalente `
a une conjonction de disjonction de litt´eraux.
On travaille de mˆeme avec f = g ∧ h.

3.4

formes normales et table de v´
erit´
e

Forme normale disjonctive.
On rep`ere les lignes v o`
u Ev (f ) = 1. Soit l’une de ces lignes. Si v (xi ) = 1 dans la clause on a le litt´eral xi sinon on a le litt´eral
¬xi . On effectue la conjonction de ces litt´eraux pour chaque ligne, la disjonction de ces formules-lignes.
Exemple: la formule ¬x ∨ (y ⇒ z), a pour table de v´erit´e
x

y

z

¬x ∨ (y ⇒ z)

0

0

0

1

0

0

1

1

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1

.

On r´ecup`ere les lignes 1,2, 3, 4, 5, 6, 8.
f ≡ (¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ ¬z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ ¬y ∧ z) ∨ (x ∧ y ∧ z)
Forme normale conjonctive.
On rep`ere les lignes v o`
u Ev (f ) = 0. Soit l’une de ces lignes. Si v (xi ) = 1 dans la clause on a le litt´eral ¬xi sinon on a le litt´eral
xi . On effectue la disjonction de ces litt´eraux pour chaque ligne, la conjonction de ces formules-lignes.



Documents similaires


2016 chapitre 6 logique
serie2
87vpyde
how to math 3
exercices logique
logique combinatoire


Sur le même sujet..