[PDF] Cours logique - Mémo n?1 Logique propositionnelle

View - Download Cours logique - Mémo n?1 Logique propositionnelle

Previous PDF

Next PDF

Cours logique - Memo n1

Logique propositionnelle

Emmanuel Coquery

1 Syntaxe

Denition 1 (Formules logiques)Soient les deux constantes>et?, un en- semblePdevariables propositionnelles, noteesp;q;r;:::, et lesconnecteurs lo- giquesf:;_;^;);,g. {>,?,poupest une variable propositionnelle sont des formules. { SiAest une formule, alors(:A)est une formule. { SiAetBsont des formules alors(A_B),(A^B),(A)B)et(A,B) sont des formules. On pourra se passer des parentheses en utilisant les regles suivantes ::est plus prioritaire que les autres operateurs et_et^sont plus prioritaires que)et,. Denition 2 (Formules atomiques)Une formule estatomiquesi c'est>,?ou si c'est une variable propositionnelle.

Denition 3 (Sous-formules)

Etant donnee une formule logiqueA, l'ensemble

de sessous-formulesest donne par la fonctionsf(A), denie inductivement comme suit : { SiAest atomique,sf(A) =fAg. { SiAest de la forme:B, alorssf(A) =fAg [sf(B). { SiAest de la formeB_C,B^C,B)CouB,C, alorssf(A) =fAg [sf(B)[sf(C). Denition 4 (Arbre de syntaxe abstraite)L'arbre de syntaxe abstraiteASA(A) associe a une formuleAest un arbre dont les noeud sont etiquete par des connec- teurs logiques ou des variables propositionnelles. Il est inductivement deni comme suit : { SiAest atomique, alorsASA(A)est une feuille etiquetee parA. { SiA=:B, alorsASA(A)est un arbre dont la racine est etiquetee par:et qui a un seul ls :ASA(B). { SiA=B_C, alorsASA(A)est un arbre dont la racine est etiquetee par_ et qui a deux ls. Le ls gauche estASA(B)et le ls droit estASA(C). { SiA=B^C, alorsASA(A)est un arbre dont la racine est etiquetee par^ et qui a deux ls. Le ls gauche estASA(B)et le ls droit estASA(C). { SiA=B)C, alorsASA(A)est un arbre dont la racine est etiquetee par )et qui a deux ls. Le ls gauche estASA(B)et le ls droit estASA(C). { SiA=B,C, alorsASA(A)est un arbre dont la racine est etiquetee par ,et qui a deux ls. Le ls gauche estASA(B)et le ls droit estASA(C).

2 Semantique

Denition 5L'ensemble desbooleens, noteB, est l'ensemblef0;1g.0denote la valeurfauxet1la valeurvrai. Denition 6Unefonction booleenneanarguments est une fonctionBn! B. 1 Denition 7La fonction booleennef:associee au connecteur:est donnee par la table de verite suivante :xf :(x)10 01 Les fonction booleennesf_,f^,f)etf,associees aux connecteurs_,^,)et ,sont donnees par la table de verite suivante :x yf _(x;y)f ^(x;y)f )(x;y)f ,(x;y)1 11111

1 01000

0 11010

0 00011

Denition 8Uneinterpretationpour un ensemble de variable propositionnellesP est une fonctionI:P! B. Denition 9Lavaleur de verited'une formuleApar rapport a une interpretation I, notee[A]Iest denie inductivement de la maniere suivante : { Sipest une variable propositionnelle,[p]I=I(p). {[>]I= 1et[?]I= 0. { SiAest une formule logique alors[:A]I=f:([A]I). { SiAetBsont deux formules logiques alors : {[A_B]I=f_([A]I;[B]I) {[A^B]I=f^([A]I;[B]I) {[A)B]I=f)([A]I;[B]I) {[A,B]I=f,([A]I;[B]I) Denition 10Une interpretationIest unmodeled'une formuleA, noteIj=A, si et seulement si[A]I= 1. Une interpretationIest un modele d'un ensemble de formulesE=fA1;:::;Ang, noteIj=E, si pour toute formuleAi2E,Ij=Ai. Denition 11Une formuleAest ditesatisablesi il existe une interpretationI telle queIj=A. Une ensemble de formulesE=fA1;:::;Angest satisable si il existe une in- terpretationIqui est un modele deE. Une formule (resp. un ensemble de formules) qui n'est pas satisable est dit insatisable. Denition 12Le problemeSATconsiste a determiner si une formule est satis- able. Autrement dit,SAT(A) =truesiAest satisable. SinonSAT(A) =false. L'algorithme naf pour resoudre ce probleme consiste a enumerer toutes les in- terpretations possibles deApour verier si une de ces interpretations est un modele deA. On peut remarquer que siApossedenvariables, il existe 2ninterpretations possibles pourA. Il n'existe cependant pas d'algorithme connu permettant de faire mieux dans tous les cas (le probleme est dit NP-Complet). Denition 13Une formuleAestvalide, si toute interpretation est un modele de A. On notej=Ale fait queAsoit valide. On dit egalement queAest unetautologie. Un ensemble de formules est valide si toutes ses formules sont valides. Propriete 1Une formuleAest valide si et seulement si:Aest insatisable. 2 Preuve:(Inter^et de la preuve : comprendre les interactions entre les denitions 7,

9, 10, 11 et 13.)

Aest valide si et seulement si (notessi) pour toute interpretationI,Ij=A, i.e. ssi [A]I= 1. D'apres les denitions 7 et 9 [A]I= 1 ssi [:A]I= 0. DoncAest valide ssi pour toute interpretationI,I6j=:A, i.e. si:Aest insatisable.2 Denition 14SoitE=fA1;:::;Angune ensemble de formules etBune formule. Best une consequence logique deE, noteEj=Bsi tout modele deEest un modele deB.

Propriete 2

{fA1;:::;Ang j=Bsi et seulement si(A1^:::^An))Best valide. { SiEest insatisable, alors pour toute formuleB,Ej=B. { SiBest valide, alors pour toutE,Ej=B. {Ej=Bsi et seulement siE[ :Best insatisable.

Preuve:A faire en TD2

3 Equivalence de formules

Denition 15Deux formulesAetBsont dites equivalentes, noteAB, siAj=

BetBj=A.

Propriete 3 (Principe de substitution)SoientA,BetCdes formules telles queABetAest une sous-formule deC. Toute formuleC0obtenue en remplacant une occurrence deAparBdansCest equivalente aC.

Preuve:A faire en TD.2

Denition 16Soitfune fonction booleenne anarguments. SoitAune formule ayantnvariablesp1;:::;pn. Si, pour toute interpretationIdeA, on af(I(p1);:::;I(pn)) = [A]I, alors ont dit quefestrealisee parA. Denition 17SoitCun ensemble de connecteurs.Cest ditfonctionnellement completsi pour toute fonction booleennefil existe une formuleAne contenant que des connecteurs deCet telle quefsoit realisee parA. Propriete 4f:;_;^g,f:;^g,f:;_getf:;)gsont fonctionnellement complets. Preuve:(Inter^et de la preuve : voir une preuve par recurrence, preuve constructive : on peut en faire un programme.) On commence par prouver quef:;_;^gest fonctionnellement complet. Soitf:Bn! B. On montre par recurrence qu'il existe une formuleAfayant p

1;:::;pncomme variables telle que pour tout (b1;:::;bn)2 Bn, en posantI(p1) =

b

1;:::;I(pn) =bn, on a [Af]I=f(b1;:::;bn).

Considerons le cas de basen= 1.

Il n'y a que 4 fonctions booleennes a 1 argument, decrites dans le tableau ci- dessous :f(0)f(1)f 111
f 210
f 301
f 400
3 Le tableau ci-dessous donne pour chaquefila formuleAiqui la realise (i.e. telle que pour toutb12 f0;1g, en posantI(p1) =b1, on a [Ai]I=fi(b1) :A 1p

1_ :p1A

2:p1A 3p 1A 4p

1^ :p1Considerons le cas oufposseden+ 1 arguments et supposons la propriete

demontree pour toutfayantnarguments ou moins. Posonsf0(b1;:::;bn) =f(b1;:::;bn;0) etf1(b1;:::;bn) =f(b1;:::;bn;1). Alors il existeA0ayant pour variablesp1;:::;pnet realisantf0etA1ayant pour variablesp1;:::;pnet realisantf1.

PosonsAf= ((:pn+1)^A0)_(pn+1^A1).

Montrons queAfrealisef. Soit (b1;:::nn+1)2Bn+1etItqI(pk) =bkpour

1kn+ 1.

{ sibn+1= 0, alors [pn+1]I= 0 et donc [pn+1^A1]I= 0, d'ou [Af]I= [(:pn+1)^A0]I= [A0]I=f0(b1;:::;bn) =f(b1;:::;bn;bn+1). { sibn+1= 1, alors [pn+1]I= 1 et donc [:pn+1^A0]I= 0, d'ou [Af]I= [pn+1^A1]I= [A1]I=f1(b1;:::;bn) =f(b1;:::;bn;bn+1). 2

Quelques equivalences remarquables :

> ^AA ? _AA > _A > ? ^A ?

A_ :A >

A^ :A ?

::AA

A_AAA^A

A_BB_A

A^BB^AA_(B_C)(A_B)_C

A_B_C

A^(B^C)(A^B)^C

A^B^C

A^(A_B)A

A_(A^B)A

:(A^B) :A_ :B :(A_B) :A^ :B

A)B :A_B

A)B :B) :A

A,B(A)B)^(B)A)

A_(B^C)(A_B)^(A_C)

A^(B_C)(A^B)_(A^C)

Quelques tautologies remarquables :

A)A(identite)

((A)B))A))A(loi de Pierce)

