[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.quotesdbs_dbs47.pdfusesText_47

[PDF] Montrer par récurrence que la suite (un) est croissante

[PDF] Montrer pour unréel

[PDF] montrer qu il existe 3 réels ab et c

[PDF] Montrer qu un point est le milieu d un segment et calculer une droite

[PDF] montrer qu une droite est tangente ? une courbe

[PDF] Montrer qu'un point appartient ? une médiatrice

[PDF] Montrer qu'un triangle est rectangle

[PDF] Montrer qu'un triangle est rectangle ( 3eme )

[PDF] Montrer qu'une fonction est affine

[PDF] montrer qu'une suite est géométrique

[PDF] Montrer qu'une surface latérale est égale ? celle d'une sphère

[PDF] montrer qu'un ensemble est fini

[PDF] montrer qu'un ensemble est infini

[PDF] montrer qu'un parallélogramme est un losange

[PDF] montrer qu'un point appartient ? une droite représentation paramétrique