[PDF] MAT210 Logique et mathématiques discrètes : Cours 1

View - Download MAT210 Logique et mathématiques discrètes : Cours 1

Previous PDF

Next PDF

Chapitre 2Raisonnements, preuves et théorie desensembles Ce document contient certains exercices qui seront faits enéquipe lors de la deuxième semaine du cours de MAT210.

2.1 Raisonnements valides

La section 1.6 du livre de référenceDiscrete Mathematics and its applications, Seventh Editionde

K. H. Rosen présente lesrègles d"inférence. La tableau 1 de la page 72 résume les principales. Ces

formes de raisonnement sont valides: elles garantissent lavéracité de la conclusion quand toutes les

prémisses sont vraies.

Il est important de distinguer la validité d"un raisonnement et la valeur de vérité de la conclu-

sion. Il existe quatre possibilités. Voici un exemple de chacune, tirés du " Petit cours d"autodéfense

intellectuelle» de Normand Baillargeon (page 55).

1. Le raisonnement est valide et la conclusion est vraie.

Tous les hommes sont mortels.

Socrate est un homme.

Donc Socrate est mortel.

2. Le raisonnement est valide mais la conclusion est fausse.

Tous les hommes sont bleus.

Socrate est un homme.

Donc Socrate est bleu.

3. Le raisonnement est invalide et la conclusion est fausse.

Quelques hommes sont bleus.

Socrate est un homme.

Donc Socrate est bleu.

4. Le raisonnement est invalide mais la conclusion est vraie.

Certains hommes sont mortels.

Socrate est un homme.

Donc Socrate est mortel.

1

2 CHAPITRE 2. RAISONNEMENTS, PREUVES ET THÉORIE DES ENSEMBLES

Exemple 2.1

Analysez chacun des raisonnements suivants pour voir s"il est valide ou non. Indiquez sa structure à

l"aide de connecteurs logiques. Si le raisonnement est valide, tentez de trouver sa structure dans le

tableau de la page 72. (a) Exemple tiré du "petit cours d"autodéfense intellectuelle» cité plus haut. Si les structuresde base d"une société sont justes, les citoyens ne se rebellentpas. Les citoyens de notre société ne se rebellent pas. Donc, les structuresde base de notre société sont justes.

Solution :

Ce raisonnement (invalide) est de la forme

p→q q

Invalide?p

oùpdésigne "les structures de base de notre société sont justes» etqdésigne "les citoyens ne se rebellent pas».

Ou encore, en utilisant les quantificateurs

?xP(x)→Q(x) Q(a)

Invalide?P(a)

oùP(x) désigne "les structures de base de la sociétéxsont justes» etQ(x) désigne "les citoyens de la sociétéxne se rebellent pas». Avecaqui désigne "notre société» en particulier. Ce raisonnementest invalide. Eneffet,lesprémisses (p→q)et(q)peuventêtretouteslesdeux vraies sans que la conclusionpne soit vraie comme le montre la table de vérité suivante. p qp→q(p→q)?q FVVV Voici un autre raisonnement qui présente la même faille.

S"il pleut, alors les trottoirssont mouillés.

Les trottoirssont mouillés.

Donc, il pleut.

Cette erreur de logique est assez courante, mais elle n"est pas toujours aussi facile à détecter!

(b) Encore le trottoir...

S"il pleut, alors les trottoirs sont mouillés.

Les trottoirs ne sont pas mouillés.

Donc, il ne pleut pas.

Geneviève Savard, ÉTS, 2014

2.1. RAISONNEMENTS VALIDES3

Solution :

Ce raisonnement est valide. Il s"agit d"unmodus tollens. p→q ¬q

Valide

?¬p oùpdésigne "il pleut» etqdésigne "les trottoirs sont mouillés». Exercice 2.1Analysez chacun des raisonnements suivants pour voir s"il est valide ou non. Indiquez

sa structure à l"aide de connecteurs logiques. Si le raisonnement est valide, tentez de trouver sa

structure dans le tableau de la page 72.

(a) S"il pleut, alors les trottoirs sont mouillés. Il ne pleut pas. Donc les trottoirs ne sont pas

mouillés. (b) S"il pleut, alors les trottoirs sont mouillés. Il pleut.Donc les trottoirs sont mouillés.

