[PDF] [PDF] Logique

[PDF] Chapitre 4 Quelques types de raisonnement

Montrer une implication 3 1 Méthode directe Soit deux assertions P et Q On veut montrer que l'assertion P =⇒ Q est vraie Si P est fausse, l'assertion P =⇒ Q  

[PDF] Le raisonnement mathématique Limplication, une notion polysémique

Le raisonnement mathématique L'implication, une notion polysémique Nous présentons des résultats à deux items d'un questionnaire que nous avons 

[PDF] BASES DU RAISONNEMENT

10 sept 2006 · Implication Si P et Q sont des assertions, l'assertion P ⇒ Q exprime l'idée que si P est vraie, alors Q doit être vraie aussi, sans qu'il y ait pour 

[PDF] Logique

3 5 1 Définition de l'implication logique 3 5 3 Négation, contraposée et réciproque d'une implication 5 3 Le raisonnement par contraposition

[PDF] Feuille dexercices no 2 1 Implication, réciproque, contraposée

La seule façon de démontrer qu'une implication est fausse (par exemple, pour dans un raisonnement : en effet, quand nous savons qu'une implication A ⇒ B 

[PDF] Feuille dexercices 3 Logique et raisonnement - Licence de

est impair, alors est impair Exercice 4 1 Montrer la transitivité de l' implication, c'est-à-dire que, pour toutes propositions  

[PDF] raisonnement par équivalence définition

[PDF] raisonnement par l'absurde exercices

[PDF] fiche de revision geographie 3eme

[PDF] polarité des molécules exercice

[PDF] exercice polarité 1s

[PDF] hcl polaire ou apolaire

[PDF] molécule polaire exercice corrigé

[PDF] exemple de raisonnement par analogie

[PDF] pcl3 polaire

[PDF] taille organite

[PDF] relation entre couleur et structure chimique des pigments et colorants organiques

[PDF] fiche révision brevet physique chimie

[PDF] les molécules d'adhésion cellulaire

[PDF] fiche de révision brevet histoire nathan

[PDF] fiche sur les suites 1ere s

ECE1-B2015-2016CH I : Logique et raisonnements mathématiques Dans ce chapitre, on introduit la syntaxe et la sémantique d"éléments de base du langage mathématique. L"objectif est double : pouvoir comprendre et écrire des phrases mathématiques simples, donner des bases rigoureuses afin de pouvoir démontrer ce type de phrases mathématiques.

I. Propositions mathématiques

DéfinitionProposition mathématique

On appelleproposition mathématiqueun énoncé auquel on peut attri- buer une valeur de vérité (vrai ou faux).

Exemple

Les énoncés suivants sont des propositions mathématiques. a)1 + 1 = 2

Cette proposition

est vraie.b)1 + 1 = 3

Cette proposition

est fausse.c)ln(1) = 1

Cette proposition

est fausse.

Par contre,1 + 12et(p18)

3ne sont pas des propositions puisqu"on ne

peut leur attribuer de valeur de vérité. Ce sont des expressions arithmé- tiques dont le résultat est un réel. Il est à noter qu"une proposition mathématique peut comporter des va- riables. En conséquence, il est possible que la valeur de vérité d"une propo- sition dépende du choix de ces variables.Exemple Les énoncés suivants sont des propositions dont la valeur de vérité dépend du choix des variables. a)x+ 2>4 cette proposition est vraie pour toutxplus grand que2, cette proposition est fausse sinoni.e.pour toutxstrictement infé- rieur à2. b)px 2=x cette proposition est vraie pour toutxplus grand que0, cette proposition est fausse sinoni.e.pour toutxstrictement infé- rieur à0. c)px

2+y2=x+y

Pour connaître la valeur de vérité cette proposition, on aimerait la sim- plifier, en commençant par se débarrasser de l"opérateurp: Une telle démarche est périlleuse : si on reprend la proposition précé- dente :px

2=x, une élévation au carré de part et d"autre du symbole

d"égalité fournit l"expression :x2=x2, qui est vraie pour toutxréel! L"élévation au carré n"est donc pas un opérateur neutre en terme de valeur de vérité (nous reviendrons plus tard sur ce point). Sans entrer dans les détails, on peut remarquer que : six= 0, la proposition est vraie pour touty>0, siy= 0, la proposition est vraie pour toutx>0, six <0ety <0, la proposition est fausse. Par contre,10x(py)n"est pas une proposition. C"est une expression arithmétique dont le résultat est un réel. On peut nommer une proposition. Si elle dépend d"une variable explici- tement donnée, on fera apparaître cette dépendance. Par exemple, on pourra noterp(x;y)la propositionpx

