[PDF] Introduction à la logique : corrigé de quelques exercices

View - Download Introduction à la logique : corrigé de quelques exercices

Previous PDF

Next PDF

Introduction à la logique : corrigé de quelques exercices

Brice Halimi

LLPHI133

Exercice 1.Montrer que?

n=0,1,...F n=? n=0,1,...N n. RéponseRappelons queNnest l"ensemble des propositions exactement de niveaun, et queF0=N0,F1=N0?N1, ...Fn=N0?N1?N2?...?Nn, c"est-à-dire queFnest l"ensemble des formulesde niveau0,1,...,n. Pour touti,Fn=Nn? ..., doncNn?Fn, et donc? n=0,1,...F n?? n=0,1,...N n. Il faut montrer l"inclusion réciproque. MaisFn=? i=0,1,...,nN n, doncFn?? i=0,1,...N i, et ce pour toutFn. Donc n=0,1,...F n?? i=0,1,...N i=? n=0,1,...N n. Exercice 2.(p→q)→(q→r)est-elle une proposition? Et((p→q))? Et (p→q?r)? extérieures. La deuxième non plus car il y a trop de parenthèses extérieures. La troisième non plus car il faudrait écrire((p→q)?r)ou bien(p→(q?r)).

Exercice 3.

Exercice 4.¬¬pest-elle une proposition de niveau 1 ou de niveau 2? Y a-t-il un rapport entre le niveau d"une proposition et le nombre de lettres différentes qu"elle contient? RéponseUne proposition de niveau 2 :p= niveau 0,¬p= niveau 1,¬¬p= niveau 2. Non il n"y a pas de rapport, car on peut fabriquer une proposition de n"importe quel niveaunavec une seule lettre, à savoir¬¬...¬¬p(avecnfois le connecteur de négation). 1 nablement des parenthèses àp?q→r?p? RéponseIl y a(p?((q→r)?p)),(p?(q→(r?p))),((p?q)→(r?p)). Exercice 6.Est-ce qu"on peut dire qu"une proposition de niveaun, c"est une proposition qui comportenconnecteurs? RéponseNon,((p?q)→(p?q))est de niveau 2 ((p?q)et(p?q)sont chacune de niveau 1), mais comporte 3 connecteurs.

Exercice 7.h(((p?q)→(q→(r?p))))=?

RéponseL"arbre de décomposition donne :h= 3.

Exercice 8.l(((p?q)→(q→(r?p))))=?

Réponsel= 17.

Exercice 9.Montrer par induction que toute formule a autant de parenthèses ouvrantes que de parenthèses fermantes. (La propriétéπ(φ)à considérer sera donc ici : "o(φ) =f(φ)», oùo(φ)= nombre de parenthèses ouvrantes dansφet f(φ)= nombre de parenthèses fermantes dansφ.) RéponseLa propriétéπest évidemment vraie de toute proposition simple, puisqu"une proposition simplepne comporte ni parenthèse ouvrante, ni parenthèse fermante : op) =f(p) = 0. Soitφune expression ayant le même nombre de parenthèses ouvrantes et fer- mantes. Alors le passage à¬φne cahnge rien. Supposons que deux expressionsφetψaient chacune le même nombre de parenthèses ouvrantes et fermantes. COnsidérons alors(φ?ψ): le nombre de parenthèses ouvrantes dans cette expression vaut :1+o(φ)+o(ψ), et le nombre de parenthèses fermantes dans cette expression vaut :f(φ)+f(ψ)+1. Par hypothèse d"induction, on a :o(φ) =f(φ)(1) eto(ψ) =f(ψ)(2). On déduit de façon évidente de (1) et de (2) que1 +o(φ) +o(ψ) =f(φ) +f(ψ) + 1, et par suite que(φ?ψ)aautant de parenthèses ouvrantes que de parenthèses fermantes. Le raisonnement est rigoureusement le même pour(φ?ψ)et(φ→ψ).

Exercice 10.

2 Exercice 11.Écrireφ[ψ/p]pourφ= (p→(q?p))etψ= (q→p). Écrireφ[ψ1/p1,...ψn/pn]pourφ= (((p1?p2)?p3)?...?pn))etψi=pi+1 pouri= 1,2,...n-1etψn=p1. Réponseφ[ψ/p] = (ψ→(q?ψ)) = ((q→p)→(q?(q→p))). φ[ψ1/p1,...ψn/pn] = ((((((p2?p3)?p4)?...)?pn)?p1))

Exercice 12.