(c) Si tu fais tous les exercices du livre de référence, tu réussiras le cours. Tu as réussi le cours.

Donc, tu as fais tous les exercices du livre.

(d) Ou bien la science peut expliquer ce phénomène, ou bien c"est un miracle. La science ne peut

expliquer ce phénomène. C"est donc un miracle.

(e) Les grandes villes ont des gratte-ciel. Montréal a plusieurs gratte-ciel. Donc Montréal est une

grande ville. (f) Ce sandwich ne contient pas de viande ou contient des champignons. Ce sandwich contient de la viande ou de la mayonnaise. Donc ce sandwich contient des champignons ou de la mayonnaise.

Geneviève Savard, ÉTS, 2014

4 CHAPITRE 2. RAISONNEMENTS, PREUVES ET THÉORIE DES ENSEMBLES

2.2 Typesdepreuve

Définition 2.1Unthéorèmeest un énoncé que l"on peut démontrer.

Unedémonstration(on dit aussi une preuve) consiste à déduire que l"énoncé estvrai en utilisant

un raisonnement logique (règles d"inférence) reposant surdesaxiomes(énoncés considérés vrais

sans démonstration) ou sur des théorèmes déjà démontrés. Définition 2.2Uneconjectureest une proposition que l"intuition ou l"observation nous porte à

croire vraie, mais qui n"a pas encore été formellement démontrée (ni réfutée). Si elle est démontrée,

la conjecture devient un théorème.

Le travail des mathématiciens consiste à formuler des conjectures puis à démontrer qu"elles

sont vraies (ou fausses). L"équivalent en informatique consiste à inventer un algorithme, ou un

programme, puis à démontrer qu"il produit toujours le résultat attendu.

Au cours de la session, vous serez amenés à lire différentes preuveset à en produire vous-mêmes.

Démontrer un résultat n"est pas facile; il n"y a pas de recette magique. Par contre, connaître les

principaux type de preuves est un atout précieux.

Types depreuves

•Preuve directedep→→→q Onsuppose quepest vrai et l"on démontre (en se basant sur des définitions, des axiomes, des

théorèmes déjà démontrés et des règles d"inférence), qu"ils"en suit forcément queqest vrai

aussi. •Preuve directede???x???U P(x)→→→Q(x) On suppose quexest un élément arbitraire deUtel queP(x) est vrai. On démontre qu"il s"en suit forcément queQ(x) est vrai aussi. •Preuve indirectedep→→→q, aussi appelée preuve par contraposée. On suppose queqest faux et l"on démontre qu"il s"en suit forcément quepest faux.

¬q→¬p

?p→q •Preuve par casdep→→→q

On démontre quepentraîne un nombre fini de possibilités. On étudie chacune séparément

pour vérifier qu"elle entraîneq. On conclut donc quepentraîneq. p→(p1?p2?...?pn) p

1→q

p

2→q

p n→q ?p→q

Geneviève Savard, ÉTS, 2014

2.2. TYPES DE PREUVE5

•Preuve par levidedep→→→q On montre quepest faux. Ainsi, l"implicationp→qest vraie (peu importe la valeur deq). ¬p ?p→q •Preuve trivialedep→→→q On montre queqest vrai. Ainsi, l"implicationp→qest vraie (peu importe la valeur dep). q ?p→q •Preuve par contradictiondep, aussi appelée preuve par l"absurde On suppose quepest faux et l"on montre que cela entraîne une contradiction.Ainsi,pdoit

être vrai.

¬p→F

?p •Preuve constructivede???x???U P(x) Il suffit de trouver un élémentade l"ensembleUtel queP(a) est vrai. a?U P(a) ??x?U P(x) •Preuve exhaustivede???x???U P(x) Si l"ensembleUpossède un nombre fini d"éléments, disonsU={x1,x2, ... ,xn}, et que l"on démontre que pour chacun d"eux la propriétéPest vraie, alors on peut conclure que la propriétéPest vraie pour tous les éléments deU.

U={x1,x2, ... ,xn}

P(x1)?P(x2)?...?P(xn)

