Cours sur la logique des propositions

Description

Cours sur la syntaxe, sémantique du calcul des proposition, complexité des algorithmes, arbres binaires, théorie des langages, automates finis, compléments sur les langages rationnels, expressions Algébriques, analyse des expressions,

Sujets

• Cours
• informatique
• informatique cours

Informations

• Publié par: Force_IT
• Nombre de lectures: 46
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

´
SPE MP, MP*

Ann´ee2004/2005

Option Informatique

Polycopie´ducours

Chapitre 0
Logique des propositions

2

Logique des propositions
I Syntaxe du calcul des propositions

I.1 Variables propositionnelles

Danstoutvechapitre,onsupposedonne´unensembleP={p0, p1, . . .}de variables
index´eesparlesentiersnaturels.Les´el´ementsdePtnosse´leppavariables propositionnelles.
Poure´viterd’alourdirlesnotations,onnoteralaplupartdutempscesvariablesparune
lettre unique, telle quep, q, r, . . ..

I.2 Connecteurs

Onsefixee´galementuncertainnombredesymboles,4pourˆetrepre´cis:NOT(¬),AND
(∧),OR(∨) etIMPL(⇒). OnnoteC={¬,∧,∨,⇒}s´Le´eelntmeesd.Ctnoseppase´lsed
connecteursmerialctnortıˆar,lteuiasslantdenuodrP.appasquiisonesrauercenoentc¬est
ditunaire; les autres connecteurs sont ditsbinaires. D’autreschoix de connecteurs auraient
´ete´possibles.Nousenreparleronsplusloin.

I.3 Formules logiques