A_ :A(tiers exclu)

(A)B)^A)B(modus ponens) (A)B)^ :B) :A(modus tollens) (A)B)^(B)C))(A)C) (modus barbara) 4

4 Substitutions en calcul propositionnel

Attention : ne pas confondre avec le principe de substitution. Denition 18Une substitution est une fonctiond'un ensemble ni de variables propositionnelles dans les formules. On noteradom()son domaine de denition. Notation:on notera [A1=p1;:::;An=pn] la substitutionqui, pour 1in, associe la formuleAia la variablepi. Denition 19L'application d'une substitutiona une formuleA, noteeA, est denie inductivement par : {p=(p)sipest une variable propositionnelle appartenant adom() {p=psipest une variable propositionnelle n'appartenant pas adom() {(:A)=:(A) {(A_B)=A_B {(A^B)=A^B {(A)B)=A)B {(A,B)=A,B Propriete 5SoitAune formule etune substitution quelconques. SiAest valide, alorsAest valide. Preuve:Soit= [A1=p1;:::;An=pn] une substitution quelconque. Il faut montrer pour toute interpretationI, [A]I= 1. SoitIune interpretation quelconque. On introduit une interpretation auxiliaireItelle queIest identique aIsauf pour les variables substituees par. Pour une telle variablepi, la valeur deI est donnee par la valeur de verite dansIde la formuleAiqui remplacepi. Plus formellement,Iest denie par : {I(p) =I(p) sipn'est pas dansdom() {I(p) = [(p)]Isipest dansdom() (c'est-a-direI(pi) = [Ai]Ipour 1in). On montre a present par induction que pour toute formuleB, [B]I= [B]I.

On procede par cas en fonction de la forme deB:

{B=>: on aB=>et [B]I= [>]I= 1 = [>]I= [B]I. {B=?: on aB=?et [B]I= [?]I= 0 = [?]I= [B]I. {B=pavecpqui n'est pas dansdom() : on aB=p et [B]I= [p]I=I(p) =I(p) = [p]I= [B]I. {B=pavecpqui est dansdom() : on aB=(p) et [B]I= [(p)]I=I(p) = [p]I= [B]I. {B=:C: on aB=:(C) et, par hypothese d'induction, [C]I= [C]I. On en deduit : [B]I= [:(C)]I=f:([C]I) =f:([C]I) = [:C]I= [B]I. {B=C_D: on aB=C_Det par hypothese d'induction, [C]I= [C]I et [D]I= [D]I. On en deduit : [B]I= [C_D]I=f_([C]I;[D]I) =f_([C]I;[D]I) = [C_D]I= [B]I { La demonstration des cas^,)et,est similaire au cas precedent. Ce resultat est en particulier vrai pourA, c'est-a-dire que [A]I= [A]I. Comme Aest valide, [A]I= 1. CommeIest quelconque, ce resultat est vrai pour toutI. Donc pour toute interpretationI, [A]I= 1, doncAest valide.2

Corollaire 1SiABalors pour toute substitutionAB

5 En particulier, pour demontrer uneequivalence remarquable, il sut de la demontrer lorsque les formules sont des variables (par exemple en utilisant les tables de verites), le corollaire precedent permettant d'etendre le resultat a toutes les formules. 6quotesdbs_dbs19.pdfusesText_25

[PDF] lenchainement de gymnastique

[PDF] fonction proportionnelle

[PDF] formule chimique des ions

[PDF] liste des molécules chimiques

[PDF] formule chimique brute

[PDF] tableau des grandeurs physiques

[PDF] patron d'un cube

[PDF] propriétés des fluides pdf

[PDF] les fluides pdf

[PDF] propriétés physiques des liquides

[PDF] fluide définition simple

[PDF] caractéristiques des fluides

[PDF] exemple de fluide

[PDF] propriété des fluides exercice

[PDF] propriété du carré