Ensembles logiques et fonction

Question 1

non(non P) équivaut à

Answer 1

P

Question 2

Quelle est la table de vérité de l’implication logique p(x) implique q(x)

Answer 2

p(x) q(x)
V + V = V
V + F = F
F + V = V
F + F = V

Question 3

Quelle est la table de vérité de non p

Answer 3

P
V = F
F = V

Question 4

Que signifie ∧ et quelle est sa table de vérité

Answer 4

• Et,
• P (x) Q(x) P(x) ∧ Q(x)
  v v v
  v f f
  f v f
  f f f

Question 5

Quelles sont les propriétés de ∧

Answer 5

1. 𝑝 ∧ 𝑞 ⇔ 𝑞 ∧ 𝑝 (commutativité).
2. (𝑝 ∧ 𝑞) ∧ 𝑟 ⇔ 𝑝 ∧ (𝑞 ∧ 𝑟) (associativité) :
3. 𝑝 ∧ ¬𝑝 ⇔ 𝑭 (contradiction)

Exemple 𝑝 : « Montréal est la capitale du Canada »; 𝑞 : «2 + 2 = 4 ».
* Alors, 𝑝 ∧ 𝑞 : « Montréal est la capitale du Canada et 2 + 2 = 4 ».
* Cette proposition est fausse

Question 6

Que veut dire ∨ et quelle est sa table de vérité

Answer 6

• Ou
• 𝑝 q 𝑝∨𝑞
  1 𝑉 𝑉 𝑉
  2 𝑉 𝐹 𝑉
  3 𝐹 𝑉 𝑉
  4 𝐹 𝐹 F

Question 7

Quelles sont les propriétés de la disjonction

Answer 7

1. 𝑝 ∨ 𝑞 ⇔ 𝑞 ∨ 𝑝 (commutativité).
2. (𝑝 ∨ 𝑞) ∨ 𝑟 ⇔ 𝑝 ∨ (𝑞 ∨ 𝑟) (associativité) :
3. 𝑝 ∨ ¬𝑝 ⇔ 𝑽 (tautologie) :
   𝑝 ¬𝑝 𝑝 ∨ ¬𝑝
   1 𝑉 𝐹 𝑉
   2 𝐹 𝑉 V

Exemple
* 𝑝 : « Montréal est la capitale du Canada »; 𝑞 : « 2 + 2 = 4 ».
* Alors, 𝑝 ∨ 𝑞 : « Montréal est la capitale du Canada ou 2 + 2 = 4 ».
* Cette proposition est vraie.

Question 8

Que veut dire la transitivité de l’implication

Answer 8

La transitivité de l’implication logique (ou règle du syllogisme).
* On vérifie (par une table de vérité) que la proposition composée
[(𝑝 → 𝑞) ∧ (𝑞 → 𝑟)] → (𝑝 → 𝑟)

Question 9

Que veut dire ⊕ et quelle est sa table de vérité

Answer 9

• Disjonction exclusive (ou exclusif)
• 𝑝 q 𝑝⊕𝑞
  1 𝑉 𝑉 𝐹
  2 𝑉 𝐹 𝑉
  3 𝐹 𝑉 𝑉
  4 𝐹 𝐹 F

Question 10

Que veut dire la disjonction exclusive

Answer 10

Définition La disjonction exclusive de deux propositions 𝑝 et 𝑞 est la proposition notée
𝑝 ⊕ 𝑞, fausse quand 𝑝 et 𝑞 ont même valeur de vérité (c’est-à-dire quand elles sont
simultanément vraies ou simultanément fausses), et vraie dans les autres cas.

Question 11

Quelle est la table de vérité de la biconditionelle

Answer 11

𝑝 q 𝑝 biconditionelle 𝑞
1 𝑉 𝑉 𝑉
2 𝑉 𝐹 𝐹
3 𝐹 𝑉 𝐹
4 𝐹 𝐹 V

Question 12

Quelles sont les propriétés de la biconditionelle

Answer 12

Propriétés de la biconditionnelle
1. 𝑝 𝑞 ⇔ [(𝑝 → 𝑞) ∧ (𝑞 → 𝑝)]. Identité
2. Transitivité : [(𝑝 𝑞) ∧ (𝑞 𝑝)] → (𝑝 q) est une tautologie.

Question 13

Qu’est-ce qu’une chaine binaire

Answer 13

• Une chaîne binaire est une suite finie de bits (0 et 1).
• La longueur d’une chaîne binaire est le nombre de bits qu’elle contient.
• On convient de considérer une chaîne ne contenant aucun bit comme une chaîne binaire.
• L’identification 𝑉 = 1, 𝐹 = 0 permet d’étendre aux chaînes binaires les opérations sur les
  bits en utilisant les opérateurs ∨,∧ et ⊕

Question 14

Résumée des bits

Question 15

Quelle est la définition d’une fonction booléenne

Answer 15