2+y2=x+y.1

ECE1-B2015-2016II. Connecteurs logiques

II.1. Conjonction

DéfinitionConjonction

Soientpetqsont deux propositions mathématiques.

On notepETqla proposition qui est :

vraie quandpetqsont simultanément vraies, fausse sinon. Autrement dit, une conjonctionpETqest fausse si (au moins) l"une des deux propositionspouqqui la compose est fausse. L"opérateurETpermet de combiner deux propositions pour former une nouvelle proposition.

Exemple

Les énoncés suivants sont des propositions mathématiques. a)(x+ 2>4)ET(1 + 1 = 3) La proposition1 + 1 = 3étant fausse indépendamment de la vealeur de x, cette conjonction est fausse pour toutxréel. b)(1 + 1 = 2)ET(x+ 2>4) cette proposition est vraie pour toutx>2, cette proposition est fausse sinoni.e.pour toutx <2.

II.2. Disjonction

DéfinitionDisjonction

Soientpetqsont deux propositions mathématiques.

On notepOUqla proposition qui est :

fausse quandpetqsont simultanément fausses, vraie sinon. Autrement dit, une disjonctionpOUqest vraie si (au moins) l"une des deux propositionspouqqui la compose est vraie. L"opérateurOUpermet de combiner deux propositions pour former une nouvelle proposition.Exemple Les énoncés suivants sont des propositions mathématiques. a)(x+ 2>4)OU(1 + 1 = 3) La proposition1+1 = 3étant fausse indépendamment de la valeur dex, cette disjonction est : vraie lorsque(x+ 2>4)l"esti.e.pour toutx>2, fausse sinoni.e.pour toutx <2. b)(1 + 1 = 2)OU(x+ 2>4) La proposition1 + 1 = 2étant vraie indépendamment de la valeur dex, cette disjonction est vraie pour toutxréel.

Remarque

Il ne faut pas confondre cette définition duOUavec celle utilisée dans le langage naturel. En effet, lorsqu"on vous demande au restaurant si vous sou- haitez du fromage ou du dessert, le serveur retire implicitement la possibilité de vous apporter les deux. Le " ou » du langage naturel correspond en fait auXOR(" ou » exclusif). Pourpetqdeux propositions,pXORqest vérifiée si seulement l"une des deux propositionspetqest vraie et fausse sinon.

Propriétédes opérateursETetOU

1)pET(qOUr)a même valeur de vérité que(pETq)OU(pETr)

2)pOU(qETr)a même valeur de vérité que(pOUq)ET(pOUr)

(dire que deux propositionsaetbont même valeur de vérité signifie qu"elles sont fausses en même temps et qu"elles sont vraies en même temps)

Démonstration.

Nous traitons seulement le1), le2)est laissé en exercice. Pour montrer que deux propositionsaetbont même valeur de vérité, nous allons procéder comme suit : (i)nous montrons que siaest vraie alorsbl"est aussi. (ii)nous montrons que siaest fausse alorsbl"est aussi.2 ECE1-B2015-2016Ceci démontre que les propositions sont vraies en même temps et fausses en même temps. Revenons à la démonstration consistant à démontrer quepET(qOUr)a même valeur de vérité que(pETq)OU(pETr). (i)Supposons quepET(qOUr)est vraie. Ceci signifie que les propositionspetqOUrsont vraies toutes les deux. Ainsi, l"une (au moins) des propositionsqourest vraie. On procède alors par disjonction de cas sur la valeur de vérité (par exemple) deq. siqestvraie : alorspETqest vraie.

Ainsi, la proposition(pETq)OU(pETr)est vraie.

siqestfausse : alors commeqOUrest vraie,rest forcément vraie.

On en déduit quepETrest vraie.

Ainsi, la proposition(pETq)OU(pETr)est vraie.

La proposition(pETq)OU(pETr)est donc vraie (puisque vraie indé- pendamment de la valeur deq). (ii)Supposons quepET(qOUr)est fausse. Ceci signifie que l"une (au moins) des propositionspouqOUrest fausse. On procède alors par disjonction de cas sur la valeur de vérité (par exemple) dep. sipestvraie : alorsqOUrest fausse. Ainsi,qetrsont fausses.

On en déduit quepETqetpETrsont fausses.

Ainsi, la proposition(pETq)OU(pETr)est fausse.

