Mathématiques Discrètes (Ensembles)

Thèmes abordés

Intersection, subjectif, Image réciproque, Application, Antisymétrique

Résumé du document

Ecritures logiques
Pour simplifier l'écriture propositionnelle, on peut la passer sous la forme polonaise, via un arbre.

Les parenthèses définissent les priorités, les plus hauts niveaux. Plus un élément est de bas niveau, plus il sera haut dans l'arbre. Ici, le plus bas niveau est l'union « u », il sera tout en haut. On va de plus en plus profond dans les parenthèses et à chaque opérateur on fait des branches.

Extraits

[...] A n'est pas forcément majorée / minorée Si A est majorée / minorée, elle n'admet pas forcément une borne supérieure / inférieure Si A est majorée / minorée, elle n'admet pas forcément un élément maximal / minimal Relation d'équivalence Modulo : x y x est congru à y modulo n x-y = k*n Classe d'équivalence : Soit et R une relation d'équivalence sur E. La classe d'équivalence de l'élément x est l'ensemble des éléments de E qui sont en relation avec noté . Une classe d'équivalence n'est jamais vide. L'intersection de deux classes d'équivalence distinctes est vide. Ex : Congruence module = { , } = { , } = . [...]

[...] Proposition inconsistante : qui n'est jamais vraie. Calcul propositionnel é 1 é 2 è (implication mutuelle) Implication Mutuelle A B F F V F V V V F F V V V Règles de conjonction Introduction Règles de négation Elimination Introduction [] [] ¬ ¬ Elimination ¬¬ La dernière règle se base sur le raisonnement par l'absurde. Pour conclure on suppose A. Si on arrive à deux résultats différents et alors la supposition est fausse, donc on conclut DUT Informatique Fiche de révisions - Mathématiques Discrètes (Logique) Ecritures logiques Pour simplifier l'écriture propositionnelle, on peut la passer sous la forme polonaise, via un arbre. [...]

[...] DUT Informatique Fiche de révisions - Mathématiques Discrètes (Raisonnements) q p pq'+qp' qq' ℚ DUT Informatique Fiche de révisions - Mathématiques Discrètes (Logique) Tables de vérité C'est pareil que pour l'algèbre de Boole, mais avec des opérateurs en plus. Implication A B F F V F V V V F F V V V Priorité des opérateurs 1. (négation) 2. 3. (implication) Notions supplémentaires Une tautologie : proposition A dont la table de vérité donne toujours vrai. A Une antilogie : proposition A dont la table de vérité donne toujours faux. [...]

[...] Ecriture propositionnelle : Les parenthèses définissent les priorités, les plus hauts niveaux. Plus un élément est de bas niveau, plus il sera haut dans l'arbre. Ici, le plus bas niveau est l'union il sera tout en haut. On va de plus en plus profond dans les parenthèses et à chaque opérateur on fait des branches. A B A B Pour écrire à la polonaise, on écrit de haut vers le bas-gauche. C'est-à-dire que l'on descend le maximum à gauche en écrivant à chaque fois le symbole, quand on arrive à la dernière feuille on repart sur la branche voisine. [...]

[...] Une autre technique peut conventionnelle consiste à remplacer les par les opérateurs par et les lettres par -1. Au final, la phrase logique devrait donner -1. [...]