• Soit 𝑛 un entier strictement positif.
• Soit 𝐴 l’ensemble des 𝑛-uplets (c’est-à-dire des listes ordonnées) formés uniquement des
  lettres 𝐹 (ou du nombre 0) et 𝑉 (ou du nombre 1).

Question 16

Qu’est-ce qu’une proposition composée

Answer 16

Une proposition (ou un énoncé) composée est une
fonction booléenne 𝑛-aire, où 𝑛 est le nombre d’arguments (propositions simples) de la
fonction.

Question 17

Qu’est-ce qu’une tautologie

Answer 17

Une proposition composée est une tautologie si elle est égale à 𝑉
quelles que soient ses variables booléennes. C’est une contradiction si elle vaut toujours
𝐹. Dans tous les autres cas, c’est une contingence.

Question 18

Qu’est-ce qu’une équivalence logique, donne des exemples

Answer 18

• Les propositions 𝑝 et 𝑞 sont dites logiquement équivalentes si 𝑝 𝑞 est une
  tautologie.
• 𝑝 → 𝑞 ⇔ ¬𝑝 ∨ 𝑞.
• 𝑝 𝑞 ⇔ (𝑝 → 𝑞) ∧ (𝑞 → 𝑝).
• 𝑝 𝑞 ⇔ (¬𝑝 ∧ ¬𝑞) ∨ (𝑝 ∧ 𝑞).

Question 19

Quelle est l’équivalence logique de l’identité

Answer 19

Identité : P et V = P
p ∨ F ⇔ p

Question 20

Qu’est-ce qu’un prédicat

Answer 20

une déclaration dans un univers U

Question 21

Donne les conditions de vérité de l’énoncée suivant : ∀ (x) P(x)

Answer 21

Vrai si : P(x) est vrai pour tout (x)
Faux si : P(x) est faux pour au moins un x

Question 22

Donne les conditions de vérité de l’énoncée suivant : ∃ (x) P(x)

Answer 22

Vrai si : P(x) est vrai pour au moins un x
Faux : si P(x) est faux pour tout les x

Question 23

Donne les conditions de vérité des énoncés suivant : ∀ (x) ∀(y) P (x, y) et ∀(y) ∀(x)

Answer 23

Vrai si : P(x,y) est vrai pour tout couple (x, y)
Faux si : P(x,y) est faux pour au moins un couple (x,y)

Question 24

Donne les conditions de vérité de l’énoncée suivant : ∀ (x) ∃ (y) P(x,y)

Answer 24

Vrai si pour chaque (x), il existe au moins un y tel que P(x,y) est vrai
Faux si il existe un x tel que P(x,y) est faux pour tout y

Question 25

Donne les conditions de vérité de l’énoncée suivant : ∃ (x) ∀ (y) : P(x,y)

Answer 25

Vrai si : Il existe un x tel que P(x,y) est vrai pour tout y
Faux si : Pour chaque x il existe au moins un y tel que P(x,y) est faux

Question 26

Donne les conditions de vérité de les énoncés suivant :
∃ (x) ∃ (y) P(x,y),
∃ (y) ∃ (x) P (x,y)

Answer 26

Vrai si : Il existe un couple (x,y) tel que P(x,y) est vrai

Question 27

Quelle est l’équivalence logique de l’identité de la double-négation

Answer 27

non-non p = P

Question 28

Quelle est l’équivalence logique de la commutativité

Answer 28

p ou q = q ou p
P et q = q et p

Question 29

Quelle est l’équivalence logique de l’associativité

Answer 29

(p ou q) ou r = p ou (q ou r)

Question 30

Quelle est l’équivalence logique de la distributivité

Answer 30

p ou (q et r) = (p ou q) et (p ou r)

Question 31

Quelle est l’équivalence logique de la loi de morgan

Answer 31

non (P et Q) = non p ou non q
non (p ou q) = non p et non q

Question 32

Quelle est l’équivalence logique de l’inverse

Answer 32

p ou non p = V
p et non p = F

Question 33

Quelle est l’équivalence logique de l’absorption

Answer 33

p ou (p et q) = p
p et (p ou q) = p

Question 34

Qu’est-ce que la réfléxivité

Answer 34

Réflexivité : 𝐴 = 𝐴 (tout ensemble est égal à lui-même).

Question 35

Qu’est-ce que la Symétrie

Answer 35

Symétrie : si 𝐴 = 𝐵, alors 𝐵 = 𝐴.

Question 36

Qu’est-ce que la transitivité

Answer 36

Transitivité : si 𝐴 = 𝐵 et 𝐵 = 𝐶, alors 𝐴 = C

Question 37

Qu’est-ce qu’un sous-ensemble

Answer 37

Un sous-ensemble de 𝐴 est une sous-collection de 𝐴, c’est-à-dire
un ensemble 𝐵 dont tous les éléments appartiennent à 𝐴.

Question 38

Qu’est-ce que l’Inclusion

Answer 38