sipestfausse : alorspETqest fausse etpETrest fausse.

Ainsi, la proposition(pETq)OU(pETr)est fausse.

La proposition(pETq)OU(pETr)est donc fausse (puisque fausse indépendamment de la valeur dep).Remarque

Notez que(i)et(ii)permettent d"affirmer que :

(ii")sibest vraie alorsaest vraie. Si on supposebvraie, alors, siaétait fausse, à l"aide de(ii)on pourrait conclure quebest fausse, ce qui contredit l"hypothèse "b est vraie ». (i")siaest fausse alorsbest fausse. Si on supposeafausse, alors, sibétait vraie, à l"aide de(i)on pourrait conclure quebest vraie, ce qui contredit l"hypothèse "aest fausse ». Réciproquement, en raisonnant de même, on peut prouver que(ii")permet de démontrer(ii)et(i")permet de démontrer(i). On en conclut que l"on peut remplacer(i)par(i")et(ii)par(ii")lorsque l"on souhaite démontrer que deux propositions ont même valeur de vérité.

II.3. Négation

DéfinitionNégation

Soitpune proposition mathématique.

On noteNON(p)la proposition qui est :

vraie lorsquepest fausse, fausse lorsque quepest vraie.

Exemple

a)NON(x+ 2>4)est une proposition qui est : vraie six+ 2>4est faussei.e.si pour toutxtel quex+ 2<4, fausse six+ 2>4est vraiei.e.si pour toutxtel quex+ 2>4. En fait,NON(x+ 2>4)a même valeur de vérité que(x+ 2<4). b)De même,NON(px

2=x)a même valeur de vérité que(px

26=x).3

ECE1-B2015-2016Propriétéde la négation

1)NON(pETq)a même valeur de vérité que(NON(p)OU NON(q)).

2)NON(pOUq)a même valeur de vérité que(NON(p)ET NON(q)).

3)NON(NON(p))a même valeur de vérité quep.

Les énoncés1)et2)sont appelées lois de De Morgan.

Démonstration.

1) (i) Supposons queNON(pETq)est vraie. AlorspETqest fausse. Ainsi, l"une (au moins) des deux propositions pouqest fausse. On procède alors par disjonction de cas sur la valeur de vérité (par exemple) dep. sipestvraie : alorsqest fausse.

On en déduit queNON(q)est vraie.

Ainsi, la proposition(NON(p)OU NON(q))est vraie.

sipestfausse : alorsNON(p)est vraie.

Ainsi, la proposition(NON(p)OU NON(q))est vraie.

La proposition(NON(p)OU NON(q))est donc vraie (puisque vraie indé- pendamment de la valeur de vérité dep. (ii)Supposons queNON(pETq)est fausse. AlorspETqest vraie. Ainsi, les deux propositionspetqsont vraies. On en déduit queNON(p)etNON(q)sont fausses toutes les deux.

Ainsi, la proposition(NON(p)OU NON(q))est fausse.

2)Laissé en exerice.

3) (i) SiNON(NON(p))est vraie alorsNON(p)est fausse et doncpest vraie. (ii)SiNON(NON(p))est fausse alorsNON(p)est vraie et doncpest fausse.II.4. Implication II.4.a) Définition et schéma de démonstration

DéfinitionImplication

Soientpetqdeux propositions mathématiques.

On notep)qla proposition qui est :

vraie siqest vraie à chaque fois quepl"est, fausse sinon. Lorsque la propositionp)qest vraie, on dira quepimpliqueq(la pro- positionpentraîne la propositionq). L"implicationq)pest appeléeréciproquede l"implicationp)q.

Lorsquepimpliqueq, on dira que :

pest unecondition suffisantedeq: en effet, pour que la proposition qsoit vraie, il suffit queple soit. qest unecondition nécessairedep: en effet, pour quepsoit vraie, il est nécessaire queqle soit. (siqn"est pas vraie alorspne peut être vraie : sinon, commep)q, la propositionqserait vraie!)

Schéma de démonstration

Pour montrera)b, on peut opter pour la démonstration directe. Ceci consiste à montrer quebest vraie dès queal"est. On rédigera comme suit.

Démo dea)bpar méthode directeSupposonsa.

Alors ...(démo dépendant dea)...et doncb.

Ce qui démontrea)b.4

ECE1-B2015-2016Application sur un exemple

PropriétéTransitivité de l"implication

Soientp,qetrdes propositions mathématiques.((p)q)ET(q)r)))(p)r)Cet énoncé se lit :sipimpliqueqetqimpliqueralorspimpliquer.