Exercice 13.Écrire la table de vérité de la formuleφ= (((p?q)?¬q)→(p?r)). RéponseOn peut faire la table de vérité "à la main», mais on peut aussi remarquer que l"antécédent((p?q)? ¬q)revevra toujours la VVV, sauf sipest faux etqvrai, et que(p?r)est faux seulement sipetrsont faux. Donc la propositionφreçoit la VVFsi et seulement si((p?q)?¬q)reçoit la VVV(càd sipest vrai ouqest faux) et quepetrsont faux, donc si et seulement sip,qetrsont faux. Dans tous les autres casφreçoit la VVV.

Exercice 14.

Exercice 15.Remarquer queφ≡ψsi et seulement si n"importe quelle ddvv

donne la même VV àφet àψ, autrement dit siφetψont la même table de vérité.

RéponseLa table de vérité de(p↔q) = ((p↔q)?(q↔p))est :

pq(p→q)(q→p)(p↔q)VVVVVVFFVFFVVFFFFVVVCette table de vérité suffit à résoudre l"exercice 15 du cours : on voit que(p↔q)

obtient la valeur de véritéVsi et seulement sipetqont la même valeur de vérité (qu"il s"agisse deVou deF). Par conséquent si deux propositionsφetψont

toujours la même valeur de vérité, alors(φ↔ψ)sera toujours vraie, c"est-à-dire

une tautologie. Et réciproquement(φ↔ψ)ne peut être une tautologie que siφet

ψont la même table de vérité.

Exercice 16.Montrer que :

-|= (p? ¬p) -|= (p→p) -|= (p→(p?q)) 3 -|= (p→(q→p)) -(p?p)≡p -(p?q)≡(q?p) -(p→q)≡(¬p?q) -(p?(q?r))≡((p?q)?(p?r)) RéponseLes deux premiers cas sont triviaux, on peut les traiter directement. Par exemple, sipest vrai alors(p?¬p)l"est, et sipest faux, alors¬pest vrai et donc (p? ¬p)est à nouveau vrai. Les deux cas suivants ainsi que les deux derniers se règlent au moyen d"une table de vérité. (Dans le quatrième cas on peut ramrquer que la proposition est fausse seulement à condition quepsoit vrai et(q→p)faux; or sipest vrai (q→p)ne peut être faux.) Le cas 5) est évident. Le cas 6) également, en remarquant que dans la construc- tion de la table de vérité dep?q petqjouent des rôles symétriques. Exercice 17.Démontrer le théorème 0.2, qui est une conséquence immédiate du théorème 0.1. RéponseThéorème 0.1.Soitφ(p1,...,pn)une tautologie. Alors, pour n"importe quelles propositionsχ1,...,χn,

φ[χi/pi]

est encore une tautologie. Théorème 0.2.Soient deux propositionsφ(p1,...,pn)etψ(p1,...,pn), et soient

1,...,χnnpropositions. Alors :

siφ≡ψ, alorsφ[χi/pi]≡ψ[χi/pi]. Siφ≡ψ, cela signifie que(φ↔ψ)est une tautologie, et par conséquent

(d"après le théorème 0.1)(φ↔ψ)[χi/pi] = (φ[χi/pi]↔ψ[χi/pi])est une tauto-

logie, autrement dit queφ[χi/pi]≡ψ[χi/pi]. Exercice 18.Montrer que les propositions suivantes sont des tautologies : -(((φ→ψ)?φ)→ψ)("modus ponens») -(((φ→ψ)? ¬ψ)→ ¬φ)("modus tollens») 4

Montrer les équivalences suivantes :

RéponseDans chaque cas, on écrit la table de vérité de la tautologie en remplaçant "φ» parp(ou bien en faisant comme siφétait une proposition simple), et ensuite appliquer le théorème 0.1 : si|= (p? ¬p), alors|= (φ? ¬φ)(pour n"importe quelle propositionφ). Et de même pour les autres tautologies de la liste. Si l"on doit montrer des équivalences plutôt que des tautologies, c"est le théorème 0.2 (et non plus 0.1) qu"on applique, mais le principe est le même. NB : on pourra se reporter au devoir pour des exemples corrigés de tables de vérité. 5quotesdbs_dbs1.pdfusesText_1

[PDF] initiation ? la philosophie

[PDF] initiation ? la traduction pdf

[PDF] initiation algorithmique seconde

[PDF] initiation au dessin technique pdf

[PDF] initiation au génie civil

[PDF] initiation au marketing pdf

[PDF] initiation biologie sous marine

[PDF] initiation comptabilité gratuit

[PDF] initiation elongation terminaison

[PDF] initiation excel 2010 pdf

[PDF] initiation outlook 2010 pdf

[PDF] initiation paniculaire

[PDF] initiation pratique ? la méthodologie des sciences humaines maurice angers pdf

[PDF] initiation windows 10 pdf

[PDF] initiative nationale pour le développement humain au maroc pdf