??x?U P(x) •Preuve par récurrencede???n???N P(n) Pour démontrer que la propriétéPest vraie pour tous les nombres naturels, on démontre qu"elle est vraie pourle nombre 0 (cas de base), et que si elleest vraie pour un nombren, alors elle est aussi vraie pour le nombre suivant (étape de récurrence). P(0) ?n?N?P(n)→P(n+1)? ??n?N P(n) De nombreux exemples de preuves de chaque type seront donnésen classe, en commençant par

des preuves assez courtes et "simples» en début de session. Les preuves par récurrence (Mathema-

tical Inductionen anglais) font l"objet du chapitre 5 du livre de référence.

Geneviève Savard, ÉTS, 2014

6 CHAPITRE 2. RAISONNEMENTS, PREUVES ET THÉORIE DES ENSEMBLES

2.3 Théorie des ensembles

Définition 2.3Unensembleest une collection non ordonnée d"objets. Les objets sont appelés élémentsde l"ensemble et on dit qu"ils appartiennentà l"ensemble.

Exemple 2.2

F={2,π, 7}

L"ensembleFcontient 3 éléments,πappartientàFmais 3 n"appartient pas àF. |F|=3

π?F

3?F On peut décrire un ensembleen extension(énumération de ses éléments)

A={5, 7, 911}B={1, 8, 2764}

ouen compréhension, comme ceci:

Rappel sur les ensembles de nombres

Ensemblevide:?={}

Ensembledes nombres naturels:N={ 0,1,2,3,...}

Ensembledes nombres entiers:Z={ ...,-2,-1,0,1,2,...}

Ensembledes nombres rationnels:Q=?p

q|p?Z,q?Zetq?=0?

Ensembledes nombres réels:R

Ensembledes nombres complexes:C=?

a+bi|a?Retb?R?

Geneviève Savard, ÉTS, 2014

2.3. THÉORIE DES ENSEMBLES7

Définition 2.4 Égalité d"ensembles

Deux ensembles sont dits égaux si et seulement si ils contiennent exactement les mêmes éléments.

Définition 2.5L"ensembleAestsous-ensemblede l"ensembleBsi et seulement si tous les éléments deAsont aussi des éléments deB.

A?B???x?x?A→x?B?

L"ensembleAestsous-ensemble strictde l"ensembleBsi et seulement si tous les éléments deA sont aussi des éléments deBetAn"est pas égal àB.

A?B??A?B?A?=B

Théorème 2.1Pour tout ensembleA, on a

1.??A 2.A?A

Les preuves seront vues en classe.

Définition 2.6Leproduit cartésiendes ensemblesAetB, notéA×××B, est l"ensemble de tous les

couples (paires ordonnées) dont le premier élément appartient àAet le second, àB.

A×B=?(a,b)|a?Aetb?B?

On généralise cette définition au produit cartésien denensembles: A

1×A2×...×An=?(a1,a2,...,an)|a1?A1, ...,an?An?

Exemple 2.3

Décrivez en extension les produits cartésiensA×BetB×A, oùA={0,1,2} etB={a,c}. Définition 2.7Unerelationentre les ensemblesAetBest un sous-ensemble du produit cartésien

A×B

Nous étudierons les propriétés des relations au cours 11.

Geneviève Savard, ÉTS, 2014

8 CHAPITRE 2. RAISONNEMENTS, PREUVES ET THÉORIE DES ENSEMBLES

Définition 2.8L"ensemble des parties deA, noté?(A), est l"ensemble de tous les sous-ensembles deA.

B??(A)??B?A

Exemple 2.4

Décrivez l"ensemble des parties deA, oùA={0,1,2}. nSous-ensembles deAayantnéléments nombre de sous-ensembles 0?1

1 {0},{1},{2} 3

2 {0,1},{0,2},{1,2} 3

3 {0,1,2} 1

Ainsi,?(A) contient 8 éléments, soit 2|A|.

Exemple 2.5

Décrivez l"ensemble des parties deA, oùA={0,1,2,3}. nSous-ensembles deAayantnéléments nombre de sous-ensembles 0?1

1 {0},{1},{2},{3} 4

2 {0,1},{0,2},{0,3},{1,2},{1,3},{2,3} 6

3 {0,1,2},{0,1,3},{0,2,3},{1,2,3} 4

4 {0,1,2,3} 1

Ainsi,?(A) contient 16 éléments, soit 2|A|.

Exemple 2.6

