[PDF] [PDF] Les connecteurs de la logique • Tautologie Contradiction Formules

View - Download [PDF] Les connecteurs de la logique • Tautologie Contradiction Formules

Previous PDF

Next PDF

Aujourd"hui nous allons discuter :

•Les connecteurs de la logique •Tautologie, Contradiction, Formules équivalentes •Tautologies simples (règles de De Morgan) •... et ses preuves par tableaux •Convention de l"utilisation de ( et ). •Quelques équivalences logiques souvent utiliséesMAT15001 of 38

Implication

Par definition l"implication p→qest vraie si : (i)petqsont vraies. ou si (ii)pest fausse (etq? sans importance : "je m"en fous")MAT15002 of 38

Biconditionnel

Par définition

la biconditionnelle p↔qest vraie si : (i)petqsont tous les deux vraies ou si (ii)petqsont tous les deux fausses.MAT15003 of 38 Quoi direde la vérité de petqsip→qest fausse?

Nécessairement :

pest vraieet qest fausse.

Quoi dire

de la vérité de petqsip↔qest fausse?

Nécessairement :

(i)pest vraieet qest fausse ou (ii)pest fausseet qest vraie. (Et v.v., par définition)

MAT15004 of 38

Posonsn:=123456789.

Deux propositions logiques :

p:="nest un nombre premier"; q:="nest un nombre impair".

Alors considérons

p→q="Sinest un nombre premier alorsnest un nombre impair". ="nest un nombre impair sinest un nombre premier". Vraie , ici nn"est pas variable! )MAT15005 of 38

Variation :

Deux fonctions propositionnelles avec univers de discours les nombres naturels positifs. p(n) :="nest un nombre premier" q(n) :="nest un nombre impair".

Alors considérons

?n[p(n)→q(n)] = ="Pour chaque nombre naturel positifnon a que sinest un nombre premier alorsnest un nombre impair" ="Sinest un nombre premier alorsnest un nombre impair".

Fausse

, icinest variable!)MAT15006 of 38 Tous ces définitions en forme de tableaux (V=vrai, 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

MAT15007 of 38

Maintenant nous pouvons commencer àcombiner trois propositions ou plus....

Supposonsp,q,rsont trois propositions.

Alors

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

est aussi une proposition. Vraie pour quelles valeurs de vérité dep,qetr?

Exemple, sip=F,q=Fetr=V?

Alors¬q=Vet

p?r=Vet donc ((¬q)?(p?r) =V. Maisp=Fdonc (((¬q)?(p?r))→p) =F.

Dans cette situationPsera faux.

Nous pouvons faire toutes les huit possibilités de vérités.

MAT15008 of 38

Les vérités de((¬q)?(p?r))→pen forme de tableau :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

V V V VF

F F FV F FV

AlorsPest fauxsi et seulement si

(petqsont faux etrest vraie)si et seulement s i ((¬p)?(¬q))?r)est vraie.MAT15009 of 38

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

Conclusion :Pestfaux si et seulement si ((¬p)?(¬q))?r)est vraie. OuPestvraie si et seulement si ¬((¬p)?(¬q))?r)est vraie. est vraie.

PosonsQ:=¬((¬p)?(¬q))?r)).

On ditPetQsontlogiquement é quivalent,P?Q.MAT150010 of 38

SoitP,Qcomme avant. Et soitR= (p?q)?(¬r).

On obtient un nouveau tableau :p q rp?q¬rRPQ

V V VV FVVV

V V FV VVVV

V F VV FVVV

V F FV VVVV

F V VV FVVV

F V FV VVVV

F F VF FFFF

F F FF VVVV

Conclusion :P,QetRont la même vérité, n"importe les valeurs dep,q,r. P,QetRsont des propositions composéeslogiquement

équivalentes

MAT150011 of 38

Reformulation :

On devrait voir

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

