[PDF] 4.2. Tableau de vérité. Nous présentons ces définitions en forme de

View - Download 4.2. Tableau de vérité. Nous présentons ces définitions en forme de

Previous PDF

Next PDF

4.2.Tableau de vérité.Nous présentons ces définitions en forme de tableaux de vérité, où

V:=vrai, et F:=faux.

Pour la négation:p¬pVF

FV

Pour les autres définitions:

p qp?qp?qp?qp→qp↔qV VVFVVV

V FVVFFF

F VVVFVF

F FFFFVV

4.3.Propositions logiques composées.Commençons maintenant à combiner. Sip,qetrsont

trois propositions logiques, alors

P:= ((¬q)?(p?r))→p

est aussi une proposition logique. La valeur de vérité dePdépend des valeurs de vérité dep,

qetr. Comment exactement montre le tableau suivant (qui montre aussi des calculs de vérité intermédiaires) :p q r¬q p?r(¬q)?(p?r)((¬q)?(p?r))→pV V VF V FV

V V FF V FV

V F VV V VV

V F FV V VV

F V VF V FV

F V FF F FV

F F VV V VF

F F FV F FV

En regardant la dernière colonne on se rend compte quePest faux si et seulement sipest faux etqest faux etrest vraie, ou en formule que (¬p)?((¬q)?r)) est vraie.

Ou quePest vraie si et seulement si

¬((¬p)?((¬q)?r))

est vraie. PosonsQ:=¬((¬p)?((¬q)?r))et calculons de nouveau ses valeurs de vérité : 19 20 p q r¬p¬q(¬q)?r) ((¬p)?((¬q)?r))Q

V V VF F F FV

V V FF F F FV

V F VF V V FV

V F FF V F FV

F V VV F F FV

F V FV F F FV

F F VV V V VF

F F FV V F FV