Décrivez l"ensemble des parties deA, oùA={}=?. nSous-ensembles deAayantnéléments nombre de sous-ensembles 0?1 Ainsi, bien queAne possède aucun élément,?(A) en contient un:?(A)=???

Geneviève Savard, ÉTS, 2014

2.3. THÉORIE DES ENSEMBLES9

2.3.1 Représentation de sous-ensemblespar trains de bits

On peut représenter un sous-ensemble d"un ensemble à l"aided"un train de bits. Pour ce faire, il

faut fixer un ordre pour les éléments deA, puis construire le train de bits en posant 1 à la positionj

si le j-ième élément appartientau sous-ensemble et 0 sinon. Par exemple, siA={0,1,2,4}, en choisissant l"ordre croissant, on obtient les représentations suivantes. train de bits sous-ensemble deA 0000? 1010
{0,2}=B 0011 {2,3}=C 0010 {2}=D 1011
{0,2,3}=E 1100
{0,1}=F peuvent alors être effectuées directement sur les trains debits correspondants.

1010?0011=0010

B∩C=D

1010?0011=1011

B?C=E

0011=1100

C=F

2.3.2 Opérations sur les ensembles

SoitUl"ensemble universeletAetBdessous-ensemblesdeU. Lesopérationssuivantesgénèrent des sous-ensembles deU.

Union:A?B={x?U|x?Aoux?B}

Intersection:A∩B={x?U|x?Aetx?B}

Différence:A-B={x?U|x?Aetx??B} (Souvent notéA\B) Différence symétrique:A?B={x?U|x?(A-B) oux??(B-A)}

Complément:

A={x?U|x??A}=U-A

Geneviève Savard, ÉTS, 2014

10 CHAPITRE 2. RAISONNEMENTS, PREUVES ET THÉORIE DES ENSEMBLES

2.3.3 Table des propriétés des opérations sur les ensembles

PropriétéNom

A?? =AIdentité

A∩U=A

A?U=UDomination

A∩? = ?

A?A=AIdempotence

A∩A=A

A?B=B?ACommutativité

A∩B=B∩A

A?(B?C)=(A?B)?CAssociativité

A∩(B∩C)=(A∩B)∩C

A?(B∩C)=(A?B)∩(A?C)

A?B=A∩BLois de De Morgan

A∩B=A?B

A?(A∩B)=AAbsorption

A∩(A?B)=A

A?A=UComplément

A∩A= ?

Exercice 2.2Vrai ou faux.

(a)N?Z (b)N?Z (c)N?Z (d)??N (e)??N (f)N?N (g)??N (h) {1,2}??({1,2,3}) (i) {1,2}??({1,2,3}) (j) {{1}}??({1,2,3})

Geneviève Savard, ÉTS, 2014

2.3. THÉORIE DES ENSEMBLES11

Exercice 2.3Vrai ou faux.

(a)x?{x} (b)x?{x} (c) {x}?{x} (d) {x}?{x} (e) {x}?{{x}} (f)??{x} (g)??{x} Exercice 2.4Le diagramme de Venn de la figure 1 représente fidèlement les ensemblesA,B,C,D etU. BA C D 2 3 4 75
6 8 19 U

FIG. 2.1 Diagramme de Venn

Décrivez en extension les ensembles suivants.

(a)A?B (b)A∩B (c)A∩ C (d)A∩C∩D (e)?(B) (f) U (g) A?C (h)B∩D (i)C-A (j)D-B (k)A?C (l)D×B

Geneviève Savard, ÉTS, 2014

12 CHAPITRE 2. RAISONNEMENTS, PREUVES ET THÉORIE DES ENSEMBLES

Exercice 2.5Chacune des expressions suivantes désigne un ensemble qui peut être décrit par une

Indiquez la propriété utilisée à chaque étape. La première simplification est donnée en exemple.

(a)

A∩B∩¯C?¯A∩B

A∩B∩¯C?¯A∩B

A∩B∩¯C∩¯A∩BDe Morgan

=(A∩B∩¯C)∩(¯A∩B) Complément du complément: A=A =(A∩¯A)∩B∩¯C∩BCommutativité et associativité de l"intersection =?Domination: l"intersection avec l"ensemble vide donne l"ensemble vide. (b)

A∩B∩C?C

(c)A∩(H?D?A) (d) (A∩B)?¯B (e) (

A?B)?¯B