Démonstration.

Si on reprend le schéma de démonstration précédent, le rôle deaest ici joué par(p)q)ET(q)r)et le rôle debest joué parp)r.

Supposons que(p)q)ET(q)r)est vraie.

Démontrons alors quep)rest vraie.

On suppose quepest vraie.

Comme(p)q)ET(q)r)est vraie,p)qetq)rle sont aussi.

commepest vraie etp)q, la propositionqest vraie, commeqest vraie etq)r, la propositionrest vraie. Ce qui démontrep)qet termine la démonstration.Remarque Mettons en avant deux éléments de la définition : si l"on sait quepimpliqueqet quepest vraie, alors on a forcémentq. si l"on sait quepimpliqueqet quepest fausse, il faut bien comprendre que la définition n"impose rien quand à la valeur de vérité deq. Pour bien comprendre ce mécanisme, étudions l"énoncé suivant : "s"ilfait beaualorsj"irai au parc »

Deux cas se présentent :

soit il fait beau et je me dois d"aller au parc. soit il ne fait pas beau. Dans ce cas, j"ai le choix. Soit je décide malgré tout d"aller au parc (avec mon parapluie), soit je décide de rester chez moi : cela ne remet pas en cause la véracité de l"énoncé précédent.

À retenir :pimpliqueqcorrespond à l"énoncé "sipalorsq».II.4.b) Contraposée et schéma de démonstration associé

PropriétéContraposée

Soientpetqsont deux propositions mathématiques. Les propositionsp)qetNON(q))NON(p)ont même valeur de vérité. La propositionNON(q))NON(p)est appeléecontraposéedep)q.

Soitpetqdeux propositions.

Il ne faut surtout pas confondre les propositions : q)p: la proposition réciproque dep)q. NON(q))NON(p): la proposition contraposée dep)q.Schéma de démonstration Démontrera)bpar contraposée consiste à démontrer que la proposition (équivalente)NON(b))NON(a)est vraie.

Démo dea)bpar contraposéeSupposonsNON(b).

Alors ...(démo dépendant deb)...et doncNON(a).

Ce qui démontrea)b.Exercice

Pourxélément deR, montrer que :((8">0);x6"))x60.

On procédera par contraposée.

Exercice

Soitn2N. Montrer par contraposée que sin2est pair alorsnest pair. Intérêt de la démonstration par contraposée Pour démontrerp)q, il est parfois utile de partir d"une hypothèse surq (supposerNON(q)en l"occurrence) pour démontrer un but dépendant dep (montrerNON(p)). C"est ce que permet le raisonnement par contraposée.5 ECE1-B2015-2016II.4.c) Expression dep)qà l"aide des opérateursNONetOU

Propriété

Soientpetqsont deux propositions mathématiques. La propositionp)qa même valeur de vérité que la propositionNON(p)OUq.

Démonstration.

Pour démontrer que ces deux propositions ont même valeur de vérité, nous montrons les points(i)et(ii"). (i)Supposons que la propositionp)qest vraie. Procédons par disjonction de cas sur la valeur de vérité dep. sipestvraie : alors, commep)q, on a queqest vraie.

Ainsi,NON(p)OUqest vraie.

sipestfausse : alorsNON(p)est vraie. Ainsi,NON(p)OUqest vraie. (ii")Supposons que la propositionNON(p)OUqest vraie.

Démontrons alors quep)qest vraie.

Supposons quepest vraie.

AlorsNON(p)est fausse.

CommeNON(p)OUqest vraie, on peut donc conclure queqest vraie. On a donc démontré quep)qest vraie.Application : négation dep)q

Propriété

Soientpetqsont deux propositions mathématiques. La propositionNON(p)q)a même valeur de vérité que la proposition pET NON(q).

Démonstration.

La propositionNON(p)q)a même valeur de vérité queNON(NON(p)OUq). De plus,NON(NON(p)OUq)a même valeur de vérité quepET NON(q).Exercice On considère la proposition " s"il pleut, mon jardin est mouillé ».

Quelle est sa négation?

a." s"il ne pleut pas, mon jardin n"est pas mouillé » b." s"il ne pleut pas, mon jardin est mouillé » c." s"il pleut, mon jardin n"est pas mouillé » d." si mon jardin n"est pas mouillé, il ne pleut pas » e." il pleut et mon jardin n"est pas mouillé » f.autre réponse.

II.5. L"opérateur d"équivalence