comme trois fo rmules logiques (ou trois fonctions) qui dép endent des propositions logiquesp,q,r.MAT150012 of 38

Exemple.

Par définition directe :

p↔qest la même chose que(¬p)↔(¬q). Oup↔qet(¬p)↔(¬q)sontlogiquement é quivalentes.MAT150013 of 38

Les connecteurs

Soientp,qdeux propositions logiques quelconques.

Nous avons

défini les p ropositionslogiqu es p?q,p?q,p→q,p↔q,¬p, (et aussi le "ou-strict"p?q).

Pour les fonctions propositionnelles on a :?et?.

Nous n"aurons pas besoins d"autres

connecteurs

MAT150014 of 38

Respecter notre Convention

Il faut

adopter les notations du cours !Exemples :

Il faut utiliser¬p(et paspou-p).

Et pas confondre?et?, ou?et∩.

Et Vraie (ou V) et Fausse (ou F) (et pas 1 et 0).

Et→(et pas?).

Et↔(et pas?).

Les symboles?et?ne sont pas définis encore!!MAT150015 of 38 On a parlé de lafo rmule(ou p ropositioncomp osée):

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

oùp,q,rsont des propositions logiques.MAT150016 of 38 Tableau de vérité deP: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

V V V VF

F F FV F FV

On a "vu" quePet

Q=Q(p,q,r) =¬((¬p)?(¬q))?r))

ont les mêmes vérités.

MAT150017 of 38

AvecPetQcomme avant. DiscutonsP↔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

La proposition logique composéeP↔Qest toujours vraie, pour tous les valeurs de vérité dep,qetr. On ditP↔Qestune tautologie ,notation P?Q.MAT150018 of 38

Definition

Une proposition logique composée qui est toujours vraie, quelles que soient les valeurs de vérité des propositions qui la composent, est appelée une tautologie .SiPest une tautologie, on écritP?V (IciV=une proposition vraie).MAT150019 of 38

Exemples :

p?(¬p)est une tautologie, ou p?(¬p)?V. Aussi ((p?q)→(p?q))?V.MAT150020 of 38

Definition

Une proposition logique composée qui est toujours fausse, quelles que soient les valeurs de vérité des propositions qui la composent, est appelée une c ontradiction .SiPest une contradiction on écritP?F (oùFest une proposition fausse).MAT150021 of 38

Exemple :

(p?(¬p))?F.MAT150022 of 38

Definition

Deux propositions logiques composéesPetQsont appelées logiquement équivalentes si la p ropositionlogique P↔Qest une tautologie.Dans se cas on écritP?Q. Alors c"est le cas siPvraie si et seulementQest vraie, n"importe les valeurs de vérité des composantes simples.

MAT150023 of 38

Une liste d"équivalences logiques simples utlisées tout le temps :

MAT150024 of 38

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)MAT150025 of 38 La plupart des preuves est facile. Deux exemples de preuve-par-tableau : SiP:=p?(q?r)etQ:= (p?q)?(p?r)on ap q rq?rP p?q p?rQ P↔QV V VVV V VV V

V V FFV V VV V

V F VFV V VV V

V F FFV V VV V

F V VVV V VV V

F V FFF V FF V

F F VFF F VF V

F F FFF F FF V

La dernière colonne montre queP?Q.MAT150026 of 38

Montrons

¬(p?q)?((¬p)?(¬q)).

SoitP=¬(p?q)etQ= ((¬p)?(¬q)). On ap qp?qP ¬p¬qQ P↔QV VVF F FF V

V FFV F VV V

F VFV V FV V

F FFV V VV V

La dernière colonne montre queP?Q(un des deux lois de De

Morgan).

MAT150027 of 38

Ajoutons quelques règles évidentes :

•p?V?p, •p?F?p("Identité"); •p?V?V, •p?F?F("Domination").

IciVveux dire une proposition logique vraie, et

Fveux dire une proposition logique fausse.MAT150028 of 38 A propos de l"utilisation des parenthèses(et)(et[,]etc).

