[PDF] TD no 1 Calcul propositionnel — syntaxe et sémantique

View - Download TD no 1 Calcul propositionnel — syntaxe et sémantique

Previous PDF

Next PDF

AMU-L3Inf ormatiqueCoursLogiqueetCalculabilité-2017 TDn o 1

Calculpropositionnel - syntaxeetsémantique

SYNTAXE

Exercice1.1.Considérezlesformules ducalculpropositionnel suivantes : 1 :=r!(p¬(("q)#¬r)); 2 :=p"(r"((¬q)#¬p)); 3

Pourchaque formule!

i 1 2 3

1.dessinezsonarbresyntaxique;

2.énumérezsessous-formules ;

3.énumérezlessymboles propositionnelsayantune occurrencedans!

i

SÉMANTIQUE

Exercice1.2.1.Quellessont lesvaluationsquidonnentmême valeurà p"qetp#q?

2.Énumérezles modèlesdelaformule(p"q)%(p#q).

3.Estceque cetteformuleest (in)satisfaisable, valide?

Exercice1.3.Onconsidèreles formules!=p"(¬q#(q#p))et"=(p!q)%(¬p!¬q).

1.Soitvunevaluation. Déterminer,sipossible,v(!)etv(")danschacundes quatrecas suivants :

(a)onsait quev(p)=0etv(q)=1; (b)onsait quev(p)=0; (c)onsait quev(q)=1; (d)onnesai triensur v(p)etv(q).

2.Cesdeux formulessont-ellessatisfaisables? Destautologies?

3.L'ensemble{!,"}est-ilconsistant? C'est-à-dire,existet'ilunev aluationtelleque v(!)=v(")=1?

Exercice1.4.Uneformule!estditecontingentelorsqu'elleestsatisf aisableetnon unetautologie.Diresiles formulessuiv antessontinsatisfiables,contingentes,ouencoredestautologies :

1.(p#q)#p

2.p#(q#p)

3.(p"q)%(p#¬q)

Exercice1.5.Soit!uneformuledu calculpropositionnel.

1.Quepeut-on diredemod(!)lorsque!estcontingente ?

2.Soient!et"deuxformulespropositionnelles. Quepensez-vous desaffirmations suivantes :

(a)si!estcontingente,alors ¬!l'estégalement ; (b)si!et"sontcontingentes,alors !!"et!""sontcontingentes; (c)si!!"estinsatisfiablealors !et"sontinsatisfiables; (d)si!!"estunetautologie alors!et"sontdestautologies. (e)si!!"estunetautologie alors!estunetautologie, ou"estunetautologie.

Exercice1.6.Montrezqu'une formule!estunetautologie sietseulement si¬!n'estpassatisf aisable.Onsuppose

donnéun algorithmequivérifier siuneformule estunetautologie ;construireun autrealgorithmepour vérifiersi une

formuleest satisfaisable. Exercice1.7.Proposezuneformule !ayantlatable devéritésui vante: pqr! 0001 0011 0100
0111
1000
1010
1100
1111
Exercice1.8.Danscete xercice,on identifiel'ensemble{0,1}aucorpsZ/2Z.

1.Exprimerlesopérations+et&àl'aidedes connecteurs",!,¬;

2.Exprimerlesconnecteurs",!,¬àl'aidedes opérations+et&;

3.Montrerqu'àtouteformulepropositionnelle !dontlesv ariablessontq

1 ,...q n ,onpeut associerun polynôme

ànindéterminéesPtelque!=P(a

1 ,...,a n 1 ),...,v(q n

4.Endéduireune méthodepour déterminersideux formulessontlogiquement équivalentes, ousiune formule

estunetautologie. Exercice1.9.Prouvezleséquivalences logiquessuiv antes: !""'""!!!"'"!!(Commutativité) 1 2 1 2 1 2 1 2 (Associativité) ("!'!"('!)!!'!!)'!(Élementsneutres) !"!'!!!!'!(Idempotence) !"(!!")'!!!(!"")'!(Absorption) !")')"!')!!('(!!'((Elémentabsorbant) 1 2 1 2 1 2 1 2 )(Distributivité)

¬¬!'!(Involution)

¬(!"")'¬!!¬"¬(!!")'¬!"¬"(LoisdeDe Morgan) !#"'¬"#¬!(Contraposition) 1 2 3 1 2 3 (Curryfication) AMU-L3Infor matiqueCoursLogiqueetCalculabilité-2017 TDn o 2

CalculPropositionnel -Conséquenceslogiques

Rappels,notations.Danstoutecette planche,!et"désignentdeuxensembl esquelconques(finisou non,éventuellement vides)deformules.Demême,!et"dénotentdeuxformules propositionnellesquel- conques.

Danscetteplanche, onnoteraaussi :

Taut={!!F

cp |mod(!)=Val},NonSat={!!F cp |mod(!)=!},

Cons(!)={!!F

cp Tautestl'ensembledestautologies, NonSatest l'ensembledesformules non-satisfaisables,et Cons(!)est l'ensembledesconséquences logiquesde!.

Pourrappel,si AetBsontdeuxensembles, alors

- pourprouver queA"B,onmontre que"pourtout élémenta,sia!Aalorsa!B" - pourprouver queA=Bonmontreque A"BetqueB"A - a!A#Bssia!Aeta!B - a!A$Bssia!Aoua!B Exercice2.1.Onconsidèrel'ensemble deformulespropositionnelles "={p%q%r,p&q,q&r}

1.Trouverunmodèlede".Combieny a-t-ildemodèles ?

2.Lesformules q&p,p,rsontellesdes conséquenceslogiquesde "?

Exercice2.2.Onsedonne "unensemblefini satisfaisablede formules,uneformule !conséquencede", uneformule"quin'estpas uneconséquence de".

1.Onajouteune tautologie#à".Est-ce que!et"sontdesconséquences logiquesde"${#}?

Donnezunepreuv eformelle.

2.Mêmequestion si#estuneformule insatisfaisable.

Exercice2.3(Modélisation).Ondisposede troiscasesalignées, notées1,2,3deg aucheàdroite, etde

pionsdeformes différentes: triangle,rondou carré.Lespionspeuvent-êtreplacés dansles cases.Pour

chaquei!{1,2,3}onnotec i l'assertion: "lacaseicontientunpion carré»,et onfait demêmepour les autresformes.

1.Modélisez,avec desformulesducalculpropositionnel,lesdeuxassertionssui vantes: "ilya un

pionrondimmédiatement àdroited'un pioncarré»et"chaquecasecontient un(et unseul)pion ».

2.Donnezlesmodèles del'ensemble composéparces deuxformules.Que peut-onendéduirequant

aupionsitué danslacase 2?

Exercice2.4.Démontrer:

1.!|=!ssi!${¬!}|='.

2.!${!}|="ssi!|=!&".

3.!("ssiCons(!)=Cons(").

Exercice2.5.Démontrer:

1.!""impliquemod(")"mod(!)(vuencours) ;

2.!""impliqueCons(!)"Cons(");

3.!"Cons(!);

4.mod(Cons(!))= mod(!)(partiellementvu encours);

5.mod(!)=mod(")ssiCons(!)=Cons(");

6.Cons(Cons(!))=Cons(!);

7.mod(!)"mod(")ssiCons(")"Cons(!).

Exercice2.6.Démontrer,pourtouteformule !:

1.Taut"Cons(!).

2.!!TautentraîneCons(!)=Taut.

3.!!NonSatentraîneCons (!)=F

cp

4.!!TautentraîneCons("${!})=Cons(").

5.!!NonSatentraîneCons ("${!})=Cons(!).

Exercice2.7.Unensemblede formules"estditcompletssi "estconsistantet, pourtout !!F cp ,"|=!ou"|=¬!

1.Montrezque"estcompletssi ilaun etunseul modèle.

2.Donnezl'ex empled'unensemblecompletetd'unensemblenoncomplet.

3.Sivestuneune valuation, onappellethéoriedev,eton noteT H(v),l'ensembledes formulessatis-

faitesparv.Autrement dit,TH(v)={!!F cp |v(!)=1}.Montrezque, pourtout v!Val,TH(v) estcomplet.

4.Montrezque Cons(TH(v))"TH(v).

5.Donnezl'e xempled'unensemblecompletquin'estpasdelaforme TH(v).

Exercice2.8.Soit"unensemble complettelque Cons(")"".Prouvez que:

1.!!"ssi¬!)!",

2.!*"!"ssi$!"et"!",

3.!%"!"ssi$!"ou"!".

AMU-L3Infor matiqueCoursLogiqueetCalculabilité-2017 TDn o 3 CalculPropositionnel -Équivalences,algorithmes,modélisation

Soient!,"!F

cp etq!PROP;lasubstitution, dansla formule!,dela variableqparlaformule ", notée! [q""] ,sedéfinit parinduction surlastructure d'uneformuleselon lescassui vants: p [q""] ",sip=q, p,sinon, [q""] [q""] [q""] ,ou#!{%,&,'},(¬#) [q""] [q""]

Exercice3.1.(Substitution).Ecriv ezexplicitement!

[p""]quotesdbs_dbs5.pdfusesText_9

[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

[PDF] tableau imc femme

[PDF] imc 23 femme