II.5.a) Définition et schéma de démonstration

DéfinitionÉquivalence

Soientpetqsont deux propositions mathématiques.

On notep,qla proposition qui est :

vraie sip)qetq)psont vraies, fausse sinon. Lorsquep,qest vraie, on dira quepestéquivalentq.

Remarque

Lorsquepest équivalent àqon a :

pimpliqueqdoncpest une condition suffisante deq. (qest une condition nécessaire dep) qimpliquepdoncpest une condition nécessaire deq. (qest une condition suffisante dep) On dira donc quepest unecondition nécessaire et suffisantedeq (qest une condition nécessaire et suffisante dep) ou encore quepest vraiesi et seulement siqest vraie.6 ECE1-B2015-2016Dire quepest équivalent àqrevient à dire quepetqont même valeur de vérité. En effet : le point(i)revient à démontrerp)q, le point(ii")revient à démontrerq)p.

Exemplesprécédents

Soientp,qetrdes propositions mathématiques.

1)pET(qOUr),(pETq)OU(pETr)2)pOU(qETr),(pOUq)ET(pOUr)3)NON(pETq),NON(p)OU NON(q)4)NON(pOUq),NON(p)ET NON(q)5)NON(NON(p)),pSchéma de démonstration

Démontrer quea,bconsiste à démontrer tout d"abord quea)bi.e.que aest une condition suffisante deb(sens direct) puis queb)ai.e.queaest une condition nécessaire deb(sens réciproque). On dit alors qu"on procède pardouble implication. Démo dea,bpar double implication()) Supposonsa. On a alors ...(démo dépendant dea)...et doncb.

Ce qui démontrea)b.

(() Supposonsb. On a alors ...(démo dépendant deb)...et donca.

Ce qui démontreb)a.

Et ainsi,a,b.II.5.b) Négation d"une équivalence La propostionNON(p,q)est équivalente àNON(p)qETq)p), qui est elle-même équivalente àNON(p)q)OU NON(q)p). Ainsi, démontrer quep,qn"est pas vérifié revient à démontrer que l"une (au moins) des deux implicationsp)qetq)pn"est pas vérifiée.

III. Quantificateurs

III.1. Quantificateur universel

DéfinitionQuantificateur universel

SoitEun ensemble, etpune proposition comportant une variablex.

On note8x2E; p(x)la proposition qui est :

vraie si pour tout élémentxde l"ensembleE,p(x)est vraie, fausse sinon. Autrement dit qui est fausse s"il existe au moins un élémentxde l"en- sembleEtel que la propositionp(x)est fausse. Lorsque(8x2E; p(x))est vraie, on dit que quelque soitxélémentE(ou pour tout élémentxdeE),p(x)est vérifiée.

Schéma de démonstration

Pour démontrer un énoncé universellement quantifiéi.e.un énoncé du type (8x2E; p(x)), il faut rédiger comme suit.

Démo de8x2E; p(x)Soitxélément deE.

Alors ...(démo dépendant dep)...et doncp(x)est vraie. Ceci démontre quep(x)est vraie pour toutxdeE.Exercice

Démontrer que :8x2R;(x+ 2)2=x2+ 4x+ 4.7

ECE1-B2015-2016III.2. Quantificateur existentiel

DéfinitionQuantificateur existentiel

SoitEun ensemble, etpune proposition comportant une variablex.

On note9x2E; p(x)la proposition qui est :

vraie s"il existe au moins un élémentxde l"ensembleEtel que la pro- positionp(x)est vraie. fausse sinon. Autrement dit qui est fausse s"il n"existe aucun élémentxdeEtel que la propositionp(x)est vraie.

On note aussi9!x2E; p(x)la proposition qui est :

vraie s"il existeun uniqueélémentxde l"ensembleEtel que la propo- sitionp(x)est vraie. fausse sinon.

Autrement dit qui est fausse :

-soit s"il n"existe aucun élémentxdeEtel quep(x)est vraie, -soit s"il existe (au moins) deux éléments deEqui satisfontp.

Schéma de démonstration

Démontrer un énoncé existentiellement quantifiéi.e.un énoncé du type(9x2 E;p(x))consiste à exhiber un élémentadeEqui vérifie la propositionp. Autrement dit, un élément tel quep(a)est vraie.

Exemple

Pour démontrer la proposition :9x2R; x2= 3, il suffit d"exhiber unxréel tel que son carré vaut3. On peut prendre par exemplex=p3.quotesdbs_dbs16.pdfusesText_22