[PDF] [PDF] TD 3 - Calcul propositionnel

View - Download [PDF] TD 3 - Calcul propositionnel

Previous PDF

Next PDF

Logique et complexité TD 3 M1 LMFI

TD 3 - Calcul propositionnel

On fixe un ensembleP=fpiji2Ig, où lespisont desvariables propositionnelles(elles prennent comme valeurs " vrai » ou " faux »). Lesformules du calcul propositionnelsont des mots sur l"alphabetP[f:;>;?;^;_;,;);(;)g, formés selon les règles (inductives) suivantes : -piest une formule pour touti; - siFetGsont des formules, alors:F,(F^G),(F_G),(F,G)et(F)G)aussi.

SoitFPl"ensemble des formules du calcul propositionnel. On identifie0avec " faux » et1avec " vrai ».

Unedistribution de valeurs de vérité (d.v.v.)est une application:P ! f0;1g. Par induction sur la

construction deF, on définitj=F, luest modèle deFouFest satisfaite par, comme suit : - pourpi2 P, on posej=pissi(pi) = 1; -j=>et6j=? -j=:Fssi6j=F; -j= (F^G)ssij=Fetj=G; - on procède de manière analogue pour(F_G),(F,G)et(F)G), en utilisant les tables de vérité des connecteurs binaires_;,et). On écritF=F(q1;:::;qn)si lesqisont des variables distinctes et si toutes les variables ayant une occurrence dansFfigurent parmi lesqi. Unetautologie (du calcul propositionnel)est une formuleF2Ptelle quej=Fpour toute d.v.v.. Deux formulesFetGsont(logiquement) équivalentessi(F,G)est une tautologie.

Exercice 1. Tautologies.

SoientM;NetLdes formules propositionnelles. Montrer que les formules suivantes sont des tautolo- gies : -F1=M)(N)M) -F2= ((M)N))M))M -F3= (M)N))((M)(N)L)))(M)L)) -F4= (:M) :N))(N)M)

Exercice 2. Formules à équivalence près.

1. Donner une liste complète des formulesF(p0;p1)à équivalence près.

2. Déterminer le cardinal de l"ensemble des formules en les variables propositionnellesp0;:::;pn1

à équivalence près.

Solution de l"exercice 2.

On va répondre aux deux questions simultanément. Il faut commencer par remarquer que le fait qu"une formule soit satisfaite ou non par une d.v.v. ne

dépend que de la restriction de la d.v.v. à l"ensemble des variables propositionnelles apparaissant dans

la formule. Ainsi des formules de la formeF(p0;:::;pn1)sont équivalentes ssi elles sont satisfaites par

le même ensemble de d.v.v surfp0;:::;pn1g.

L"ensemble de telles d.v.v. s"identifie naturellement àf0;1gn. Considérons l"application :F(p0;:::;pn1)7!

f2 f0;1gn:j=Fg. Par définition,passe au quotient en une application qui à une classe d"équi-

