BTS IG Informatique de Gestion

Maths:LogiqueEnsembles

Sommaire 1 Calcul des propositions 1.1 Propositions - Valeurs de vérité 1.2 Connecteurs logiques 1.2.1 Négation 1.3 Connecteurs binaires 1.4 Propriétés des connecteurs 1.5 Implication et équivalence 1.5.1 Contraposée 1.5.2 Negation 1.6 Proposition quantifiée - Prédicat 1.7 Quantificateurs 1.8 Négation d'une proposition quantifiée 2 Ensemble-Application 2.1 Les ensembles 2.1.1 Inclusion et égalité 2.1.2 Complémentaire par rapport à E 2.1.3 Union-Intersection 2.2 Applications d'un ensemble E dans un ensemble F 2.2.1 Définition:application 2.2.2 Définitions 2.2.3 Injection-Surjection-Bijection 2.2.4 Composition d'application 3 Algèbre de Boole

Calcul des propositions

Propositions - Valeurs de vérité

A toutes propositions P, on peut associer une valeur de vérité.

• Vrai: V ou 1
• Faux: F ou 0

Les valeurs de vérité 1 ou 0 sont dues à George Boole, mathématicien anglais(1895-1964)

Connecteurs logiques

Négation

Le connecteur logique négation se note : non P ou ¬P
Il est défini par :

• la table de Boole:

P		¬P
1		0
0		1

• la table de vérité:

P		¬P
V		F
F		V

Connecteurs binaires

• le connecteur conjonction noté: ET ou ∧ ou . : P∧Q
  
• le connecteur disjonction noté: OU ou ∨ ou + : P∨Q
  
• le connecteur implication noté: ⇒ :P⇒Q(P implique Q)
  
• le connecteur équivalence noté: ⇔ :P⇔Q(P équivaut à Q)
  

Tables de Boole ou tables de vérité:

P		Q		P∧Q		P∨Q		P⇒Q		P⇔Q
1		1		1		1		1		1
1		0		0		1		0		0
0		1		0		1		1		0
0		0		0		0		0		0

Propriétés des connecteurs

Commutativités		(P∨Q)⇔(Q∨P) et (P∧Q)⇔(Q∧P)
Eléments neutres		(P∨F)⇔P et (P∧V)⇔P
Distributivités		(P∨(Q∧R)⇔(P∨Q)∧(P∨R) et (P∧(Q∨R)⇔(P∧Q)∨(P∧R)
Tiers exclu non contradiction		(P∨¬P)⇔V et (P∧¬P)⇔F
Involution		¬¬P⇔P
Elements absorbants		(P∨V)⇔V et (P∧F)⇔F
Idempotence		(P∨P)⇔P et (P∧P)⇔P
Lois de Morgan		¬(P∨Q)⇔(¬P∧¬Q) et ¬(P∧Q)⇔(¬P∨¬Q)
Absorptions		(P∨(P∧Q))⇔P et (P∧(P∨Q))⇔P
Associativités		((P∨Q)∨R)⇔(P∨(Q∨R)) et ((P∧Q)∧R)⇔(P∧(Q∧R))

V et F sont des topologies (toujours vraies)
V:proposition toujours vraie
F:proposition toujours fausse

Implication et équivalence

On va montrer à l'aide des tables de vérité les propriétés:

• (P⇒Q)⇔(¬P∨Q)
• (P⇒Q)⇔(¬Q⇒¬P)

P		Q		¬P		¬Q		P⇒Q		¬P∨Q		¬Q⇒¬P
1		1		0		0		1		1		1
1		0		0		1		0		0		0
0		1		1		0		1		1		1
0		0		1		1		1		1		1

Contraposée

On a P⇒Q sa contraposée est: (¬Q⇒¬P)

Negation

On a P⇒Q sa négation est: ¬(P⇒Q)
(P⇒Q)⇔(¬P∨Q)
¬(¬P∨Q)⇔(¬¬P∧¬Q) <-Loi de Morgan
d'où ¬(P⇒Q)⇔(P∧¬Q)

Proposition quantifiée - Prédicat

Exemples:

• x<4 est une proposition avec une variable x. Elle est appelée prédicat à une variable et notée p(x)
  
• x<y est un prédicat à deux variables, noté p(x,y)

Quantificateurs

• Universel: ∀x∈,p(x) ∀ se lit "pour tout", la virgule se lit "on a"
• Existenciel: ∃x∈E, p(x) ∃ se lit "il existe au moins un "", la virgule se lit "tel que"
  

Exemples:

• ∀x∈R, e^x=1 ->Proposition fausse: e^1=e n'est pas égal à 1,par exemple.
• ∃x∈R, x<4 ->Proposition vraie: 2,1<4 par exemple.

Négation d'une proposition quantifiée

La négation de "∀x, p(x)" est "∃x, ¬p(x)"
La négation de "∃x, p(x)" est "∀x, ¬p(x)"


Exemples:(A \cup B) \cup C ou (^c A \cup B) \cap (C\cup ^c A)?

• La négation de "∀x∈R, x^2=0" est "∃x∈R, x^2 est différent de 0"
• La négation de "∃x∈R, x>7" est "∀x∈R, x est inférieur ou égal à 7"

Ensemble-Application

Les ensembles

Inclusion et égalité

Déf:Un ensemble A est inclus dans un emsemble E si tout élément de A est élément de E, ce qu'on écrit: A C E⇔(∀x, x∈A ⇒ x⇔E)
A est un sous-ensemble de E ou une partie de E

Complémentaire par rapport à E

Déf:Soit A un sous-ensemble de E. La complémentaire de A dans E est l'ensemble des éléments de E qui n'appartiennent pas à A.

Union-Intersection

Déf:Soit A et B deux sous-ensemble de E

• A⋃B={x∈E, x∈A ou x∈B}
• Aâ‹‚B={x∈E, x∈A et x∈B}

Deux ensembles sont disjoints si A⋂B=Ø(ensemble vide)

Applications d'un ensemble E dans un ensemble F

Définition:application

Soit E et F deux ensembles. Une application f de E dans F associe à tout élément x de E un élément y et un seul de F.
On note y=f(x). On dit que y est l'image de x et x est un antécédent de y.

Définitions

F est une application de E dans F, A une partie de E, B une partie de F.
L'image de la partie A est l'ensemble des images des éléments de A par f. On la note f(A).
L'image réciproque de la partie B est l'ensemble des antécédents par f des éléments de B.On la note f^-1(B).

Injection-Surjection-Bijection

• Une application f de E dans F est injective si deux éléments distincts de E ont deux images distinctes par f: ∀x∈E, ∀x'∈E, f(x)=f(x') ->x=x'
• Une application f de E dans F est surjective si tout élément de F a au moins un antécédent dans E: ∀x∈E, ∃y∈F, y=(f(x)
• Une application f de E dans F est bijective si elle est injective et surjective. Tout élément de F a un et un seul antécédent dans E.

Composition d'application

L'application composée de deux applications f: E->F et x->f(x)
g:F->G est l'application h:E->G
On la note gof et se lit g rond f.

∀x∈E, gof(x)=(g(f(x))

->En info., on parle de règles de transitivité au lieu de compositions d'applications.

Algèbre de Boole

• Table de Vérité