Considérez les formules du calcul propositionnel suivantes : j1 := r_(p¬((^q) ) ¬r )); FRANÇAIS ET LOGIQUE FORMELLE, MODÉLISATION Exercice 3 10
Previous PDF | Next PDF |
[PDF] CALCUL PROPOSITIONNEL - LAMA
2 3 Vérifier-Prouver : Les preuves formelles par la règle Modus Ponens Les tables de vérité permettent d'affirmer qu'une proposition est une TAUTOLOGIE en
[PDF] TD no 1 Calcul propositionnel — syntaxe et sémantique
Considérez les formules du calcul propositionnel suivantes : j1 := r_(p¬((^q) ) ¬r )); FRANÇAIS ET LOGIQUE FORMELLE, MODÉLISATION Exercice 3 10
[PDF] TD no 1 Calcul propositionnel — syntaxe et sémantique
Considérez les formules du calcul propositionnel suivantes : j1 := r_(p¬((^q) ) ¬r )); FRANÇAIS ET LOGIQUE FORMELLE, MODÉLISATION Exercice 3 10
[PDF] Logique : le calcul propositionnel - IRISA, Rennes
Introduction Syntaxe du calcul propositionnel Sémantique du calcul propositionnel Dans l'énoncé ϕ → ψ, la formule ϕ est l'hypoth`ese et la formula ψ est la
[PDF] Logique et Calcul Propositionnel
Definition (Formule bien formée) On définit une formule bien formée (fbf) par : p, o`u p est une variable propositionnelle (A ∨ B) (A ∧ B) (¬A) (A → B) : si A
[PDF] Théorème de complétude du calcul propositionnel
Proposition 1 1 (Theorème de compacité du calcul propositionnel) Soit Σ un noté Σ ∼A, s'il existe une démonstration formelle (ou preuve formelle) de A à
[PDF] Calcul Propositionnel - DI ENS
Les phrases (ou formules) du calcul propositionnel sont des suites de symboles qui Nous donnons maintenant une définition plus formelle de l'évaluation
[PDF] Calcul propositionnel
une variable propositionnelle p ∈ P ; 2 ¬G, où G est une formule propositionnelle ; 3 (G ∧ H) où G et H sont des formules propositionnelles ;
[PDF] a la logique 1 Introduction 2 Calcul propositionnel informel
Une formule propositionnelle est une tautologie si sa fonction de vérité ne D´ EFINITION 3 1 Un syst`eme formel L du calcul propositionnel est défini comme :
[PDF] Logique Calcul Propositionnel - Laboratoire de Recherche en
6 oct 2015 · En lien avec la leçon : 916-Formules du calcul propositionnel : représentation, formes Langages Formels Calculabilité et Complexité Vuibert
[PDF] le resultat d'une 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] calcul taux d'évolution annuel moyen excel
[PDF] taux d'évolution successif
[PDF] imc 22 femme
[PDF] tableau imc femme
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)); 3Pourchaque formule!
i 1 2 31.dessinezsonarbresyntaxique;
2.énumérezsessous-formules ;
3.énumérezlessymboles propositionnelsayantune occurrencedans!
iSÉ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 01000111
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 n4.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 2CalculPropositionnel -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 ».