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

View - Download [PDF] 42 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.quotesdbs_dbs46.pdfusesText_46

[PDF] la vérité mene t elle au bonheur

[PDF] la vérité philosophie

[PDF] la vérité philosophie citation

[PDF] la vérité philosophie cours

[PDF] la vérité philosophie pdf

[PDF] la vérité proverbe

[PDF] la vérité rend elle heureux

[PDF] La versification

[PDF] La versification

[PDF] La versification (les vers)

[PDF] la versification 4ème e muet

[PDF] la victime en droit pénal

[PDF] la victime est-elle un acteur accessoire de la procédure pénale

[PDF] la victoire et l'oeuvre du front populaire

[PDF] la vida de un inmigrante ecuatoriano