valence de formules associe l"ensemble des d.v.v. les satisfaisant. Par ce qui vient d"être dit,est une injection. On a donc au plusjP(fd.v.v. surfp0;:::;pn1gj= 22n formules à équivalence près. Montrons queest surjective, ce qui revient à donner une liste des formules propositionnelles à

équivalence près et montrera qu"il y en a bien exactement22n. On commence par construire, pour uneUniversité Paris Diderot 1 UFR de mathématiques

Logique et complexité TD 3 M1 LMFI

d.v.v., une formuleFsatisfaite uniquement par. Pour2 f0;1gon pose p i=pisi= 1 :pisi= 0:

Par constructionj=p(pi)

iet si0(pi)6=(pi)alors6j=p(pi) i. On poseF=Vn1 i=0p(pi) i. On vérifie

aisément queFest satisfaite uniquement par. Alors étant donné un sous ensembleAde l"ensemble

des d.v.v on poseFA=W

2AF, par constructionFAest satisfaite exactement par les élements deA,

ce qui montre queest surjective. En faisant la liste des partiesAdef0;1gfp0;p1get en écrivant lesFAcorrespondantes, on obtient la liste demandée à la question 1. Exercice 3. Forme normale disjonctive / conjonctive.

SoitFune formule propositionnelle.

1. Montrer queFest équivalente à une formule de la forme

m _ i=1k i^ j=1L ij; oùLijest égale àpou à:p, pourp2 P. On l"appelle uneforme normale disjonctivedeF. On pourra s"appuyer sur l"exercice précédent.

2. Montrer queFest équivalente à une formule de la formem^

i=1k i_ j=1L ij;oùLijest égale àpou à :p, pourp2 P. On l"appelle uneforme normale conjonctivedeF.

Solution de l"exercice 3.

1. Découle de la question 2 de l"exercice précédent.

2. Découle de la question précédente en appliquant les lois de de Morgan.

Exercice 4. Théorème de compacité du calcul propositionnel. SoitFPl"ensemble des formules propositionnelles construites sur un ensemble infiniPde variables propositionnelles. Un ensemble de formules propositionnellesest ditsatisfaisables"il existe une d.v.v.telle quej=F pour toutF2; il est ditfiniment satisfaisablesi toute partie finie0est satisfaisable. Le but de cet exercice est de montrer le théorème suivant : Théorème :Un ensemblePde formules propositionnelles est satisfaisable si et seulement s"il est finiment satisfaisable.

1. Un cas particulier : On dit queestcompletsi pour toute variable propositionnellep2 Pon

ap2ou:p2. Montrer le théorème ci-dessus dans le cas oùest complet.

2. Montrer à l"aide du lemme de Zorn que tout ensemble finiment satisfaisable de formules propo-

sitionnelles est contenu dans un ensemble finiment satisfaisable et complet.

3. Conclure.

4. Montrer le théorème dans le cas oùPest dénombrable sans utiliser le lemme de Zorn.

Solution de l"exercice 4.

1. Siest complet, remarquons d"abord que pour toute variable propositionnellep,ne peut

contenir à la foispet:pcar alors le sous-ensemble finifp;:pgne serait pas satisfaisable. Pour toute variable propositionnellep, on est alors forcé de définircomme suit : (p) =psip2 :psi:p2Université Paris Diderot 2 UFR de mathématiques

Logique et complexité TD 3 M1 LMFI

Montrons quesatisfait toute formule de: soitFune telle formule, soientp0;:::;pnles variables propositionnelles apparaissant dansF. Posons q i=pisipi2 :pisi:pi2; alors0=fF;q0;:::;qngest un sous-ensemble fini desatisfaisable : soit0satisfaisant les éléments de0, alors comme pouri= 0;:::;non a que0j=qiet par définitionj=qi, on voit que par définition desqiet0coincident sur l"ensemblefp0;:::;png. Or toutes les variables propositionnelles deFsont dansfp0;:::;pngdonc le fait quej=Fou non ne dépend que de la restriction deàfp0;:::;png, et ainsi comme0j=Fon aj=Fcomme voulu.

2. SoitXl"ensemble des ensembles de formules finiment satisfaisables. AlorsXest de caractère

fini (cf. corrigé du TD 2, exercice 4) d"après la définition d"être finiment satisfaisable :est

dansXssi toute partie finie deest dansX. De plusXest non vide car il contient l"ensemble vide, donc on peut appliquer le lemme de Zorn àX(pour l"inclusion) et trouver~maximal pour l"inclusion contenant. Montrons que~est complet. Supposons que~ne contienne nipni:p, alors par maximalité[ fpgn"est pas finiment satisfaisable, donc on trouve0[ fpgfini non satisfaisable, et comme2Xon a que0 contientp. Ainsi on peut écrire

0= 00[ fpg

avec00fini. Par le même raisonnement en remplaçantppar:p, on trouve1= 01[f:pg fini non satisfaisable avec01~ Mais l"ensemble00[01est fini inclus dans~, donc satisfaisable par une d.v.v.. Si(p) = 1, on contredit le fait que0n"est pas satisfaisable, et si(p) = 0on contredit le fait que1n"est pas satisfaisable. Dans tous les cas, on aboutit à une contradiction. Donc~contientpou~ contient:p: on a montré que~est complet comme voulu.

3. Il est clair que siest satisfaisable,est finiment satisfaisable. Réciproquement, supposons

finiment satisfaisable, alors par la question2on a~complet finiment satisfaisable contenant et par la question1on a que~est satisfaisable. En particulier~est satisfaisable, ce qui établit la preuve du théorème de compacité.

4. On construit par récurrencenfiniment satisfaisable contenantde sorte queS

n2Nnsoit complet. Le lemme clé suivant a été démontré auparavant : Lemme.Siest finiment satisfaisable etpest une variable propositionnelle alors soit[fpg est finiment satisfaisable soit[ f:pgest finiment satisfaisable.

On énumère alors les variables propositionnellesfpi:i2Ng, et à chaque étape on ajoutepiou

:pien utilisant le lemme.

Exercice 5. Théorème de Ramsey fini.

SiAest un ensemble on notePn(A)l"ensemble des parties deAayant exactementnéléments. On admet le théorème suivant (connu sous le nom de théorème de Ramsey) : Théorème A :Pour toute applicationfdeP2(N)dansf0;1gil existe un sous-ensemble infiniAde Ntel que la restriction defàP2(A)soit constante.

Le but de l"exercice est d"utiliser le théorème de compacité du calcul propositionnel (voir l"exercice

précédent) pour déduire du théorème A le résultat suivant. Théorème B :Pour tout entiern>2, il existe un entierNtel que pour toute applicationfde P

2(f0;1;:::;Ng)dansf0;1gil existe une partieA f0;1;:::;Ngànéléments telle quefsoit

constante surP2(A). Pour cela on considère des formules propositionnelles construites sur l"ensemble de variablesP= fpfn;mg;fn;mg 2 P2(N)g.

1. SoitAune partie finie deNayant au moins deux éléments. Construire une formuleFAtelle

que siest une distribution de valeurs de vérité surP, alorsj=FAssiest constante sur fpfn;mg;fn;mg 2 P2(A)g.Université Paris Diderot 3 UFR de mathématiques

Logique et complexité TD 3 M1 LMFI

2. Soitn >1un entier. Montrer, en utilisant le théorème A, que l"ensemblef:FA;A2 Pn(N)g

n"est pas satisfaisable.

3. Montrer le théorème B.

4.Application :On considère le jeu suivant, à deux joueurs. On place un certain nombre de

points sur une feuille. Chaque joueur, à son tour, relie par un trait deux points encore non reliés, trait rouge pour le premier joueur, bleu pour le second. Le premier joueur ayant ainsi

tracé un pentagone est déclaré vainqueur. Montrer que, si l"on place au départ suffisamment de

points, il ne peut y avoir de partie nulle (i.e. sans vainqueur).Université Paris Diderot 4 UFR de mathématiques

quotesdbs_dbs5.pdfusesText_9

[PDF] logique propositionnelle table de vérité

[PDF] calcul propositionnel formel

[PDF] calcul des propositions exercices corrigés

[PDF] le resultat dune multiplication est

[PDF] comment calculer le taux de possession du stock

[PDF] cout de stockage annuel

[PDF] calcul du stock moyen

[PDF] exercice cout de passation et possession

[PDF] calcul tangente formule

[PDF] calcul tangente fonction

[PDF] calcul tangente en ligne

[PDF] calculer tangente calculatrice

[PDF] a quoi sert le sinus

[PDF] taux d'évolution successif

[PDF] imc 22 femme