Les variables propositionnelles et les connecteurs sont des objets abstraits.Aucun sens
neleurestattribu´e.Introduisonsdeuxnouveauxsymbolestoutaussiabstraits,not´es)
et(,quenousappelleronsparenth`esefermanteetparenth`eseouvrante.Noussupposerons
bienentenduquetouslesobjetsd´efinisjusqu’`apre´sentsontdistincts.Parexemple,aucune
variablepropositionnellen’est´egale`alaparenthe`sefermante.Soitalors
[ [
A={P C(,)}.

L’ensembleAestl’alphabet de la logique des propositions´seLe´le.mentsdeAsont donc
leslettrespselge`rselrennoade`streIle.agngceetodselmsuqreabritdefttanerme’dnual
langage.
Unmotsur l’alphabetAest une suite finie de lettres deA,´eventuelldivtnemenU.e
mots’e´critenjuxtaposantseslettres.Ainsi,((p0⇒p1)∧ ¬p2Par ailleurs,) est un mot.
(()p0p0⇒ ∨(p2etderencepotepr´ef´ei:r’cseruelrpmei.ssauunstneeitepenusnovasuoN
celaqu’ils’agitdanstoutelapremie`repartiedecechapitre.
∗
.
On noteAl’ensemble des mots sur l’alphabetA..
∗
Th´eor`eme1Il existe une plus petite partieLdeAifiertan´v
• P⊂ L.
•SiG∈ L, alors¬G∈ L.
•SiGetHsont dansL, et siαest un connecteur binaire, alors le mot(GαH)est encore
dansLpselnera(eth`esesd(GαH)font partie du mot).
∗
à
L’ensembleArenuosiaˆ’dnertes,maessuaaucisn’ire´rppoicd-´tsev´ertieneselifiertuot
minimal.Enrevanche,consid´eronsl’intersectionLde tous les langages surA(’cse-ta`d-rie
∗
toutes les parties deA´v)fiireltna`rme´hoettie.eeCoispestrsdutointefictseerntri´envio
encore clairement les points en question, et est bien entendu minimale au sens de l’inclusion.à

De´finition1On appelleformule logiqueoupropositiontout mot deL.

1

Syntaxe du calcul des propositions3
I.4Uned´efinitionparlebasdesformules

Lapr´ec´edented´efinitiondesformuleslogiquesn’estpasdutoutpratique.Ilestp´enible
de l’utiliser pour fabriquer des formules.C’est cependant faisable :par exemple, comme
P ⊂ L, on ap0etp1dansLparl.Etdesp’uneedt´libiete´irporatsedse´L, le mot (p0∧p1)
estuneformulelogique.Ilyamieux`afaire.Introduisonspourcelaquelquesnotations.

On poseL0=Ppour tout entier naturel. Puis,n´tdifine,no
[ [
Ln+1=Ln{¬G, G∈ Ln} {GαH, G∈ Ln, H∈ Ln, α∈ C \ {¬}}.

Onpose´egalement

[
′
L=Ln.
n≥0

′
The´ore`me2On aL=L.
à
On aL0=P ⊂ L. Ilest clair que siLn⊂ Ldsetie´abildesttp´reosp,rlie´seLentraˆınent que
′ ′
Ln+1⊂ Lne.Oeuqtiude´dnL ⊂L. Inversement,siGetHeinnne`tpaaptraL, alors ils
sonttouslesdeuxdansunmeˆmeLnpour un certain entiern(. Donc,GαH)∈ Ln+1donc
′ ′
(GαH)∈ L, ceci pour tout connecteur binaireα.Demˆeme,Lategn.ioseatstpelb´nra
′
Ainsi,parminimalit´edeL, on aL ⊂ L.à
+
Les lettrespetqigned´esserpailbvsratnedelnns.leosopioitomeLtF= (p⇒(p∨q)) est
une formule logique.En effet,petqsont dansL0, doncpet (p⇒q) sont dansL1etFest
finalement dansL2.+
-
Montrer queF= (((p⇒q)∧(q⇒r))⇒(p⇒r)) est dansL3.-
De´finition2On appelle hauteur d’une formuleFle plus petit entierntel queF∈ Ln.1
Ainsi, une variable propositionnelle est une formule de hauteur 0.Les formules de l’exemple
ci-dessussontdehauteursrespectivesinfe´rieuresou´egalesa`2et3.Onparieraitsurl’´egalit´e
maisquisait?N’yaurait-ilpasunesubtilede´compositiondecesformulesplusastu-
cieusequelade´composition´evidente?Nousde´montreronsunpeuplusloinlethe´ore`mede
lectureuniquequiassure,lorsqu’onatrouve´unede´compositiond’uneformule,quecette
de´compositionestlaseulepossible.
I.5 Inductions structurelles
Dufaitmˆemequel’ensembledesformulesest´etag´e(c’est-a`-diresepre´sentecommeune
r´eunioncroissanted’ensembles),onpeuteffectuerdesde´monstrationsparre´currencesurla
hauteurdesformules.Onpeutfaireencorepluse´le´gant,eneffectuantdesd´emonstrations
par“inductionstructurelle”.Lethe´ore`meci-dessousdonneleprincipe.
Proposition 3SoitP[F]orsflemuOns.ppsue´tetropstnaelruunpri´eproso:e
•eifierv´lelepropositionnelTuoetavirbaP.
•Pour toute formuleGiuqifiev´erPla formule¬Gocerefinee´irvP.
•SiGetHe´vsafiirrofxelumonseutdntPetαest un connecteur binaire, alors(GαH)
ve´rifieencoreP. Alors,P[F]est vraie pour toute formule logiqueF.
Avantded´emontrercettepropri´ete´,donnonsunexemple.
Proposition 4bredunomeparpadentreesh`ouesnarvesete´tsalagDanstouteformuleoliguq,eelonbmer
enth`esesfermantes.

4Logique des propositions
à
Notonso[F] etf[Fmorbdeperanehte`sesouvrantesetdeen]l`htnerapmrefseseelsdteana
formuleF.
•SiF∈ P, alorso[F] =f[F] = 0.
•SiGest une formule telle queo[G] =f[G], alorso[¬G] =o[G] etf[¬G] =f[G]. Donc
o[¬G] =f[¬G].
•SoientGetHsont deux formules, et soitαSupposonsun connecteur binaire.o[G] =
f[G] eto[H] =f[H]. Alorso[(GαH)] =o[G] +o[H1e]+adnvletimeeˆemopru
f[(GαH)].à
à
Leth´eor`emed’inductionseprouveparr´ecurrencesurlahauteurhdes formules.Par hy-
pothe`se,laproprie´te´estvraiepourhSoit maintenant un= 0 (variables propositionnelles).
entierhrSp.alospnpous´te´irpoePvraie pour toutes les formules deLh. SoitF∈ Lh+1.
Onatroispossibilite´s:
•F∈ Lha bien: onP[F].
•F=¬G,`ouG∈ Lha alors: OnP[Geredesh`otyp’hrl,cnoD.ecnerruce´ona]paP[F].
•F= (GαH)o,u`G, H∈ LhetαOn a alorsest un connecteur binaire :P[G] etP[H]
parl’hypoth`esedere´currence.Donc,onaP[F].à

I.6Leth´eor`emedelectureunique
The´ore`me5SoitFune formule logique.On est dans un, et un seul, des trois cas suivants :
•Fest une variable propositionnelle.
•Il existe une unique formule logiqueGtelle queF=¬G.
•Il existe une unique formule logiqueG, une unique formule logiqueHet un unique
connecteur binaireαtels queF= (GαH).
à
Une formule est un mot dont les lettres sont dans l’alphabetAbetuua´dfiein´dre.apitduch
Lapremi`erelettredecemotestunevariablepropositionnelleou bieneeshu`enapertnou
bien’exccasstmutluanmeneeullamqr.teRonncu,ruetcensiortsecsmelecsmooropcapeeu`r
parenth`esessontimportantes.Onpourraitavoirl’impressionqu’ilyapleindeparenthe`ses
inutiles,maisellessontenfaitfondamentalesa`lade´monstrationduthe´ore`medelecture
unique. Celadit, nous ferons plus tard quelques conventions qui nous permettront de ne
pase´crireexplicitementcertainesparenthe`ses.
Onestforc´ementdansundestroiscasduthe´ore`me(unlecteurconsciencieuxleprou-
veraitparinductionstructurelle).Lepointcrucialquireste`amontrerestl’uncit´edans
chacun des cas.
′ ′
Si l’on est dans le premier cas, c’est facile.SiF=p=p`uopetpsont des variables
′
propositionnelles, alorsp=p(on vient de le dire, suivez un peu. . .).
′ ′
Danslesecondcas,c’estaussitr`esfacile.SiF=¬G=¬G, alorsG=G: onrappelle
qu’uneformulen’estqu’unesuitedelettresetquedeuxmotssonte´gauxsietseulementsi
ilsontlesmˆemeslettres.
Letroisi`emecasestmoinstrivial,ilnecessitequelqueslemmes.
Lemme 6SoientFune formule etGe´xfinurpdeeF. Alorso[G]≥f[G].
à
Le motGnutsedexfie´rpmutoFlorsqu’il existe un motHtel qu