Considérons aussi la propositionR=p?(q?(¬r). On peut aussi calculer son tableau.p q rPQR

V V VVVV

V V FVVV

V F VVVV

V F FVVV

F V VVVV

F V FVVV

F F VFFF

F F FVVV

Conclusion : les propositions composéesP,QetRont la même valeur de vérité, n"importe les valeurs dep,q,r. On ditP,QetRsont des propositions composées (ou formules logiques) logiquement équivalentes. Calculons aussi les vérités de la propositionP↔Q:p q rP QP↔QV V VV VV

V V FV VV

V F VV VV

V F FV VV

F V VV VV

F V FV VV

F F VF FV

F F FV VV

On voit que la proposition logique composéeP↔Qest toujours vraie, pour tous les valeurs de vérité dep,qetr. On ditP↔Qest unetautologie, notationP?Q.

4.4.Tautologie et contradiction.Nous généralisons.

Définition 4.2.Une proposition logique composée (ou une formule logique) qui est toujours vraie,

quelles que soient les valeurs de vérité des propositions qui la composent, est appelée une tautologie.

Notation :P?V.

Par exemple:p?(¬p)?Vet((p?q)→(p?q))?V.

21

Définition 4.3.Une proposition logique composée (ou une formule logique) qui est toujours fausse,

quelles que soient les valeurs de vérité des propositions qui la composent, est appelée une contra-

diction. Notation :P?F

Par exemple :p?(¬p)?F.

Définition 4.4.Deux formules logiquesPetQsont appeléeslogiquement équivalentessi la propo- sition logiqueP↔Qest une tautologie. Notation :P?Q.

Par exemple:(p↔q)?[(p→q)?(q→p)].

Définition 4.5.SiP→Qest une tautologie, oùPetQsont deux formules logiques, on dit que P→Qest unerègle d"inférence. NotationP?Q.

Par exemple:(p?q)?q.

4.5.Propositions logiquement équivalents à l"implication.Considérons la proposition suiv-

ante.

Proposition 4.1.Les trois formules logiques "p→q", "(¬q)→(¬p)" et "(¬p)?q" sont logiquement

équivalentes. Ou

Proof.Nous vérifions par un tableau de vérité.p qp→q¬q¬p(¬q)→(¬p)(¬p?q)V VVF F VV

V FFV F FF

F VVF V VV

F FVV V VV

Les trois colonnes correspondantes sont identique. Donc la proposition est vraie.

4.6.Formules logiquement équivalentes.Donnons une petite reformulation. On pourrait voir

P=P(p,q,r), Q=Q(p,q,r), R=R(p,q,r)

comme trois formules ou comme trois fonctions qui dépendent des propositions logiquesp,q,r. Par exemple P:{propositions logiques}3→ {propositions logiques} où le triple de propositions(p,q,r)est envoyé vers la propositionP=P(p,q,r).

Par définition:PetQsont logiquement équivalentes si les fonctions composées avec la fonction

"vérité" deviennent identiques: SiAetBsont deux ensembles etb?Bun élément fixé, on peut définir lafonction constante,

souvent aussi notéb, comme la fonction qui associe à chaque élémenta?Ace même élémentb

(oub(a) =b). Dans le même sens nous considéronsVcomme la proposition composée (ou formule logique) qui a la valeur de véritéVn"importe les valeurs dep,q,r. Et de même pourF. 22

4.7.Équivalences logiques de base.Une première liste d"équivalences logiques utilisées tout le

temps : Théorème 4.1.Voici des équivalences logiques : p?V?p(Identité) p?F?p(Identité) p?V?V(Domination) p?F?F(Domination) p?p?p(Idempotence) p?p?p(Idempotence)

¬(¬p)?p(Loi de la double négation)

p?q?q?p(Commutativité) p?q?q?p(Commutativité) ((p?q)?r)?(p?(q?r))(Associativité) ((p?q)?r)?(p?(q?r))(Associativité)

¬(p?q)?((¬p)?(¬q))(Loi de De Morgan)

¬(p?q)?((¬p)?(¬q)(Loi de De Morgan)

Proof.La plupart des preuves est facile: il faut soi-même se convaincre! Nous donnons deux exemples de preuve par tableau : SiP:=p?(q?r)etQ:= (p?q)?(p?r)on ap q rq?r Pp?q p?r QV V VV VV V V

V V FF VV V V

V F VF VV V V

V F FF VV V V

F V VV VV V V

F V FF FV F F

F F VF FF V F

F F FF FF F F

EffectivementP?Q(un des deux lois de la distributivité). Montrons¬(p?q)?((¬p)?(¬q))(Loi de De Morgan). SoitP=¬(p?q)etQ= ((¬p)?(¬q)). On a 23
p qp?q P¬p¬q QV VV FF F F

V FF VF V V

F VF VV F V

F FF VV V V

EffectivementP?Q.

4.8.Preuve d"equivalences logiques par de l"algèbre.Remarquons tout d"abord que siP,Q

etRsont trois formules logiques (ou propositions composées) etP?QetQ?Ralors aussi P?R. (Et siP?Qalors aussiQ?P(c.-à.d., l"équivalence logique est symmétrique), et on a toujoursP?P.) Donc on peut enchaîner des équivalences logiques pour obtenir d"autres.

Nous avons déjà un certain nombre d"équivalence montrées, que nous pouvons utiliser. À la place

d"utiliser un tableau pour vérifier une équivalence logique, on peut aussi utiliser les petites règles

déjà montrées, comme en algèbre. Donnons un exemple. La proposition soi-même est sans importance. Proposition 4.2.SoitP:= ((¬q)?(p?r))→petQ:= (p?(q?(¬r))). On aP?Q. Proof.Nous allons utiliser une suite d"équivalences logiques (avec les raisons) ?(¬(¬q)? ¬(p?r)))?p(Selon De Morgan) ?(q? ¬(p?r)))?p(Double négation) ?(q?((¬p)?(¬r)))?p(Selon De Morgan) ?q?(p?((¬p)?(¬r)))(Assoc. et comm. pour?) ?q?((p?(¬p))?(p?(¬r)))(Distrib.) ?q?(V?(p?(¬r)))(Selon(p?(¬p))?V) ?q?(p?(¬r))(Selon comm. et(p?V)?p) ?Q(Assoc. et commut.)

Et voilà !

Chaque ligne est claire. Mais trouver la chaîne n"est pas si évidente. Remarque.On a vu beaucoup de()"s dans cette preuve. Parce quep?(q?r) = (p?q)?r, écrire p?q?r n"est pas ambigu. On supprime des()"s, qui sont dans ce cas superflus.

Ainsi pour

p?q?r On pose la convention que "¬" a uneplus haute prioritéque?ou?ou→ou ... 24
Donc¬p?qveut dire(¬p)?q(et pas¬(p?q), ce qui est vraiment différent).

Et¬p→qveut dire(¬p)→q.

Mais c"est ambigu d"écrire"p?q?r"et"p?q→r"; on n"a pas le droit d"écrire ça (il faut ajouter

des()"s pour clarifier ce qu"on veut vraiment). Nous ne posons pas de priorités entres les autres

opérations.Vous aussi êtes obligés d"évitez des ambiguïtés, en utilisant les()"s et[ ],s. Et à

chaque symbol "(" il faut correspondre un symbol ")".

4.9.Règles d"inference de base.Voici quelques règles d"inférence6utilisées tout le temps aussi.

Théorème 4.2.Les suivants sont des équivalences logiques. p?(p?q)(Addition) p?q?p(Simplification) [p?(p→q)]?p(Modus ponens) [¬q?(p→q)]?q?p(Modus tollens) [(p→q)?(q→r)]?(p→r)(Syllogisme par hypothèse) [(p?q)? ¬q]?p(Syllogisme disjonctif)

Proof.Aussi facile à montrer avec un tableau de vérité. Par exempleModus ponens:p qp→q p?(p→q)(p?(p→q))→pV VV VV

V FF FV

F VV FV

F FV FV

La dernière colonne contient seulement desV, donc correspond à une tautologie. SiP?QetQ?Ralors aussiP?R. (MaisP?Qn"implique pas en général queQ?P).

EtP?Qsi et seulement siP?QetQ→P.

Donc on peut composer des règles d"inférences, et obtenir d"autre règles d"inférence.

Par exemple.

Lemme 4.1.Une autre règle d"inférence :

(q?(¬p→ ¬q))?p. Proof.On combine(¬p→ ¬q)?(q→p)avec modus ponens (q?(¬p→ ¬q))?(q?(q→p))?p.

Cette règle d"inférence est utilisée dans une preuve par l"absurde, comme nous verrons plus tard.6

Voir [R, §3.1]

25

4.10.Fonctions propositionnelles et quantifications.Il y a des énoncés comme"n >2"qui

sont presque des propositions logiques mais qui contiennent des indéterminés (comme "n" dans

l"exemple). Du moment qu"on précise ces indéterminés elles deviennent des propositions logiques.

C"est donc vraiment une famille de propositions logiques. Par exemplep(n) := "n >2". C"est une famille de propositions logiques, dépendant de la variablenqui varie dans l"ensembleN. Icip(n)est fausse sin= 0,1ou2et vraie sinon (pour n?N).

SoitUun ensemble. Une fonction

p:U→ {propositions logiques} qui associe à chaqueu?Ula proposition logique p(u) s"appellefonction propositionnelleavecUcomme univers du discours de la variableu. Exemple: SoitUl"ensemble des hommes qui habitent Montréal etp(X) :="Xpeut patiner". SoitP(u)une fonction propositionnelle avecUcomme univers de discours de la variableu. On définit deux nouvelles propositions logiques vraies, les deuxquantifications.

On écrit

?u P(u) (ou?u:P(u)) pour la proposition logique: "P(u)est vraie pour tous les valeurs deusur son univers de discours", ou, "pour chaque valeurudans l"univers de discours la propositionP(u)est vraie". (On dit parfois: la quantification universelle.)

Dans l"exemple:

?X P(X)est une traduction logique de "Tous les hommes qui habitent Montréal peuvent patiner."

Et on écrit

?u P(u) (ou?u:P(u)) pour la proposition logique: "P(u)est vraie pour au moins une des valeurs deuchoisi dans son univers de discours", ou "il existe au une valeurudans l"univers de discours telle que la propositionP(u)est vraie". (On dit: parfois: la quantification existentielle.) Dans l"exemple:?X P(X)est une traduction logique de "Au moins un homme qui habite Mon- tréal peut patiner." Exemple: Sip(n) := "n >2"avec univers du discoursN. alors"?n n >2"est fausse (car au moinsp(1) = "1>2"n"est pas vraie); et"?n n >2"est vraie (car au moinsp(3) = "3>2"est vraie).

On remarque:

?u p(u)est vraie sip(u)est vraie pour chaqueu; ?u p(u)est fausse s"il existe au moins unutel quep(u)est fausse. Traduction

¬(?u p(u))? ?u(¬p(u))

26
?u p(u)est vraie s"il existe unutel quep(u)est vraie;?u p(u)est fausse si pour chaqueuon a quep(u)est fausse. Traduction:

¬(?u p(u))? ?u(¬p(u))

On formule ses résultats en forme d"une proposition. Proposition 4.3.SoitP(u)une fonction propositionnelle avecUcomme univers de discours de la variableu. Alors

¬(?u p(u))? ?u(¬p(u))

et

¬(?u p(u))? ?u(¬p(u)).

4.11.Utilisation dans les arguments et preuves mathématiques.On utilise les règles d"inférence

dans les arguments et dans les preuves. Typiquement (icipetqsont certains propositions logiques explicites) : Un petit argument comme le suivant est logiquement correct (par modus ponens) :"On apet aussi quepimpliqueq, donc on a aussiq", ce qui est une version courte pour:"La proposition logiquepest vraie et l"implicationp→qest vraie, alors automatiquement la proposition logiqueq est aussi vraie". Remarque.Si on dit en mathématique "on montrep", ça veut dire "on donne des arguments pour montrer que la proposition logiquepest vraie". C"est plus court. Ou un argument comme:"pimpliqueqetqimpliquer, alors nécessairementpimpliqueraussi",

ce qui est la version courte de"Les implicationsp→qetq→rsont vraies alors nécessairement

l"implicationp→rest aussi vraie"(par Syllogisme par hypothèse). Ou trivialement :"On saitpetq, donc en particulierp", ce qui courte pour :"On sait que les propositions logiquespetqsont vraie, doncpest vraie"(par Simplification). Ou:"On saitpouq, maisqest faux; donc nécessairementpest vraie,"est courte pour:On sait p?qest vraie, mais que la propositionqest fausse; alors la proposition logiquepest vraie.

Tout ça devrait paraître naturel.

Exercice4.1.(i) Mais comparer maintenant les deux "arguments" semblables suivants. "On sait quepimpliqueq, maispest faux; alorsqest aussi faux"(courte pour :On sait que l"implicationp→qest vraie et que la propositionpest fausse; alors la propositionqest fausse) et "On sait quepimpliqueq, maisqest faux; alorspest aussi faux"(courte pour :On sait que l"implicationp→qest vraie et que la propositionqest fausse; alors la propositionpest fausse).

La différence semble être petite, mais le premier argument est logiquementinvalide(car basée

sur une contre-vérité) et le deuxième argument est logiquement valide.

Trouver pourquoi.

(ii) Est-ce que l"argument suivant est valide: "On aqet queqest impliqué parp; alorsp.

La (contre-) vérité sous-entendue ?

27
(iii) Est-ce que vous acceptez :On sait queqest vraie, alors l"implicationp→qest vraie? (iv) Et :On sait quepest faux, alors l"implicationp→qest vraie? (v) Et :On sait que l"implicationp→qest faux, alorsqest vraie?

4.12.Preuve par contradiction.Soitpune proposition logique explicite, qu"on veut montrer

vraie. Une méthode est de supposer le contraire est vraie, alors quepest faux. Puis d"utiliser cet

hypothèse, et des théorèmes déjà montrés pour obtenir une contradiction ou une absurdité. On

conclut quepest vraie.

Encore une fois, comme un modèle.

Proposition 4.4.p

Structure d"une preuve par l"absurde typique.Montronsppar une preuve par l"absurde. Supposons par contre quepsoit fausse, c.-à-d que¬pvraie.

Puis en utilisant cet hypothèse¬p(et les théorèmes déjà montrés) on montre qu"une certain

proposition logique auxiliaire, disonsq, est aussi fausse (donc¬qest vrai). Puis on remarque que

c"était déjà connu (ou on avait déjà montré sans utiliser l"hypothèse queqest faux !) queqest

vraie. C"est absurde (ou une contradiction).

On conclut quepest vraie.

Remarque.C"est quoi le principe logique utilisé? Dans la preuve on montre en fait que l"implication

(¬p)→(¬q)est vraie et aussi queqest vraie. Par l"inférenceq?(¬p→ ¬q)?p(lemme 4.1) on

conclutpest vraie. Ce qu"on voulait montrer en effet. Par exemple, souventqest une proposition logique qui est évidemment vrai commeq= "3>2".

4.13.Preuves typique d"une implication.En mathématiques il faut souvent montrer des im-

plicationsp→q, oùpetqsont deux propositions logiques. Il y a trois versions. Voir par exemple

prop.3.2 7. Soientpetqdeux propositions logiques explicites en mathématiques, et on veut montrer quep impliqueq.

Théorème 4.3.p→q

Structure d"une preuve directe typique.Sipest fausse, l"implication est automatiquement vraie, donc il n"y a rien à montrer dans ce cas. (Cette phrase est souvent omise).

Supposonspest vraie. Puis (avec cette hypothèse et avec de l"aide des théorèmes déjà montrés),

on montre queqsera aussi vraie.

On aura montré quep→qest vraie.

Cette version est claire, j"espère. Une autre version: Structure d"une preuve indirecte typique.Il suffit de montrer sa contraposée(¬q)→(¬p).

Si¬qest faux (ouqest vraie), l"implication est automatiquement vraie et il n"y a rien à montrer.

(Cette phrase est souvent omise). Supposons¬qest vraie, c.-à-d,qest fausse. Puis (avec cette hypothèse et avec de l"aide des théorèmes déjà montrés), on montre quepsera aussi fausse, ou que¬pest vraie.7

Voir [R, p. 164]

28

On aura montré queP→Qest vraie.

Remarque.Cette version est basée sur l"équivalence logique:(p→q)?(¬q→ ¬p).Chacun con-

stitue la structure d"une preuve valide. Avec une preuve directe on peut travailler avec l"hypothèse

quePest vraie pour montrer qu"alorsQest aussi vraie. Mais de temps en temps il est plus facile de commencer avec l"hypothèse queQest faux pour montrer qu"alorsPest aussi faux. Structure d"une preuve par l"absurde typique.Montronsp→qpar une preuve par l"absurde. Sup- posons par contre quep→qest fausse, c.-à-d quepest vraie maisqest fausse.

Puis en utilisant ces deux hypothèses (quepest vraie etqfausse) (et les théorèmes déjà montrés)

on montre qu"un certain proposition logique auxiliaire, disonsr, est fausse (donc que¬rest vrai).

Puis on remarque que c"était déjà connu (ou on montre directement sans utiliser l"hypothèsep?¬q)

querest vraie. Ce qui est absurde (ou une contradiction).

On conclut quep→qest vraie.

Remarque.C"est une variation sur une preuve par l"absurde, ou l"énoncé à montrer estP:=p→q

(à la place dep). On a(p→q)?(¬p?q)et le contraire est¬(¬p?q)?p? ¬p(par De Morgan et double négation.

Différence entre la preuve directe, la preuve indirecte et la preuve par l"absurde pour montrer une

implicationp→q? Pour la preuve directe: on peut utiliser l"hypothèseppour montrer la conclusion

q. Pour la preuve indirecte: on peut utiliser l"hypothèse¬qpour montrer la conclusion¬p. Et pour une preuve par l"absurde: on peut utiliser deux hypothèses pour commencer le raisonnement

(pvraie etqfaux) pour dériver une absurdité (ou une contradiction). Ça dépend des propositions

explicitespetqet de vos connaissance d"autres théorèmes quel façon est préférable! Il y a aussi des fausse preuves, basées sur une contre-vérité. Considérons la "preuve": Structure d"une fausse preuve typique.Il suffit de montrer(¬P)→(¬Q)est vraie. Si¬Pest faux (ouPest vraie), l"implication est automatiquement vraie. Donc il n"y a rien à faire. Supposons¬Pest vraie, ouPest fausse. Puis (avec cette hypothèse et avec de l"aide des théorèmes déjà montrés), on montre queQsera aussi fausse,¬Qest vraie

On aura montré queP→Qest vraie.

Remarque.Pourquoi c"est unefaussepreuve (donc pas une preuve du tout), car c"est basée sur une

contre-vérité: les formules logiquesp→qet(¬p)→(?=q)ne sont pas logiquement équivalentes.

Une telle FAUSSE preuve est inacceptable. (En fait, ce qu"on montrerait vraiment en fait est la réciproqueq→p).

4.14.Si et seulement si.Aussi utilisé souvent est l"équivalence logique entre "(p↔q)et "(p→

q)?(q→p)". Proof.Encore une fois montrée par un tableau de vérité : 29
p qp↔qq→p q→p((p→q)?(q→p))V VVV VV

V FFF VF

F VFV FF

F FVV VV

On conclut la preuve, car les colonnes correspondantes sont identiques. En mots:P↔Qest vraie si et seulement siP→Qet sa réciproqueQ→Psont vraies. On conclut que pour montrer quep↔q(est vraie) il suffit de montrer quep→q(est vraie) et puis de montrer qu"aussiq→p(est vraie) (ou alternativement que(¬p)→(?=q)(est vraie)). 30

Département de mathématiques et de statistique, Université de Montréal, C.P. 6128, succursale

Centre-ville, Montréal (Québec), Canada H3C 3J7

E-mail address:broera@DMS.UMontreal.CA

quotesdbs_dbs47.pdfusesText_47

[PDF] maths tableur troisième

[PDF] Maths tarif

[PDF] maths taux de variation

[PDF] maths terminale es fonction exponentielle

[PDF] Maths Terminale S

[PDF] maths terminale s exercices corrigés livre

[PDF] maths terminale st2s statistiques

[PDF] maths terminale stmg exercices

[PDF] maths terminale stmg programme

[PDF] Maths TES : Suites géométriques

[PDF] Maths theoreme al-kashy

[PDF] Maths Théoreme de pythagore

[PDF] Maths Theroeme de THALES

[PDF] MATHS TLE ES LIMITES ET DERIVATION

[PDF] maths très urgent s'il vous plait