L’inclusion veut dire qu’un ensemble est présent dans un autre. Si B est inclus dans A on écris. On note ceci par 𝐵 ⊂ 𝐴 (ou 𝐴 ⊃ 𝐵).
𝐵 ⊂ 𝐴 ⇔ {∀𝑥: 𝑥 ∈ 𝐵 → 𝑥 ∈ 𝐴}
Pour démontrer que deux ensembles sont égaux (𝐴 = 𝐵), on peut démontrer la double
inclusion : 𝐴 ⊂ 𝐵 et 𝐵 ⊂ 𝐴.

Question 39

Qu’est-ce que la réfléxivité (dans l’inclusion)

Answer 39

𝐴 ⊂ 𝐴 (tout ensemble est inclus dans lui-même).

Question 40

Qu’est-ce que l’antisymétrie (dans l’inclusion)

Answer 40

si 𝐴 ⊂ 𝐵 et 𝐵 ⊂ 𝐴, alors 𝐴 = 𝐵.

Question 41

Qu’est-ce que la transitivité (dans l’inclusion)

Answer 41

si 𝐴 ⊂ 𝐵 et 𝐵 ⊂ 𝐶, alors 𝐴 ⊂ C

Question 42

Que veut dire ∩

Answer 42

Intersection : L’intersection des ensembles 𝐴 et 𝐵 est l’ensemble de tous les éléments
communs à 𝐴 et à 𝐵.
𝐴 ∩ 𝐵 = {𝑥 ∈ 𝐸: (𝑥 ∈ 𝐴) ∧ (𝑥 ∈ 𝐵)}

Question 43

Quelles sont les propriétés de l’intersection

Answer 43

L’intersection est commutative : 𝐴 ∩ 𝐵 = 𝐵 ∩ 𝐴.
2. L’intersection est associative : (𝐴 ∩ 𝐵) ∩ 𝐶 = 𝐴 ∩ (𝐵 ∩ 𝐶).
3. Le référentiel 𝐸 est neutre pour l’intersection : 𝐴 ∩ 𝐸 = 𝐴 pour tout 𝐴 ⊂ 𝐸.
4. L’ensemble vide est absorbant pour l’intersection : 𝐴 ∩ ∅ = ∅ pour tout 𝐴 ⊂ 𝐸.

Question 44

Qu’est-ce que ∪

Answer 44

L’union (ou la réunion) des ensemble 𝐴 et 𝐵 est l’ensemble de tous les éléments
appartenant soit à 𝐴 ou à 𝐵 ou aux deux (ou inclusif).
* On note ce nouvel ensemble 𝐴 ∪ 𝐵 (« 𝐴 union 𝐵 ») et on a
𝐴 ∪ 𝐵 = 𝑥 ∈ 𝐸: 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵 .

Question 45

Quelles sont les propriétés de l’union

Answer 45

-Commutative
-Associative
-Le référentiel E est absorbant
-L’ensemble vide est neutre pour l’union
-(A U B)complémentaire = A complémentaire ∩ B complémentaire
; (A ∩ B) complémentaire = A complémentaire U B complémentaire

Question 46

Que veut dire le C

Answer 46

Complémentaire Soit 𝐴 et 𝐵 deux sous-ensembles de 𝐸.
Le complémentaire (ou le complément) de 𝐴 (dans 𝐸) est l’ensemble de tous les éléments de
𝐸 qui n’appartiennent pas à 𝐴.

Question 47

Que représente le - ou le ∖

Answer 47

Différence La différence de l’ensemble 𝐴 et de l’ensemble 𝐵 est l’ensemble de tous les
éléments de 𝐴 qui n’appartiennent pas à 𝐵.

Question 48

Qu’est-ce que la différence symétrique

Answer 48

La différence symétrique des ensembles 𝐴 et 𝐵 est l’ensemble
𝐴Δ𝐵 = (𝐴 − 𝐵) ∪ (𝐵 − 𝐴).

Question 49

Résumé des propriétés de l’union et intersection

Answer 49

1. 𝐴 ∪ (𝐵 ∪ 𝐶) = (𝐴 ∪ 𝐵) ∪ 𝐶 et 𝐴 ∩ (𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ 𝐶 (associativité).
2. 𝐴 ∪ 𝐵 = 𝐵 ∪ 𝐴 et 𝐴 ∩ 𝐵 = 𝐵 ∩ 𝐴 (commutativité).
3. 𝐴 ∪ ∅ = 𝐴 et 𝐴 ∩ 𝑋 = 𝐴 (identité).
4. 𝐴 ∪ 𝐴
   𝑐 = 𝑋 et 𝐴 ∩ 𝐴
   𝑐 = ∅ (complémentaires).
5. 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶) et 𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)
   (distributivité).

Question 50

Injection

Answer 50

Fonction dont tout les x donne au plus un y
Une fonction
f
:
E
→
F
est dite injective si deux éléments de l’ensemble de départ ont toujours deux images par
f
distinctes

Question 51

Surjection

Answer 51

Fonction dont tout les y ont au moins un X :
∀𝑦 ∈ 𝐵, ∃𝑥 ∈ 𝐴: 𝑦 = 𝑓 𝑥 .

Question 52

Bijection

Answer 52

Combinaison des 2