(f) (A?¯B)?(C?¯A)

Vérifiez ensuite vos réponses (b) et (d) avec un tableau d"appartenance (voir page 132 du manuel).

Merci à mon collègue Stéphane Lafrance pour le partage de sonfichier contenant la table des propriétés de l"union et l"intersectinet certainesdéfinitions!

2.4 Fonctions

Définition 2.9Unefonctionfd"un ensembleAvers un ensembleBest une règle qui, à chaque

élémentade l"ensembleA, associe un et un seul élémentbde l"ensembleB. Cet élémentbest noté

f(a). On écrit alors parfois (a,b)?f. La notation usuelle pour désigner une fonctionfd"un ensembleAvers un ensembleBest f:A-→B L"ensembleAest appelé ledomainede la fonctionf, noté Dom(f), et le sous-ensemble deBformé des éléments atteints parfest appelé l"imagedef, noté Im(f).

Im(f)=?b?B|?a?A,f(a)=b??B

Geneviève Savard, ÉTS, 2014

2.4. FONCTIONS13

Par ailleurs, on peut aussi voir une fonctionfdeAversBcomme un sous-ensemble du produit cartésienA×Bayant la propriété suivante: ?a?A,?!b?B, (a,b)?f où le symbole?! désigne "il existe un et un seul». Définition 2.10Soitf:A-→Bune fonction. On dit que fest injectivesi elle n"associe jamais la même image à deux éléments distincs: ?a1?A,?a2?A,(a1?=a2)→?f(a1)?=f(a2)?

fest surjectivesi son image est l"ensembleBau complet, c"est-à-dire si tous les éléments deB

sont atteints: ?b?B,?a?A,f(a)=b fest bijectivesi elle est injective et surjective: ?b?B,?!a?A,f(a)=b Exercice 2.6Déterminez si la relationfest une fonction ou non. Tracez aussi son graphe sagittal. De plus, sifest une fonction, déterminez si elle est injective, surjective ou bijective.

Ici,L={a,b,c,d,e} ,C={1,2,3,4} etD={1,2,3,4,5}

(a)f={(1,a),(2,d),(3,c),(4,e)}?C×L (d)f={(1,a),(2,a),(3,a),(4,a)}?C×L

Geneviève Savard, ÉTS, 2014

14 CHAPITRE 2. RAISONNEMENTS, PREUVES ET THÉORIE DES ENSEMBLES

Exercice 2.7Déterminez si la fonctionfest injective, surjective ou bijective. T

8désigne ici l"ensemble des trains de bits de longueur 8.

(a)f:T8-→N,f(t)=nombre de 0 dans le train de bitst. (b)f:T8-→T8,f(t)=¯tle train formé en prenant le complément de chaque bit det. (c)f:T8-→T8,f(t)=(t?11110000) (d)f:T8-→{0,1,2,3,...,8},f(t)=nombre de 1 dans le train de bitst. (e)f:{0,1,2,3,...,255}-→T8,f(n)=t, oùtest la représentation binaire du nombren. (f)f:T8-→N,f(t)=n, oùnest la valeur du nombre représenté en binaire par le traint.

(g)f:R-→Z,f(x)=?x?, où?x?est le plus petit entier supérieur ou égal àx(fonction plafond ou

ceiling function) . Les notions decompositionde fonctions, defonction inverse, degraphed"une fonction, de

fonctioncroissante ou décroissanteont été vues en MAT145. Consultez la section 2.3 du manuel

de référence pour plus de détails.

Geneviève Savard, ÉTS, 2014

quotesdbs_dbs35.pdfusesText_40

[PDF] discrete mathematics and its applications 7th edition solutions

[PDF] introduction to computer science pdf

[PDF] computer science courses pdf

[PDF] programming books pdf

[PDF] computer pdf

[PDF] séance racisme ce2

[PDF] evaluation discrimination cycle 3

[PDF] séquence le respect cycle 3

[PDF] sociologie du genre pdf

[PDF] genre et développement durable pdf

[PDF] discrimination ethnique ? l embauche

[PDF] qu'est-ce que la discrimination positive

[PDF] discrimination ? l'école exemple

[PDF] discrimination ? l'école statistique

[PDF] discrimination ? l'école exposé