Maths discrètes

Qu’est ce que la négation?

Le contraire d’une proposition [¬]

Qu’est-ce qu’une conjonction?

Donne vrai si deux propositions sont vrai [^]

Qu’est-ce qu’une dijonction?

Donne vrai si l’une des deux propositions est vrai [∨].

Qu’est-ce que la dijonction exclusive?

Donne vrai si l’une des deux propositions est vrai, mais pas les deux [(+)].

Vx, P(x) est similaire à?

P ^ Q ^…

Ex tels que P est similaire à?

P v Q v …

Qu’est ce qu’est les lois de la négation des qualificateurs

1. -(Vx, P(x)) = Ex tels que -P(x)

2. -(Ex tels que P(x)) = Vx, -P(x)

Qu’est-ce que les lois de deMorgan?

1. -(P^Q) = -P v -Q

2. -(P v Q) = -P ^ -Q

Qu’est-ce que l’implication?

Si une proposition est vrai, alors celle-ci aussi [P → Q]

Qu’est-ce que la loi de l’implication?

P → Q = - (P ^ -Q)

Qu’est-ce que la réciproque?

Le contraire d’une implication : P → Q = Q → P

Qu’est-ce qu’une contraposé?

1. La négation d’une implication : P → Q = -Q → -P

Qu’est-ce que la biconditionnelle?

Quand deux propositions on la même valeurs [P <=> Q]

Exemple de l’associativité

(P ^ Q) ^ R = P ^ (Q ^ R)

Exemple de distributivité

P ^ (Q v R) = (P ^ Q) v (P ^ R)

Exemple de commutativité

P v Q <=> Q v P

Exemple de double négation

--P = P

Exemple d’idempotence

P ^ P = P

Exemple de contradiction

P ^ -P = faux

Exemple de contre-exemple

-(P → Q) <=> P ^ -Q

Qu’est-ce qu’une preuve par contraposé (et ses cas)?

1. On prend l’inverse de l’énoncé au complet

   • Si __, alors __

Qu’est-ce qu’une preuve cas-par-cas (et ses cas)

1. On divise la grosse équation en cas séparément pour vérifier que chaque cas est vrai

• Soit … un entier, alors (grosse équation)

• Si >, montre que chaque cas est >

• Si entier ou est un multiple, montre quand n est pair et impair.

Qu’est-ce qu’une preuve par l’absurde (et ses cas)

1. On suppose que le contraire d’une parti de l’énoncé est vrai, on essai alors de la contredire

• Pour irrationel (On l’a transforme en rationnel a/b, b \= 0, si les a et b sont pair, contradiction!)

Qu’est-ce qu’une preuve bicondotionnelle (et ses cas)?

1. Il faut prouver un côté en supposant que l’autre est vrai, de chaque côté.

• … si et seulement si …

(Cas spécial) Comment montrer que logc^d est irrationel?

1. Dire qu’il est rationnel par l’absurde

2. Logc^d = a/b

3. C^a/b = d

4. C^a = d^b

5. Si les deux sont impair et pair, impossible!

(Cas spécial) Comment prouver que Racine carré de x est irrationel

1. Est rationnel

2. Racine carré de x = a/b

3. X = a²/b²

(Preuve spéciale) Quoi faire quand prouver pair et impair?

Pair : n = 2k

Impair : n = 2k+1

Que veut dire a|b?

a divise b (b/a) ou ka = b

Quelles sont les propriétés de la divisibilité?

1. Loi des sommes : Si a|b et a|c, a|b+c

2. Loi des produits : Si a|b, a|bc et ac|bc

3. Loi de transitivité : Si a|b et b|c, a|c

4. Lemme d’Euclide : Si p|ab (nombre premier), p|a et p|b

(Cas spécial) Comment prouver qu’un nombre est premier?

Trouver le premier plus petit k qui divise le nombre, si k² > que le nombre, il est premier.

Propriété du PGCD

1. PGCD(a,b) = PGCD(b,a)

2. PGDC(a,b) |a et |b

Comment trouver le PGCD avec exposant?

1.Prendre le plus grand nombre premier le divise chaque PGCD.

2. Prendre le plus petit exposant et les aditionner.

Comment teouver PPCM avarc exposant?

Même que PGCD mais additioner les plus grand exposant.

Comment trouver le PCGD avec l’agorithme d’Euclide?

1. PGCD(a,b) => a = q x b + r (quotient et reste)

2. b = q x r1 + r2

3. Faire cela jusqu’à ce que le dernier r = 0, le premier r est la réponse.

Qu’est-ce que l’identité de Bézout?

PGCD(a,b) = ax + by = c

Comment utiliser le corollaire de Bézout?

1. Prendre l’avant dernière ligne d’Euclide.

2. Mettre r = a - b x q

3. Remplacer bq par ligne supérieur.

4. Remplacer jusqu’attend que x(a du PGCD) + y(b du PGCD)

Comment écrire “a et b sont congrues modulo m”?

• a = b (mod m), m divise a avec un reste b

• m | a - b

• a - b = km

Quelles sont les propriétés de l’arithmétique modulaire?

1. a = a (mod m)

2. Si a = b (mod m), alors b = a (mod m) [Symétrie]

3. Si a = b (mod m) et b = c (mod m), alors a = c (mod m) [Transitivité]

4. a est toujours congrues m à une valeur unique r

La ressemblance avec divisibilité et congruence modulo?

• m | a = a = 0 (mod m)

• m / a = a = n (mod m)

Propriété algébrique de la congruence modulo?

1. Si a = b (mod m) et a’ = b’ (mod m), alors a + a’ = b + b’ (mod m) [Loi des sommes]

2. Si a = b (mod m), alors ac = bc (mod m)

3. Si a = b (mod m) et c = d (mod m), alors ac = ad (mod m) [Loi des produits]

4. Si a = b (mod m), alors a² = b² (mod m) [Loi des puissances]

SEULEMENT QUAND m EST CONSTANT!!

Quelle règle pour les égalités modulos ne s’applique pas?

La divisibilité entre deux modulo. À la place, on le muliplie par son inverse modulaire!

Qu’est-ce que des inverses modulaires et comment le trouver?

• Si a x b = 1 (mod m), et b sont des inverses

• Trouver facilement avec PGCD(a,m) = 1

Comment trouver si une solution est unique modulo m?

Si la solution n’a pas d’inverse modulaire