Logique

Notions de logique

Une assertion ou proposition est un énoncé qui peut prendre la valeur vrai ou faux.

Un connecteur logique est une combinaison entre  propositions permettant d'obtenir de nouvelles propositions. Les plus courantes sont ET, OU, ⇒, ⇔ et la négation.

Soient P et Q des propositions,

  •     Conjonction de deux propositions : P et Q est vrai si les deux propositions sont vraies simultanément, faux sinon.
  •     Disjonction de deux propositions : P ou Q est vrai si l'une au moins des deux propositions est vraie.
  •     Négation d'une proposition : non P  est vrai si et seulement si P est faux.
  •     Implication : P ⇒ Q est vrai si P est faux ou si P et Q sont vrais.
  •     Réciproque :  on appelle réciproque de P ⇒ Q la proposition Q ⇒  P.
  •     Contraposée : la contraposée de P ⇒ Q est la proposition non Q ⇒  non P.
  •     Équivalence  P ⇔ Q   est vrai si les deux propositions sont vraies ou si elles sont toutes les deux fausses.

 

Propriétés

  •     non (non P)=P (la double négation est une affirmation) ;
  •     P ⇒ Q est équivalent à (non P ou Q) et aussi à sa contraposée non Q ⇒  non P ;
  •     P ⇔ Q est  équivalent  à P ⇒ Q et Q ⇒  P ;
  •     Associativité : (P et Q) et R est équivalent à P et (Q et R )  ;
  •     Associativité : (P ou Q) ou R est équivalent à P ou (Q ou R )  ;
  •     Distributivité : (P et Q) ou R est équivalent à  (P ou R) et (Q ou R) ;
  •     Distributivité : (P ou Q) et R est équivalent à  (P et R) ou (Q et R) ;
  •     Loi de Morgan : non  ( P et Q ) est équivalent à ( non P ou non Q)  ;
  •     Loi de Morgan : non  ( P ou Q ) est équivalent à ( non P et non Q)  ;


Quantificateurs

  •     quantificateur universel   $\forall$ : pour tout ...
  •     quantificateur existentiel   $\exists$: il existe au moins un ...

Rq : dans une propriété, dans une réponse, tout élément devrait être introduit par un quantificateur et on devrait préciser à quel ensemble, il appartient.

  •     La négation de$\forall x\in E,P(x)$ est $\exists x\in E, non P(x)$ (principe du contre exemple).
  •     La négation de $\exists x\in E,P(x)$ est $\forall x\in E, non P(x)$.

Rq : L'ordre des quantificateurs est important.
 

Fichier Joint: