3. Propriétés des connecteurs
non ( non p) = p
non ( p ou q) = ( non p) et ( non q)
non ( p et q) = ( non p) ou ( non q)
( p ⇒ q) =
( non p) ou q
non ( p ⇒ q) =
p et ( non q)
La négation d'une implication n'est donc pas une implication.
( p ⇒ q) =
( non q) ⇒ ( non p)
Cette seconde implication est la contraposée de la première. Faites
attention à l'ordre des propositions.
( p ⇐⇒ q) =
( p ⇒ q) et (q ⇒ p)
Pour démontrer une équivalence, on démontre souvent une implication et sa réciproque.
4. Quantificateurs
• Notation
Les quantificateurs servent à indiquer la quantité d'éléments qui interviennent
dans une proposition. On utilise :
le quantificateur universel ∀
∀x
signifie : pour tout x ;
le quantificateur existentiel ∃
∃ x
signifie : il existe au moins un x.
• Ordre
Si l'on utilise deux fois le même quantificateur, l'ordre n'a pas d'importance.
On peut permuter les quantificateurs dans des écritures du type :
∀x ∈ E ∀y ∈ E p(x,y)
∃ x ∈ E ∃ y ∈ E p(x,y)
© Dunod – La photocopie non autorisée est un délit.
Logique binaire 37
121
Algèbre générale
9782100549245-fredon-C37-51.qxd 18/06/10 10:33 Page 121