Nous avons montré l"associativité :

p?(q?r)?(p?q)?r. Logiquement il n"y a pas de confusion possible : on a le droit d"écrirep?q?r.

Aussip?q?rest sans ambiguité.MAT150029 of 38

Maisp?q?rest ambigue!

Parce que

(p?q)?r et p?(q?r) sont deux choses logiquement différentes (non-équivalentes). Nous ne posons pas de convention de priorité entre?et?! Il faut continuer d"utiliser les(,)dans ce cours!MAT150030 of 38

Seulement :

par convention¬aura plus haute priorité que les autres opérations logiques.

Par exemple :

¬p→qveut dire(¬p)→qet non¬(p→q). Ce sont les seules conventions de ce cours à propos de priorité d"opérations logiques. Pour le reste il faut utiliser les (,).MAT150031 of 38 Quelques équivalences moins simples souvent utilisées Une équivalence utilisée souvent en mathématiques : (P↔Q)?((P→Q)?(Q→P)). En mots :P↔Qest vraiesi et seulement si P→Qet sa réciproqueQ→Psont vraies. (Comparer avec le théorème du sandwich, dans la théorie des ensembles.)

MAT150032 of 38

Preuve par une vérification par tableau.

P QP↔QP→Q Q→P((P→Q)?(Q→P))V VVV VV

V FFF VF

F VFV FF

F FVV VV

En effet, colonnes 3 et 6 sont identiques.

MAT150033 of 38

Deux autres exemples d"équivalence, très importants pour nous : (P→Q)?(¬Q→ ¬P) (une implication est équivalente à sa contraposé) et (P→Q)?(¬P?Q)MAT150034 of 38

Preuve par une vérification par tableau.

P QP→Q¬Q¬P(¬Q)→(¬P)(¬P?Q)V VVF FV V

V FFV FF F

F VVF VV V

F FVV VV V

En effet, colonnes 3, 6 et 7 sont identiques.

MAT150035 of 38

Preuves pas algèbre

À la place d"utiliser un tableau pour vérifier une équivalence logique, on peut aussi utiliser les petites (ou grandes) équivalences déjà montrées, comme en algèbre.

Un exemple suffit pour comprendre, peut-être.

MAT150036 of 38

Montrons queP:= ((¬q)?(p?r))→petQ:= (p?(q?(¬r))) sont équivalentes : ?(¬(¬q)? ¬(p?r)))?p(Selon De Morgan) ?(q? ¬(p?r)))?p(Double négation) ?(q?((¬p)?(¬r)))?p(Selon De Morgan) ?q?(((¬p)?(¬r))?p)(Assoc. pour?) ?q?(p?((¬p)?(¬r)))(comm. pour?) ?q?((p?(¬p))?(p?(¬r)))(Distrib.) ?q?(V?(p?(¬r)))(Selon(p?(¬p))?V) ?q?(p?(¬r))(Selon(V?p)?p) ?(q?p)?(¬r)(Assoc. de?) ?(p?q)?(¬r)(Commut. de?) ?Q(Assoc. de?)MAT150037 of 38 L"algèbre (de Boole) est utilisé en programmation...

MAT150038 of 38

quotesdbs_dbs33.pdfusesText_39

[PDF] longueur d'un vecteur formule

[PDF] formule distance maths

[PDF] norme d'un vecteur dans l'espace

[PDF] calculer distance avec coordonnées gps

[PDF] démonstration dérivée u/v

[PDF] démonstration dérivée composée

[PDF] relation entre k et taux d'avancement

[PDF] quotient réactionnel définition

[PDF] quotient de réaction exercices

[PDF] démonstration mathématique 5ème

[PDF] r archimédien demonstration

[PDF] dérivation première s

[PDF] relation metrique dans un cercle

[PDF] relation métrique et angulaire dans le triangle

[PDF] différence symétrique de deux ensembles