7
F I C H E 1 – L o g i q u e e t r a i s o n n e m e n t
© Dunod – La photocopie non autorisée est un délit.
1
• 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.
II 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)
Mais si les quantificateurs sont différents, leur ordre est important.
Dans l'écriture ∀x ∈ E ∃ y ∈ E p(x,y) y dépend de x.
Dans l'écriture ∃ y ∈ E ∀x ∈ E p(x,y) y est indépendant de x.