Ensembles logiques et fonction Flashcards
non(non P) équivaut à
P
Quelle est la table de vérité de l’implication logique p(x) implique q(x)
p(x) q(x)
V + V = V
V + F = F
F + V = V
F + F = V
Quelle est la table de vérité de non p
P
V = F
F = V
Que signifie ∧ et quelle est sa table de vérité
- Et,
- P (x) Q(x) P(x) ∧ Q(x)
v v v
v f f
f v f
f f f
Quelles sont les propriétés de ∧
- 𝑝 ∧ 𝑞 ⇔ 𝑞 ∧ 𝑝 (commutativité).
- (𝑝 ∧ 𝑞) ∧ 𝑟 ⇔ 𝑝 ∧ (𝑞 ∧ 𝑟) (associativité) :
- 𝑝 ∧ ¬𝑝 ⇔ 𝑭 (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
Que veut dire ∨ et quelle est sa table de vérité
- Ou
- 𝑝 q 𝑝∨𝑞
1 𝑉 𝑉 𝑉
2 𝑉 𝐹 𝑉
3 𝐹 𝑉 𝑉
4 𝐹 𝐹 F
Quelles sont les propriétés de la disjonction
- 𝑝 ∨ 𝑞 ⇔ 𝑞 ∨ 𝑝 (commutativité).
- (𝑝 ∨ 𝑞) ∨ 𝑟 ⇔ 𝑝 ∨ (𝑞 ∨ 𝑟) (associativité) :
- 𝑝 ∨ ¬𝑝 ⇔ 𝑽 (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.
Que veut dire la transitivité de l’implication
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
[(𝑝 → 𝑞) ∧ (𝑞 → 𝑟)] → (𝑝 → 𝑟)
Que veut dire ⊕ et quelle est sa table de vérité
- Disjonction exclusive (ou exclusif)
- 𝑝 q 𝑝⊕𝑞
1 𝑉 𝑉 𝐹
2 𝑉 𝐹 𝑉
3 𝐹 𝑉 𝑉
4 𝐹 𝐹 F
Que veut dire la disjonction exclusive
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.
Quelle est la table de vérité de la biconditionelle
𝑝 q 𝑝 biconditionelle 𝑞
1 𝑉 𝑉 𝑉
2 𝑉 𝐹 𝐹
3 𝐹 𝑉 𝐹
4 𝐹 𝐹 V
Quelles sont les propriétés de la biconditionelle
Propriétés de la biconditionnelle
1. 𝑝 𝑞 ⇔ [(𝑝 → 𝑞) ∧ (𝑞 → 𝑝)]. Identité
2. Transitivité : [(𝑝 𝑞) ∧ (𝑞 𝑝)] → (𝑝 q) est une tautologie.
Qu’est-ce qu’une chaine binaire
- 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 ⊕
Résumée des bits
Quelle est la définition d’une fonction booléenne
- 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).
Qu’est-ce qu’une proposition composée
Une proposition (ou un énoncé) composée est une
fonction booléenne 𝑛-aire, où 𝑛 est le nombre d’arguments (propositions simples) de la
fonction.
Qu’est-ce qu’une tautologie
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.
Qu’est-ce qu’une équivalence logique, donne des exemples
- Les propositions 𝑝 et 𝑞 sont dites logiquement équivalentes si 𝑝 𝑞 est une
tautologie. - 𝑝 → 𝑞 ⇔ ¬𝑝 ∨ 𝑞.
- 𝑝 𝑞 ⇔ (𝑝 → 𝑞) ∧ (𝑞 → 𝑝).
- 𝑝 𝑞 ⇔ (¬𝑝 ∧ ¬𝑞) ∨ (𝑝 ∧ 𝑞).
Quelle est l’équivalence logique de l’identité
Identité : P et V = P
p ∨ F ⇔ p
Qu’est-ce qu’un prédicat
une déclaration dans un univers U
Donne les conditions de vérité de l’énoncée suivant : ∀ (x) P(x)
Vrai si : P(x) est vrai pour tout (x)
Faux si : P(x) est faux pour au moins un x
Donne les conditions de vérité de l’énoncée suivant : ∃ (x) P(x)
Vrai si : P(x) est vrai pour au moins un x
Faux : si P(x) est faux pour tout les x
Donne les conditions de vérité des énoncés suivant : ∀ (x) ∀(y) P (x, y) et ∀(y) ∀(x)
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)
Donne les conditions de vérité de l’énoncée suivant : ∀ (x) ∃ (y) P(x,y)
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
Donne les conditions de vérité de l’énoncée suivant : ∃ (x) ∀ (y) : P(x,y)
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
Donne les conditions de vérité de les énoncés suivant :
∃ (x) ∃ (y) P(x,y),
∃ (y) ∃ (x) P (x,y)
Vrai si : Il existe un couple (x,y) tel que P(x,y) est vrai
Quelle est l’équivalence logique de l’identité de la double-négation
non-non p = P
Quelle est l’équivalence logique de la commutativité
p ou q = q ou p
P et q = q et p
Quelle est l’équivalence logique de l’associativité
(p ou q) ou r = p ou (q ou r)
Quelle est l’équivalence logique de la distributivité
p ou (q et r) = (p ou q) et (p ou r)
Quelle est l’équivalence logique de la loi de morgan
non (P et Q) = non p ou non q
non (p ou q) = non p et non q
Quelle est l’équivalence logique de l’inverse
p ou non p = V
p et non p = F
Quelle est l’équivalence logique de l’absorption
p ou (p et q) = p
p et (p ou q) = p
Qu’est-ce que la réfléxivité
Réflexivité : 𝐴 = 𝐴 (tout ensemble est égal à lui-même).
Qu’est-ce que la Symétrie
Symétrie : si 𝐴 = 𝐵, alors 𝐵 = 𝐴.
Qu’est-ce que la transitivité
Transitivité : si 𝐴 = 𝐵 et 𝐵 = 𝐶, alors 𝐴 = C
Qu’est-ce qu’un sous-ensemble
Un sous-ensemble de 𝐴 est une sous-collection de 𝐴, c’est-à-dire
un ensemble 𝐵 dont tous les éléments appartiennent à 𝐴.
Qu’est-ce que l’Inclusion
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 𝐵 ⊂ 𝐴.
Qu’est-ce que la réfléxivité (dans l’inclusion)
𝐴 ⊂ 𝐴 (tout ensemble est inclus dans lui-même).
Qu’est-ce que l’antisymétrie (dans l’inclusion)
si 𝐴 ⊂ 𝐵 et 𝐵 ⊂ 𝐴, alors 𝐴 = 𝐵.
Qu’est-ce que la transitivité (dans l’inclusion)
si 𝐴 ⊂ 𝐵 et 𝐵 ⊂ 𝐶, alors 𝐴 ⊂ C
Que veut dire ∩
Intersection : L’intersection des ensembles 𝐴 et 𝐵 est l’ensemble de tous les éléments
communs à 𝐴 et à 𝐵.
𝐴 ∩ 𝐵 = {𝑥 ∈ 𝐸: (𝑥 ∈ 𝐴) ∧ (𝑥 ∈ 𝐵)}
Quelles sont les propriétés de l’intersection
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 𝐴 ⊂ 𝐸.
Qu’est-ce que ∪
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
𝐴 ∪ 𝐵 = 𝑥 ∈ 𝐸: 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵 .
Quelles sont les propriétés de l’union
-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
Que veut dire le C
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 à 𝐴.
Que représente le - ou le ∖
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 à 𝐵.
Qu’est-ce que la différence symétrique
La différence symétrique des ensembles 𝐴 et 𝐵 est l’ensemble
𝐴Δ𝐵 = (𝐴 − 𝐵) ∪ (𝐵 − 𝐴).
Résumé des propriétés de l’union et intersection
- 𝐴 ∪ (𝐵 ∪ 𝐶) = (𝐴 ∪ 𝐵) ∪ 𝐶 et 𝐴 ∩ (𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ 𝐶 (associativité).
- 𝐴 ∪ 𝐵 = 𝐵 ∪ 𝐴 et 𝐴 ∩ 𝐵 = 𝐵 ∩ 𝐴 (commutativité).
- 𝐴 ∪ ∅ = 𝐴 et 𝐴 ∩ 𝑋 = 𝐴 (identité).
- 𝐴 ∪ 𝐴
𝑐 = 𝑋 et 𝐴 ∩ 𝐴
𝑐 = ∅ (complémentaires). - 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶) et 𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)
(distributivité).
Injection
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
Surjection
Fonction dont tout les y ont au moins un X :
∀𝑦 ∈ 𝐵, ∃𝑥 ∈ 𝐴: 𝑦 = 𝑓 𝑥 .
Bijection
Combinaison des 2
