Rudiments de Logique et Théorie des Ensembles Flashcards
Définition Assertion :
On appelle assertion un énoncé mathématique pouvant être soit V soit F
Définition Équivalence :
Soit P et Q deux assertions, on dit qu’elle sont équivalentes lorsqu’elles sont simultanément vraies ou fausses
Définition Négation d’une assertion :
Soit P une assertion, on appelle négation de P l’assertion ayant les valeurs de vérité opposées. Elle est notée nonP.
Propriété Double négation :
Soit P une assertion. Alors nonnonP =P
Propriété Équivalence + Négation :
Soit P et Q deux assertions équivalentes. Alors, nonP = nonQ
Définition Conjonction :
Soit P et Q deux assertions, on appelle conjonction de P et Q l’assertion vraie lorsque P et Q le sont, fausses sinon. Elle est notée PnQ, ou encore P et Q.
Définition Disjonction :
Soit P et Q deux assertions, on appelle disjonction de P et Q l’assertion vraie dès que l’une des deux est vraie, fausse sinon. Elle est notée PuQ, ou encore P ou Q.
Propriété Équivalences à connaître :
non(PnQ) =
non(PuQ) =
= (nonP)u(nonQ)
= (nonP)n(nonQ)
Propriété Équivalences logiques :
PnQ =
PuQ =
(PnQ)nR =
(PuQ)uR =
Pn(QuR) =
Pu(QnR) =
= QnP
= QuP
= Pn(QnR)
= Pu(QuR)
= (PnQ)u(PnR)
= (PuQ)n(PuR)
Définition Implication :
Soit P et Q deux assertions. L’assertion (nonP)uQ est appelée implication de P vers Q, notée P=>Q
Définition Implication (Réciproque) :
Soit P et Q deux assertions. Q=>P est appelée réciproque de P=>Q.
Propriété Négation des assertions de l’implication :
Soit P et Q deux assertions.
P=>Q = ((nonQ)=>(nonP))
Propriété Négation de l’implication :
Soit P et Q deux assertions.
Non(P=>Q) = Pn(nonQ)
Définition P<=>Q :
Soit P et Q deux assertions. L’assertion P<=>Q est l’assertion (P=>Q)n(Q=>P).
Définition Ensemble :
Un ensemble est une collection d’objets. Un élément x d’un ensemble E appartient à E, ce qui se note x€E
Définition Ensemble vide :
L’ensemble ne contenant aucun élément est appelé ensemble vide, noté ø
Définition Ensembles égaux :
Soit E et F deux ensembles. On dit que E et F sont égaux lorsque tout élément x de E appartient à F, et réciproquement. On note E = F
Définition ensemble inclus :
On dit que E est inclus dans F lorsque tout élément de E appartient à F. On note ECF.
Définition Parties d’un ensemble :
Soit E un ensemble. L’ensemble des ensembles inclus dans E est noté P(E), c’est l’ensemble des parties de E
Définition Complémentaire d’une partie :
Soit E un ensemble et F une partie de E. Le complémentaire de F dans E est l’ensemble des éléments de E n’appartenant pas à F. Il est noté E\F ou F^c, F(conjugué), C_E(F)
Définition d’un ensemble en extension/compréhension :
Définir un ensemble en extension, c’est faire la liste de ses éléments
Définir un ensemble en compréhension, c’est définir ses éléments selon plusieurs critères.
Définition : Intersection de E et F :
Soit E et F deux ensembles. L’intersection de E et F, notée EnF est l’ensemble des éléments appartenant à la fois à E et F.
EnF = {x€E|x€F} = {x€F|x€E}
Définition Union de E et F :
Soit E et F deux ensembles. L’union de E et F est l’ensemble des éléments appartenant à E ou à F. Il est noté EuF.
Définition Différence entre A et B :
Soit E un ensemble. A,B deux parties de F. La différence de A par B est l’ensemble des éléments de E qui appartiennent à A, mais non a B, noté A\B.
Définition Différence symétrique :
Soit E un ensemble, A et B deux parties de E. La différence symétrique de A et B notée AdeltaB est l’ensemble des éléments appartenant à A ou B, mais pas au deux, autrement dit,
(AuB)(AnB)
Propriété Différence symétrique (différente notation) :
Soit E un ensemble, A et B deux parties de E. AdeltaB = (A\B)u(B\A)
Définition Quantificateur universel :
L’assertion pour tout (quantificateur universel) x€E, P(x) est vraie lorsque P(x) est vraie pour tout élément x de E.
Définition Quantificateur existentiel :
L’assertion il existe (quantificateur existentiel) x€E, P(x) est vraie lorsqu’il existe au moins un élément x de E tel que P(x) est vraie.
Définition Quantificateur existentiel unique :
L’assertion il existe un unique (QE unique) x€E est vraie lorsqu’il existe un et un seul élément x de E tel que P(x) est vraie.
Propriété Négation sur les quantificateurs :
Non(pour tout x€E, P(x)) = il existe x€E, nonP(x)
Non(il existe x€E, P(x)) = pour tout x€E, nonP(x)
Théorème Unique minimum d’une partie :
Soit À une partie de |N non vide, alors A possède un unique minimum a. Il vérifie a€A et pour tout x€A, a=<x
Propriété Principe de récurrence :
Soit A une partie de |N non vide qui vérifie pour tout n€A, n+1€A.
Alors, en notant à le minimum de A,
A = {n€|N tel que a=<n} = [a;+l’infini].
Définition Indicatrice :
Soit A une partie de F. L’indicatrice de A est la fonction qui a tout élément x de E associe 1 si c appartient à A, 0 sinon. Elle est notée 1_A.
Propriété : Indicatrice (rédaction pour 1_A(x) = 1
Soit A une partie de E, alors pour tout x€E, (x€A<=>1_A(x) = 1)
Propriété Indicatrice de l’intersection/union de deux parties :
Soit A et B deux parties de E. Alors :
- pour tout x€E, 1_AnB(x) =1_A(x)1_B(x)
- pour tout x€E, 1_AuB(x) = 1_A(x) + 1_B(x) - 1_AnB(x)